数据结构实验一线性表-数据结构实验报告-_第1页
数据结构实验一线性表-数据结构实验报告-_第2页
数据结构实验一线性表-数据结构实验报告-_第3页
数据结构实验一线性表-数据结构实验报告-_第4页
数据结构实验一线性表-数据结构实验报告-_第5页
已阅读5页,还剩4页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构实验一线性表-[数据结构实验报告]-第第页数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第1页。数据结构实验一线性表[数据结构实验报告]数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第1页。

数据结构试验报告

题目与内容

哈夫曼(Huffman)树与哈夫曼码

输入一个文本,统计各字符出现的频度,输出结果:

使用二叉链表或三叉链表作存储结构,构造哈夫曼

(Huffman)树;

确定和输出各字符的哈夫曼码;

输入一个由0和1组成的代码序列,翻译并输出与之对应的文本;

二、数据结构及存储结构

在这个程序中我用了三叉链表tree作为哈夫曼树的结

构:左、右儿子和父亲

节点;并且在开始,我还用此结构生成了单链表,用来

存储读取的字符。编码的时候,我把编码放在栈结构stack

中,然后逆序输出即为哈夫曼编码。存放叶节点时用到了指针数组。

structtree(){

chardata;

intm,sign;

structtree*lchild,*rchild,*parent;

}

structstack{

intdata;

structstack*next;

}

算法设计思想

先调用frequency函数读取字符,创建链表来存储字符及其相关信息;同时把字符放进数组中进行备份,因为后面编码时要用到这些字符〔它们就是叶节点〕。然后遍历这个链表输出个字符的频度。接着调用ctree函数来生成哈夫曼

树。在ctree函数中,首先对刚刚那个链表根据频度排序,变成频度递增链表;然后取其前两个节点作为新建哈夫曼树的左右儿子〔注:左数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第2页。儿子的频度心得体会

这次编程,从开始编到测试胜利,我一共花了四天。

这主要是因为之前我花了不少时间看书,把数据结构和存储结构都想好了,还看了大虽程序,不管是相关还是不相关的。

例如,有一个困扰我很久的问题:当询问是否继续时,输入y就继续,否则跳出;以前用getchar要等按了回车才进行判断,假如按了好几个y,则后面几个y被当成以后的输入处理了,这样就会出错。然而我在一个程序中看到了getche

这个指令解决了这个问题,它不需等回车就进行处理。另外在定义哈夫曼树结构时,我加了个sign变虽来标志它是左

子树还是右子树,这样后面编码时就很方便。这次编程使我认识到:要重视详情,虽然很小,但是它会使程序不能运行

或出错。这个程序中我由于把y写成y,结果浪费了我半天的时间去查错。

五、程序清单

)

或右⑴儿子的标志*/

structtree*lchild,*rchild,*parent;/*左儿子右

儿子父节点*/

};

structstack(/*定义栈的结构*/

intdata;

structstack*next;

};

structtree*ps,*root,*head;

/*数组存放字符root为二叉树的根结点head为链表

*/

intsize;/*标志字符个数*/

/*************************统计各字符出现的频度

/*************************

统计各字符出现的频度

***********************

数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第3页。voidfrequency()(

structtree*r,*p,*q;

intn,l,j=1;

/*录入第一个字符并创建链表*/

clrscr();/*清屏*/

head=NULL;

printf(InputthetextendofENTER:);

n=get);

if(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=p;/*把字符(后面的叶节点)放进数组备份*/

n=get);

}

/*录入其它字符*/

while(n!=){

l=O;r=p;

for(q=head;q!=NULLl==0;q=q-parent){if(q-data==n){/*检查是否和已经录入的字符相同

q-m++;/*假如相同则此字符的频度变虽加1*/

1=1;

)

r=p;

)

if(l==O){/*假如不同则录入并加入链表*/

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

数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第4页。p-data=n;

p-m=1;

p-sign=-1;

p-lchild=NULL;

p-rchild=NULL;

p-parent=NULL;

r-parent=p;

ps=p;/*把字符(后面的叶节点)放进数组备份*/

j++;

)

n=get);

}

/*输出字符的频度*/

p=head;

size=0;

printf(Frequencyasfollows:characters

frequency);

while(p!=NULL){

printf(%c%d〞,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-mq-m){

数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第5页。n=q-m;/*交换信息*/

p-m=n;

n=q-data;

q-data=p-data;

p-data=n;

}

}

}

/***********生成哈夫曼树***********/

p=head;

while(p!=NULLp-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-mt-m){/*推断是否为头节点*/

t-parent=q;

head=t;

}

数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第6页。else{

r=r-parent;

while(r!=NULLr-mm){

e=r;

r=r-parent;

}

t-parent=r;

e-parent=t;

}

p=head;

root=t;

}

elsebreak;/*假如链表为空则结束*/

/******************************

******************************

voidccode()(

structtree*p,*q;

intj;

printf(codesasfollows:characterscode);

for(j=0;j

head=NULL;

p=ps;/*从叶到根求编码*/

printf(%c〞,p-data);

while(p-parent!=NULL){/*把编码存入栈中1*/

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

q-data=p-sign;

q-next=head;

head=q;

p=p-parent;

}

q=head;/*输出编码*/

while(q!=NULL){

数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第7页。printf(%d,q-data);

q=q-next;

}

printf();

}

}

/******************************

******************************

chartranslate()(

structtree*r,*p,*q;

intn;

charc;

/*读取01序列*/

Error:printf(Inputcodesconsistof0and1(endofENTER):);

n=get);

if(n!=){/*读取第一个字符*/

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

p-data=n;

p-next=NULL;

head=p;

r=head;

n=get);

}

while(n!=)(/*读取其它字符*/

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

p-data=n;

p-next=NULL;

r-next=p;

r=p;

n=get);

}

p=head;

数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第8页。while(p!=NULL){/*推断是否右非法字符*/

if(p-data!=0p-data!=1){

printf(Thereareilleagecharactersinyourcodes!);

gotoError;

}

p=p-next;

}

printf(Thetextofthecodesis:);

p=head;

q=root;

推断是while(p!=NULL){/*由根到叶遍历*/if(q-lchild==NULLq-rchild==NULL){/*

推断是

否叶节点*/

putq-data);

q=root;

}

else{/*往下遍历*/

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

elseq=q-rchild;

if(q-lchild==NULLq-rchild==NULL){

putq-data);

q=root;

}

}

p=p-next;

}

printf(Inputcodesagain(y/n)?〞);/*询问是否

继续译码*/

c=getche();

printf();

return(c);/*返回是否继续的标志*/

数据结构实验一线性表-[数据结构实验报告]-全文共9页,当前为第9页。}

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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论