gpt4 book ai didi

c++ - 从有序列表构建霍夫曼编码树

转载 作者:行者123 更新时间:2023-11-28 07:20:11 24 4
gpt4 key购买 nike

我正在从以最低频率开始的有序链表(按字母频率排序)构建霍夫曼编码树。创建树后,我遍历了它,似乎树的实现不正确。当我遍历树时,有序链表中的一些节点似乎被遗漏了。 (我不认为这是因为我的遍历错误。)这是我的树代码:

//My class for the nodes in the ordered linked list that will be converted to a tree
class fList{
public:
fList();
int frequency;
char letter;
fList* next;
fList* left;
fList* right;
};

fList::fList(){
frequency = 0;
letter = NULL;
next = NULL;
left = NULL;
right = NULL;
}
fList* head = NULL;

.
.
.
.
.

//Create the huffman encoding tree from the linked list stored in head
while(head->next != NULL){
fList *tree = new fList();
fList *temp = new fList();
fList *trail = new fList();

/* Take the first two frequency numbers, add them, create a new node
* with the total frequency number and have new node point to the first
* two nodes (right child and left child)
*/
total = (head->frequency + head->next->frequency);
tree->frequency = total;
//Set a new head node
tree->left = head;
tree->right = head->next;
head = head->next->next;
tree->left->next = NULL;
tree->right->next = NULL;

//place tree node in its correct place in sorted list
temp = head;
trail = temp;
if(head->frequency >= tree->frequency){
tree->next = head;
head = tree;
}

else if(temp->next != NULL){
while(temp != NULL){
if(temp->frequency >= tree->frequency){
tree->next = temp;
trail->next = tree;
break;
}
else{
trail = temp;
temp = temp->next;
}
}//while

//insert at the end of list
if(temp == NULL){
temp = tree->next;
trail->next = tree;
}
}//else if !=NULL

else if(head == NULL || head->next == NULL) head = tree;
}

最佳答案

在您发布的代码段的末尾,在行中

else if(temp->next = NULL && head != NULL) head = tree;

您通过设置 temp->next = NULL 无意中截断了树,您可能是想询问是否 temp->next == NULL。这可能就是为什么某些条目(由 temp 链接的条目)被排除在最终结果之外的原因。

关于c++ - 从有序列表构建霍夫曼编码树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19613460/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com