数据结构实验报告Word文件下载.docx
- 文档编号:163206
- 上传时间:2023-04-28
- 格式:DOCX
- 页数:8
- 大小:17.32KB
数据结构实验报告Word文件下载.docx
《数据结构实验报告Word文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告Word文件下载.docx(8页珍藏版)》请在冰点文库上搜索。
然后遍历这个链表输出个字符的频度。
接着调用ctree函数来生成哈夫曼树。
在ctree函数中,首先对刚才那个链表按照频度排序,变成频度递增链表;
然后取其前两个节点作为新建哈夫曼树的左右儿子(注:
左儿子的频度 心得体会
这次编程,从开始编到测试成功,我一共花了四天。
这主要是因为之前我花了不少时间看书,把数据结构和存储结构都想好了,还看了大量程序,不管是相关还是不相关的。
例如,有一个困扰我很久的问题:
当询问是否继续时,输入y就继续,否则跳出;
以前用getchar要等按了回车才进行判断,如果按了好几个y,则后面几个y被当成以后的输入处理了,这样就会出错。
然而我在一个程序中看到了getche这个指令解决了这个问题,它不需等回车就进行处理。
另外在定义哈夫曼树结构时,我加了个sign变量来标志它是左子树还是右子树,这样后面编码时就很方便。
这次编程使我认识到:
要重视细节,虽然很小,但是它会使程序不能运行或出错。
这个程序中我由于把‘y’写成y,结果浪费了我半天的时间去查错。
五、程序清单
#include
structtree{/*定义哈夫曼树的结构*/
/*存放字符*/
/*m存放字符出现的频率sign是左(0)或右
(1)儿子的标志*/
/*左儿子右儿子父节点*/
};
structstack{/*定义栈的结构*/
structtree*ps,*root,*head;
/*数组存放字符root为二叉树的根结点head为链表的头节点*/
intsize;
/*标志字符个数*/
/*************************统计各字符出现的频度***********************/
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;
m=1;
sign=-1;
lchild=NULL;
rchild=NULL;
parent=NULL;
head=p;
ps=p;
/*把字符(后面的叶节点)放进数组备份*/
/*录入其它字符*/
while(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){/*如果不同则录入并加入链表*/
r->
parent=p;
j++;
/*输出字符的频度*/
p=head;
size=0;
Frequencyasfollows:
charactersfrequency"
while(p!
=NULL){
%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->
for(q=p->
if(p->
m>
q->
m){
n=q->
m;
/*交换信息*/
m=p->
m=n;
data;
data=p->
/***********生成哈夫曼树***********/
/*取递增链表前两个为左右儿子生成哈夫曼树*/
q=p->
parent->
/*然后把它们从链表中删掉*/
t=(structtree*)malloc(sizeof(structtree));
t->
lchild=p;
/*频度:
左儿子 t->
rchild=p->
m+p->
rchild->
parent=t;
sign=1;
lchild->
sign=0;
root=t;
/*root为根结点*/
root->
if(q!
=NULL){/*判断链表是否为空*/
head=q;
r=head;
e=head;
/*把新生成的根结点插入到链表中去*/
if(head->
t->
m){/*判断是否为头节点*/
parent=q;
head=t;
else{
r=r->
while(r!
r->
mm){
e=r;
parent=r;
e->
elsebreak;
/*如果链表为空则结束*/
/******************************编码******************************/
voidccode(){
structtree*p,*q;
intj;
codesasfollows:
characterscode"
for(j=0;
j
p=ps;
/*从叶到根求编码*/
%c"
data);
while(p->
=NULL){/*把编码存入栈中*/
q=(structstack*)malloc(sizeof(structstack));
sign;
next=head;
q=head;
/*输出编码*/
while(q!
%d"
q->
q=q->
next;
/******************************译码******************************/
chartranslate(){
charc;
/*读取01序列*/
Error:
printf("
Inputcodesconsistof0and1(endofENTER):
){/*读取第一个字符*/
next=NULL;
){/*读取其它字符*/
next=p;
=NULL){/*判断是否右非法字符*/
data!
0'
1'
Thereareilleagecharactersinyourcodes!
gotoError;
Thetextofthecodesis:
"
q=root;
=NULL){/*由根到叶遍历*/
lchild==NULL&
rchild==NULL){/*判断是否叶节点*/
putq->
else{/*往下遍历*/
data=='
)q=q->
lchild;
elseq=q->
rchild;
rchild==NULL){
Inputcodesagain(y/n)?
/*询问是否继续译码*/
c=getche();
return(c);
/*返回是否继续的标志*/
/******************************主程序******************************/
voidmain(){
charc,a;
do{
frequency();
ctree();
ccode();
c=translate();
/*translate子函数返回值赋给c*/
for(;
c=='
y'
||c=='
Y'
;
){/*判断是否继续译码*/
Inputtextagain(y/n)?
a=getche();
while(a=='
||a=='
/*判断是否循环*/
get);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)