數(shù)據(jù)結(jié)構(gòu)實驗三哈夫曼樹實驗報告

...wd......wd......wd...題目：哈夫曼編/譯碼器題目要求：寫一個哈夫曼碼的編/譯碼系統(tǒng)，要求能對要傳輸?shù)膱笪倪M展編碼和解碼。構(gòu)造哈夫曼樹時，權(quán)值小的放左子樹，權(quán)值大的放右子樹，編碼時右子樹編碼為1，左子樹編碼為0.概要設(shè)計：數(shù)據(jù)構(gòu)造：typedefstruct{intbit[MAXBIT];intstart;}HCodeType;/*編碼構(gòu)造體*/typedefstruct{intweight;intparent;intlchild;intrchild;charvalue;}HNode;/*結(jié)點構(gòu)造體*/函數(shù)：voidDEMONHuffmanTree(HNodeHuffNode[MAXNODE],intn)作用：構(gòu)造一個哈夫曼樹，并循環(huán)構(gòu)建intmain()作用：運用已經(jīng)構(gòu)建好的哈弗曼樹，進展節(jié)點的處理，到達成功解碼編譯詳細設(shè)計：哈夫曼樹的建設(shè)：voidDEMONHuffmanTree(HNodeHuffNode[MAXNODE],intn){inti=0,j,m1,m2,x1,x2;charx;/*初始化存放哈夫曼樹數(shù)組HuffNode[]中的結(jié)點*/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);//實際值，可根據(jù)情況替換為字母i++;}/*輸入n個葉子結(jié)點的權(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中存放兩個無父結(jié)點且結(jié)點權(quán)值最小的兩個結(jié)點x1=x2=0;//找出所有結(jié)點中權(quán)值最小、無父結(jié)點的兩個結(jié)點，并合并之為一顆二叉樹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è)置找到的兩個子結(jié)點x1、x2的父結(jié)點信息*/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é)點的哈夫曼編碼的保存：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é)點存在*/{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)試分析與心得體會：雖然哈夫曼樹的建設(shè)有書上的參考，但是實際寫整個代碼的時候還是問題重重。首先就是哈弗曼樹忘記了初始的賦值，導(dǎo)致最后出現(xiàn)了問題。這樣的錯誤還是很容易解決，但是之后就出現(xiàn)了WA的情況。在同學(xué)的幫助下，最后發(fā)現(xiàn)是因為在選取節(jié)點的時候，循環(huán)出現(xiàn)了問題，雖然看起來編譯沒有錯，但是邊緣情況就會出現(xiàn)數(shù)據(jù)錯誤，這個還是很令人警醒，而這種思考的不全面的問題，在debug的過程中會耗去大量的時間，這是要注意的。用戶操作說明：輸入表示字符集大小為n〔n

<=

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

輸入串長小于或等于100的目標報文。運行結(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é)點構(gòu)造體*//*構(gòu)造一顆哈夫曼樹*/voidHuffmanTree(HNodeHuffNode[MAXNODE],intn){inti=0,j,m1,m2,x1,x2;charx;/*初始化存放哈夫曼樹數(shù)組HuffNode[]中的結(jié)點*/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);//實際值，可根據(jù)情況替換為字母i++;}/*輸入n個葉子結(jié)點的權(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中存放兩個無父結(jié)點且結(jié)點權(quán)值最小的兩個結(jié)點x1=x2=0;//找出所有結(jié)點中權(quán)值最小、無父結(jié)點的兩個結(jié)點，并合并之為一顆二叉樹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è)置找到的兩個子結(jié)點x1、x2的父結(jié)點信息*/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];/*定義一個結(jié)點構(gòu)造體數(shù)組*/HCodeTypeHuffCode[MAXLEAF],cd;/*定義一個編碼構(gòu)造體數(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é)點存在*/{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*//*保存求出的每個葉結(jié)點的哈夫曼編碼和編碼的起始位*/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()) {