数据结构-单链表（增删查改）

前言

学习目标：
单链表的基本使用方法、单链表的增删查改、单链表的两种指定插入删除方式

代码

一、SList.h

头文件，函数声明，结构体

#pragma once

#include 
#include 
#include 

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;//这里不能用SLTNode* next代替，因为到这一步时还没重命名完成
}SLTNode;

//打印
void SListPrint(SLTNode* phead);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SLTNode** pphead);
//头删
void SListPopFront(SLTNode** pphead);


//查找指定数据所在节点
SLTNode* SListFindNode(SLTNode* pphead, SLTDataType x);
//指定插入：把x插入到pos位置，pos位置由SListFind找出来
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//指定删除
void SListErase(SLTNode** pphead, SLTNode* pos);、


//查找指定数据x所在位置
int SListFindDest(SLTNode* phead, SLTDataType x);
//指定插入：下标法
void SListInsert(SLTNode** pphead, int pos, SLTDataType x);
//指定删除
void SListErase(SLTNode** pphead, int pos);


//修改
void SListModify(SLTNode** pphead, int pos, SLTDataType x);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

二、SListTset.c

测试函数SListNode（）和main（）

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void SListNode()
{
	SLTNode* plist = NULL;
	
	//增删查改
}

int main()
{
	SListNode();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三、SList.c

1、辅助功能

1.1、SListPrint

打印

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)  //打印时为cur不等于NULL，跳出循环后cur指向NULL(cur=NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n"); //当链表中没有数据时，直接打印NULL
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.2、*BuyNode

说明： 每次添加数据都需要动态申请空间（结构体），然后把数据x放入该空间的data，再把该空间的next置为NULL（尾插时或者plist=NULL时不用再在其它地方操作，其它插入也可以覆盖），最后返回该结构体的地址。

//开辟空间的函数
SLTNode* BuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;   //在开辟空间后就及时把该空间的next赋值为NULL
	return newnode;
}
1
2
3
4
5
6
7
8

2、头尾插入删除

说明：插入删除这一部分要时刻考虑三个关键点：1、plist为NULL，2、只有一个节点（或指定插入删除中有两个及以上节点但插入或删除第一个），3、一般的有两个以上节点。

2.1、SListPushFront

说明：不用考虑多种情况

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuyNode(x);  
	
	//头插，不管plist是否为NULL都符合条件
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6
7
8
9

2.2、SListPopFront

说明：要考虑plist=NULL，有一个及以上节点

//头删
void SListPopFront(SLTNode** pphead)
{
	//plist==NULL时
	assert(*pphead);

	//有一个及以上节点时
	SLTNode* Next = (*pphead)->next;
	free(*pphead);
	*pphead = Next;
}
1
2
3
4
5
6
7
8
9
10
11

2.3、SListPushBack

说明：分两种情况：1、如果原来链表plist=NULL，那么newnode就是新建链表的头节点。2、有一个及以上节点

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuyNode(x);
	
	//plist=NULL时尾插
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//有一个及以上节点
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.4、SListPopBack

说明：需要找当前位置前一个，所以除了考虑1>plist=NULL和2>大于等于2个节点，还得3>考虑一个节点的情况。

//尾删
void SListPopBack(SLTNode** pphead)
{
	//plist=NULL
	assert(*pphead);
	//有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//有两个及以上节点
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;//这里用的prev是找到NULL前一个的前一个节点
			tail = tail->next;
		}

		free(tail);
		tail=NULL;
		prev->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3、查找和指定结构体插删

3.1、SListFindNode

说明：查找指定数所在节点，把该节点的结构体指针返回

//查找指定数所在的节点
SLTNode* SListFindNode(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* cur = phead;

	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.2、SLIistInsert

指定结构体插入(包括头插，随机插，不包括尾插)：

说明：要用SListInsert函数，需要先用SListFindNode函数查找输入数的指针并返回指针，然后才能传参。
如应在SListNode（）测试函数中如下操作：
SLTNode* pos = SListFindNode（plist，input1）；
if（pos!=NULL）
{
SListInsert（&plist，pos，input2）;
}
指定插同样需要考虑三种情况。也可以只考虑后两种（只有一个节点或两个及以上节点），因为plist=NULL已经被SListFindNode（）排除掉。

//指定插入:插入pos位置，pos由SListFindNode得到
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(*pphead);
	SLTNode* newnode = BuyNode(x);
	SLTNode* prev = *pphead;

	//一个节点(或者多个节点)，但pos刚好就是第一个节点位置，相当于头插
	if (prev == pos)
	{
		newnode->next = prev;
		*pphead = newnode;
	}
	//两个及以上的节点
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.3、SListErase

指定结构体删除(包括头删，随机删，尾删)：

说明：使用方法和SListInsert（）类似，同样需要考虑三种情况。也可以只考虑后两种，因为plist=NULL已经被SListFindNode（）排除掉。

//指定删除
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead);
	SLTNode* prev = *pphead;

	if (pos == *pphead)
	{
		*pphead = (*pphead)->next;
		free(prev);
		prev = NULL;
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、查找和指定位置插删

4.1、SListFindDest

说明：查找x这个数在链表中为第count个数，返回count，在SListNode（）测试函数中用int pos接收

int SListFindDest(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	int count = 1;
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return count;
		}
		cur = cur->next;
		count++;
	}

	printf("没有该数据！\n");
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.2、SListInsert

