【数据结构与算法】单链表的增删查改（附源码）

这么可爱的猫猫不值得点个赞吗??

一.链表的概念和结构

一.链表的概念和结构

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

链表其实有很多种类：

1.单向双向

2.带头不带头

3.循环不循环

其中共能组合出8种形式的链表；

这篇文章讲的是结构最简单的链表，也就是单向不带头不循环链表，即单链表。

单链表中的元素称为节点，节点有一个数据data，还有一个结构体指针next 存储下一个节点的地址，最后一个节点的next是NULL。

二.单链表的逻辑结构和物理结构

1.逻辑结构

2.物理结构

三.结构体的定义

typedef int SLdatatype;  //对数据类型重定义，方便后续更改

typedef struct SListNode
{
	SLdatatype data;
	struct SListNode* next;
}SLNode;

四.增加

1.尾插 SListpushback

想要实现尾插，就要先找到尾节点，但要注意，当链表是空时，就没有尾节点，这个时候直接插入就行了；

我们可以申请一个新的节点newnode，然后插入链表中，由于尾插和头插都需要申请新的节点，所以我们可以将这封装成一个函数；

注意，不管是尾插还是头插，最后都会使链表发生改变，所以我们要传二级指针进去。

找尾节点时，while里的循环条件要写成 tail->next !=NULL

请看逻辑结构：

申请新节点 BuySListNode

SLNode* BuySListNode(SLdatatype x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	assert(newnode);
	newnode->data = x;  //x是要插入的数据
	newnode->next = NULL;
	return newnode;
}

尾插 SListpushback

void SListpushback(SLNode** pphead,SLdatatype x)  //注意传的是二级指针
{
	SLNode* newnode = BuySListNode(x);
	if (*pphead == NULL)   //判断链表是否为空
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* tail = *pphead;  //寻找尾节点
		while (tail->next != NULL)   //注意这里不能写成 while(tail!=NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

2.头插 SListpushfront

头插时只需让新节点的 next 指向旧的头节点，然后再把 newnode 赋给头节点，使之成为新的头节点，即使是空表也没关系，newnode 会直接成为头节点。

void SListpushfront(SLNode** pphead, SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
}

五.删除

1.尾删 SListpopback

尾删前，我们需要判断：

1.若为空表，则直接结束函数；

2.若链表中只有一个节点，则直接 free 头节点，然后置为NULL；

3.寻找尾节点 tail 和尾节点的前一个节点 pre ,因为我们释放掉尾节点后，pre就成为了新的尾节点，而尾节点的 next 是 NULL ，所以我们需要找到尾节点的前一个节点。

找尾的方法和之前的一样。

void SListpopback(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)  //注意这里因为优先级的问题，*pphead 要打括号
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* pre = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			pre = tail;   //记录 tail 的前一个节点
			tail = tail->next;
		}
		pre->next = NULL;  //next 置为NULL
	}
}

2.头删 SListpopfront

在头删前：

1.判断是否为空表；

2.定义一个 next 用来保存头节点中的 next ，释放完后，这个 next 就成为了新的头节点。

void SListpopfront(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SLNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

六.查找插入释放打印

1.查找 SListfind

在插入和释放前，都需要调用 find 函数，来找到希望插入或是释放的位置。

SLNode* SListfind(SLNode* phead, SLdatatype x)
{
	SLNode* pos = phead;
	while (pos)
	{
		if (pos->data == x)
		{
			return pos;
		}
		pos = pos->next;
	}
}

2.插入 SListinsert

如果是链表中只有一个节点，就变成了头插，只需要调用头插函数就行了，如果是空表也不用担心，可以设置成不调用函数；

在插入前，需要找到指定位置 pos 的前驱 pre，

使pre->next=newnode , newnode->next=pos

如图所示，假设在3的前一个位置插入数据：

void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
	if (pos->next == NULL)
	{
		SListpushfront(pphead, x);
	}
	else
	{
		SLNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		pre->next = newnode;
		newnode->next = pos;
	}
}

3.释放 SListerase

释放前：

1.如果只有一个节点，则直接释放头节点，再置为空即可；

2.如果不止一个节点，还需找到要释放的位置的前一个节点 pre ，将 pre 的 next 指向 pos 的next，然后再释放;

如图所示，假设要释放掉3这个节点：

void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{
	if (pos->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* pre = *pphead;
		while (pre->next !=pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);
	}
}

