文章目錄

• • （一）設計描述
  • （二）需求分析
  • （三）詳細設計
  • （四）代碼實現與測試
  • （五）個人總結

（一）設計描述

1.題目描述
設計一個利用哈夫曼算法的編碼和譯碼系統，重復地顯示并處理以下項目，直到選擇退出為止。

1) 輸入一串字符，然后統計其中各個字符的個數,即每個字符的權值。 2) 進行初始化操作,并建立哈夫曼樹； 3) 編碼：利用建好的哈夫曼樹生成哈夫曼編碼，并輸出編碼； 4) 譯碼，即輸入每個字符對應的二進制的編碼（0或1），然后輸出對應的字符。 5) 結束操作。

2.設計目的與要求

1）目的：

通過布置具有一定難度的實際程序設計項目，進一步理解和掌握課堂上所學各種基本抽象數據類型的邏輯結構、存儲結構和操作實現算法

2）要求：

1.要求利用C\C++語言來完成系統的設計； 2.突出C語言的函數特征（以多個函數實現每一個子功能）或者C++語言面向對象的編程思想； 3.畫出功能模塊圖； 4.進行簡單界面設計，能夠實現友好的交互； 5.具有清晰的程序流程圖和數據結構的詳細定義； 6.熟練掌握C語言或者C++語言的各種操作。

（二）需求分析

第一步定義Treecount（哈夫曼樹節點的個數），隨后定義兩個結構體，HTnode和HTcode，結構體HTnode儲存數據信息，即（輸入的字符（data），權值（weight），父結點（parent），左孩子（lchild），右孩子（rchild））。 結構體HTnode儲存結果信息，即（輸入的字符（data），BT數組（儲存哈夫曼編碼結果），start（哈夫曼編碼的起始位置），num統計各個字符的出現的個數，即權值，input 輸入的字符）

第二步	定義字符指針P，數組letter[]和數組string[],數組letter用來調用數據 input，data，num；string[]用來輸入字符，同時讓指針P指向string[];由于數組是單個存儲，判斷字符是否相同，用account，num分別統計字母個數以及每個字符的對應次數，即求權值。
第三步	首先定義兩個數組huffnode，array[]分別儲存結點與字符，然后進行哈夫曼樹的初始化，然后找到權值最小的兩個結點，并記錄當前下標。由于是逆序輸出，左右子樹的結點位置為2n-1；得知左右子樹的權值后，讓左右子樹權值進行相加，把值賦給一個新的結點。
第四步	結構體HTcode實例化一個對象begin，并定義兩個數組huffnode，huffcode，調用哈夫曼樹，并記錄編碼的位置為n-1；倒序編碼，并記錄下標。然后回溯頭結點，找到左孩子，賦值為0；找到右孩子賦值為1。然后進行start–，倒著計算編碼，沿著父母結點往上走到結點，保存并求出每個葉子節點的哈夫曼編碼與編碼的起始位。
第五步	定義數組code數組，字符指針q，輸入0和1的數字組合，此時哈夫曼樹對應的葉子結點下標為2n-2；然后進行譯碼，如果讀到0，從根結點的左孩子繼續讀入，直到讀到1，然后繼續讀入，即讀到了一個葉子（字符），即翻譯一個字符成功，然后進行遍歷輸出結果。
第六步	用戶選擇結束系統

（三）詳細設計

1.實現思想

1.首先要構造一棵哈夫曼樹，哈夫曼樹的結點結構包括權值，雙親，左右孩子；假如由n個字符來構造一棵哈夫曼樹，則共有結點2n-1個；在構造前，先初始化，初始化操作是把雙親，左右孩子的下標值都賦為0；然后依次輸入每個結點的權值

2.第二步是通過n-1次循環，每次先找輸入的權值中最小的兩個結點，把這兩個結點的權值相加賦給一個新結點，，并且這個新結點的左孩子是權值最小的結點，右孩子是權值第二小的結點；鑒于上述找到的結點都是雙親為0的結點，為了下次能正確尋找到剩下結點中權值 最小的兩個結點，每次循環要把找的權值最小的兩個結點的雙親賦值不為0（i）.就這樣通過n-1循環下、操作，創建了一棵哈夫曼樹，其中，前n個結點是葉子（輸入的字符結點）后n-1個是度為2的結點

3.編碼的思想是逆序編碼，從葉子結點出發，向上回溯，如果該結點是回溯到上一個結點的左孩子，則在記錄編碼的數組里存“0”，否則存“1”，注意是倒著存；直到遇到根結點（結點雙親為0），每一次循環編碼到根結點，把編碼存在編碼表中，然后開始編碼下一個字符（葉子）

