數(shù)據(jù)結(jié)構(gòu)實驗――赫夫曼編碼

1、實驗題目：赫夫曼編碼1、請根據(jù)該內(nèi)容設(shè)計其中出現(xiàn)的字符的赫夫曼編碼。2、用設(shè)計出的赫夫曼編碼對英文內(nèi)容進行編碼和譯碼。要求：1. 以文件（.txt格式）形式輸入英文內(nèi)容。2. 以文件（.txt格式）形式輸出各字符的赫夫曼編碼。（注意標點符號和英文大小寫）3. 以文件（.txt格式）形式輸出編碼后的結(jié)果。源程序：#include #include #include #define M 10000 /定義字符串最大長度#define N 128 /定義葉子節(jié)點個數(shù)typedef struct node /定義赫夫曼樹節(jié)點結(jié)構(gòu)體int weight;struct node *LChild,*RChi

2、ld,*Parent; /分別指向該節(jié)點的左孩子，右孩子和雙親節(jié)點struct node *next; /指向建立的赫夫曼樹的下一個節(jié)點HFMNode,*HFMTree;typedef struct /定義赫夫曼編碼的結(jié)構(gòu)體char ch; /存儲對應(yīng)的字符char codeN+1; /存儲對應(yīng)字符的編碼int start; /存儲編碼的起始位置CodeNode;int n; /存儲真正葉子節(jié)點個數(shù)void clearscreen(system("cls"void Open(char s /打開存放字符或編碼的文件，將其存入字符串數(shù)組中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' /存取字符串結(jié)束fclose(fp;void Save(char s /保存字符或編碼到文件中char name10;FILE *fp;printf("請輸入要保存的文件名(加后綴名：&q

4、uot;gets(name;if(fp=fopen(name,"wt"=NULLprintf("存儲失?。?quot;exit(1;fputs(s,fp;printf("n保存成功，文件名為:%s。n",name;printf("n按回車鍵繼續(xù)."getchar(;fclose(fp;void SearchStr(char s,char str,int count /查找字符串中字符的個數(shù)和每個字符出現(xiàn)的次數(shù)int i,j,k=0;for(i=0;i 初始化每個字符出現(xiàn)的次數(shù) 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' /將字符串結(jié)尾置0n=k; /將實際的字符個數(shù)作為葉子節(jié)點個數(shù)存入nvoid SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2/查找赫夫曼鏈表中兩個權(quán)值最小的節(jié)點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 / 令第二個最小的節(jié)點不等于第一個節(jié)點min=p->weight;*HT2=p;void CreatHFMTree(HFMTree *HT,int count/創(chuàng)建赫夫曼樹int i;HFMTree p,HT1,HT2; /HT1，HT2分別存放權(quán)值最小和次小的節(jié)點的位置p=*HT=(HFMTreemalloc(sizeof(HFMNode;p->next=p->LChild=p->RChild

7、=p->Parent=NULL; /初始化赫夫曼鏈表且有2n-1個節(jié)點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 將各個字符出現(xiàn)的次數(shù)作為權(quán)值 /存入赫夫曼鏈表的前n個單元中p->weight=counti;p=p->next;for(i=n;i<2*n-1;i+ /將后n-1個節(jié)點賦權(quán)值，建樹SelectMin(*HT,i,

8、&HT1,&HT2; /每次從前i個節(jié)點中選取權(quán)值最小的兩個節(jié)點HT1->Parent=HT2->Parent=p; p->LChild=HT1;p->RChild=HT2;p->weight=HT1->weight+HT2->weight; /將兩個節(jié)點的權(quán)值相加存入最后一個節(jié)點中p=p->next; /p指向下一個沒有存儲權(quán)值的節(jié)點void HFMCode(HFMTree HT,CodeNode HC,char str/從每個葉子節(jié)點開始，利用赫夫曼樹對每個字符進行編碼，最終建立一個赫夫曼表int i;HFMTree q,p=

9、HT;for(i=0;i 將字符存入 赫夫曼編碼 結(jié)構(gòu)體數(shù)組的字符單元中 HCi.ch=stri;HCi.coden-1='0' /初始化編碼的最后一位for(i=0;i HCi.start=n-1;for(q=p;q->Parent;q=q->Parent /判斷q所指向的節(jié)點，左孩子置0，右孩子置1if(q=q->Parent->LChildHCi.code-HCi.start='0'else HCi.code-HCi.start='1'p=p->next; /判斷下一個葉子節(jié)點FILE *fp;if(fp=fo

10、pen("對應(yīng)編碼.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' /編碼數(shù)組初始化for(i=0;si;i+ /將每個字符在赫夫曼編碼表中對應(yīng)的編碼存

11、入存放總編碼的數(shù)組中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指向赫夫曼樹的根節(jié)點for(i=0,p=root;codei;i+ /從根節(jié)點開始按編碼順序訪問樹 if(codei='0'p

12、=p->LChild;else p=p->RChild;if(p->LChild=NULL&&p->RChild=NULL /到根節(jié)點時將該節(jié)點對應(yīng)的字符輸出for(j=0,q=HT;q!=p;q=q->next,j+;sk+=strj;p=root; /回溯到根節(jié)點 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; /查找字符串中不同的字符及其出現(xiàn)的次數(shù)CreatHFMTree(HT,count; /用每個字符出現(xiàn)的次數(shù)作為葉子節(jié)點的權(quán)值建立赫夫曼樹HFMCode(*HT,HC,str; /利用赫夫曼樹對每個葉子節(jié)點進行編碼，存入編碼表中TotalCoding(s,HC,code; /利用編碼表對字符串進行最終編碼printf("n讀入的字符串為:n"puts(s;printf("n最終的赫夫曼編碼是:n"puts(code;printf("n

14、對應(yīng)編碼已輸出到: 對應(yīng)編碼.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; /將編碼進行解碼存入字符串數(shù)組ss中printf("n得到的最終字符串為:n"puts(ss;printf("n保存譯碼，

15、"Save(ss; /保存譯碼后的字符串void main(/主函數(shù)char sM,ssM; /定義字符串數(shù)組，s存放將要編碼的字符串，ss存解碼后的字符串char strN; /存放輸入的字符串中n個不同的字符int countN; /存放n個不同字符對應(yīng)的在原字符串中出現(xiàn)的次數(shù)char codeM; /存放最終編碼完成后的編碼char choice;HFMTree HT; /定義一個赫夫曼樹的鏈表CodeNode HCN; /定義一個赫夫曼編碼表的數(shù)組，存放每個字符對應(yīng)的赫夫曼編碼doclearscreen(;printf("赫夫曼編碼譯碼系統(tǒng)n"printf("1.進行編碼n"printf("2.進行譯碼n"printf("0.退出n"scanf("%c",&choice;getcha