c语言实现哈夫曼树编码和解码（c语言实现哈夫曼树译码）

本文实例为大家分享了C语言实现哈夫曼树的具体代码，供大家参考，具体内容如下

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 //哈夫曼树C语言实现 #include <stdio.h> #include <stdlib.h> typedef struct HuffmanNode { char letter;//存储的字符，叶节点为字母，非叶节点为# struct HuffmanNode *parent;//父亲结点 int code;//如果为父亲结点的左孩子，则为0，右孩子为1 }HuffmanNode; typedef struct HeapNode { int rate;//出现频率 HuffmanNode *node;//对应于哈夫曼树中的结点 }HeapNode; /*------------------全局变量----------------------*/ int heapSize;//堆大小 int num;//记录字符数量 HeapNode *heap;//堆数组 char *letter;//字符数组 int *rate;//字符出现频率 HuffmanNode **array; //记录叶节点的数组，打印编码的时候可以从叶结点回溯向上 char ch; /*----------------------函数声明-------------------------*/ void init(int numOfLetters);//初始化变量 void input();//输入数组 int parent(int i);//求父节点 int left(int i);//求左孩子 int right(int i);//求右孩子 void swap(int i,int j);//交换函数 void heapIfy(int i,int localHeapSize);//维持堆性质函数，使用前提为左右子树均为最小堆 void buildHeap();//初始化堆 HeapNode* extractMin();//去掉并返回堆中最小的元素 void heapInsert(int rate,HuffmanNode *p);//向堆中插入数据（前提：堆已经初始化） HuffmanNode* buildTree();//构造哈夫曼树 void display();//显示函数 void backPrint(HuffmanNode *p,HuffmanNode *root);//从叶节点回溯打印编码code /*----------------------函数实现-------------------------*/ void init(int numOfLetters) { heapSize=numOfLetters;//堆大小初始化为字母数 num=numOfLetters;//记录字符数量 heap=(HeapNode*)malloc((numOfLetters+1)*sizeof(HeapNode));//分配堆空间，最多只需要字符的个数，因为合并过程中删除两个，插入一个 letter=(char*)malloc((numOfLetters+1)*sizeof(char));//用于存储字符 rate=(int *)malloc((numOfLetters+1)*sizeof(int));//用于存储字符出现频率 array=(HuffmanNode **)malloc((numOfLetters+1)*sizeof(HuffmanNode));//记录叶节点的数组，打印编码的时候可以从叶结点回溯向上 } void input() { int i=1; while(i<=heapSize) { printf("输入第%d个字符\n",i); scanf("%c",&letter[i]);ch=getchar(); printf("输入第%d个字符的频度\n",i); scanf("%d",&rate[i]);ch=getchar(); //向堆中插入各个结点 heap[i].rate=rate[i]; heap[i].node=(HuffmanNode *)malloc(sizeof(HuffmanNode)); array[i]=heap[i].node; heap[i].node->parent=NULL; heap[i].node->letter=letter[i]; i++; } } int parent(int i) { return i/2; } int left(int i) { return 2*i; } int right(int i) { return 2*i+1; } void swap(int i,int j) //交换结构体数组，需要交换结构体内数据 { int rate; HuffmanNode *p; rate=heap[i].rate; p=heap[i].node; heap[i].rate=heap[j].rate; heap[i].node=heap[j].node; heap[j].rate=rate; heap[j].node=p; } void heapIfy(int i,int localHeapSize)//维持堆性质函数，使用前提为左右子树均为最小堆 { int l=left(i); int r=right(i); int least=i; //找出heap成员rate 的i,left(i),right(i)的最小值 if(l<=localHeapSize&&heap[least].rate>heap[l].rate) { least=l; } if(r<=localHeapSize&&heap[least].rate>heap[r].rate) { least=r; } if(least!=i) { swap(i,least); heapIfy(least,localHeapSize); } } void buildHeap()//初始化堆 { int i=0; for(i=heapSize/2;i>=1;i--) { heapIfy(i,heapSize); } } HeapNode* extractMin() { if(heapSize>=1) { HeapNode *min; swap(1,heapSize); min=&heap[heapSize]; --heapSize; heapIfy(1,heapSize); return min; } else { printf("堆中没有元素"); return NULL; } } void heapInsert(int rate,HuffmanNode *p) { ++heapSize; int i=heapSize; while(i>1&&heap[parent(i)].rate>rate) { heap[i].rate=heap[parent(i)].rate; heap[i].node=heap[parent(i)].node; i=parent(i); } heap[i].rate=rate; heap[i].node=p; } HuffmanNode* buildTree() { buildHeap();//初始化堆 HeapNode *p;//用于临时存储最小堆结点 HeapNode *q;//用于临时存储次小堆结点 int count=heapSize; int i; for(i=1;i<=count-1;i++) { HuffmanNode *tree=(HuffmanNode*)malloc(sizeof(HuffmanNode));//生成内结点 tree->letter='#';//内结点的字符记作#，没有实际意义 p=extractMin(); q=extractMin(); p->node->parent=tree; p->node->code=0; q->node->parent=tree; q->node->code=1; //printf("%c:%d",p->node->letter,p->node->code); //printf("\n"); printf("%c:%d",q->node->letter,q->node->code); printf("\n");//测试 heapInsert(p->rate+q->rate,tree);//插入堆中 } return extractMin()->node; } void display() { HuffmanNode*p=buildTree();////哈夫曼树的根节点地址 int i=1; while(i<=num) { printf("%c:",array[i]->letter); backPrint(array[i],p); printf("\n"); i++; } } void backPrint(HuffmanNode *p,HuffmanNode *root) { if(p!=root) { backPrint(p->parent,root); printf("%d",p->code);//printf("++++");//测试 } } int main(int argc ,char* argv[]) { int number; printf("输入的字符个数为：\n"); scanf("%d",&number); ch=getchar(); init(number); input(); display(); system("PAUSE"); return 0; }