链表合并排序的 C++ 实现在加入超过 1 个节点的子列表时失败 [英] C++ Implementation of Mergesort of Linked-List Fails on Joining Sublists Of More Than 1 Node
问题描述
我一直致力于链表的模板化实现，目的是重新发明轮子，偶然发现这种类型的问题，以帮助了解指向类实例处理的指针的细微差别.我偶然发现的问题与合并子列表有关，其中第二次合并(子列表可以有多个节点的第一次合并)失败，而先前的类实例(来自 split 或 mergesorted) 似乎超出了范围(这应该不会对合并产生任何影响，因为指针分配是在分配原始列表节点之前始终保持在范围内的先验列表)
这里的关键是所有的类实例都有指向原始列表中原始节点的指针，所以只要子列表实例保持在作用域内，直到子列表的开始节点返回并分配给上一次递归中的列表.我正在尝试移动一个完美的 100% 工作 C 实现.因此，我对为什么不能像对待 C 中的结构那样对待类实例的理解存在问题，这就是这里的问题——但我无法将手指放在解释原因的文档上.
list_t 类包含结构 node_t 以形成列表.
/* 链表节点 */模板结构 node_t {数据；node_t*下一个;};模板类列表_t {node_t*头，*尾；int (*cmp)(const node_t*, const node_t*);上市:list_t (void);/* 构造函数 */list_t (int(*f)(const node_t*, const node_t*));~list_t (void);/* 析构函数 */list_t (const list_t&);/* 复制构造函数 *//* 比较函数的设置器 */,,,list_t 拆分(无效)；/* 拆分列表 ~ 1/2 */.../* 在 mergesort_start 之后合并列表 */node_t*合并排序(node_t*a，node_t*b)；void mergesort_run (list_t<T> *l);/* 归并排序函数 */无效归并排序(无效)；/* 合并排序的包装器 */}; (是的，我知道没有 _t 后缀，这不是重点)
split 功能工作正常，并且是:
/* 将列表 l 拆分为列表 a &乙 */模板list_tlist_t<T>::split (void){list_ts;/* 类的新实例 */node_t*pa = head,/* 指向当前头部的指针 */*pb = pa->next;/* 第二个指向双进的指针 */while (pb) {/* 而不是列表结尾 */pb = pb->下一个；/* 推进第二个 ptr */if (pb) {/* 如果不是 nullptr */pa = pa->下一个；/* 推进当前的ptr */pb = pb->下一个；/* 再次推进第二个 ptr */}}s.tail = 尾巴;/* 第二个半尾将是当前尾 */尾巴 = pa;/* 当前尾部在 pa */s.head = pa->next;/* 第二个半头是下一个 ptr */pa->next = nullptr;/* 设置下一个 ptr NULL 以结束第一个 1/2 */返回 s;/* 返回新实例 */} 对于合并排序，我有一个调用实际合并排序函数mergesort_run 的包装器.这样做是为了更新 tail 指针仅在排序完成后调用，例如
/* 包装到 mergesort_run 中的实际合并排序路由 */模板void list_t<T>::mergesort(void){合并排序运行(这个)；/* 将尾指针设置为排序后的最后一个节点 */for (node_t *pn = head; pn; pn = pn->next)尾巴 = pn;} mergesort_run如下:
/* 按排序顺序拆分和合并拆分 */模板void list_t<T>::mergesort_run (list_t<T> *l){/* 基本情况——长度为 0 或 1 */if (!l->head || !l->head->next) {返回;}/* 将头部拆分为 'a' 和 'b' 子列表 */list_tla = l->split();/* 递归排序子列表 */mergesort_run(l);mergesort_run(&la);/* 将两个排序列表合并在一起 */l->head = 归并排序 (l->head, la.head);} 合并函数，mergesorted 按排序顺序合并子列表:
template node_t*list_t::mergesorted (node_t *a, node_t *b){node_t*结果= nullptr;/* 基本情况 */如果一个)返回 (b)；否则如果(！b)退货(一)；/* 选择 a 或 b，然后重复 */如果 (cmp (a, b) <= 0) {结果 = 一个;结果->下一个=归并排序(a->下一个，b)；}别的 {结果 = b;结果->下一个=归并排序(a，b->下一个)；}返回结果；} 我正在使用的 C 实现
以上每个(除了我拆分初始包装器)都是来自以下工作 C 拆分/合并排序的实现:
/* 将列表 l 拆分为列表 a &乙 */void split (list_t *l, list_t *a){node_t *pa = l->head，*pb = pa->next;而 (pb) {pb = pb->下一个；如果(铅){pa = pa->下一个；pb = pb->下一个；}}a->尾=l->尾；l->尾=pa；a->head = pa->next;pa->next = NULL;}/* 按排序顺序合并拆分 */node_t *mergesorted (node_t *a, node_t *b){node_t *res = NULL;/* 基本情况 */如果一个)返回 (b)；否则如果(！b)退货(一)；/* 选择 a 或 b，然后递归 */如果 (a-> 数据 <= b-> 数据) {res = a;res->next = 归并排序 (a->next, b);}别的 {资源= b;res->next = 归并排序 (a, b->next);}返回资源；}/* 通过改变下一个指针(不是数据)对链表进行排序 */无效归并排序(list_t *l){list_t la;node_t *head = l->head;/* 基本情况——长度为 0 或 1 */if (!head || !head->next) {返回;}/* 将头部拆分为 'a' 和 'b' 子列表 */分裂 (l, &la);/* 递归排序子列表 */归并排序(l)；归并排序(&la);/* answer = 将两个排序的列表合并在一起 */l->head = 归并排序 (l->head, la.head);/* 将尾指针设置为排序后的最后一个节点 */for (head = l->head; head; head = head->next)l->尾=头；}第二次合并，第一次合并的节点消失
我已经使用 gdb 和 valgrind 逐步完成了 C++ 实现.在 gdb 中，代码将无错误地完成，但在 valgrind 中，您在已释放的块之后读取了 4 和 8 个字节的无效数据，这表明析构函数正在释放内存(它应该)但是在递归展开时完成的指针分配依赖于来自嵌套递归调用的指针的地址，而不是仅使用原始地址处的值(作为上面的C代码做的很好)
发生的事情是，在将列表拆分为具有单个节点的子列表并进行第一次合并之后——我们仍然很好.当下一次展开发生时，您会将组合节点与另一个子列表合并——2 节点子列表的值将丢失.因此，在选择了 C 和 C++ 实现之后，我感觉自己像个白痴，因为我可以在 CI 中简单地调试/纠正问题，但缺少一些关键的理解，这使我可以对相同代码的 C++ 类实现做同样的事情.
测试代码
int main (void) {
list_t升；int arr[] = {12, 11, 10, 7, 4, 14, 8, 16, 20, 19,2、9、1、13、17、6、15、5、3、18}；无符号 asz = sizeof arr/sizeof *arr;for (unsigned i = 0; i 左子列表在拆分为节点12 和11 后的开始合并正常.一旦我将 11, 12 子列表与 10 合并 - 11, 12 子列表值就消失了.
MCVE
#include /* 链表节点 */模板结构 node_t {数据；node_t*下一个;};/* 带重载(升序)类型的默认比较函数 */模板 int compare_asc (const node_t *a, const node_t *b){返回(a->数据>b->数据)-(a->数据数据)；}/* 比较具有重载(降序)类型的函数 */模板 int compare_desc (const node_t *a, const node_t *b){返回(a->数据数据)-(a->数据>b->数据)；}模板类列表_t {node_t*头，*尾；int (*cmp)(const node_t*, const node_t*);上市:list_t (void);/* 构造函数 */list_t (int(*f)(const node_t*, const node_t*));~list_t (void);/* 析构函数 */list_t (const list_t&);/* 复制构造函数 *//* 比较函数的设置器 */void setcmp (int (*f)(const node_t*, const node_t*));node_t*addnode(T 数据)；/* 在末尾简单添加 */node_t*加法(T数据)；/* 按顺序添加 */void delnode(T数据)；/* 删除节点 */无效的prnlist(无效)；/* 打印空格分隔 */list_t 拆分(无效)；/* 拆分列表 ~ 1/2 */空插入排序(空)；/* 插入排序列表 *//* 在 mergesort_start 之后合并列表 */node_t*合并排序(node_t*a，node_t*b)；void mergesort_run (list_t<T> *l);/* 归并排序函数 */无效归并排序(无效)；/* 合并排序的包装器 */};/* 构造函数(默认) */模板list_t<T>::list_t (void){头 = 尾 = nullptr;cmp = compare_asc;}/* 构造函数将比较函数作为参数 */模板list_t::list_t (int(*f)(const node_t*, const node_t*)){头 = 尾 = nullptr;cmp = f;}/* 析构函数释放所有列表内存 */模板list_t<T>::~list_t (void){node_t*pn = 头；而 (pn) {node_t*受害者= pn;pn = pn->下一个；删除受害者；}}/* 复制构造函数 - 复制现有列表 */模板list_t<T>::list_t (const list_t& l){cmp = l.cmp;/* 分配比较函数 ptr */头 = 尾 = nullptr;/* 初始化头/尾 *//* 将数据复制到新列表 */for (node_t *pn = l.head; pn; pn = pn->next)this->addnode (pn->data);}/* 设置器比较函数 */模板void list_t::setcmp (int(*f)(const node_t*, const node_t*)){cmp = f;}/* 添加使用尾部 ptr */模板node_t*list_t::addnode(T 数据){node_t*节点=新节点_t；/* 分配/初始化节点 */节点->数据=数据；节点->下一个= nullptr;如果(！头)头 = 尾 = 节点；别的 {尾->下一个=节点；尾=节点；}返回节点；}模板node_t*list_t::addinorder(T 数据){if (!cmp) {/* 验证比较函数不是 nullptr */std::cerr <<"错误:比较为空指针.\n";返回 nullptr；}node_t*节点=新节点_t；/* 分配/初始化节点 */节点->数据=数据；节点->下一个= nullptr;node_t**ppn = &head,/* ptr-to-ptr 到头 */*pn = 头；/* 指向头部的指针 */while (pn && cmp (node, pn) > 0) {/* 节点在当前之后排序 */ppn = &pn->next;/* ppn 到下一个地址 */pn = pn->下一个；/* 前进指针到下一个 */}节点->下一个= pn;/* 设置节点->next to next */如果(pn == nullptr)尾=节点；*ppn = 节点；/* 设置当前节点 */返回节点；/* 返回节点 */}模板void list_t::delnode (T 数据){node_t**ppn = &head;/* 指向节点的指针 */node_t*pn = 头；/* 指向节点的指针 */for (; pn; ppn = &pn->next, pn = pn->next) {如果(pn->数据==数据){*ppn = pn->下一个；/* 将地址设置为下一个 */删除 pn;休息;}}}模板void list_t<T>::prnlist (void){如果(！头){std::cout <<"空列表\n";返回;}for (node_t *pn = head; pn; pn = pn->next)std::cout <<" " <<pn->数据；std::cout <<'\n';}/* 将列表 l 拆分为列表 a &乙 */模板list_tlist_t<T>::split (void){list_ts;/* 类的新实例 */node_t*pa = head,/* 指向当前头部的指针 */*pb = pa->next;/* 第二个指向双进的指针 */while (pb) {/* 而不是列表结尾 */pb = pb->下一个；/* 推进第二个 ptr */if (pb) {/* 如果不是 nullptr */pa = pa->下一个；/* 推进当前的ptr */pb = pb->下一个；/* 再次推进第二个 ptr */}}s.tail = 尾巴;/* 第二个半尾将是当前尾 */尾巴 = pa;/* 当前尾部在 pa */s.head = pa->next;/* 第二个半头是下一个 ptr */pa->next = nullptr;/* 设置下一个 ptr NULL 以结束第一个 1/2 */返回 s;/* 返回新实例 */}/** 插入排序的链表.* 按排序顺序重新排序列表.*/模板void list_t<T>::insertionsort (void){node_t*sorted = head,/* 将排序列表初始化为第一个节点 */*pn = head->next;/* 将原始列表节点推进到下一个 */排序 -> 下一个 = NULL;/* 初始化 sorted-> NULL 旁边 */while (pn) {/* 从第二个节点迭代现有的 */node_t**pps = &sorted,/* ptr-to-ptr 到排序列表 */*ps = *pps,/* ptr 到排序列表 */*下一个= pn->下一个；/* 将下一个列表保存为单独的指针 */while (ps && cmp(ps, pn) <0) {/* 循环直到排序 */pps = &ps->next;/* 获取下一个节点的地址 */ps = ps->下一个；/* 获取下一个节点指针 */}*pps = pn;/* 按排序顺序插入现有的作为当前 */pn->next = ps;/* 将下一个设置为下一个排序 */pn = 下一个；/* 重新初始化指向 next 的现有指针 */}头 = 排序;/* 将头部更新为已排序的头部 *//* 设置尾指针指向排序后的最后一个节点 */for (pn = head; pn; pn = pn->next)尾巴 = pn;}/* FIXME 归并排序递归不起作用 */模板node_t*list_t::mergesorted (node_t *a, node_t *b){node_t*结果= nullptr;/* 基本情况 */如果一个)返回 (b)；否则如果(！b)退货(一)；/* 选择 a 或 b，然后重复 */如果 (cmp (a, b) <= 0) {结果 = 一个;结果->下一个=归并排序(a->下一个，b)；}别的 {结果 = b;结果->下一个=归并排序(a，b->下一个)；}返回结果；}/* 按排序顺序拆分和合并拆分 */模板void list_t<T>::mergesort_run (list_t<T> *l){/* 基本情况——长度为 0 或 1 */if (!l->head || !l->head->next) {返回;}/* 将头部拆分为 'a' 和 'b' 子列表 */list_tla = l->split();/* 递归排序子列表 */mergesort_run(l);mergesort_run(&la);/* 将两个排序列表合并在一起 */l->head = 归并排序 (l->head, la.head);}/* 包装到合并排序运行中的实际合并排序路由 */模板void list_t<T>::mergesort(void){合并排序运行(这个)；/* 将尾指针设置为排序后的最后一个节点 */for (node_t *pn = head; pn; pn = pn->next)尾巴 = pn;}int main (void) {list_t升；int arr[] = {12, 11, 10, 7, 4, 14, 8, 16, 20, 19,2、9、1、13、17、6、15、5、3、18}；无符号 asz = sizeof arr/sizeof *arr;for (unsigned i = 0; i 插入排序的结果 -- 预期结果
使用 -DISORT 编译以测试插入排序(工作):
$ ./bin/ll_merge_post12 11 10 7 4 14 8 16 20 19 2 9 1 13 17 6 15 5 3 181 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20归并排序的结果 -- 不好
$ ./bin/ll_merge_post12 11 10 7 4 14 8 16 20 19 2 9 1 13 17 6 15 5 3 180 16108560 16108656 16108688 16108560 16108816 16108784 16108848 16108752 16108720 16109072 16108976 16108944 16109008 16108880 16108912 16109136 16109104 16109168 16109040所以我被卡住了.(这可能很简单，我应该看到但没有看到)为什么子列表的合并失败?理解 C++ 中的类实例与我缺少的 C 结构处理的关键部分是什么?
在 mergesort_run 中，您有一个本地列表 la，其中包含一半的源列表.在函数结束时，您将 la 的内容合并回新列表，但变量本身仍指向您合并的节点.当 la 的析构函数运行时，这些节点将被删除.
如果在合并后将la的头节点设置为空指针(la.head = nullptr)，那么当析构函数运行时任何要删除的节点.
一个不相关的问题是，在创建新列表(如 split)时，您没有在某些地方复制 cmp.
I have been working on a templated implementation of a linked-list, on purpose, to reinvent the wheel, to stumble into just this type problem to help learn the subtle nuances of pointer to class instance handling. The problem I have stumbled into has to do with merging sublists where on the second merge (the first merge where sublists can have multiple nodes) fails where a prior class instance (either from split or mergesorted) appears to go out of scope (which should not have any affect on the merge as the pointer assignment is the a prior list that always remains in scope until after the assignment of the original list node has taken place)
The key here is that all class instances have pointers to the original nodes from the original list, so as long as the sublist instance remains in scope until the beginning node of the sublist is returned and assigned to the list in the previous recursion. I am trying to move a perfectly-good 100% working C implementation. So it is a problem with my understanding of why I cannot treat class instances as I would a struct in C that is the issue here -- but I cannot put my finger on documentation that explains why.
The class list_t contains the struct node_t to form the list.
/* linked list node */
template <class T>
struct node_t {
T data;
node_t<T> *next;
};
template <class T>
class list_t {
node_t<T> *head, *tail;
int (*cmp)(const node_t<T>*, const node_t<T>*);
public:
list_t (void); /* constructors */
list_t (int(*f)(const node_t<T>*, const node_t<T>*));
~list_t (void); /* destructor */
list_t (const list_t&); /* copy constructor */
/* setter for compare function */
,,,
list_t split (void); /* split list ~ 1/2 */
...
/* merge lists after mergesort_start */
node_t<T> *mergesorted (node_t<T> *a, node_t<T> *b);
void mergesort_run (list_t<T> *l); /* mergesort function */
void mergesort (void); /* wrapper for mergesort */
};
(yes I know no _t suffix, that's not the point here)
The split function is working fine and is:
/* split list l into lists a & b */
template <class T>
list_t<T> list_t<T>::split (void)
{
list_t<T> s; /* new instance of class */
node_t<T> *pa = head, /* pointer to current head */
*pb = pa->next; /* 2nd pointer to double-advance */
while (pb) { /* while not end of list */
pb = pb->next; /* advance 2nd ptr */
if (pb) { /* if not nullptr */
pa = pa->next; /* advance current ptr */
pb = pb->next; /* advance 2nd ptr again */
}
}
s.tail = tail; /* 2nd half tail will be current tail */
tail = pa; /* current tail is at pa */
s.head = pa->next; /* 2nd half head is next ptr */
pa->next = nullptr; /* set next ptr NULL to end 1st 1/2 */
return s; /* return new instance */
}
For the mergesort, I have a wrapper that calls the actual mergesort function mergesort_run. This was done so updating the tail pointer is only called after the sort completes, e.g.
/* wrapper to the actual mergesort routing in mergesort_run */
template <class T>
void list_t<T>::mergesort(void)
{
mergesort_run (this);
/* set tail pointer to last node after sort */
for (node_t<T> *pn = head; pn; pn = pn->next)
tail = pn;
}
mergesort_run is as follows:
/* split and merge splits in sort order */
template <class T>
void list_t<T>::mergesort_run (list_t<T> *l)
{
/* Base case -- length 0 or 1 */
if (!l->head || !l->head->next) {
return;
}
/* Split head into 'a' and 'b' sublists */
list_t<T> la = l->split();
/* Recursively sort the sublists */
mergesort_run(l);
mergesort_run(&la);
/* merge the two sorted lists together */
l->head = mergesorted (l->head, la.head);
}
The merge function, mergesorted merges the sublist in sort order:
template <class T>
node_t<T> *list_t<T>::mergesorted (node_t<T> *a, node_t<T> *b)
{
node_t<T> *result = nullptr;
/* Base cases */
if (!a)
return (b);
else if (!b)
return (a);
/* Pick either a or b, and recur */
if (cmp (a, b) <= 0) {
result = a;
result->next = mergesorted (a->next, b);
}
else {
result = b;
result->next = mergesorted (a, b->next);
}
return result;
}
Working C Implementation I am Moving From
Each of the above (other than me splitting out the initial wrapper) is an implementation from the following working C split/mergesort:
/* split list l into lists a & b */
void split (list_t *l, list_t *a)
{
node_t *pa = l->head,
*pb = pa->next;
while (pb) {
pb = pb->next;
if (pb) {
pa = pa->next;
pb = pb->next;
}
}
a->tail = l->tail;
l->tail = pa;
a->head = pa->next;
pa->next = NULL;
}
/* merge splits in sort order */
node_t *mergesorted (node_t *a, node_t *b)
{
node_t *res = NULL;
/* base cases */
if (!a)
return (b);
else if (!b)
return (a);
/* Pick either a or b, and recurse */
if (a->data <= b->data) {
res = a;
res->next = mergesorted (a->next, b);
}
else {
res = b;
res->next = mergesorted (a, b->next);
}
return res;
}
/* sorts the linked list by changing next pointers (not data) */
void mergesort (list_t *l)
{
list_t la;
node_t *head = l->head;
/* Base case -- length 0 or 1 */
if (!head || !head->next) {
return;
}
/* Split head into 'a' and 'b' sublists */
split (l, &la);
/* Recursively sort the sublists */
mergesort(l);
mergesort(&la);
/* answer = merge the two sorted lists together */
l->head = mergesorted (l->head, la.head);
/* set tail pointer to last node after sort */
for (head = l->head; head; head = head->next)
l->tail = head;
}
On 2nd Merge The Nodes From The 1st Merge Vanish
I have stepped through the C++ implementation with gdb and valgrind. In gdb the code will complete without error, but in valgrind you have the invalid read of 4 and 8 bytes after a block that has been freed suggesting the destructor is freeing memory (which it should) but that the pointer assignments done as the recursion unwinds has a dependence on the address of the pointer from the nested recursive call instead of just using the values at the address from the original (as the above C code does perfectly)
What is happening is that after the list is split down to sublists with a single node and the first merge takes place -- we are still good. When the next unwind happens where you would merge the combined node with another sublist -- the values of the 2-node sublist are lost. So after picking though the C and C++ implementations, I am feeiling like an idiot, because problems I could simply debug/correct in C I am missing some critial understanding that allows me to do the same with a C++ class implementation of the same code.
Test Code
int main (void) {
list_t<int> l;
int arr[] = {12, 11, 10, 7, 4, 14, 8, 16, 20, 19,
2, 9, 1, 13, 17, 6, 15, 5, 3, 18};
unsigned asz = sizeof arr / sizeof *arr;
for (unsigned i = 0; i < asz; i++)
l.addnode (arr[i]);
l.prnlist();
#ifdef ISORT
l.insertionsort();
#else
l.mergesort();
#endif
l.prnlist();
}
The beginning merge of the left-sublist after it is split down to nodes 12 and 11 goes fine. As soon as I go to merge the 11, 12 sublist with 10 -- the 11, 12 sublist values are gone.
MCVE
#include <iostream>
/* linked list node */
template <class T>
struct node_t {
T data;
node_t<T> *next;
};
/* default compare function for types w/overload (ascending) */
template <typename T>
int compare_asc (const node_t<T> *a, const node_t<T> *b)
{
return (a->data > b->data) - (a->data < b->data);
}
/* compare function for types w/overload (descending) */
template <typename T>
int compare_desc (const node_t<T> *a, const node_t<T> *b)
{
return (a->data < b->data) - (a->data > b->data);
}
template <class T>
class list_t {
node_t<T> *head, *tail;
int (*cmp)(const node_t<T>*, const node_t<T>*);
public:
list_t (void); /* constructors */
list_t (int(*f)(const node_t<T>*, const node_t<T>*));
~list_t (void); /* destructor */
list_t (const list_t&); /* copy constructor */
/* setter for compare function */
void setcmp (int (*f)(const node_t<T>*, const node_t<T>*));
node_t<T> *addnode (T data); /* simple add at end */
node_t<T> *addinorder (T data); /* add in order */
void delnode (T data); /* delete node */
void prnlist (void); /* print space separated */
list_t split (void); /* split list ~ 1/2 */
void insertionsort (void); /* insertion sort list */
/* merge lists after mergesort_start */
node_t<T> *mergesorted (node_t<T> *a, node_t<T> *b);
void mergesort_run (list_t<T> *l); /* mergesort function */
void mergesort (void); /* wrapper for mergesort */
};
/* constructor (default) */
template <class T>
list_t<T>::list_t (void)
{
head = tail = nullptr;
cmp = compare_asc;
}
/* constructor taking compare function as argument */
template <class T>
list_t<T>::list_t (int(*f)(const node_t<T>*, const node_t<T>*))
{
head = tail = nullptr;
cmp = f;
}
/* destructor free all list memory */
template <class T>
list_t<T>::~list_t (void)
{
node_t<T> *pn = head;
while (pn) {
node_t<T> *victim = pn;
pn = pn->next;
delete victim;
}
}
/* copy ctor - copy exising list */
template <class T>
list_t<T>::list_t (const list_t& l)
{
cmp = l.cmp; /* assign compare function ptr */
head = tail = nullptr; /* initialize head/tail */
/* copy data to new list */
for (node_t<T> *pn = l.head; pn; pn = pn->next)
this->addnode (pn->data);
}
/* setter compare function */
template <class T>
void list_t<T>::setcmp (int(*f)(const node_t<T>*, const node_t<T>*))
{
cmp = f;
}
/* add using tail ptr */
template <class T>
node_t<T> *list_t<T>::addnode (T data)
{
node_t<T> *node = new node_t<T>; /* allocate/initialize node */
node->data = data;
node->next = nullptr;
if (!head)
head = tail = node;
else {
tail->next = node;
tail = node;
}
return node;
}
template <class T>
node_t<T> *list_t<T>::addinorder (T data)
{
if (!cmp) { /* validate compare function not nullptr */
std::cerr << "error: compare is nullptr.\n";
return nullptr;
}
node_t<T> *node = new node_t<T>; /* allocate/initialize node */
node->data = data;
node->next = nullptr;
node_t<T> **ppn = &head, /* ptr-to-ptr to head */
*pn = head; /* ptr to head */
while (pn && cmp (node, pn) > 0) { /* node sorts after current */
ppn = &pn->next; /* ppn to address of next */
pn = pn->next; /* advance pointer to next */
}
node->next = pn; /* set node->next to next */
if (pn == nullptr)
tail = node;
*ppn = node; /* set current to node */
return node; /* return node */
}
template <class T>
void list_t<T>::delnode (T data)
{
node_t<T> **ppn = &head; /* pointer to pointer to node */
node_t<T> *pn = head; /* pointer to node */
for (; pn; ppn = &pn->next, pn = pn->next) {
if (pn->data == data) {
*ppn = pn->next; /* set address to next */
delete pn;
break;
}
}
}
template <class T>
void list_t<T>::prnlist (void)
{
if (!head) {
std::cout << "empty-list\n";
return;
}
for (node_t<T> *pn = head; pn; pn = pn->next)
std::cout << " " << pn->data;
std::cout << '\n';
}
/* split list l into lists a & b */
template <class T>
list_t<T> list_t<T>::split (void)
{
list_t<T> s; /* new instance of class */
node_t<T> *pa = head, /* pointer to current head */
*pb = pa->next; /* 2nd pointer to double-advance */
while (pb) { /* while not end of list */
pb = pb->next; /* advance 2nd ptr */
if (pb) { /* if not nullptr */
pa = pa->next; /* advance current ptr */
pb = pb->next; /* advance 2nd ptr again */
}
}
s.tail = tail; /* 2nd half tail will be current tail */
tail = pa; /* current tail is at pa */
s.head = pa->next; /* 2nd half head is next ptr */
pa->next = nullptr; /* set next ptr NULL to end 1st 1/2 */
return s; /* return new instance */
}
/** insertion sort of linked list.
* re-orders list in sorted order.
*/
template <class T>
void list_t<T>::insertionsort (void)
{
node_t<T> *sorted = head, /* initialize sorted list to 1st node */
*pn = head->next; /* advance original list node to next */
sorted->next = NULL; /* initialize sorted->next to NULL */
while (pn) { /* iterate over existing from 2nd node */
node_t<T> **pps = &sorted, /* ptr-to-ptr to sorted list */
*ps = *pps, /* ptr to sorted list */
*next = pn->next; /* save list next as separate pointer */
while (ps && cmp(ps, pn) < 0) { /* loop until sorted */
pps = &ps->next; /* get address of next node */
ps = ps->next; /* get next node pointer */
}
*pps = pn; /* insert existing in sort order as current */
pn->next = ps; /* set next as sorted next */
pn = next; /* reinitialize existing pointer to next */
}
head = sorted; /* update head to sorted head */
/* set tail pointer to last node after sort */
for (pn = head; pn; pn = pn->next)
tail = pn;
}
/* FIXME mergesort recursion not working */
template <class T>
node_t<T> *list_t<T>::mergesorted (node_t<T> *a, node_t<T> *b)
{
node_t<T> *result = nullptr;
/* Base cases */
if (!a)
return (b);
else if (!b)
return (a);
/* Pick either a or b, and recur */
if (cmp (a, b) <= 0) {
result = a;
result->next = mergesorted (a->next, b);
}
else {
result = b;
result->next = mergesorted (a, b->next);
}
return result;
}
/* split and merge splits in sort order */
template <class T>
void list_t<T>::mergesort_run (list_t<T> *l)
{
/* Base case -- length 0 or 1 */
if (!l->head || !l->head->next) {
return;
}
/* Split head into 'a' and 'b' sublists */
list_t<T> la = l->split();
/* Recursively sort the sublists */
mergesort_run(l);
mergesort_run(&la);
/* merge the two sorted lists together */
l->head = mergesorted (l->head, la.head);
}
/* wrapper to the actual mergesort routing in mergesort_run */
template <class T>
void list_t<T>::mergesort(void)
{
mergesort_run (this);
/* set tail pointer to last node after sort */
for (node_t<T> *pn = head; pn; pn = pn->next)
tail = pn;
}
int main (void) {
list_t<int> l;
int arr[] = {12, 11, 10, 7, 4, 14, 8, 16, 20, 19,
2, 9, 1, 13, 17, 6, 15, 5, 3, 18};
unsigned asz = sizeof arr / sizeof *arr;
for (unsigned i = 0; i < asz; i++)
l.addnode (arr[i]);
l.prnlist();
#ifdef ISORT
l.insertionsort();
#else
l.mergesort();
#endif
l.prnlist();
}
Result of Insertion Sort -- Expected Results
Compile with -DISORT to test insertion sort (working):
$ ./bin/ll_merge_post
12 11 10 7 4 14 8 16 20 19 2 9 1 13 17 6 15 5 3 18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Result of Mergesort -- Not Good
$ ./bin/ll_merge_post
12 11 10 7 4 14 8 16 20 19 2 9 1 13 17 6 15 5 3 18
0 16108560 16108656 16108688 16108560 16108816 16108784 16108848 16108752 16108720 16109072 16108976 16108944 16109008 16108880 16108912 16109136 16109104 16109168 16109040
So I'm stuck. (and it is probably something simple I should see but don't) Why is the merging of the sublists failing? What is the critical piece of understanding of class instance in C++ verses C struct handling I'm missing?
In mergesort_run, you have a local list la that contains half of your source list. At the end of the function you merge the content of la back into the new list, but the variable itself still points at the nodes you merged. When the destructor for la is run, these nodes will be deleted.
If you set the head node of la to a NULL pointer (la.head = nullptr) after doing the merge, then when the destructor runs there aren't any nodes for it to delete.
One unrelated issue is that you don't copy cmp in places when creating a new list (like split).
这篇关于链表合并排序的 C++ 实现在加入超过 1 个节点的子列表时失败的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
