1

我正在努力提高我的 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 个结构（带头和尾）。我的问题是，这是强制性的吗？我不能只用 1 个结构来实现它吗？

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

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

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

 temp = first

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

4）我们可以传递第一个或最后一个节点指针来删除整个列表对吗？（即遍历和删除顺序？）

谢谢！

4

2 回答 2

2

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 指针的双链表。而是做一个完整的圆圈。 Last->next = First. First->prev = Last. 然后代替 while 循环直到直到p->next == NULL，循环直到 p->next == first。该列表仅指向第一个节点（如果为空，则为 NULL）。我发现这种风格更灵活，*NULL 的变化更少。

第二范式转变。有时，双链表的唯一原因是允许将节点添加到开头或结尾。这可以通过一个next环绕圆圈的单个字段来完成。在这种情况下，列表指针不指向第一个节点，而是指向最后一个节点。（注意：first 是 last->next） 在开头或结尾插入是一样的，在 last 之后，first 之前添加一个节点。不同之处在于我们是保持列表指针不变，还是推进它。

于 2013-11-06T01:10:32.470 回答
1

1）没有必要有一个列表结构，但是如果结构跟踪某些元数据（例如列表的长度），它会使某些操作更快地执行，否则要获得长度，你必须每次都遍历你的列表这对于大型列表可能很昂贵）。

3）我假设你的意思是

temp = *first

并且 temp++ 不指向下一个节点，因为不能保证您的节点位于连续的内存地址中（另一方面，数组可以）。

4）您可以使用 first 或 last 删除列表，但您必须确保 head 的前一个也指向 NULL 的某个属性，否则您可能会陷入无限循环

于 2013-11-05T23:44:19.173 回答