#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
typedef struct
{
int weight;
int parent, lch, rch;
}HTNode,*HuffmanTree;
int j = 0;
int k = 0;
int cmp(const void* a, const void* b)
{
return *(int*)a - *(int*)b;
}
int Select(HuffmanTree HT, int n)
{
int p = 0; //用于控制数组arr，按顺序存储数据
int arr[MAX_SIZE] = { 0 };
int count = 0;
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0 && HT[i].weight != 0)
{
arr[p++] = HT[i].weight;
count++;
}
}
qsort(arr, count, sizeof(int), cmp);
for (int i = 1; i <= n; i++)
{
if (HT[i].weight == arr[0]) //arr[0]是最小元素
{
j = i;
break;
}
}
for (int i = 1; i <= n; i++)
{
if (HT[i].weight == arr[1] && i != j)
{
k = i;
break;
}
}
return 0;
}
void CreatHuffmanTree(HuffmanTree HT, int n)
{
int m = 2 * n - 1;
HT = (HTNode*)malloc(sizeof(HTNode) * (m + 1));
for (int i = 1; i <= m + 1; i++)
{
HT[i].lch = 0;
HT[i].rch = 0;
HT[i].parent = 0;
HT[i].weight = 0;
}
for (int i = 1; i <= n; i++)
{
int input = 0;
printf("请输入每个元素的权值:>");
scanf("%d", &input);
HT[i].weight = input;
}
//开始创建哈夫曼树
for (int i = 1; i < n; i++)
{
Select(HT, m + 1);
HT[n + i].lch = j;
HT[n + i].rch = k;
HT[n + i].weight = HT[j].weight + HT[k].weight;
HT[j].parent = n + i;
HT[k].parent = n + i;
}
for (int i = 1; i <= m; i++)
{
printf("i:%d\tweight:%d\tparent:%d\tlch:%d\trch:%d\n", i,HT[i].weight, HT[i].parent, HT[i].lch, HT[i].rch);
}
}
int main()
{
HuffmanTree HT = 0;
CreatHuffmanTree(HT, MAX_SIZE);
return 0;
}
