在链表中插入节点-Java 学习之路

我试图在两个索引之间动态插入一个节点，这两个索引包含Node类型的结构 . 数组中的第一个元素是头指针，第二个元素是尾 .

我正在尝试动态增长数组的两个索引之间的双链表 . 以下是我到目前为止尝试过的代码 .

我可以动态地创建头部和尾部作为节点，但是根据我要求我这样做 .

保证在 qllentry[0].data 和 qllentry[1].data 的值之间插入 data 值的节点是保证的

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct Node {
    int data;
    struct Node *qprev;
    struct Node *qnext;
}Node;

struct Node qllentry[2];


int main()
{

struct Node head, tail;
    head.data = INT_MAX;
    tail.data = INT_MIN;

    head.qnext = &tail;
    tail.qprev = &head;
    head.qprev = NULL;
    tail.qnext = NULL;


    qllentry[0] = head;
    qllentry[1] = tail;
    int key = 20;
    struct Node *curr ;
    struct Node *prev;
    curr= &qllentry[0];

    while(curr->qnext != NULL && curr->data >= key) {
                curr = curr->qnext;
        }
    prev = curr->qprev;

    struct Node *new_node = (struct Node*)malloc(sizeof(struct Node));
        new_node->data = key;
        new_node->qnext = prev->qnext;
        prev->qnext = new_node;
        new_node->qprev = prev;
        if (new_node->qnext != NULL)
            new_node->qnext->qprev = new_node;


    return 0;
}

正如预期的那样，新节点的插入不会发生在头部和尾部索引之间 . 我添加了一些用于调试的print语句

任何帮助表示赞赏 .

2 回答

虽然保持指向列表头部和尾部的数组（或者指针）是没有错的，但如果使用数组，则在分配地址 keep your array references out of your list operations 之后 . 将 &array[x] 与列表操作混合使用只会引起混淆 . 使用列表时，将其视为列表并忘记数组 .

您的主要问题是迭代一个节点到远处寻找插入 new_node 的位置，导致您在停止之前迭代到 tail . 在 node before 上插入 new_node 停止迭代 . 你通过测试来做到这一点：

/* test curr->qnext->data > key to stop before tail */
    while (curr->qnext && curr->qnext->data > key)
                curr = curr->qnext;

（ note: 使用 prev = curr->qprev; 旁边的变量进行间接屏蔽级别的隐藏级别只是隐藏细节 - 这可能会在以后增加混乱 . 这是完全合法的，但可以谨慎使用......）

现在，您可以集中精力在 &head 和 &tail 之间插入 new_node .

在任何列表插入中，只需 re-wiring 指向当前节点的指针 - >下一个指向 new_node ，指向下一个节点的指针 - > prev指向 new_node . 要完成插入， new_node->qprev 指向 curr 和 new_node->qnext 指向 curr->next ，例如

new_node->qprev = curr;         /* rewire pointers */
    new_node->qnext = curr->qnext;
    curr->qnext->qprev = new_node;
    curr->qnext = new_node;

（ note: 解决这个问题的简单方法是拉一张纸和一支2号铅笔，为 new_node 绘制一个块 tail ，然后为 tail 绘制一个块，然后为prev / next指针绘制线条没有 new_node 并且带有它的列表 . 然后，在逻辑笔直的情况下，坐下来键盘并将其啄出来 . ）

此外，您必须 always validate 您的分配，例如

/* allocate and VALIDATE! */
    if (!(new_node = malloc (sizeof *new_node))) {
        perror ("malloc - new_node");
        exit (EXIT_FAILURE);
    }

在您编写的任何动态分配内存的代码中，您对分配的任何内存块都有2个职责：（1）始终保留指向内存块起始地址的指针，因此，（2）当它为no时可以释放它需要更久 . 因此，如果您分配它，请在完成后跟踪指向块的指针和 free . 例如，当完成输出列表值（或在专用循环中）时，您可以释放您分配的内存，类似于：

curr = &head;                   /* output list */
    while (curr) {
        printf ("%d\n", curr->data);
        struct Node *victim = curr; /* self-explanatory */
        curr = curr->qnext;
        /* do not forget to free allocated memory */
        if (victim != &head && victim != &tail) {
            free (victim);
        }
    }

完全放在一起，您可以执行以下操作：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct Node {
    int data;
    struct Node *qprev;
    struct Node *qnext;
} Node;

struct Node qllentry[2];


int main (void) {

    struct Node head = { .data = INT_MAX }, 
                tail = { .data = INT_MIN },
                *curr,
                *new_node;

    qllentry[0] = head;     /* keep your array and list operations separate */
    qllentry[1] = tail;

    head.qnext = &tail;     /* begin list operations */
    tail.qprev = &head;

    int key = 20;

    curr = &head;

    /* test curr->qnext->data > key to stop before tail */
    while (curr->qnext && curr->qnext->data > key)
                curr = curr->qnext;

    /* allocate and VALIDATE! */
    if (!(new_node = malloc (sizeof *new_node))) {
        perror ("malloc - new_node");
        exit (EXIT_FAILURE);
    }

    new_node->data = key;           /* assign value to new_node */

    new_node->qprev = curr;         /* rewire pointers */
    new_node->qnext = curr->qnext;
    curr->qnext->qprev = new_node;
    curr->qnext = new_node;

    curr = &head;                   /* output list */
    while (curr) {
        printf ("%d\n", curr->data);
        struct Node *victim = curr; /* self-explanatory */
        curr = curr->qnext;
        /* do not forget to free allocated memory */
        if (victim != &head && victim != &tail) {
            free (victim);
        }
    }

    return 0;
}

