數(shù)據(jù)結構課程設計實驗報告(赫夫曼編碼)《精選文檔》

1、+數(shù)據(jù)結構課程設計 題目：赫夫曼編碼院、 系：計算機科學與工程學院學科專業(yè)：計算機科學與技術 學 生： 高經(jīng)典 學 號： 090602103 指導教師： 梁晨 2010年12月22日目 錄1課程設計的題目-02課程設計的目的設計要解決的問題-13概要設計函數(shù)劃分、總體設計-14詳細設計算法、流程圖、程序-25調(diào)試結果- -326課程設計總結- -337心得體會-34二課程設計的目的穩(wěn)固構造赫夫曼樹的算法。設計實驗用程序實現(xiàn)赫夫曼樹的構造。熟悉用先序、中序或后序的訪問方法得到個葉子結點的赫夫曼編碼。三概要設計函數(shù)劃分、總體設計總體設計輸入一個字符串用結構體鏈表存儲字符串中出現(xiàn)的不同字符及其出現(xiàn)的

2、次數(shù)。定義赫夫曼數(shù)的結點結構體，把不同的字符及其在字符串中出現(xiàn)的次數(shù)作為葉子結點的元素及其權值，統(tǒng)計葉子結點的個數(shù)n，開辟可以存儲2*n個結點的順序表，來赫夫曼樹的各個結點，然后按照一定的規(guī)那么構造赫夫曼樹。開辟一個可以存儲葉子結點元素及指向存儲其赫夫曼編碼鏈表的指針的順序表，然后從葉子結點開始向上訪問，是左孩子的把“0接進鏈表是右孩子的把“1接進鏈表，直到根結點，然后把葉子結點的元素及存儲其赫夫曼鏈表的頭指針讀入順序表，直到把所有的葉子結點的元素及指向存儲其赫夫曼編碼鏈表的頭指針讀入順序表，這樣得到的赫夫曼編碼是倒序的。從存儲其葉子結點及指向存儲其赫夫曼編碼鏈表頭指針的順序表表頭開始順序訪問

3、各元素，在輸出其赫夫曼編碼之前，把鏈表中的編碼順序讀入到等長的棧中，然后編碼出棧就會得到順序的赫夫曼編碼，直到把所有的葉子結點都訪問到。用一個字符型的指針指向字符串的第一個字符，從存儲葉子結點元素及指向存儲其赫夫曼編碼鏈表的頭指針的順序表表頭開始訪問順序表中的各元素，直到找到葉子結點的元素和當前字符相等就結束訪輸出赫夫曼編碼，回到表頭，指針后移，直到輸出字符串的最后一個字符的赫夫曼編碼，這樣就得到輸入字符串的赫夫曼編碼。函數(shù)劃分 該程序有一個主函數(shù)和多個子函數(shù)，主函數(shù)完成對子函數(shù)的調(diào)用，各子函數(shù)實現(xiàn)相應的功能。子函數(shù)：結點的開辟。實現(xiàn)對輸入字符串中出現(xiàn)的不同字符及其出現(xiàn)字數(shù)的信息記錄。用葉子結

4、點構造赫夫曼樹。獲得構造的赫夫曼樹中所有葉子結點的元素及其赫夫曼編碼。輸出各葉子結點元素及其對應的赫夫曼編碼。輸出輸入的字符串的赫夫曼編碼。調(diào)用各子函數(shù)四詳細設計算法、流程圖、程序算法創(chuàng)立存儲葉子結點元素及其權值的鏈表定義結構體node，其數(shù)據(jù)成員包括，字符型的元素a和整型元素b和指向node的next指針，來存儲葉子結點的內(nèi)容和權值。定義三個指向node的指針head、p1、p2和字符指針n、t、h，調(diào)用setnode()函數(shù)開辟一個結點讓head指向該結點，p1=head,讓n指向輸入字符串的第一個元素，當n指向的內(nèi)容不是0時，如果n指向字符串的第一個字符，那么開辟一個結點，讓p2指向該結

