《实验报告模版二叉树基本操作与哈夫曼编码译码系统的设计》由会员分享，可在线阅读，更多相关《实验报告模版二叉树基本操作与哈夫曼编码译码系统的设计（24页珍藏版）》请在装配图网上搜索。
1、课程设计报告（ 2013 /2014 学年 第 2 学期）题 目：二叉树基本操作与哈夫曼编码译码系统的设计专业：学生姓名：班级学号：指导教师指导单位日期评分细则评分项成绩遵守机房规章制度（5分）上机时的表现（5分）学习态度（5分）程序准备情况（5分）程序设计能力（10分）团队合作精神（5分）课题功能实现情况（10分）算法设计合理性（10分）用户界面设计（10分）报告书写认真程度（5分）内容详实程度（10分）文字表达熟练程度（10分）回答问题准确度（10分）简短评语教师签名：年月日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格课题题目二叉树基本操作与哈夫曼编码译码系统的设计一、 课题
2、内容和要求创建一棵二叉树，分别实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。设计哈夫曼编码/译码系统。能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存。二、需求分析我们根据需求得到以上的菜单，以链表方式存储二叉树，以插入二叉搜索树的方式，将数据一个一个地插入二叉树，以递归的方式分别实现先、中、后三种方式的遍历和计算二叉树的高度，删除二叉树时，先搜索找到那个节点，若有两个子节点，查找中序遍历直接后继节点，之后常规的替代删除操作，最后是哈夫曼树的实现，从文件读取字符串的时候，用while循环来得到每个字母的出现次数，得到权值，之后实现哈夫曼树，通过译码函
3、数输出译码序列。三、概要设计typedef char Etype;typedef struct btnodeEtype data;struct btnode * lch,* rch;int weight;btnode;typedef struct btreestruct btnode * root;btree;typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char * HuffmanCode;其他的就是各类函数，见下文。四、详细设计#include#include#include
4、#include#include#includetypedef char Etype;typedef struct btnodeEtype data;struct btnode * lch,* rch;int weight;btnode;typedef struct btreestruct btnode * root;btree;btnode * newnode()btnode * p=(btnode*)malloc(sizeof(btnode);return p;btnode * newnode(Etype e)btnode * p=(btnode*)malloc(sizeof(btnode
5、);p-data=e;p-lch=NULL;p-rch=NULL;return p;void MAKEBTREE(btree * bt,int x,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;void CREATEBTREE(btree * bt) /*构造一颗空二叉数*/ bt-root=NULL; /模仿先序递归遍历方法，建立二叉树btnode *creat_bt2() btnode *t; Etype
6、 e; scanf(%c,&e); if(e=#)t=NULL; /对于#值，不分配新结点 else t=(btnode *)malloc(sizeof(btnode); t-data=e; t-lch=creat_bt2(); /左孩子获得新指针值 t-rch=creat_bt2(); /右孩子获得新指针值 return t; /creat_bt2void preorder(btnode *p) /前序遍历 if(p) printf(%3c,p-data); preorder(p-lch); preorder(p-rch); /preorder/中序递归遍历二叉树void inorder(b
7、tnode *p) if(p) inorder(p-lch); coutdatarch); /inorder/后序递归遍历二叉树void postorder(btnode *p) if(p) postorder(p-lch); postorder(p-rch); coutdatalch)Depth(p-rch)?Depth(p-lch):Depth(p-rch);int leafcount(btnode * bt) /输入btree的root /计算叶结点数 int count=0; if(bt!=NULL) leafcount(bt-lch); leafcount(bt-rch); if(b
8、t-lch=NULL)&(bt-rch=NULL) count+;return count; int remove(btree *bt) /输入那个节点的值 btnode *p=bt-root; btnode *c,*r,*s,*q; Etype x,e; cout请输入要删除的节点的值e; while(p&p-data!=e) q=p; if(edata)p=p-lch; else p=p-rch; if(!p) cout不存在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;
9、q=r; if(p-lch)c=p-lch; else c=p-rch; if(p=bt-root)bt-root=c; else if(p=q-lch)q-lch=c; else q-rch=c; free(p); return 1; int insert(btree *btr,Etype et) /二叉搜索树的插入函数btnode * r, *p=btr-root, *q;while(p)q=p;if(etdata)p=p-lch;else if(etp-data)p=p-rch;else coutduplicateroot)if(etdata)q-lch=r; else q-rch=r;
10、 else btr-root=r;return 1;void mycreate (btree bt) /创建二叉搜索树 int x=1;Etype c;cout第一个输入的值为根的值,请输入根值c;btnode btn;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其他节点的值weight; b=ht0.root-weight; *k1=0; *k2=0; for(c=0;c=htc.root-weight) a
11、=htc.root-weight; *k1=c; for(d=0;d=htd.root-weight) b=htd.root-weight; *k2=d; btree createhfmtree() /生成哈弗曼树 btree zero,ht26; int i,k,k1,k2; int w26; for(i=0;i26;i+) wi=0; CREATEBTREE(&zero); FILE* fp; fp=fopen(c:test.txt,r+); while(!feof(fp) wfgetc(fp)-97+; for(i=0;idata=97+i; printf(%3d ,hti.root-d
12、ata); for(k=25;k0;k-) Fmin(ht,&k1,&k2,k); MAKEBTREE(&htk1,htk1.root-weight+htk2.root-weight,&htk1,&htk2);htk1.root-data=!;printf(%3d ,htk1.root-data); htk2=htk; return ht0;int m,s1,s2;typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char * HuffmanCode;void Select(Huff
13、manTree HT,int n) int i,j; for(i=1;i=n;i+) if(HTi.parent=0) s1=i; break; for(j=i+1;j=n;j+) if(HTj.parent=0) s2=j; break; for(i=1;iHTi.weight) if(s2!=i) s1=i; for(j=1;jHTj.weight) if(s1!=j) s2=j; if(s1s2) int temp=s1; s1=s2; s2=temp;void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
14、int i;char *cd;int p;int cdlen;if (n=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); for (i=1; i=n; i+) HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+) HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; /添加查看，便于调试/*printf(构造过程显示：n); for(
15、i=1;i=m;i+) printf(%4d%4d%4d%4d%4dn,i,HTi.weight, HTi.parent,HTi.lchild, HTi.rchild);system(pause);*/for(i=n+1;i=m;i+) Select(HT,i-1); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; /添加查看，便于调试 /*printf(s1=%d,s2=%dn,s1,s2); for(j=1;j=i;j+)
16、printf(%d%4d%4d%4d,j,HTj.weight,HTj.parent,HTj.lchild, HTj.rchild); system(pause); */cd = (char *)malloc(n*sizeof(char);p=m;cdlen=0;for(i=1;i=m;i+) HTi.weight=0;while(p) if(HTp.weight=0) HTp.weight=1; if(HTp.lchild!=0) p=HTp.lchild; cdcdlen+=0; else if(HTp.rchild=0) HCp=(char *)malloc(cdlen+1)*sizeo
17、f(char); cdcdlen=0; strcpy(HCp,cd); else if(HTp.weight=1) HTp.weight=2; if(HTp.rchild!=0) p=HTp.rchild; cdcdlen+=1; else HTp.weight=0; p=HTp.parent; -cdlen; int hfm()HuffmanTree HT; HuffmanCode HC; int *w,i; int n=0;int x,y,z=0;FILE *fp;fp=fopen(c:test.txt,r+);FILE * fp2=fopen(c:test.txt,r+);int zim
18、u26=0;repeat:while(!feof(fp) y=fgetc(fp); for(x=97;x123;x+) for(i=0;iz;i+) if(y=zimui) goto repeat; if(x=y) n+; zimuz=y; z+; HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode);w=(int *)malloc(n*sizeof(int);for(i=0;in;i+)wi=0; while(!feof(fp2) wfgetc(fp2)-97+; HuffmanCoding(HT,HC,w,n); printf(输出编码：n);for
19、(i=1;iroot=creat_bt2();break; /调用递归建立二叉树算法 case 3:if(t) printf(先序遍历二叉树:); preorder(t-root); printf(n); else printf(二叉树为空!n); break; case 4:if(t) printf(中序遍历二叉树:); inorder(t-root); printf(n); else printf(二叉树为空!n); break; case 5:if(t) printf(后序遍历二叉树:); postorder(t-root); printf(n); else printf(二叉树为空!n
20、); break; case 6:if(t) printf(二叉树的高度为：%d,Depth(t-root); printf(n); else printf(二叉树为空！n); break;case 7:remove(t); break;case 8:hfm(); break; case 0:exit(0); /switch while(k=1&k=10); printf(n再见！按回车键，返回n); ch=getchar(); /main 五、测试数据及其结果分析六、调试过程中的问题创建二叉树的时候，要注意生成节点，不能只是给指针赋值，只有生成节点，二叉树才能保存下来。递归设计的时候注意程序的结束，不然会死循环七、课程设计总结我设计了，哈夫曼树一段的程序，它包括了创建一个二叉搜索树，创建一个根节点，然后在写了一个插入函数，其他的节点值通过插入的方式进入程序，方便本组的同学进行程序编辑。另外，我还根据实验要求收集资料，然后进行整合，提供给其他同学。并于最后完成校验程序。总之，这次学习到了很多东西，了解许多二叉树数据结构的细节，感觉到收获颇丰。
实验报告模版二叉树基本操作与哈夫曼编码译码系统的设计
