Question

紧急！数据结构课程设计 题目：哈夫曼树的建立（由键盘输入各个节点，并建立二叉树，能实现对二叉树的查询

数据结构课程设计 题目：哈夫曼树的建立（由键盘输入各个节点，并建立二叉树，能实现对二叉树的查询、插入、删除操作，构造其哈夫曼树）

内容 设计要求：
1．核心数据结构用到的结构体要采用动态内存分配和链表结构。
2．使用文件进行存储和管理。程序启动时可从文件中读取信息，或从键盘输入信息，可先建立二叉树，然后构造其哈夫曼树，有兴趣的同学可以将树直接画在显示屏幕上。
3．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。
4．对系统进行功能模块分析、画出总流程图和各模块流程图。
5．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。
6．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。
7．所有程序需调试通过

Answer 1

WPL=sigma(f(i)*t(i))最小
i in {1..n}
f(i) 频率 or 频数
t(i) 节点i的深度
首先，哈夫曼树是带权路径长度最小的二叉树，用途是平均查找信息的代价最小。
普通二叉树的用途也普通，比较通用，就是信息存储和查找。
普通二叉树可能有的只有一个子节点，而哈夫曼树一定有两个。

二叉树具有以下重要性质：
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
证明：用数学归纳法证明：
归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。
归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。
归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。

性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故命题正确。

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：
n=no+n1+n2 (式子1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1

满二叉树和完全二叉树是二叉树的两种特殊情形。
1、满二叉树(FullBinaryTree)
一棵深度为k且有2k-1个结点的二又树称为满二叉树。
满二叉树的特点：
（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
【例】图(a)是一个深度为4的满二叉树。

2、完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
特点：
（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
【例】如图(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。
【例】图(b)是一棵完全二叉树。

性质4 具有n个结点的完全二叉树的深度为

证明：设所求完全二叉树的深度为k。由完全二叉树定义可得：
深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：
n>2k-1-1。
另一方面，由性质2可得：
n≤2k-1，
即：2k-1-l<n≤2k-1
由此可推出：2k-1≤n<2k，取对数后有：
k-1≤lgn<k
又因k-1和k是相邻的两个整数，故有
,
由此即得：

注意：
的证明【参见参考书目】

Answer 2

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define N 20
#define M 2*N-1
char * cd;

typedef char *Huffmancode[N+1];
typedef struct
{
int weight;
int parent;
int LChild;
int RChild;
char c;
}HTNNOde,HuffmanTree[M+1];

void select(HuffmanTree p,int k,int *i,int *j)
{
int m,n=1;
while((n<=k)&&p[n].parent!=0) //寻找双亲节点为空的起始节点
{
n++;
}
m=p[n].weight;
*i=n;
while(n<=k) //找最小的值
{
if(p[n].weight<m&&p[n].parent==0)
{
*i=n;
m=p[n].weight;
}
n++;
}
n=1;
while((n<=k&&p[n].parent!=0)||n==(*i))
{
n++;
}
m=p[n].weight;
*j=n;
while(n<=k) //找次小的值
{
if(p[n].weight<m&&n!=*i&&p[n].parent==0)
{
*j=n;
m=p[n].weight;

}
n++;
}
if(*i>*j)
{
n=*i;
*i=*j;
*j=n;
}

}

void creatHuffmanTree(HuffmanTree ht,int w[],int n)
{
int m=2*n-1,i,s1,s2;
for(i=1;i<=n;i++)
{
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}

for(i=n+1;i<=m;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
// printf("%d\n",ht[i].weight);
}
for(i=n+1;i<=m;i++)
{
select(ht,i-1,&s1,&s2); /*ht前i-1项选双亲为零且权最小的两结点*/
// printf("%d,%d\n",s1,s2);
ht[i].weight=ht[s1].weight+ht [s2].weight;
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].LChild=s1;
ht[i].RChild=s2;

// printf("%d\n",ht[i].weight);
}
// i=1;

/* while(i<=9)
{printf("%d\n",ht[i].weight);
i++;}
*/
}

void CrtHuffmanCode(HuffmanTree ht,Huffmancode hc,int n,char w[N][20])
{
int i,p,c;
int start,j=1;
// char w[20][20];
cd=(char *)malloc(n*sizeof(char ));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{ start=n-1;
c=i;
p=ht[i].parent;
while ( p!=0)
{
--start;
if(ht[p].LChild == c)
cd[start]='0';
else cd[start]='1';
c=p;
p=ht[p].parent;
}

hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(hc[i],&cd[start]);
strcpy(w[j],hc[i]);
j++;
printf("%s\n",hc[i]);//实验性打印
}
}
void translationhuffman(char w[N][20],HuffmanTree ht,int n)
{
char litter[20];int i;char yes_no;
do
{
printf("输入哈夫曼编码编码\n");
scanf("%s",litter);

for(i=1;i<=n;i++)
if(strcmp(litter,w[i])==0)
{
printf("该密码对应的字母\n");
printf("%c",ht[i].c);
break;
}
if(i==n+1)
printf("无该密码对应字母\n");
printf(" \n要继续译码吗（Y/N）\n");
do
{
yes_no=getchar();
}while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');
}while(yes_no!='N'&&yes_no!='n');

}
main()
{

HuffmanTree ht;
Huffmancode hc;
int i,n;
int h[50];char w[N][20];
printf("请输入节点总个数");
scanf("%d",&n);
printf("请输入哈夫曼树权值和对应字母\n");
for(i=1;i<=n;i++)
scanf("%d %c",&h[i],&ht[i].c);
creatHuffmanTree(ht,h,n);
/* i=1;
while(i<=9)
{printf("%d\n",ht[i].weight);
i++;}*/
CrtHuffmanCode(ht,hc,n,w);
translationhuffman(w,ht,n);

}这是除过查询以外的所有功能都包含了，包括编码和译码，其余的你自己可以添加的，我调试过，没一点问题的

Answer 3

还是自己做吧，老师布置的课程设计都是网上很难找到的，跟数学建模差不多。题目难，解法难。

Answer 4

需要的话留下邮箱，我这里有一份哈夫曼树的课程设计。 基本满足你的要求~

Answer 5

这个是课程设计的考核作业，估计有些长度喽。