1、課程設計（數(shù)據(jù)結構）哈夫曼樹和哈夫曼編碼二OO九年六月二十六日課程設計任務書及成績評定課題名稱 表達式求值 哈夫曼樹和哈夫曼編碼I、題目的目的和要求：鞏固和加深對數(shù)據(jù)結構的理解，通過上機實驗、調試程序，加深對課本知識的理解, 最終使學生能夠熟練應用數(shù)據(jù)結構的知識寫程序。（1）通過本課程的學習，能熟練掌握兒種基本數(shù)據(jù)結構的基本操作。（2）能針對給定題LI,選擇相應的數(shù)據(jù)結構，分析并設訃算法，進而給出問題的 正確求解過程并編寫代碼實現(xiàn)。II、設計進度及完成情況日期內容6.8-60選取參考書，查閱有關文獻資料，完成資料搜集和系統(tǒng)分析匸 作。65和6.19創(chuàng)建相關數(shù)據(jù)結構,錄入源程序。6.22-6.2

2、5調試程序并記錄調試中的問題，初步完成課程設計報告。6.26上交課程設計報告并進行課程設計答辯，要求每個同學針對自 己的設計回答指導教師3-4個問題。考核結束后將課程設計報告和源程序的電子版交班長統(tǒng)一刻 光盤上交。川、主要參考文獻及資料1嚴蔚敬數(shù)據(jù)結構（C語言版）清華大學出版社19992 嚴蔚敬數(shù)據(jù)結構題集（C語言版）清華大學出版社19993 譚浩強C語言程序設計清華大學出版社4 與所用編程環(huán)境相配套的C語言或C+相關的資料IV、成績評定:設計成績： （教師填寫）扌旨導老師： （簽字）二oo九年六月二十六日第一章概述1第二章系統(tǒng)分析2第三章概要設計3第四章 詳細設計及實現(xiàn)代碼8第五章 調試過程

3、中的問題及系統(tǒng)測試情況1213第六章結束語13 參考文獻第一章概述課程設計是實踐性教學中的一個重要環(huán)節(jié)，它以某一課程為基礎，可以涉及和課程 相關的各個方面，是一門獨立于課程之外的特殊課程。課程設計是讓同學們對所學的課 程更全面的學習和應用，理解和掌握課程的相關知識。數(shù)據(jù)結構是一門重要的專業(yè) 基礎課，是計算機理論和應用的核心基礎課程。數(shù)據(jù)結構課程設計，要求學生在數(shù)據(jù)結構的邏輯特性和物理表示、數(shù)據(jù)結構的選擇 和應用、算法的設計及其實現(xiàn)等方面，加深對課程基本內容的理解。同時，在程序設計 方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。在這次的課程設訃中我選擇的題LI是表達式求值和哈

4、夫曼樹及哈夫曼編碼。這里我 們介紹一種簡單直觀、廣為使用的算法，通常稱為“算符優(yōu)先法”。哈夫曼樹乂稱最優(yōu) 樹，是一類帶權路徑長度最短的樹，有著廣泛的應用。功能：表達式求值以棧為存儲結構，實現(xiàn)輸入的表達式的求值；哈夫曼樹和哈夫曼編碼是實現(xiàn)最優(yōu)二義樹的構造，并能通過最優(yōu)二義樹進行編 碼，應用到電文中，并以此來譯碼。利用鍵盤，輸入相應的數(shù)值，通過程序實現(xiàn)表達式的求值；再利用鍵盤，輸入各個 頂點，通過程序構造最優(yōu)二義樹以及為此編碼。第二章系統(tǒng)分析一、表達式求值根據(jù)一元多項式相加的運算規(guī)則：對于兩個一元多項式中所有指數(shù)相同的項，對應 系數(shù)相加，若其和不為零，則構成“和多項式”中的一項；對于兩個一元多項式

5、所 有指數(shù)不相同的項，則分別復抄到“和多項式”中去。在此，安裝上述抽象數(shù)據(jù)類型Polynomial中基本操作的定義，“和多項式”鏈表中 的結點無需另生成，而應該從兩個多項式的鏈表中摘取。其運算規(guī)則如下：假設指 著qa和qb分別指向多項式A和多項式B中當前進行比較的某個結點，則比較兩個 結點中的指數(shù)項，有下列3種情況：指針qa所指結點的指數(shù)值V指針qb所指結點 的指數(shù)值，則應摘取qa指針所指結點插入到“和多項式”鏈表中去；指針qa所 指結點的指數(shù)值指針qb所指結點的指數(shù)值，則應摘取指針qb所指結點插入到“和 多項式”鏈表中去；指針qa所指結點的指數(shù)值二指針qb所指結點的指數(shù)值，則將 兩個結點中的

