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

...wd......wd......wd...題目：哈夫曼編/譯碼器題目要求：寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)，要求能對(duì)要傳輸?shù)膱?bào)文進(jìn)展編碼和解碼。構(gòu)造哈夫曼樹時(shí)，權(quán)值小的放左子樹，權(quán)值大的放右子樹，編碼時(shí)右子樹編碼為1，左子樹編碼為0.概要設(shè)計(jì)：數(shù)據(jù)構(gòu)造：typedefstruct{intbit[MAXBIT];intstart;}HCodeType;/*編碼構(gòu)造體*/typedefstruct{intweight;intparent;intlchild;intrchild;charvalue;}HNode;/*結(jié)點(diǎn)構(gòu)造體*/函數(shù)：voidDEMONHuffmanTree(HNodeHuffNode[MAXNODE],intn)作用：構(gòu)造一個(gè)哈夫曼樹，并循環(huán)構(gòu)建intmain()作用：運(yùn)用已經(jīng)構(gòu)建好的哈弗曼樹，進(jìn)展節(jié)點(diǎn)的處理，到達(dá)成功解碼編譯詳細(xì)設(shè)計(jì)：哈夫曼樹的建設(shè)：voidDEMONHuffmanTree(HNodeHuffNode[MAXNODE],intn){inti=0,j,m1,m2,x1,x2;charx;/*初始化存放哈夫曼樹數(shù)組HuffNode[]中的結(jié)點(diǎn)*/while(i<n){HuffNode[i].weight=0;//權(quán)值HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1; scanf("%c",&x);scanf("%c",&HuffNode[i].value);//實(shí)際值，可根據(jù)情況替換為字母i++;}/*輸入n個(gè)葉子結(jié)點(diǎn)的權(quán)值*/ scanf("%c",&x); for(i=0;i<n;i++){scanf("%d",&HuffNode[i].weight);}for(i=n;i<2*n-1;i++){HuffNode[i].weight=0;//權(quán)值HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].value=i;}/*循環(huán)構(gòu)造Huffman樹*/for(i=0;i<n-1;i++){m1=m2=MAXQZ;//m1、m2中存放兩個(gè)無父結(jié)點(diǎn)且結(jié)點(diǎn)權(quán)值最小的兩個(gè)結(jié)點(diǎn)x1=x2=0;//找出所有結(jié)點(diǎn)中權(quán)值最小、無父結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)，并合并之為一顆二叉樹for(j=0;j<n+i;j++){if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1){m2=m1;//m1中是最小x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1){m2=HuffNode[j].weight;x2=j;}}/*endfor*//*設(shè)置找到的兩個(gè)子結(jié)點(diǎn)x1、x2的父結(jié)點(diǎn)信息*/HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;}}葉子節(jié)點(diǎn)的哈夫曼編碼的保存：for(j=cd.start+1;j<n;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;主函數(shù)展示：intmain(){HNodeHuffNode[MAXNODE];HCodeTypeHuffCode[MAXLEAF],cd;inti,j,c,p,n,k=0;charwen[100];charz;scanf("%d",&n);HuffmanTree(HuffNode,n);for(i=0;i<n;i++){cd.start=n-1;c=i;p=HuffNode[c].parent;while(p!=-1)/*父結(jié)點(diǎn)存在*/{if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;/*求編碼的低一位*/c=p;p=HuffNode[c].parent;/*設(shè)置下一循環(huán)條件*/}/*endwhile*/for(j=cd.start+1;j<n;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}/*endfor*/z=getchar();z=getchar();for(;z!='\n';z=getchar()) { wen[k++]=z; for(i=0;i<n;i++) { if(z==HuffNode[i].value) { for(j=HuffCode[i].start+1;j<n;j++) printf("%d",HuffCode[i].bit[j]); break; } else; } } printf("\n"); for(i=0;i<k;i++) { printf("%c",wen[i]); } printf("\n");return0;}調(diào)試分析與心得體會(huì)：雖然哈夫曼樹的建設(shè)有書上的參考，但是實(shí)際寫整個(gè)代碼的時(shí)候還是問題重重。首先就是哈弗曼樹忘記了初始的賦值，導(dǎo)致最后出現(xiàn)了問題。這樣的錯(cuò)誤還是很容易解決，但是之后就出現(xiàn)了WA的情況。在同學(xué)的幫助下，最后發(fā)現(xiàn)是因?yàn)樵谶x取節(jié)點(diǎn)的時(shí)候，循環(huán)出現(xiàn)了問題，雖然看起來編譯沒有錯(cuò)，但是邊緣情況就會(huì)出現(xiàn)數(shù)據(jù)錯(cuò)誤，這個(gè)還是很令人警醒，而這種思考的不全面的問題，在debug的過程中會(huì)耗去大量的時(shí)間，這是要注意的。用戶操作說明：輸入表示字符集大小為n〔n

<=

100〕的正整數(shù)，以及n個(gè)字符和n個(gè)權(quán)值〔正整數(shù)，值越大表示該字符出現(xiàn)的概率越大〕；

輸入串長小于或等于100的目標(biāo)報(bào)文。運(yùn)行結(jié)果：附帶自己的算法完成的結(jié)果圖，可以通過PrtSc和圖片編輯器獲得；附錄：#include<stdio.h>#include<stdlib.h>#defineMAXBIT100#defineMAXLEAF30#defineMAXNODEMAXLEAF*2-1#defineMAXQZ10000//權(quán)值typedefstruct{intbit[MAXBIT];intstart;}HCodeType;/*編碼構(gòu)造體*/typedefstruct{intweight;intparent;intlchild;intrchild;charvalue;}HNode;/*結(jié)點(diǎn)構(gòu)造體*//*構(gòu)造一顆哈夫曼樹*/voidHuffmanTree(HNodeHuffNode[MAXNODE],intn){inti=0,j,m1,m2,x1,x2;charx;/*初始化存放哈夫曼樹數(shù)組HuffNode[]中的結(jié)點(diǎn)*/while(i<n){HuffNode[i].weight=0;//權(quán)值HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1; scanf("%c",&x);scanf("%c",&HuffNode[i].value);//實(shí)際值，可根據(jù)情況替換為字母i++;}/*輸入n個(gè)葉子結(jié)點(diǎn)的權(quán)值*/ scanf("%c",&x); i=0;while(i<n){scanf("%d",&HuffNode[i].weight);i++;}for(i=n;i<2*n-1;i++){HuffNode[i].weight=0;//權(quán)值HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].value=i;}/*循環(huán)構(gòu)造Huffman樹*/for(i=0;i<n-1;i++){m1=m2=MAXQZ;//m1、m2中存放兩個(gè)無父結(jié)點(diǎn)且結(jié)點(diǎn)權(quán)值最小的兩個(gè)結(jié)點(diǎn)x1=x2=0;//找出所有結(jié)點(diǎn)中權(quán)值最小、無父結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)，并合并之為一顆二叉樹for(j=0;j<n+i;j++){if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1){m2=m1;//m1中是最小x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1){m2=HuffNode[j].weight;x2=j;}}/*endfor*//*設(shè)置找到的兩個(gè)子結(jié)點(diǎn)x1、x2的父結(jié)點(diǎn)信息*/HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;}}intmain(){HNodeHuffNode[MAXNODE];/*定義一個(gè)結(jié)點(diǎn)構(gòu)造體數(shù)組*/HCodeTypeHuffCode[MAXLEAF],cd;/*定義一個(gè)編碼構(gòu)造體數(shù)組，同時(shí)定義一個(gè)臨時(shí)變量來存放求解編碼時(shí)的信息*/inti,j,c,p,n,k=0;charwen[100];charz;scanf("%d",&n);HuffmanTree(HuffNode,n);for(i=0;i<n;i++){cd.start=n-1;c=i;p=HuffNode[c].parent;while(p!=-1)/*父結(jié)點(diǎn)存在*/{if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;/*求編碼的低一位*/c=p;p=HuffNode[c].parent;/*設(shè)置下一循環(huán)條件*/}/*endwhile*//*保存求出的每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位*/for(j=cd.start+1;j<n;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}/*endfor*/z=getchar();z=getchar();for(;z!='\n';z=getchar()) {