《实验报告模版 二叉树基本操作与哈夫曼编码译码系统的设计》由会员分享，可在线阅读，更多相关《实验报告模版 二叉树基本操作与哈夫曼编码译码系统的设计（24页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告（ 2013 /2014 学年 第 2 学期）题 目：二叉树基本操作与哈夫曼编码译码系统的设计二叉树基本操作与哈夫曼编码译码系统的设计专业：专业：学生姓名：学生姓名：班级学号：班级学号：指导教师指导教师指导单位指导单位日期日期评分项评分项成绩成绩遵守机房规章制度（遵守机房规章制度（5 分）分）上机时的表现（上机时的表现（5 分）分）学习态度（学习态度（5 分）分）程序准备情况（程序准备情况（5 分）分）程序设计能力（程序设计能力（10 分）分）团队合作精神（团队合作精神（5 分）分）课题功能实现情况（课题功能实现情况（10 分）分）算法设计合理性（算法设计合理性（10 分）分）用户
2、界面设计（用户界面设计（10 分）分）报告书写认真程度（报告书写认真程度（5 分）分）内容详实程度（内容详实程度（10 分）分）文字表达熟练程度（文字表达熟练程度（10 分）分）评分细则评分细则回答问题准确度（回答问题准确度（10 分）分）简短评语简短评语教师签名：教师签名：年月日年月日评分等级评分等级备注备注评分等级有五种：优秀、良好、中等、及格、不及格评分等级有五种：优秀、良好、中等、及格、不及格课题题目课题题目二叉树基本操作与哈夫曼编码译码系统的设计二叉树基本操作与哈夫曼编码译码系统的设计一、课题内容和要求课题内容和要求创建一棵二叉树，分别实现先序、中序和后序遍历一棵二叉树，计算二叉树结
3、点个数等操作。设计哈夫曼编码/译码系统。能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存。二、需求分析二、需求分析我们根据需求得到以上的菜单，以链表方式存储二叉树，以插入我们根据需求得到以上的菜单，以链表方式存储二叉树，以插入二叉搜索树的方式，将数据一个一个地插入二叉树，以递归的方式分二叉搜索树的方式，将数据一个一个地插入二叉树，以递归的方式分别实现先、中、后三种方式的遍历和计算二叉树的高度，删除二叉树别实现先、中、后三种方式的遍历和计算二叉树的高度，删除二叉树时，先搜索找到那个节点，若有两个子节点，查找中序遍历直接后继时，先搜索找到那个节点，若有两个子节点，查找中
4、序遍历直接后继节点，之后常规的替代删除操作，最后是哈夫曼树的实现，从文件读节点，之后常规的替代删除操作，最后是哈夫曼树的实现，从文件读取字符串的时候，用取字符串的时候，用 while 循环来得到每个字母的出现次数，得到权值，循环来得到每个字母的出现次数，得到权值，之后实现哈夫曼树，通过译码函数输出译码序列。之后实现哈夫曼树，通过译码函数输出译码序列。三、概要设计三、概要设计typedef char Etype;typedef struct btnodeEtype data;struct btnode * lch,* rch;int weight;btnode;typedef struct bt
5、reestruct btnode * root;btree;typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char * HuffmanCode;其他的就是各类函数，见下文。四、详细设计四、详细设计#include#include#include#include#include#includetypedef char Etype;typedef struct btnodeEtype data;struct btnode * lch,* rch;int weight;btnode;t
6、ypedef 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);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-we
7、ight=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 e;scanf(“%c“,if(e=#)t=NULL; /对于#值，不分配新结点 elset=(btnode *)malloc(sizeof(btnode);t-data=e;t-lch=creat_bt2(); /左孩子获得新指针值 t-rch
8、=creat_bt2(); /右孩子获得新指针值return t; /creat_bt2void preorder(btnode *p) /前序遍历if(p)printf(“%3c“,p-data);preorder(p-lch);preorder(p-rch); /preorder/中序递归遍历二叉树void inorder(btnode *p)if(p)inorder(p-lch);coutdatarch); /inorder/后序递归遍历二叉树void postorder(btnode *p) if(p) postorder(p-lch);postorder(p-rch);coutdat
9、alch)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(bt-lch=NULL)return count; int remove(btree *bt) /输入那个节点的值btnode *p=bt-root;btnode *c,*r,*s,*q;Etype x,e;coute;while(pif(edata)p=p-lch;else p=
10、p-rch;if(!p)coutdata;if(p-lchr=p;while(s-lch)r=s;s=s-lch;p-data=s-data;p=s;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-d
11、ata)p=p-rch;elsecoutroot)if(etdata)q-lch=r;else q-rch=r;else btr-root=r;return 1;void mycreate (btree bt) /创建二叉搜索树int x=1;Etype c;coutc;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();coutweight;b=ht0.root-weight;*k1=0;*k2=0;f
12、or(c=0;c=htc.root-weight)a=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;idata=97+i;printf(“%3d “,hti.root-data);for(k=25;k0;k-) Fmin(ht,MAKEBTREE(htk1.root-data=!;printf(“%3d “,htk1.root-data);htk2
13、=htk;return ht0;int m,s1,s2;typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char * HuffmanCode;void Select(HuffmanTree HT,int n) int i,j; 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(HuffmanT
14、ree char *cd;int p;int cdlen;if (nroot=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);prin
15、tf(“n“);else printf(“二叉树为空!n“);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); /switchwhile(k=1printf(“n 再见！按回车键，返回n“);ch=getchar(); /main五、测试数据及其结果分析五、测试数据及其结果分析六、调试过程中的问题六、调试过程中的问题创建二叉树的时候，要注意生成节点，不能只是给指针赋值，只有生创建二叉树的时候，要注意生成节点，不能只是给指针赋值，只有生 成节点，二叉树才能保存下来。成节
