哈夫曼(Huffman)编码

广告位

    一、实验目的 1、掌握二叉树基本概念。 2、掌握二叉树建立方法。 3、掌握二叉树基…

 

 

一、实验目的
1、掌握二叉树基本概念。
2、掌握二叉树建立方法。
3、掌握二叉树基本操作和遍历方法。
4、掌握哈夫曼(Huffman)树建立、编码
5、了解解码方法。

二、实验内容
1、二叉树的定义和操作。
2、对输入权值个数及其权值,构造哈夫曼树。
权值数量 5
权值 5 4 3 2 1
3、输出其哈夫曼编码。

三、根据课本内容,编写以下程序
1、请编程实现二叉树的二叉链表链式存储。
2、请编程实现二叉树的前序,后序和中序遍历。
3、请编程实现哈夫曼树和哈夫曼树编码

【例如】

输入:
6
1 3 5 7 4 9

输出:
1010 1011 00 01 100 11


#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct{     int weight;     int parent,lch,rch; }HTNode, *HuffmanTree; typedef char *HuffmanCode;   void Select(HuffmanTree *HT, int n, int *s1, int *s2) {     int a, b, i;     int min = 1024;     for(i = 1; i <= n; i++) {         if((*HT)[i].parent == 0  && (*HT)[i].weight < min ){             min = (*HT)[i].weight;             a = i;         }     }     *s1 = a;       min = 1024;     for(i = 1; i <= n; i++) {         if((*HT)[i].parent == 0  && (*HT)[i].weight < min && i != a){             min = (*HT)[i].weight;             b = i;         }     }     *s2 = b; }  void CreatHuffmanTree(HuffmanTree *HT, int n) {     int i, s1, s2;     if(n <= 1)         return;     int m = 2 * n - 1;     *HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));     for(i = 1; i <= m; i++){         (*HT)[i].lch = 0;         (*HT)[i].rch = 0;         (*HT)[i].parent = 0;     }     for(i = 1; i <= n; i++)         scanf("%d", &(*HT)[i].weight);       for(i = n + 1; i <= m; i++){         Select(HT, i-1, &s1, &s2);         (*HT)[s1].parent = i;         (*HT)[s2].parent = i;         (*HT)[i].lch = s1;         (*HT)[i].rch = s2;         (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;     } }  void CreatHuffmanCode(HuffmanTree *HT, HuffmanCode *HC, int n) {     char *cd;     int i;     HC = (char **)malloc((n+1)*sizeof(char *));     cd = (char *)malloc(n*sizeof(char));     cd[n-1] = '';     for(i = 1; i <= n; i++){         int start = n - 1;         int c = i;         int f = (*HT)[i].parent;         while(f){             --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]);     }     for(i = 1; i <= n; i++)         printf("%s ",HC[i]);     printf("n");     free(cd); }  int main() {     int n;     HuffmanTree ht;     HuffmanCode hc;     scanf("%d", &n);     CreatHuffmanTree(&ht, n);     CreatHuffmanCode(&ht, &hc, n);     return 0; } 

 

說着敷衍話

关于作者: 說着敷衍話

为您推荐