上回我们一起学习了线性表中的顺序表,今天我们将一起来学链表中的单链表。
链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车的某节车厢去掉/加上,不会影响其他车厢,每节车厢都是独立存在的,且每节车厢都有车门,你只能再火车上移动,车厢是独立存在的,只能从所以前面的车厢一节一节的往后走,从这节车尾到下节车头。
与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为“结点/节点”节点的组成主要有两个部分:当前节点要保存的数据和保存下?个节点的地址(指针变量)。 图中指针变量 plist保存的是第?个节点的地址,我们称plist此时“指向”第?个节点,如果我们希望plist“指向”第?个节点时,只需要修改plist保存的内容为0x0012FFA0。
链表中每个节点都是独立申请的(即需要插?数据时才去申请一块节点的空间),我们需要通过指针 变量来保存下?个节点位置才能从当前节点找到下?个节点。
//假设保存的是整型的数据类型
struct SListNode
{
int data; //节点数据
struct SListNode* next; //指针变量?保存下?个节点的地址
};
注意:1、链式机构在逻辑上是连续的,在物理结构上不一定连续2、节点?般是从堆上申请的3、从堆上申请来的空间,是按照?定策略分配出来的,每次申请的空间可能连续,可能不连续
具体我还是和上篇的顺序表一样写。大家测试的话,可以自己尝试
首先我们要写一个单链表,包含增删查改等操作。
我们先像上回的顺序表定义三个文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; //节点数据
struct SListNode* next; //指针保存下?个节点的地址
}SLTNode;
void SLTPrint(SLTNode* phead);
//头部插?删除/尾部插?删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插?数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插?数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);
我们逐步来实现
其实很简单,话不多说,直接上代码:
void SLTPrint(SLTNode* phead) {
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
就是检查每节”车厢“后面是否还有”车厢“,有的话就打印数据,没有的话就是NULL也就会停止。
SLTNode* SLTBuyNode(SLTDataType x) {
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
就是再火车前接上一节车厢。
本来有0,1,2,3四节车厢,现在再车头接上4这节车厢,过程如图:
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}
思路和头插差不多只不过这回是把新的车厢接到最后,过程如图
把新的4接到3后面,但是我们要考虑如果本来就是NULL的情况,所以代码示例:
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//链表为空,新节点作为phead
if (*pphead == NULL) {
*pphead = newnode;
return;
}
//链表不为空,找尾节点
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//ptail就是尾节点
ptail->next = newnode;
}
如果要避免问题,可以再头插也加上一个判断。不过那样的,我们不用下载写个插入,可以偷个懒,直接调用尾插,去给NULL加上数据,感兴趣的可以自己尝试。
有了前面的例子大家想必一下子就想到了写法,头删和尾删的过程如图:
头删就是把第一个节点销毁,尾删就是销毁最后一个节点,并将倒数第二个节点中的next指针,指向NULL
代码示例:
void SLTPopBack(SLTNode** pphead) {
assert(pphead);
//链表不能为空
assert(*pphead);
//链表不为空
//链表只有一个节点,有多个节点
if ((*pphead)->next == NULL) {
free(*pphead);
*pphead = NULL;
return;
}
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
//销毁尾结点
free(ptail);
ptail = NULL;
}
void SLTPopFront(SLTNode** pphead) {
assert(pphead);
//链表不能为空
assert(*pphead);
//让第二个节点成为新的头
//把旧的头结点释放掉
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
这个功能就比较有意思了,说白了就是遍历。就航向你去火车上找人一样,你如果不知道他再不在,你是不是得从车头一直往车走,然后一节车厢一节车厢地找他。所以代码写法很明了了。
代码示例:
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {
assert(pphead);
//遍历链表
SLTNode* pcur = *pphead;
while (pcur) //等价于pcur != NULL
{
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
完成字写我们可以加点难度了,我们要删除一个pos后的节点,我们该怎么办?
解决方法如图:
我们只需要,把pos->next改成pos->next->next,释放删除的空间,因为是pos后一个节点这里我们不用考虑如果只有一个节点的情况
代码示例:
void SLTEraseAfter(SLTNode* pos) {
assert(pos);
//pos->next不能为空
assert(pos->next);
//pos pos->next pos->next->next
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}
思路解析如图
我们只要把pos中pos->next给到上面的一个节点就行,但是,这回我们得讨论当只有一个节点的时候,这是我们可以直接调用头删。
代码示例:
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead);
assert(*pphead);
assert(pos);
//pos刚好是头结点,没有前驱节点,执行头删
if (*pphead == pos) {
//头删
SLTPopFront(pphead);
return;
}
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
也就是类似再某个数组的下标加上一个数据。
思路如图:
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
pos->next = newnode;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead);
assert(pos);
//要加上链表不能为空
assert(*pphead);
SLTNode* newnode = SLTBuyNode(x);
//pos刚好是头结点
if (pos == *pphead) {
//头插
SLTPushFront(pphead, x);
return;
}
//pos不是头结点的情况
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev -> newnode -> pos
prev->next = newnode;
newnode->next = pos;
}
我们都知道动态内存开辟后是一定要销毁的,那么单链表该怎么销毁呢?
这里我提供了一个方法:从头向尾一个一个节点遍历,释放空间
代码示例:
void SListDesTroy(SLTNode** pphead) {
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
注意:我这里定义了一个next来保存节点的地址,不可直接释放pcur不然你就找不到下一个节点了。
这篇我们简单了解了以下单链表,希望大家能够多多练习。
天气越来越冷了,注意保暖。