目录
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
,表示链表已被销毁。