四川航天職業技術學院《計算機軟件技術基礎》實習報告書專業：電子工程準考證號：010110471022姓名：邱軍銳指導老師：趙威填表日期：年月日四川航天職業技術學院制《計算機軟件技術基礎》實習報告書時間：年月日至月日學時：實習內容：1.了解算法知識體系 2.掌握算法相關方法3.完成哈夫曼（huffman)與哈夫曼碼問題實習課題實習計劃：1.資料收集、整理 2.實習報告書撰寫目標：1.完成算法相關問題知識的積累、深化 2.完成哈夫曼與哈夫曼碼問題方案的選擇、落實要求：1.緊扣實習課題，重點突出 2.報告書符合實習報告格式教師評語：成績考核：教師簽名：時間：年月日備注：哈夫曼（huffman)與哈夫曼碼需求分析編輯一個可以完成哈夫曼（huffman)與哈夫曼碼問題的程序。程序的具體要求有下面幾點：輸入一個文本，統計各字符出現的頻度，輸出結果；使用二叉鏈表或三叉鏈表作存儲結構，構造哈夫曼(Huffman)樹；確定和輸出各字符的哈夫曼碼；輸入一個由0和1組成的代碼序列，翻譯并輸出與之對應的文本；2.數據結構及儲存結構在這個程序中我用了三叉鏈表tree作為哈夫曼樹的結構：左、右兒子和父親

節點；并且在開始，我還用此結構生成了單鏈表，用來存儲讀取的字符。編碼的時候，我把編碼放在棧結構stack中，然后逆序輸出即為哈夫曼編碼。存放葉節點時用到了指針數組。

structtree(){

chardata;

intm,sign;

structtree*lchild,*rchild,*parent;

}

structstack{

intdata;

structstack*next;

}3．設計思想先調用frequency函數讀取字符，創建鏈表來存儲字符及其相關信息；同時把字符放進數組中進行備份，因為后面編碼時要用到這些字符（它們就是葉節點）。然后遍歷這個鏈表輸出個字符的頻度。接著調用ctree函數來生成哈夫曼樹。在ctree函數中，首先對剛才那個鏈表按照頻度排序，變成頻度遞增鏈表；然后取其前兩個節點作為新建哈夫曼樹的左右兒子（注：左兒子的頻度<=右兒子的頻度），再把它們從鏈表中刪除，并且把新建的哈夫曼樹的根結點插入到鏈表中。這樣重復操作，就生成了哈夫曼樹。然后調用ccode函數編碼。我采用的是從葉到根的編碼方式。先從數組中取出數據（即為一個葉節點），看其m的值（0/1），放進stack棧中，然后向根遍歷，接著把棧中的數據取出輸出，即為編碼。最后調用translate函數進行譯碼。先讀取01序列放進新創建的一個鏈表（隊列形式）中，然后從根到葉進行遍歷：從鏈表中取出一個數據，是0則到左子樹，1則到右子樹，如果其左右子樹為空，則輸出字符data，再取下一個數據從根重新遍歷。這樣就得到譯碼了。4.程序清單 #include<stdio.h>

#include<conio.h>

structtree{/*定義哈夫曼樹的結構*/

chardata;/*存放字符*/

intm,sign;/*m存放字符出現的頻率sign是左(0)或右(1)兒子的標志*/

structtree*lchild,*rchild,*parent;/*左兒子右兒子父節點*/

};

structstack{/*定義棧的結構*/

intdata;

structstack*next;

};

structtree*ps[50],*root,*head;

/*數組存放字符root為二叉樹的根結點head為鏈表的頭節點*/

intsize;/*標志字符個數*/

/*************************統計各字符出現的頻度***********************/

voidfrequency(){

structtree*r,*p,*q;

intn,l,j=1;

/*錄入第一個字符并創建鏈表*/

clrscr();/*清屏*/

head=NULL;

printf("InputthetextendofENTER:\n");

n=getchar();

if(n!='\n'){

p=(structtree*)malloc(sizeof(structtree));

p->data=n;

p->m=1;

p->sign=-1;

p->lchild=NULL;

p->rchild=NULL;

p->parent=NULL;

head=p;

ps[0]=p;/*把字符(后面的葉節點)放進數組備份*/

n=getchar();}

/*錄入其它字符*/

while(n!='\n'){

l=0;r=p;

for(q=head;q!=NULL&&l==0;q=q->parent){

if(q->data==n){/*檢查是否和已經錄入的字符相同*/

q->m++;/*如果相同則此字符的頻度變量加1*/

l=1;

}

r=p;

}

if(l==0){/*如果不同則錄入并加入鏈表*/

p=(structtree*)malloc(sizeof(structtree));

p->data=n;

p->m=1;

p->sign=-1;

p->lchild=NULL;

p->rchild=NULL;

p->parent=NULL;

r->parent=p;

ps[j]=p;/*把字符(后面的葉節點)放進數組備份*/

j++;

}

n=getchar();

}

/*輸出字符的頻度*/

p=head;

size=0;

printf("\nFrequencyasfollows:\ncharactersfrequency\n");

while(p!=NULL){

printf("%c%d\n",p->data,p->m);

p=p->parent;

size++;/*統計字符的個數*/

}

}

