课程设计构造哈夫曼树

课程设计构造哈夫曼树 中国矿业大学徐海学院计算机系 《软件认知实践》报告 姓 名: 学 号: 专 业: 设计题目: 指导教师: 2013年12月 目 录 第1章 题目概述 ........................................ 1第1.1节 题目要求 ........................................................................... 1 第1.2节 主要难点 ........................................................................... 1 第2章 系统流程图 ....................................... 2第3章 数据结构和算法 ................................... 3 第4章 核心代码 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ..................................... 3 第5章 实验小结 ......................................... 5 参考文献 ................................................ 9 中国矿业大学徐海学院《软件认知实践》报告 第1章 题目概述 设计程序以实现构造哈夫曼树的哈夫曼算法 第1.1节 题目要求 (1)可以使用实验工具的有关功能。 (2)要能演示构造过程。 (3)求解出所构造的哈夫曼树的带权路径长度。 第1.2节 主要难点 (1)构造哈夫曼树:根据给定的权值构成二叉树集合，其中每棵二叉树中只有一个带权的根节点，其左右子树均为空;在二叉树集合中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根节点的权值为其左、右子树上根节点的权值之和;在二叉树集合中删除这两棵树，并将得到的二叉树加入集合中;重复上述步骤，直至二叉树集合中只含一棵树为止。 (2)求带权路径长度:先求每个叶子结点到树根之间的路径长度与该叶子结 点所带权值之积，在将所得之积求和。 1 中国矿业大学徐海学院《软件认知实践》报告 第2章 系统流程图 开始 输出叶子结点个数n 输入n个ASCII和权值 结点1~n与n+1~m分别初始化 引用pr()函数 输入初始状态图 构建哈夫曼树 引用pr()函数 输入初始状态图 引用bm()函数从叶子到根逆向求书编码 引用print()函数 输出哈夫曼编码 引用dq()函数求带权路径长度 输出带权路径长度 结束 2 中国矿业大学徐海学院《软件认知实践》报告 第3章 数据结构和算法 使用树TREE的结构，编造最优二叉树(即哈夫曼树)，涉及到主要函数有 Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree 等，用于在一定时间复杂度内寻找到最佳(最短)路径，节约比较次数。 1.Init huffmantree(&T) 操作结果:构造一个已知结点和权值的huffmantree. 2.Destory huffmantree(&T) 条件:huffmantree已经存在 结果:销毁huffmantree. 3.huffman coding(&T) 条件:huffmantree已经存在 结果:输出huffman code. 4.Visit huffmantree(&T) 条件:huffmantree已经存在 结果:显示 huffman tree. 代码运行结果 3 中国矿业大学徐海学院《软件认知实践》报告 4 中国矿业大学徐海学院《软件认知实践》报告 第4章 核心代码分析 (1) 定义 int s1=0,s2=0;//定义两个全局变量 typedef struct// 定义/结构体 { int c;//字符域 int w;//权值域 int p,l,r;/双亲域/左孩子域右孩子域， }HT,*HuffmanTree;//动态分配数组存储赫夫曼树 typedef char * *HuffmanCode;//动态分配数组存储赫夫曼编码 HT *HTree; 2) 找出两个最小权值s1，s2 ( void Select(HT *HTree,int b) { int i,j,t; for(i=1;i<=b;i++) if(!HTree[i].p) { s1 = i; break; } for(j=i+1;j<=b;j++) if(!HTree[j].p) { s2 = j; break; } for(i=1;i<=b;i++) if((HTree[s1].w>HTree[i].w)&&(!HTree[i].p)&&(s2!=i)) s1=i; for(j=1;j <= b;j++) if((HTree[s2].w>HTree[j].w)&&(!HTree[j].p)&&(s1!=j)) s2=j; if(s1>s2)//令s1小于s2 5 中国矿业大学徐海学院《软件认知实践》报告 { t=s1; s1=s2; s2=t; } } HuffmanCode HCode (3) 输出状态图 void pr(HT *HTree,int m) { int i; HT *h; printf("\n输出状态图\n字符\t权值\t双亲\t左孩子\t右孩子"); h=HTree+1; for(i=1;i<=m;i++,h++) { \t%d\t%d\t%d\t%d",h->c,h->w,h->p,h->l,h->r); printf("\n%c } (4) 逐个字符求赫夫曼编码 void Strcpy(char *p1,char *p2,int i,int j) { int k; for(k=0;i<=j;k++,i++) *(p1+k)=*(p2+i); } (5) 逐个字符求赫夫曼编码 void bm(HT *HTree,int n,char *code) { int i,start,t,P; for(i=1;i<=n;i++) { start=n-1;//编码结束符位置 for(t=i,P=HTree[i].p;P!=0;t=P,P=HTree[P].p)//从叶子到根逆 向求编码 { if (HTree[P].l==t) code[--start]='0';//左孩子编码为0 else 6 中国矿业大学徐海学院《软件认知实践》报告 code[--start]='1';//有孩子编码为1 } HCode[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间 Strcpy(HCode[i],code,start,n-1);//把code占到hcode上 } } (6) 输出赫夫曼编码函数 void Print(HuffmanTree HTree,HuffmanCode HCode,int n) { int i; for(i=1;i<=n;i++) { printf("%c--",HTree[i].c); printf("%d--",HTree[i].w); printf("%s",HCode[i]); printf("\n"); } } (7) 带权路径长度 dq(HT *HTree,int n) { int i,l,P,WPL; int wpl[100]; for(i=1;i<=n;i++) { for(l=0,P=HTree[i].p;P!=0;P=HTree[P].p) l+=1;//l是路径个数 wpl[i]=HTree[i].w*l; } for(i=1,WPL=0;i<=n;i++) WPL+=wpl[i]; return WPL; } (8) 主函数 void main() 7 中国矿业大学徐海学院《软件认知实践》报告 { int n,m,i,C,W,WPL; HT *h; printf("赫夫曼树应用～"); printf("\n输入叶子节点个数:"); scanf("%d",&n); m=2*n-1; HTree=(HT *)malloc((m+1)*sizeof(HT));//0号单元未用,初始化赫 夫曼树 h=HTree+1; printf("\n输入%d个字符的Asc码(97-133)和权值:",n); //叶子结点初始化 for(i=1;i<=n;i++,h++) { scanf("%d",&C); scanf("%d",&W); >c=C; h- h->w=W; h->p=0; h->l=0; h->r=0; } //中间结点初始化 for(i=n+1;i<=m;i++,h++) { h->c=' '; h->w=0; h->p=0; h->l=0; h->r=0; } printf("\n初始\n"); pr(HTree,m);//输出初始状态图 //建赫夫曼树 for(i=n+1;i<=m;i++) { Select(HTree,i-1); HTree[s1].p=i; 8 中国矿业大学徐海学院《软件认知实践》报告 HTree[s2].p=i; HTree[i].l=s1; HTree[i].r=s2; HTree[i].w=HTree[s1].w+HTree[s2].w; } //输出终结状态图 printf("\n终结\n"); pr(HTree,m); //从叶子到根逆向求赫夫曼树编码 char *code; HCode=(HuffmanCode)malloc((n+1)*sizeof(char));//0号单元未用,分配n个字符编码的头指针向量 code=(char *)malloc(n*sizeof(char));//分配求编码的公用工作空间 code[n-1]='\0';//编码结束符 bm(HTree,n,code); printf("\n赫夫曼编码为:\n"); Print(HTree,HCode,n); //带权路径长度 WPL=dq(HTree,n); printf("\n带权路径长度:%d\n",WPL); } 第5章 实验小结 通过这一段时间的课程设计，我通过查找资料，仔细思考，运行修改，编出赫夫曼树应用这个程序。 在编程序的过程中，也遇到了很多困难:检查没有错误却无法得出想要的结果，语句也和书上的一样却无法连接结点，又或是想达到的效果编不出来等等。这说明我们掌握的知识不够完整，不够扎实，需要加深巩固。我们一点点地摸索、求证、询问、查找，虽然还有不完美的地方，终于将程序完成，也对树的知识有了更深的理解。 这一周的课程设计让我收获颇丰，也感谢老师平时上课的教导。 参考文献 严蔚敏 吴伟民编.《数据结构(c语言版)》. 清华大学出版社 9 中国矿业大学徐海学院《软件认知实践》报告 谭浩强编.《C程序设计》.清华大学出版社 10