自学内容网 自学内容网
自学内容网 > 正文

单链表专题

🕗 发布于 2024-11-07 15:03 数据结构  

单链表

🔥 博客主页: 偷心编程
🎥 系列专栏: 《Java学习》 《C语言学习》 《数据结构C语言版》
❤️ 感谢大家点赞👍收藏⭐评论✍️
在这里插入图片描述
在这里插入图片描述

1. 链表的概念

  链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的 。

  链表也是线性表的一种，特点是：物理上不连续，逻辑上连续。

在这里插入图片描述

2. 链表的分类

1. 单向或者双向

在这里插入图片描述

2. 带头或者不带头

在这里插入图片描述

3. 循环或者非循环

在这里插入图片描述

当然了我们最常用的还是下面两种结构：

在这里插入图片描述

3. 实现无头单向非循环链表（单链表）

3.1 单链表的声明

typedef int SLTDataType;

typedef struct SListNode {
SLTDataType data;
struct SListNode* next;
}SListNode;

3.2 单链表的打印

//打印这个链表
void SListPrint(SListNode* phead) {
if (!phead) {
printf("NULL!链表为空!!!");
return;
}
while (phead) {
printf("%d ", phead->data);
phead = phead->next;
}
}

3.3 尾插

  1. 处理一般的单链表（链表不为空）
//尾插
void SListPushBack(SListNode* phead, SLTDataType x) {
//创建一个新的节点用来接收新的数据
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
newnode->data = x;
newnode->next = NULL;
//尾插，链表必须找尾
SListNode* ptail = phead;
while (ptail->next) {
ptail = ptail->next;
}
ptail->next = newnode;
return;
}
  1. 考虑链表为空的情况

错误示范

