huffman树--静态链表和链表实现(借助优先队列)

mac2025-02-25  1

静态链表实现:

#include<iostream> #include<vector> #include<string> using namespace std; const int maxWeight = 32767; struct HTNode { char data; int weight; int parent,lchild,rchild; }; struct HFTree { vector<HTNode>elem; int root; int num; // huffman树外结点个数 }; void createHFTree(HFTree &HT,string value,vector<int>fr) {//输入数据value[n]和 相应权值fr[n],构造用三叉链表表示的Huffman树HT int min1,min2; HT.elem.resize(value.length()*2-1); //huffman是一颗正则二叉树,有2*n-1个结点 for(int i = 0; i < value.length(); i++) { HT.elem[i].data = value[i]; HT.elem[i].weight = fr[i]; } for(int i = 0; i < 2*value.length()-1; i++) { HT.elem[i].parent = HT.elem[i].lchild = HT.elem[i].rchild = -1; } int s1,s2; for(int i = value.length(); i < 2*value.length() - 1 ; i++) //循环n-1次,因为还有 { //n-1个结点要添加 min1 = min2 = maxWeight; s1 = s2 = 0; for(int k = 0;k < i; k++) { if(HT.elem[k].parent == -1) { if(HT.elem[k].weight < min1 ) //最小 { min2 = min1; s2 = s1; min1 = HT.elem[k].weight; s1 = k; } else if(HT.elem[k].weight < min2) //次小 { min2 = HT.elem[k].weight; s2 = k; } } } HT.elem[s1].parent = HT.elem[s2].parent = i; HT.elem[i].lchild = s1; HT.elem[i].rchild = s2; HT.elem[i].weight = HT.elem[s1].weight + HT.elem[s2].weight; } HT.num = value.length(); HT.root = 2*value.length() - 2; } int main() { string values = "ABCDE"; vector<int> fr = {7,5,2,4,6}; HFTree HF; createHFTree(HF,values,fr); for(int i = 0; i < HF.elem.size(); i++) { cout<<HF.elem[i].data<<" parent is "<<HF.elem[i].parent<<" lchild is "<<HF.elem[i].lchild<<" rchild is "<<HF.elem[i].rchild <<" weight is "<<HF.elem[i].weight<<endl; } return 0; }

二叉链表实现:

#include<iostream> #include<vector> #include<string> #include<queue> using namespace std; struct Node { char data; double weight; Node *lchild,*rchild; Node(char _data,double _weight) { data = _data; weight = _weight; lchild = rchild = NULL; } }; class cmp { public: bool operator()(const Node *n1,const Node *n2) const { return n1->weight > n2->weight; } }; void createHuffmanTree(Node *&root,string values,vector<double>weights) { if(values.length() <= 0) { root = NULL; return ; } priority_queue<Node*,vector<Node*>,cmp> q; //优先队列 for(int i = 0; i < values.length(); i++) { Node *newNode = new Node(values[i],weights[i]); q.push(newNode); } for(int i = 0; i < values.length() - 1; i++) //循环n-1次,加n-1个结点 {//因为huffman树是正则二叉树(只有度为2和0的结点),所以共2n-个结点,所以再加n-1个结点就够了 Node *x = q.top(); q.pop(); Node *y = q.top(); q.pop(); Node* cur = new Node('#',x->weight + y->weight); cur->lchild = x; cur->rchild = y; q.push(cur); } root = q.top(); } void printHuffmanCode(const Node *root,string code) { if(root->lchild == NULL && root->rchild == NULL) { cout<<root->data<<": huffman code is "<<code<<endl; } else { printHuffmanCode(root->lchild,code+"0"); printHuffmanCode(root->rchild,code+"1"); } } void printHuffmanTree(Node *root,int k) //这里是先打印水平打印,先打印的右子树再打左子树 { if(root != NULL) { printHuffmanTree(root->rchild,k+5); for(int i = 0; i < k; i++) { cout<<" "; } cout<<root->data<<endl; printHuffmanTree(root->lchild,k+5); } } int main() { string values = "abcde"; vector<double>weights = {0.05,0.20,0.35,0.30,0.10}; Node *root = NULL; createHuffmanTree(root,values,weights); printHuffmanCode(root,""); printHuffmanTree(root,0); return 0; }

(注:huffman编码树的形态不一定是一样的,因为同一层左右子女位置可以交换,这里实现的weight小的在左边,大的在右边。

===========================================================

严版huffman:

typedef struct { int weight; int parent,lchild,rchild; }HTNode, *HuffmanCode; typedef char **HuffmanCode; void HuffmanCoding(HuffmanTree &HT,int *w,int n) { if(n <= -1) return ; int m = 2*n-1; HT = (HuffmanCode)malloc((m+1)*sizeof(HTNode)); int i; for(HTNode *p=HT, i = 1; i <= n; i++, p++, w++) { *p = {*w, 0, 0, 0}; } for( ;i <= m; i++) { *p = {0,0,0,0};} for(i = n+1;i <= m; i++) { select(HT, i-1,s1,s2); //s1, s2为权值最小的俩个关键字的下标 HT[s1].parent = i; Ht[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } } void getHuffmanCode(HuffmanTree &HT, HuffmanCode&HC) { HC = (HuffmanCode)malloc((n+1)*sizeof(char*)); cd = (char*)malloc(n*sizeof(char)); cd[n-1] = "\0"; for(int i = 1; i <= n; i++) { int start = n-1; for(int c = i,f = HT[i].parent; f != 0; c = f,f = HT[f].parent) {//从叶子到根逆向求编码 if(HT[f].lchild == c) cd[--start] = '0'; else cd[--start] = '1'; } HC[i] = (char*)malloc((n-start)*sizeof(char)); strcpy(HC[i], &cd[start]); } free(cd); }
最新回复(0)