哈夫曼編碼實驗報告

北京郵電大學信息與通信工程學院第6頁北京郵電大學電信工程學院第1頁數(shù)據(jù)結構實驗報告實驗名稱：實驗三——哈夫曼編碼學生姓名：牛佳寧班級：2010211107班內序號：27學號：10210213日期：2011年12月10日1．實驗要求利用二叉樹結構實現(xiàn)赫夫曼編/解碼器。1、讀入一串字符，統(tǒng)計字符個數(shù)及權值。2、建立哈夫曼樹。3、根據(jù)哈夫曼樹建立哈夫曼表。4、將字符串進行編碼。5、輸入一串01數(shù)，進行解碼。2.程序分析2.1存儲結構哈夫曼樹為正則二叉樹，有n個葉子的哈夫曼樹共有2n-1個結點，可以用一個大小為2n-1的數(shù)組來儲存哈夫曼樹的各個結點，如圖weightLchildRChildparent2-1-1-13-1-1-16-1-1-19-1-1-1對應的編碼表可用如圖所示結構datacodeZ100C101B112.2關鍵算法分析一、創(chuàng)建哈夫曼樹1、根據(jù)權值初始化哈夫曼樹for(inti=0;i<n;i++) { HTree[i].weight=a[i]; HTree[i].LChild=-1; HTree[i].RChild=-1; HTree[i].parent=-1；}2、開始建立哈夫曼樹，intx,y; for(inti=n;i<2*n-1;;i++) { selectMin(x,y,o,i);//從1到i選擇兩個權值最小的 HTree[x].parent=HTree[y].parent=i; HTree[i].weight=HTree[x].weight+HTree[y].weight; HTree[i].LChild=x; HTree[i].parent=-1; }二、建立哈夫曼編碼表voidHuffman::CreateCodeTable(charb[],intn){ HCodeTable=newHCode[n]; for(inti=0;i<n;i++) { HCodeTable[i].data=b[i];//生成編碼表 intchild=i; intparent=HTree[i].parent; intk=0; while(parent!=-1) { if(child==HTree[parent].LChild) HCodeTable[i].code[k]='0';//左孩子標‘0’ else HCodeTable[i].code[k]='1';//右孩子標‘1’ k++; child=parent; parent=HTree[child].parent; } HCodeTable[i].code[k]='\0'; char*b=newchar[k];//將編碼字符逆置,再初始化一個數(shù)組倒著儲存編碼數(shù)組，再將該數(shù)組重新賦給編碼數(shù)組 for(intj=0;j<k;j++) { b[j]=HCodeTable[i].code[k-1-j]; } for(intjj=0;jj<k;jj++) { HCodeTable[i].code[jj]=b[jj]; } }}三、編碼函數(shù)：根據(jù)編碼表進行編碼，從編碼表中第一個開始遍歷，若找到要編碼的字符則輸出編碼，并進行下一個字符的查找voidHuffman::Encode(char*s,intn){ while(*s!='\0') { for(inti=0;i<n;i++) { if(*s==HCodeTable[i].data) { cout<<HCodeTable[i].code; s++; } } } cout<<endl;}四、解碼：利用哈夫曼樹進行解碼，編碼串左到右依次逐位判斷，從根結點開始根據(jù)每一位是0還是1，確定是左分支還是右分支，直到到葉子節(jié)點為止，從編碼表中找到對應字符并輸出voidHuffman::Decode(char*s,char*d,intn)//s為編碼串，{ while(*s!='\0') { intparent=2*n-1-1;//根節(jié)點在HTree中的下標； while(HTree[parent].LChild!=-1) { if(*s=='0') parent=HTree[parent].LChild; else parent=HTree[parent].RChild; s++; } *d=HCodeTable[parent].data; cout<<*d; d++; } cout<<endl;}五、利用STL中的排序函數(shù)選擇兩個權值最小結點intHuffman::SelectMin(intx,y,o,i)//選擇兩個最小的{ list<int>ilist; for(intj=0;j<i;j++) { if(HTree[j].parent=-1) ilist.push_back(HTree[j].weight); } ilist.sort(); list<int>::iteratorit=ilist.begin(); x=*it; y=*++it; returnx,y;}六、建立數(shù)組不重復的儲存字符并且統(tǒng)計出現(xiàn)次數(shù)即權值：利用循環(huán)鏈表來實現(xiàn)，每插入一個結點之前先定義節(jié)點指針指向第一個結點，邊向后移動邊比較儲存的字符是否相同，若相同則使該節(jié)點權值加一，不同則將該節(jié)點加入到循環(huán)鏈表中，直到遍歷整個字符串，代碼如下voidLinklist::Construct(chars[])//建立循環(huán)鏈表存放字符串{ rear=newNode; rear->next=rear; for(unsignedinti=0;i<strlen(s);i++) { if(rear->next==rear)//放入第一個字符 { Node*p=newNode; p->data=s[0]; p->weight=1; p->next=rear->next; rear->next=p; rear=p; } else { Node*q=rear->next->next;//q指向第一個字符 while(q!=rear->next)//遍歷鏈表看q存儲的字符是否有與要插入的字符相同的 { if(q->data==s[i]) { q->weight++;//若有則權值加一 break; } else q=q->next; } if(q==rear->next)//若鏈表中無與要插入字符相同的字符，則將該字符使用頭插法插入 { Node*r=newNode; r->data=s[i]; r->weight=1; r->next=rear->next; rear->next=r; rear=r; } } }}qq時間復雜度計算：select函數(shù)的時間復雜度為O(n),則建立哈夫曼樹的時間按復雜度為Ｏ（ｎ＾２）建立哈夫曼編碼表的時間復雜度為O（n）。編碼的函數(shù)時間復雜度為O（n）。解碼函數(shù)的時間復雜度為O（n^2）。程序運行結果運行環(huán)境為vc6.0編碼前的長度為32編碼后的長度為22，壓縮比為22/32=68.75%4.總結在調試過程中遇到過很多困難，比如在寫選擇權重最小的兩個節(jié)點的編碼時，就出現(xiàn)了選擇出最大的輸出兩遍等問題你，邏輯上有些麻煩，但是使用STL后，程序變得簡單多了，而且不用考慮那些過于細致的問題。吸取上次八皇后問題編碼時使用遞歸函數(shù)容易出現(xiàn)停止遞歸的條件不明顯等問題，這次選擇了用循環(huán)來實現(xiàn)遞歸，雖然代碼變長，但是思維變得清晰起來，也不太容易出