//尾插
void SListPushBack(SListNode* phead, SLTDataType x) {
//创建一个新的节点用来接收新的数据
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (!newnode) {
perror("malloc:");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//处理空链表的情况
if (!phead) {
phead = newnode; //我们要改变第一个节点（指向NULL）里面的内容，但是这是传值调用，无法再main里面改变，因此要传递地址，所以最终是二级指针
return ;
}
//尾插，链表必须找尾
SListNode* ptail = phead;
while (ptail->next) {
ptail = ptail->next;
}
ptail->next = newnode;
return;
}

正确示范

//尾插
void SListPushBack(SListNode** pphead, SLTDataType x) {
assert(pphead);
//创建一个新的节点用来接收新的数据
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (!newnode) {
perror("malloc:");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//处理空链表的情况
if (!*pphead) {
*pphead = newnode;
return ;
}
//尾插，链表必须找尾
SListNode* ptail = *pphead;
while (ptail->next) {
ptail = ptail->next;
}
ptail->next = newnode;
return;
}


//创建了节点(动态开辟了空间)就要给里面的元素初始化
/*SListNode* head = (SListNode*)malloc(sizeof(SListNode));
head->data = 2;
head->next = NULL;*/
//要么就不开辟空间
SListNode* head = NULL;

3.4 头插

  1. 可以跟尾插一样，分类讨论
//头插
void SListPushFront(SListNode** pphead, SLTDataType x) {
assert(pphead);
//创建一个新的节点用来接收新的数据
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (!newnode) {
perror("malloc:");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//处理空链表的情况
if (!*pphead) {
*pphead = newnode;
return;
}
//处理一般情况
newnode->next = *pphead;
*pphead = newnode;
}
  1. 也可以合并
//头插
void SListPushFront(SListNode** pphead, SLTDataType x) {
assert(pphead);
//创建一个新的节点用来接收新的数据
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (!newnode) {
perror("malloc:");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
newnode->next = *pphead;
*pphead = newnode;
}

3.5 尾删

//尾删
void SListPopBack(SListNode** pphead) {
assert(pphead);
//处理链表为空的情况
if (!*pphead) {
printf("链表为空，无法删除！");
return;
}
//处理只有一个节点的情况
if (!((*pphead)->next)) {
free(*pphead);
*pphead = NULL;
return;
}
//处理一般情况
//找倒数第二个节点和最后一个节点
SListNode* prev = *pphead;
SListNode* ptail = *pphead;
while (ptail->next) {
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
return;
}

3.6 头删

  1. 分类讨论
//头删
void SListPopFront(SListNode** pphead) {
assert(pphead);
//处理链表为空的情况
if (!*pphead) {
printf("链表为空，无法删除！");
return;
}
//处理只有一个节点的情况
if (!((*pphead)->next)) {
free(*pphead);
*pphead = NULL;
return;
}
//处理一般情况
SListNode* ptem = *pphead;
*pphead = (*pphead)->next;
free(ptem);
ptem = NULL;
}
  1. 合并
//头删
void SListPopFront(SListNode** pphead) {
assert(pphead);
//处理链表为空的情况
if (!*pphead) {
printf("链表为空，无法删除！");
return;
}
SListNode* ptem = *pphead;
*pphead = (*pphead)->next;
free(ptem);
ptem = NULL;
}

3.7 查找


//查找
SListNode* SListFind(SListNode* phead, SLTDataType x) {
while (phead) {
if (phead->data == x) {
return phead;
}
phead = phead->next;
}
printf("没有找到！");
return NULL;
}

3.8 在指定位置之前插入数据

  1. 给的pos是int
//在指定位置之前插入数据（默认链表不为空）
void SListInsert(SListNode** pphead, int pos, SLTDataType x) {
assert(pphead && (*pphead));
//创建一个新的节点用来接收新的数据
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (!newnode) {
perror("malloc:");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//处理在第一个节点的情况（说明是头插）,关键在于没有第pos-1个节点，所以要分类讨论
if (pos==1) {
SListPushFront(pphead, x);
return;
}
//处理一般情况
//找到第pos-1个节点
SListNode* prev = *pphead;
int i;
for (i = 0;i<pos-2; i++) {
prev = prev->next;
}
newnode->next = prev->next;
prev->next = newnode;
}
  1. 给的pos是一个指针
//在指定位置之前插入数据(默认链表不为空)
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x) {
assert(pphead && (*pphead));
//创建一个新的节点用来接收新的数据
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (!newnode) {
perror("malloc:");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//处理在第一个节点的情况（说明是头插）,关键在于没有第pos-1个节点，所以要分类讨论
if (pos==*pphead) {
SListPushFront(pphead, x);
return;
}
//处理一般情况
//找到第pos-1个节点
SListNode* prev = *pphead;
while (prev->next != pos) {
prev = prev->next;
}
newnode->next = prev->next;
prev->next = newnode;
}

3.9 在指定位置之后插入数据

  1. 给的pos是int
//在指定位置之后插入数据(默认链表不为空)
void SListInsertAfter(SListNode** pphead, int pos, SLTDataType x) {
assert(pphead && (*pphead));
//创建一个新的节点用来接收新的数据
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (!newnode) {
perror("malloc:");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//适用所有情况
//找到第pos个节点
SListNode* prev = *pphead;
int i;
for (i = 0; i < pos - 1; i++) {
prev = prev->next;
}
newnode->next = prev->next;
prev->next = newnode;
}
  1. 给的pos是一个指针
//在指定位置之后插入数据(默认链表不为空)
void SListInsertAfter( SListNode* pos, SLTDataType x) {
//创建一个新的节点用来接收新的数据
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (!newnode) {
perror("malloc:");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//适用所有情况
//找到第pos个节点
newnode->next = pos->next;
pos->next = newnode;
}

3.10 删除指定节点

//删除pos节点(默认链表不为空)
void SListErase(SListNode** pphead, SListNode* pos) {
//pos为第一个节点的情况
if (pos == *pphead) {
*pphead = pos->next;
free(pos);
pos = NULL;
return;
}
//处理一般情况
//找到第pos-1个节点
SListNode* pcur = *pphead;
while (pcur->next != pos) {
pcur = pcur->next;
}
pcur->next = pos->next;
free(pos);
pos = NULL;
}

//删除pos之后的节点
void SListEraseAfter(SListNode* pos) {
SListNode* ptem = pos->next;
pos = ptem->next;
free(ptem);
ptem = NULL;
}

3.11 销毁链表

//销毁链表
void SListDesTroy(SListNode** pphead) {
//处理一般情况
SListNode* pnext = (*pphead);
while (pnext) {
pnext = (*pphead)->next;
free(*pphead);
*pphead = pnext;
}
}

4. 一些细节

4.1 指针与二级指针

  若是涉及到我们需要改变头节点，也就是要改变head指针的内容的时候，我们就要传入二级指针（涉及到“头”的改变就要传二级指针）

4.2 创建一个获取节点的函数

//获取一个新的节点
SListNode* getNode(SLTDataType x) {
SListNode* node = (SListNode*)malloc(sizeof(SListNode));
if (!node) {
perror("malloc:");
exit(1);
}
node->data = x;
node->next = NULL;
return node;
}

4.3 单链表中可能需要分情况的点

  1. 链表为空链表或者非空链表
  2. 单链表只能由前一个节点得到下一个节点，因此在增 、删的时候prev节点很重要。由于这个特性，我们常常要就处理第一个节点的时候进行讨论（没有prev节点，这时候直接改变头结点）

4.4改变结构的处理顺序

  我们在处理问题的时候，无论是单链表还是双向链表，我们总是先改变外部结构（新创建的节点里面的数据），然后再改变我们原本的内部结构（改变链表内部节点的next指向或者数据等等）


原文地址：https://blog.csdn.net/2301_81375781/article/details/143381117

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024