食用指南:本文在有C基础的情况下食用更佳
🔥这就不得不推荐此专栏了: C语言
♈️今日夜电波: あなたは煙草 私はシャボン——今泉愛夏
1:31 ━━━━━━️💟──────── 4:36
🔄 ◀️ ⏸ ▶️ ☰
💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍
目录
一、单链表介绍
单链表是什么?
单链表需要实现的基本功能?
单链表的基本结构是怎么样的?
二、总体思路
结构体定义
接口函数定义
三、具体每个接口函数的实现
1、打印
2、申请新的节点
3、尾插
4、头插
5、尾删
6、头删
7、找节点(用于后续的插入以及删除操作)
8、基于第7小点在pos之前插入x
9、基于第7小点在pos以后插入x
10、基于第7小点删除pos位置
11、基于第7小点删除pos的后一个位置
12、销毁链表,释放空间
四、总体代码
1、头文件
2、主体函数文件
3、测试用例
一、单链表介绍
单链表是什么?
单链表是一种常见的数据结构,它由一个个节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。
单链表需要实现的基本功能?
基本的操作为:增、删、查、改
具体为:
- 插入元素:将新元素插入到链表的指定位置,可以是链表的头部、尾部或中间位置。
- 删除元素:从链表中删除指定位置的元素。
- 查找元素:根据给定的值,在链表中查找对应的元素,并返回其位置。
- 遍历链表:按顺序访问链表中的每个元素。
- 获取链表长度:获取链表中元素的个数。
- 判断链表是否为空:判断链表是否为空链表。
- 清空链表:删除链表中的所有元素,使其成为一个空链表。
单链表的基本结构是怎么样的?
一张图让你理解
注:此文实现的是没有带哨兵的单链表
注意:最后一个节点的next指针指向的是NULL
二、总体思路
如何实现?按照单链表的基本介绍以及功能来一步一步实现!首先实现什么?->节点!最基本的元素,没有节点之后的都实现不了。接着实现什么?接口!按照功能将每一个接口都写好,以此来保证后续所写功能的连续性。最后,按照接口将每一个功能都实现即可!注意在编写的过程中也要反复的比对接口,及时修改接口的传参或者地址的传递。
对此节点定义如下:
结构体定义
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
int 型 data 用于储存数据,结构体指针型 next 用于指向下一个节点。
接口函数定义
//打印
void SLTPrint(SLTNode* phead);
//生成新的节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
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);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pphead);
重点:
此为对本版本单链表的不断优化后得到的接口。其中* phead 存储的是结构体类型的地址,即:他是用于改变结构体内的数据而设置的,* pos也是同理。而重点在于**pphead,他存储的结构体指针的地址,他是用于改变结构体指针的,即改变的是结构体的地址。x则是用于传参,输入需要添加的数据。
你可能有个疑问,在此处为什么要使用**pphead呢?
注意看在用到**pphead的函数,其中大多都是插入以及删除的操作,仔细看操作,例如:在插入时指针为空,而申请了新的节点,再将节点的地址替换原来的指针。删除了最后一个节点,将节点制空。即将节点替换为NULL。因此,使用**pphead是有必要的。
三、具体每个接口函数的实现
1、打印
void SLTPrint(SLTNode* phead)//打印全部节点
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
2、申请新的节点
SLTNode* BuySListNode(SLTDataType x)//申请新的节点
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
}
3、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
SLTNode* newnode = BuySListNode(x);
//pphead空指针,对地址进行操作
if(!*pphead)
*pphead = newnode;
else//不为空,以下为对结构体进行操作
{
SLTNode* dit = *pphead;
while (dit->next)
{
dit = dit->next;
}
dit->next = newnode;
}
}
4、头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
SLTNode* newnode = BuySListNode(x);
if (!*pphead)//加这个干啥?
*pphead = newnode;
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}
5、尾删
void SLTPopBack(SLTNode** pphead)//尾删
{
//判空
assert(pphead);
assert(*pphead);//空链表不能删
//一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else//多个节点
{
SLTNode* tail = *pphead,*ftail=*pphead;
while (tail->next != NULL)
{
ftail = tail;
tail = tail->next;
}
free(ftail->next);
ftail->next = NULL;
}
}
6、头删
void SLTPopFront(SLTNode** pphead)//头删
{
assert(*pphead);//判空
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}
7、找节点(用于后续的插入以及删除操作)
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{
//判空
assert(phead);
//遍历找值
SLTNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
8、基于第7小点在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)// 在pos之前插入x
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
/*SLTNode* newnode=BuySListNode(x);
newnode->next = pos;
*pphead=newnode;*/
SLTPushFront(pphead, x);
}
else
{
SLTNode* pre = *pphead;
/*while (pre != NULL)
{
if (pre->next == pos)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = pos;
pre->next = newnode;
}
}*/
while (pre->next != pos)
{
pre = pre->next;
}
SLTNode* newnode = BuySListNode(x);
newnode->next = pos;
pre->next = newnode;
}
}
9、基于第7小点在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)// 在pos以后插入x
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
10、基于第7小点删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置
{
assert(pphead);
assert(pos);
if (*pphead == pos)//在头
{
SLTPopFront(pphead);
}
else
{
SLTNode* dit = *pphead;
while (dit->next != pos)
{
dit = dit->next;
}
dit->next = pos->next;
free(pos);
//pos=NULL//此为形参无用
}
}
11、基于第7小点删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)// 删除pos的后一个位置
{
assert(pos);
assert(pos->next);//检查pos是否为尾结点
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}
12、销毁链表,释放空间
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
四、总体代码
1、头文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 01
#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);
//生成新的节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
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);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pphead);
2、主体函数文件
#include"SList.h"
SLTNode* BuySListNode(SLTDataType x)//申请新的节点
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
}
void SLTPrint(SLTNode* phead)//打印全部节点
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
SLTNode* newnode = BuySListNode(x);
//pphead空指针,对地址进行操作
if(!*pphead)
*pphead = newnode;
else//不为空,以下为对结构体进行操作
{
SLTNode* dit = *pphead;
while (dit->next)
{
dit = dit->next;
}
dit->next = newnode;
}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
SLTNode* newnode = BuySListNode(x);
if (!*pphead)//加这个干啥?
*pphead = newnode;
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}
void SLTPopBack(SLTNode** pphead)//尾删
{
//判空
assert(pphead);
assert(*pphead);//空链表不能删
//一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else//多个节点
{
SLTNode* tail = *pphead,*ftail=*pphead;
while (tail->next != NULL)
{
ftail = tail;
tail = tail->next;
}
free(ftail->next);
ftail->next = NULL;
}
}
void SLTPopFront(SLTNode** pphead)//头删
{
assert(*pphead);//判空
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{
//判空
assert(phead);
//遍历找值
SLTNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)// 在pos之前插入x
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
/*SLTNode* newnode=BuySListNode(x);
newnode->next = pos;
*pphead=newnode;*/
SLTPushFront(pphead, x);
}
else
{
SLTNode* pre = *pphead;
/*while (pre != NULL)
{
if (pre->next == pos)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = pos;
pre->next = newnode;
}
}*/
while (pre->next != pos)
{
pre = pre->next;
}
SLTNode* newnode = BuySListNode(x);
newnode->next = pos;
pre->next = newnode;
}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)// 在pos以后插入x
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置
{
assert(pphead);
assert(pos);
if (*pphead == pos)//在头
{
SLTPopFront(pphead);
}
else
{
SLTNode* dit = *pphead;
while (dit->next != pos)
{
dit = dit->next;
}
dit->next = pos->next;
free(pos);
//pos=NULL//此为形参无用
}
}
void SLTEraseAfter(SLTNode* pos)// 删除pos的后一个位置
{
assert(pos);
assert(pos->next);//检查pos是否为尾结点
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
3、测试用例
#include"SList.h"
void text()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 10);
SLTPushFront(&plist, 20);
SLTPushFront(&plist, 30);
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* p = SLTFind(plist, 10);//把找到的地址给p
SLTInsert(&plist, p, 100);
SLTPrint(plist);
SLTInsertAfter(p, 200);
SLTPrint(plist);
SLTErase(&plist, p);
SLTPrint(plist);
SLTNode* pp = SLTFind(plist, 100);
SLTEraseAfter(pp);
SLTPrint(plist);
SLTDestroy(&plist);
}
int main()
{
text();
return 0;
}
测试结果:
感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o!
文章来源:https://www.toymoban.com/news/detail-629497.html
给个三连再走嘛~ 文章来源地址https://www.toymoban.com/news/detail-629497.html
到了这里,关于【数据结构】—C语言实现单链表(超详细!)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!