#include <stdio.h>#include <malloc.h>#include <string.h>#define MAXINT 32767 typedef char** HuffmanCode;typedef struct { int parent; int lch, rch,weight;}HuffmanNode, * HuffmanTree;
void Select(HuffmanTree ht, int n, int* s1, int* s2) { int i, min1 = MAXINT, min2 = MAXINT; *s1 = 0; *s2 = 0; for (i = 1; i <= n; i++) { if (ht[i].parent == 0) { if (ht[i].weight < min1) { min2 = min1; *s2 = *s1; min1 = ht[i].weight; *s1 = i; } else if (ht[i].weight < min2) { min2 = ht[i].weight; *s2 = i; } } }}void CreatHuffTree(HuffmanTree& HT, int n){ int m = 2 * n - 1; HT = (HuffmanTree)malloc((m + 1) * sizeof(HuffmanNode)); printf("请输入n个元素得权值"); int sum; for (int i = 1; i <= n; i++) { scanf("%d", &sum); HT[i].weight = sum; HT[i].lch = 0; HT[i].parent = 0; HT[i].rch = 0; } for (int i = n + 1; i <= m; i++) { HT[i].lch = 0; HT[i].parent = 0; HT[i].rch = 0; HT[i].weight = 0; } int x1, x2; for (int i = n + 1; i <= m; i++) { Select(HT, i - 1, &x1, &x2); HT[x1].parent = i; HT[x2].parent = i; HT[i].lch = x1; HT[i].rch = x2; HT[i].weight = HT[x1].weight + HT[x2].weight; }}void CreatHuffmancode(HuffmanTree HT, HuffmanCode& HC, int n){ HC = (HuffmanCode)malloc((n + 1) * sizeof(char*)); char* cd; cd = (char*)malloc(n * sizeof(char)); cd[n - 1] = '\0'; int start; int c, f; for (int i = 1; i <= n; i++) { int start = n - 1; c = i; f = HT[i].parent; while (f != 0) { --start; if (HT[f].lch == c) cd[start] = '0'; else cd[start] = '1'; c = f; f = HT[f].parent; } HC[i] = (char*)malloc((n - start) * sizeof(char)); strcpy(HC[i], &cd[start]); } free(cd);}int main(){ HuffmanTree HT; HuffmanCode HC; printf("请输入元素个数:"); int n; scanf("%d", &n); CreatHuffTree(HT, n); printf("Weigth Lchild Rchild Parent \n"); for (int i = 1; i <= 2 * n - 1; i++) { printf("%-7d%-7d%-7d%-20d", HT[i].weight, HT[i].lch, HT[i].rch, HT[i].parent); printf("\n"); } CreatHuffmancode(HT, HC, n); for (int i = 1; i <= n; i++) { printf("%c的编码为：", 'A' + i-1); printf("%s",HC[i]); printf("\n"); } return 0;}
评论