[问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作：
按先序序列构造一棵二叉链表表示的二叉树T；对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；求二叉树的深度/结点数目/叶结点数目；(选做)将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） ABC DE G F则输出结果为
先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG[选作内容] 采用非递归算法实现二叉树遍历。 CODE:
#include <iostream> #include <cstdio> using namespace std; typedef struct TNode { char data; struct TNode *l,*r; } TNode,*Tree; void CreatBiTree(Tree &t) { char ch; ch=getchar(); //注意字符可能是空格所以不能用cin if(ch==' ') t=NULL; else { t=new TNode; t->data=ch; CreatBiTree(t->l); CreatBiTree(t->r); } return; } void Preordering(Tree t) { if(t!=NULL) { cout<<t->data; Preordering(t->l); Preordering(t->r); } } void Middleorder(Tree t) { if(t!=NULL) { Middleorder(t->l); cout<<t->data; Middleorder(t->r); } } void Postorder(Tree t) { if(t!=NULL) { Postorder(t->l); Postorder(t->r); cout<<t->data; } } typedef struct QNode { Tree base; struct QNode *next; } QNode,*QueuePtr; typedef struct { QueuePtr f,r; } LinkQueue; void InitQueue(LinkQueue &q) { q.f=q.r=new QNode; q.f->next=NULL; return; } void Qpush(LinkQueue &q,Tree t) { QueuePtr p; p=new QNode; p->base=t; p->next=NULL; q.r->next=p; q.r=p; return; } bool Empty(LinkQueue q) { return q.f==q.r; } void arrangement(Tree t) { LinkQueue q; InitQueue(q); if(t) Qpush(q,t); while(!Empty(q)) { q.f=q.f->next; Tree k; k=new TNode; k=q.f->base; cout<<k->data; if(k->l) Qpush(q,k->l); if(k->r) Qpush(q,k->r); } cout<<endl; return; } int Deap(Tree t) { if(!t) return 0; int m,n; m=Deap(t->l); n=Deap(t->r); return m>n?m+1:n+1; } int Node(Tree t) { if(!t) return 0; else return Node(t->l)+Node(t->r)+1; } int Leaf(Tree t) { if(!t) return 0; else{ if(!t->l&&!t->r) return 1; else return Leaf(t->l)+Leaf(t->r); } } void Swap(Tree &t) { Tree root; root=t->l; t->l=t->r; t->r=root; if(t->l) Swap(t->l); if(t->r) Swap(t->r); } int main() { Tree t; CreatBiTree(t); cout<<"先序："; Preordering(t); cout<<endl; cout<<"中序："; Middleorder(t); cout<<endl; cout<<"后序："; Postorder(t); cout<<endl; cout<<"层次："; arrangement(t); cout<<"树的深度："; cout<<Deap(t)<<endl; cout<<"结点数目："; cout<<Node(t)<<endl; cout<<"叶结点数目："; cout<<Leaf(t)<<endl; cout<<"左右子树交换位置后："<<endl; Swap(t); cout<<"先序："; Preordering(t); cout<<endl; cout<<"中序："; Middleorder(t); cout<<endl; cout<<"后序："; Postorder(t); cout<<endl; cout<<"层次："; arrangement(t); return 0; }[问题描述] 一电文，有若干个不同字符，要求从终端输入这些不同字符及其出现的频率，然后对这些字符进行哈夫曼编码，并输出。 ［测试数据］ 利用教材P.139 例5.2中的数据调试程序 (可自己设定测试数据)。 [选作内容] 1、打印出该哈夫曼树 2、若从终端输入任意一段电文（假设仅为26个大小写英文字母）,试编程高效地求出该段电文的哈夫曼编码。 提示：如何快速统计不同字符的出现频率 3、译码：将上述1的编码结果还原成电文。 样例输入：
aabbcdeffff样例输出：
各个字母出现的次数为： a:2 b:2 c:1 d:1 e:1 f:4 1 a 2 0 0 0 2 b 2 0 0 0 3 c 1 0 0 0 4 d 1 0 0 0 5 e 1 0 0 0 6 f 4 0 0 0 每次连接的结点: 3 4 7 5 1 8 2 7 9 8 6 10 9 10 11 1 a 2 8 0 0 2 b 2 9 0 0 3 c 1 7 0 0 4 d 1 7 0 0 5 e 1 8 0 0 6 f 4 10 0 0 7 2 9 3 4 8 3 10 5 1 9 4 11 2 7 10 7 11 8 6 11 11 0 9 10 Huffman Code: a:101 b:00 c:010 d:011 e:100 f:11 String Huffman Code: 101101000001001110011111111 写一串由上面Huffman Code组成的编码,输入#结束: 1110001010101100 fecadb 1111 ff #CODE:
#include <iostream> #include <algorithm> #include <cstring> #include <string> using namespace std; struct Huffman { char data; int s,w,p,l,r; }; Huffman h[60]; int b[1000]; void CreatHuffman(int e) { int i,j; Huffman m1,m2,m; for(j=e; j<=2*e-3; j++) //一共e个节点，所以要遍历e-1遍 { m1.w=0; m2.w=0; for(i=1; i<j; i++) //每次遍历选出两个权值最小的进行建立二叉树 { if(h[i].p==0) { if(m1.w==0) //先对m1进行赋值 { m1=h[i]; } else if(m2.w==0) //在对m2进行赋值 { m2=h[i]; if(m1.w>m2.w) //保证m1的权重小于m2的权重。 { m=m1; m1=m2; m2=m; } } else { if(m1.w>h[i].w) //保证m1是最小的 { m2=m1; m1=h[i]; } else if(m2.w>h[i].w) //如果不判断，到最后可能m1是最小的，但是m2不一定是次小的 m2=h[i]; } } } cout<<m1.s<<" "<<m2.s<<" "<<j<<endl; //输出两个最小的结点 h[j].w=m1.w+m2.w; //建立新的结点作为两个结点的双亲结点 h[j].s=j; h[j].l=m1.s; h[j].r=m2.s; h[m1.s].p=j; //对孩子节点的双亲节赋值 h[m2.s].p=j; } } int out(int t,int k) { if(h[t].p==0) //双亲结点为0则为哈夫曼树的根节点，返回搜索的长度，即字符的哈夫曼编码的长度 return k; if(h[h[t].p].l==t) //是左孩子就输出0，再看双亲 { b[k]=0; out(h[t].p,++k); } else if(h[h[t].p].r==t) //是右孩子就输出1，再看双亲 { b[k]=1; out(h[t].p,++k); } } int pop(int i,int n,int t) { while(h[t].l!=0||h[t].r!=0) //左右孩子都为0那么证明到了叶子节点，输出叶子节点代表的字符 { if(b[i]==0) { t=h[t].l; i++; } else if(b[i]==1) { t=h[t].r; i++; } } cout<<h[t].data; return i; } int main() { int a[60]; string str; while(cin>>str) { memset(a,0,sizeof(a)); memset(h,0,sizeof(h)); int i,j; for(i=0; i<str.length(); i++) //将输入的字符串统计各个字符出现的，区分大小写。用一个数组存储，前26个存储小写字母，后26个存储大写字母 { if(str[i]<='z'&&str[i]>='a') a[str[i]-'a']++; else if(str[i]<='Z'&&str[i]>='A') a[str[i]-'A'+26]++; } int e=1; cout<<"各个字母出现的次数为："<<endl; for(i=0; i<26; i++) //将各个字母出现的次数输出，出现的次数为0就不需要输出了，同时记录次数不为0的字母的个数。将字母出现的次数作为该字母的权重。 { if(a[i]!=0) { cout<<(char)('a'+i)<<":"<<a[i]<<"\t"; h[e].w=a[i]; h[e].s=e; h[e++].data=(char)('a'+i); } } cout<<endl; for(i=26; i<52; i++) { if(a[i]!=0) { cout<<(char)('A'+i-26)<<":"<<a[i]<<"\t"; h[e].w=a[i]; h[e].s=e; h[e++].data=(char)('A'+i-26); } } cout<<endl; for(i=1; i<e; i++) //输出HT初态，包括节点、字符、权重、双亲节点、左右孩子节点 cout<<h[i].s<<" "<<h[i].data<<" "<<h[i].w<<" "<<h[i].p<<" "<<h[i].l<<" "<<h[i].r<<endl; cout<<"每次连接的结点:"<<endl; //建立哈夫曼树 CreatHuffman(e); cout<<endl; for(i=1; i<=2*e-3; i++) //输出HT的终态，包括节点、字符、权重、双亲节点、左右孩子节点 cout<<h[i].s<<" "<<h[i].data<<" "<<h[i].w<<" "<<h[i].p<<" "<<h[i].l<<" "<<h[i].r<<endl; cout<<endl; cout<<"Huffman Code:"<<endl; //输出各个字符的哈夫曼编码 for(i=1; i<e; i++) { cout<<h[i].data<<":"; for(int k=out(i,0); k>0; k--) //通过调用out()函数来获取编码长度，以及对数组赋值 cout<<b[k-1]; cout<<endl; } cout<<"String Huffman Code:"<<endl; //输出字符串的哈夫曼编码 for(i=0; i<str.length(); i++) { for(j=1; j<e; j++) { if(h[j].data==str[i]) //查找到字符所在位置 { memset(b,-1,sizeof(b)); for(int k=out(j,0); k>0; k--) cout<<b[k-1]; break; } } } cout<<endl; cout<<"写一串由上面Huffman Code组成的编码,输入#结束:"<<endl; //可以通过输入哈夫曼编码来翻译成字符串 while(cin>>str) { if(str[0]=='#') break; for(i=0; i<str.length(); i++) //字符数组转成整型数组 { b[i]=str[i]-'0'; } int t; for(i=1; i<=2*e-3; i++) //寻找根节点 { if(h[i].p==0) { t=h[i].s; break; } } for(i=0; i<str.length();) // { i=pop(i,str.length(),t); } cout<<endl; } } return 0; }[问题描述] 试设计一个算法，用最少的比较，尽快地将N个随机的百分制成绩转换成五级分制. 0～59 ———————————————————— bad 60～69 ———————————————————— pass 70～79 ———————————————————— general 80～89 ———————————————————— good 90～100 ———————————————————— excellent [设计要求] 输入n个任意的百分制分数，要求输出对应的等级
非标准正确答案 CODE:
#include <iostream> #include <string> using namespace std; struct grade { double data; int node,score; string str; }; grade a[1100]; int e; void per() { cout<<"90~100:"; cin>>a[e].data; a[e].node=e; a[e].score=90; a[e].str="excellent"; e++; cout<<"80~89:"; cin>>a[e].data; a[e].score=80; a[e].str="good"; e++; cout<<"70~79:"; cin>>a[e].data; a[e].score=70; a[e].str="general"; e++; cout<<"60~69:"; cin>>a[e].data; a[e].score=60; a[e].str="pass"; e++; cout<<"0~59:"; cin>>a[e].data; a[e].score=0; a[e].str="bad"; e++; } int main() { cout<<"输入各分数段的百分制:"<<endl; e=1; per(); double sum=0; int i,t,n; for(i=1; i<e; i++) { sum+=a[i].data; if(sum>=0.5) break; } cout<<"以"<<a[i].score<<"为根"; cout<<"输入任意的百分制分数,输入其他结束:"<<endl; while(cin>>n) { t=i; if(n<0||n>100) break; if(n>a[t].score) { int j=1; while(j<=t) { if(a[j].score<=n) { cout<<a[j].str<<endl; break; } else { j++; } } } else { while(t<=5) { if(a[t].score<=n) { cout<<a[t].str<<endl; break; } else { t++; } } } } return 0; }[问题描述] n堆果子, 每堆果子数量任意，试设计一种最佳方案,将这n堆果子合并为一堆，使得合并工作量最小。 注：规定合并两堆果子的工作量是这两堆果子的数量之和。 [标准输入] M，N M表示M组测试数据，N表示每组测试数据数量不超过N个，每堆果子数量不超过10000。随后的M行是测试数据。 [标准输出] M行数据表示对应果子的合并工作量
[输入样例]：
2 6 7, 5, 2, 4 5,6,2,9,7【输出样例】：
35 65CODE:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct fruit { int w,s; }; int main() { int n,m; while(cin>>m>>n) { while(m--) { fruit a[11000]; memset(a,0,sizeof(a)); int e=1,i,j; char ch=','; while(ch==',') { a[e].s=e; cin>>a[e++].w; ch=getchar(); } int sum=0; fruit m1,m2,m3; for(i=e; i<2*e-2; i++) { cout<<i<<','; m1.w=m2.w=-1; for(j=1; j<i; j++) { if(a[j].s!=-1) { if(m1.w==-1) { m1=a[j]; } else if(m2.w==-1) { m2=a[j]; if(m1.w>m2.w) { m3=m1; m1=m2; m2=m3; } } else { if(m1.w>=a[j].w) { m2=m1; m1=a[j]; } else if(m2.w>=a[j].w) m2=a[j]; } } } a[m1.s].s=-1; a[m2.s].s=-1; a[i].w=m1.w+m2.w; a[i].s=i; sum+=a[i].w; } cout<<sum<<endl; } } return 0; }