c++ 哈夫曼树简便构造(数据结构作业篇)

// 用最小栈方式构建哈弗曼树

// 定义一个哈夫曼树的节点

struct MinHeapNode {

// One of the input characters

char data;

// Frequency of the character

unsigned freq;

// 哈夫曼的编码值, #号表示无编码

string code_huff = "#";

// Left and right child

MinHeapNode *left, *right;

    MinHeapNode(char data, unsigned freq)

    {

left = right = NULL;

this->data = data;

this->freq = freq;

    }

};

// 定义一个哈弗曼树的存储节点

struct Node {

char data;

string code_huff = "#";

}node[256];

// For comparison of

// two heap nodes (needed in min heap)

struct compare {

bool operator()(MinHeapNode* l, MinHeapNode* r)

    {

return (l->freq > r->freq);

    }

};

// 递归的方式打印哈夫曼编码从树的根部

void printCodes(struct MinHeapNode* root, string str)

{

if (!root)

return;

if (root->data != '$')

    {

cout << root->data << ": " << str << "\n";

        root->code_huff = str;

node[cou].data = root->data;

node[cou].code_huff = root->code_huff;

cou++;

    }

printCodes(root->left, str + "0");

printCodes(root->right, str + "1");

}

// 创建一个哈夫曼树

// data 为字符数组, freq 为对应频数, size 为字符数组元素的个数

struct MinHeapNode* HuffmanCodes(char data[], unsigned int freq[], int size)

{

struct MinHeapNode *left, *right, *top;

// 创建一个根据频数值的最小堆并插入字符数组中所有的字符

priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;

// 将需要排序的内容压入堆中

for (int i = 0; i < size; ++i)

    {

if (freq[i] != 0)

        minHeap.push(new MinHeapNode(data[i], freq[i]));

    }

// Iterate while size of heap doesn't become 1

while (minHeap.size() != 1) {

// 从最小堆中取出两个最小频数的项目

        left = minHeap.top();

        minHeap.pop();

        right = minHeap.top();

        minHeap.pop();

// 创建树中的和节点, 并连接左右两个子节点, 后再将其压入堆中

        top = new MinHeapNode('$', left->freq + right->freq);

        top->left = left;

        top->right = right;

        minHeap.push(top);

    }

// 输出哈夫曼编码通过已创建的哈弗曼树

printCodes(minHeap.top(), "");

// 返回哈夫曼树的根

return minHeap.top();

}

以上程序中所用到的知识点如下：

• 头文件精简法

可以用一个文件包含 c++ 所有的头文件 # 用来精简头文件的结构

• 哈弗曼树的节点个数

# 建立叶节点个数为n，权值为weight的哈夫曼树共有 2n-1个节点

• priority_queue 的用法

用法: priority_queue<Type, Container, Functional> maxHeap; # Type 为数据类型, Container 为保存数据的容器, Functional 为元素比较方式 # Container 默认用的是 vector, Functional 默认用 operator< # 默认形成大顶堆, 队头元素最大 # 上面程序中传入 compare 比较函数, 实现形成小顶堆, 队头元素最小

• 堆的操作

入堆操作

用法: Heap.push(参数) # 将参数内容压入堆中

出堆操作

用法: Heap.pop(参数) # 将堆顶内容弹出

堆头

用法: Heap.top() # 表示堆头

• 函数内的数组元素值改变

用法: 函数名: void str(char a[], int b[]) 使用函数: str(a, b); #可以直接传入数组头, 函数内改变数组元素即改变

• '\n'是一个字符
• 不忽略空白符的从文件中读取字符的解决方法

用 file.getline() 来解决

# 根据行的方式来读取

用 file >> noskipws;

# 强制读入每一个字符, 不过滤空白符, 包括换行符