数据结构之顺序表的相关知识点及应用

在前文顺序表中，我们学习了什么是线性表，以及线性表中的顺序表，最后我们也是实现了顺序表。接下来，就开始学习线性表的另一种——链表。

链表的概念及结构

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

链表的结构跟火车车厢是类似的，当人少或者非节假日时车次的车厢会相应减少，当人多或者节假日时车次的车厢会额外增加。只需要将火车的某节车厢去掉或者加上，不会影响其他车厢，每节车厢都是独立存在的，且每节车厢都有车门。想象一下，假设每节车厢的车门都是被锁上的，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？ 最简单的做法：每节车厢里都放一把下一节车厢的钥匙。下面就是火车和链表的具体图示：

与顺序表不同的是，链表里的每节“车厢”都是独立申请下来的空间，我们称之为“结点/节点” 。节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。 图中指针变量 plist 保存的是第一个节点的地址，我们称 plist 此时指向第一个节点，如果我们希望plist指向第二个节点时，只需要把plist保存的内容修改为0x0012FFA0。 为什么还需要指针变量来保存下一个节点的位置？ 因为链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。 结合前面学到的结构体知识，我们可以给出每个节点对应的结构体代码： 假设当前保存的节点为整型：

struct SListNode
{
	int data; //节点想保存的数据
	struct SListNode* next; //指向下一个节点的指针
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数 据，也需要保存下一个节点的地址（当下一个节点为空时，即该节点为最后一个节点时，保存的地址为空）。 当我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿到下一个节点的地址（下一个节点的钥匙）就可以了。

链表与顺序表的区别与优劣势

顺序表的优势：顺序表可以随机访问其中的元素，而链表不可以。就是因为顺序表的底层是数组，而数组是可以通过下标达到随机访问的目的。而链表只能通过指针去遍历访问。

链表的优势：插入或者删除数据时，不需要移动其它元素；不需要开辟过多的空间，按需所给，即用多少，给多少，不会浪费空间。

链表的分类

链表根据：是否带头，单双向，是否循环，分为八大类。

重点有两个：单链表和双链表。

单链表：不带头单向不循环链表；双链表：带头双向循环链表。

头指的是头节点，也叫做哨兵位。头节点中存放的是无效信息，只是一个哨兵的作用。

注意：头节点在单链表中不存在，只是为了更好的理解，才引用了这个。

单向是指：

双向是指：

从前一个节点指向后一个节点（例如：1->2）的指针被称为后继指针。

从后一个节点指向前一个节点（例如：2->1）的指针被称为前驱指针。

循环是指链表是否成环。

单链表的实现

接下来，我们就开始用单链表实现对数据的增加，查找，删除。

在创建单链表之前，要做一些提前准备。创建3个文件：SList.h   SList.c  test.c  前面两个是实现单链表的，而后面的test.c文件是测试单链表的各种功能。链表是由一个个的节点串联组成的。

创建节点：

typedef int SLTDataType;

//创建一个节点
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;//注意这里不能写重命名之后的
}SListNode;

其实这个链表不需要初始化，因为我们的空间都是按需所给的，不存在没有用到的空间。

单链表中增加节点 

接下来就是要开始增加数据了，在增加数据之前首先得有空间（节点），因此我们就先得写申请空间的函数（以后增加数据都得用到，因此就封装成函数）。这里不需要判断空间是否充足。

增加节点并初始化节点：

//增加节点(空间)
SListNode* SLTBuyNode(SLTDataType x)
{
	//开辟一个节点的空间
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	//判断是否开辟成功
	if (newnode == NULL)//失败
	{
		perroe("malloc:");
		exit(1);
	}
	//成功就先把节点数据设置好，再返回这个新节点的地址
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

单链表中尾插数据 

当我们增加了多个节点之后，就可以尝试把节点串联起来形成一个链表了。那怎么串联呢？可以把新增加的节点地址给到链表中最后一个节点中的指针。这个过程其实就是尾插数据。

 情况一：原链表中有节点

思路：先把遍历找到 plist->next == NULL，再把 plist->next 改为新增加的节点的地址，就相当于把新增加的节点串联到原链表中去了。

情况二：原链表中没有节点

思路：这个就只需要把新增加的节点的地址，直接给头节点（我们给的指针，可以看看代码）就可以了。

//尾插数据
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);//不能为空，否则就会对空指针解引用，从而报错
	//首先判断是否为空，再根据判断的情况来尾插
	if (*pphead == NULL)//指向头节点的指针为空，也就是链表为空
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* newnode = *pphead;//头指针
		while (newnode->next)
		{
			newnode = newnode->next;
		}
		//此时newnode为尾节点
		newnode->next = SLTBuyNode(x);
	}
}

