4.3 流程圖 6
1.問題描述
設計乙個利用哈夫曼演算法的編碼和解碼系統，重複地顯示並處理以下專案，直到選擇退出為止。
1) 初始化：鍵盤輸入字符集大小n、n個字元和n個權值，建立哈夫曼樹；
2) 編碼：利用建好的哈夫曼樹生成哈夫曼編碼；
3) 輸出編碼；
4）顯示哈夫曼樹；
5）介面設計的優化；
6) 設字符集及頻度如下表：
字元空格 a b c d e f
頻度 4 9 23 2 17 15
字元 g h i j k
頻度 1 2 3 3 4
2.問題分析
（1）定義乙個變數名為htnode的結構體，用該結構體中的char data、int weight、int parent、int lchild、int rchild分別表示哈夫曼樹中每個結點的權值、權重、雙親結點、左孩子、右孩子，再定義乙個htnode型別的陣列ht[60]存放哈夫曼樹；另外定義乙個變數名為hcode的結構體，採用hcode型別變數的cd[start]~cd[n]存放當前結點的哈夫曼編碼、最後定義乙個hcode型別的陣列hcd[30]的陣列用於存放當前葉子結點ht[i]的哈夫曼編碼。
（2）編寫codeinput(n,ht)函式並在函式中設定乙個for(i=0;n;++)迴圈，首先輸入n個字元，再編寫乙個for(j=0;j（3）編寫createht(ht,n)函式來構造一棵哈夫曼樹，首先用乙個for(i=0;<2*n-1;++)迴圈將所有2n-1個結點的parent、lchild、rchild域均置初值為-1；再用乙個for(i=n;<2*n-1;++)迴圈來構造哈夫曼樹，在該迴圈中首先令lnode和rnode為最小權值的兩個結點位置且其域值均為-1，再用乙個for(k=0;k<=i-1;k++)迴圈在陣列ht[30]中尋找權值最小並且尚未構造二叉樹的結點中查詢，由於只能在尚未構造二叉樹的結點中查詢，因此在for(k=0;k<=i-1;k++)迴圈中加入乙個if(ht[k].parent==-1)語句來判斷結點lnode和rnode是否已經在二叉樹中，如果結點lnode和rnode在二叉樹中，則結點lnode和rnode的parent的值為其雙親結點在陣列ht[30]中的序號就不會為-1了，在查詢到ht[lnode]和ht[rnode]後將他們作為ht[i]的左右子樹，ht[lnode]和ht[rnode]的雙親結點置為ht[i]，且ht[i].weight=ht[lnode].
weight+ht[rnode].weight。如此處理下去，直到所有2n-1個結點處理完畢。
（4）編寫createhcode(ht,hcd,n)函式來求哈夫曼編碼，由於求哈夫曼編碼只需求葉子結點的哈夫曼編碼。對於當前葉子結點ht[i]，首先將對應的哈夫曼編碼hcd[i]的start域值置初值n，找其雙親結點ht[f]，若當前結點是雙親結點的左孩子結點，則在hcd[i]的cd陣列中新增0，若當前結點是雙親的右孩子結點，則在hcd[i]的cd陣列中新增1，將start域減1。再對雙親結點進行同樣的操作，直到無雙親結點為止，最後讓start指向哈夫曼編碼最開始字元。
因此在函式中設定乙個for(i=0;i（5）最後編寫codeoutput(n,hcd)函式，首先利用for(i=0;i （6）顯示哈夫曼樹
（7）介面的優化
3. 演算法設計
3．1抽象資料型別定義
（1）樹的抽象資料型別定義
adt stack
資料關係：若d為空集，則稱為空樹。
若d僅為乙個資料元素，則r為空集，否則r=，h是如下的二元關係：
（1）再d中存在唯一的稱為根的資料元素root，它在關係h下無前驅。
（2）若d-<>空集，則存在乙個劃分d1，d2，···，dm（m>0）。
（3）對應於d-的劃分，h-{}有唯一的乙個劃分h1，h2，···，hm（m>0）。
基本操作：
inittree(&t)
操作結果：構造空樹t。
destroytree(&t)
初始條件：樹t已存在。
操作結果：樹t被銷毀。
cleartree(&t)
初始條件：樹t已存在。
操作結果：將樹t清為空棧。
treeempty(t)
初始條件：樹t已存在。
操作結果：若樹t為空，則返回true，否則false。
treedepth(t)
初始條件:樹t已存在。
操作結果：返回t的深度。
root（t）
初始條件：樹t已存在。
操作結果：返回樹t的根。
3．2程式劃分
本程式包括四個部分：
（1）主程式部分
void main()
（2）哈夫曼樹部分——實現哈夫曼樹的抽象資料型別
（3）求哈夫曼編碼部分——實現求哈夫曼編碼演算法的資料型別
（4）列印哈弗曼樹
4. 詳細設計
4．1資料型別的定義
（1）哈夫曼樹型別
//哈夫曼樹型別
typedef structhtnode;
htnode ht[60];
（2）求哈夫曼編碼型別
typedef structhcode;
hcode hcd[30];
4．2主要的演算法描述
（1）主函式
int main()
{ int n;
資料結構課程設計報告 哈夫曼編碼
廣東工業大學華立學院 課程設計 課程名稱 資料結構 題目名稱 哈夫曼編碼 學生學部 系 資訊與計算機學部 專業班級 09計算機2班 學號學生姓名 指導教師 2010 年 12 月23 日 廣東工業大學華立學院 課程設計 任務書 一 課程設計 程序安排 二 應收集的資料及主要參考文獻 1 嚴蔚敏，吳偉...
資料結構課程設計哈夫曼編碼
淮海工學院電腦科學系 實驗報告書 課程名 資料結構 題目 樹形資料結構實驗 班級 軟體112 學號 姓名樹型資料結構實驗報告要求 1目的與要求 1 熟練掌握huffman樹的建立演算法與程式設計實現 2 熟練掌握huffman編碼演算法的實現與程式設計應用 3 建立較為實用的通訊報文huffman編...
資料結構課程設計哈夫曼編碼
資料結構與演算法 課程設計 2009 2010學年第二學期第20周 指導教師 王老師 班級 電腦科學與技術 3 班 學號 姓名 資料結構與演算法 課程設計 一 前言 1 摘要 2 資料結構與演算法 課程設計任務書 二 實驗目的 三 題目 赫夫曼編碼 解碼器 1 問題描述 2 基本要求 3 測試要求 ...