數(shù)據(jù)結構課程設計 哈夫曼樹及編碼

HUFFMAN樹及編碼需求分析隨機輸入一篇英文文章(或讀一個TXT文件)，生成并顯示HUFFMAN樹，輸出每個字母的HUFFMAN編碼，判斷ASCII編碼與HUFFMAN編碼對本篇報文長度節(jié)省效果。輸入的形式為鍵盤隨機輸入，輸入的字符串長度在10000以內；輸出HUFFMAN樹的存儲結構；程序功能為輸入英文文章中每個字母的HUFFMAN編碼，以及與ASCLL碼編碼長度的比較結果；測試數(shù)據(jù)：正確的輸入一篇英文文章，會輸出各個字母的HUFFMAN編碼。錯誤的輸入即其輸出輸入錯誤。概要設計首先統(tǒng)計英文文章中各個字母的個數(shù)作為權值，再統(tǒng)計出現(xiàn)的字母的個數(shù)，以決定所構造赫夫曼樹的節(jié)點個數(shù)，之后便開始構造赫夫曼樹，再構造每個節(jié)點的哈夫曼編碼。所設計的抽象數(shù)據(jù)類型如下：typedefstruct{unsignedintweight; //權值unsignedintparent,lchild,rchild;//雙親，左孩子，右孩子}HTNode,*HuffmanTree;typedefchar**HuffmanCode;所設計的函數(shù)如下：intmin(HuffmanTreeHT,inti)找出所有權值中最小的那個。voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)找出每次最小的兩個權值最小的權值。StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)構造赫夫曼樹并構造每個字母的赫夫曼編碼。voidPrintHT(HuffmanTreeHT,intn)輸出赫夫曼樹的存儲結構。詳細設計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是工作指針，指向赫夫曼樹中的結點if(n<=1){returnERROR;}intm=2*n-1;//n個字符構造的赫夫曼樹共有m=2*n-1個結點printf("->待構造的赫夫曼樹共有2X%d-1=%d個結點\n",n,m);if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))//申請赫夫曼樹結點占用的內存空間,0號單元不用{exit(OVERFLOW);}//if一 printf("->赫夫曼樹共分配了％d個結點空間，其中包含一個不用的0號單元\葉,m+1);//printf("->初始化所有葉子節(jié)點的權值，父親和孩子：\n");for(p=HT+1,i=1;i<=n;++i,++p,++w){p->weight=*w;p->parent=0;//雙親初始值為0,表示此結點還沒有被選擇最小的算法選擇過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;//選出的兩個權值最小的結點的雙親就是即將生成的結點HT[s2].parent=i;HT[i].lchild=s1;//即將生成的結點左孩子是s1,右孩子是s2,HT[i].rchild=s2;//因為s1比s2先選，所以s1總是小于等于s2HT[i].weight=HT[s1].weight+HT[s2].weight;//即將生成結點的權值就是兩個權值最小的結點的權值之和}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 〃葉子結點根結點的右孩子{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的存儲結構|\n");printf("+ + + + + +\n");printf("|結點編號|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ù)，再調用HuffmanCoding(HT,HC,w,再函數(shù)，此函數(shù)又會調用voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)函數(shù)，而此函數(shù)又會調用intmin(HuffmanTreeHT,inti)函數(shù)，構造完成后便調用PrintHT(HT,n)函數(shù)輸出赫夫曼樹的存儲結構。Intmain()主函數(shù)調用HuffmanCoding(HT,HC,w,n)調用voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)調用”intmin(HuffmanTreeHT,inti)PrintHT(HT,n)點PrintHT(HT,n)點調用輸入界面:請隨札輸入英文文命

ITC:\Users\ZHANG\Pegkto|p網(wǎng)g緒構課程設計湍夫是風編碼.exeip隨|FL輸入英父文K；：IhereisnodoubtthatInternethaschangedonrlifegreatlyltmake;asr..or71imeatidiDiakefrierdsfroma11overtAewor1dWhi1eon;r..eotherhandtherauchattenTi(facetofacecoounmiicationManyyearsagobe:orethepopulari^yofccunputerpeaplegottakispaperButnowadayspeaplecanjustreadtheinstantnewsontrieInternetandgett/e^firsth;二zonnatiotinakesthemfee1keepingintonchwiththewor1dTheworidseemssoneartothem輸出界面:Cl口\廿缶「sWHANC3\D巳skt^p檄拒結構課程設赫壬慎御緝回一以巳-＞待構造的赫夫曼樹共有2X29-1=57個結-＞赫夫曼樹共分配了58個結點空間,其中包含-個不用的0號單元-＞您建立的赫夫曼列對應的杯夫晝編碼如下］10111100001110101011110011011110101011111010111101111000111011000101101010000110011110011000101011111100111001101110110111011110001110100000010101110nmm ■JC:\Users\ZHANG\De新。p瀕據(jù)結構課程設計場5夫昌榭犒磚exe54 172 56 49 505521957515256315575354575340□556交章用赫夫曼編碼.共需169位1進制數(shù)文章用ASCLL瑪編瑪共需4272位故利用ASCLL碼編碼出要的位數(shù)是林夫曼編碼的有一墨倍調試分析調試過程中未設計多種不合理輸入的對應輸出結果，后加上。算法的時間復雜度為O(n3),StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)函數(shù)中的一重for循環(huán)調用了select函數(shù)，而select函數(shù)又調用了min函數(shù)，故共有三重for循環(huán)，故時間復雜度為O(n3)。通過這次課程設計，讓我受益匪淺，使我掌握了二叉樹的的存儲結構和赫夫曼編碼的基本思想。程序中有多處運用了三重循環(huán)，這里很多地方可以優(yōu)化以達到減小時間和空間復雜度。在此次課程設計的最大收獲就是讓我明白一個道理：無論你做的是多么小的一個程序或軟件，都要使用模塊化設計，這樣使程序實現(xiàn)的功能更清晰明了。用戶使用說明直接輸入一篇英文文章即可。測試結果a.正確輸入：ThereisnodoubtthatInternethaschangedourlifegreatlyItmakestheworldsmallerPeoplecangettoknowtheworldinashorttimeandmakefriendsfromallovertheworldWhileontheotherhandthemuchattentionontheInternetisolatesthedistanceandreducesfacetofacecommunicationManyyearsagobeforethepopularityofcomputerpeoplegottoknowtheworldbylisteningtotheradioorreadingnewspaperButnowadayspeoplecanjustreadtheinstantnewsontheInternetandgetthefirsthandinformationimmediatelyThefastwaytomasterinformationmakesthemfeelkeepingintouchwiththeworldTheworldseemssoneartothem結果:UC:\LHer氾HANG\D已sktop俊扼結構課程設計海夫旻挪-)赫夫曼樹共分配了5&個結點空間，其中包含-〉您建立的赫夫曼樹對應的赫夫曼編碼如S：1011110000111010101111001101111010101111101011110111100011101100010110101000011001111001100010101111110011100110111011011101111000111010000001010111010111111100111b.錯誤的輸入BC^UsersVHAN小盹如叩典堤融課程設計遍夫旻瓣碼.exe請I灼"輸入蛆文文直：12222222222222641234152985146656314566666656184641651498461846814高入錯誤!7.測試情況：測試情況如設計的一致，首先輸出各字母及在文章出現(xiàn)的次數(shù)，再輸出各字母的赫夫曼編碼，最后輸出ASCLL碼與赫夫曼編碼的差異。TOC\o"1-5"\h\z55 | 219 | 57 | 51 | 52 1 1 十I 56 | 315 | 57 | 53 | 54 |H F —rl 1 —rl-I 57 | 534 | 0 | 55 | 56 |T 1 1 1 —F文章用'赫夫曼編碼共需L69位:過制數(shù)文章用ASCLL碼嘛碼共啟2地位故利IJASCLL碼編碼芯要的位數(shù)是林夫曼編碼的25.找倍Processreturned0(0x0)execuTiontime:14.728sPressanykeytocontinue.附程序源代碼：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineOVERFLOW-2#defineOK1#defineERROR0typedefintStatus;typedefstruct(unsignedintweight; 〃權值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}1；HT[flag].parent=returnflag;1；}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的存儲結構l\n〃)；printf("+ + + + + —+\n〃);printf("|結點編號|weight|parent|leftchildrightchild|\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是工作指針，指向赫夫曼樹中的結點if(n<=1)(returnERROR;}intm=2*n-1;//n個字符構造的赫夫曼樹共有m=2*n-1個結點printf("->待構造的赫夫曼樹共有2X%d-1=%d個結點\n”,n,m);if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))//申請赫夫曼樹結點占用的內存空間,0號單元不用(exit(OVERFLOW);}//ifprintf(〃->赫夫曼樹共分配了％d個結點空間，其中包含一個不用的0號單元\/,m+1);//printf("->初始化所有葉子節(jié)點的權值，父親和孩子：\n");for(p=HT+1,i=1;i<=n;++i,++p,++w)(p->weight=*w;p->parent=0;//雙親初始值為0，表示此結點還沒有被選擇最小的算法選擇過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;//選出的兩個權值最小的結點的雙親就是即將生成的結點HT[s2].parent=i;HT[i].lchild=s1;//即將生成的結點左孩子是s1，右孩子是s2，HT[i].rchild=s2;//因為si比s2先選，所以si總是小于等于s2HT[i].weight=HT[s1].weight+HT[s2].weight;//即將生成結點的權值就是兩個權值最小的結點的權值之和}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〃葉子結點根結點的右孩子(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]==5i)a[105]++;elseif(str[i]=='j')a[106]++;elseif(str[i]=='k')a[107]++;elseif(str[i]==T')a[108]++;elseif(str[i]==