數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告2

!-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：___實(shí)驗(yàn)三樹(shù)__題目2_________________謝謝閱讀學(xué)生姓名：_____________________感謝閱讀班 級(jí)：__________________________謝謝閱讀班內(nèi)序號(hào)：________________學(xué) 號(hào)：_____________________日 期：__________________________精品文檔放心下載!-1．實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康模赫莆斩鏄?shù)基本操作的實(shí)現(xiàn)方法了解哈夫曼樹(shù)的思想和相關(guān)概念培養(yǎng)使用二叉樹(shù)解決實(shí)際問(wèn)題的能力實(shí)驗(yàn)內(nèi)容：利用二叉樹(shù)結(jié)構(gòu)實(shí)現(xiàn)赫夫曼編/解碼器?；疽笕缦拢?、初始化(Init)：能夠?qū)斎氲娜我忾L(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的謝謝閱讀頻度，并建立赫夫曼樹(shù)2、建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹(shù)進(jìn)行編碼，并將每個(gè)字符精品文檔放心下載的編碼輸出。3、編碼(Encoding)：根據(jù)編碼表對(duì)輸入的字符串進(jìn)行編碼，并將編碼后的字符串精品文檔放心下載輸出。4、譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹(shù)對(duì)編碼后的字符串進(jìn)行譯碼，并輸精品文檔放心下載出譯碼結(jié)果。5、打印(Print)：以直觀的方式打印赫夫曼樹(shù)（選作）謝謝閱讀6、計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。感謝閱讀測(cè)試數(shù)據(jù)：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.謝謝閱讀提示：1、用戶界面可以設(shè)計(jì)為“菜單”方式：能夠進(jìn)行交互。2、根據(jù)輸入的字符串中每個(gè)字符出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對(duì)沒(méi)有出現(xiàn)的字符一律不用編碼。精品文檔放心下載程序分析2.1存儲(chǔ)結(jié)構(gòu)二叉樹(shù)： rootlchild parent rchild!-靜態(tài)三叉鏈表存儲(chǔ):weight LChild RChild parent謝謝閱讀0123…哈夫曼編碼的存儲(chǔ)結(jié)構(gòu)0 10 10 12.2程序流程(或程序結(jié)構(gòu)、或類關(guān)系圖等表明程序構(gòu)成的內(nèi)容，一般為流程圖謝謝閱讀等)2.3關(guān)鍵算法分析1.建立了一個(gè)類classHuffman{private:HNode*HTree;HCode*HCodeTable;public:voidSelectMin(int&x,int&y,inta,intb);//權(quán)值最小的兩個(gè)字符感謝閱讀voidCreateHTree(intrealcounts[],intn); //創(chuàng)建哈夫曼樹(shù)精品文檔放心下載!-voidCreateCodeTable(charcounts[],intn); //創(chuàng)建哈夫曼編碼表謝謝閱讀voidReverse(charc[]); //逆序感謝閱讀voidEncode(char*s,char*d); //編碼精品文檔放心下載voidDecode(char*s,char*d,int n); //解碼精品文檔放心下載~Huffman(){delete[]HTree;delete[]HCodeTable;} //析構(gòu)函數(shù)謝謝閱讀};2.建立哈夫曼樹(shù)voidHuffman::CreateHTree(intrealcounts[],intn)精品文檔放心下載{HTree=newHNode[2*n-1]; //根據(jù)權(quán)重?cái)?shù)組初始化哈夫曼樹(shù)謝謝閱讀for(inti=0;i<n;i++){HTree[i].weight=realcounts[i];精品文檔放心下載HTree[i].LChild=-1;HTree[i].RChild=-1;HTree[i].parent=-1;}intx,y;if(n>1)//因?yàn)槿绻挥幸环N字符就直接它自個(gè)兒了感謝閱讀{for(i=n;i<2*n-1;i++) //建立哈夫曼樹(shù)謝謝閱讀!-{SelectMin(x,y,0,i); //找出最小權(quán)重的兩個(gè)字符感謝閱讀HTree[x].parent=HTree[y].parent=i;謝謝閱讀HTree[i].weight=HTree[x].weight+HTree[y].weight;謝謝閱讀HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;}}}時(shí)間復(fù)雜度：n3.選取權(quán)值最小的兩個(gè)值voidHuffman::SelectMin(int&x,int&y,inta,intb)精品文檔放心下載{intj,min1,min2;min1=min2=-1;for(j=a;j<b;j++)if(HTree[j].parent==-1){if(HTree[j].weight<min1||min2==-1)謝謝閱讀{if(min1!=-1)!-{min2=min1;y=x;}min1=HTree[j].weight;x=j;}elseif(HTree[j].weight<min2||min2==-1)謝謝閱讀{min2=HTree[j].weight;y=j;}}}時(shí)間復(fù)雜度：n4.哈夫曼編碼表voidHuffman::CreateCodeTable(charcounts[],intn)精品文檔放心下載{inti;HCodeTable=newHCode[n];感謝閱讀if(n<2){!-HCodeTable[0].data=counts[0];謝謝閱讀HCodeTable[0].code[0]='0';謝謝閱讀HCodeTable[0].code[1]='\0';精品文檔放心下載cout<<"字符及其編碼:"<<counts[0]<<"0 "<<endl;謝謝閱讀}else{for(i=0;i<n;i++){HCodeTable[i].data=counts[i];謝謝閱讀cout<<"字符及其編碼:"<<counts[i]<<" ";謝謝閱讀intchild=i;intparent=HTree[i].parent;謝謝閱讀intk=0;while(parent!=-1){if(child==HTree[parent].LChild)感謝閱讀HCodeTable[i].code[k]='0';感謝閱讀elseHCodeTable[i].code[k]='1';謝謝閱讀k++;!-child=parent;parent=HTree[child].parent;精品文檔放心下載}HCodeTable[i].code[k]='\0';謝謝閱讀Reverse(HCodeTable[i].code);謝謝閱讀k=0;while(HCodeTable[i].code[k]!='\0')精品文檔放心下載{cout<<HCodeTable[i].code[k];謝謝閱讀k++;}cout<<endl;}}}時(shí)間復(fù)雜度：n5.逆序voidHuffman::Reverse(charc[])精品文檔放心下載{inti=0,j=0;inttemp;!-while(c[j+1]!='\0'){j++;}while(i<j){temp=c[i];c[i]=c[j];c[j]=temp;i++;j--;}}時(shí)間復(fù)雜度：n6。對(duì)輸入的字符串進(jìn)行編碼voidHuffman::Encode(char*s,char*d)//編碼精品文檔放心下載{cout<<"哈夫曼編碼為：";floatsum=0; //統(tǒng)計(jì)字節(jié)數(shù)intn=0;while(*s!='\0'){ int i=0;!-while(HCodeTable[i].data!=*s)精品文檔放心下載{i++;}for(intj=0;HCodeTable[i].code[j]!='\0';j++)感謝閱讀{*d=HCodeTable[i].code[j];cout<<*d;d++;sum+=1;}s++;n++;}*d='\0';cout<<endl;cout<<"編碼前字符串所占比特位為："<<8*n<<endl;謝謝閱讀cout<<"編碼后的字符串所占比特位為"<<sum<<endl;感謝閱讀cout<<"壓縮比為："<<sum/(8*n)<<endl;感謝閱讀cout<<endl;}7。對(duì)已編譯好的字符串進(jìn)行解碼!-voidHuffman::Decode(char*d,char*s,intn) //解碼精品文檔放心下載{cout<<"解碼為：";if(n<2){while(*d!='\0'){cout<<HCodeTable[0].data;d++;}精品文檔放心下載}while(*d!='\0'){intparent=2*n-1-1;//根節(jié)點(diǎn)在HTree中的下標(biāo)感謝閱讀while(HTree[parent].LChild!=-1)感謝閱讀{if(*d=='0')parent=HTree[parent].LChild;謝謝閱讀elseparent=HTree[parent].RChild;感謝閱讀d++;}*s=HCodeTable[parent].data;精品文檔放心下載cout<<*s;s++;!-}cout<<endl;}8。主函數(shù)，包含了交互的操作。voidmain(){stringbuffer;char*d;char*s;inti,q,j=0,n=0,realcounts[N];精品文檔放心下載charcounts[N],c[N];d=&c[0];intcount[127];for(i=0;i<127;i++){count[i]=0;}cout<<"請(qǐng)輸入初始化的字符串(英文):\n"<<endl;感謝閱讀getline(cin,buffer);s=&buffer[0];while(buffer[j]!='\0')!-{count[buffer[j]]++;//不同字符的個(gè)數(shù)感謝閱讀j++;}j=0;for(i=0;i<127;i++){if(count[i]!=0){realcounts[j]=count[i];//提取出真正存在的字符的權(quán)值謝謝閱讀counts[j]=i;//j++;n++;}}Huffmanh;menu:cout<<"1-察看編譯后的文字(包含壓縮比)"<<endl;謝謝閱讀cout<<"2-察看編譯前的內(nèi)容"<<endl;do!-{cout<<"請(qǐng)輸入想要的操作的編號(hào)"<<endl;感謝閱讀cin>>q;switch(q){case1:{h.CreateHTree(realcounts,n);精品文檔放心下載h.CreateCodeTable(counts,n);精品文檔放心下載h.Encode(s,d);b