5、點，讓t指向字符串的第一個元素，當*t!=0并且*t=*n那么r+r為整型，初始值為0，把p2-a=*n,p2-b=r,p1-next=p2,p1=p2,n+,t回到字符串首；否那么i+i為整型，初始值為1r=0，j=1；讓t指向字符串第一個元素，當*t！=0，如果*t=*n，r+，t+；讓h指向字符串的第一個元素，當h！=n時如果*h=*n就跳出此循環(huán)，否那么，j+，h+如果i=j那么開辟新的結點p2-a=*n,p2-b=r,p1-next=p2,p1=p2;n+,當把最后一個結點連入鏈表中，p1-next=NULL,然后把p1=head-next,當p!=NULL時輸出結點中葉子結點的元素

6、和對應的權值；最后返回head。/setnode()函數(shù)的算法：設指向node的指針p，用malloc開辟一個node結點并讓p指向該結點，返回p。構造赫夫曼樹定義結構體node1，其數(shù)據(jù)項字符型a存放葉子結點元素、整型weight存放對應權值、整型sign起標記作用、和指向左、右孩子及父母結點的指針lchild、rchild和parent。定義指向node1的指針p0、p1、p2、p3、p4和整型的m、n、i、j、k1、k2，n=0、p=head-next，當p！=NULL，n+，p=p-next，開辟可以存儲2*n個node1的順序表，讓p0指向表頭，p1=p0,p=head-next,當

7、p！=NULL時p1-a=p-a,p1-weight=p-bp1的指向左、右孩子及父母的指針指空，p=p-next，p1+；p1+,p=p-next;i=1,當i=n-1,j=0,當jsign=NULL并且m=p2-weight用break結束循環(huán)否那么p2+；p2=p0，當p2！=p時，如果m=p2-weight并且p2-sign=NULL,把p2-weight賦給m，否那么p2+；把p0賦給p2，當p2不等于p1時，如果m等于p2-weight并且p2-sign等于NULL，把1賦給p2-sign,如果j=0，把p2賦給p1-lchild,p2-weight賦給p1-weight,p1賦給

8、p2-parent,用break結束循環(huán)；如果j=1，那么把p2賦給p1-rchild,p1-weight加p2-weight賦給p1-weight,p1賦給p2-parent,用break結束循環(huán)；如果j等于0，k1+，p2+；如果j等于1，k2+，p2+；j+；如果k1大于k2把p1-lchild賦給p3，p1-rchild賦給p4，p4賦給p1-lchild,p3賦給p1-rchild,p1-sign=NULL,p1+,i+;然后p-，把p1-parent=NULL,p1+,把p0賦給p2，當p2不等于p時輸出p2的各數(shù)據(jù)項，拍p2+；返回p0。獲得各葉子結點的赫夫曼編碼定義只存儲赫夫曼

9、編碼的結構體code，它的數(shù)據(jù)項有字符型的a存儲0、1編碼以及指向下一個結點的指針next。定義結構體huffmancode，它的數(shù)據(jù)項有字符型a(存儲葉子結點元素)、指向結構體code的指針head。設指向node1的指針p1、p2、p4，指向huffmancode的指針l、l1和指向code的指針h、h1，把pp為函數(shù)的形參賦給p2，當p2-lchild和p2-rchild同時為NULL，n+，n為整型，初始化為零，p2+；調(diào)用malloc函數(shù)開辟可以存儲n+1個huffmancode結點的順序表，讓l指向該順序表的表頭，把l賦給l1，把p賦給p4，當p4-lchild和p4-rchild

10、同時為NULL把p4賦給p1調(diào)用setcode函數(shù)開辟一個結點讓h1指向該結點，把h1賦給l1-head,當p1-parent不等以NULL時，如果p1等于p1-parent-lchild，調(diào)用setcode()函數(shù)讓h指向它，h-a=0，h1-next=h,h1=h;否那么，調(diào)用setcode函數(shù)開辟一個結點讓h指向它，h-a=1，h1-next=h,h1=h;然后，把p1-parent賦給p1，把NULL賦給h1-next,p4-a賦給l1-a,l+,當把所有的葉子結點元素及其赫夫曼編碼讀入順序表后把NULL賦給l1-a;返回l。/setcode函數(shù)的算法：設指向code的指針p，調(diào)用ma

11、lloc函數(shù)開辟一個code結點，讓p指向該結點，返回p。輸出各葉子結點的赫夫曼編碼設指向huffmancode的指針p，指向code的指針和指向字符型的指針base、top；把head1函數(shù)的形參賦給p，當p-a!=NULL時，把0賦給n，p-head-next賦給h，當h！=NULL時n+，h=h-next，開辟一個可以存儲n+1個字符的棧，讓base指向棧底，top=base,把h=p-head-next，當h！=NULL時，*top=h-a，top+，h=h-next；top-，當to不等于base時，輸出*top，top- -;輸出*top；p+。輸出字符串的赫夫曼編碼設指向huff

