《算法与数据结构》实验指导书(11)

《算法与数据结构》实验指导书

//*CHAPTER :6 * //*PROGRAM :哈夫曼树 * //*CONTENT :构造哈夫曼树,哈夫曼编码 * //* * * * * * * * * * * * * * * * * * * * * * * * #include <dos.h> #include <conio.h> #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct

{unsigned int weight; //结点权值

unsigned int parent,lchild,rchild; //结点的父指针，左右孩子指针 }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表

void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成一棵哈夫曼树

void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //对哈夫曼树进行编码 void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //显示哈夫曼编码 void Select(HuffmanTree,int,int&,int&); //在数组中寻找权值最小的两个结点 void main()

{HuffmanTree HT; //哈夫曼树HT

HuffmanCode HC; //哈夫曼编码表HC int n,i; //n是哈夫曼树叶子结点数 unsigned int *w; //w存放叶子结点权值 char j='y';

textbackground(3); //设定屏幕颜色 textcolor(15); clrscr(); //程序解说

printf("本程序将演示构造哈夫曼树.\n"); printf("首先输入叶子结点数目.\n例如:8\n"); printf("然后输入每个叶子结点的权值.\n"); printf("例如:5 29 7 8 14 23 3 11\n");

printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n");

printf(" 5---0110\n 29---10\n 7---1110\n 8---1111\n 14---110\n"); printf(" 23---00\n 3---0111\n 11---010\n"); while(j!='N'&&j!='n')

{printf("请输入叶子结点数目:");

scanf("%d",&n); //输入叶子结点数

if(n<=1) {printf("该数不合理!\n");continue;}

w=(unsigned int*)malloc(n*sizeof(unsigned int)); //开辟空间存放权值 printf("请输入各叶子结点的权值:\n");

for(i=0;i<n;i++) scanf("%d",&w[i]); //输入各叶子结点权值 CreateHuffmanTree(HT,w,n); //生成哈夫曼树 HuffmanCoding(HT,HC,n); //进行哈夫曼编码