数据结构实验报告.docx

1、数据结构实验报告数据结构实验报告题目与内容 哈夫曼(Huffman)树与哈夫曼码 1.输入一个文本，统计各字符出现的频度，输出结果; 2.使用二叉链表或三叉链表作存储结构，构造哈夫曼(Huffman)树; 3.确定和输出各字符的哈夫曼码; 4.输入一个由0和1组成的代码序列，翻译并输出与之对应的文本; 二、 数据结构及存储结构 在这个程序中我用了三叉链表tree作为哈夫曼树的结构：左、右儿子和父亲 节点;并且在开始，我还用此结构生成了单链表，用来存储读取的字符。编码的时候，我把编码放在栈结构stack中，然后逆序输出即为哈夫曼编码。存放叶节点时用到了指针数组。 struct tree() ch

2、ar data; int m,sign; struct tree *lchild,*rchild,*parent; struct stack int data; struct stack *next; 算法设计思想 先调用frequency函数读取字符，创建链表来存储字符及其相关信息;同时把字符放进数组中进行备份，因为后面编码时要用到这些字符(它们就是叶节点)。然后遍历这个链表输出个字符的频度。接着调用ctree函数来生成哈夫曼树。在ctree函数中，首先对刚才那个链表按照频度排序，变成频度递增链表;然后取其前两个节点作为新建哈夫曼树的左右儿子(注：左儿子的频度心得体会 这次编程，从开始编到测

3、试成功，我一共花了四天。这主要是因为之前我花了不少时间看书，把数据结构和存储结构都想好了，还看了大量程序，不管是相关还是不相关的。例如，有一个困扰我很久的问题：当询问是否继续时，输入y就继续，否则跳出;以前用getchar要等按了回车才进行判断，如果按了好几个y，则后面几个y被当成以后的输入处理了，这样就会出错。然而我在一个程序中看到了getche这个指令解决了这个问题，它不需等回车就进行处理。另外在定义哈夫曼树结构时，我加了个sign变量来标志它是左子树还是右子树，这样后面编码时就很方便。这次编程使我认识到：要重视细节，虽然很小，但是它会使程序不能运行或出错。这个程序中我由于把y写成y，结果

4、浪费了我半天的时间去查错。 五、 程序清单 #include #include struct tree /*定义哈夫曼树的结构*/ char data; /*存放字符*/ int m,sign; /*m存放字符出现的频率 sign是左(0)或右(1)儿子的标志*/ struct tree *lchild,*rchild,*parent; /*左儿子 右儿子 父节点*/ ; struct stack /*定义栈的结构*/ int data; struct stack *next; ; struct tree * ps,*root,*head; /*数组存放字符 root为二叉树的根结点 head

5、为链表的头节点*/ int size; /*标志字符个数*/ /*统计各字符出现的频度*/ void frequency() struct tree *r,*p,*q; int n,l,j=1; /*录入第一个字符并创建链表*/ clrscr(); /*清屏*/ head=NULL; printf(Input the text end of ENTER: ); n=get); if(n!= ) p=(struct tree*)malloc(sizeof(struct tree); p-data=n; p-m=1; p-sign=-1; p-lchild=NULL; p-rchild=NULL;

6、 p-parent=NULL; head=p; ps=p; /*把字符(后面的叶节点)放进数组备份*/ n=get); /*录入其它字符*/ 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) /*如果不同则录入并加入链表*/ p=(struct tree*)malloc(sizeof(struct tree); p-data=n; p-m=1; p-sign=-1; p-lchild

7、=NULL; p-rchild=NULL; p-parent=NULL; r-parent=p; ps=p; /*把字符(后面的叶节点)放进数组备份*/ j+; n=get); /*输出字符的频度*/ p=head; size=0; printf( Frequency as follows: characters frequency ); while(p!=NULL) printf(%c %d ,p-data,p-m); p=p-parent; size+; /*统计字符的个数*/ /*生成树*/ void ctree() struct tree *t,*r,*p,*e,*q; int n;

8、/*给链表排序生成频度递增链表*/ for(p=head;p-parent!=NULL;p=p-parent) for(q=p-parent;q!=NULL;q=q-parent) if(p-mq-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=(struct tree*)malloc(

9、sizeof(struct tree); 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-

10、parent=q; head=t; else r=r-parent; while(r!=NULL&r-m m) e=r; r=r-parent; t-parent=r; e-parent=t; p=head; root=t; else break; /*如果链表为空则结束*/ /*编码*/ void ccode() struct tree *p,*q; int j; printf( codes as follows: characters code ); for(j=0;j head=NULL; p=ps; /*从叶到根求编码*/ printf(%c ,p-data); while(p-par

11、ent!=NULL) /*把编码存入栈中*/ q=(struct stack *)malloc(sizeof(struct stack); 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( ); /*译码*/ char translate() struct tree *r,*p,*q; int n; char c; /*读取01序列*/ Error: printf( Input codes consist of

12、0 and 1 (end of ENTER): ); n=get); if(n!= ) /*读取第一个字符*/ p=(struct tree*)malloc(sizeof(struct tree); p-data=n; p-next=NULL; head=p; r=head; n=get); while(n!= ) /*读取其它字符*/ p=(struct tree*)malloc(sizeof(struct tree); p-data=n; p-next=NULL; r-next=p; r=p; n=get); p=head; while(p!=NULL) /*判断是否右非法字符*/ if(

13、p-data!=0&p-data!=1) printf(There are illeage characters in your codes! ); goto Error; p=p-next; printf( The text of the codes is:); p=head; q=root; while(p!=NULL) /*由根到叶遍历*/ if(q-lchild=NULL&q-rchild=NULL) /*判断是否叶节点*/ putq-data); q=root; else /*往下遍历*/ if(p-data=0) q=q-lchild; else q=q-rchild; if(q-

14、lchild=NULL&q-rchild=NULL) putq-data); q=root; p=p-next; printf( Input codes again(y/n)?); /*询问是否继续译码*/ c=getche(); printf( ); return(c); /*返回是否继续的标志*/ /*主程序*/ void main() char c,a; do frequency(); ctree(); ccode(); c=translate(); /*translate子函数返回值赋给c*/ for(;c=y|c=Y;) /*判断是否继续译码*/ c=translate(); printf( Input text again(y/n)?); a=getche(); while(a=y|a=Y); /*判断是否循环*/ clrscr(); get);