首页 文章

c中的双链表实现

提问于
浏览
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并销毁 . 我在破坏清单方面遇到了一些麻烦 . 我知道我做错了,我会继续纠正它 .

3)我发现了节点指针

temp = first

指着一些地址 . 如果我做温度为什么不指向下一个节点?

4)我们可以传递第一个或最后一个节点指针来删除整个列表吗? (即遍历和dleete sequentialluy?)

谢谢!

2 回答

  • 1

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

    2)好主意InitList(),DestroyList(),AddNode,DeleteNode等 .

    您的初始化可能需要

    (*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 . 然后,而不是直到 p->next == NULL 的while循环,循环直到 p->next == first . 该列表只指向第一个节点(如果为空则为NULL) . 我发现这种风格更灵活,更少* NULL的变化 .

    第二范式转变 . 有时,双链接列表的唯一原因是允许在开头或结尾添加节点 . 这可以通过一个循环的单个 next 字段来完成 . 在这种情况下,列表指针不指向第一个节点,而是指向最后一个节点 . (注意:首先是last-> next)在开头或结尾插入是相同的,在最后一个之后和之前添加一个节点 . 不同之处在于我们将列表指针保持原样,还是将其推进 .

  • 1

    1)没有必要有一个列表结构,但如果结构跟踪某些元数据(例如,列表的长度,否则为了获得长度,你必须每次迭代列表),它会使某些操作更快地执行这对于大型列表而言可能很昂贵) .

    3)我假设你的意思

    temp = *first
    

    和temp没有指向下一个节点,因为它不能保证你的节点在连续的内存地址中(另一方面是数组) .

    4)你可以使用first或last来删除列表,但是你必须确保某个属性,即head的前一个也指向NULL,否则你可能陷入无限循环

相关问题