C语言小秘密列表（一）

链接列表，这是学习C语言的人熟悉的概念. 许多研究了链表的人都觉得链表没有什么可担心的，但是如果您进入linux内核，那就去看看您必须对Linux内核中链表的实现感到惊奇. 有人可能认为Linux内核链表实现仅此而已，但是您必须知道，如果您以前从未见过这样的实现，那么您可以编写这样的链表吗？因此，在撰写链接列表文章时，我知道不是，我可能会用一篇文章来解释链接列表的知识点，因此我专门将其分为三部分（单链接列表，双链接列表，Linux内核链接列表，并且linux内核链接列表由于其特殊性而被单独取出，在后面让我们在博客中进行详细讨论），请尽可能使用简短的文本描述以及简单易懂的代码来解释请读者阅读我理解的清单，希望上述清单对您有所帮助. . 然后回到事实，开始我们的链表之旅.

本文的引用地址:

那么什么是链表？链表是物理存储单元上的非连续，非顺序存储结构. 数据元素的逻辑顺序是通过链接列表中的指针链接顺序实现的. 链表由一系列节点组成，即链表中的每个元素，并且可以在运行时动态生成节点. 每个节点由两部分组成: 一个是存储数据元素的数据字段，另一个是存储相邻节点地址的指针字段. 与线性表序列结构相比，链表更便于插入和删除操作.

对于链表，我们可以将它们分为单个链表，双链表和循环链表. 首先，让我们讨论单链列表.

所谓的单链表是指数据节点是单向排列的. 单个链表节点，其结构类型分为两部分:

1. 数据字段: 用于存储自己的数据

2. 指针字段: 用于存储下一个节点地址或指向其直接后继节点的指针.

如下所示:

注意: 如果图中有红色箭头，它将成为单向循环列表.

那么什么是双链表？双链表实际上是对单个链表的改进. 当我们对单链表进行操作时，有时当您要对节点的直接前体进行操作时，必须从表头开始. 这受到单链列表节点结构的限制. 因为单链列表的每个节点只有一个链接域，该链接域存储直接后继节点的地址，所以您能否定义一个链接域，该链接域既存储直接后继节点的地址，又存储存储直接后继节点的地址的链接域前任节点？双链域节点的结构是什么？这是一个双向链接列表.

在双向链表中，除了数据字段外，该节点还具有两个链字段. 一个存储直接后继节点地址，通常称为右链字段. 一个存储直接的前任节点地址，通常称为左链域.

如下所示:

注意: 如果图中有红色箭头，它将成为一个双向圆形链接列表.

阅读上面的介绍后，我认为读者对链接列表有一个大致的了解. 因此，我们的下一个任务是学习如何使用链表. 我们从最简单的代码开始，并教会读者学习使用链表. 首先，让我们看一下单个链表的创建. 为了便于说明，我将所有代码放入源文件中以执行. 当然，读者应该在实际编写代码的过程中使用头文件进行维护或读取，而不是在源文件中使用. 写到最后.

#include

#include

#include

#include

#define N 3

#undef _EXAM_ASSERT_TEST_ //禁用

//#定义_EXAM_ASSERT_TEST_ //启用

#ifdef _EXAM_ASSERT_TEST_ //启用断言测试

void assert_report（const char *文件名，const char *函数名，unsigned int line_no）

{

printf（“ \ n [EXAM]错误报告file_name: ％s，function_name: ％s，第％u \ n行，

文件名，函数名，行号）;

中止（）;

}

#define ASSERT_REPORT（条件）\

做{\

如果（条件）\

NULL; \

其他\

assert_report（__ FILE __，__ func __，__ LINE__）； \

}而（0）

#else //禁用断言测试

#define ASSERT_REPORT（条件）为空

#endif / * ASSERT结尾* /

typedef枚举_SListReturn

{

SLIST_RETURN_OK

} SListReturn;

typedef结构节点

{

字符名称[10];

int得分；

结构节点*链接;

}螺柱；

螺柱*创建（int n）

{

螺柱* p，* h，* s;

int i;

如果（（h =（stud *）malloc（sizeof（stud）））== NULL）

{

printf（“分配内存空间失败！”）；

退出（0）;

}

h->名称[0] ='\ 0';

h->分数= 0;

h->链接= NULL;

p = h;

对于（i = 0; i

{

如果（（s =（stud *）malloc（sizeof（stud）））== NULL）

{

printf（“分配内存空间失败！”）；

退出（0）;

}

p->链接= s;

printf（“请输入％d个人的名称: ”，i +1）；

scanf（“％s”，s->名称）；

printf（“请输入个人％d的等级: ”，i +1）；

scanf（“％d”和s->得分）；

s->链接= NULL;

p = s;

}

返回h;

}

SListReturn销毁（螺柱*头）

{

stud * tmp，* next;

tmp = head;

while（tmp！= NULL）

{

next = tmp->链接；

tmp->链接= NULL;

免费（tmp）;

tmp =下一个；

}

返回SLIST_RETURN_OK;

}

SList返回打印（螺柱*头）

{

螺柱* tmp = head->链接;

while（tmp！= NULL）

{

printf（“％s分数是％d \ t”，tmp->名称，tmp->分数）；

tmp = tmp->链接；

}

返回SLIST_RETURN_OK;

}

void main（）

