我正在努力提高我的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)Node的1个结构和List本身的1个结构当然不是强制性的 . 它通常用1个结构完成 .
2)好主意InitList(),DestroyList(),AddNode,DeleteNode等 .
您的初始化可能需要
3)作为@Jamil Seaidoun,不要
temp++
,而不是temp = temp->next
.4)你可以通过任何一端 . 经典问题是
free()
之前没有得到下一个指针漫记
模式转变 . 考虑一个没有NULL指针的双链接列表 . 而是制作完整的圆圈 .
Last->next = First
.First->prev = Last
. 然后,而不是直到p->next == NULL
的while循环,循环直到p->next == first
. 该列表只指向第一个节点(如果为空则为NULL) . 我发现这种风格更灵活,更少* NULL的变化 .第二范式转变 . 有时,双链接列表的唯一原因是允许在开头或结尾添加节点 . 这可以通过一个循环的单个
next
字段来完成 . 在这种情况下,列表指针不指向第一个节点,而是指向最后一个节点 . (注意:首先是last-> next)在开头或结尾插入是相同的,在最后一个之后和之前添加一个节点 . 不同之处在于我们将列表指针保持原样,还是将其推进 .1)没有必要有一个列表结构,但如果结构跟踪某些元数据(例如,列表的长度,否则为了获得长度,你必须每次迭代列表),它会使某些操作更快地执行这对于大型列表而言可能很昂贵) .
3)我假设你的意思
和temp没有指向下一个节点,因为它不能保证你的节点在连续的内存地址中(另一方面是数组) .
4)你可以使用first或last来删除列表,但是你必须确保某个属性,即head的前一个也指向NULL,否则你可能陷入无限循环