[ 数据结构--C语言 ] 无头单向非循环链表的简单实现(单链表) _单链表

蹉跎莫遣韶光老，人生唯有读书好。这篇文章主要讲述[ 数据结构--C语言 ] 无头单向非循环链表的简单实现(单链表)相关的知识，希望能为你提供帮助。

目录
1. 链表
2. 接口实现
3.菜单
1. 链表1.1 链表的概念及结构

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

个人理解为：链表有两种结构，为逻辑结构和物理结构。
逻辑结构：链表是链式结构在逻辑上是连续的，它们之间用指针连接起来，上一个节点的next存储下一个节点的地址，一次类推，最后一个节点的next指向NULL。我们可以类比为一列火车(如图1-1)，依次链接起来的(如图1-2)。

物理结构：链式结构在逻辑上连续但是在物理结构上不一定连续，也就是说这些结点在内存中不一定是连续存储的。两次申请的空间可能连续可能不连续。
注意：现实中的节点一般都是从堆上申请出来的，从堆上申请的空间，是按照一定的策略分配的，两次申请的空间可能连续可能不连续（如图1-3）。

1.2链表的分类实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1、单向或者双向

2、带头或者不带头

3、循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构:无头单向非循环链表(本篇文章所实现）和带头双循环链表。

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

1.3接口

//不会改变链表的头指针，传一级指针
//打印
void SListPrint(SLTNode* plist);

//可能会改变链表的头指针，传二级指针
//尾插
void SListPushBack(SLTNode** pplist, SLTDataType x);
//头插
void SListPushFront(SLTNode** pplist, SLTDataType x);
//头删
void SListPopFront(SLTNode** pplist);
//尾删
void SListPopBack(SLTNode** pplist);

//查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x);

//在pos位置之前插入
void SListInsertBefore(SLTNode** pplist,SLTNode* pos, SLTDataType x);
//在pos位置之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** pplist, SLTNode* pos);

//删除pos后面的值
void SListEraseAfter(SLTNode** pplist, SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pplist);

本篇文章我们将实现以上这些接口。
2. 接口实现2.1 节点的创建

struct SListNode

SLTDataType data;
struct SListNode* next; //指向下一个指针(结构体类型)
;

data表示该节点的值，next表示指向下一个指针(仍然是结构体类型，是一个结构体指针)。
2.2 打印链表

void SListPrint(SLTNode* plist);

void SListPrint(SLTNode* plist)

SLTNode* cur = plist;
while (cur != NULL)

printf("%d-> ", cur-> data);
cur = cur-> next;

printf("NULL\\n");

2.3 创建新节点

SLTNode* BuySListNode(SLTDataType x)

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode-> data = https://www.songbingjia.com/android/x;
newnode-> next = NULL;
return newnode;

新节点包括数据data，next我们默认置NULL
2.4 尾插

void SListPushBack(SLTNode** pplist, SLTDataType x);

void SListPushBack(SLTNode** pplist, SLTDataType x)

SLTNode* newnode = BuySListNode(x);
//找尾节点的指针
//*pplist = plist
if (*pplist == NULL)

*pplist = newnode; //形参的改变不会影响实参

else

//找尾
SLTNode* tail = *pplist; //tail是局部变量
while (tail-> next != NULL)

tail = tail-> next;

//尾节点链接新节点
tail-> next = newnode;

尾插的核心是寻找尾结点，寻找的关键要点是尾结点的next指针指向空，因为我们只需要判断尾指针的下一个指针是否为空则可以找到尾。
注意：
我们学过函数知道，形参的改变不影响实参，要改变实参就要传地址，用指针接收，因此我们改变的是结构体指针的地址，我们需要二级指针来接收。

2.5 头插

//头插
void SListPushFront(SLTNode** pplist, SLTDataType x);

void SListPushFront(SLTNode** pplist, SLTDataType x)

SLTNode* newnode = BuySListNode(x);
newnode-> next = *pplist;
*pplist = newnode; //形参的改变不会影响实参

头插相对来说比较简单。得到新节点后，让新节点的next指向头结点，头结点再被改为newnode即可。
2.6 尾删

//尾删
void SListPopBack(SLTNode** pplist);

//尾删
void SListPopBack(SLTNode** pplist)

assert(pplist);

//1.空
if (*pplist == NULL)

return;

//2.一个结点
else if ((*pplist)-> next == NULL)

free(*pplist);
*pplist = NULL;

else

//3.多个结点
SLTNode* prev = NULL;
SLTNode* tail = *pplist;
while (tail-> next != NULL)

prev = tail;
tail = tail-> next;

free(tail);
prev-> next = NULL;

//SLTNode* tail = *pplist;
//while (tail-> next-> next != NULL)
//
//tail = tail-> next;
//
//free(tail-> next);
//tail-> next = NULL;

尾删需要考虑链表的节点个数，分为空链表，一个节点，多个几点这三类。
1、如果为空链表，直接return。
2、如果有一个节点，我们直接讲这个节点free释放，再将头结点置空即可。
3、如果有多个节点，我们首先还是要找尾，但是这次我们不仅要找尾，还要找尾结点的上一个节点，因此我们可以有两种方法来解决
第一种方法：
创建两个临时结构体指针，一个找尾，一个找尾的上一个节点，找到后只需要free掉尾结点，再将上一个节点的next指位NULL
第二种方法：
只需创建一个临时结构体指针，我们通过next的next找尾，next找尾的上一个节点，也可实现尾删。
2.7 头删

void SListPopFront(SLTNode** pplist);

void SListPopFront(SLTNode** pplist)

assert(pplist);
//1.空
if (*pplist == NULL)

return;

//2.非空单节点与多节点可合并
else

SLTNode* head = (*pplist)-> next;
free(*pplist);
*pplist = head;

头删也要分为两种情况，链表为空和非空
1、链表为空，直接return。
2、链表不为空，我们找到第二个节点，释放掉第一个节点，再将第二个节点的地址给头结点即可。
2.8 查找

SLTNode* SListFind(SLTNode* plist, SLTDataType x)

SLTNode* cur = plist;
while (cur != NULL)

if (cur-> data =https://www.songbingjia.com/android/= x)

return cur;

cur = cur-> next;

return NULL;

查找是比较简单的，只需要注意的是，查找返回的是具体数值的地址，若为空，则返回NULL。
2.9 在pos位置之前插入

void SListInsertBefore(SLTNode** pplist,SLTNode* pos, SLTDataType x);

//在pos位置之前插入
void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDataType x)

assert(pplist);
assert(pos);
//1.头插 pos是第一个节点
if (pos == *pplist)

SListPushFront(pplist, x);

//2. pos不是第一个节点
else

SLTNode* prev = *pplist;
while (prev-> next != pos)

prev = prev-> next;

SLTNode* newnode = BuySListNode(x);
prev-> next = newnode;
newnode-> next = pos;

在写之前一定要判断该链表和该位置是否为空，如果都不存在链表和该位置，插值也是无稽之谈。
这是我们也要分为pos位第一个位置和pos不是第一个位置两种情况：
1、如果pos在第一个位置，相当于头插的作用，我们只需要调用头插接口即可。
2、如果pos不在第一个位置，我们先找到pos位置的上一个节点prev，prev的next保存newnode的地址，newnode的next保存pos位置的地址即可。
2.10 在pos位置之后插入

void SListInsertAfter(SLTNode* pos, SLTDataType x);

void SListInsertAfter(SLTNode* pos, SLTDataType x)

assert(pos);
//存一份pos下一位的地址
SLTNode* next = pos-> next;
SLTNode* newnode = BuySListNode(x);
pos-> next = newnode;
newnode-> next = next;

首先仍然需要对pos位置进行断言
接下来这一步非常关键，我们必须要创建一个next指针来保存pos的next指针的地址，因为只有pos位置才能访问到pos的next指针，创建newnode后，只需要将pos的next保存newnode的地址，再让newnode的next保存刚刚创建的next的指针的地址即可。
2.11 删除pos位置

void SListErase(SLTNode** pplist, SLTNode* pos);

//删除pos位置
void SListErase(SLTNode** pplist, SLTNode* pos)

assert(pplist);
assert(pos);
//1.pos是第一个相当于头删
if (*pplist == pos)

SListPopFront(pplist);

//2.
else

SLTNode* prev = *pplist;
while (prev-> next != pos)

prev = prev-> next;

prev-> next = pos-> next;
free(pos);
pos = NULL;

删除操作一定要对链表进行断言
这里我们依然要分为pos位置是第一个节点和pos位置不是第一个节点两种情况：
1、pos位置是第一个节点，相当于头删，调用头删接口即可
2、pos位置不是第一个节点，我们需要找到pos位置的前一个节点prev，然后将prev的next保存pos的next的地址，再将pos位置free，再置空即可。
2.12 删除pos后面的值

void SListEraseAfter(SLTNode** pplist, SLTNode* pos);

void SListEraseAfter(SLTNode** pplist, SLTNode* pos)

assert(pplist);
assert(pos);
SLTNode* next = pos-> next;
if (next)

pos-> next = next-> next;
free(next);

这个比较简单，只需要创建临时指针next保存pos的next地址，再让pos的next保存next的next的地址，再释放掉next即可。
3.菜单

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void menu()

printf("************************************\\n");
printf("*****1.尾插*****\\n");
printf("*****2.头插*****\\n");
printf("*****3.尾删*****\\n");
printf("*****4.头删*****\\n");
printf("*****5.查找 x*****\\n");
printf("*****6.在pos位置之前插入*****\\n");
printf("*****7.在pos位置之后插入*****\\n");
printf("*****8.删除pos位置的元素*****\\n");
printf("*****9.删除pos之后的元素*****\\n");
printf("*****10.打印单链表*****\\n");
printf("*****-1.退出*****\\n");
printf("************************************\\n");

int main()

SLTNode* plist = NULL;
int option = -1;
menu();
do

printf("请输入选项:> ");
scanf("%d", & option);
if (option == 1)

int x = 0;
printf("请输入你要尾插的数字:> ");
scanf("%d", & x);
SListPushBack(& plist, x);

else if (option == 2)

int x = 0;
printf("请输入你要头插的数字:> ");
scanf("%d", & x);
SListPushFront(& plist, x);

else if (option == 3)

SListPopBack(& plist);

else if (option == 4)

SListPopFront(& plist);

else if (option == 5)

int x = 0;
printf("请输入你要查找的值x:> ");
scanf("%d", & x);
SLTNode* cur = SListFind(plist, x);
if (cur != NULL)

printf("存在数字%d\\n",x);

else

printf("未找到数字%d", x);

else if (option == 6)

int x = 0;
int y = 0;
printf("请分别输入pos值x和pos前所插入的值y:> ");
scanf("%d %d", & x,& y);
SLTNode* pos = SListFind(plist, x);
if (pos != NULL)

SListInsertBefore(& plist, pos, y);

else

printf("该链表不存在%d\\n",x);

else if (option == 7)

int x = 0;
int y = 0;
printf("请分别输入pos值x和pos后所插入的值y:> ");
scanf("%d %d", & x, & y);
SLTNode* pos = SListFind(plist, x);
if (pos != NULL)

SListInsertAfter(pos, y);

else

printf("该链表不存在%d\\n",x);

else if (option == 8)

int x = 0;
printf("请输入要删除pos位置的值:> ");
scanf("%d", & x);
SLTNode* pos = SListFind(plist, x);
SListErase(& plist, pos);

else if (option == 9)

int x = 0;
printf("请输入要删除pos位置之后的值:> ");
scanf("%d", & x);
SLTNode* pos = SListFind(plist, x);
SListEraseAfter(& plist, pos);

else if (option == 10)

SListPrint(plist);

while (option != -1);
SListDestroy(& plist);
return 0;