#include stdioh #include stdlibh #include stringh 定义链表节点结构体 typedef struct ListNode int c; 存储字符使用 int 类型能够正确处理特殊字符 int frequency; 存储字符出现频度 char code; 存储字符编码在后续实现哈夫曼编码时使用 int order; 存储节点插入先后顺序 st

问题出在排序函数中，需要对节点的指针域也进行交换，以保证链表的正确性。修改sort函数如下：

void sort(ListNode *head) { ListNode *p, *q; int tmpc, tmpfrequency, tmporder; ListNode *tmpparent, *tmpleft, *tmpright, *tmpnext; char *tmpcode; p = head->next; while(p != NULL) { q = p->next; while(q != NULL) { if(p->frequency < q->frequency || (p->frequency == q->frequency && p->order > q->order)) { tmpc = q->c; q->c = p->c; p->c = tmpc; tmpfrequency = q->frequency; q->frequency = p->frequency; p->frequency = tmpfrequency; tmporder = q->order; q->order = p->order; p->order = tmporder; tmpcode = q->code; q->code = p->code; p->code = tmpcode; tmpparent = q->parent; q->parent = p->parent; p->parent = tmpparent; tmpleft = q->left; q->left = p->left; p->left = tmpleft; tmpright = q->right; q->right = p->right; p->right = tmpright; tmpnext = q->next; q->next = p->next; p->next = tmpnext; p->code += q->code - (q->code = p->code); // 交换指针域，保证链表的正确性 } q = q->next; } p = p->next; }