c++ - 连接超过1个节点的子列表时，链表合并合并的C++实现失败-6ren

c++ - 连接超过1个节点的子列表时，链表合并合并的C++实现失败

转载作者：行者123 更新时间：2023-12-02 10:23:35

我一直在研究链表的模板化实现，目的是重新发明轮子，偶然发现这种类型的问题，以帮助学习指向类实例处理的指针的细微差别。我遇到的问题与合并子列表有关，在第二次合并(子列表可以具有多个节点的第一次合并)中，如果先前的类实例(来自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，我有一个包装器，调用了实际的mergesort函数 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和 valgrind逐步完成了C++实现。在 gdb中，代码将完整无误地完成，但是在 valgrind中，在释放了一个块之后，您有4字节和8字节的无效读取，这表明析构函数正在释放内存(应该释放)，但是在递归展开时完成指针分配依赖于嵌套递归调用中指针的地址，而不是仅仅使用原始地址中的指针值(如上述C代码完美地实现)

发生的事情是，在将列表拆分为具有单个节点的子列表并进行第一次合并之后，我们仍然很好。当下一次展开发生时，您将合并的节点与另一个子列表合并-2节点子列表的值将丢失。因此，在选择了C和C++实现之后，我感觉像个白痴，因为我可以简单地在C中调试/纠正问题，所以我缺少一些批判性的理解，这些理解使我可以对相同代码的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++的类实例理解的关键理解是什么？

最佳答案

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

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

一个不相关的问题是，在创建新列表(例如cmp)时，您不会在地方复制split。

关于c++ - 连接超过1个节点的子列表时，链表合并合并的C++实现失败，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57735047/

文章推荐： c++ - 用MinGW构建ASSIMP会导致文件太大错误

文章推荐： sql-server - 将SSRS中的多个值参数传递给存储过程

文章推荐： php - 自定义 Wordpress Woocommerce 帐单地址编辑表单

文章推荐： c++ - LeakSanitizer 和泄漏库

java - 自定义 JPA 实现//现有的无 SQL JPA 实现
背景: 我最近一直在使用 JPA，我为相当大的关系数据库项目生成持久层的轻松程度给我留下了深刻的印象。我们公司使用大量非 SQL 数据库，特别是面向列的数据库。我对可能对这些数据库使用 JPA 有一
java - 未由 S3FileSystem FileSystem 实现 Hadoop Jar 实现
我已经在我的 maven pom 中添加了这些构建配置，因为我希望将 Apache Solr 依赖项与 Jar 捆绑在一起。否则我得到了 SolarServerException: ClassNotF
c# - 实现 "Inherit"(实现)通用接口(interface)的接口(interface)？
interface ITurtle { void Fight(); void EatPizza(); } interface ILeonardo : ITurtle {
java - 任何 JPA 实现(或更广泛的 Java ORM 实现)是否支持可更新游标
我希望可用于 Java 的对象/关系映射 (ORM) 工具之一能够满足这些要求: 使用 JPA 或 native SQL 查询获取大量行并将其作为实体对象返回。允许在行(实体)中进行迭代，并在对当前
generics - 如果我为 B 实现 From ，是否也会为 Vec 实现 From>？
好像没有，因为我有实现From for 的代码, 我可以转换 A到 B与 .into() , 但同样的事情不适用于 Vec .into()一个Vec . 要么我搞砸了阻止实现派生的事情，要么这不应该发

c# - 在 C# 中，如果 A 实现 IX 并且 B 继承自 A ，是否必然遵循 B 实现 IX？
在 C# 中，如果 A 实现 IX 并且 B 继承自 A ，是否必然遵循 B 实现 IX？如果是，是因为 LSP 吗？之间有什么区别吗: 1. Interface IX; Class A : IX;

OpenVG 实现？
就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the

performance - 实现 (^)
我正在阅读标准haskell库的(^)的实现代码: (^) :: (Num a, Integral b) => a -> b -> a x0 ^ y0 | y0 a -> b ->a expo x0

博弈树的C++实现
我将把国际象棋游戏表示为 C++ 结构。我认为，最好的选择是树结构(因为在每个深度我们都有几个可能的移动)。这是一个好的方法吗？ struct TreeElement{ SomeMoveType

字符串匹配alg的c++实现
我正在为用户名数据库实现字符串匹配算法。我的方法采用现有的用户名数据库和用户想要的新用户名，然后检查用户名是否已被占用。如果采用该方法，则该方法应该返回带有数据库中未采用的数字的用户名。例子: “贾

图算法的C++实现
我正在尝试实现 Breadth-first search algorithm , 为了找到两个顶点之间的最短距离。我开发了一个 Queue 对象来保存和检索对象，并且我有一个二维数组来保存两个给定顶点

Python A* 实现
我目前正在 ika 中开发我的 Python 游戏，它使用 python 2.5 我决定为 AI 使用 A* 寻路。然而，我发现它对我的需要来说太慢了(3-4 个敌人可能会落后于游戏，但我想供应 4-

DHT的C++实现
我正在寻找 Kademlia 的开源实现C/C++ 中的分布式哈希表。它必须是轻量级和跨平台的(win/linux/mac)。它必须能够将信息发布到 DHT 并检索它。最佳答案 OpenDHT是

C++实现
我在一本书中读到这一行:-“当我们要求 C++ 实现运行程序时，它会通过调用此函数来实现。” 而且我想知道“C++ 实现”是什么意思或具体是什么。帮忙!？最佳答案 “C++ 实现”是指编译器加上链接

背包分支定界的C++实现
我正在尝试使用分支定界的 C++ 实现这个背包问题。此网站上有一个 Java 版本:Implementing branch and bound for knapsack 我试图让我的 C++ 版本打印

FNV哈希的C#实现
在很多情况下，我需要在 C# 中访问合适的哈希算法，从重写 GetHashCode 到对数据执行快速比较/查找。我发现 FNV 哈希是一种非常简单/好/快速的哈希算法。但是，我从未见过 C# 实现的

LRU缓存替换策略及C#实现
目录 LRU缓存替换策略核心思想不适用场景算法基本实现算法优化

大角度非迭代的空间坐标旋转C#实现
1. 绪论在前面文章中提到空间直角坐标系相互转换，测绘坐标转换时，一般涉及到的情况是：两个直角坐标系的小角度转换。这个就是我们经常在测绘数据处理中，WGS-84坐标系、54北京坐标系

实现.Net7下的数据库定时检查
在软件开发过程中，有时候我们需要定时地检查数据库中的数据，并在发现新增数据时触发一个动作。为了实现这个需求，我们在 .Net 7 下进行一次简单的演示. PeriodicTimer .

查找算法之二分查找的C++实现
二分查找二分查找算法，说白了就是在有序的数组里面给予一个存在数组里面的值key，然后将其先和数组中间的比较，如果key大于中间值，进行下一次mid后面的比较，直到找到相等的，就可以得到它的位置。

行者123

个人简介
我是一名优秀的程序员,十分优秀！

作者热门文章

html - 出于某种原因，IE8 对我的 Sass 文件中继承的 html5 CSS 不友好？

JMeter 在响应断言中使用 span 标签的问题

html - 在 :hover and :active? 上具有不同效果的 CSS 动画

html - 相对于居中的 html 内容固定的 CSS 重复背景？

滴滴打车优惠券免费领取

全站热门文章

【译】通过新的WinUI工作负荷和模板改进，深入原生Windows开发

Linux服务器磁盘空间占用情况分析与清理指南

一篇文章讲清楚synchronized关键字的作用及原理

HuggingChatmacOS版现已发布

WaterCloud：一套基于.NET8.0+LayUI的快速开发框架，完全开源免费！

枚举类型的基本用法（动手动脑）

PasteForm最佳CRUD实践，实际案例PasteTemplate详解之管理前端的代码(二)

零基础入门大语言模型

VulnStack-红日靶机二

三，MyBatis-Plus的各种查询的“超详细说明”，比如(等值查询，范围查询，模糊查询...)

首页

博学

6Ren·AI

商城

c++ - 连接超过1个节点的子列表时，链表合并合并的C++实现失败