C语言中如何实现链表

C语言中如何实现链表

文章开头：

在C语言中，实现链表主要涉及以下几个步骤：定义链表的结点、创建链表、添加链表结点、删除链表结点、查找链表结点、打印链表和释放整个链表。我们以一个单链表为例，每一个结点包括两部分：一部分是数据域，存放元素的值；另一部分是指针域，存放下一个结点的地址。创建链表首先需要定义一个头结点来指明链表的头部，然后通过malloc函数依次申请结点的内存并赋值，同时将前一个结点的指针指向新的结点，以达到连接的效果。

正文：

一、定义链表的结点

在C语言中，我们可以通过定义结构体来实现链表节点。结构体允许我们集合不同类型的数据，对于链表节点，我们通常需要包括元素值（也被称为数据域）和指向下一节点的指针（也被称为指针域）。例如，我们可以定义一个简单的链表节点如下：

“`c

typedef struct Node {

int data;

struct Node *next;

} Node;

“`

在上述定义中，我们定义了一个名为Node的结构体，它包含了一个整型的数据和一个指向同样是Node类型的指针。同时我们也使用typedef给这个结构体类型起了别名Node，方便后续引用。

二、创建链表

在定义完链表节点之后，我们就可以开始创建链表了。一般我们会创建一个头结点来 represent 整个链表，这个头结点的数据域通常不存储有效信息，它的存在主要是方便我们对链表的操作，比如在链表的开头添加新节点，或者遍历整个链表。应创建链表的代码可以如下：

“`c

Node* createList() {

Node *head, *tAIl;

head = (Node*)malloc(sizeof(Node));

tail = head;

while (…) { // 这里可以根据实际需求进行循环，比如读取用户数据等

Node *new = (Node*)malloc(sizeof(Node));

tail->next = new;

tail = new;

}

tail->next = NULL; // 尾节点的next应该设置为NULL

return head;

}

“`

在此函数中，我们首先使用malloc函数申请了一个Node大小的内存空间作为头结点，并将tail指针指向头节点，然后在循环中不断输入新的节点，同时更新tail指针的位置。最后，将尾节点的next指针设置为NULL。

三、添加链表结点

添加链表结点，我们可以在链表的头部添加，也可以在尾部添加，甚至在链表的中间插入新的节点。以头部添加为例，可以有如下的代码：

“`c

void addAtHead(Node* head, int data) {

Node *new = (Node*)malloc(sizeof(Node));

new->data = data;

new->next = head->next;

head->next = new;

}

“`

在此函数中，我们首先申请了一个新的节点，并设置其data为传入的参数，然后将新节点的next指向原头节点的next，最后将头节点的next指向新节点，从而实现在链表头部添加新节点。

四、删除链表结点

删除链表结点需要分为两个步骤，找到要删除的结点以及删除结点。首先我们需要从头结点开始遍历整个链表，找到要删除的结点。然后，由于单链表的单向性，我们需要获取待删除结点的前一个结点，将其next指向待删除结点的next。注意，当所有的指针都不再指向一个内存空间后，这块内存空间就变成了孤儿，必须要手动释放，否则会造成内存泄露。

五、查找链表结点

查找链表节点，我们通常是知道节点的内容，然后遍历整个链表，当链表节点的数据域与我们的目标数据相等时，就找到了我们需要的链表节点。

六、打印链表

打印链表通常需要从头结点开始，逐个访问每个结点，并打印节点的数据域，直到遇到next指针为NULL的节点。

七、释放整个链表

最后，当我们不再需要这个链表时，我们需要逐个释放每个节点所占用的内存，避免产生内存泄露。释放链表可以从头结点开始，首先释放头节点的next节点，然后将头节点的next指向下一个节点，再释放该节点，以此类推，直到全部节点被释放。