数据结构课程设计报告赫夫曼编码

1、数据结构课程设计 题目：赫夫曼编码 院、 系：计算机科学与工程学院学科专业： 计算机科学与技术 学 生： 学 号： 指导教师： 2010年12月26目 录1课程设计的题目- 0 页2课程设计的目的（设计要解决的问题）-2页3概要设计（函数划分、总体设计）- 2页4详细设计（各函数算法、流程图、程序）-3页5调试结果-23页6课程设计总结-24页7心得体会- 24页1、 课程设计的目的：1 了解利用赫夫曼树求解给定权值的字符串的赫夫曼编码的算法思想；2 学习利用计算机程序语言实现赫夫曼树构造的算法；3 利用构造好的赫夫曼树对任一字符串求解其赫夫曼编码，以此熟悉赫夫曼编码的整个求解过程；2、 概要

2、设计:（1） 函数划分：功能模块总共分为四个块，由四个主要的函数来实现，分别为：1 linklist calculation(char temp,int n)-统计字符种类及各个字符在字符串中出现次数的函数：用temp接收用户输入的字符串，将字符串存入一个链表当中，链表的每个结点存储字符串的一个字符，然后用两个指针p和t，查找字符串中相同的字符，将相同的字符结点删除，只保留一个，并且在保留的那个字符结点中统计当前字符的权值（即其在字符串中出现的次数），统计完成后将链表的头结点返回；2 status auto_calculation(linklist l)-自动统计权值的函数，以每个字符在字符串

3、中出现的次数作为其权值：将calculation()中统计的各个字符在字符串中出现的次数作为权值存储到全局数组w中；3 status input_weight(linklist l)-手动输入各个字符权值的函数：对之前建立好的存储字符串中每种字符信息的链表的结点进行操作，手动输入每个字符的权值，并将其对应的存储在每个结点的权值变量weight中，待链表中所有字符权值手动输入完毕后，再将链表中存储的每种字符的权值赋给存储权值的全局数组w中；4 void creat_huffmantree(huffmantree &ht,linklist l)-根据字符串中每个字符的权值构造赫夫曼树的函数：利用之

4、前用于存储存储字符串中每种字符信息的链表，统计出字符种类个数n（即链表的结点数），然后开辟长度为2n的存储空间构造赫夫曼树，这其中还需要调用选择权值最小的两个结点的select()函数；5 void text_code(huffmantree ht,linklist head,int n)-根据构造好的赫夫曼树求解字符串中每个字符的编码的函数：将之前构造好的赫夫曼树，由叶子结点向根结点求每个字符的赫夫曼编码，并且将得到的编码保存与相应字符对应的一个数组中，这个数组是code这个结构体的一个成员，它其中还包括存储每个字符及其权值的变量；6 void calculte_code(char temp

5、,linklist head)-输出每个字符以及整个字符串的赫夫曼编码的函数：将每个字符输出，同时逆序输出求解得到的编码，即是其对应的赫夫曼编码，然后输出整个字符串的赫夫曼编码；7 选择权值最小的两个结点的函数-void select(huffmantree &ht,int nn,int *s11,int *s22)，这是辅助建造赫夫曼树的函数。（2） 总体设计： 求解一个字符串的赫夫曼编码的算法主要是根据字符串中各个字符的权值构造赫夫曼树来进行编码的，对于字符的权值，我采用了自动统计和手动输入两种方式得到，这样可以方便用户的各种需求。 对于自动统计各个字符的权值这一功能，主要是依据各个字符在

6、字符串中出现的次数作为它的权值。因为字符串中会有重复出现的字符，而它们的权值是每种字符出现的次数即可，即只需将统计得到的权值存储在一个字符的信息中即可，因此，我采用了链表这种数据结构，将用户输入的字符串的每个字符分别保存在一个链表的每个结点中，然后查找链表中字符相同的结点，用一个指针p从链表的第一个结点开始，再用一个查找指针t指向p的下一个结点，然后让指针t从p的下一个结点开始，查找p后面的所有结点，如果找到与p中的字符相同结点，就将t所指的结点从链表中删除，p所指的结点的权值加1，t继续向下查找，直至查找完最后一个结点，然后将p指向下一个待查找的字符，t继续从p的下一个结点开始，重复上述过程

7、，直至将链表中的所有结点都查找一遍，最后，链表中存储的就是字符串中不同的字符及它们各自在字符串中的出现次数。 对于手动输入各个字符权值这一功能模块，同样需要先统计出字符串中不同字符的个数，然后给每个字符手动赋上相应的权值，因此，同样利用统计各个字符在字符串中出现次数的链表，手动给每个结点中的字符赋权值，覆盖掉原先的出现次数即可。 待自动统计或者通过手动输入的方式给每个字符赋上相应的权值以后，将链表中的权值对应的存储到一个全局数组w中，w数组定义为全局变量的原因是整个程序运行过程中，多个函数都会访问它，因此定义为全局变量可以方便每个函数的访问。然后，统计出字符串中不同字符的个数n，开辟2n个连续

