【链表6】<最新>链表（link list） / 开普饭

文/Edward

回顾之前讲述的链接两个结构体节点的内容，我们可以简单的将一些存储对象数据的结构体变量链接到一起，然后再去通过next指针遍历整个数据链，这就类似于将一些毫无关联的结构体变量链接成了一个整体，这个整体就是链表。

我们之前讲述连接两个结构体这一章节的内容其实讲述了一个不完整的链表结构，不完整的地方在于，这种连接多个结构体变量的方式无法动态地去添加节点和删除节点，只能在有限的已经被定义的结构体变量中去做链接，本小节内容将会针对如何去动态创建链表节点，详细地阐述如何使用C语言中的链表。

链表的理想形态

我们到底需要一种怎么样的链表？这是首先需要讨论的问题。

一个链表的理想形态主要有以下几点：

链表的内存大小是动态的。当一个链表被创建时，如果没有存储任何内容，我们则希望这个链表最好不占用内存空间。
链表的节点可以自由删减。当我们需要向链表中存入一个数据时，这个链表的内存可以被动态增加以用于存放数据。当我们需要将链表中的某一个节点删除，这个链表的内存可以被动态地释放，防止无故坏死的内存块存在。
链表中的数据可以被检索，遍历。当我们需要在链表中查询某个元素的时候，链表可以快速地响应。
链表中的数据可以被快速插入。当我们需要向链表中某一个位置插入一个数据时，这个数据节点可以被快速地插入，而不需要像线性表一样，对整体数据进行移位，因为这会远远加重程序的时间复杂性。

基于上面我们所希望的一个链表所具有的特性，我们可以简单地画出链表的内存特征。我们先声明一个链表节点的结构体存储：

typedef struct Node{int data;struct Node *next;} Node_t;

当这个表示链表节点的结构体存储类型被申明好之后，我们就可以使用它去定义一个节点指针了，这个节点指针被定义好之后，应该将其指向NULL，防止其称为野指针。

Node_t *node;

注意，此时只不过是定义了一个节点指针，它本身没有指向任何内存。具体存储示意图如图1所示。

图1 链表初始节点

当我们定义和声明好之后一个初始化节点之后，尽管此时不存入任何数据，但是我们还是需要为这个节点分配一个内存，以准备任何时刻都有数据存储进来，而此时的next指针由于不指向任何内存，因此需要将其指向NULL。分配内存，还是使用我们之前讲述过的malloc函数。

node_t *ll_pt;ll_pt = (node_t *)malloc(sizeof(node_t));

此时，初始的链表节点就指向了一块内存了，如图2所示。此时，我们可以对这个节点中的data部分存入我们想要存入的数值，而next指针由于此时没有指向任何东西，所以需要将其指向到NULL。

图2 链表初始化

链表初始化完成之后就可以将数据存入链表里面了，还可以对这个链表再增加一个数据节点，增加的方式为，新建一个节点，将上一个节点的next指针指向这个节点，将这个新建的节点的next指针指向NULL。此时的内存分布如图3所示。

图3 链表指向新节点

链表操作

（1）初始化链表

初始化链表其实就是初始化链表的第一个节点，此时需要做的内容为：

创建一个结构体类型；

创建一个结构体指针作为链表的第一个节点；

为这个节点分配一块内存。

上述的操作代码如图4所示。

图4初始化链表节点

（2）创建并添加新节点

初始化链表之后，我们就可以对这个链表进行数据的存储了，先来做向后追加节点。向后追加节点的步骤很简单，即在一个函数里面声明一个节点，然后将初始化完成之后的头节点中的next指针指向这个新增的节点，而新增节点的next指针则指向NULL。代码如图5所示。

图5 向后追加新节点

这个函数我们还可以修改一下，在ll_append函数的形参列表中，加入需要追加的节点数据。同时，我们可以将链表初始化函数和节点追加函数进行统一，其思路为，判断传入的list变量是否为NULL，如果是NULL，则代表此时的链表还没有被初始化，进而进行初始化，否则只向这个链表添加节点。代码如图6所示。

图6 统一的链表初始化和追加数据函数

（3）遍历链表

此时，我们可以向这个链表里面添加数据了，添加完成数据之后，我们需要对这个链表进行遍历输出数据。

遍历的思路为，已知链表的第一个节点即为链表的起始处，且最后一个节点的next指针势必为NULL，那么我们只需要抓住这两点进行判断。定义一个遍历指针，先指向list处，接着打印其中的数据部份，打印完成后将这个指针指向它自己的next指针，如此循环，直至自己的next指针为NULL，则代表遍历结束。具体代码如图7所示。

图7 遍历链表

（4）释放链表

最后，链表使用完成之后需要释放，直接使用free函数，对节点遍历后，一个个释放即可。但需要注意的是，我们必须保证节点指针在被释放之前，next指针要指向下一个节点，直至next指针为NULL。

图8释放链表

本文源码

#include<stdio.h>#include<stdlib.h>/*声明一个链表节点*/typedef struct NODE{ int data; struct NODE *next;}node_t;

node_t * ll_init(void);node_t* ll_append(node_t *list, int data);int ll_seek(node_t *list);int ll_delete(node_t *list);

int main(void){ node_t *ll_pt = NULL; ll_pt = ll_append(ll_pt, 1000); ll_pt = ll_append(ll_pt, 2000); ll_pt = ll_append(ll_pt, 3000); ll_pt = ll_append(ll_pt, 4000); ll_pt = ll_append(ll_pt, 5000); ll_pt = ll_append(ll_pt, 6000); ll_pt = ll_append(ll_pt, 7000);

ll_seek(ll_pt); printf("\n Before free %d", ll_pt -> data); ll_delete(ll_pt); printf("\n After free %d", ll_pt -> data); return 0;}int ll_delete(node_t *list){ node_t *p, *pr; p = list; while(p != NULL) { pr = p; p = p -> next; free(pr); } return 1;}int ll_seek(node_t *list){ node_t *p; p = list; int i; while(p != NULL) { printf("%d:%d | ", i, p -> data); p = p -> next; i ++; } return 1;}node_t* ll_append(node_t *list, int data){ node_t *p = NULL, *head, *pr; head = list; p = (node_t *)malloc(sizeof(node_t)); if(p == NULL) { /*申请返回NULL，申请错误*/ } if(list == NULL) //如果此时的List为NULL，则对List进行初始化 { head = p; head->data = data; head->next = NULL; } else //否则，就追加新的节点 { pr = head; while(pr->next != NULL) //找到最后一个节点 { pr = pr -> next; } pr->next = p; //当前的next指针指向新节点 p->data = data; p->next = NULL; //新节点的next指针指向NULL } return head;}

【链表6】<最新>链表（link list）

相关推荐