华科数据结构实验

数据结构课程设计 哈夫曼编码和译码的实现 - 2 - #include #include #include #include #define MAXNUM 100 /*哈夫曼结点的结构*/ typedef struct char data; int weight; int parent; int lchild; int rchild; HuffNode; /*哈夫曼编码存储结构*/ typedef struct int cdMAXNUM;/存放 HUFFMAN 编码的数组 int begin; HuffCode; /*哈夫曼树的构造函数*/ int HuffmanCreate(HuffNode *ht) int min1,min2,p1,p2,i,k,n; system(“CLS“); printf(“t 请输入要编码的数据的个数:“); scanf(“%d“, if(n ntttt 结点的值:“,i); scanf(“%c“, printf(“tttt 节点权重：“); scanf(“%d“, printf(“ntt=n“); for(i = 1;i= 2 * n - 1; i+) hti.parent = hti.lchild = hti.rchild = 0; for(i = n+1;i= 2 * n - 1;i+)/产生新的 Huffman 节点 min1 = min2 = 32767;/min1 和 min2 开始赋最大值 p1=p2=1; for(k = 1;k=i-1;k+)/在输入的节点中选取权值最小的值 min1 和 min2 if(htk.parent = 0) if(htk.weight min1)/运用选择排序生成 HUFFMAN 树 min2 = min1; p2 = p1; min1 = htk.weight; p1 = k; else if(htk.weight min2) min2 =htk.weight; p2 = k; htp1.parent = i; htp2.parent = i; hti.weight = min1 + min2; hti.lchild = p1; hti.rchild = p2; printf(“nnnttt 提示:哈夫曼树构建成功！nnnn“); system(“PAUSE“); return n; - 4 - /*哈夫曼编码函数*/ void HuffmanCode(HuffNode ht,HuffCode hcd,int n) system(“CLS“); HuffCode d; int i,f,c,k; for(i = 1;i = n; i+ ) d.begin = n + 1; c = i; f = hti.parent ; while(f!=0) if(htf.lchild = c) d.cd-d.begin = 0; else d.cd-d.begin = 1; c = f; f = hti.parent ; /printf(“aaaaa=%d“,d.begin); if(d.begin = 0) break; hcdi = d; printf(“t 输出哈夫曼编码：n“); for(i = 1;i = n; i+) printf(“%c:“,hti.data); for(k = hcdi.begin;k = n; k+) printf(“%c“,hcdi.cdk); printf(“tn“); printf(“n 提示: 编码成功!n“); printf(“tnnnnn“); system(“PAUSE“); /*哈夫曼译码函数*/ void Huffmandecode(HuffNode ht,HuffCode hcd, int n) system(“CLS“); - 5 - int f,m,k; char c,ch100; printf(“t 请输入电文发译码的数据(0 or 1),nt 以#为结束标志:“); c = getchar(); k = 1; while(c != #) chk = c; c = getchar(); k = k + 1; m = k; f = 2 * n - 1; k = 1; printf(“t 输出哈夫曼译码：n“); printf(“n“); while(k m) while(htf.lchild != 0) if(chk = 0) f = htf.lchild; if(chk = 1) f = htf.rchild; k+; printf(“%c“,htf.data); f = 2 * n - 1; printf(“tnnn“); printf(“提示: 译码成功!nn“); system(“PAUSE“); /*主函数*/ int main(int argc ,char *argv) system(“CLS“); system(“color 0A“); int n,select,flag = 0; HuffNode ht2*MAXNUM; - 6 - HuffCode hcdMAXNUM; while(1) system(“CLS“); fflush(stdin); printf(“ttt 哈夫曼编码译码系统“); printf(“nt*菜单*n“); printf(“t* *n“); printf(“t* 1-建立哈夫曼树 *n“); printf(“t* 2-编码 *n“); printf(“t* 3-译码 *n“); printf(“t* 4-退出系统 *n“); printf(“t* *n“); printf(“t*n“); printf(“t* 电信班 * U20 * *n“); printf(“t*n“); printf(“t 请选择你所要实现的功能(请输入 14 数字): bb“); scanf(“%d“, if(select != 1 getch(); continue; flag = 1; switch(select) case 1:n = HuffmanCreate(ht);bre