8、的存储单元来建立赫夫曼树，其中这段存储空间中的0号单元不使用，而作为后面判断每个结点是否存在双亲或者左右孩子使用。开始构造赫夫曼树，先将n个字符的权值对应存储到1n号存储单元中，并且将它们的左右孩子以及双亲都初始化为0号单元，即没有双亲和左右孩子，然后从现有的权值表中选出两个双亲为0且权值最小的相加后，添加到n+12n单元中，更新权值表，重复上述过程，建立赫夫曼树。赫夫曼树构造完成后，将此存储空间的头指针通过宏引带回，方便后续的操作。 调用一个text_code()函数对建立好的赫夫曼树有叶子结点向根结点逆向求每个叶子结点的编码，并将编码存储在一个结构体成员数组中，这个结构体还包含存储字符的变

9、量，以及存储字符权值的变量，这样就可以将每个字符与它的权值和编码对应起来。 最后，利用之前用于统计字符种类及其每个字符出现次数的链表倒序输出每个字符的编码，即得到它的赫夫曼编码，然后，在输出整个字符串的赫夫曼编码。3、 详细设计（1） 各函数算法：1 linklist calculation(char temp,int n)：字符数组temp接收用户输入的 字符串，整型变量n为字符串中字符的个数。若接收到的字符串不为空，则创建一个存储字符串的链表head，用一个for循环将字符串中的每个字符及其权值等相关信息存储在链表中的每个结点中，并且初始化每个字符的权值为1。链表建立完毕后，用一个指针p指

