学习408之数据结构--链表-单链表的增删查改的实现-如何解决顺序表增容后空间浪费问题？

顺序表的问题及思考问题：

中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，

我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：
如何解决以上问题呢？

链表的概念及结构

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

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

一、链表的组成

为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指向其直接后继的信息（即直接后继的存储位置）。

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。

n个结点（ai的存储映像）链结成一个链表，即为线性表（a1，a2，…，an）的链式存储结构。因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在—起。

（一）头指针

对于线性表来说，总得有头有尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。

最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为(通常用NULL或“^”符号表示，如下图所示)。

（二）头结点

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针，如下图所示**。**

（三）头指针与头结点的异同点

头指针

头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针；
头指针具有标志作用，所以常用头指针冠以链表的名字；
无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点

头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可存放链表的长度)；
有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了；
头结点不一定是链表必需要素。

二、单链表的读取

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

单链表在C语言中描述：

typedef int SLDataType;//num的数据类型

/*线性表的单链表存储结构*/
typedef struct Node
{
	SLDataType data;
	struct Node* next;
}Node;

typedef struct Node* LinkList; /* 定义LinkList */

假设p是指向线性表的第i各元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针，指向第i+1各元素，即指向a i+1 的指针。
也就是说，如果p->data等于ai，那么p->next->data等于ai+1。

三、单链表的插入与删除

（一）单链表的插入

先来看单链表的插入。假设存储元素e的结点为 s，要实现结点 p、p->next 和 s 之间逻辑关系的变化，只需将结点** s 插入到结点 p 和 p->next 之间**即可。可如何插入呢(如下图所示)

s->next = p->next;  /* 将p的后继结点复制给s的后继 */
p->next = s;		/* 将s赋值给 p 的后继 */

那么上列两行代码可以交换，我们简单看一下代码。

p->next = s;	       /* s？的值是什么？，把什么赋值给了p->next这个指针？
s->next = p->next;   /* s->next 和 s有什么区别吗？ 这两端赋值相当于将s赋值给了s的后继

（二）单链表的删除

现在我们再来看单链表的删除。设存储元素 ai 的结点为 q，要实现将结点 q 删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可。

p->next = p->next->next; /* q 的表示*/
//  ↓↓↓↓↓↓
q = p->next;
p->next = q->next;  /* 转换成两步 */

对于插入或删除数据越频繁的操作，单链表的效率优势就越明显。

四、单链表增删查改实现

诸位也许了解过链表的类型，这里我们简单说一下。

我们常见的两种类型：

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

基于之前的顺序表，我们在一些重复操作上已经介绍的很详细了。这里我们就直接进行无头+单向+非循环链表增删查改实现。

无头+单向+非循环链表增删查改实现

首先创建一个结构体，作为链表中的结点，每一个节点就是一个结构体。

typedef int SLTDataType;     //方便后续更改数据类型

typedef struct SLTNode
{
	SLTDataType data;        //存储的数据
	struct SLTNode* next;    //用于指向下一结点的指针
}SLTNode;									//typedef 重新命名

（一）边编写代码边测试

我们在一份函数编写结束后，就可以进行测试，寻找bug。
也更容易使我们的程序被调试。
比如测试：

//test.c
//我们以链表的头插和尾删来举例，暂不考虑成功性
//暂不考虑代码的成功性，此代码是作为举例示范的，需要依据具体情况进行设计

void SListTest1(){
	SLTNode* plist = NULL;
	//测试头插是否成功
	PushFront(plist, 1);
	PushFront(plist, 2);
	PushFront(plist, 3);
	PushFront(plist, 4);
	PushFront(plist, 5);

	SLTPrint(plist);

	PopBack(plist);
	PopBack(plist);
	PopBack(plist);
	SLTPrint(plist);
}

int main(){
	SListTest1();
	return 0;
}

如上所示，我们可以多创建几个SListTest函数来检查及调试（遇到问题一定要多多调试，调试的过程也不是F11按到程序结束啥也不思考就完成了的）
现在我们开始编写代码吧。
首先为了我们检查测试的便利，我们需要一份打印链表的函数。

//链表打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

（二）链表的增添功能–插入

我们对链表的插入逐步入手，首先考虑一下链表的插入类型。
先从位置来看，我们可以对链表进行头插和尾插及指定位置插入。
而每种插入方式可能伴随着链表的类型的变化而存在不同。比如链表是空链表或非空链表。因此，在分位置插入后的每一种小点后，我们还需要按照链表的类型进行分类。
现在进入正题吧。

首先是单链表的头插

我们首先尝试来写一下

//node.h  作为函数声明  引用头文件
//打印链表
void SLTPrint(SLTNode* phead);


//链表的插入
//链表的头插
void SLTPushFront(SLTNode* phead, SLTDataType x);

//node.c  函数的定义
// 申请一个结点
SLTNode* BuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
		perror("malloc fail");
	newnode->data = x;
	newnode->next = NULL;
  return newnode;
}

