基于c语言实现哈夫曼树赫夫曼树

# 赫夫曼编码 ## 实验目的 ​ 构建所输入符号（及权值）的赫夫曼树，并利用该树求出各符号的编码，深入理解最优二叉树的概念及其特性。 ## 实验内容 ​ 读入各个符号及其权值，建立哈夫曼树；利用建立的哈夫曼树对各符号进行编码，输出编码结果。 ## 设计过程和算法描述 ```c++ # define MAX 10 # include<stdio.h> # include<stdlib.h> typedef int ElemType; # include<stdio.h> # include<string.h> # include<malloc.h> # include<stdlib.h> # define Max 1000 # define N 8 /*权值*/ # define M 2*N-1 /*结点*/ typedef char elemtype; typedef struct { elemtype data; int weight; int parent; int lchild; int rchild; } huffnode; typedef struct { char cd[N]; int start; char ch; } huffcode; huffnode ht[M + 1]; huffcode hcd[N + 1]; char zifu[N] = { '\0' }; void creat()/*构造哈夫曼树*/ { int x, i, j, p1, p2, min1, min2; for (i = 1; i <= M; i++) { ht[i].weight = 0; ht[i].parent = 0; ht[i].lchild = 0; ht[i].rchild = 0; } printf("输入%d个字符的权值:\n", N); for (i = 1; i <= N; i++) { scanf("%d", &x); ht[i].weight = x; } printf("输入%d个字符:\n", N); scanf("%s", zifu); for (i = N + 1; i <= M; i++) { = 1; p2 = 1; min1 = Max; min2 = Max; for (j = 1; j <= i - 1; j++) { if (ht[j].parent == 0) { if (ht[j].weight<min1) { min2 = min1; = p1; min1 = ht[j].weight; = j; } else if (ht[j].weight<min2) { min2 = ht[j].weight; = j; } } } ht[i].weight = ht[p1].weight + ht[p2].weight; ht[i].lchild = p1; ht[i].rchild = p2; ht[p1].parent = i; ht[p2].parent = i; } } int menu(void) //菜单函数 { int menu; system("cls"); printf("\n\t\t\t********主菜单********\n"); printf("\n\t\t\t 1.构造哈夫曼树\n"); printf("\t\t\t 2.求哈夫曼编码\n"); printf("\t\t\t 3.输出哈夫曼编码\n"); printf("\t\t\t 0.退出程序\n"); printf("\n\t\t\t**********************\n"); do { printf("\t\t\t请选择:"); scanf("%d", &menu); } while (menu<0 || menu>3); return(menu); } void huffman() { int i, c, p; for (i = 1; i <= N; i++) { hcd[i].start = N; = i; = ht[i].parent; while (p != 0) { hcd[i].start--; if (ht[p].lchild == c) hcd[i].cd[hcd[i].start] = '0'; else hcd[i].cd[hcd[i].start] = '1'; = p; = ht[p].parent; } } for (i = 1; i <= N; i++) hcd[i].ch = zifu[i - 1]; } void print1() { int z; for (z = 1; z <= M; z++) printf("%c,%d,%d,%d,%d\n", ht[z].data, ht[z].weight, ht[z].parent, ht[z].lchild, ht[z].rchild); printf("\n\t按任意键继续"); getch(); } void print() { int i, j; printf("各字符的哈夫曼编码为:\n"); for (i = 1; i <= N; i++) { printf("%c:", hcd[i].ch); for (j = hcd[i].start; j<N; j++) printf("%c", hcd[i].cd[j]); printf("\n"); } printf("\n\t按任意键继续"); getch(); } void main() { int select = 0; do { select = menu(); switch (select) { case 1: creat(); break; case 2: huffman(); break; case 3: print(); break; } } while (select != 0); } ``` 实验结果分析（30 分）     ## 总结 ​ 这次实验遇到了一些困难，输入的字符无法传递到编码的函数中，输出值错误等等，通过逐段的调试和修改，最后解决了问题。学到了哈夫曼树的构造方法及其用代码是如何实现的，也锻炼了我的程序纠错能力，收获很多。