网站建设入门培训百度学术官网入口网页版
目录
1.链表的基本概念及结构
1.1基本概念
1.2结构
2.链表的分类
3.链表的实现（循环链表增删查改实现）
1.动态申请节点（结点）编辑
2.单链表打印
3.单链表尾插
4.单链表头插
5.单链表尾删
6.单链表头删
7.单链表查找
8.在指定位置之前插入数据
9.在指定位置之后插入数据
10.删除pos节点
11.删除pos之后的节点
12.销毁链表
1.链表的基本概念及结构
链表是一种常见的基础数据结构，它由一系列节点（Node）组成，每个节点包含数据和到下一个节点的引用（指针）。以下是链表的基本概念及其结构：
1.1基本概念
-
节点（Node）：链表的基本单元，每个节点包含两部分，一部分是存储数据的域（称为数据域），另一部分是存储下一个节点地址的域（称为指针域或链接域）。
-
头节点（Head）：链表的第一个节点，通常用于表示整个链表。
-
尾节点（Tail）：链表的最后一个节点，其指针域通常指向NULL，表示链表的结束。
-
链表的长度：链表中节点的数量。
-
链表的遍历：按照节点间的链接顺序访问链表中的每个节点。
-
动态性：链表的大小不是固定的，可以在运行时动态地增加或减少节点。
1.2结构
在C语言中，链表节点通常使用结构体（struct）来定义。以下是链表节点的一个基本结构：
链表的结构就像是火车一样一节一节的连在一起。
但是每个节点的地址并不像顺序表一样是连续的，而是随机存储的，因此每个节点才需要下一个节点的地址来找到下一节点。
2.链表的分类
-
单向链表（Singly Linked List）:
- 每个节点包含一个数据域和一个指向下一个节点的指针。
- 遍历链表只能从头节点开始，并且只能向一个方向进行。
-
双向链表（Doubly Linked List）:
- 每个节点包含一个数据域、一个指向前一个节点的指针和一个指向下一个节点的指针。
- 可以从两个方向遍历链表。
-
循环链表（Circular Linked List）:
- 单向链表的变种，最后一个节点的指针指向头节点，形成一个环。
- 可以从任意节点开始遍历整个链表。
-
双向循环链表（Doubly Circular Linked List）:
- 双向链表的变种，头节点的前一个指针指向最后一个节点，最后一个节点的下一个指针指向头节点，形成一个环。
- 可以从任意节点开始，向前或向后遍历整个链表。
3.链表的实现（循环链表增删查改实现）
1.动态申请节点（结点）
-
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));：使用malloc函数动态分配一个SLTNode大小的内存块，并将其强制转换为SLTNode*类型的指针。sizeof(SLTNode)获取SLTNode结构体的大小。 -
if (newnode == NULL)：检查malloc是否成功分配了内存。如果newnode是NULL，说明内存分配失败。 -
perror("malloc fail!");：如果内存分配失败，使用perror函数打印错误消息。 -
exit(1);：如果内存分配失败，终止程序执行，返回错误代码1。 -
newnode->data = x;：将传入的参数x赋值给新节点的数据域。 -
newnode->next = NULL;：将新节点的指针域初始化为NULL，表示当前节点后面没有其他节点。 -
return newnode;：返回新创建的节点。
2.单链表打印
3.单链表尾插
-
assert(pphead);：使用assert宏来确保传入的头节点指针的指针不是NULL。如果pphead是NULL，程序将终止执行。 -
SLTNode* newnode = SLTBuyNode(x);：调用之前定义的SLTBuyNode函数来创建一个新的节点，并将数据x存储在新节点的数据域。 -
if (*pphead == NULL)：检查链表是否为空。如果链表为空（即头节点指针为NULL），则将新节点设置为头节点。 -
else：如果链表不为空，则需要找到链表的最后一个节点。 -
SLTNode* ptail = *pphead;：初始化一个指针ptail，指向头节点。 -
while (ptail->next)：遍历链表，直到找到最后一个节点（即节点的next指针为NULL）。 -
ptail = ptail->next;：在循环中，将ptail移动到下一个节点。 -
ptail->next = newnode;：当找到最后一个节点时，将其next指针指向新创建的节点，从而将新节点添加到链表的末尾。
4.单链表头插
-
assert(pphead);：使用assert宏来确保传入的pphead不是NULL。如果pphead是NULL，程序将在这里终止。 -
SLTNode* newnode = SLTBuyNode(x);：调用SLTBuyNode函数创建一个新的节点，并将数据x存储在新节点的数据域中。 -
newnode->next = *pphead;：将新节点的next指针指向原来的头节点。这一步是为了将新节点插入到链表的头部。 -
*pphead = newnode;：更新头节点指针，使其指向新创建的节点。这样，新节点就成为了链表的新头部。
5.单链表尾删
这个接口的实现一开始先要判断链表是否为单节点链表，如果是则直接释放头节点，不是则进行相应的操作。
-
assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。 -
if ((*pphead)->next == NULL)：检查链表是否只有一个节点。如果是，直接释放这个节点，并将头节点指针设置为NULL。 -
else：如果链表有多个节点，需要遍历链表找到最后一个节点。 -
while (ptail->next)：遍历链表直到ptail指向最后一个节点。 -
free(ptail);：释放最后一个节点的内存。 -
ptail = NULL;：将ptail指针设置为NULL，防止野指针。 -
prev->next = NULL;：将倒数第二个节点的next指针设置为NULL，断开与已删除节点的连接。
6.单链表头删
这里的(*pphead)->next不能写成*pphead->next 因为->预算符优先级是高于*的。
-
assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。 -
SLTNode* next = (*pphead)->next;：保存头节点的下一个节点指针。这是因为一旦释放头节点，我们就无法访问链表的其余部分。 -
free(*pphead);：释放头节点的内存。 -
*pphead = next;：更新头节点指针，使其指向原来的第二个节点（现在成为新的头节点）。
7.单链表查找
-
assert(phead);：使用assert宏来确保传入的phead不是NULL。如果phead是NULL，程序将在这里终止。 -
SLTNode* plist = phead;：初始化一个指针plist，使其指向头节点。 -
while (plist)：开始循环，当plist不为NULL时继续执行。 -
if (plist->data == x)：检查当前节点的数据是否与要查找的值x匹配。 -
return plist;：如果找到匹配的节点，返回该节点。 -
plist = plist->next;：如果没有找到匹配的节点，移动plist到下一个节点。 -
return NULL;：如果在链表中没有找到匹配的节点，返回NULL。
8.在指定位置之前插入数据
9.在指定位置之后插入数据
-
assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。 -
assert(pos);：使用assert宏来确保传入的pos不是NULL。如果pos是NULL，程序将在这里终止。 -
SLTNode* newnode = SLTBuyNode(x);：调用SLTBuyNode函数创建一个新的节点，并将数据x存储在新节点的数据域中。 -
if (pos == *pphead)：检查插入的位置是否是头节点。如果是，使用SLTPushFront函数在头节点位置插入新节点。 -
else：如果插入的位置不是头节点，需要找到pos的前一个节点。 -
SLTNode* prev = *pphead;：初始化prev指针指向头节点。 -
while (prev->next != pos)：遍历链表直到找到pos的前一个节点。 -
newnode->next = pos;：将新节点的next指针指向pos。 -
prev->next = newnode;：将pos的前一个节点的next指针指向新节点。
10.删除pos节点
-
assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。 -
assert(pos);：使用assert宏来确保传入的pos不是NULL。如果pos是NULL，程序将在这里终止。 -
if (pos == *pphead)：检查要删除的节点是否是头节点。如果是，使用SLTPopFront函数执行头删操作。 -
else：如果要删除的节点不是头节点，需要找到该节点的前一个节点。 -
SLTNode* prev = *pphead;：初始化prev指针指向头节点。 -
while (prev->next != pos)：遍历链表直到找到pos的前一个节点。 -
prev->next = pos->next;：将pos的前一个节点的next指针指向pos的下一个节点，完成删除操作。 -
free(pos);：释放pos节点的内存。 -
pos = NULL;：将pos指针设置为NULL，防止野指针。
11.删除pos之后的节点
-
assert(pos);：使用assert宏来确保传入的pos不是NULL。如果pos是NULL，程序将在这里终止。 -
SLTNode* newnode = SLTBuyNode(x);：调用SLTBuyNode函数创建一个新的节点，并将数据x存储在新节点的数据域中。 -
newnode->next = pos->next;：将新节点的next指针指向pos的下一个节点，这样新节点就位于pos的后面。 -
pos->next = newnode;：将pos的next指针指向新节点，完成新节点的插入操作。
12.销毁链表
-
assert(pphead && *pphead);：使用assert宏来确保传入的pphead不是NULL，且链表不为空。如果这些条件不满足，程序将在这里终止。 -
SLTNode* pcur = *pphead;：初始化一个指针pcur，使其指向头节点。 -
while (pcur)：开始循环，当pcur不为NULL时继续执行。 -
SLTNode* next = pcur->next;：保存pcur的下一个节点的指针，因为pcur将被释放。 -
free(pcur);：释放pcur节点的内存。 -
pcur = next;：移动pcur指针到下一个节点。 -
*pphead = NULL;：循环结束后，将头指针设置为NULL，表示链表已被销毁。