//链表的头插
void SLTPushFront(SLTNode* phead, SLTDataType x)
{
	//1.空链表
	//2.非空链表
	SLTNode* newnode = BuyNode(x);
	if (phead == NULL)
	{
		newnode->next = NULL;
		phead = newnode;
	}
	else{
		newnode->next = phead;
		phead = newnode;
	}
}

//test.c  main函数  程序
void SListTest1(){
	SLTNode* plist = NULL;
	//测试头插是否成功
	PushFront(plist, 1);
	PushFront(plist, 2);
	PushFront(plist, 3);
	PushFront(plist, 4);
	PushFront(plist, 5);

	SLTPrint(plist);
}

int main(){
	SListTest1();
	return 0;
}

现在让我们来进行一下测试，看一下结果.

如果你写的内容与上列代码一致，很遗憾，在自行测试中，你的代码一定没有成功，进行调试时，你会发现链表并没有发生改变。
原因是什么呢？
这里提一个思路，再试着写一次代码吧。
在正确答案之前，让我们先了解一下思路。因此根据提示未作出的朋友仍然可以在详细介绍后，再尝试写一次代码。不要怕麻烦。完整的写一遍才能更好地理解。

//现在来把正确答案写下来吧

//node.h
//链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//test.c

void SListTest1()
{
	SLTNode* plist = NULL;
	//测试头插是否成功
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);

	SLTPrint(plist);
}

int main()
{
	SListTest1();
	return 0;
}
//node.c   
//链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//1.空链表
	//2.非空链表
	SLTNode* newnode = BuyNode(x);
	if (*pphead == NULL)
	{
		newnode->next = NULL;
		*pphead = newnode;
	}
	else{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

程序运行后，成功执行。

接下来我们再进入调试中观察。

单链表的尾插

搞清楚上面的头插，现在我们应该可以写成尾插的代码。原理都差不多。

//node.h
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//test.c
void SListTest1()
{
	SLTNode* plist = NULL;
	//测试头插是否成功
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);

	SLTPrint(plist);

	SLTPushBack(&plist,11);
	SLTPushBack(&plist,10);
	SLTPushBack(&plist,9);
	SLTPrint(plist);
}

//node.c
//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

单链表在pos位置之前插入

现在考虑一下该函数中的参数。
检查结果时，可以转至（三）查找功能，使用SLTFind函数寻找pos的位置，再结合打印函数来检查结果是否正确。

//node.c
//链表在pos位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos,SLTDataType x)
{
	//pos != NULL  怎么判断？
	assert(pos);//暴力检查

	SLTNode* newnode = BuyNode(x);

	//plist只有一个结点 == 头插
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//plist有多个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

单链表在pos位置之后插入

//链表在pos位置之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

在上列代码，可以发现在单链表在pos位置前后插入时，我们使用了assert来断言。
那么是否因为上列头插尾插没有写assert就判断不需要（￣□￣｜｜）。

这就好比我们去银行存钱。账户中有钱和没有钱，我们都可以存钱。
所以在插入时，我们断言pphead是一定不为空的，因为它存储的是plist的地址。
但是pphead就可以为空，当pphead为空时，plist就是空链表。

（三）链表的删除功能–删除

删除比起插入，就是去银行取钱，有钱当然可以取钱，但是账户没有钱，我们当然无法取款。

在删除过程中，综上，把代码敲出来吧。
原理都是大差不差的。

单链表的头删

//单链表的头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	SLTNode* Del = *pphead;
	*pphead = (*pphead)->next;
	free(Del);
}

单链表的尾删

//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* Del = *pphead;
		while (Del->next->next)
		{
			Del = Del->next;
		}
		free(Del->next);
		Del->next = NULL;
		//方法二
		/*SLTNode* Del = *pphead;
		SLTNode* prev = NULL;
		while (Del->next == NULL);
		{
			prev = Del;
			Del = Del->next;
		}
		free(Del);
		prev->next = NULL;*/
	}
}

删除单链表在pos位置

//删除单链表在pos位置
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	//只有一个结点
	//有多个结点
	if (pos == *pphead)//头删
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* Del = *pphead;
		while (Del->next != pos)
		{
			Del = Del->next;
		}
		Del->next = pos->next;
		free(Del);
	}
}

删除单链表在pos位置之后的结点

//删除单链表在pos位置之后的结点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	assert(pphead);
	assert(*pphead);
	//只有一个结点
	//多个结点
	SLTNode* Del = pos;
	pos->next = Del->next;
	free(Del);
}

（三）链表的查找功能–查找+打印进行测试

//node.c
//查找pos位结点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
		SLTNode* cur = phead;
		while (cur)
		{
			if (cur->data == x)
				return cur;
			cur = cur->next;
		}
		return NULL;
}

