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

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

主程序首先隨機(jī)輸入一篇英文文章，再統(tǒng)計(jì)各字母?jìng)€(gè)數(shù)，再調(diào)用HuffmanCoding(HT,HC,w,再函數(shù)，此函數(shù)又會(huì)調(diào)用voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)函數(shù)，而此函數(shù)又會(huì)調(diào)用intmin(HuffmanTreeHT,inti)函數(shù)，構(gòu)造完成后便調(diào)用PrintHT(HT,n)函數(shù)輸出赫夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)。Intmain()主函數(shù)調(diào)用HuffmanCoding(HT,HC,w,n)調(diào)用voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)調(diào)用”intmin(HuffmanTreeHT,inti)PrintHT(HT,n)點(diǎn)PrintHT(HT,n)點(diǎn)調(diào)用輸入界面:請(qǐng)隨札輸入英文文命

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