#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXVALUE 32767
#define NODENUM 8//叶子结点数
typedef struct
{char data;int weight;int parent, lch, rch;
}htNode,*huffmanTree;
typedef char** huffmanCode;
void initHuffmanTree(huffmanTree* HT)
{*HT = (htNode*)malloc(sizeof(htNode) * 2 * NODENUM);//2nif (*HT == NULL){perror("error");exit(1);}//初始化都为-1for (int i = 1; i <= 2 * NODENUM - 1; i++)//n个叶子结点有2n-1个结点{(*HT)[i].parent = (*HT)[i].rch = (*HT)[i].lch = -1;}printf("请输入%d个叶子结点的权值\n", NODENUM);for (int i = 1; i <= NODENUM; i++){scanf("%d", &((*HT)[i].weight));}char c = getchar();//吸收上面scanf残留的换行符printf("请输入data的字母符号,并且换行符结束\n");for (int i = 1; i <= NODENUM; i++){char a = getchar();if (a == '\n'){break;}else{(*HT)[i].data = a;}}
}
void createHuffmanTree(huffmanTree* HT, int n)
{if (n<=1){return;}int min1, min2;int rnode, lnode;for (int i = n + 1; i <= 2 * n - 1; i++){min1 = MAXVALUE, lnode = -1;min2 = MAXVALUE, rnode = -1;for (int j = 1; j <= i - 1; j++){if ((*HT)[j].weight < min1 && (*HT)[j].parent == -1){min2 = min1, rnode = lnode;min1 = (*HT)[j].weight, lnode = j;}else if ((*HT)[j].weight < min2 && (*HT)[j].parent == -1){min2 = (*HT)[j].weight;rnode = j;}}(*HT)[lnode].parent = (*HT)[rnode].parent = i;(*HT)[i].lch = lnode, (*HT)[i].rch = rnode;(*HT)[i].weight = (*HT)[lnode].weight + (*HT)[rnode].weight;}
}
void createHuffmanTreeCode(huffmanTree HT, huffmanCode* HC, int n)//HC三级
{*HC = (char**)malloc(sizeof(char*) * n + 1);//0号单元不使用,给HC分配十个空间，一个空间里面又是一个小数组，这个小数组在下面根据宽度申请空间if (*HC == NULL){perror("error");exit(1);}char* cd = (char*)malloc(sizeof(char) * n);//临时存放的十个空间的字符数组if (cd == NULL){perror("error");free(*HC);//cd开辟失败就把HC也关闭exit(1);}int start = 0;//作为临时数组的下标索引int c = 0;//根据i的数值去定位下标权值weight i = 1 对于权值第一位的是5int f = 0;//代表双亲parentcd[n - 1] = '\0';for (int i = 1; i <= n; i++){start = n - 1;//因为从叶子结点到根结点，所以存放在临时数组的0和1要在临时数组中倒着放c = i;//c不是真的为1，是1对于的下标权值weight这里切记f = HT[c].parent;//f为c对应的parent，单单对应parent的数字就行，不要去对标这个parent的权值while (f!=-1){start--;//上面的start = n-1是对应\0的位置，需要再往后一格if (HT[f].lch == c){cd[start] = '0';}else {cd[start] = '1';}//不断网上走，直到根节点c = f;f = HT[c].parent;}(*HC)[i] = (char*)malloc(sizeof(char) * (n - start));if ((*HC)[i] == NULL){perror("error");return;}strcpy((*HC)[i], &cd[start]);}free(cd);
}
int main()
{huffmanTree HT = NULL;//一级//初始化initHuffmanTree(&HT);huffmanCode HC;createHuffmanTree(&HT, NODENUM);createHuffmanTreeCode(HT, &HC, NODENUM);//输出编码for (int i = 1; i <= NODENUM; i++){printf("%c:\t", HT[i].data);printf("%s\n", HC[i]);}return 0;
}