实验报告模版二叉树基本操作与哈夫曼编码译码系统的设计

课程设计报告（2013/2014学年第2学期）题目：二叉树基本操作与哈夫曼编码译码系统的设计专业：学生姓名：班级学号：指导教师指导单位日期评分细则评分项成绩遵守机房规章制度（5分）上机时的表现（5分）学习态度（5分）程序准备情况（5分）程序设计能力（10分）团队合作精神（5分）课题功能实现情况（10分）算法设计合理性（10分）用户界面设计（10分）报告书写认真程度（5分）内容详实程度（10分）文字表达熟练程度（10分）回答问题准确度（10分）简短评语教师签名：年月日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格课题题目二叉树基本操作与哈夫曼编码译码系统的设计一、课题内容和要求创建一棵二叉树，分别实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。设计哈夫曼编码/译码系统。能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存。二、需求分析我们根据需求得到以上的菜单，以链表方式存储二叉树，以插入二叉搜索树的方式，将数据一个一个地插入二叉树，以递归的方式分别实现先、中、后三种方式的遍历和计算二叉树的高度，删除二叉树时，先搜索找到那个节点，若有两个子节点，查找中序遍历直接后继节点，之后常规的替代删除操作，最后是哈夫曼树的实现，从文件读取字符串的时候，用while循环来得到每个字母的出现次数，得到权值，之后实现哈夫曼树，通过译码函数输出译码序列。三、概要设计typedefcharEtype;typedefstructbtnode{Etypedata;structbtnode*lch,*rch;intweight;}btnode;typedefstructbtree{structbtnode*root;}btree;typedefstruct{intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;其他的就是各类函数，见下文。四、详细设计#includestdio.h#includestdlib.h#includestring.h#includeiostream.h#includeconio.h#includefstream.htypedefcharEtype;typedefstructbtnode{Etypedata;structbtnode*lch,*rch;intweight;}btnode;typedefstructbtree{structbtnode*root;}btree;btnode*newnode(){btnode*p=(btnode*)malloc(sizeof(btnode));returnp;}btnode*newnode(Etypee){btnode*p=(btnode*)malloc(sizeof(btnode));p-data=e;p-lch=NULL;p-rch=NULL;returnp;}voidMAKEBTREE(btree*bt,intx,btree*lt,btree*rt){btnode*p=newnode();p-weight=x;p-lch=lt-root;p-rch=rt-root;lt-root=NULL;rt-root=NULL;bt-root=p;}voidCREATEBTREE(btree*bt)/*构造一颗空二叉数*/{bt-root=NULL;}//模仿先序递归遍历方法，建立二叉树btnode*creat_bt2(){btnode*t;Etypee;scanf(%c,&e);if(e=='#')t=NULL;//对于'#'值，不分配新结点else{t=(btnode*)malloc(sizeof(btnode));t-data=e;t-lch=creat_bt2();//左孩子获得新指针值t-rch=creat_bt2();//右孩子获得新指针值}returnt;}//creat_bt2voidpreorder(btnode*p)//前序遍历{if(p){printf(%3c,p-data);preorder(p-lch);preorder(p-rch);}}//preorder//中序递归遍历二叉树voidinorder(btnode*p){if(p){inorder(p-lch);coutp-dataendl;inorder(p-rch);}}//inorder//后序递归遍历二叉树voidpostorder(btnode*p){if(p){postorder(p-lch);postorder(p-rch);coutp-dataendl;}}//postorderintDepth(btnode*p){if(!p)return0;elsereturn1+((Depth(p-lch)Depth(p-rch))?Depth(p-lch):Depth(p-rch));}intleafcount(btnode*bt)//输入btree的root{//计算叶结点数intcount=0;if(bt!=NULL){leafcount(bt-lch);leafcount(bt-rch);}if((bt-lch==NULL)&&(bt-rch==NULL))count++;returncount;}intremove(btree*bt)//输入那个节点的值{btnode*p=bt-root;btnode*c,*r,*s,*q;Etypex,e;cout请输入要删除的节点的值endl;cine;while(p&&p-data!=e){q=p;if(ep-data)p=p-lch;elsep=p-rch;}if(!p){cout不存在endl;return0;}x=p-data;if(p-lch&&p-rch){s=p-rch;r=p;while(s-lch){r=s;s=s-lch;}p-data=s-data;p=s;q=r;}if(p-lch)c=p-lch;elsec=p-rch;if(p==bt-root)bt-root=c;elseif(p==q-lch)q-lch=c;elseq-rch=c;free(p);return1;}intinsert(btree*btr,Etypeet)//二叉搜索树的插入函数{btnode*r,*p=btr-root,*q;while(p){q=p;if(etp-data)p=p-lch;elseif(etp-data)p=p-rch;else{coutduplicateendl;return0;}}r=newnode(et);if(btr-root)if(etq-data)q-lch=r;elseq-rch=r;elsebtr-root=r;return1;}voidmycreate(btreebt)//创建二叉搜索树{intx=1;Etypec;cout第一个输入的值为根的值,请输入根值endl;cinc;btnodebtn;btn.lch=NULL;btn.rch=NULL;btn.data=c;bt.root-data=btn.data;bt.root-lch=btn.lch;bt.root-rch=btn.rch;c=getchar();cout其他节点的值endl;while((c=getchar())!='\n'&&x){x=insert(&bt,c);}}voidFmin(btreeht[],int*k1,int*k2,intk){inta,b,c,d;a=ht[0].root-weight;b=ht[0].root-weight;*k1=0;*k2=0;for(c=0;ck;c++){if(a=ht[c].root-weight){a=ht[c].root-weight;*k1=c;}}for(d=0;dk;d++){if(d==*k1)continue;if(b=ht[d].root-weight){b=ht[d].root-weight;*k2=d;}}}btreecreatehfmtree()//生成哈弗曼树{btreezero,ht[26];inti,k,k1,k2;intw[26];for(i=0;i26;i++)w[i]=0;CREATEBTREE(&zero);FILE*fp;fp=fopen(c:\\test.txt,r+);while(!feof(fp)){w[fgetc(fp)-97]++;}for(i=0;i26;i++){MAKEBTREE(&ht[i],w[i],&zero,&zero);ht[i].root-data=97+i;printf(%3d,ht[i].root-data);}for(k=25;k0;k--){Fmin(ht,&k1,&k2,k);MAKEBTREE(&ht[k1],ht[k1].root-weight+ht[k2].root-weight,&ht[k1],&ht[k2]);ht[k1].root-data='!';printf(%3d,ht[k1].root-data);ht[k2]=ht[k];}returnht[0];}intm,s1,s2;typedefstruct{intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,intn){inti,j;for(i=1;i=n;i++)if(HT[i].parent==0){s1=i;break;}for(j=i+1;j=n;j++)if(HT[j].parent==0){s2=j;break;}for(i=1;i=n;i++){if(HT[i].parent==0)if(HT[s1].weightHT[i].weight)if(s2!=i)s1=i;}for(j=1;j=n;j++){if(HT[j].parent==0)if(HT[s2].weightHT[j].weight)if(s1!=j)s2=j;}if(s1s2){inttemp=s1;s1=s2;s2=temp;}}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){inti;char*cd;intp;intcdlen;if(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i=n;i++){HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i=m;i++){HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}//添加查看，便于调试/*printf(构造过程显示：\n);for(i=1;i=m;i++)printf(%4d%4d%4d%4d%4d\n,i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);system(pause);*/for(i=n+1;i=m;i++){Select(HT,i-1);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2