4．譯碼的思想是循環讀入一串哈夫曼序列，讀到“0”從根結點的左孩子繼續讀，讀到“1”從右孩子繼續，如果讀到一個結點的左孩子和右孩子是否都為0，如果是說明已經讀到了一個葉子（字符），翻譯一個字符成功，把該葉子結點代表的字符存在一個存儲翻譯字符的數組中，然后繼續從根結點開始讀，直到讀完這串哈夫曼序列，遇到結束符便退出翻譯循環

3.2 創建哈夫曼樹圖示
已知葉子節點為{10，20，30，40}，以這4個權值構建樹b的過程為：




3.實現流程圖

（四）代碼實現與測試

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<windows.h>#define Treecount 50 //最大葉結點個數 #define MAXSIZE 500 typedef struct node {char data;int weight;int parent;int lchild;int rchild; } HTnode; typedef struct code {char data;int BT[MAXSIZE]; //數組，存放字符的哈夫曼編碼int start; //該編碼在數組中的開始位置char input;int num; } HTcode; void Createhufftree(HTnode HuffNode[],int n,HTcode array[]) { // array[]: 用來存儲字符及其權值int i,j;int minfirst,minsecond;int Lnode,Rnode;for(i=0; i<2*n-1; i++) {HuffNode[i].data=0;HuffNode[i].weight=0;HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;}for(i=0; i<n-1; i++) {minfirst=minsecond=32767; //給最小和次小的樹賦最大值Lnode=Rnode=-1;for(j=0; j<n+i; j++) {if(HuffNode[j].parent==-1 && HuffNode[j].weight<minfirst) { //每次找出剩下的最小權值，并將最小權值賦給次小minfirst=minsecond;Rnode=Lnode;minfirst=HuffNode[j].weight;Lnode=j; //記錄下標} else if(HuffNode[j].parent==-1 && HuffNode[j].weight<minsecond) {minsecond=HuffNode[j].weight;Rnode=j;}}HuffNode[Lnode].parent = n+i;HuffNode[Rnode].parent = n+i;HuffNode[n+i].weight = HuffNode[Lnode].weight+HuffNode[Rnode].weight;HuffNode[n+i].lchild = Lnode;HuffNode[n+i].rchild = Rnode;}for(i=0; i<n; i++) {HuffNode[i].weight=array[i].num; //將字符個數賦給權值HuffNode[i].data=array[i].input;} } void QQ() {printf("請輸入二進制譯碼啟動密碼，密碼錯誤默認結束（即為默認退出）：");long sercret;scanf("%d",&sercret);if(sercret==11011) {Sleep(1000);} else {Sleep(1000);printf("非法操作，結束系統");exit(-1);} } void HuffmanCoding(int n, HTcode array[]) {// array[]: 用來存儲字符及其權值HTnode HuffNode[1000];HTcode HuffCode[Treecount];HTcode begin;FILE *fp;fp=fopen("D:\\a.txt","w");Createhufftree(HuffNode,n,array);int i, j ;int loc,p;char code[30],*q;for(i=0; i<n; i++) {begin.start=n-1; //編碼的開始位置loc=i;p=HuffNode[loc].parent;while(p!=-1) {if(HuffNode[p].lchild==loc)begin.BT[begin.start]=0;elsebegin.BT[begin.start]=1;begin.start--; //倒著計算編碼loc=p; //沿著父母結點往上走到頂點p=HuffNode[loc].parent;}for(j=begin.start+1; j<n; j++)HuffCode[i].BT[j]=begin.BT[j];HuffCode[i].start=begin.start; // 保存求出的每個葉節點的哈夫曼編碼和編碼的起始位printf("\n");}printf("各個字符對應的二進制編碼(1//0//1//0)如下：\n");for(i=0; i<n; ++i) {printf("字符%c的密文:",HuffNode[i].data);for(j=HuffCode[i].start + 1; j<n; j++) //start走過了，加一恢復到開始位，編碼個數小于nprintf("%d", HuffCode[i].BT[j]);printf("\n");}printf("\n");printf("編碼成功，1s后打印哈夫曼編碼：\n");Sleep(1000);for(i=0; i<n; ++i) {for(j=HuffCode[i].start+1; j<n; j++) {fprintf(fp,"%d",HuffCode[i].BT[j]);}for(j=HuffCode[i].start + 1; j<n; j++) {printf("%d", HuffCode[i].BT[j]);}}printf("\n\n");if(i>0) {QQ();}// 譯碼：system("cls");printf(" ----- ∮哈夫曼譯碼系統已經就緒 ∮------- \n");printf("各字符的對應的編碼如下：\n"); for(i=0; i<n; ++i) {printf("字符%c的密文:",HuffNode[i].data);for(j=HuffCode[i].start + 1; j<n; j++) //start走過了，加一恢復到開始位，編碼個數小于nprintf("%d", HuffCode[i].BT[j]);printf("\n");}printf(" --> 請輸入對應的二進制數字： \n");scanf("%s",&code);q = code;loc = 2*n -2; // 哈夫曼樹的根節點下標printf("譯碼成功，正在打印譯碼結果：\n");Sleep(2000);while( *q != NULL) {if( *q== '0') {loc = i =HuffNode[loc].lchild;if(HuffNode[loc].lchild == -1 && HuffNode[loc].rchild == -1) {printf("%c",HuffNode[i].data);fprintf(fp,"%c",HuffNode[i].data);loc = 2*n - 2;}} else if(*q == '1') {loc = i = HuffNode[loc].rchild;if(HuffNode[loc].lchild == -1 && HuffNode[loc].rchild == -1) {fprintf(fp,"%c",HuffNode[i].data);printf("%c",HuffNode[i].data);loc = 2*n-2; // 重新從根遍歷}} else {printf("非法輸入！");}q++;}printf("\n");fclose(fp); } void menu() {system("color F");printf(" ");printf(" \n");printf(" ____〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓____ \n");printf(" || 哈夫曼編碼 || \n");printf(" _________☆界面選擇如下☆_________ \n");printf(" \n");printf(" -> 1 ☆.編碼與譯碼 \n");printf(" -> 2 ☆.結束系統 \n");printf("------------ ☆ ☆----------------- \n");printf(" ∮請手動輸入編號： "); } void Treeaction() {HTcode letter[50];char string[1000], *p;int i, account=0;printf(" ----- ∮哈夫曼編碼系統已經就緒 ∮------- \n");printf(" 》》 請輸入你要編碼的字符串:");scanf("%s",&string);for(i=0; i<50; i++) {letter[i].input=0;letter[i].num=0;}p=string;while(*p!=NULL) {for(i=0; i<=account+1; i++) {if(letter[i].input==NULL) { //letter[i].input存儲所有的字符,用letter[i].num存儲相同的字符的數量letter[i].input=*p;letter[i].num++;account++; // 統計不同字符的個數break;} else if(letter[i].input==*p) {letter[i].num++;break;}}p++;}printf("\n");printf("不同的明文(字符)個數:%d\n",account);printf("\n");printf("輸出輸入的字符的權值\n");for(i=0; i<account; i++) { //輸出不同字符及其所對應的權值printf("當前字符%c的權值為%d",letter[i].input,letter[i].num);printf("\n");}printf("\n");HuffmanCoding(account,letter);} int main() {int n,flaglist=1;char choice;while(flaglist) {menu();scanf("%d",&n);switch(n) {case 1:system("cls");Treeaction();printf("\n");printf("2秒后系統進行返回！\n") ;Sleep(2000);printf("\n");system("cls");printf("已經返回！\n"); printf("請根據個人意愿進行操作！\n");printf("\n");break;case 2:exit(0);}}return 0; }