指定位数前插：找到该数在链表中为第pos个数，返回pos，再作为参数传给SListInsert（）

说明：可以和上面一样，考虑三种情况。也可以只考虑后两种，因为plist=NULL已经被SListFindDest（）排除掉。

void SListInsert(SLTNode** pphead, int pos, SLTDataType x)
{
    //plist=NULL的情况
    assert(*pphead);
	SLTNode* newnode = BuyNode(x);
	//第一个数
	if (pos == 1)
	{
		//下面这两步不能交换，否则将不能再找到原来的链表
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		int count = 1;
		SLTNode* prev = *pphead;

		while (count < pos-1)
		{
			prev = prev->next;
			count++;
		}
		//找到第pos(int类型)个数的前一个数

		newnode->next = prev->next;
		prev->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

4.3、SListErase

指定位数删：找到该数在链表中为第pos个数，返回pos，再作为参数传给SListInsert（）

说明： 可以和上面一样，考虑三种情况。也可以只考虑后两种，因为plist=NULL已经被SListFindDest（）排除掉。

void SListErase(SLTNode** pphead, int pos)
{
	assert(*pphead);
	SLTNode* prev = *pphead;

	if (pos == 1)
	{
		*pphead = (*pphead)->next;
		free(prev);
		prev = NULL;
	}
	else
	{
		int count = 1;
		while (count < pos - 1)
		{
			prev = prev->next;
			count++;
		}

		SLTNode* del = prev->next;
		prev->next = del->next;
		free(del);
		del = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

5、插入删除总结

5.1、存在情况：

1、头插：什么都不需要考虑
2、头删：1>考虑plist=NULL
3、尾插：1>考虑plist=NULL，2>和有一个及以上节点
4、尾删：1>考虑plist=NULL，2>和有一个节点，3>有两个及以上节点
5、指定结构体插：1>考虑plist=NULL，2>和有一个节点（有两个及以上节点但插入或删除第一个），3>一般的有两个以上节点
6、指定结构体删：1>考虑plist=NULL，2>和有一个节点（有两个及以上节点但插入或删除第一个），3>一般的有两个以上节点

5.2、需要找到的位置：

需要找自身位置：头删，尾插
需要找前一个位置：指定结构体插，指定结构体删
需要找到前一个的前一个位置：尾删

5.3、找前一个节点的方法：

1、用prev和tail两个指针：

SLTNode* prev=NULL;
SLTNode* tail=*pphead;
if(tail!=pos)
{
    prev=tail;
    tail=tail->next;
}
//出循环tail=pos,prev->next=tail
1
2
3
4
5
6
7
8

2、只用prev一个指针

SListNode* prev=*pphead;
while(prev->next!=pos)
{
    prev=prev->next;
}
//出循环prev->next=pos
1
2
3
4
5
6

3、扩展：找前一个节点的前一个节点：

SLTNode* prev=NULL;
SLTNode* tail=*pphead;
if(tail->next!=pos)//(pos=NULL时就是尾删的方法)
{
    prev=tail;
    tail=tail->next;
}
//出循环tail->next=pos,prev->next=tail
1
2
3
4
5
6
7
8

6、修改

说明：需要用SListFindDest（），先找到第pos个数，再修改数据。

void SListModify(SLTNode** pphead, int pos, SLTDataType x)
{
	SLTNode* cur = *pphead;
	int count = 1;
	while (count < pos)
	{
		cur = cur->next;
		count++;
	}
	cur->data = x;
}
1
2
3
4
5
6
7
8
9
10
11

总结

1、需要修改链表才传地址，如插入删除修改传&plist，而查找则不需要传地址。
2、* plist和 ** pphead和 * phead的说明：plist本身为一级指针，插入删除修改传址调用后pphead为二级指针，它保存的是plist的地址，而查找传值调用phead仍为一级指针，它保存的是plist指向的链表的首地址。
3、分清插入删除需要考虑的三大要素。

最后希望各位大佬批评指正，谢谢！