c++ - 链表合并排序的 C++ 实现在加入超过 1 个节点的子列表时失败

Question

我一直致力于链表的模板化实现，目的是为了重新发明轮子，偶然发现这种类型的问题，以帮助了解指向类实例处理的指针的细微差别。我偶然发现的问题与合并子列表有关，其中第二次合并（子列表可以有多个节点的第一次合并）失败，其中先前的类实例（来自split或mergesorted）似乎超出范围（不应该有对合并的任何影响，因为指针分配是始终保持在范围内的先前列表，直到原始列表节点的分配发生之后）

这里的关键是所有类实例都有指向原始列表中原始节点的指针，因此只要子列表实例保持在作用域内，直到返回子列表的开始节点并分配给上一次递归中的列表。我正在尝试移动一个完美的 100% 工作 C 实现。所以我理解为什么我不能像对待 C 中的结构那样对待类实例是一个问题，这就是这里的问题——但我不能把手指放在解释原因的文档上。

该类list_t包含node_t形成列表的结构。

/* 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 */
};

（是的，我不知道_t后缀，这不是重点）

该split功能运行良好，并且是：

/* 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 */
}

对于归并排序，我有一个调用实际归并排序函数的包装器mergesort_run。这样做是为了更新tail指针仅在排序完成后调用，例如

/* 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如下：

/* 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);
}

合并函数，mergesorted按排序顺序合并子列表：

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; 
} 

工作中的 C 实现我正在迁移

以上每个（除了我拆分初始包装器）都是来自以下工作 C 拆分/合并排序的实现：

/* 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;
}

第 2 次合并第 1 次合并中的节点消失

我已经使用gdb和逐步完成了 C++ 实现valgrind。在gdb代码中将完成而没有错误，但是在valgrind一个已被释放的块之后您有 4 和 8 个字节的无效读取，这表明析构函数正在释放内存（它应该）但是在递归展开时完成的指针分配有一个依赖于来自嵌套递归调用的指针地址，而不是仅使用原始地址处的值（正如上面的 C 代码所做的那样）

正在发生的事情是，在列表被拆分为具有单个节点的子列表并发生第一次合并之后——我们仍然很好。当下一次展开发生时，您会将组合节点与另一个子列表合并 - 2 节点子列表的值将丢失。因此，在选择了 C 和 C++ 实现之后，我感觉自己像个白痴，因为我可以在 CI 中简单地调试/纠正的问题缺少一些重要的理解，这些理解允许我对相同代码的 C++ 类实现做同样的事情。

测试代码

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();
}

将左子列表拆分为节点后开始合并12并11正常运行。一旦我将11, 12子列表与10-合并，子11, 12列表值就消失了。

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();
}

插入排序的结果——预期结果

编译-DISORT以测试插入排序（工作）：

$ ./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

合并排序的结果——不好

$ ./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

所以我被困住了。（这可能是我应该看到但没有看到的一些简单的东西）为什么子列表的合并失败了？什么是对 C++ 中的类实例的关键理解与我缺少的 C 结构处理？

标签： c++templatesmergesort

Answer 1

在mergesort_run中，您有一个本地列表la，其中包含一半的源列表。在函数结束时，您将 的内容合并la回新列表，但变量本身仍指向您合并的节点。当la运行析构函数时，这些节点将被删除。

如果在合并后将头节点设置la为 NULL 指针 ( la.head = nullptr)，那么当析构函数运行时，没有任何节点可以删除。

cmp一个不相关的问题是您在创建新列表（如split）时不会在某些地方复制。