1、数据结构课程设计实验报告赫夫曼编码3464278(此文档为word格式，下载后您可任意编辑修改！)+南京信息工程大学数据结构课程设计 题目：赫夫曼编码院、 系：滨江学院学科专业：计算机科学与技术 学 生： 学 号： 指导教师： 王鹤蒙 2010年12月22日目 录1课程设计的题目-02课程设计的目的（设计要解决的问题）3概要设计（函数划分、总体设计）-14详细设计（算法、流程图、程序）-25调试结果- 6课程设计总结- -337心得体会二课程设计的目的巩固构造赫夫曼树的算法。设计实验用程序实现赫夫曼树的构造。熟悉用先序、中序或后序的访问方法得到个叶子结点的赫夫曼编码。三概要设计（函数划分、总体
2、设计）总体设计（1） 输入一个字符串用结构体链表存储字符串中出现的不同字符及其出现的次数。（2） 定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出现的次数作为叶子结点的元素及其权值，统计叶子结点的个数n，开辟可以存储2*n个结点的顺序表，来赫夫曼树的各个结点，然后按照一定的规则构造赫夫曼树。（3） 开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链表的指针的顺序表，然后从叶子结点开始向上访问，是左孩子的把“0”接进链表是右孩子的把“1”接进链表，直到根结点，然后把叶子结点的元素及存储其赫夫曼链表的头指针读入顺序表，直到把所有的叶子结点的元素及指向存储其赫夫曼编码链表的头指针读入顺序表，
3、这样得到的赫夫曼编码是倒序的。（4） 从存储其叶子结点及指向存储其赫夫曼编码链表头指针的顺序表表头开始顺序访问各元素，在输出其赫夫曼编码之前，把链表中的编码顺序读入到等长的栈中，然后编码出栈就会得到顺序的赫夫曼编码，直到把所有的叶子结点都访问到。（5） 用一个字符型的指针指向字符串的第一个字符，从存储叶子结点元素及指向存储其赫夫曼编码链表的头指针的顺序表表头开始访问顺序表中的各元素，直到找到叶子结点的元素和当前字符相等就结束访输出赫夫曼编码，回到表头，指针后移，直到输出字符串的最后一个字符的赫夫曼编码，这样就得到输入字符串的赫夫曼编码。函数划分 该程序有一个主函数和多个子函数，主函数完成对子函
4、数的调用，各子函数实现相应的功能。子函数：（1） 结点的开辟。（2） 实现对输入字符串中出现的不同字符及其出现字数的信息记录。（3） 用叶子结点构造赫夫曼树。（4） 获得构造的赫夫曼树中所有叶子结点的元素及其赫夫曼编码。（5） 输出各叶子结点元素及其对应的赫夫曼编码。（6） 输出输入的字符串的赫夫曼编码。（7） 调用各子函数四详细设计（算法、流程图、程序）算法创建存储叶子结点元素及其权值的链表定义结构体node，其数据成员包括，字符型的元素a和整型元素b和指向node的next指针，来存储叶子结点的内容和权值。定义三个指向node的指针head、p1、p2和字符指针n、t、,p2-b=r,p1
5、-next=p2,p1=p2,n+,t回到字符串首；否则i+（i为整型，初始值为1）r=0，j=1；让t指向字符串第一个元素，当*t！=0，如果*t=*n，r+，t+；让h指向字符串的第一个元素，当h！=n时如果*,p2-b=r,p1-next=p2,p1=p2;n+,当把最后一个结点连入链表中，p1-next=NULL,然后把p1=（起标记作用）、和指向左、右孩子及父母结点的指针lchild、rchild和parent。定义指向node1的指针p0、p1、p2、p3、p4和整型的m、n、i、j、k1、k2，n=0、p=+，p=p-next，开辟可以存储2*n个node1的顺序表，让p0指向表
6、头，p1=p0,p=-1,j=0,当jsign=NULL并且m=p2-weight用break结束循环否则p2+；p2=p0，当p2！=p时，如果m=p2-weight并且p2-sign=NULL,把p2-weight赋给m，否则p2+；把p0赋给p2，当p2不等于p1时，如果m等于p2-weight并且p2-sign等于NULL，把1赋给p2-sign,如果j=0，把p2赋给p1-lchild,p2-weight赋给p1-weight,p1赋给p2-parent,用break结束循环；如果j=1，则把p2赋给p1-rchild,p1-weight加p2-weight赋给p1-weight,p
7、1赋给p2-parent,用break结束循环；如果j等于0，k1+，p2+；如果j等于1，k2+，p2+；j+；如果k1大于k2把p1-lchild赋给p3，p1-rchild赋给p4，p4赋给p1-lchild,p3赋给p1-rchild,p1-sign=NULL,p1+,i+;然后p-，把p1-parent=NULL,p1+,把p0赋给p2，当p2不等于p时输出p2的各数据项，拍p2+；返回p0。获得各叶子结点的赫夫曼编码定义只存储赫夫曼编码的结构体code，它的数据项有字符型的a（存储0、1编码）以及指向下一个结点的指针next。定义结构体huffmancode，它的数据项有字符型a(
8、存储叶子结点元素)、指向结构体code的指针head。设指向node1的指针p1、p2、p4，指向huffmancode的指针l、l1和指向code的指针h、+，（n为整型，初始化为零），p2+；调用malloc函数开辟可以存储n+1个huffmancode结点的顺序表，让l指向该顺序表的表头，把l赋给l1，把p赋给p4，当p4-lchild和p4-rchild同时为NULL把p4赋给p1调用setcode（）函数开辟一个结点让h1指向该结点，把h1赋给l1-，p-+，+1个字符的栈，让base指向栈底，top=base,把h=p-（n为整型）p1=p0（p0为形参）当p1-a!=NULL时，
9、如果p1-a等于*p把p1-+1个字符的栈底，top=base，把p1-，如果n等于1，p=p-next,输出p-a和p-b,否则，以p为实参调用settree（p），将返回值赋给p1，以p1为实参调用gethuffmamcode（p1）函数，将返回值赋给p2（p2为指向huffmancode的指针），以p2为实参调用printhuffmancode（p1）函数，然后以a，p2为实参调用print（a，p2）函数。coutdata()函数的算法：设指向node的指针p，把head-next赋给p，当p！=NULL时n+，p=p-next;返回n。主函数调用control（）函数。流程图创建存储
10、叶子结点元素及其权值的链表开辟一个新的结点，让head指向它p1=headn=a *n！= 0 n=是=a?否开辟新的结点，让p1指向它 i+ r=0 t=n j=1 *t！= 0 t=a *t=是= 0 ？ 否 *t！= 0 *t=*n是？否r+r+ t+ t+p2-a=*n h=a p2-b=r p1-next=p2 *h=是*n？ 否p1=p2 n+break j+ h+ i=j？是 否开辟新结点，让p2指向它p2-a=*np2-b=rp1-next=p2p1=p2p1-next=NULL p1=head-nextp1!=NULL输出p1-a 输出p1-a返回headsetnode函数开
11、辟一个node结点，让p指向它返回p构造赫夫曼树 p=head-next p！=NULLn+p=p-nextp0=（listnode1）malloc（2*n*sizeof（node1）p1=p0p=head-nextp！=NULLp1-a=p-ap1-weight=p-bp1-lchild p1-rchild p1-parent p1-sign全置空p1+i=1i=n-1j=0jsign= =NULL?否m=p2-weightp2+breakp2=p0p2!=p1m=p2-weight 是并且p2-sign= =NULL?否m=p2-weightp2+p2=p0p2!=p1m=p2-weigh
12、t是并且p2-sign= =NULL?否 j=0? 是 p2-sign j=0? =1? 是 否p1-lchild=p2 p1-rchild=p2p1-weight p1-weight+= k1+=p2-weight p2-weightk2+ p2-parent p2-parent =p1=p1breakp2+j+k1k2 是?否p3=p1-lchildp4=p1-rchildp1-lchild=p4p1-rchild=p3p1-sign=NULLp1+i+p1- -p1-parent=NULLp1+p2=p0p2!=p1输出p2-a p2-weightp2-lchild p2-parent
13、p2-rchildp2+返回p0获得各叶子结点的赫夫曼编码 p2=p p2=lchild= =NULL&p2-rchild= =NULLn+p2+l=(listhuffmancode)malloc(n+1)*sizeof(huffmancode)p4=pp4-lchild= =NULL&p4-rchild= =NULLp1=p4h1=setcode()l1-head=h1P1-parent！=NULL 是 p1=p1-parent-lchild? 否开辟一个结点让h指向它 h-a= 0 h1-next=hh1=hh-a= 0 h1-next=hh1=hh1-next=NULLl1-a=p4-a
14、 l1+l1-a=NULL 返回l setcode函数开辟一个code结点，让p指向该结点 返回p输出各叶子结点的赫夫曼编码 p=head1p-a!=NULLh=h-head-nexth!=NULLn+h=h-nextbase=(char *)malloc(n+1)*sizeof(char)h=h-head-nexth!=NULL*top=h-atop+h=h-nexttop-top!=base输出*toptop-输出*top输出字符串的赫夫曼编码p2=p*p2!= 0 *p2p2+*p!= 0 n=0p1=p0p1-a!=NULL p1-a= =*p? 是否h=p1-head-nextp1+
15、h!=NULLn+h=h-nextbase=(char *)malloc(n+1)*sizeof(char)top=baseh=p1-head-nexth!=NULL*top=h-atop+h=h-next-toptop!=base输出*topbreakp+control函数输入ap=getdata(a)n=coutdata(p)是n= =1?否p=p-nextp1=settree(p) 输出p-a和p-bp2=gethuffmancode(p1)printhuffmancode(p2)print(a,p2) countdata()函数p=head-nextp!=NULLn+p=p-next返
16、回n 主函数调用control()函数程序的编译环境是Visual studio 2010把统计叶子结点元素和权值的函数放在“计算权值. p;listnode getdata(char *a) *统计输入字符串中的不同字符及其出现的次数的函并且把统计出的数据，作为叶子结点的元素和权值* listnode ,*t,*=a;*n!=0;n+) if(n=a) p2=setnode(); for(t=n;*t!=0;t+) 统计相同的字符在字符串中出现的次数 if(*t=*n) r+; p2-a=*n; p2-b=r; p1-next=p2; p1=p2; else i+; r=0; j=1; fo
17、r(t=a;*t!=0;t+) if(*t=*n) r+; for(;) break; else j+; if(i=j) p2=setnode(); 调用setnode（）函数开辟结点 p2-a=*n; p2-b=r; p1-next=p2; p1=p2; p1-next=NULL; cout电文的长度为：iendl; coutendl; p1= =0; for(p=+; return n; 把构造赫夫曼树的函数放在头文件“构造赫夫曼树.; 结点的权值和结点的标记struct node1 *parent,*lchild,*rchild; 指向父母结点和左、右孩子的指针*listnode1; 指
18、向node1的指针listnode1 settree(listnode ,i,j,k1,k2; struct node1 *p3,*p4; n=0; for(p=+; p0=(listnode1)malloc(2*n*sizeof(node1); 开辟可以存储2n个赫夫曼树结点的顺序表 p1=p0; for(p=NULL; p1+; for(i=1;i=n-1;i+) for(j=0;jsign=NULL) m=p2-weight; break; for(p2=p0;p2!=p1;p2+) if(m=p2-weight) if(p2-sign=NULL) m=p2-weight; for(p2
19、=p0;p2!=p1;p2+) if(m=p2-weight) if(p2-sign=NULL) p2-sign=1; if(j=0) 把先找到的权值最小的作为左孩子 p1-lchild=p2; p1-weight=p2-weight; p2-parent=p1; else if(j=1) 把后找到的权值最小的最为右孩子 p1-rchild=p2; p1-weight=p1-weight+p2-weight; p2-parent=p1; break; if(j=0) k1+; 标记先找到的权值最小的结点在顺序表中的位置 else if(j=1) k2+; 标记后找到的权值最小的结点在顺序表中的
20、位置 if(k1k2) *如果先找到的权值最小的结点在顺序表中的位置在后找到的后面 则他们父母结点的左右孩子指针交换* p3=p1-lchild; p4=p1-rchild; p1-lchild=p4; p1-rchild=p3; p1-sign=NULL; p1+; p1-; p1-parent=NULL; p1+; p2=p0; cout叶子结点t权值t左孩子tt父母结点t右孩子endl; 输出构造的赫夫曼树 while(p2!=p1) coutatt weighttlchildtparenttrchildendl; p2+; coutlchild=NULL&p4-rchild=NULL;
21、p4+)p1=p4; l;把输出赫夫曼编码的函数放在头文件“输出赫夫曼编码.;char *base,*top;cout叶子结点t权值endl;for(p=0; +; base=(char *)malloc(n+1)*sizeof(char); top=base; ;char *base,*top,*p2;cout电文内容：;for(p2=p;*p2!=0;p2+) cout*p2;coutendl;couta!=NULL;p1+) if(p1-a=*p) +; base=(char *)malloc(n+1)*sizeof(char); top=base; ; couta; listnode
22、p; p=getdata(a); n=coutdata(p); if(n=1) 如果只有一个叶子结点，说明该叶子结点就是根结点，无法构造赫夫曼树 p=p-next; coutendl; cout根结点tt权值endl; coutatt bendl; coutendl; else listnode1 p1; p1=settree(p); listhuffmancode p2; p2=gethuffmancode(p1); printhuffmancode(p2); print(a,p2); coutendl程序结束.endl;主函数放在源文件“赫夫曼编码.cpp“中#include#includ
23、e控制函数.()control(); 调用control函数五调试结果 六课程设计总结 本次课程设计的目的是：把一个随机输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到各个叶子结点的赫夫曼编码和整个输入的字符串的赫夫曼编码。在写代码前，首先，对问题进行了分析，明确了目标，列出了大的框架，然后逐渐细化，划分出不同的功能模块，由具体的子函数去实现，先在纸上编写代码，写好后进行了反复的逻辑推理，发现并解决逻辑问题，然后，上机调试，方法是：一个一个功能模块分开进行调试，主要看调试的模块能否达到预期的结果，这样可以缩小排错的范围，便以纠错和提高编程的效率
24、，当每个功能模块都调试好后，就把各个部分组合起来，再进行调试，主要检查各函数接口是否正确，当达到预期的结果，调试结束，编程部分完成，然后按实验要求完成实验报告。由于写代码前做了充分的准备工作，所以写起代码来比较顺利，使编程的效率有不少的提高并且最终达到实验预期的结果。七心得体会每一次的课程设计对我来说都是一个不小的提高，哲学上说：“实践是检验真理正确性的唯一标准”，尤其是学编程，自己不动手操作，只看书永远都编不出像Windows之类的东西，正如老师说的那样，课程设计非常锻炼人，每完成一个项目，不仅是知识体系的完善和知识的验证，更是编程技术的提升，当自己编的多了，就会开始摸索编程的捷径，想着用更高效的方法去完成一个个项目，就这样在一次次的锻炼中自己会从一个菜鸟迅速的成长，终将成为一个优秀的软件工程师。一个成功的项目必须在写代码前，先要对课题有充分的思考和规划，否则即使完成了项目也会浪费很多的时间和精力，我认为科学合理的编程方法是我这次课程设计的最大收获。