/****************************生成樹**********************************/

voidctree(){

structtree*t,*r,*p,*e,*q;

intn;

/****給鏈表排序生成頻度遞增鏈表*****/

for(p=head;p->parent!=NULL;p=p->parent){

for(q=p->parent;q!=NULL;q=q->parent){

if(p->m>q->m){

n=q->m;/*交換信息*/q->m=p->m;

p->m=n;

n=q->data;

q->data=p->data;

p->data=n;

}

}

}

/***********生成哈夫曼樹***********/

p=head;

while(p!=NULL&&p->parent!=NULL){

/*取遞增鏈表前兩個為左右兒子生成哈夫曼樹*/

q=p->parent->parent;/*然后把它們從鏈表中刪掉*/

t=(structtree*)malloc(sizeof(structtree));

t->lchild=p;/*頻度:左兒子<=右兒子*/

t->rchild=p->parent;

t->m=p->m+p->parent->m;

t->rchild->parent=t;

t->rchild->sign=1;

t->lchild->parent=t;

t->lchild->sign=0;

t->sign=-1;

root=t;/*root為根結點*/

root->parent=NULL;

if(q!=NULL){/*判斷鏈表是否為空*/

head=q;

r=head;

e=head;/*把新生成的根結點插入到鏈表中去*/

if(head->m>t->m){/*判斷是否為頭節點*/

t->parent=q;

head=t;

}

else{

r=r->parent;

while(r!=NULL&&r->m<t->m){

e=r;

r=r->parent;

}

t->parent=r;

e->parent=t;

}

p=head;

root=t;

}elsebreak;/*如果鏈表為空則結束*/

}

}

/******************************編碼******************************/

voidccode(){

structtree*p,*q;

intj;

printf("\ncodesasfollows:\ncharacterscode\n");

for(j=0;j<size;j++){/*做size(葉節點個數)次循環*/

head=NULL;

p=ps[j];/*從葉到根求編碼*/

printf("%c",p->data);

while(p->parent!=NULL){/*把編碼存入棧中*/

q=(structstack*)malloc(sizeof(structstack));

q->data=p->sign;

q->next=head;

head=q;

p=p->parent;

}

q=head;/*輸出編碼*/

while(q!=NULL){

printf("%d",q->data);

q=q->next;

}

printf("\n");

}

}

/******************************譯碼******************************/

chartranslate(){

structtree*r,*p,*q;

intn;

charc;

/*讀取01序列*/

Error:printf("\nInputcodesconsistof0and1(endofENTER):\n");

n=getchar();

if(n!='\n'){/*讀取第一個字符*/

p=(structtree*)malloc(sizeof(structtree));

p->data=n;

p->next=NULL;

head=p;

r=head;

n=getchar();

}

while(n!='\n'){/*讀取其它字符*/p=(structtree*)malloc(sizeof(structtree));

p->data=n;

p->next=NULL;

r->next=p;

r=p;

n=getchar();

}

p=head;

while(p!=NULL){/*判斷是否右非法字符*/

if(p->data!='0'&&p->data!='1'){

printf("Thereareilleagecharactersinyourcodes!\n");

gotoError;

}

p=p->next;

}

printf("\nThetextofthecodesis:");

p=head;

q=root;

while(p!=NULL){/*由根到葉遍歷*/

if(q->lchild==NULL&&q->rchild==NULL){/*判斷是否葉節點*/

putchar(q->data);

q=root;

}

else{/*往下遍歷*/

if(p->data=='0')q=q->lchild;

elseq=q->rchild;

if(q->lchild==NULL&&q->rchild==NULL){

putchar(q->data);

q=root;

}

}

p=p->next;

}

printf("\n\nInputcodesagain(y/n)?");/*詢問是否繼續譯碼*/

c=getche();

printf("\n\n");

return(c);/*返回是否繼續的標志*/

}

/******************************主程序*************