4.打印 SListprint

虽然可以直接用头节点 phead 遍历，但博主还是推荐定义一个新的结构体指针 cur ，把phead 的值赋给 cur ，会显得更优雅；

注意这里的 while 里的式子要写成 cur ，如果写成 cur->next ，那么最终打印出来的结果会少一个节点的数据。

void SListprint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}

七.源码

1.SList.h

#define _CRT_SECURE_NO_WARNINGS


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLdatatype;

typedef struct SListNode
{
	SLdatatype data;
	struct SListNode* next;
}SLNode;


void SListprint(SLNode* phead);   //打印

void SListpushback(SLNode** pphead,SLdatatype x);   //尾插

void SListpushfront(SLNode** pphead, SLdatatype x);   //头插

void SListpopfront(SLNode** pphead);   //头删

void SListpopback(SLNode** pphead);   //尾删

SLNode* SListfind(SLNode* phead,SLdatatype x);   //查找

void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x);   //插入

void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x);   //释放

2.SList.c

#define _CRT_SECURE_NO_WARNINGS

#include "SList.h"


void SListprint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}


SLNode* BuySListNode(SLdatatype x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SListpushback(SLNode** pphead,SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* tail = *pphead;  //寻找尾节点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}


void SListpushfront(SLNode** pphead, SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
}


void SListpopfront(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SLNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}


void SListpopback(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* pre = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			pre = tail;
			tail = tail->next;
		}
		pre->next = NULL;
	}
}


SLNode* SListfind(SLNode* phead, SLdatatype x)
{
	SLNode* pos = phead;
	while (pos)
	{
		if (pos->data == x)
		{
			return pos;
		}
		pos = pos->next;
	}
}


void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{
	SLNode* newnode = BuySListNode(x);
	if (pos->next == NULL)
	{
		SListpushfront(pphead, x);
	}
	else
	{
		SLNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		pre->next = newnode;
		newnode->next = pos;
	}
}



void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{
	if (pos->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* pre = *pphead;
		while (pre->next !=pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);
	}
}

3.test.c

博主写的主函数只是用来测试单链表的，写起主函数来也不难，大家可以自行编写。

#include "SList.h"


void testSList1()
{
	SLNode* plist = NULL;
	
	SListpushback(&plist,1);
	SListpushback(&plist,2);
	SListpushback(&plist,3);
	SListpushback(&plist,4);
	SListprint(plist);
	SListpushfront(&plist, 0);
	SListprint(plist);
	SListpopfront(&plist);
	SListpopfront(&plist);
	SListpopfront(&plist);
	SListprint(plist);
	SListpopback(&plist);
	SListpopback(&plist);
	SListpopback(&plist);
	SListprint(plist);
}

void testSList2()
{
	SLNode* plist = NULL;
	SListpushback(&plist, 1);
	SListpushback(&plist, 2);
	SListpushback(&plist, 3);
	SListpushback(&plist, 4);
	SLNode* pos = SListfind(plist, 3);
	if (pos)
	{
		SListinsert(&plist,pos, 20);
		SListprint(plist);
	}
	pos = SListfind(plist, 2);
	if (pos)
	{
		SListerase(&plist,pos,2);
		SListprint(plist);
	}
	
}

int main()
{
	//testSList1();
	testSList2();
	return 0;
}

八.单链表的一些问题

在单链表中，要想找到某一个数据，就需要从头节点开始，所以单链表是非随机存取的存储结构，且要想对单链表进行一些操作，总是要找到前驱节点，有时还需判断一些特殊情况，有什么办法能解决这些问题呢？

博主将在下篇双向带头循环链表中讲解，敬情期待~

??本篇文章到此就结束了，如有错误或是建议，欢迎小伙伴们提出~??

??希望可以多多支持博主哦~??

??谢谢你的阅读~??

一.链表的概念和结构

二.单链表的逻辑结构和物理结构

1.逻辑结构

2.物理结构

三.结构体的定义

四.增加

1.尾插 SListpushback

2.头插 SListpushfront

五.删除

1.尾删 SListpopback

2.头删 SListpopfront

六.查找 插入 释放 打印

1.查找 SListfind

2.插入 SListinsert

3.释放 SListerase

4.打印 SListprint

七.源码

1.SList.h

2.SList.c

3.test.c

八.单链表的一些问题

六.查找插入释放打印