广州北京网站建设公司哪家好网站提交入口链接

// C++ program for Huffman Coding
#include <cstdlib>
#include <iostream>
using namespace std;// This constant can be avoided by explicitly
// calculating height of Huffman Tree
#define MAX_TREE_HT 100// A Huffman tree node
struct MinHeapNode {// One of the input characterschar data;// Frequency of the characterunsigned freq;// Left and right child of this nodestruct MinHeapNode *left, *right;
};// A Min Heap: Collection of
// min-heap (or Huffman tree) nodes
struct MinHeap {// Current size of min heapunsigned size;// capacity of min heapunsigned capacity;// Array of minheap node pointersstruct MinHeapNode** array;
};// A utility function allocate a new
// min heap node with given character
// and frequency of the character
struct MinHeapNode* newNode(char data, unsigned freq)
{struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));temp->left = temp->right = NULL;temp->data = data;temp->freq = freq;return temp;
}// A utility function to create
// a min heap of given capacity
struct MinHeap* createMinHeap(unsigned capacity){struct MinHeap* minHeap= (struct MinHeap*)malloc(sizeof(struct MinHeap));// current size is 0minHeap->size = 0;minHeap->capacity = capacity;minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));return minHeap;
}// A utility function to
// swap two min heap nodes
void swapMinHeapNode(struct MinHeapNode** a,struct MinHeapNode** b){struct MinHeapNode* t = *a;*a = *b;*b = t;
}// The standard minHeapify function.
void minHeapify(struct MinHeap* minHeap, int idx){int smallest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < minHeap->size&& minHeap->array[left]->freq< minHeap->array[smallest]->freq)smallest = left;if (right < minHeap->size&& minHeap->array[right]->freq< minHeap->array[smallest]->freq)smallest = right;if (smallest != idx) {swapMinHeapNode(&minHeap->array[smallest],&minHeap->array[idx]);minHeapify(minHeap, smallest);}
}// A utility function to check
// if size of heap is 1 or not
int isSizeOne(struct MinHeap* minHeap)
{return (minHeap->size == 1);
}// A standard function to extract
// minimum value node from heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap){struct MinHeapNode* temp = minHeap->array[0];minHeap->array[0] = minHeap->array[minHeap->size - 1];--minHeap->size;minHeapify(minHeap, 0);return temp;
}// A utility function to insert
// a new node to Min Heap
void insertMinHeap(struct MinHeap* minHeap,struct MinHeapNode* minHeapNode){++minHeap->size;int i = minHeap->size - 1;while (i&& minHeapNode->freq< minHeap->array[(i - 1) / 2]->freq) {minHeap->array[i] = minHeap->array[(i - 1) / 2];i = (i - 1) / 2;}minHeap->array[i] = minHeapNode;
}// A standard function to build min heap
void buildMinHeap(struct MinHeap* minHeap){int n = minHeap->size - 1;int i;for (i = (n - 1) / 2; i >= 0; --i)minHeapify(minHeap, i);
}// A utility function to print an array of size n
void printArr(int arr[], int n)
{int i;for (i = 0; i < n; ++i)cout << arr[i];cout << "\n";
}// Utility function to check if this node is leaf
int isLeaf(struct MinHeapNode* root){return !(root->left) && !(root->right);
}// Creates a min heap of capacity
// equal to size and inserts all character of
// data[] in min heap. Initially size of
// min heap is equal to capacity
struct MinHeap* createAndBuildMinHeap(char data[],int freq[], int size){struct MinHeap* minHeap = createMinHeap(size);for (int i = 0; i < size; ++i)minHeap->array[i] = newNode(data[i], freq[i]);minHeap->size = size;buildMinHeap(minHeap);return minHeap;
}// The main function that builds Huffman tree
struct MinHeapNode* buildHuffmanTree(char data[],int freq[], int size){struct MinHeapNode *left, *right, *top;// Step 1: Create a min heap of capacity// equal to size. Initially, there are// modes equal to size.struct MinHeap* minHeap= createAndBuildMinHeap(data, freq, size);// Iterate while size of heap doesn't become 1while (!isSizeOne(minHeap)) {// Step 2: Extract the two minimum// freq items from min heapleft = extractMin(minHeap);right = extractMin(minHeap);// Step 3: Create a new internal// node with frequency equal to the// sum of the two nodes frequencies.// Make the two extracted node as// left and right children of this new node.// Add this node to the min heap// '$' is a special value for internal nodes, not// usedtop = newNode('$', left->freq + right->freq);top->left = left;top->right = right;insertMinHeap(minHeap, top);}// Step 4: The remaining node is the// root node and the tree is complete.return extractMin(minHeap);
}// Prints huffman codes from the root of Huffman Tree.
// It uses arr[] to store codes
void printCodes(struct MinHeapNode* root, int arr[],int top){// Assign 0 to left edge and recurif (root->left) {arr[top] = 0;printCodes(root->left, arr, top + 1);}// Assign 1 to right edge and recurif (root->right) {arr[top] = 1;printCodes(root->right, arr, top + 1);}// If this is a leaf node, then// it contains one of the input// characters, print the character// and its code from arr[]if (isLeaf(root)) {cout << root->data << ": ";printArr(arr, top);}
}// The main function that builds a
// Huffman Tree and print codes by traversing
// the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size){// Construct Huffman Treestruct MinHeapNode* root= buildHuffmanTree(data, freq, size);// Print Huffman codes using// the Huffman tree built aboveint arr[MAX_TREE_HT], top = 0;printCodes(root, arr, top);
}// Driver code
int main()
{char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };int freq[] = { 5, 9, 12, 13, 16, 45 };int size = sizeof(arr) / sizeof(arr[0]);HuffmanCodes(arr, freq, size);return 0;
}