//链表在pos位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos,SLTDataType x)
{
	//pos != NULL  怎么判断？
	assert(pos);//暴力检查

	SLTNode* newnode = BuyNode(x);

	//plist只有一个结点 == 头插
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//plist有多个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

（四）链表的查找功能–修改

//修改pos位的结点数据
void SLTModify(SLTNode** pphead, SLTNode* pos,SLTDataType x)
{
	pos->data = x;
}

（五）销毁空间

//销毁链表
void Destroy(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* cur = *pphead;
	
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = cur->next;
	}
	*pphead = NULL;
}

五、增删查改和打印

完善这些功能，我们依旧将代码分类在三个文件中，node.h , node.c , test.c

//node.h
#pragma once

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


typedef int SLTDataType;

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

//链表的增删查改及打印

//打印链表
void SLTPrint(SLTNode* phead);

//查找pos位结点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//链表的插入
//链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//链表在pos位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//链表在pos位置之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//单链表的头删
void SLTPopFront(SLTNode** pphead);

//单链表的尾删
void SLTPopBack(SLTNode** pphead);

//删除单链表在pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);

//单链表在pos位置之后删除
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);

//修改pos位的结点数据
void SLTModify(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//销毁链表
void Destroy(SLTNode** pphead);

#include "node.h"

void SListTest1()
{
	SLTNode* plist = NULL;
	//测试头插是否成功
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);

	SLTPrint(plist);

	SLTPushBack(&plist,11);
	SLTPushBack(&plist,10);
	SLTPushBack(&plist,9);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 4);
	if(pos)
	{
		SLTInsert(&plist, pos, 43);
	}
	SLTPrint(plist);

	pos = SLTFind(plist, 5);
	if(pos){
		SLTInsert(&plist, pos, 54);
	}
	SLTPrint(plist);

}

void SListTest2()
{
	SLTNode* plist = NULL;
	//测试头插是否成功
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);

	SLTPushBack(&plist, 11);
	SLTPushBack(&plist, 10);
	SLTPushBack(&plist, 9);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 4);
	if (pos)
	{
		SLTInsert(&plist, pos, 43);
	}
	SLTPrint(plist);

	pos = SLTFind(plist, 5);
	if (pos) {
		SLTInsert(&plist, pos, 54);
	}
	SLTPrint(plist);
}

void SListTest3()
{
	SLTNode* plist = NULL;
	//测试头插是否成功
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);

	SLTPushBack(&plist, 11);
	SLTPushBack(&plist, 10);
	SLTPushBack(&plist, 9);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if(pos)
	{
		SLTInsertAfter(&plist, pos, 111);
	}
	pos = SLTFind(plist,1);
	if (pos)
	{
		SLTInsertAfter(&plist, pos, 222);
	}
	SLTPrint(plist);

	pos = SLTFind(plist, 222);
	SLTModify(&plist, pos, 0);
	SLTPrint(plist);

}
int main()
{
	//SListTest1();
	//SListTest2();
	SListTest3();
	return 0;
}

#include "node.h"

//链表打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

// 申请一个结点
SLTNode* BuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
		perror("malloc fail");
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//1.空链表
	//2.非空链表
	assert(pphead);
	SLTNode* newnode = BuyNode(x);
	if (*pphead == NULL)
	{
		newnode->next = NULL;
		*pphead = newnode;
	}
	else{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}

}

//链表在pos位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos,SLTDataType x)
{
	//pos != NULL  怎么判断？
	assert(pos);//暴力检查
	assert(pphead);

	SLTNode* newnode = BuyNode(x);

	//plist只有一个结点 == 头插
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//plist有多个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

//链表在pos位置之后插入
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	SLTNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//单链表的头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	SLTNode* Del = *pphead;
	*pphead = (*pphead)->next;
	free(Del);
}

//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* Del = *pphead;
		while (Del->next->next)
		{
			Del = Del->next;
		}
		free(Del->next);
		Del->next = NULL;

		//方法二
		/*SLTNode* Del = *pphead;
		SLTNode* prev = NULL;
		while (Del->next == NULL);
		{
			prev = Del;
			Del = Del->next;
		}
		free(Del);
		prev->next = NULL;*/
	}
}

//删除单链表在pos位置
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	//只有一个结点
	//有多个结点
	if (pos == *pphead)//头删
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* Del = *pphead;
		while (Del->next != pos)
		{
			Del = Del->next;
		}
		Del->next = pos->next;
		free(Del);
	}
}

//删除单链表在pos位置之后的结点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	assert(pphead);
	assert(*pphead);
	//只有一个结点
	//多个结点
	SLTNode* Del = pos;
	pos->next = Del->next;
	free(Del);
}

//查找pos位结点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

//修改pos位的结点数据
void SLTModify(SLTNode** pphead, SLTNode* pos,SLTDataType x)
{
	pos->data = x;
}


//销毁链表
void Destroy(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = cur->next;
	}
	*pphead = NULL;
}

单链表增删查改的实现