12、mancode的指針p1，指向code的指針h和指向字符型的指針base，top，p2，讓p2指向字符串的第一個元素，當*p2！=0時，輸出*p2，p2+；當*p！=0時p為函數(shù)的形參，把0賦給nn為整型p1=p0p0為形參當p1-a!=NULL時，如果p1-a等于*p把p1-head-next賦給h，當h！=NULL時，h=h-next,base指向可以存儲n+1個字符的棧底，top=base，把p1-head-next賦給h，當h！=NULL，*top=h-a,top+,h=h-next，top自減，當top！=base，輸出*top，top-，輸出*top，用break結束循環(huán)，p+。c

13、ontrol函數(shù)定義長度為20的字符數(shù)組a，指向node的指針p，整型n和指向node1的指針p1，輸入a把a作為實參調(diào)用函數(shù)getdataa，把返回值賦給p，把p作為實參調(diào)用coutdatap把返回值賦給n，如果n等于1，p=p-next,輸出p-a和p-b,否那么，以p為實參調(diào)用settreep，將返回值賦給p1，以p1為實參調(diào)用gethuffmamcodep1函數(shù)，將返回值賦給p2p2為指向huffmancode的指針，以p2為實參調(diào)用printhuffmancodep1函數(shù)，然后以a，p2為實參調(diào)用printa，p2函數(shù)。/coutdata()函數(shù)的算法：設指向node的指針p，把he

14、ad-next賦給p，當p！=NULL時n+，p=p-next;返回n。主函數(shù)調(diào)用control函數(shù)。流程圖創(chuàng)立存儲葉子結點元素及其權值的鏈表開辟一個新的結點，讓head指向它p1=headn=a *n！= 0 n=是=a?否開辟新的結點，讓p1指向它 i+ r=0 t=n j=1 *t！= 0 t=a*t=是= 0 ？否 *t！= 0 *t=*n是？否r+r+ t+ t+p2-a=*n h=a p2-b=r h！=n p1-next=p2*h=是*n？ 否p1=p2 n+break j+ h+i=j？是 否開辟新結點，讓p2指向它p2-a=*np2-b=rp1-next=p2p1=p2p1-

15、next=NULL p1=head-nextp1!=NULL輸出p1-a輸出p1-a返回head/setnode函數(shù)開辟一個node結點，讓p指向它返回p構造赫夫曼樹 p=head-next p！=NULLn+p=p-nextp0=listnode1malloc2*n*sizeofnode1p1=p0p=head-nextp！=NULLp1-a=p-ap1-weight=p-bp1-lchild p1-rchild p1-parent p1-sign全置空p1+i=1i=n-1j=0jsign= =NULL?否m=p2-weightp2+breakp2=p0p2!=p1m=p2-weight

16、是并且p2-sign= =NULL?否m=p2-weightp2+p2=p0p2!=p1m=p2-weight是并且p2-sign= =NULL?否 j=0?是 p2-sign j=0? =1? 是 否p1-lchild=p2 p1-rchild=p2p1-weight p1-weight+= k1+=p2-weight p2-weightk2+ p2-parent p2-parent =p1=p1breakp2+j+k1k2是?否p3=p1-lchildp4=p1-rchildp1-lchild=p4p1-rchild=p3p1-sign=NULLp1+i+p1- -p1-parent=NU

17、LLp1+p2=p0p2!=p1輸出p2-a p2-weightp2-lchild p2-parent p2-rchildp2+返回p0獲得各葉子結點的赫夫曼編碼 p2=p p2=lchild= =NULL&p2-rchild= =NULLn+p2+l=(listhuffmancode)malloc(n+1)*sizeof(huffmancode)p4=pp4-lchild= =NULL&p4-rchild= =NULLp1=p4h1=setcode()l1-head=h1P1-parent！=NULL是 p1=p1-parent-lchild? 否開辟一個結點讓h指向它 h-a= 0 h1-

