大专实习报告

四川航天职业技术学院《计算机软件技术基础》实习报告书专业：电子工程准考证号：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);/*返回是否继续的标志*/

}

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