c - 将项目推送到链表 (C)

Question

我目前正在尝试将一个结构推送到列表中，事情是我必须在不使用标准库的情况下执行此操作(因此没有 malloc 或 calloc 等)。因此我有点挣扎，这就是我到目前为止所得到的。

typedef struct node node_t;
struct node{
    int val;
    node_t *next;
    node_t *prev;
};

node_t nodes[10];
node_t blocked[10];



void init(){
    for(int i = 0; i < 10; i++){
        nodes[i].val = i;
        if(i == 0){
            nodes[i].next = &nodes[i+1];
            nodes[i].prev = NULL;
        }
        else if(i == 9){
            nodes[i].next = NULL;
            nodes[i].prev = &nodes[i-1];
        }else{
            nodes[i].next = &nodes[i+1];
            nodes[i].prev = &nodes[i-1];
        }
    }
}


node_t *push(node_t **arr, node_t node){

node_t *newhead = &node;
printf("%d\n", newhead->val);
newhead->next = (*arr);
printf("%d\n", (*arr)->val);

return newhead; 
}

int main(){


    init();
    node_t *head = &nodes[0];


    node_t *blockhead = &blocked[0];
    blockhead = push(&blockhead,nodes[3]);
    blockhead = push(&blockhead,nodes[4]);


    return 0;
}

我遇到的问题是列表只跟踪我添加到列表中的最后一个元素，并且如果尝试访问列表中的下一个值将会崩溃，这可能意味着我正在尝试访问 NULL 指针但据我所知，一切似乎都是正确的，但也许我错过了一些非常明显的东西？整个“push”函数的要点是简单地将节点添加到列表的前面，先于其他所有节点。

Answer 1

您面临的直接问题是在此之前没有 node 声明:

node_t *newhead = &node;

您正在获取不存在的地址 - 这绝不是一个好主意(并且会调用未定义行为，并且通常会引发 SegFault)。

不需要全局声明节点，也不需要阻塞(基于您当前的代码)。避免使用全局变量。在 main() 中声明变量，并根据需要将变量(或指针)传递给任何函数。

如果您使用node_t类型的数组作为没有分配的链表，然后希望“push”(例如，在开头添加一个新的node_t作为新的列表地址)那么您实际上只需要让 newnode.next 指向您的 nodes 数组(因为数组的地址只是指向其的指针)第一个成员)，并且需要 array[0].prev 指向 newnode 的地址。

从你的问题中我可以了解到，代码的目的是练习指针理解。无论您处理的是存储在堆栈上的列表还是全局分配的列表，如果更改列表中的第一个节点，您都会更改列表地址(因为列表的开头是第一个节点的地址)为了更改函数内的列表地址，您必须将列表的地址作为参数传递给函数 - 或者 - 您返回指向新的第一个节点的指针并将地址分配给您的列表指针返回到调用者中。 (两者如下所示)

由于您想要将本地声明的节点“推送”到列表的头部，以类似的方式，您必须将该节点的地址传递给您的如果节点本身作为参数传递给推送函数，那么它会使用该节点的实际地址，而不是创建的节点副本的地址。您可以使用类似于以下内容的方法来执行此操作，以通过推送到列表头部的新节点将节点数组作为列表进行寻址:

/* push takes address of array and address of node as parameters */
node_t *push (node_t **arr, node_t *node)
{
    node->next = *arr;              /* next for new node is list address */
    (*arr)[0].prev = node;          /* prev for list is new node address */
    *arr = node;                    /* new node address is new list address */

    return node;                    /* return pointer to new 1st node */
}

上面您只需将 newnode->next 设置为当前列表地址，然后设置 list->prev 指向新节点，然后设置列表地址作为newnode的地址(还返回指向该地址的指针，可以根据需要在调用者中分配回该指针)。

其余的更改实际上只是对您所拥有的内容进行清理，根据需要向函数添加参数，以便可以在 main() 中正确声明节点 > 并添加一个 prn 函数来打印列表。另外，代码中没有使用魔数(Magic Number)。如果您需要一个(或多个)常量#define，或者使用全局enum来定义它们(这是全局的有效使用)。

总而言之，您可以执行以下操作:

#include <stdio.h>

#define LMAX 10         /* if you need a constant, define one */

typedef struct node {
    int val;
    struct node *prev, *next;
} node_t;

void init (node_t *nodes)
{
    for (int i = 0; i < LMAX; i++){
        nodes[i].val = i;
        if (i == 0)
            nodes[i].prev = NULL;
        else {
            nodes[i-1].next = &nodes[i];
            nodes[i].prev = &nodes[i-1];
        }
    }
}

/* push takes address of array and address of node as parameters */
node_t *push (node_t **arr, node_t *node)
{
    node->next = *arr;              /* next for new node is list address */
    (*arr)[0].prev = node;          /* prev for list is new node address */
    *arr = node;                    /* new node address is new list address */

    return node;                    /* return pointer to new 1st node */
}

/* simple print list */
void prn (node_t *list)
{
    for (; list; list = list->next)
        printf (" %d", list->val);
    putchar ('\n');
}

int main (void) {

    node_t nodes[LMAX],                 /* array of nodes */
        *head = nodes,                  /* list pointer */
        singlenode = { .val = LMAX };   /* new node to push */

    init(head);                 /* init list  */
    prn (head);                 /* print list */

    push (&head, &singlenode);  /* push new node to list */
    prn (head);                 /* print new list */

    return 0;
}

示例使用/输出

$ ./bin/lldblstatic
 0 1 2 3 4 5 6 7 8 9
 10 0 1 2 3 4 5 6 7 8 9

仔细检查，注意地址和指针的使用。如果您还有其他问题，请随时询问。