實驗四 哈夫曼樹與哈夫曼編碼

實驗四哈夫曼樹與哈夫曼編碼一、實驗?zāi)康?、使學(xué)生熟練掌握哈夫曼樹的生成算法。2、熟練掌握哈夫曼編碼的方法。二、實驗內(nèi)容本次實驗提供4個題目，難度相當(dāng)，學(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