18、next=hh1=hh-a= 0 h1-next=hh1=hh1-next=NULLl1-a=p4-a l1+l1-a=NULL 返回l /setcode函數(shù)開辟一個code結點，讓p指向該結點 返回p輸出各葉子結點的赫夫曼編碼 p=head1p-a!=NULLh=h-head-nexth!=NULLn+h=h-nextbase=(char *)malloc(n+1)*sizeof(char)h=h-head-nexth!=NULL*top=h-atop+h=h-nexttop-top!=base輸出*toptop-輸出*top輸出字符串的赫夫曼編碼p2=p*p2!= 0 *p2p2+*p!=

19、 0 n=0p1=p0p1-a!=NULL p1-a= =*p? 是否h=p1-head-nextp1+h!=NULLn+h=h-nextbase=(char *)malloc(n+1)*sizeof(char)top=baseh=p1-head-nexth!=NULL*top=h-atop+h=h-next-toptop!=base輸出*topbreakp+control函數(shù)輸入ap=getdata(a)n=coutdata(p)是n= =1?否p=p-nextp1=settree(p) 輸出p-a和p-bp2=gethuffmancode(p1)printhuffmancode(p2)pr

20、int(a,p2) /countdata()函數(shù)p=head-nextp!=NULLn+p=p-next返回n 主函數(shù)調(diào)用control()函數(shù)/程序的編譯環(huán)境是Visual studio 2021/把統(tǒng)計葉子結點元素和權值的函數(shù)放在“中#includeusing namespace std;typedef struct node /存儲葉子結點元素及其權值的結構體char a; /葉子結點的元素int b; /葉子結點的權值struct node *next; /指向下一個結點的指針*listnode;listnode setnode() /開辟結點的函數(shù)listnode p;p=(list

21、node)malloc(sizeof(node);return p;listnode getdata(char *a) /*統(tǒng)計輸入字符串中的不同字符及其出現(xiàn)的次數(shù)的函并且把統(tǒng)計出的數(shù)據(jù)，作為葉子結點的元素和權值*/ listnode head,p1,p2; char *n,*t,*h; int i=1,j=1,r=0; head=setnode(); p1=head; for(n=a;*n!=0;n+) if(n=a) p2=setnode(); for(t=n;*t!=0;t+) /統(tǒng)計相同的字符在字符串中出現(xiàn)的次數(shù)if(*t=*n) r+; p2-a=*n; p2-b=r; p1-nex

22、t=p2; p1=p2; else i+; r=0; j=1; for(t=a;*t!=0;t+) if(*t=*n) r+; for(h=a;h!=n;h+) if(*h=*n) break; else j+; if(i=j) p2=setnode(); /調(diào)用setnode函數(shù)開辟結點 p2-a=*n; p2-b=r; p1-next=p2; p1=p2; p1-next=NULL; cout電文的長度為：iendl; cout-endl; p1=head; cout葉子結點t權值next;p1!=NULL;p1=p1-next) coutatt bendl; cout-next;p!=N

23、ULL;p=p-next) n+; return n; /把構造赫夫曼樹的函數(shù)放在頭文件“中#include#include計算權值.husing namespace std;typedef struct node1 /赫夫曼樹的結點結構體 char a; /結點元素int weight,sign; /結點的權值和結點的標記struct node1 *parent,*lchild,*rchild; /指向父母結點和左、右孩子的指針*listnode1; /指向node1的指針listnode1 settree(listnode head) /構造赫夫曼樹的函數(shù) listnode p; list