// C++(STL) program for Huffman Coding with STL
#include <bits/stdc++.h>
using namespace std;// A Huffman tree node
struct MinHeapNode {// One of the input characterschar data;// Frequency of the characterunsigned freq;// Left and right childMinHeapNode *left, *right;MinHeapNode(char data, unsigned freq){left = right = NULL;this->data = data;this->freq = freq;}
};// For comparison of
// two heap nodes (needed in min heap)
struct compare {bool operator()(MinHeapNode* l, MinHeapNode* r){return (l->freq > r->freq);}
};// Prints huffman codes from
// the root of Huffman Tree.
void printCodes(struct MinHeapNode* root, string str)
{if (!root)return;if (root->data != '$')cout << root->data << ": " << str << "\n";printCodes(root->left, str + "0");printCodes(root->right, str + "1");
}// The main function that builds a Huffman Tree and
// print codes by traversing the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)
{struct MinHeapNode *left, *right, *top;// Create a min heap & inserts all characters of data[]priority_queue<MinHeapNode*, vector<MinHeapNode*>,compare>minHeap;for (int i = 0; i < size; ++i)minHeap.push(new MinHeapNode(data[i], freq[i]));// Iterate while size of heap doesn't become 1while (minHeap.size() != 1) {// Extract the two minimum// freq items from min heapleft = minHeap.top();minHeap.pop();right = minHeap.top();minHeap.pop();// Create a new internal node with// frequency equal to the sum of the// two nodes frequencies. Make the// two extracted node as left and right children// of this new node. Add this node// to the min heap '$' is a special value// for internal nodes, not usedtop = new MinHeapNode('$',left->freq + right->freq);top->left = left;top->right = right;minHeap.push(top);}// Print Huffman codes using// the Huffman tree built aboveprintCodes(minHeap.top(), "");
}// Driver Code
int main()
{char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };int freq[] = { 5, 9, 12, 13, 16, 45 };int size = sizeof(arr) / sizeof(arr[0]);HuffmanCodes(arr, freq, size);return 0;
}// This code is contributed by Aditya Goel

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111