{

int号；

螺柱*头;

number = N;

head = creat（number）;

ASSERT_REPORT（打印（标题）== SLIST_RETURN_OK）；

ASSERT_REPORT（毁灭（头部）== SLIST_RETURN_OK）；

}

运行结果为:

root @ ubuntu: / home / paixu#./tt

请输入第一个人的姓名: rewq

请输入第一人称分数: 123

请输入第二个人的姓名: fdsa

请输入第二人称分数: 456

请输入第三人的姓名: vcxz

请输入第三人的得分: 789

rewq得分是123 fdsa得分是456 vcxz得分是789

看看上面的代码，如果您之前已经阅读过我写的“ C Secrets的证书”，那么读者会知道，在这段代码的红色部分中，我们使用了自己的断言来学习，好，此处全部使用这里. 如果您尚未阅读本文，建议您阅读. 毕竟，断言仍然非常有用. 代码的蓝色部分也是一个特征点，因为过去我们可能在代码中返回了一些int值或NULL，因此代码的返回值无法直观地反映运行结果，并且使得代码可读性相对较差，因此为了改进我们的代码，我们必须学会自己定义返回类型，并尝试从各个方面尽可能地改进我们编写的代码. 在这里，我们使用枚举数据结构定义返回类型. 由于代码之间的关系，我在这里只使用了返回类型SLIST_RETURN_OK. 根据我的代码的需求，读者可以自己添加更多的返回值. 我只是这里有一个例子. 如:

typedef枚举_SListReturn

{

SLIST_RETURN_OK，

SLIST_RETURN_STOP，

SLIST_RETURN_FAIL

} SListReturn;

现在，我们从上述代码中选择一些代码以添加注释以进行解释.

螺柱* p，* h，* s; / * * h保存标头节点的指针，* p指向当前节点的前一个节点，* s指向当前节点* /

h->链接= NULL; / *清空头节点的链接字段* /

p = h; / * p指向头节点* /

p->链接= s; / *将s的地址分配给p指向的节点的链域，以使p和s指向的节点连接* /

除了在代码中创建链接列表的功能外，我们还使用两个函数，一个是SListReturn print（stud * head）函数，通过它我们可以打印出链接列表中的数据. 另一个函数是SListReturn destroy（stud * head），通过它释放应用的列表空间. 通过以上功能，我认为读者应该知道如何创建链表以及如何处理链表中的数据. 在这里，我只是打印数据. 如果读者有兴趣，可以执行其他操作.

上面的代码实现了单个链接列表的创建，但是链接列表的常见操作是搜索，插入c 链表，删除等. 这里没有解释. 删除操作类似于插入操作，因此在此不再一一解释. 这里我们以搜索并插入Explained为例，但是读者在编写删除操作时不要忘记释放已删除的节点. 接下来，让我们看一下搜索和插入操作.

代码功能是在找到的节点之后添加一个新节点.

#include

#include

#include

#include

#define N 3 / * N是人数* /

//#undef _EXAM_ASSERT_TEST_ //禁用

#define _EXAM_ASSERT_TEST_ //启用

#ifdef _EXAM_ASSERT_TEST_ //启用断言测试

void assert_report（const char *文件名，const char *函数名，unsigned int line_no）

{

printf（“ \ n [EXAM]错误报告file_name: ％s，function_name: ％s，第％u \ n行，

文件名，函数名，行号）;

中止（）;

}

#define ASSERT_REPORT（条件）\

做{\

如果（条件）\

NULL; \

其他\

assert_report（__ FILE __，__ func __，__ LINE__）； \

}而（0）

#else //禁用断言测试

#define ASSERT_REPORT（条件）为空

#endif / * ASSERT结尾* /

typedef枚举_SListReturn

{

SLIST_RETURN_OK，

} SListReturn;

typedef结构节点

{

字符名称[20];

int得分；

结构节点*链接;

}螺柱；

螺柱*创建（int n）

{

螺柱* p，* h，* s;

int i;

如果（（h =（stud *）malloc（sizeof（stud）））== NULL）

{

printf（“分配内存空间失败！”）；

退出（0）;

}

h->名称[0] ='\ 0'; / *清空标头节点的数据字段* /

h->分数= 0;

h->链接= NULL; / *清空头节点的链接字段* /

p = h; / * p指向头节点* /

对于（i = 0; i

{

如果（（s =（stud *）malloc（sizeof（stud）））== NULL）

{

printf（“分配内存空间失败！”）；

退出（0）;

}

p->链接= s; / *将s的地址分配给p指向的节点的链域，从而连接p和s指向的节点

printf（“请输入％d个人的名称: ”，i +1）；

scanf（“％s”，s->名称）； / *名称* /

printf（“请输入个人％d的等级: ”，i +1）；

scanf（“％d”和s->得分）； / *得分* /

s->链接= NULL;

p = s;

}

返回（h）;

}

螺柱*搜索（螺柱* h，char * x）/ *查找功能* /

{

螺柱* p;

char * y;

p = h->链接；

while（p！= NULL）

{

y = p->名称；

if（strcmp（y，x）== 0）

返回（p）;

else p = p->链接；

}

如果（p == NULL）

printf（“未找到数据！”）；

}

SListReturn insert（stud * p）/ *插入函数，在指针p之后插入* /

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-168476-1.html