大專實(shí)習(xí)報(bào)告

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

節(jié)點(diǎn)；并且在開始，我還用此結(jié)構(gòu)生成了單鏈表，用來存儲(chǔ)讀取的字符。編碼的時(shí)候，我把編碼放在棧結(jié)構(gòu)stack中，然后逆序輸出即為哈夫曼編碼。存放葉節(jié)點(diǎn)時(shí)用到了指針數(shù)組。

structtree(){

chardata;

intm,sign;

structtree*lchild,*rchild,*parent;

}

structstack{

intdata;

structstack*next;

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

#include<conio.h>

structtree{/*定義哈夫曼樹的結(jié)構(gòu)*/

chardata;/*存放字符*/

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

structtree*lchild,*rchild,*parent;/*左兒子右兒子父節(jié)點(diǎn)*/

};

structstack{/*定義棧的結(jié)構(gòu)*/

intdata;

structstack*next;

};

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

/*數(shù)組存放字符root為二叉樹的根結(jié)點(diǎn)head為鏈表的頭節(jié)點(diǎn)*/

intsize;/*標(biāo)志字符個(gè)數(shù)*/

/*************************統(tǒng)計(jì)各字符出現(xiàn)的頻度***********************/

voidfrequency(){

structtree*r,*p,*q;

intn,l,j=1;

/*錄入第一個(gè)字符并創(chuàng)建鏈表*/

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;/*把字符(后面的葉節(jié)點(diǎn))放進(jìn)數(shù)組備份*/

n=getchar();}

/*錄入其它字符*/

while(n!='\n'){

l=0;r=p;

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

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

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;/*把字符(后面的葉節(jié)點(diǎn))放進(jìn)數(shù)組備份*/

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++;/*統(tǒng)計(jì)字符的個(gè)數(shù)*/

}

}

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

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){

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

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為根結(jié)點(diǎn)*/

root->parent=NULL;

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

head=q;

r=head;

e=head;/*把新生成的根結(jié)點(diǎn)插入到鏈表中去*/

if(head->m>t->m){/*判斷是否為頭節(jié)點(diǎn)*/

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;/*如果鏈表為空則結(jié)束*/

}

}

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

voidccode(){

structtree*p,*q;

intj;

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

for(j=0;j<size;j++){/*做size(葉節(jié)點(diǎn)個(gè)數(shù))次循環(huán)*/

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'){/*讀取第一個(gè)字符*/

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){/*判斷是否葉節(jié)點(diǎn)*/

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)?");/*詢問是否繼續(xù)譯碼*/

c=getche();

printf("\n\n");

return(c);/*返回是否繼續(xù)的標(biāo)志*/

}

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