實驗三哈夫曼編碼

PAGE第8頁共9頁華北水利水電學院數(shù)據(jù)結構實驗報告2012～2013學年第一學期2010級計算機科學與技術專業(yè)班級：2010134學號：201013432姓名：蔡啟林實驗三樹的應用實驗題目：樹的應用——哈夫曼編碼實驗內(nèi)容：利用哈夫曼編碼進行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r間，降低傳輸成本。根據(jù)哈夫曼編碼的原理，編寫一個程序，在用戶輸入結點權值的基礎上求哈夫曼編碼。從鍵盤輸入若干字符及每個字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結點的權值，建立哈夫曼樹，求出各字符的哈夫曼編碼。要求：輸出存放哈夫曼樹的數(shù)組HT的初態(tài)和終態(tài)；輸出每個字符的哈夫曼編碼；輸入由上述若干字符組成的字符串，對電文進行編碼并輸出；（選作）輸入電文的哈夫曼編碼，進行譯碼并輸出。程序源代碼：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<conio.h>#defineMAXLEAF100structHTNode{ charletter; intparent; intlchild; intrchild; intweight;};structChNode{ charletter; intweight;};structHCode{ charcode[MAXLEAF]; intm_start;};//創(chuàng)建哈夫曼樹voidCreateHT(HTNodeht[],intn,ChNodes[]){ inti,k,s1,s2; intm1,m2; for(i=0;i<2*n-1;i++) { ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; ht[i].weight=0; } for(i=0;i<n;i++) { ht[i].letter=s[i].letter; ht[i].weight=s[i].weight; } printf("哈夫曼樹初態(tài)為:\n"); printf("dataweightparentlchildrchild\n"); for(i=0;i<2*n-1;i++) { printf("%-6c%-6d%-6d%-6d%-6d\n",ht[i].letter,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild); } for(i=n;i<2*n-1;i++) { m1=m2=32767; s1=s2=0; for(k=0;k<=i-1;k++) { if(ht[k].parent==0) { if(ht[k].weight<m1) { m2=m1; s2=s1; m1=ht[k].weight; s1=k; } elseif(ht[k].weight<m2) { m2=ht[k].weight; s2=k; } } } ht[s1].parent=i; ht[s2].parent=i; ht[i].weight=ht[s1].weight+ht[s2].weight; ht[i].lchild=s1; ht[i].rchild=s2; } printf("\n哈夫曼樹終態(tài)為:\n"); printf("dataweightparentlchildrchild\n"); for(i=0;i<2*n-1;i++) { printf("%-6c%-6d%-6d%-6d%-6d\n",ht[i].letter,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild); } printf("\n");}//哈夫曼編碼voidCreateCode(HTNodeht[],HCodehcd[],intn){ inti,f,letter; HCodehc; for(i=0;i<n;i++) { hc.m_start=n-1; letter=i; f=ht[i].parent; while(f!=-1) { if(ht[f].lchild==letter) hc.code[hc.m_start--]='0'; else hc.code[hc.m_start--]='1'; letter=f; f=ht[f].parent; } hc.m_start++; hcd[i]=hc; } printf("哈夫曼編碼:\n"); printf("結點信息權值哈夫曼編碼\n"); for(i=0;i<n;i++) { printf("%c%s%d%s",ht[i].letter,"",ht[i].weight,""); for(intj=hcd[i].m_start;j<n;j++) printf("%c",hcd[i].code[j]); printf("\n"); }}//譯碼voidCoding(HTNodeht[],HCodehcd[],intn,charstr[]){ for(inti=0;str[i]!='\0';i++) { for(intj=0;j<n;j++) { if(str[i]==ht[j].letter) { for(intk=hcd[j].m_start;k<n;k++) { printf("%c",hcd[j].code[k]); } break; } } } printf("\n");}voidmain(){ charstr[MAXLEAF]; printf("**********************歡迎使用赫夫曼編譯系統(tǒng)**********************\n"); printf("從鍵盤輸入若干字符:\n"); scanf("%s",str); ChNodes[20]; memset(s,0,sizeof(ChNode)*20); intj=0; for(inti=0;str[i]!='\0';i++) { intflag=0; for(intk=0;k<j;k++) { if(str[i]==s[k].letter) { s[k].weight++; flag=1; break; } } if(!flag) { s[j].letter=str[i]; s[j].weight=1; j++; } } HTNodeht[MAXLEAF]; memset(ht,0,sizeof(HTNode)*MAXLEAF); HCodehcd[MAXLEAF]; intnum=-1; while(1) { printf("************************主菜單********************************\n"); printf("**1.創(chuàng)建哈夫曼樹并查看初態(tài)和終態(tài)**\n"); printf("**2.創(chuàng)建并查看哈夫曼編碼**\n"); printf("**3.譯碼**\n"); printf("**4.退出**\n"); printf("****************************************************************\n"); scanf("%d",&num); if(num==0) break; switch(num) { case1: { CreateHT(ht,j,s); } break; case2: { CreateCode(ht,hcd,j); } break; case3: { charstr[MAXLEAF]; printf("請輸入譯文:\n"); scanf("%s",str); printf("譯碼后為:"); Coding(ht,hcd,j,str); } break; default: break; } printf("按任意鍵繼續(xù)..."); getch(); system("cls"); }}測試結果：五、小結（包括收獲、心得體會、存在的問題及解決問題的方法、建議等）注：內(nèi)容一律使用宋體五號字，單倍行間距通過這次的課程設計,我對赫夫曼樹以及赫夫曼編碼有了更深的認識和理解，我在設計期間遇到的難點就是開始的時候，代碼中有許多的錯誤，特別是輸出赫夫曼樹的存儲結構的初態(tài)和終態(tài)。后來在好好的看教材的基礎上解決了這個問題，但是這個存儲結構還有一些問題，在這次編譯哈夫曼樹的存儲結構的初態(tài)和終態(tài)，使得我更加的明白了哈夫曼到底是怎么存儲信息的。這次的編譯過程遇到很小的知識錯誤，就是設置清屏時沒有設置頭文件，就是這個小小的錯誤，讓我在調(diào)試程序的時候沒有捕獲的數(shù)據(jù)，后來修改后才解決這個問題。許多的錯誤讓我明白了一個道理細心是非常重要的。同時，對于編程者而言，思路清晰是相當重要的。在適當?shù)臅r候和同學一起交流探討是一個十分好的學習機會。請教老師也很重要，因為畢