哈弗曼树的建立问题;

static int s1, s2;
typedef struct {
unsigned int weight; //结点的权值
unsigned int parent; //结点的亲
unsigned int lchild; //左孩子
unsigned int rchild; //右孩子
char data;  //数据
} HTnode, *Huffmantree;
typedef char **Huffmancode;

* * *


/*
TODO: 查询两个权值最小的节点，赋值给s1，s2
功能描述：在ht[1]~ht[n]的范围内选择两个parent为0且weight最小的结点，其序号赋值给s1，s2
参数说明：ht-Huffmantree型树
n-int型 表示节点数
返回值说明：无

void selectMin(Huffmantree ht, int n)
{
int min = 0, i;
// 选最小；
for (i = 0; i < n; i++)
{
if ((ht + i)->parent == 0)
{
min = i;
break;
}
}
for (i = 0; i < n; i++)
{
if ((ht + i)->parent == 0)
if ((ht + i)->weight < (ht + min)->weight)
min = i;
}
s1 = min;
//选次小
for (i = 0; i < n; i++)
{
if ((ht + i)->parent == 0 && i != s1)
{
min = i;
break;
}
}
for (i = 0; i < n; i++)
{
if ((ht + i)->parent == 0 && i != s1)
if ((ht + i)->weight < (ht + min)->weight)
min = i;
}
s2 = min;
}

* * *


/*
TODO: 建立哈弗曼树。
功能描述：根据键盘输入创建哈弗曼树，期间调用selectMin函数实现，给生成的父结点的data赋值为减号-，打印输出用以下格式。
printf("%c%4d%4d%4d%4d\n", ht[i].data,ht[i].weight, ht[i].parent, ht[i].lchild,ht[i].rchild);
参数说明：ht-Huffmantree型树
n-int型 表示节点数
w-int型指针 表示权值
d-char型指针 表示节点数据
返回值说明：Huffmantree型树

Huffmantree createHuffmanTree(Huffmantree ht, int *w, int n, char *d) {
int i, m;

// 申请空间；
m = 2 * n-1;
ht = (Huffmantree)malloc(sizeof(HTnode)*m+1); // 从i=1开始写入；
//对n个结点进行初始化 ;
for (i = 1 ; i < n+1 ; i++)
{
(ht + i)->data = d[i-1];
(ht + i)->weight = w[i-1];
(ht + i)->lchild = 0;
(ht + i)->rchild = 0;
(ht + i)->parent = 0;
}
// 对剩余的结点初始化
for (i = n+1; i < m+1; i++)
{
(ht + i)->weight = 0;
(ht + i)->lchild = 0;
(ht + i)->rchild = 0;
(ht + i)->parent = 0;

}
//添加结点；

for (i = n+1; i < m+1; i++)
{
selectMin(ht, i);
(ht + s1)->parent = i;
(ht + s2)->parent = i;

(ht + i)->lchild = s1;
(ht + i)->rchild = s2;
(ht + i)->weight = (ht + s1)->weight + (ht + s2)->weight;  //权重相加；
(ht + i)->data = '-';
}
for(i=1;i<m+1;i++)
printf("%c%4d%4d%4d%4d\n", ht[i].data, ht[i].weight , ht[i].parent, ht[i].lchild, ht[i].rchild);
return ht;
}

* * *

Huffmantree ht = NULL;   //输入一个哈夫曼树型指针；
Huffmancode hc = NULL;   //字符指针；
int *w = NULL;
char *d = NULL;
int i;
int n;
printf("请输入节点数\n");
scanf_s("%d", &n);  //申请空间；
w = (int *)malloc(n * sizeof(int));
d = (char*)malloc(n * sizeof(char));
printf("请输入节点的权值以及字符，先输入权值后输入字符并且两者之间无空格\n");
for (i = 0; i < n; i++) {
scanf_s("%d%c", &w[i], &d[i]);
}
printf("输出哈夫曼树的存储结构\n");

#数据结构C语言##C/C++#