数据结构上机实验 树和二叉树的应用 哈夫曼编码设计 (含代码和报告).doc

数据结构上机实验_树和二叉树的应用_哈夫曼编码设计 (含代码和报告)数据结构实验报告
题目:数据结构实验报告
学院:工商管理学院
班级:信息1001
姓名:彭振宇
学号:
时间:2012/6/26
实验三:树和二叉树的应用
实验题目:树和二叉树的应用
实验内容:哈夫曼编码设计
:掌握树和二叉树的概念及工作原理,运用其原理及概念完成上述实验题中的内容。
:为了使学生更好的掌握与理解课堂上老师所讲的概念与原理,实验前每个学生要认真预****所做的实验内容及编写源程序伪码(写在纸上及盘中均可)以便在实验课中完成老师所布置的实验内容。
:
。其序号分别为s1和s2




:
#include<>
#include<>
#include<>
#define MAXSIZE 30 //最大叶子数
#define MAXCODE 10000 //编码最大长度
#define OK 1
#define ERROR 0
#define OVERLOW -2
//=============赫夫曼树和赫夫曼编码的存储表示=====
typedef struct
{
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树
typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表

/*----------------算法描述----------------*/
void Select(HuffmanTree HT, int n, int *s1, int *s2)
//选择parent为0且weight最小的两个结点。其序号分别为s1和s2
{
int minsum = ;
int i,j;
for(i=1; i<=n; i++)
{
if(HT[i].parent)
continue;
for(j=i+1; j<=n; j++)
{
if(HT[j].parent)
continue;
if(HT[i].weight + HT[j].weight < minsum)
{
minsum = HT[i].weight + HT[j].weight;
*s1 = i;
*s2 = j;
}
}
}
}
void CreateHuffmanTree(HuffmanTree &HT, int *w, int n)
{//建立赫夫曼树叶
int m, s1, s2, i;
if(n <= 1)
return;
m = 2*n-1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
for( i = 1; i <= n; i++, ++w)
{
HT[i].weight = *w;