这里可能会有小伙伴有疑惑：为什么要用二级指针来接收？这里首先得弄清楚什么时候用用一级指针，什么时候用二级指针？ 要想清楚修改的是指针所指向的对象还是要修改指针本身，如果要修改指针指向的对象（不要需改变一级指针的值，传本身），用一级指针就行，如果要修改的是指针变量的内容（要改变一级指针的值，就得传地址），就需要对指针变量进行取地址，用二级指针接收。那么接下来就得判断是否需要改变头指针的值？当链表中没有数据时，头指针的值就会被改变，此时就需要传一级指针的地址。而有数据的话，头指针的指向就不会改变。但因为这里情况不确定，就需要全部考虑，因此，就得用二级指针来接收。

如果在下面的函数中存在要改变头指针的情况，我们就需要用二级指针。 

打印单链表中节点的数据 

尾插完之后，我们就需要检测是否正确，因此可以封装一个函数——打印节点数据。

//打印节点数据
void SLTPrint(SListNode* phead)
{
	SListNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

单链表中头插数据 

接下来，就开始实现头插。

同样也有两种情况：

情况一：原链表中有数据

思路：先创建一个新的节点，把新节点的地址给*pphead，再把新节点的next指针指向原来头指针指向的地址。

情况二：原链表中没有数据

思路：和上面一样，这个只要把新的节点的地址给到*pphead，就可以了。

//头插数据
void SLTPushFront(SListNode** pphead, SLTDataType x)
{
	assert(pphead);
	//判断是否为空
	if (*pphead == NULL)
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* pcur = *pphead;
		*pphead = SLTBuyNode(x);
		(*pphead)->next = pcur;//注意操作符的优先级
	}
}

单链表中查找数据 

接下来就开始通过给的节点数据来查找该节点的地址。

思路：通过头指针来遍历整个链表，如果 plist->data == x，就说明找到了，返回 plist 此时的值；如果plist = NULL了，就说明这个链表中没有该数据，返回一个空指针就行了。 

//查找数据
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{
	assert(phead);
	SListNode* plist = phead;
	while (plist)
	{
		if (plist->data == x)
		{
			return plist;
		}
		plist = plist->next;
	}
	return NULL;
}

有了查找函数，就可以实现任意位置的增加数据和删除数据的操作了。

单链表中尾删数据  

情况一：当链表有多个数据： 

思路：先通过头指针找到尾节点的前一个节点，再把尾节点空间释放掉， 最后把plist->next 为尾指针的指针置为空。（注意：顺序不能反过来，因为如果先把plist->next置为空之后，再去找就找不到了。）

情况二：当链表只有一个数据：（当没有数据时，采取强制措施）

思路：就只需要把这个节点给释放掉就行了。

//尾删数据
void SLTPopBack(SListNode** pphead)
{
	assert(pphead && *pphead);//*pphead不能为空，否则就是空链表
    //注意操作符的优先级
	if ((*pphead)->next == NULL)//只有一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* plist = *pphead;
		//找到尾节点的前一个节点
		while (plist->next->next)
		{
			plist = plist->next;
		}
		free(plist->next);
		plist->next = NULL;
	}
}

单链表中头删数据 

情况一：单链表中有多个数据：

思路：先把头指针的值拷贝一份，把这个头指针改为 phead->next，再把拷贝指向的节点给给释放掉。

情况二：单链表中只有一个节点数据： 

思路：直接把这个空间给释放掉，再把头指针置为空。

