實驗四 哈夫曼樹與哈夫曼編碼_第1頁
實驗四 哈夫曼樹與哈夫曼編碼_第2頁
實驗四 哈夫曼樹與哈夫曼編碼_第3頁
實驗四 哈夫曼樹與哈夫曼編碼_第4頁
實驗四 哈夫曼樹與哈夫曼編碼_第5頁
已閱讀5頁,還剩4頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

實驗四哈夫曼樹與哈夫曼編碼一、實驗?zāi)康?、使學(xué)生熟練掌握哈夫曼樹的生成算法。2、熟練掌握哈夫曼編碼的方法。二、實驗內(nèi)容本次實驗提供4個題目,難度相當,學(xué)生可以根據(jù)自己的情況選做,其中題目一是必做題,其它選作!題目一、哈夫曼樹和哈夫曼編碼[問題描述]一電文,有若干個不同字符,要求從終端輸入這些不同字符及其出現(xiàn)的頻率,然后對這些字符進行哈夫曼編碼,并輸出。[測試數(shù)據(jù)]利用教材P.148例6-2中的數(shù)據(jù)調(diào)試程序(可自己設(shè)定測試數(shù)據(jù))。[選作內(nèi)容]1、打印出該哈夫曼樹2、若從終端輸入任意一段電文(假設(shè)僅為26個大小寫英文字母),試編程高效地求出該段電文的哈夫曼編碼。提示:如何快速統(tǒng)計不同字符的出現(xiàn)頻率3、譯碼:將上述1的編碼結(jié)果還原成電文。三、算法設(shè)計設(shè)計思路設(shè)計過程1、程序所需頭文件已經(jīng)預(yù)處理宏定義以及變量如下#include<iostream>#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>usingnamespacestd;typedefstructnode{charch;intdata;structnode*parent;structnode*lchild,*rchild,*next;}hufnode;typedefhufnode*linkhuf;typedefstructHFcode{charch;intdata;intcode[20];inttop;}tagHFcode;linkhufinsert(linkhufroot,linkhufs){ linkhufp1,p2; if(root==NULL) root=s; else { p1=NULL; p2=root; while(p2&&p2->data<s->data) { p1=p2; p2=p2->next; } s->next=p2; if(p1==NULL) root=s; else p1->next=s;}returnroot;}2、創(chuàng)建哈夫曼樹voidcreatehuffman(linkhuf*root){linkhufs,rl,rr;while(*root&&(*root)->next){ rl=*root; rr=(*root)->next; *root=rr->next; s=(linkhuf)malloc(sizeof(hufnode)); s->next=NULL; s->data=rl->data+rr->data; s->parent=NULL; s->lchild=rl; s->rchild=rr; rl->parent=s; rr->parent=s; rl->next=rr->next=NULL; *root=insert(*root,s);}}voidinorder(linkhuft){if(t){inorder(t->lchild);printf("%5d",t->data);inorder(t->rchild);}}3、哈夫曼編碼voidHFcoding(linkhufroot,linkhuftemp,tagHFcodeHFcode[],int*leaftop){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL){temp=root;HFcode[(*leaftop)].top=0;HFcode[(*leaftop)].ch=root->ch;HFcode[(*leaftop)].data=root->data;while(temp->parent!=NULL){if(temp->parent->lchild==temp) HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=0;else HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=1;HFcode[(*leaftop)].top++;temp=temp->parent;}(*leaftop)++;}HFcoding(root->lchild,temp,HFcode,leaftop);HFcoding(root->lchild,temp,HFcode,leaftop);}}4、輸出求得的哈夫曼編碼voidOutCoding(tagHFcodeHFcode[],intleaftop){ inti,j=0; for(i=0;i<leaftop;i++) { printf("%d\t",HFcode[i].data); j=HFcode[i].top-1; while(j>=0) { printf("%d",HFcode[i].code[j]); j--; } printf("\n"); } }四、調(diào)試與測試輸入字符ABCDEFGH進行測試五、心得體會做這次實驗,發(fā)現(xiàn)在寫程序的時候出現(xiàn)了很多的錯誤,及還有很多的知識不以靈活運用,特別是對棧和隊列的操作問題。大一的課程以及C語言沒掌握好,所以這次做實驗,覺得有好多知識不熟悉,后來經(jīng)過查找資料,在自己的努力下和同學(xué)的幫助下,終于完了本次實驗。以后在課余時間里還要多寫程序,熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤,以便能節(jié)省調(diào)試程序的時間。六、源代碼#include<iostream>#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>usingnamespacestd;typedefstructnode{charch;intdata;structnode*parent;structnode*lchild,*rchild,*next;}hufnode;typedefhufnode*linkhuf;typedefstructHFcode{charch;intdata;intcode[20];inttop;}tagHFcode;linkhufinsert(linkhufroot,linkhufs){ linkhufp1,p2; if(root==NULL) root=s; else { p1=NULL; p2=root; while(p2&&p2->data<s->data) { p1=p2; p2=p2->next; } s->next=p2; if(p1==NULL) root=s; else p1->next=s;}returnroot;}voidcreatehuffman(linkhuf*root){linkhufs,rl,rr;while(*root&&(*root)->next){ rl=*root; rr=(*root)->next; *root=rr->next; s=(linkhuf)malloc(sizeof(hufnode)); s->next=NULL; s->data=rl->data+rr->data; s->parent=NULL; s->lchild=rl; s->rchild=rr; rl->parent=s; rr->parent=s; rl->next=rr->next=NULL; *root=insert(*root,s);}}voidinorder(linkhuft){if(t){inorder(t->lchild);printf("%5d",t->data);inorder(t->rchild);}}voidHFcoding(linkhufroot,linkhuftemp,tagHFcodeHFcode[],int*leaftop){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL){temp=root;HFcode[(*leaftop)].top=0;HFcode[(*leaftop)].ch=root->ch;HFcode[(*leaftop)].data=root->data;while(temp->parent!=NULL){if(temp->parent->lchild==temp) HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=0;else HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=1;HFcode[(*leaftop)].top++;temp=temp->parent;}(*leaftop)++;}HFcoding(root->lchild,temp,HFcode,leaftop);HFcoding(root->lchild,temp,HFcode,leaftop);}}//輸出求得的哈夫曼編碼voidOutCoding(tagHFcodeHFcode[],intleaftop){ inti,j=0; for(i=0;i<leaftop;i++) { printf("%d\t",HFcode[i].data); j=HFcode[i].top-1; while(j>=0) { printf("%d",HFcode[i].code[j]); j--; } printf("\n"); } }intmain(){tagHFcodeHFcode[20];linkhuff=NULL;linkhuftemp=NULL;linkhufp[6];inti;inta[20];charch;intleaftop=0;printf("請輸入各節(jié)點的節(jié)點值和權(quán)值:\n");for(i=0;i<7;i++){p[i]=(linkhuf)malloc(sizeof(hufnode));scanf("%c",&(p[i]->ch));getchar();scanf("%d",&p[i]->data);p[i]->lchild=NULL;p[i]->rchild=NULL;p[i]->nex

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論