初阶数据结构【单链表及其接口的实现】

前言

在前面我们学到了数据结构中一个简单的数据结构—顺序表，通过我们对其的了解，我们不难知道，其实顺序表就是一个可以动态增长的数组，但是我们在对其进行增容时，往往增容是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
对此，我们引入链表：

一、链表

1.1 链表的概念及结构

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

1. 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续；
2. 现实中的结点一般都是从堆上申请出来的；
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表:

1.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.2.1 单向或者双向

1. 单向链表：每个节点只包含一个指向下一个节点的地址。它只能从前往后遍历，不能从后往前遍历；
2. 双向链表：每个节点包含两个地址，一个指向前一个节点，一个指向后一个节点。它可以从任一节点开始向前或向后遍历。
   单向链表
   
   双向链表
   

1.2.2 带头或者不带头

1. 带头链表：最前面有一个头节点，称作“哨兵位”，它不存储数据，用来指向第一个存储有效数据的节点；
2. 不带头链表：直接从第一个节点开始，没有额外的头节点。

带头链表

不带头链表

1.2.3 循环或者非循环

1. 循环链表：链表的最后一个节点的地址域指向链表的第一个节点，形成一个闭环;
2. 非循环链表：链表的最后一个节点的地址域为空（null），表示链表的结束。

循环链表

非循环链表

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

这期我们主要来看第一个：单向非循环链表的接口的实现：

二、单链表接口实现

我们先定义一个以下的单链表：

typedef int SListDataType;

typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;
}SListNode;

使用接口的时候我们将单链表的第一个节点的地址传个接口：
刚开始的时候我们还没有对单链表开辟空间，所以是个空链表，即头指针为NULL

//头指针
SListNode* pList = NULL;

2.1 单链表基本功能接口

打印输出

为了方便我们进行对其他接口的验证我们先写一个打印单链表的接口：

void SListPrint(SListNode* phead)
{
	//如果这个链表是空链表，那头指针就是指向NULL，所以此处无需加断言
	SListNode* cur = phead;
	if (cur == NULL)
	{
		printf("空链表!");
	}
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

空间的开辟接口

我们在实现单链表的增加和插入的时候，我们肯定会开辟一个新的节点，容易让程序冗余，所以我们写一个开辟一个新节点的函数接口，方便后面的使用：

//创造节点函数
SListNode* CreateSListNode(SListDataType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newNode->data = x; //放入数据x
	newNode->next = NULL;
	return newNode;
}

单链表销毁

当我们在程序彻底结束的时候要对我们开辟的空间进行一个释放，我们可以使用这个接口：
我们在写这个接口的时候我们要注意：

我们在释放一个节点后，下一个节点的地址就丢失了，所以我们要定义个指针变量cur来存储地址：
cur = plist；
先将plist指向下一个节点：plist = plist->next;
再释放cur的空间：free(cur);
最后将cur指向的空间更新为此时的plist

当cur为空的时候全部的节点被释放，结束循环：

void SListDestroy(SListNode* plist)
{
	assert(plist);  //防止plist为NULL
	SListNode* cur = plist;
	while (cur)
	{
		plist = plist->next;
		free(cur);
		cur = plist;
	}
}

2.2 单链表的增加节点接口

单链表的头插

我们首先用开辟新节点的接口来开辟一个新节点：newNode：

首先这里我们要注意先后顺序：

我们要先将新节点的next置为第一个节点的地址（即plist）； 再将头指针指向新节点：
newNode->next = *pphead;
*pphead = newNode;

如果相反，会造成原来的第一个节点地址丢失；

其次，这里我们要对plist的值做修改，所以我们要传plist的指针才可以达到此效果：

//头插
void SListPushFront(SListNode** pphead, SListDataType x)
{
	SListNode* newNode = CreateSListNode(x);
	newNode->next = *pphead;
	*pphead = newNode;
}

单链表的尾插

因为我们无法得知最后一个节点的地址，所以我们要进行找尾的操作：

这个时候跳出循环的tail就是最后一个节点的地址；

因为这个时候我们要对tail进行解引用，所以我们要单独考虑空链表的情况：

//尾插
void SListPushBack(SListNode** pphead, SListDataType x)
{
	SListNode* newNode = CreateSListNode(x);
	//如果phead为空
	if (*pphead == NULL)
	{
		*pphead = newNode;
	}
	else
	{
		//找尾
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
	
}

单链表在pos后插入接口

//插入（在后面）
void SListInsertAfter(SListNode* pos, SListDataType x)
{
	assert(pos);
	SListNode* newNode = CreateSListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

2.3 单链表的删除节点接口

单链表的头删

//头删
void SListPopFront(SListNode** pphead)
{
	//1.为空不删
	if (*pphead == NULL)  //防止我们对空指针进行解引用
	{
		return;
	}
	//2.如果只有1个节点 或 3.有一个以上的节点
	else
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

单链表的尾删

void SListPopBack(SListNode** pphead)
{
	//1.空
	if (*pphead == NULL)
	{
		return;
	}
	//2.只有一个
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//3.一个以上
	else
	{
		SListNode* prev = NULL;  //定义个指针prev来指向tail指向的节点的前一个节点；
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

单链表删除pos所指节点

//删除pos位置的节点
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->next;  //下一个节点的地址
	SListNode* nextnext = next->next;  //下下一个节点地址
	pos->next = nextnext;
	free(next);
}

2.4 单链表的修改接口

这个实现比较简单

//修改pos指向的节点值
void SListUpdata(SListNode* pos, SListDataType x)
{
	assert(pos);
	pos->data = x;
}

2.5 单链表的查找接口

为方便后面的插入接口我们需要找到单链表的某个节点的地址，以方便插入和修改：

我们采取遍历的方式，如果没有此节点，我们返回NULL

SListNode* SListFind(SListNode* plist, SListDataType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

完整的C语言实现源代码已绑定与本文绑定，大家自行下载；

总结

这期我们主要介绍了链表的相关概念和单链表的接口实现，下期我们将实现常用链表之一的双链表的接口实现；
最后，祝26考研一战成硕，加油！