//头删数据
void SLTPopFront(SListNode** pphead)
{
	assert(pphead && *pphead);
	//注意操作符的优先级
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* pcur = *pphead;
		*pphead = (*pphead)->next;
		free(pcur);
	}
}

单链表中在指定位置之前插入数据 

注意：这里我们所说的指定位置一定要存在，不考虑不存在的情况。 

情况一：指定位置不是头指针

思路：先创建一个新的节点，在原链表中找到pos的前一个节点，在前一个节点的next指针指向新增加的节点，接着，在把新增加的节点的next指针指向pos这个节点的地址。 

情况二：指定位置是头指针——头插

情况三：链表中没有数据——我们也就不能通过pos找到在哪里插入数据，因此我们就采用断言。

//在指定位置之前插⼊数据
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
    assert(pos);//这个位置肯定要存在
	//先判断插入的位置
	if (*pphead == pos)
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SListNode* pcur = SLTBuyNode(x);//要插入的节点
		SListNode* prev = *pphead;
		while (prev->next != pos)//找到pos的前一个节点
		{
			prev = prev->next;
		}
		prev->next = pcur;
		pcur->next = pos;
	}
}

有在指定位置之前插入肯定就有在指定位置之后插入

单链表中在指定位置之后插入数据

情况一：pos这个位置存在

思路：先创建一个新的节点，再把新增加的节点的next指针指向原链表pos下一个节点的地址，接着把pos位置的节点的next指针改为新增加的节点的地址。

情况二：pos这个位置不存在，同样要报错，既然是在指定位置之后插入数据，就肯定要存在这个位置，不然谈何插入呢。

//在指定位置之后插入数据
void SLTInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode *pcur = SLTBuyNode(x);
	//下面的顺序不能反过来
	pcur->next = pos->next;
	pos->next = pcur;
}

注意：如果把pos下一个节点的地址记录下来了，就可以更改顺序。不能更改顺序的原因是原链表中pos下一个节点的地址会找不到。

单链表中删除pos节点的位置

情况一：pos这个位置的节点存在

思路：先通过头指针遍历找到pos前一个位置的节点，把pos前一个节点的next改为指向pos->next，再把pos这个节点的空间销毁就行了。

注意：因为节点的空间都是我们通动态内存开辟来的，因此我们要用free手动销毁它。 

还有一种特殊且容易忽略的情况：要删除的位置是头节点——头删

情况二：pos这个位置不存在——直接报错就行

//删除pos节点
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//先判断是否为头节点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		//找到pos前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

单链表中删除pos节点之后的位置 

情况一：存在pos的位置

思路：把pos->next->next的值赋值给一个新的指针，再把pos->next的空间释放，最后把新指针的值给到pos->next就可以了。

情况二：不存在pos位置，pos->next要不为空，也就是pos后面必须要有节点

//删除pos之后的节点
void SLTEraseAfter(SListNode* pos)
{
	assert(pos && pos->next);//如果pos后面没节点了，就不能删了
	SListNode* pcur = pos->next;
	pos->next = pos->next->next;
	free(pcur);
	pcur = NULL;
}

销毁链表 

//销毁链表
void SListDesTroy(SListNode** pphead)
{
	assert(pphead && *pphead);//检查
	SListNode* pcur = *pphead;
	while (pcur)
	{
		SListNode* nextNode = pcur->next;//先把pcur的下一个节点的地址存起来
		free(pcur);//释放掉pcur的节点空间
		pcur = nextNode;//把pcur指向next
	}
	*pphead = NULL;
}

 上面就是单链表的全部逻辑以及实现。

单链表源码

下面是单链表的源码：

SList.h

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

typedef int SLTDataType;

//创建一个节点
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;//注意这里不能写重命名之后的
}SListNode;

//增加节点(空间)
SListNode* SLTBuyNode(SLTDataType x);

//尾插数据
void SLTPushBack(SListNode** pphead, SLTDataType x);

//打印节点数据
void SLTPrint(SListNode* phead);

//头插数据
void SLTPushFront(SListNode** pphead, SLTDataType x);

