數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-哈夫曼樹及編碼

HUFFMAN樹及編碼需求分析隨機輸入一篇英文文章（或讀一個TXT文件），生成并顯示HUFFMAN樹，輸出每個字母的HUFFMAN編碼，判斷ASCII編碼與HUFFMAN編碼對本篇報文長度節(jié)省效果。(a)輸入的形式為鍵盤隨機輸入，輸入的字符串長度在10000以內(nèi)；(b)輸出HUFFMAN樹的存儲結(jié)構(gòu)；(c)程序功能為輸入英文文章中每個字母的HUFFMAN編碼，以及與ASCLL碼編碼長度的比較結(jié)果；(d)測試數(shù)據(jù)：正確的輸入一篇英文文章，會輸出各個字母的HUFFMAN編碼。錯誤的輸入即其輸出輸入錯誤。2.概要設(shè)計首先統(tǒng)計英文文章中各個字母的個數(shù)作為權(quán)值，再統(tǒng)計出現(xiàn)的字母的個數(shù)，以決定所構(gòu)造赫夫曼樹的節(jié)點個數(shù)，之后便開始構(gòu)造赫夫曼樹，再構(gòu)造每個節(jié)點的哈夫曼編碼。所設(shè)計的抽象數(shù)據(jù)類型如下：typedefstruct{unsignedintweight;//權(quán)值unsignedintparent,lchild,rchild;//雙親，左孩子，右孩子}HTNode,*HuffmanTree;typedefchar**HuffmanCode;所設(shè)計的函數(shù)如下：intmin(HuffmanTreeHT,inti)找出所有權(quán)值中最小的那個。voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)找出每次最小的兩個權(quán)值最小的權(quán)值。StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)構(gòu)造赫夫曼樹并構(gòu)造每個字母的赫夫曼編碼。voidPrintHT(HuffmanTreeHT,intn)輸出赫夫曼樹的存儲結(jié)構(gòu)。3.詳細(xì)設(shè)計intmin(HuffmanTreeHT,inti){intj,flag=1;unsignedintk=10000;for(j=1;j<=i;j++){if(HT[j].weight<k&&HT[j].parent==0){k=HT[j].weight,flag=j;}//if}HT[flag].parent=1;returnflag;}voidSelect(HuffmanTreeHT,inti,int&s1,int&s2){intj;s1=min(HT,i);s2=min(HT,i);if(s1>s2){j=s1;s1=s2;s2=j;}}StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){ints1,s2,i,start,f;char*cd;HuffmanTreep=NULL;//p是工作指針，指向赫夫曼樹中的結(jié)點if(n<=1){returnERROR;}intm=2*n-1;//n個字符構(gòu)造的赫夫曼樹共有m=2*n-1個結(jié)點printf("->待構(gòu)造的赫夫曼樹共有2×%d-1=%d個結(jié)點\n",n,m);if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))//申請赫夫曼樹結(jié)點占用的內(nèi)存空間,0號單元不用{exit(OVERFLOW);}//ifprintf("->赫夫曼樹共分配了%d個結(jié)點空間，其中包含一個不用的0號單元\n",m+1);//printf("->初始化所有葉子節(jié)點的權(quán)值，父親和孩子：\n");for(p=HT+1,i=1;i<=n;++i,++p,++w){p->weight=*w;p->parent=0;//雙親初始值為0，表示此結(jié)點還沒有被選擇最小的算法選擇過p->lchild=0;//左右孩子初始化為0，表示空p->rchild=0;}for(;i<=m;i++,p++){p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;++i){Select(HT,i-1,s1,s2);HT[s1].parent=i;//選出的兩個權(quán)值最小的結(jié)點的雙親就是即將生成的結(jié)點HT[s2].parent=i;HT[i].lchild=s1;//即將生成的結(jié)點左孩子是s1，右孩子是s2，HT[i].rchild=s2;//因為s1比s2先選，所以s1總是小于等于s2HT[i].weight=HT[s1].weight+HT[s2].weight;//即將生成結(jié)點的權(quán)值就是兩個權(quán)值最小的結(jié)點的權(quán)值之和}if(!(HC=(HuffmanCode)malloc((n+1)*sizeof(char*)))){exit(OVERFLOW);}//ifif(!(cd=(char*)malloc(n*sizeof(char)))){exit(OVERFLOW);}cd[n-1]='\0';for(inti=1;i<=n;++i){start=n-1;for(intc=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c){cd[--start]='0';}//ifelse//葉子結(jié)點根結(jié)點的右孩子{cd[--start]='1';}//else}if(!(HC[i]=(char*)malloc((n-start)*sizeof(char)))){exit(OVERFLOW);}strcpy(HC[i],&cd[start]);//printf("->葉子節(jié)點%d的赫夫曼編碼為:%s\n",i,HC[i]);}free(cd);returnOK;}//HuffmanCodingvoidPrintHT(HuffmanTreeHT,intn){intm=2*n-1;printf("\n+-------------------------------------------------------------+\n");printf("|赫夫曼樹HT的存儲結(jié)構(gòu)|\n");printf("+----------+----------+----------+--------------+-------------+\n");printf("|結(jié)點編號|weight|parent|leftchild|rightchild|\n");printf("+----------+----------+----------+--------------+-------------+\n");for(inti=1;i<=m;i++){printf("|%4d|%4d|%4d|%4d|%4d|\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);printf("+----------+----------+----------+--------------+-------------+\n");}}for(inti=0;i<len;i++){if(str[i]=='A')a[65]++;elseif(str[i]=='B')a[66]++;elseif(str[i]=='C')a[67]++;elseif(str[i]=='D')a[68]++;elseif(str[i]=='E')a[69]++;elseif(str[i]=='F')a[70]++;elseif(str[i]=='G')a[71]++;elseif(str[i]=='H')a[72]++;elseif(str[i]=='I')a[73]++;elseif(str[i]=='J')a[74]++;elseif(str[i]=='K')a[75]++;elseif(str[i]=='L')a[76]++;elseif(str[i]=='M')a[77]++;elseif(str[i]=='N')a[78]++//部分統(tǒng)計字母代碼主程序首先隨機輸入一篇英文文章，再統(tǒng)計各字母個數(shù)，再調(diào)用HuffmanCoding(HT,HC,w,n)函數(shù)，此函數(shù)又會調(diào)用voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)函數(shù)，而此函數(shù)又會調(diào)用intmin(HuffmanTreeHT,inti)函數(shù)，構(gòu)造完成后便調(diào)用PrintHT(HT,n)函數(shù)輸出赫夫曼樹的存儲結(jié)構(gòu)。IIntmain()主函數(shù)調(diào)用HuffmanCoding(HT,HC,w,n)HuffmanCoding(HT,HC,w,n)調(diào)用voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)調(diào)用intmin(HuffmanTreeHT,inti)intmin(HuffmanTreeHT,inti)PrintHT(HT,n) 調(diào)用PrintHT(HT,n)輸入界面：輸出界面：4.調(diào)試分析(a)調(diào)試過程中未設(shè)計多種不合理輸入的對應(yīng)輸出結(jié)果，后加上。(b)算法的時間復(fù)雜度為O(n3),StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)函數(shù)中的一重for循環(huán)調(diào)用了select函數(shù)，而select函數(shù)又調(diào)用了min函數(shù)，故共有三重for循環(huán)，故時間復(fù)雜度為O(n3)。(c)通過這次課程設(shè)計，讓我受益匪淺，使我掌握了二叉樹的的存儲結(jié)構(gòu)和赫夫曼編碼的基本思想。程序中有多處運用了三重循環(huán)，這里很多地方可以優(yōu)化以達(dá)到減小時間和空間復(fù)雜度。在此次課程設(shè)計的最大收獲就是讓我明白一個道理：無論你做的是多么小的一個程序或軟件，都要使用模塊化設(shè)計，這樣使程序?qū)崿F(xiàn)的功能更清晰明了。5.用戶使用說明直接輸入一篇英文文章即可。6.測試結(jié)果正確輸入：ThereisnodoubtthatInternethaschangedourlifegreatlyItmakestheworldsmallerPeoplecangettoknowtheworldinashorttimeandmakefriendsfromallovertheworldWhileontheotherhandthemuchattentionontheInternetisolatesthedistanceandreducesfacetofacecommunicationManyyearsagobeforethepopularityofcomputerpeoplegottoknowtheworldbylisteningtotheradioorreadingnewspaperButnowadayspeoplecanjustreadtheinstantnewsontheInternetandgetthefirsthandinformationimmediatelyThefastwaytomasterinformationmakesthemfeelkeepingintouchwiththeworldTheworldseemssoneartothem結(jié)果：‘b．錯誤的輸入7.測試情況：測試情況如設(shè)計的一致，首先輸出各字母及在文章出現(xiàn)的次數(shù)，再輸出各字母的赫夫曼編碼，最后輸出ASCLL碼與赫夫曼編碼的差異。附程序源代碼：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineOVERFLOW-2#defineOK1#defineERROR0typedefintStatus;typedefstruct{unsignedintweight;//權(quán)值unsignedintparent,lchild,rchild;//雙親，左孩子，右孩子}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲赫夫曼樹typedefchar**HuffmanCode;//動態(tài)分配數(shù)組存儲赫夫曼編碼表intmin(HuffmanTreeHT,inti){intj,flag=1;unsignedintk=10000;for(j=1;j<=i;j++){if(HT[j].weight<k&&HT[j].parent==0){k=HT[j].weight,flag=j;}//if}HT[flag].parent=1;returnflag;}voidSelect(HuffmanTreeHT,inti,int&s1,int&s2){intj;s1=min(HT,i);s2=min(HT,i);if(s1>s2){j=s1;s1=s2;s2=j;}}voidPrintHT(HuffmanTreeHT,intn){intm=2*n-1;printf("\n+-------------------------------------------------------------+\n");printf("|赫夫曼樹HT的存儲結(jié)構(gòu)|\n");printf("+----------+----------+----------+--------------+-------------+\n");printf("|結(jié)點編號|weight|parent|leftchild|rightchild|\n");printf("+----------+----------+----------+--------------+-------------+\n");for(inti=1;i<=m;i++){printf("|%4d|%4d|%4d|%4d|%4d|\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);printf("+----------+----------+----------+--------------+-------------+\n");}}StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){ints1,s2,i,start,f;char*cd;HuffmanTreep=NULL;//p是工作指針，指向赫夫曼樹中的結(jié)點if(n<=1){returnERROR;}intm=2*n-1;//n個字符構(gòu)造的赫夫曼樹共有m=2*n-1個結(jié)點printf("->待構(gòu)造的赫夫曼樹共有2×%d-1=%d個結(jié)點\n",n,m);if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))//申請赫夫曼樹結(jié)點占用的內(nèi)存空間,0號單元不用{exit(OVERFLOW);}//ifprintf("->赫夫曼樹共分配了%d個結(jié)點空間，其中包含一個不用的0號單元\n",m+1);//printf("->初始化所有葉子節(jié)點的權(quán)值，父親和孩子：\n");for(p=HT+1,i=1;i<=n;++i,++p,++w){p->weight=*w;p->parent=0;//雙親初始值為0，表示此結(jié)點還沒有被選擇最小的算法選擇過p->lchild=0;//左右孩子初始化為0，表示空p->rchild=0;}for(;i<=m;i++,p++){p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;++i){Select(HT,i-1,s1,s2);HT[s1].parent=i;//選出的兩個權(quán)值最小的結(jié)點的雙親就是即將生成的結(jié)點HT[s2].parent=i;HT[i].lchild=s1;//即將生成的結(jié)點左孩子是s1，右孩子是s2，HT[i].rchild=s2;//因為s1比s2先選，所以s1總是小于等于s2HT[i].weight=HT[s1].weight+HT[s2].weight;//即將生成結(jié)點的權(quán)值就是兩個權(quán)值最小的結(jié)點的權(quán)值之和}if(!(HC=(HuffmanCode)malloc((n+1)*sizeof(char*)))){exit(OVERFLOW);}//ifif(!(cd=(char*)malloc(n*sizeof(char)))){exit(OVERFLOW);}cd[n-1]='\0';for(inti=1;i<=n;++i){start=n-1;for(intc=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c){cd[--start]='0';}//ifelse//葉子結(jié)點根結(jié)點的右孩子{cd[--start]='1';}//else}if(!(HC[i]=(char*)malloc((n-start)*sizeof(char)))){exit(OVERFLOW);}strcpy(HC[i],&cd[start]);//printf("->葉子節(jié)點%d的赫夫曼編碼為:%s\n",i,HC[i]);}free(cd);returnOK;}//HuffmanCodingintmain(){HuffmanTreeHT;HuffmanCodeHC;int*w;charstr[10005];inta[150],b[60];memset(a,0,sizeof(int)*150);printf("請隨機輸入英文文章：");scanf("%s",str);intlen=strlen(str);for(inti=0;i<len;i++){if(str[i]=='A')a[65]++;elseif(str[i]=='B')a[66]++;elseif(str[i]=='C')a[67]++;elseif(str[i]=='D')a[68]++;elseif(str[i]=='E')a[69]++;elseif(str[i]=='F')a[70]++;elseif(str[i]=='G')a[71]++;elseif(str[i]=='H')a[72]++;elseif(str[i]=='I')a[73]++;elseif(str[i]=='J')a[74]++;elseif(str[i]=='K')a[75]++;elseif(str[i]=='L')a[76]++;elseif(str[i]=='M')a[77]++;elseif(str[i]=='N')a[78]++;elseif(str[i]=='O')a[79]++;elseif(str[i]=='P')a[80]++;elseif(str[i]=='Q')a[81]++;elseif(str[i]=='R')a[82]++;elseif(str[i]=='S')a[83]++;elseif(str[i]=='T')a[84]++;elseif(str[i]=='U')a[85]++;elseif(str[i]=='V')a[86]++;elseif(str[i]=='W')a[87]++;elseif(str[i]=='X')a[88]++;elseif(str[i]=='Y')a[89]++;elseif(str[i]=='Z')a[90]++;elseif(str[i]=='a')a[97]++;elseif(str[i]=='b')a[98]++;elseif(str[i]=='c')a[99]++;elseif(str[i]=='d')a[100]++;elseif(str[i]=='e')a[101]++;elseif(str[i]=='f')a[102]++;elseif(str[i]=='g')a[103]++;elseif(str[i]=='h')a[104]++;elseif(str[i]=='i')a[105]++;elseif(str[i]=='j')a[106]++;elseif(str[i]=='k')a[107]++;elseif(str[i]=='l')a[108]++;elseif(str[i]=='m')a[109]++;elseif(str[i]=='n')a[110]++;elseif(str[i]=='o')a[111]++;elseif(str[i]=='p')a[112]++;elseif(str[i]=='q')a[113]++;elseif(str[i]=='r')a[114]++;elseif(str[i]=='s')a[115]++;elseif(str[i]=='t')a[116]++;