本文参考原博客:http://www.noobyard.com/article/p-olaugukb-ho.htmlios
本文整理了最小堆结合哈夫曼树实现编解码的相关代码。算法
直接上代码吧:函数
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> using namespace std; typedef struct TreeNode *HuffmanTree; typedef struct TreeNode{ char ch; //要编码的字符 int Weight; //权值 HuffmanTree Left; HuffmanTree Right; }HuffmanNode; #define MinData -10 //随着堆元素的具体值而改变 typedef struct HeapStruct *MinHeap; struct HeapStruct{ HuffmanTree *data; //用哈夫曼树结点类定义堆元素的数据 存储时从下标1开始 int Size; //堆的当前元素的个数 int Capacity; //堆的最大容量 }; HuffmanTree NewHuffmanNode(); MinHeap CreateMinHeap(int MaxSize); bool Insert(MinHeap H,HuffmanTree item); HuffmanTree DeleteMin(MinHeap H); MinHeap BuildMinHeap(MinHeap H); HuffmanTree Huffman(MinHeap H); void PreOrderTraversal(HuffmanTree BST); void HuffmanCode(HuffmanTree BST,int depth); void HuffmanDecode(char ch[],HuffmanTree BST); int main() { int i,N; //叶子结点个数N MinHeap h; //小根堆h HuffmanTree T,BT = NULL; printf("请输入叶子结点的个数:\n"); scanf("%d",&N); h = CreateMinHeap(2*N); //建立最小堆 //N个叶子节点最终造成的哈夫曼树最多有2N-1个树结点 printf("请输入%d个叶子结点对应的权值:\n",N); for(i=1; i<=N; i++) { //最小堆元素赋值 T = NewHuffmanNode(); scanf("%d",&(T->Weight)); //权值写入T h->data[++(h->Size)] = T; //将T赋给小根堆h的data } char string[50]; printf("请连续输入这%d个叶子结点各自表明的字符:\n",N); getchar(); //吸取上面的换行符 gets(string); for(i=1; i<=h->Size; i++) { //最小堆元素赋值 h->data[i]->ch= string[i-1]; } BT = Huffman(h); //构造哈夫曼树 printf("先序遍历此哈夫曼树的权值:\n"); PreOrderTraversal(BT); //先序遍历此哈夫曼树 printf("\n"); HuffmanCode(BT,0); printf("请输入二进制编码序列进行解码操做:\n"); char ch[100]; gets(ch); printf("Result:"); HuffmanDecode(ch,BT); return 0; } /*哈夫曼树构造算法*/ HuffmanTree Huffman(MinHeap H) { //假设H->Size个权值已经存在H->data[]->Weight里 int i,num; HuffmanTree T; BuildMinHeap( H ); //将H->data[]按权值调整为最小堆 //此处必须将H->Size的值交给num,由于后面作DeleteMin()和 Insert()函数会改变H->Size的值 num = H->Size; for(i=1; i<num; i++) //作 H->Size-1次合并 { T = NewHuffmanNode(); //创建一个新的根结点 T->Left = DeleteMin(H); //从最小堆中删除一个节点,做为新T的左子结点 T->Right = DeleteMin(H); //从最小堆中删除一个节点,做为新T的右子结点 T->Weight = T->Left->Weight+T->Right->Weight; //计算新权值 Insert(H,T); //将新T插入到最小堆 } T = DeleteMin(H); return T; } /************递归进行哈夫曼编码*************/ void HuffmanCode(HuffmanTree BST,int depth) //depth为目前编码到哈夫曼树的深度(层次) { static int code[10]; //编码空间 if( BST ) { if( (BST->Left == NULL) && (BST->Right == NULL)) //找到了叶结点 { printf("字符%c对应权值为%d的哈夫曼编码为:",BST->ch,BST->Weight); for(int i=0; i<depth; i++) { printf("%d",code[i]); } printf("\n"); } else { code[depth] = 0; //往左子树方向编码为0 HuffmanCode(BST->Left,depth+1); //递归将左右孩子结点code赋予0,1值 code[depth] = 1; //往右子树方向编码为1 HuffmanCode(BST->Right,depth+1); } } } /*******************哈夫曼解码*********************/ void HuffmanDecode(char ch[],HuffmanTree BST) //ch[] 要解码的序列 { int code = 0; //用于判断保存左右信息 string decodechars = ""; //字符解码保存点 HuffmanTree temp; //定义一个哈夫曼树结点用于保存传进来的以前生成的哈夫曼树 int i; //定义计数点 temp=BST; //导入编码时生成的树用于解码 for (i=0;i<strlen(ch);i++) { while(temp->Left!=NULL && temp->Right !=NULL) //只要左右孩子不空,没有到达叶节点,指针就继续向下走 { code = ch[i] - '0'; //ch[i]中只有0和1的字符,减去'0'后等于0,则为0,不然为1 if(code == 0) { temp = temp->Left; //为0则左走 }else { temp = temp->Right; //为1则右走 } i++; //解下一位密码 } i--; //由于上一行在结束时会i++,这里必须减掉1,不然在下一次for循环里就会多加一 decodechars = decodechars + temp->ch; temp = BST; } cout<<decodechars<<endl; } /*****先序遍历*****/ void PreOrderTraversal(HuffmanTree BST) { if( BST ) { printf("%d ",BST->Weight); //先访问根节点 PreOrderTraversal(BST->Left); //再访问左子树 PreOrderTraversal(BST->Right); //最后访问右子树 } } HuffmanTree NewHuffmanNode() { HuffmanTree BST = (HuffmanTree)malloc(sizeof(HuffmanNode)); BST->Weight = 0; BST->Left = BST->Right = NULL; return BST; } MinHeap CreateMinHeap(int MaxSize) { //建立容量为MaxSize的最小堆 MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct)); H->data = (HuffmanTree *)malloc((MaxSize+1) * sizeof(HuffmanTree)); H->Size = 0; H->Capacity = MaxSize; HuffmanTree T = NewHuffmanNode(); T->ch = '\0'; //空字符 T->Weight = MinData; //定义哨兵-为小于堆中全部可能元素权值的值,便于之后更快操做 H->data[0] = T; return H; } bool IsFull(MinHeap H) { return (H->Size == H->Capacity); } bool IsEmpty(MinHeap H) { return (H->Size == 0); } /*插入算法-将新增结点插入到从其父结点到根结点的有序序列中*/ bool Insert(MinHeap H,HuffmanTree item) { //将元素item插入到最小堆H中,其中H->data[0]已被定义为哨兵 int i; if( IsFull(H) ) { printf("最小堆已满\n"); return false; } i = ++H->Size; //i指向插入后堆中的最后一个元素的位置 for(; H->data[i/2]->Weight > item->Weight; i/=2) //无哨兵,则增长判决条件 i>1 H->data[i] = H->data[i/2]; //向下过滤结点 H->data[i] = item; //将item插入 return true; } HuffmanTree DeleteMin(MinHeap H) { //从最小堆H中取出权值为最小的元素,并删除一个结点 int parent,child; HuffmanTree MinItem,temp = NULL; if( IsEmpty(H) ) { printf("最小堆为空\n"); return NULL; } MinItem = H->data[1]; //取出根结点-最小的元素-记录下来 /*用最小堆中的最后一个元素从根结点开始向上过滤下层结点*/ temp = H->data[H->Size--]; //最小堆中最后一个元素,暂时将其视为放在了根结点 for(parent=1; parent*2<=H->Size; parent=child){ child = parent*2; if((child != H->Size) && (H->data[child]->Weight > H->data[child+1]->Weight)) //有右儿子,而且左儿子权值大于右儿子 { child++; //child指向左右儿子中较小者 } if(temp->Weight > H->data[child]->Weight) { H->data[parent] = H->data[child]; //向上过滤结点-temp存放位置下移到child位置 }else { break; //找到了合适的位置 } } H->data[parent] = temp; //temp存放到此处 return MinItem; } MinHeap BuildMinHeap(MinHeap H) {/*这里假设全部的H->Size个元素已经存在H->data[]中*/ /*本函数将H->data[]中的元素调整,使其知足堆的有序性*/ int i,parent,child; HuffmanTree temp; for(i=H->Size/2;i>0;i--) //从最后一个父结点开始,直到根结点 { temp = H->data[i]; for(parent=i; parent*2<=H->Size; parent=child) { /*向下过滤*/ child = parent*2; if((child != H->Size) && (H->data[child]->Weight > H->data[child+1]->Weight)) /*有右儿子,而且左儿子权值大于右儿子*/ { child++; //child指向左右儿子中较小者 } if(temp->Weight > H->data[child]->Weight) { H->data[parent] = H->data[child]; //向上过滤结点-temp存放位置下移到child位置 }else { break; //找到了合适的位置 } }//结束内部for循环对以H->data[i]为根的子树的调整 H->data[parent] = temp; //temp(原H->data[i])存放到此处 } return H; }
结果:ui