（五）個人總結

通過這次課程設計，我收獲了很多，認清了課程設計的需求，更認清了自己。談起缺點，自己代碼實現的能力也是破綻百出，對相對較難的題目不能冷靜解決，經常犯一些低級的錯誤。然無獨有偶，自己也有優點，自己思想上能理解難題，并嘗試解決難題，考慮比較周到。
這次的課程設計，難度處于中等地位，但實現起來并不沒有想象中的那么容易。它需要考慮多種因素，必須充分理解題目要求，化大難題為多個小難題，把具體實現步驟細分，認真完成每一步步驟，然后綜合實現題目對應的問題。 時間如白駒過隙，無聲滑過指尖。
學期即將完結，即將大二，不免多生感想。回想一年時光，自己雖說付出努力，然并不能收益眾多。深知自己與他人之差距，然必須成為優秀者，方可日后有一席之地。

我沒有科學家的那樣的天賦異稟，而我卻又有一顆積極向上的心，以“努力不一定成功，但不努力絕不會成功”為座右銘，付諸行動與汗水，不忘初心，厚積薄發。正如詩人王之渙所說:“欲窮千里目，更上一層樓。”要有“燕雀安知鴻鵠之志”的眼光，實現能力之飛躍，思想之迅捷，然自己必須十分努力，才能看起來毫不費力。
風雨過后才會見到彩虹。你盡管去努力，剩下的交給天命。定當不忘學習，砥礪前行。肺腑之言，溢于言表。

總結

以上是生活随笔為你收集整理的Huffman编码的设计与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。