|
6级 树定义： 节点，根节点，父节点，子节点，叶子节点，兄弟节点 度，树的度 层，树的深度 边（边长），树的高度 树构造： 存树，指针结构体/数组（二叉树） struct node{ int val; vector<node*> chi; }; node root=new node; struct node{ int val; vector<node*> chi; node(int a){ val=a; } }; node root=new node;//无构造 node root=new node(0);//有构造 树遍历： struct node{ int val; node *l,*r; node(int a){ val=a; l=nullptr; r=nullptr; } } root=new node(0); 先序遍历、中序遍历、后序遍历 void xx(node *p){ if(p==nullptr) return ; cout<<p->val; xx(p->l); xx(p->r); } //栈-递归-深度优先 层序遍历 //队列-广度优先 void cx(node *p){ queue<node*> q; q.push(p); while(!q.empty()){ node *u=q.front(); q.pop(); if(u->l!=nullptr) q.push(u->l); if(u->r!=nullptr) q.push(u->r); cout<<u->val; } } 哈夫曼编码：压缩数据 字符出现频率高的用短码，字符出现频率低的用长码 构造哈夫曼树： 1、统计字符出现频率 2、将<字符,频率>存入可排序的结构中 3、反复进行以下操作，直到剩下最后一个数据 a、取出两个最小值 b、拼接成一个新数据 c、放回原结构中 4、最后剩下的数据，就是哈夫曼树的根节点 输入一个文章，通过哈夫曼编码计算每个字符的编码值 struct HuffmanNode{ char val; int cnt; HuffmanNode *l,*r; HuffmanNode(char c,int a){ val=c;cnt=a; l=r=nullptr; } }; map<char,int> m; struct cmp{ bool operator()(HuffmanNode *a,HuffmanNode *b){ return a->cnt>b->cnt;//需要小顶堆，频率大的在前小的在后 } }; HuffmanNode* buildHuffmanTree(){ while(pq.size()>1){ //拿两个 HuffmanNode *a=pq.top();pq.pop(); HuffmanNode *b=pq.top();pq.pop(); //合并 HuffmanNode *c=new HuffmanNode('@',a->cnt+b->cnt); c->l=a; c->r=b; //放回去 pq.push(c); } return pq.top(); } void printHCodes(HuffmanNode *p,string str){ if(p->val!='@'){ cout<<p->val<<":"<<str<<endl; return ; } if(p->l!=nullptr) printHCodes(p->l,str+'0'); if(p->r!=nullptr) printHCodes(p->r,str+'1'); } int main(){ string s; cin>>s; //1、统计字符出现频率 for(int i=0;s[i];i++) m[s[i]]++; /*2、频繁的插入删除数据的动态排序，堆排序最合适，所以priority_queue适用于当前情景。 priority_queue<类型> 默认大顶堆（从小到大排序） priority_queue<类型,vector<类型>,排序规则> */ priority_queue<HuffmanNode*,vector<HuffmanNode*>,cmp> pq; //for(map<char,int>::iterator i=m.begin();i!=m.end();i++) for(auto i=m.begin();i!=m.end();i++){ HuffmanNode *p=new HuffmanNode(i->first,i->second); pq.push(p); } HuffmanNode *root = buildHuffmanTree(); printHCodes(root,""); return 0; } 输入输出，数据类型，符号，字符数组，字符串，函数，递归，递归记忆化，结构体，文件操作，排序算法 输入输出：cin、cout、getchar、putchar、getline、cin.getline、scanf、printf getchar putchar 字符 getline 字符串 cin.getline 字符数组 scanf 格式化输入 printf 格式化输出 精度 double x; cout<<fixed<<setprecision(3)<<x; printf("%.3lf",x); %[标识][宽度][.精度][类型] 标识： 默认右对齐 0 前边补0 + 正数显示正号 - 左对齐 空格 不写默认右对齐 printf("%10d\n",55); printf("%+10d\n",55); printf("%-10d\n",55); printf("%010d\n",55); 宽度：一个整数，代表【至少】占位宽 .精度：一个整数，表示保留多少位小数 类型： int %d long long %ld double %lf float %f char %c bool %b char* %s 字符数组 string是c++的类型，printf是c语言的函数，不兼容 string s="abc"; printf("%s",s.c_str());//将s转换成char* 输出 int a,b; scanf("%d,%d",&a,&b); name1 is abc ddd name2 char *a,*b; scanf("%s is abc ddd %s",a,b); char c[100]; cin.getline(c,100); string s; getline(cin,s); getline 与 cin混用，清除垃圾 cin.ignore(); 字符数组相关函数 strlen strcmp等 https://noicode.online/a/jichuyufa/20240511/205.html 字符串相关函数 https://noicode.online/a/zifuchuanstring/20240512/259.html https://noicode.online/a/zifuchuanstring/20240512/258.html https://noicode.online/a/zifuchuanstring/20240512/257.html https://noicode.online/a/zifuchuanstring/20240512/256.html 函数类型，函数名，参数，返回值，函数体 全局变量，局部变量 形式参数，实际参数 值传递，引用传递 void swap(int &a,int &b){ int *c=a; a=b; b=c; } 递归函数：爬楼梯，斐波那契数列，汉诺塔，全排列 //1205 void hnt(int n,char a,char b,char c){ if(n==1) cout<<a<<"->"<<n<<"->"<<b<<endl; else{ hnt(n-1,a,c,b); //cout<<a<<"->"<<n<<"->"<<b<<endl; printf("%c->%d->%c\n",a,n,b); hnt(n-1,c,b,a); } } //1199 void qpl(string str,int st,int en){ if(en==st){ cout<<str<<endl; return ; } for(int i=st;i<=en;i++){ swap(str[i],str[st]); qpl(str,st+1,en); } } //递归记忆化：算过的数据保存下来避免重算浪费时间 //计算斐波那契数第60项 int feib(int n){ if(n<=2) return 1; return feib(n-1)+feib(n-2); } //记忆化 int fb[10000]={0,1,1}; int feib(int n){ if(fb[n]!=0) return fb[n]; fb[n]=feib(n-1)+feib(n-2); return fb[n]; } //文件操作：文件读取，输入输出重定向 //文件读取 ifstream fin("xxx.in");//通过fin指令从xxx.in中读取数据 ofstream fout("xxx.out");//通过fout指令将数据写入到xxx.out中，默认重新写入，覆盖原内容 int a,b; fin>>a>>b; fout<<a+b; fin.close(); fout.close(); //ofstream fout("xxx.out",ios::app);//追加写入 //输入输出重定向 freopen("xxx.in","r",stdin); freopen("xxx.out","w",stdout);//重新写入 int a,b; cin>>a>>b; cout<<a+b; fclose(stdin); fclose(stdout); //freopen("xxx.out","a",stdout);//追加写入 冒泡、选择、插入、计数、快速 void qsort(int left,int right){ if(left>=right) return ; int t=a[left]; int i=left,j=right; while(i!=j){ while(i<j&&a[j]<=t) j--; while(i<j&&a[i]>=t) i++; if(i!=j) swap(a[i],a[j]); } swap(a[left],a[i]); qsort(left,i-1); qsort(i+1,right); } 归并 int a[1000]; void marsort(int left,int right){ if(left>=right) return ; int mid=(left+right)/2; marsort(left,mid); marsort(mid+1,right); hb(left,mid,right); } 将两个有序的序列合并成一个 void hb(int left,int mid,int right){ int b[1000]={}; int i=left,j=mid+1,t=0; while(i<=mid&&j<=right) if(a[i]<a[j]) b[t++]=a[i++]; else b[t++]=j++; while(i<=mid) b[t++]=a[i++]; while(j<=right) b[t++]=a[j++]; t=0; for(int k=left;k<=right;k++){ a[k]=b[t++]; } } 快速幂，差分数组，二分法（二分查找，二分答案），高精度算法，dfs，bfs，dijstra，floyd，贪心，动归 栈stack、队列queue、优先队列priority_queue stack push pop top queue push pop front priority_queue push pop top 有固定的进出逻辑 字典map，集合set，可重复字典multimap，可重复集合multiset 自动有序，数据存储顺序与存入的先后顺序无关 数组类模版array，双向队列deque，向量vector，单向链表forward_list，双向链表list 哈希 kmp trie字典树 ac自动机 (责任编辑：admin) |