数据结构实验三：树的应用

1、 数据结构 实验报告实验三 树的应用实验目的：1掌握二叉树基本操作；2掌握构造哈夫曼树及哈夫曼编码的方法实验要求：1C完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3写出算法设计小结和心得。实验内容：1采用二叉链表存储结构，编写程序实现按层次遍历二叉树。2从键盘输入若干字符，统计每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出每个字符及对应的哈夫曼编码。一个完整的哈夫曼编码/译码系统应具有以下功能：（1）初始化：从终端读入一段英文字符，统计每个字符出现的频率，建立哈夫曼树；（2）编码：利用建好的哈夫曼树对各

2、字符进行编码，并输出结果（要求输出哈夫曼树存储结构的初态、终态及字符的哈夫曼编码）；（3）译码：利用已建立的哈夫曼编码对输入的字符序列进行译码，并输出结果；（选做）（4）解码：利用哈夫曼编码，对任意输入的0、1序列能正确解码，并输出结果。（选做） 程序源代码：（1）#include stdio.h#include conio.h#include stdlib.htypedef char TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/*创建二叉树*/vo

3、id create(BiTree *T)char c;scanf(%c,&c);if(c!=#) *T=(BiTree)malloc(sizeof(BiTNode); (*T)-data=c; create(&(*T)-lchild); create(&(*T)-rchild);else *T=NULL;/*按层遍历*/void Traverse(BiTree T)BiTree Queue20; BiTree p;int front=0,rear=0;if(T) p=T; Queuerear=p; rear=(rear+1)%20; while(front!=rear) p=Queuefron

4、t; printf(%c,p-data); front=(front+1)%20; if(p-lchild) Queuerear=p-lchild; rear=(rear+1)%20; if(p-rchild) Queuerear=p-rchild; rear=(rear+1)%20; main()BiTree T;create(&T);Traverse(T);getch();（2）#include#include#include#include#include#define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE MAXLEAF*2-1

5、#define MAXBIT 50typedef struct node /*结点类型定义*/ char letter; int weight; int parent; int lchild; int rchild;HNodeType;typedef struct /*编码类型定义*/ char letter; int bitMAXBIT; int start;HCodeType;typedef struct /*输入符号的类型*/ char s; int num;lable;void HuffmanTree(HNodeType HuffNode,int n,lable a) int i,j,

6、m1,m2,x1,x2,temp1; char temp2; for (i=0;i2*n-1;i+) /*结点初始化*/ HuffNodei.letter=0; HuffNodei.weight=0; HuffNodei.parent=-1; HuffNodei.lchild=-1; HuffNodei.rchild=-1; for (i=0;in-1;i+) for (j=i+1;jai.num) temp1=ai.num; ai.num=aj.num; aj.num=temp1; temp2=ai.s; ai.s=aj.s; aj.s=temp2; for (i=0;in;i+) Huff

7、Nodei.weight=ai.num; HuffNodei.letter=ai.s; for (i=0;in-1;i+) /*构造huffman树*/ m1=m2=MAXVALUE; x1=x2=0; for (j=0;jn+i;j+) if (HuffNodej.parent=-1&HuffNodej.weightm1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.parent=-1&HuffNodej.weightm2) m2=HuffNodej.weight; x2=j; HuffNodex1.parent=n

8、+i; HuffNodex2.parent=n+i; HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight; HuffNoden+i.lchild=x1; HuffNoden+i.rchild=x2; void HuffmanCode(int n,lable a) HNodeType HuffNodeMAXNODE; HCodeType HuffCodeMAXLEAF,cd; int i,j,c,p; HuffmanTree(HuffNode,n,a); for (i=0;in;i+) /*按结点位置进行编码*/ cd.start=n-1

9、; c=i; p=HuffNodec.parent; while (p!=-1) if (HuffNodep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=HuffNodec.parent; for (j=cd.start+1;jn;j+) /*储存编码*/ HuffCodei.bitj=cd.bitj; HuffCodei.start=cd.start; for (i=0;in;i+) HuffCodei.letter=HuffNodei.letter; printf( %c ,HuffCodei.l

10、etter); for (j=HuffCodei.start+1;jn;j+) printf(%d,HuffCodei.bitj); printf(n); int main() lable data30; char s100,*p; int i,count=0; for (;) cout / 求哈夫曼编码,输入end结束 /endl; printf( 输入字符:); scanf(%s,s); if (!strcmp(s,end) exit(0); for (i=0;i30;i+) datai.s=0; datai.num=0; p=s; while (*p) /*计算字符个数与出现次数*/ for (i=0;i=count+1;i+) if (datai.s=0) datai.s=*p; datai.num+; count+; break; else if (datai.s=*p) datai.num+; break; p+; printf(n); printf( 不同字符数:%dn,count); for (i=0;icount;i+) printf( %c ,datai.s); printf(weight:%dn,datai.num); HuffmanCode(count,data); count=0; getch();=Word行业资料分享-可编辑版