24、node1 p0,p1,p2; int m,n,i,j,k1,k2; struct node1 *p3,*p4; n=0; for(p=head-next;p!=NULL;p=p-next) n+; p0=(listnode1)malloc(2*n*sizeof(node1); /開辟可以存儲2n個赫夫曼樹結點的順序表 p1=p0; for(p=head-next;p!=NULL;p=p-next) /把葉子結點的信息讀入到 順序表中 p1-a=p-a; p1-weight=p-b; p1-lchild=NULL; p1-parent=NULL; p1-rchild=NULL; p1-sign

25、=NULL; p1+; for(i=1;i=n-1;i+) for(j=0;jsign=NULL) m=p2-weight; break; for(p2=p0;p2!=p1;p2+) if(m=p2-weight) if(p2-sign=NULL) m=p2-weight; for(p2=p0;p2!=p1;p2+) if(m=p2-weight) if(p2-sign=NULL) p2-sign=1; if(j=0) /把先找到的權值最小的作為左孩子 p1-lchild=p2; p1-weight=p2-weight; p2-parent=p1; else if(j=1) /把后找到的權值最

26、小的最為右孩子 p1-rchild=p2; p1-weight=p1-weight+p2-weight; p2-parent=p1; break; if(j=0) k1+; /標記先找到的權值最小的結點在順序表中的位置 else if(j=1) k2+; /標記后找到的權值最小的結點在順序表中的位置 if(k1k2) /*如果先找到的權值最小的結點在順序表中的位置在后找到的后面 那么他們父母結點的左右孩子指針交換*/ p3=p1-lchild; p4=p1-rchild; p1-lchild=p4; p1-rchild=p3; p1-sign=NULL; p1+; p1-; p1-parent

27、=NULL; p1+; p2=p0; cout葉子結點t權值t左孩子tt父母結點t右孩子endl; /輸出構造的赫夫曼樹 while(p2!=p1) coutatt weighttlchildtparenttrchildendl; p2+; cout-endl; return p0; /把葉子結點赫夫曼編碼的獲取的函數(shù)放在頭文件“中#include#include構造赫夫曼樹.husing namespace std;typedef struct code /存儲赫夫曼編碼的結構體 char a; /存儲0、1編碼struct code *next; /指向鏈表下一個結點的指針*listcod

28、e; /指向該結構體的指針typedef struct huffmancode /存儲葉子結點元素和赫夫曼編碼鏈表的頭指針的結構體char a; /葉子結點的元素listcode head; /指向存儲赫夫曼編碼鏈表的指針*listhuffmancode; listcode setcode() /開辟存儲0、1編碼結點的函數(shù)listcode p;p=(listcode)malloc(sizeof(code);return p;listhuffmancode gethuffmancode(listnode1 p) /把得到的葉子結點及其 赫夫曼編碼存到順序表中的函數(shù)listnode1 p1,p2

29、,p4;int n=0;listhuffmancode l,l1;listcode h,h1;for(p2=p;p2-lchild=NULL&p2-rchild=NULL;p2+)n+;l=(listhuffmancode)malloc(n+1)*sizeof(huffmancode); /開辟可以存儲n+1個葉子結點信息的順序表 l1=l;for(p4=p;p4-lchild=NULL&p4-rchild=NULL;p4+)p1=p4;h1=setcode();l1-head=h1; for(;p1-parent!=NULL;p1=p1-parent)if(p1=p1-parent-lchi

30、ld)h=setcode();h-a=0;h1-next=h;h1=h;else if(p1=p1-parent-rchild)h=setcode();h-a=1;h1-next=h;h1=h;h1-next=NULL;l1-a=p4-a;l1+;l1-a=NULL;return l;/把輸出赫夫曼編碼的函數(shù)放在頭文件“中#include#include獲得赫夫曼編碼.husing namespace std;void printhuffmancode(listhuffmancode head1) /輸出葉子結點及其赫夫曼編碼 的函數(shù)listhuffmancode p; p=head1; li

31、stcode h;int n;char *base,*top;cout葉子結點t權值a!=NULL;p+)coutahead;for(h=h-next;h!=NULL;h=h-next)n+;base=(char *)malloc(n+1)*sizeof(char);top=base;h=p-head;for(h=h-next;h!=NULL;h=h-next)*top=h-a; top+;top-;for(;top!=base;top-)cout*top;cout*top;coutendl; cout-endl; void print(char *p,listhuffmancode p0)

32、/輸出輸入字符串的赫夫曼編碼listhuffmancode p1;listcode h;int n;char *base,*top,*p2;cout電文內(nèi)容：;for(p2=p;*p2!=0;p2+)cout*p2;coutendl;couta!=NULL;p1+)if(p1-a=*p)h=p1-head;for(h=h-next;h!=NULL;h=h-next)n+;base=(char *)malloc(n+1)*sizeof(char);top=base;h=p1-head;for(h=h-next;h!=NULL;h=h-next)*top=h-a;top+;for(-top;top!=base;top-)cout*top;cout*top;break;/把control函數(shù)放在頭文件“中#include#include輸出赫夫曼編碼.husing namespace std;void control() /調(diào)用各個功能函數(shù)cout 數(shù)據(jù)結構課程設計endl;cout-endl;char