10、向链表的第一个结点，同时用一个指针t指向p的下一个结点，然后让指针t从p的下一个结点开始，查找p后面的所有结点，如果找到与p中的字符相同结点，就将t所指的结点从链表中删除，同时p所指的结点的权值加1，t继续向下查找，直至查找完最后一个结点，然后将p指向下一个待查找的字符，t继续从p的下一个结点开始，重复上述过程，直至将链表中的所有结点都查找一遍，最后，链表中存储的就是字符串中不同的字符及它们各自在字符串中的出现次数，以上操作完成后，将链表的头指针返回，算法结束；2 status auto_calculation(linklist l）：l为之前建立好的链表的头结点指针，如果链表不为空，则用p指

11、向头结点的下一个结点，然后用一个for循环输出链表中各个结点中的字符及其对应的权值（这里为字符在字符串中的出现次数为其权值），同时用一个变量n统计出不同字符的个数，然后给一个指向整型变量的全局指针w开辟n个连续的存储整型数据的内存单元，将开辟好的存储空间的首地址返回给w，然后用一个指针p从链表的第一个结点开始，循环的将各个结点中的权值赋到w的每个存储单元中。如果链表为空，输出“统计错误”的提示信息。最后返回一个状态值；3 status input_weight(linklist l)：l为之前建立好的链表的头结点指针，将指针p指向链表头结点的下一个结点（即第一个结点），如果链表不为空，p从第一

12、个结点开始直至最后一个，循环的得到用户给当前结点中字符赋的权值，同时用一个整型变量n统计链表的结点数，根据n的大小开辟一段存储整型数据的连续存储单元，并将此段存储空间的首地址返回给全局指针变量w，然后将链表中每个结点的权值赋到w这个数组的每个存储单元中。如果链表为空，则输出相应的提示信息，最后返回一个状态值;4 void creat_huffmantree(huffmantree &ht,linklist l)：l为之前建立好的链表的头结点的指针，ht用来返回构造好的赫夫曼树的头指针。首先，用一个指针temp_p指向l的下一个结点（即链表的第一个结点），然后用一个n统计出链表的结点数，即得到字

13、符串中不同字符的个数，如果nhead，head=p n=0 是 否 0=i 当it-a.code; 1=t-a.weight; t=p-next; null=t-next; 输出“没有字符” p=p-next p!=null p-next=t; p=p1; t!=null p-a.code=t-a.code 是 否 p-a.weight+ t-next=p-next t=p1; t=temp_p t-next=t; t-next=t 返回指针head的值2 status auto_calculation(linklist l)：自动统计权值的函数，以每个字符在字符串中出现的次数为权值开始调用函

14、数l-next=pp=null 是 否 0=n; pnull 输出字符及其对应的权值 n+;p-next=p; 输出“统计错误，没有字符！”用malloc开辟n个连续的整型 存储单元，首地址赋给w l-next=p; 0=i;当ia.weight=wi; 返回状态值ok; 返回状态值error函数调用完成3 status input_weight(linklist l)：手动输入各个字符权值的函数开始调用函数l-next=ppnull 是 否 0=n l-next=ppnull 输入结点中每个字符的权值=p-a.weightn+p-next=p 输出“没有字符”的提示信息 用malloc开辟n

15、个连续的整型存储单元，并把首地址赋给wl-next=p0=i 当 ia.weight=wi返回状态值ok 返回状态值error函数调用完毕4 void select(huffmantree &ht,int nn,int *s11,int *s22):在构造赫夫曼树的顺序表中选出双亲为0，且权值最小的两个结点，并用s11和s22返回这两个结点所在顺序表中的序号开始调用函数ht=p1=k当knn pk.parent=0 是 否 pk.weight=temp k=*s11 k+ break 1=k当knn pk.parent=0 是 否 pk.weighttemp k+ k=*s11 1=k当knn

16、 pk.parent=0且k*s11是 否 pk.weight=temp k=*s22 k+ break 1=k当knnpk.weight=0且k*s11 是 否 pk.weighttemp k=*s22函数调用完毕5 void creat_huffmantree(huffmantree &ht,linklist l)：建立赫夫曼树的函数开始调用函数l-next=temp_p当temp_pnulln+temp_p-next=temp_pn1 是 否 函数调用完毕 用malloc开辟n个连续htnode 类型的存储单元，并把首地址赋给ht ht=p,1=i 当in时 wi-1=pi.weight

17、; 0=pi.lchild 0=pi.rchlid 0=pi.parent i+ 当im时0=pi.weight;0=pi.parent;0=pi.lchild0=pi.rchild;i+n+1=iim0=s1;0=s2调用select(ht,i-1,&s1,&s2)i=hts1.parenti=hts2.parents1=hti.lchilds2=hti.rchildhti.weight=hts1.weight+hts2.weighti+1=jjphead-next=tp1=i当in且tpnulli=k1=j,pk.parent=mpm.lchild=k是 否 0=tp-a.cj-1 1=t

18、p-a.cj-1 当j-1tp-a.cj-1 i+ tp-next=tp 函数调用完毕7 void calculte_code(char temp,linklist head)：输出各个字符及整个字符串编码的函数开始调用函数head-next=p当pnull输出p-a.code0=n0=i当p-a.ci0n+i+n-1=i当i0输出p-a.cii-输出“电文的编码：”0=m0=k当tempk0m+k+0=i当inext=p当pnull p-a.code=tempi 是 否 0=n;0=j 当p-a.cj0 n+ j+ n-1=j 当j0 输出p-a.cj j+ 输出“n”函数调用完毕（3） 源

19、程序：(由于采用了c+中的引用形参，因此必须采用.cpp为扩展名的源文件编译）/huffmancoding.cpp#include#include#include#define length 100;#define ok 1;#define error 0;typedef int status;typedef structunsigned int weight;unsigned int lchild ,rchild ,parent;htnode,*huffmantree;typedef structchar code;unsigned int weight;char c10;code,*cod

20、e_p;typedef struct lnodecode a;struct lnode *next;node,*linklist;typedef char *huffmancode;int *w; /w存放n个字符的相应权值linklist calculation(char temp,int n) /统计字符种类及各个字符在字符串中出现次数的函数，n表示字符串的个数int i=0;linklist p;linklist t;linklist head;/创建一个字符串链表head=(linklist)malloc(sizeof(node); /创建一个带头结点的链表head-next=null

21、;p=head;if(n!=0)/将字符串存储到一个链表中，每个结点存储一个字符，方便后续统计字符的种类个数及其各个字符的权值for(i=0;ia.code=tempi;t-a.weight=1; /权值先初始化为1p-next=t;t-next=null;p=p-next;/*对链表进行处理，字符串中的每种字符只保留一个，同时统计每种字符在字符串中出现的次数，如果采用自动统计权值的话， 就以每个字符在字符串中出现的次数作为其权值*/linklist p1;p=head-next;linklist temp_p;while(p!=null)t=p-next;p1=p;while(t!=null

22、)if(p-a.code=t-a.code)p-a.weight+;p1-next=t-next;temp_p=t;t=t-next;free(temp_p);elsep1=t;t=t-next;p=p-next;elseprintf(没有字符！);return head;status auto_calculation(linklist l) /自动统计权值的函数，以每个字符在字符串中出现的次数作为其权值printf(各字符权值统计如下：n);linklist p=l-next;if(p)int n=0;for(;p!=null;p=p-next)printf(%c : %d,p-a.code

23、,p-a.weight);printf(n);n+;w=(int *)malloc(n*sizeof(int);p=l-next;int i;for(i=0;inext)wi=p-a.weight;return ok;elseprintf(统计错误，没有字符！n);return error;status input_weight(linklist l) /手动输入各个字符权值的函数linklist p=l-next;if(p!=null)int n=0;printf(请输入各个字符的权值：n);for(p=l-next;p!=null;p=p-next)printf(%c:,p-a.code)

24、;scanf(%d,&p-a.weight);n+;w=(int *)malloc(n*sizeof(int);p=l-next;int i=0;for(i=0;inext)wi=p-a.weight;return ok;elseprintf(没有字符！n);return error;void select(huffmantree &ht,int nn,int *s11,int *s22)int temp=0;huffmantree p=ht;int k;for(k=1;k=nn;k+)if(!pk.parent)temp=pk.weight;*s11=k;break;for(k=1;k=nn

25、;k+)if(!pk.parent)if(pk.weighttemp)temp=pk.weight;*s11=k;for(k=1;k=nn;k+)if(!pk.parent&k!=*s11)temp=pk.weight;*s22=k;break;for(k=1;k=nn;k+)if(!pk.parent&k!=*s11)if(pk.weight*s22)temp=*s11;*s11=*s22;*s22=temp;/建立赫夫曼树void creat_huffmantree(huffmantree &ht,linklist l)int n=0;linklist temp_p=l-next;for(

26、;temp_p!=null;temp_p=temp_p-next) /统计字符串中不同字符的个数n+;if(n=1)return;int m=2*n-1;int i;huffmantree p;ht=(huffmantree)malloc(m+1)*sizeof(htnode); /零号单元未用for(p=ht,i=1;i=n;i+) /给它赋上相应的权值pi.weight=wi-1;pi.lchild=0;pi.rchild=0;pi.parent=0;for(;i=m;i+)pi.weight=0;pi.parent=0;pi.lchild=0;pi.rchild=0;int s1,s2;

27、 /建立huffman树for(i=n+1;i=m;i+)s1=0;s2=0;select(ht,i-1,&s1,&s2);hts1.parent=i;hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;int j;for(j=1;jnext;int m;int k;int j;int i;for(i=1;inext)k=i;for(j=1,m=pk.parent; m!=0; k=m,m=pk.parent,j+)if(pm.lchild=k)tp-a.cj-1=0;elsetp-a.cj-

28、1=1;for(;j-1a.cj-1=0;void calculte_code(char temp,linklist head)int n;linklist p=head-next;printf(各个字符的编码如下：n);for(;p!=null;p=p-next)printf(%c:,p-a.code);n=0;for(int i=0;p-a.ci!=0;i+)n+;for(int i=n-1;i=0;i-)printf(%c,p-a.ci);printf(n);printf(电文的编码：);int m=0;for(int k=0;tempk!=0;k+)m+;int i,j;for(i=0

29、;inext;p!=null;p=p-next)if(p-a.code=tempi)n=0;for(j=0;p-a.cj!=0;j+)n+;for(j=n-1;j=0;j-)printf(%c,p-a.cj);printf(n);void main()char s100;int n=0;huffmantree ht=null;linklist l;printf(请输入一串电文：);scanf(%s,&s);for(int i=0;si!=0;i+)n+;if(n!=1) /一个结点无法构造赫夫曼树，无赫夫曼编码l=calculation(s,n);int num=0;char choice;d

30、ochoice=n;printf(t1.自动统计字符权值（以每个字符在字符串中出现的次数作为其权值）nt2.手动输入字符的权值n);printf(tt请选择：);scanf(%d,&num);switch(num)case 1:auto_calculation(l);break;case 2:input_weight(l);break;default:printf(选项输入错误，重新选择(y/n)？n);scanf(%c,&choice);while(choice=y|choice=y);creat_huffmantree(ht,l);text_code(ht,l,n);calculte_co

31、de(s,l);elseprintf(只有一个字符，无法构造赫夫曼树,无赫夫曼编码！n);4、 调试结果（1） 自动统计的调试结果（截图）：（2） 手动输入权值的调试结果（截图）：5、 课程设计总结：赫夫曼树作为一种最优二叉树，它的特点就是树的n个叶子结点的带权路径长度最短，树的带权路径长度也是最短的，因此，赫夫曼树在解决最佳判定问题以及最短编码问题等领域有着重要的应用。本次课程设计就是利用赫夫曼树对一段已知权值的字符串进行赫夫曼编码的应用，赫夫曼编码的特点是编码最短，且在译码过程中不会产生歧义，当用户输入一段字符串以后，我们可以根据用户对每个字符赋的权值，或者可以根据统计出的每个字符在字符串中出现的次数作为权值对每个字符求解赫夫曼编码。在整个程序设计中，我设计了两个功能模块供用户选择：一个是利用每个字符在字符串中出现的次数作为其权值对其进行编码；另一个就是根据用户对每个字符自定义的权值对其进行编码。在程序设计中，我利用到了链表这种数据结构对字符串中的字符种类个数进行统计，同时通过查找链表结点，得到每个字