Example Use/Output

$ ./bin/llarray
2147483647
20
-2147483648

Memory Use/Error Check

您必须使用内存错误检查程序，以确保您不会尝试访问内存或写入超出/超出已分配块的范围，尝试读取或基于未初始化值的条件跳转，最后，确认你释放了你分配的所有内存 .

对于Linux valgrind 是正常的选择 . 每个平台都有类似的记忆检查器 . 它们都很简单易用，只需通过它运行程序即可 .

$ valgrind ./bin/llarray
==8665== Memcheck, a memory error detector
==8665== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==8665== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==8665== Command: ./bin/llarray
==8665==
2147483647
20
-2147483648
==8665==
==8665== HEAP SUMMARY:
==8665==     in use at exit: 0 bytes in 0 blocks
==8665==   total heap usage: 1 allocs, 1 frees, 24 bytes allocated
==8665==
==8665== All heap blocks were freed -- no leaks are possible
==8665==
==8665== For counts of detected and suppressed errors, rerun with: -v
==8665== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

始终确认已释放已分配的所有内存且没有内存错误 .

Simple Pointer Dump/Check

最后，除了使用调试器逐步调试地址之外，您还可以编写一个简短的调试路由，以帮助您选择是否以及在哪里，您的指针处理有任何问题 . （你根本不需要输出任何内容，如果你愿意的话，你可以用相等的方法检查地址）这可以让你一次查看所有指针 . 只需输出节点指针的简单路由通常很有帮助 . 你所需要的只是，例如，

void debugptrs (struct Node *list)
{
    printf ("list pointers:\n\n");
    for (struct Node *iter = list; iter; iter = iter->qnext)
        printf ("prev: %16p    curr: %16p    next: %16p\n", 
                (void*)iter->qprev, (void*)iter, (void*)iter->qnext);
    putchar ('\n');
}

这将提供类似于以下的输出：

$ ./bin/llarray
list pointers:

prev:            (nil)    curr:   0x7ffd56371910    next:        0x1038010
prev:   0x7ffd56371910    curr:        0x1038010    next:   0x7ffd56371930
prev:        0x1038010    curr:   0x7ffd56371930    next:            (nil)

我总是觉得从头到尾可视地遍历地址是有帮助的 . 如果节点的任何prev或next不是作为前一行（或下一行）上该节点的地址输出的内容，则您知道问题所在 .

仔细看看，如果您有其他问题，请告诉我 .

回复于 2024-04-29T10:33:37+08:00

以下是基于代码的一些修改代码问题，它按预期打印结果我猜：

dlink.c:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct Node {
    int data;
    struct Node *qprev;
    struct Node *qnext;
} Snode;

int main() {
    struct Node *head = (struct Node*)malloc(sizeof(struct Node));
    struct Node *tail = (struct Node*)malloc(sizeof(struct Node));

    // init head,
    head->data = INT_MAX;
    head->qnext = tail;
    head->qprev = NULL;

    // init tail,
    tail->data = INT_MIN;
    tail->qprev = head;
    tail->qnext = NULL;

    int key = 20;
    struct Node *curr = head;
    struct Node *prev;

    //get the pointer of the process which has less priority than the current process
    while(curr->data >= key && curr->qnext != NULL) {
        curr = curr->qnext;
    }
    prev = curr->qprev;

    printf("head %p, data is %d, next is %p, prev is %p\n", head, head->data, (void *)head->qnext, (void *)head->qprev);
    printf("tail %p, data is %d, next is %p, prev is %p\n", tail, tail->data, (void *)tail->qnext, (void *)tail->qprev);
    printf("prev of new node %p, data is %d, next is %p, prev is %p\n", prev, prev->data, (void *)prev->qnext, (void *) prev->qprev);
    printf("--------------------\n\n");

    struct Node *new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = key;
    new_node->qnext = prev->qnext;
    prev->qnext = new_node;
    new_node->qprev = prev;

    if (new_node->qnext != NULL)
        new_node->qnext->qprev = new_node;
    else
        tail = new_node;

    printf("head %p, data is %d, next is %p, prev is %p\n", head, head->data, (void *)head->qnext, (void *)head->qprev);
    printf("new_node %p, data is %d, next is %p, prev is %p\n", new_node, new_node->data, (void *)new_node->qnext, (void *)new_node->qprev);
    printf("tail %p, data is %d, next is %p, prev is %p\n", tail, tail->data, (void *)tail->qnext, (void *)tail->qprev);

    return 0;
}

The running result:

head 0x2380010, data is 2147483647, next is 0x2380030, prev is (nil)
tail 0x2380030, data is -2147483648, next is (nil), prev is 0x2380010
prev of new node 0x2380010, data is 2147483647, next is 0x2380030, prev is (nil) // this is same as head,
--------------------

head 0x2380010, data is 2147483647, next is 0x2380460, prev is (nil)
new_node 0x2380460, data is 20, next is 0x2380030, prev is 0x2380010
tail 0x2380030, data is -2147483648, next is (nil), prev is 0x2380460

Suggestions

唐't mix struct (head, tail) & struct pointer (new_node), it'令人困惑，容易犯错误 .
单个链表可能就足以进行这样的插入，在单个链表中插入元素有一种棘手的方法 .
为了获得良好的性能，您可以分配一个大缓存，然后从缓存中创建新节点 .
编译c代码时，添加 -Wall 选项，这将为您提供更多警告 .

回复于 2024-04-29T10:33:37+08:00

在链表中插入节点

2 回答

相关问题