c - c中的双链表实现

Question

我正在努力提高我的 C 编程技能，因此开始尝试编写双链表。

这是我到目前为止的想法。

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//forward definition

typedef struct Node node_t;


//Define the structures needed for double linked list

//Each node
typedef struct Node 
{
        int data;
        node_t *next;
        node_t *prev;
}node_t;




void initList(node_t** first , node_t** last)
{
    //Allocate memory for the first and the last node

    *first = (node_t*) malloc(sizeof(node_t));
    *last =  (node_t*) malloc(sizeof(node_t));
    (*first)->data = 1;
    (*last)->data = 2;

    (*first)->prev = NULL;
    (*last)->next = NULL;

    (*first)->next = (*last)->prev;

    return;

}

void destroyList(node_t** first)
{
    node_t* temp;

    temp = *first;

    free((*first)->next);
    free((*first));
    temp = NULL;



    return;
}



int main()
{

    node_t *first =NULL, *last = NULL;

    printf("Initalizing the List\n");
    initList(&first,&last);

    printf(" 1st element is %d\n",first->data);
    printf(" 2nd element is %d\n",last->data);

    printf("Destroying the List\n");




    destroyList(&first) ;


    return 0;
}

我实际上在网上查找了一些代码，我看到大多数实现都有

1) Node 的 1 个结构和 List 本身的 1 个结构(有头和尾)。 我的问题是，这是强制性的吗？我不能只用一种结构来实现它吗？

2) 我的想法是将这个文件作为一个库并从应用程序中调用它。喜欢
InitList()、DestroyList()、AddNode、DeleteNode等

这就是为什么我对 INit 和销毁使用双指针。我在销毁列表时遇到了一些麻烦。我知道我做错了，我会继续改正。

3) 我找到了那个节点指针

 temp = first

指向某个地址。如果我做 temp++。为什么它不指向下一个节点？

4)我们可以通过第一个或最后一个节点指针来删除整个列表，对吗？。 (即遍历和删除 sequentialluy？)

谢谢!

Answer 1

1) Node 的 1 个结构和 List 本身的 1 个结构当然不是强制性的。通常用 1 个结构完成。

2) InitList()、DestroyList()、AddNode、DeleteNode 等好主意

你的init可能需要

(*first)->next = *last;
(*last)->prev = *first;
//  rather than
(*first)->next = (*last)->prev;

3) 作为@Jamil Seaidoun，不要执行temp++，而是执行temp = temp->next。

4) 你可以通过任何一端。经典问题是在 free()

之前没有得到下一个指针

// bad code
free(temp);
temp = temp->next;

// good code
next = temp->next;
free(temp);
temp = next;

---

杂谈

范式转变。考虑一个没有 NULL 指针的双链表。而是做一个完整的圆圈。 最后->下一个 = 第一个。 First->prev = Last。然后，代替直到 p->next == NULL 的 while 循环，循环直到 p->next == first。该列表仅指向第一个节点(如果为空，则指向 NULL)。我发现这种风格更灵活，*NULL 的变化更少。

第二次范式转换。有时，双链表的唯一原因是允许在开头或结尾添加节点。这可以通过围绕一个圆圈的单个 next 字段来完成。本例中的列表指针不指向第一个节点，而是指向最后一个节点。 (注意:first 是 last->next) 在开头或结尾插入是一样的，在 last 之后和 first 之前添加一个节点。不同之处在于我们是将列表指针保持原样，还是将其提前。