/*从文件构建Huffman树*/ pNode buildHuffmanTreeFromFile(FILE* input) { int times[LIST_SIZE] = { 0 }; Byte byte; while (fread(&byte, sizeof(byte), 1, input) == 1) { ++times[byte]; //使用 fread 函数从文件 input 中读取一个字节,如果读取成功,则将对应字节的出现次数加一 } //首先进行文件中的字符频度统计,构建频度表 return buildHuffmanTree(times); }计算时间复杂度
时间: 2024-04-22 17:27:03 浏览: 23
该函数的时间复杂度主要由两个部分组成:
1. 统计字符频度:需要遍历整个文件中的每个字符,时间复杂度为 O(n),其中 n 是文件中字符的个数。
2. 构建 Huffman 树:根据频度表构建 Huffman 树的时间复杂度为 O(nlogn),其中 n 是字符集大小。
因此,该函数的总时间复杂度为 O(nlogn)。
相关问题
pNode buildHuffmanTree(int times[]) { pNode nodelist[FOREST_SIZE] = { NULL }; pNode root = NULL; int index; /*创建森林表*/ for (index = 0; index < LIST_SIZE; ++index) { if (times[index] > 0) { /*将所有节点逐个放入森林表*/ addNodeToList(nodelist, FOREST_SIZE, createDataNode(index, times[index])); } } /*构建Huffman树*/ while (1) { pNode left = popMinNodeFromList(nodelist, FOREST_SIZE); pNode right = popMinNodeFromList(nodelist, FOREST_SIZE); if (right == NULL) { /*当森林中只剩下一颗树节点的时候表示整个Huffman树构建完成*/ root = left; break; } else { pNode node = createBlankNode(left->weight + right->weight); node->left = left; node->right = right; /*每次从森林表中取出两个最小的节点,并创建新节点重新放入森林表*/ addNodeToList(nodelist, FOREST_SIZE, node); } } generateHuffmanCode(root); return root; }分析时间复杂度
这段代码的时间复杂度是O(nlogn),其中n是LIST_SIZE,即森林表中节点的数量。首先,这段代码会遍历times数组,将所有出现过的字符及其出现次数都放入nodelist数组中,这个过程的时间复杂度是O(n)。接下来,代码会通过不断从nodelist数组中取出两个权重最小的节点,构建一颗新的节点,并将新节点放回nodelist数组中,直到整个Huffman树构建完成。这个过程中,每次从nodelist数组中取出最小的两个节点的时间复杂度是O(logn),一共需要取出n-1次,所以这个过程的时间复杂度是O(nlogn)。最后,代码会对构建好的Huffman树进行编码,这个过程的时间复杂度是O(n)。因此,整个函数的时间复杂度就是O(nlogn)。
/*对文件数据进行Huffman编码*/ int encodeFileData(pNode root, FILE* input, FILE* output) { int total = 0; int count = 0; if (root) { Byte byte; int buffer = 0; pNode nodelist[LIST_SIZE] = { NULL }; /*将Huffman树转换成Huffman表*/ convertTreeToList(root, nodelist); while (fread(&byte, sizeof(byte), 1, input) == 1) { char* cursor = nodelist[byte]->code; while (*cursor) { buffer <<= 1; if (*cursor == '0') { buffer |= 0; } else { buffer |= 1; } ++count; if (count == 8) { Byte byte = (Byte)buffer; fwrite(&byte, sizeof(byte), 1, output); count = 0; buffer = 0; ++total; } ++cursor; } } if (count > 0) { buffer <<= (8 - count); char byte = (char)buffer; fwrite(&byte, 1, 1, output); ++total; } } return total; }
这段代码是用来对文件数据进行Huffman编码的。它使用了Huffman表,将输入文件中的每个字节转换成对应的Huffman编码,并将编码后的结果写入输出文件中。
首先,这段代码定义了一个变量total,用来记录编码后的字节数。接着,它定义了一个缓冲区buffer和一个计数器count,用来临时存储编码后的数据。然后,它调用了convertTreeToList函数,将Huffman树转换成Huffman表,以便于编码时查找每个字节对应的Huffman编码。
在主循环中,它使用fread函数从输入文件中读取一个字节,并调用Huffman表中对应字节的节点,得到该字节对应的Huffman编码。然后,它将编码中的每一位依次存入缓冲区buffer中。当缓冲区中的位数达到8位时,将缓冲区中的数据写入输出文件,并将计数器count和缓冲区buffer清零。最后,如果还有剩余的位数,将其补齐到8位并写入输出文件。整个过程重复直到输入文件中的所有字节都被编码。
最终,这段代码返回编码后的字节数total。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)