//查找数据
SListNode* SLTFind(SListNode* phead, SLTDataType x);

//尾删数据
void SLTPopBack(SListNode** pphead);

//头删数据
void SLTPopFront(SListNode** pphead);

//在指定位置之前插⼊数据
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x);

//在指定位置之后插入数据
void SLTInsertAfter(SListNode* pos, SLTDataType x);

//删除pos节点
void SLTErase(SListNode** pphead, SListNode* pos);

//删除pos之后的节点
void SLTEraseAfter(SListNode* pos);

//销毁链表
void SListDesTroy(SListNode** pphead);

SList.c

#include "SList.h"

//增加节点(空间)并初始化
SListNode* SLTBuyNode(SLTDataType x)
{
	//开辟一个节点的空间
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	//判断是否开辟成功
	if (newnode == NULL)//失败
	{
		perror("malloc:");
		exit(1);
	}
	//成功就先把节点数据设置好，再返回这个新节点的地址
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}


//尾插数据
void SLTPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);//不能为空，否则就会对空指针解引用，从而报错
	//首先判断是否为空，再根据判断的情况来尾插
	if (*pphead == NULL)//指向头节点的指针为空，也就是链表为空
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* newnode = *pphead;//头指针
		while (newnode->next)
		{
			newnode = newnode->next;
		}
		//此时newnode为尾节点
		newnode->next = SLTBuyNode(x);
	}
}


//打印节点数据
void SLTPrint(SListNode* phead)
{
	SListNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}


//头插数据
void SLTPushFront(SListNode** pphead, SLTDataType x)
{
	assert(pphead);
	//判断是否为空
	if (*pphead == NULL)
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* pcur = *pphead;
		*pphead = SLTBuyNode(x);
		(*pphead)->next = pcur;
	}
}


//查找数据
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{
	assert(phead);
	SListNode* plist = phead;
	while (plist)
	{
		if (plist->data == x)
		{
			return plist;
		}
		plist = plist->next;
	}
	return NULL;
}


//尾删数据
void SLTPopBack(SListNode** pphead)
{
	assert(pphead && *pphead);//*pphead不能为空，否则就是空链表
	//注意操作符的优先级
	if ((*pphead)->next == NULL)//只有一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* plist = *pphead;
		//找到尾节点的前一个节点
		while (plist->next->next)
		{
			plist = plist->next;
		}
		free(plist->next);
		plist->next = NULL;
	}
}


//头删数据
void SLTPopFront(SListNode** pphead)
{
	assert(pphead && *pphead);
	//注意操作符的优先级
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* pcur = *pphead;
		*pphead = (*pphead)->next;
		free(pcur);
	}
}


//在指定位置之前插⼊数据
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);//这个位置肯定要存在
	//先判断插入的位置
	if (*pphead == pos)
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SListNode* pcur = SLTBuyNode(x);//要插入的节点
		SListNode* prev = *pphead;
		while (prev->next != pos)//找到pos的前一个节点
		{
			prev = prev->next;
		}
		prev->next = pcur;
		pcur->next = pos;
	}
}


//在指定位置之后插入数据
void SLTInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode *pcur = SLTBuyNode(x);
	//下面的顺序不能反过来
	pcur->next = pos->next;
	pos->next = pcur;
}


//删除pos节点
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//先判断是否为头节点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		//找到pos前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}


//删除pos之后的节点
void SLTEraseAfter(SListNode* pos)
{
	assert(pos && pos->next);//如果pos后面没节点了，就不能删了
	SListNode* pcur = pos->next;
	pos->next = pos->next->next;
	free(pcur);
	pcur = NULL;
}


//销毁链表
void SListDesTroy(SListNode** pphead)
{
	assert(pphead && *pphead);
	SListNode* pcur = *pphead;
	while (pcur)
	{
		SListNode* nextNode = pcur->next;//先把pcur的下一个节点的地址存起来
		free(pcur);//释放掉pcur的节点空间
		pcur = nextNode;//把pcur指向next
	}
	*pphead = NULL;
}

好啦！本期数据结构单链表的学习就到此为止啦！我们下一期再一起学习吧！