6、系數(shù)相加，若和數(shù)不為零，則修改qa所指結點的系數(shù)值，同時釋放qb 所指結點；反之，從多項式A的鏈表中刪除相應結點，并釋放指針qa和qb所指結 點。二、哈夫曼樹和哈夫曼編碼建立哈夫曼樹的算法思想是:1）根據(jù)給定的兒個權值wi, W2,Wn）構成n顆二叉樹的集合F=T1, T2, Tn,其中每顆二叉樹Ti中只有一個帶權為W的根結點，其左右子樹均空。2）在F中選取兩棵根結點的權值最小作為左右子樹構造一棵新的二義樹，且置新的二 義樹的根結點的權值為其左、右子樹上根結點的權值之和。3）在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。4）重復（2）和（3）,直到F只含一棵樹為止。這棵樹便是哈夫曼樹。第三

7、章概要設計I. 以下算法描述了這個求值過程：int cmp(term a, term b);依a的指數(shù)值v(或=)(或)b的指數(shù)值，分別返回-1、0、+1void CreatPolyn(poIynomail&p,int m)輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表pInitList(p); h =GetHead(p);e.coef =0.0; e.expn = -1; SetCurElem(h,e); 設置頭結點的數(shù)據(jù)元素for (i=l; i<=m ; +i) 依次輸入m個非零項scanf (e.coef, e.expn);if (!LocateElem(P,e,q(

8、*cmp)() 當前鏈表中不存在該指數(shù)項 if(MakeNode(s,e) InsFirst(q,s); 生成結點并插入鏈表)/CreatPolynvoid AddPolyn(polynomai &Pa. polynomai &Pb)多項式加法：Pa；Pa+Pb,利用兩個多項式的結點構成“和多項式”。ha =GetHead(Pa); hb =GetHead(Pb);/ha 和 hb 分別指向 Pa 和 Pb 中當前結點 while(qa&&qb)/qa 和 qb 均非空a=GetCurElem(qa); b=GetCurElem(qb);/a 和 b 為兩表中

9、'勺前比較元素 switch(*cmp(a.b) case-l:/多項式PA中當前結點的指數(shù)值小ha=qa; qa=NextPos(pa<qa);break;case 0: 兩者的指數(shù)值相等sum=a.coef+b.coef;if(sum!=0.0)修改多項式PA中當前結點的系數(shù)值SetCurElem(qa,sum);ha=qa;else/刪除多項式PA中當前結點DelFirst(ha.qa); FreeNode(qa);)DelFirst(hb.qb); FreeNode(qb); qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);break;case 1

10、: 多項式PB中當前結點的指數(shù)值小DelFirst(hb.qb); InsFirst(ha,qb);qb=Nextpos(Pb,hb); ha=NextPos(Pa,ha);break;(/switch/whileif(!ListEmpty(Pb) Append(Pa,qb); 鏈接 pb 中剩余結點FreeNode(Pb): 釋放Pb的頭結點)/AddPolynII. 哈夫曼樹及哈夫曼編碼ADT BinaryTree數(shù)據(jù)對象:D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關系：R：若D二，則R二，稱BinaryTree為空二叉樹；若DH4 則R二H , H是如下二元關系：(1) 在D中存在惟一的稱為

11、根的數(shù)據(jù)元素root,它在關系H下無前驅；(2) 若 D- root H，則存在 D- root = DI, Dr,且 DlQDr 二；(3) 若D1H®,則D1中存在惟一的元素XI, <root,Xl>eH,且存在D1上的關系Hl e H;若DrH，則Dr中存在惟一的元素Xr, <root, Xr> G H,且存在Dr上的關系 Hr W H;H= <root,X 1 >,<root,Xr>,H 1 ,Hr;(4) (DI,Hl)是一顆符合本定義的二義樹，稱為根的左子樹,(Dr,Hr)是一顆符合本 定義的二叉樹，稱為根的右子樹?；静僮?/p>

12、P：Initqueue(&q)；操作結果：構造空二義樹T。Destroyqueue(&q):初始條件：二義樹T已存在。操作結果：銷毀二義樹T。CreateB訂ree(&T, definition)；初始條件：definition給出二義樹T的定義。操作結果：按definition構造_.義樹T。ClearBiTree(&T)；初始條件：二義樹T已存在。操作結果:將二義樹T清為空樹。BiTreeEmpty(T)；初始條件：二義樹T已存在。操作結果：若T為空二義樹，則返回TRUE,否則FALSEoBiTreeDepth(T)；初始條件：二義樹T已存在。操作結果：返回

13、T的深度。Root(T)初始條件：二義樹T已存在。操作結果：返回T的根。Value (T, e)初始條件：二義樹T存在，e是T中某個結點。操作結果：返回e的值。Assign(T，&e, value):初始條件：二義樹T存在，e是T中某個結點。操作結果：結點e賦值為valueoParent (T, e)；初始條件：二叉樹T存在，e是T中某個結點。操作結果:若e是T的非根結點，則返回它的雙親，否則返回“空”。LeftChild (T, e)；初始條件：二義樹T存在，e是T中某個結點。操作結果:返回e的左孩子。若e無左孩子，則返回“空”。RightChild (T, e)；初始條件：二義樹T

14、存在，e是T中某個結點。操作結果:返回e的右孩子。若e無右孩子，則返回“空”；LeftSibling (T, e)；初始條件：二義樹T存在，e是T中某個結點。操作結果:返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回“空”。RightSibling (T, e)；初始條件：二義樹T存在，e是T中某個結點。操作結果:返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回“空”。InsertChild (T, p, LR, c)；初始條件：二義樹T存在，p指向T中某個結點，LR為0或1,非空二叉樹c與T 不相交且右子樹為空。操作結果:根據(jù)LR為0或為1,插入c為T中p所指結點的左或右子樹。P所指結點

15、 的原有左或右子樹則成為c的右子樹。DeleteChild (T, p, LR)；初始條件：二義樹T存在，p指向T中某個結點，LR為0或1。操作結果：根據(jù)LR為0或為1,刪除T中p所指結點的左或右子樹。PreOrderTraverse(T, Visit()；初始條件：二義樹T存在，Visit是對結點操作的應用函數(shù)。操作結果：先序遍歷T,對每個結點調用函數(shù)V isit-次且僅一次。一旦visit () 失敗，則操作失敗。InOrderTraverse(T, Visit()；初始條件：二義樹T存在，Visit是對結點操作的應用函數(shù)。操作結果：中序遍歷T,對每個結點調用函數(shù)Visit 次且僅一次。一

16、旦visit () 失敗，則操作失敗。PostOrderTraverse (T, Visit ()；初始條件：二義樹T存在，Visit是對結點操作的應用函數(shù)。操作結果:后序遍歷T,對每個結點調用函數(shù)V isit-次且僅一次。一旦visit () 失敗，則操作失敗。LevelOrderTraverse(T, Visit()；初始條件：二義樹T存在，Visit是對結點操作的應用函數(shù)。操作結果:層序遍歷T,對每個結點調用函數(shù)Visit 次且僅一次。一旦visit () 失敗，則操作失敗。ADT BinaryTree求哈夫曼編碼的算法如下：Void HuffmanCoding(HuffmanTree&

17、amp;HT,HuffmanCode&HC,int *w,int n)/w存放n個字符的權值(均>0),構造哈夫曼樹HT,并求n個字符的哈夫曼編碼HC。if(n<=l) return;m=2*n-l;HT=(HuffmanTree)malloc(m+1 )*sizeof(HTNode);/0 號單元未用。for(p=HT+l ,i=l ;iv二n,+i,+p,+w) *p= *w,0,0,0;for(;i<=m,+i,+p,) *p=0,0,0,0;for(i=n+l ;i<=m,+i,)/ 哈夫曼樹在HTl.i-l選擇parent為0且weight最小的兩個結

18、點，其序號分別為si和s2。Select(HT,i-1 ,sl ,s2);HTsl.parent=I; HTs2.parent=i;HTi.lchild=s 1; HTi .rchild=s2;HTi.weight= HTsl.wei2ht+ HTs2. weight;從葉子到根逆向求每個字符的哈夫曼編碼。HC=(HaffmanCode)malloc(n+1 )*sizeof(char *);分配 n 個字符編碼的頭指針向量 cd=(char *)malloc(n*sizeof(char*)#分配求編碼的匸作空間cdn-lJ0”；編碼結束符。for(i=l;i<=n;+i)逐個字符求哈夫

19、曼編碼start=n-1;編碼結束符位置for(c=i,f=HTi.parent;f!=0;c=fJ=HTf.parent)/ 從葉子到根逆向求編碼 if(HTf.lchild=c) cd start二 ”0”；eles cdstart=nP,;HCi=(char »)malloc(n-start)*sizeof(char);/為第 i 個字符編碼分配空間 strcpy(HCi,&cdstart);從 cd 復制編碼(串)到 HC>free(cd);釋放工作空間)/HuffmanCod i ng第四章 詳細設計及實現(xiàn)代碼表達式求值的源代碼：#include Hstdio

20、.hHinclude "stdlib.h"typedef struct polynodeint cofe;int exp;struct polynode *next;JPNode;PNode *Creat_Linkst(int n)PNode *head,*p,*s;int i;head=(PNode*)malloc(sizeof(PNode);head->next=NULL;p=head;printf(Henter cofe,exp:nn);for(i=l;i<=n;+i)s=(PNode *)nialloc(sizeof(PNode); scanf(n%d5

21、%d,&s->cofe,&s->exp); s->next=NULL;p->next=s;p=s;return(head);void polyADD(PNode *pa,PNode *pb)PNode *pre,*qa,*qb,*q;int sum;pre=pa;qa=pa->next;qb=pb->next;while(qa&&qb)if(qa->exp=qb->exp) sum=qa->cofe+qb->cofe;if(sum) qa->cofe=sum;pre=qa; elsepre->

22、;next=qa->next;free(qa); qa=pre->next;q=qb;qb=qb->next;free(q);)else) if(qa->exp>qb->exp) pre=qa;qa=qa->next;) elsepre->next=qb;pre=qb;qb=qb->next;pre->next=qa;)if(qb)pre->next=qb;free(pb);)void print_Linkst(PNode *H)PNode *p;p=H->next;while(p)printf(H%dxA%d+,p-&g

23、t;cofe,p->exp);p=p->next;) if(p->exp)printf(H%dxA%dn,p->cofe,p->exp);else printf(H%dnM,p->cofe);)main()PNode *HA,*HB;int la,lb;printf(Henter la,lb:");scanf("%d,%d",&la,&lb);printf(Hncreat HAnH);H A=Creat_Li nkst (la);printf("A(x)=");print_Linkst(HA)

24、;printf("ncreat HBn");HB=Creat_Linkst(lb);printf("B(x)=H);print_Linkst(HB);polyADD(HA,HB); printf(HnA(x)=M);)哈夫曼樹和哈夫曼編碼的程序：#define maxvalue 10000#define maxnodenumber 100#define maxbit 10typedef structint weight;int parentjchildjchild:(htnode;typedef stiuct int bitmaxbit; int start;(h

25、codetype;typedef htnode *huffmantree;htnode htmaxnodenumber; hcodetype cd maxnodenuniber;void crthuffmantree(int n)int iJ,ml,m25kLk2;for(i=0;i<2*n-l ;i+)hti.weight=O;hti.parent=l;hti.lchild=l;hti.rchild=l;printf(Hshuruyizuweight:nH);for(i=0;i<n;i+)scanfC%d",&hti .weight);printf(Hi wei

26、ght parent lchild rchildnM);for(i=0;i<n-l ;i+)ml=niax value;m2=maxvalue;kl=0;k2=0;for(j=0;j<n+i;j+)if(htj.parent=-l &&htj.weight<m 1) m2=ml;k2=kl;ni 1 =ht j .weight ;kl=j;if(htj.parent=-1&&htj.weight<m2) m2=htj. weight;k2=j;htkl.parent=n+i;htk2.parent=n+i; htn+i.weight=ht

27、kl.weight+htk2.weight;htn+i.lchild=kl;htn+i.rchild=k2;>for(i=0;i<2*n-l ;i+)%5dn",i,hti. weight,hti.parent,hti.printf(” d%5d%5d%5dlchild,hti.rchild);printf(“n");/*crthuffmantree*/void gethuffmancode(htnode ht,int n)int i,j,c,p;printf(Hcode:%dnn,n);for(i=0;i<n;i+)c二i;j二maxbit;doj-;p=htc. parent;if(htp .lchild=c)cdi.bitj=O;elsecdi.bit|j=l；c 二 p;)while(p!=l);cdi.start=j+l;/*根也置1,所以編碼從下一位置始*/)for(i=0;i<n;i+)printf("%d:",hti