数据结构实验――赫夫曼编码

1、实验题目：赫夫曼编码1、请根据该内容设计其中出现的字符的赫夫曼编码。2、用设计出的赫夫曼编码对英文内容进行编码和译码。要求：1. 以文件（.txt格式）形式输入英文内容。2. 以文件（.txt格式）形式输出各字符的赫夫曼编码。（注意标点符号和英文大小写）3. 以文件（.txt格式）形式输出编码后的结果。源程序：#include #include #include #define M 10000 /定义字符串最大长度#define N 128 /定义叶子节点个数typedef struct node /定义赫夫曼树节点结构体int weight;struct node *LChild,*RChi

2、ld,*Parent; /分别指向该节点的左孩子，右孩子和双亲节点struct node *next; /指向建立的赫夫曼树的下一个节点HFMNode,*HFMTree;typedef struct /定义赫夫曼编码的结构体char ch; /存储对应的字符char codeN+1; /存储对应字符的编码int start; /存储编码的起始位置CodeNode;int n; /存储真正叶子节点个数void clearscreen(system("cls"void Open(char s /打开存放字符或编码的文件，将其存入字符串数组中char name10;FILE *f

3、p;int i=0;printf("请输入要打开的文件名(加后缀名："gets(name; /要打开的文件名if(fp=fopen(name,"rt"=NULLprintf("打开失败！n" /若打开失败，则直接退出exit(1;si+=fgetc(fp;while(si-1!=EOFsi+=fgetc(fp;si='0' /存取字符串结束fclose(fp;void Save(char s /保存字符或编码到文件中char name10;FILE *fp;printf("请输入要保存的文件名(加后缀名：&q

4、uot;gets(name;if(fp=fopen(name,"wt"=NULLprintf("存储失败！"exit(1;fputs(s,fp;printf("n保存成功，文件名为:%s。n",name;printf("n按回车键继续."getchar(;fclose(fp;void SearchStr(char s,char str,int count /查找字符串中字符的个数和每个字符出现的次数int i,j,k=0;for(i=0;i 初始化每个字符出现的次数 counti=0;for(i=0;si;i+fo

5、r(j=0;j 在 str 中查找是否有该字符 if(strj=sicountj+;break;if(j=k /在str中无该字符，将其存入最后一个单元strk=si;countk+;strk='0' /将字符串结尾置0n=k; /将实际的字符个数作为叶子节点个数存入nvoid SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2/查找赫夫曼链表中两个权值最小的节点int i,min;HFMTree p;min=32767;for(i=0,p=HT;i next if(p->weight Parent=0 min=p-&

6、gt;weight;*HT1=p;min=32767;for(i=0,p=HT;i next if(p->weight Parent=0&&p!=*HT1 / 令第二个最小的节点不等于第一个节点min=p->weight;*HT2=p;void CreatHFMTree(HFMTree *HT,int count/创建赫夫曼树int i;HFMTree p,HT1,HT2; /HT1，HT2分别存放权值最小和次小的节点的位置p=*HT=(HFMTreemalloc(sizeof(HFMNode;p->next=p->LChild=p->RChild

7、=p->Parent=NULL; /初始化赫夫曼链表且有2n-1个节点for(i=1;i<2*n-1;i+p->next=(HFMTreemalloc(sizeof(HFMNode;p=p->next;p->next=p->LChild=p->RChild=p->Parent=NULL;for(i=0,p=*HT;i 将各个字符出现的次数作为权值 /存入赫夫曼链表的前n个单元中p->weight=counti;p=p->next;for(i=n;i<2*n-1;i+ /将后n-1个节点赋权值，建树SelectMin(*HT,i,

8、&HT1,&HT2; /每次从前i个节点中选取权值最小的两个节点HT1->Parent=HT2->Parent=p; p->LChild=HT1;p->RChild=HT2;p->weight=HT1->weight+HT2->weight; /将两个节点的权值相加存入最后一个节点中p=p->next; /p指向下一个没有存储权值的节点void HFMCode(HFMTree HT,CodeNode HC,char str/从每个叶子节点开始，利用赫夫曼树对每个字符进行编码，最终建立一个赫夫曼表int i;HFMTree q,p=

9、HT;for(i=0;i 将字符存入 赫夫曼编码 结构体数组的字符单元中 HCi.ch=stri;HCi.coden-1='0' /初始化编码的最后一位for(i=0;i HCi.start=n-1;for(q=p;q->Parent;q=q->Parent /判断q所指向的节点，左孩子置0，右孩子置1if(q=q->Parent->LChildHCi.code-HCi.start='0'else HCi.code-HCi.start='1'p=p->next; /判断下一个叶子节点FILE *fp;if(fp=fo

10、pen("对应编码.txt","w+"=NULLprintf("无法打开n"exit(1;for(i=0;i fprintf(fp,"%c的编码是",HCi.ch;fprintf(fp,"%sn",HCi.code;fclose(fp;void TotalCoding(char s,CodeNode HC,char code/利用赫夫曼编码表对整个字符串进行编码int i,j;code0='0' /编码数组初始化for(i=0;si;i+ /将每个字符在赫夫曼编码表中对应的编码存

11、入存放总编码的数组中for(j=0;j if(si=HCj.chstrcpy(code+strlen(code,HCj.code+HCj.start;void DeCoding(char code,HFMTree HT,char str,char s/对赫夫曼编码进行解码，放入字符串s中int i,j,k=0;HFMTree root,p,q;for(root=HT;root->Parent;root=root->Parent; /用root指向赫夫曼树的根节点for(i=0,p=root;codei;i+ /从根节点开始按编码顺序访问树 if(codei='0'p

12、=p->LChild;else p=p->RChild;if(p->LChild=NULL&&p->RChild=NULL /到根节点时将该节点对应的字符输出for(j=0,q=HT;q!=p;q=q->next,j+;sk+=strj;p=root; /回溯到根节点 sk='0' /解码完毕，在字符串最后一个单元存入'0'void Coding(char s,char str,char code,int count,HFMTree *HT,CodeNode HCclearscreen(;printf("n

13、打开存放字符串的文件.nn"Open(s; /打开源码文件SearchStr(s,str,count; /查找字符串中不同的字符及其出现的次数CreatHFMTree(HT,count; /用每个字符出现的次数作为叶子节点的权值建立赫夫曼树HFMCode(*HT,HC,str; /利用赫夫曼树对每个叶子节点进行编码，存入编码表中TotalCoding(s,HC,code; /利用编码表对字符串进行最终编码printf("n读入的字符串为:n"puts(s;printf("n最终的赫夫曼编码是:n"puts(code;printf("n

14、对应编码已输出到: 对应编码.txtn"printf("n保存编码,"Save(code; /保存最终的赫夫曼编码void TransCode(char code,char str,char ss,HFMTree *HT,CodeNode HCclearscreen(;printf("n打开编码的文件.nn"Open(code; /打开编码文件DeCoding(code,*HT,str,ss; /将编码进行解码存入字符串数组ss中printf("n得到的最终字符串为:n"puts(ss;printf("n保存译码，

15、"Save(ss; /保存译码后的字符串void main(/主函数char sM,ssM; /定义字符串数组，s存放将要编码的字符串，ss存解码后的字符串char strN; /存放输入的字符串中n个不同的字符int countN; /存放n个不同字符对应的在原字符串中出现的次数char codeM; /存放最终编码完成后的编码char choice;HFMTree HT; /定义一个赫夫曼树的链表CodeNode HCN; /定义一个赫夫曼编码表的数组，存放每个字符对应的赫夫曼编码doclearscreen(;printf("赫夫曼编码译码系统n"printf("1.进行编码n"printf("2.进行译码n"printf("0.退出n"scanf("%c",&choice;getcha