数据结构之单链表

前言：上一篇文章我们了解到顺序表，这一次来看另一种线性表-------单链表。

1. 单链表的概念

单链表，想必很多人会感到陌生吧。那么，到底什么是单链表呢？先了解清楚单链表的概念及特性，才能够更好的实现单链表。

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

单链表就像火车车厢一样，每节车厢都通过链条进行链接。

那么，在链表里每节“车厢”是怎样的呢？

不过，在数据结构里“车厢”有一个专属名词-----节点（结点）。与顺序表不同的是，链表里的每节车厢都是独立申请下来的空间，我们称之为节点。

节点主要由两部分组成，当前节点要保存的数据和保存下一个节点的地址。

链表的性质：

1.链式结构在逻辑上是连续的，在物理结构上不一定是连续的。

2.节点一般是从堆上申请的。

3.从堆上申请出来的空间可能连续也可能不连续。

现在我们已经了解到了链表的结构，接下来要该如何设计链表呢？在节点里需要保存数据及保存下一个节点的地址。这是两个不同的数据类型，因此使用结构体，也便于代码的可读性与可维护性。

2. 单链表的实现

2.1 单链表的定义

//链表存储数据类型
typedef int SLDataType;
//单链表的定义
typedef struct SinglyLinkedList
{
	SLDataType data;//保存的数据
	struct SinglyLinkedList* next;//存储下一个节点的地址
}SList;

2.2 单链表的接口

//打印单链表
void DisplaySList(SList* phead);

//尾插
void SListPushBack(SList** pphead, SLDataType x);

//尾删
void SListPopBack(SList** pphead);

//头插
void SListPushFront(SList** pphead, SLDataType x);

//头删
void SListPopFront(SList** pphead);

//单链表查找
SList* SListFind(SList* phead, SLDataType x);

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x);

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x);

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos);

//销毁链表
void SListDestroy(SList** pphead);

2.2.1 单链表尾插

//尾插
void SListPushBack(SList** pphead, SLDataType x)
{
	assert(pphead);
	//开辟一个节点大小的空间，开辟失败就退出程序。
	/*SList* newnode = (SList*)malloc(sizeof(SList));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;*/
	
	//SListBuyNewNode是一个创建新节点的函数，不仅仅在尾插
	//中需要创建节点，在头插中也需要。因此为了避免代码冗余以
	//及代码的可读性与可维护性，将创建新节点的功能封装成一个
	//函数来实现。
	SList* newnode = SListBuyNewNode(pphead, x);
	//单链表为空的情况
	if (NULL == *pphead)
	{
		//plist为空，让plist指向newnode,指向链表的头结点
		*pphead = newnode;
	}
	else
	{
		SList* tail = *pphead;
		//找尾节点
		while (NULL != tail->next)
		{
			tail = tail->next;
		}
		//连接新的节点
		tail->next = newnode;
	}
 }

尾插数据需要一个节点大小的空间，用来存储数据及保存下一个节点的地址。因此首先申请一块节点大小的空间。

接下来又分两种情况：

1.plist指向空，需要让plist指向链表头结点。

2.plist不指向空，新申请的结点直接连接在链表尾节点的后面。

assert(pphead);
pphead保存的是一级指针变量plist的地址，所以pphead一定不为
空。对pphead进行断言，是为了防止参数传输错误。

还有一个问题，不知道大家发现没有。这里为什么要用二级指针呢？答案很简单。plist是一个结构体指针，在尾插中有可能要改变plist，因此要用二级指针。这涉及到了实参与形参的关系。

2.2.2 创建新节点

//创建新节点
SList* SListBuyNewNode(SList** pphead,SLDataType x)
{
	SList* newnode = (SList*)malloc(sizeof(SList));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2.2.3 打印单链表

//打印单链表
//这里也可以用二级指针来接收，保持代码风格的一致性
void DisplaySList(SList* phead)
{
	SList* cur = phead;
	while (NULL != cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SList* cur=phead,此时cur指向了链表的头结点，只要cur不等于
NULL，就打印链表节点里的数据。然后更新cur,指向下一个节点。

2.2.4 单链表尾删

//尾删
void SListPopBack(SList** pphead)
{
	assert(pphead);
	//单链表为空的情况
	assert(*pphead);
	//单链表至少有一个节点
	if (NULL == (*pphead)->next)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SList* tail = *pphead;
		SList* prev = NULL;
		//找尾节点
		while (NULL != tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		//释放尾节点的空间
		free(tail);
		tail = NULL;
	}
}

这里包含了3种情况：

1.plist指向空，代表没有链表（没有数据可以删除）

2.有多个节点

3.只有一个节点

画图分析：

1.尾删节点首先将尾节点的空间还给操作系统，然后再让尾节点的前
一个节点指向空（防止野指针的出现）
2.一直尾删，直到剩下一个节点。这个时候再尾删就要改变plist指针
了，因此尾删也需要二级指针
3.在尾删节点的时候，需要找到尾节点才能删除，由于单链表具有单
向性，因此还需要一个前驱指针，用来记录尾节点的前一个节点。

2.2.5 单链表头插

//头插
void SListPushFront(SList** pphead, SLDataType x)
{
	assert(pphead);
	//创建新节点
	SList* newnode = SListBuyNewNode(pphead, x);
	//新节点成为链表的头结点
	newnode->next = *pphead;
	//plist指向链表的头结点
	*pphead = newnode;
}

注意：一定要先让新节点的next保存当前plist的值，再更新plist，指向新的头结点。

2.2.6 单链表头删

//头删
void SListPopFront(SList** pphead)
{
	assert(pphead);
	//单链表为空的情况
	assert(*pphead);
	//记录当前头结点
	SList* cur = *pphead;
	//更新plist
	*pphead = (*pphead)->next;
	//释放头结点的空间
	free(cur);
	cur = NULL;
}

注意：
1.先让plist指向当前头结点的下一个节点，如果先删除当前头
结点，就找不到下一个节点了。
2.释放当前头结点的空间。
2.plist为空，说明链表为空，没有数据删除。

2.2.7 单链表查找

//单链表查找
SList* SListFind(SList* phead, SLDataType x)
{
	//单链表为空不查找
	assert(phead);

	SList* cur = phead;
	while (NULL != cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

从头结点开始遍历进行查找，找到了就返回该节点的地址，否则返回NULL。

2.2.8 从指定位置之后开始插入数据

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x)
{
	assert(pphead);
	//创建新节点
	SList* newnode = SListBuyNewNode(pphead, x);
	//链表为空
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		SList* cur = *pphead;
		//找pos位置
		while (NULL != cur)
		{
			if (cur == pos)
			{
				newnode->next = cur->next;
				cur->next = newnode;
			}
			cur = cur->next;
		}
	}
}

从头结点开始遍历找pos位置，找到pos位置将新节点插入进去。

注意：让新节点的next保存pos位置下一个节点的地址，再让pos位置的节点的next保存新节点的地址。

2.2.9 从指定位置之前插入数据

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x)
{
	assert(pphead);
	//创建新节点
	SList* newnode = SListBuyNewNode(pphead, x);
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		SList* cur = *pphead;
		//记录pos位置前一个节点
		SList* prev = NULL;
		while (NULL != cur)
		{
			if (cur == pos)
			{
				newnode->next = prev->next;
				prev->next = newnode;
			}
			prev = cur;
			cur = cur->next;
		}
	}
}

从头结点开始遍历找pos位置，找到pos位置，让pos位置的前一个节点的next保存新节点的地址，新节点的next保存pos位置节点的地址。

2.2.10 从指定位置删除数据

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos)
{
	assert(pphead);
	//单链表为空
	assert(*pphead);

	SList* cur = *pphead;
	//找pos位置
	while (NULL != cur->next)
	{
		if (cur->next == pos)
		{
			cur->next = pos->next;
			free(pos);
			pos = NULL;
		}
		cur = cur->next;
	}
}

单链表不能为空，为空说明没有数据可以删除。找到pos位置，让pos位置的前一个节点的next指向pos位置节点的下一个节点，然后再释放掉pos位置的节点。

2.2.11 销毁链表

//销毁链表
void SListDestroy(SList** pphead)
{
	assert(pphead);
	SList* cur = *pphead;
	while (NULL != cur)
	{
		SList* prev = cur;
		cur = cur->next;
		free(prev);
		prev = NULL;
	}
	*pphead=NULL;
}

从头结点开始遍历，先让cur指向头结点的下一个节点，再释放掉当前
的头结点。最后再让*pphead=NULL。在循环过程中，*pphead的指
向一直没有发生改变，销毁链表时，也要让plist指向空，防止出现野
指针。

3. 单链表完整代码的实现

SList.h的实现

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

typedef int SLDataType;

typedef struct SinglyLinkedList
{
	SLDataType data;
	struct SinglyLinkedList* next;//存储下一个节点的地址
}SList;


//打印单链表
void DisplaySList(SList* phead);

//尾插
void SListPushBack(SList** pphead, SLDataType x);

//尾删
void SListPopBack(SList** pphead);

//头插
void SListPushFront(SList** pphead, SLDataType x);

//头删
void SListPopFront(SList** pphead);

//单链表查找
SList* SListFind(SList* phead, SLDataType x);

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x);

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x);

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos);

//销毁链表
void SListDestroy(SList** pphead);

SList.c实现

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

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

//创建新节点
SList* SListBuyNewNode(SList** pphead,SLDataType x)
{
	SList* newnode = (SList*)malloc(sizeof(SList));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//尾插
void SListPushBack(SList** pphead, SLDataType x)
{
	assert(pphead);
	/*SList* newnode = (SList*)malloc(sizeof(SList));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;*/
	SList* newnode = SListBuyNewNode(pphead, x);
	//单链表为空的情况
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		SList* tail = *pphead;
		while (NULL != tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
 }

//尾删
void SListPopBack(SList** pphead)
{
	assert(pphead);
	//单链表为空的情况
	assert(*pphead);
	//单链表至少有一个节点
	if (NULL == (*pphead)->next)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SList* tail = *pphead;
		SList* prev = NULL;
		while (NULL != tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}
}

//头插
void SListPushFront(SList** pphead, SLDataType x)
{
	assert(pphead);
	/*SList* newnode = (SList*)malloc(sizeof(SList));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;*/
	SList* newnode = SListBuyNewNode(pphead, x);
	//至少有一个节点
	/*if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}*/

	newnode->next = *pphead;
	*pphead = newnode;
}

//头删
void SListPopFront(SList** pphead)
{
	assert(pphead);
	//单链表为空的情况
	assert(*pphead);

	SList* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
	cur = NULL;
}

//单链表查找
SList* SListFind(SList* phead, SLDataType x)
{
	//单链表为空不查找
	assert(phead);

	SList* cur = phead;
	while (NULL != cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//从指定位置之后开始插入数据
void SListInsertAfter(SList** pphead, SList* pos, SLDataType x)
{
	assert(pphead);
	SList* newnode = SListBuyNewNode(pphead, x);
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		SList* cur = *pphead;
		while (NULL != cur)
		{
			if (cur == pos)
			{
				newnode->next = cur->next;
				cur->next = newnode;
			}
			cur = cur->next;
		}
	}
}

//从指定位置之前插入数据
void SListInsert(SList** pphead, SList* pos, SLDataType x)
{
	assert(pphead);
	SList* newnode = SListBuyNewNode(pphead, x);
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		SList* cur = *pphead;
		SList* prev = NULL;
		while (NULL != cur)
		{
			if (cur == pos)
			{
				newnode->next = prev->next;
				prev->next = newnode;
			}
			prev = cur;
			cur = cur->next;
		}
	}
}

//从指定位置删除数据
void SListErase(SList** pphead, SList* pos)
{
	assert(pphead);
	//单链表为空
	assert(*pphead);

	SList* cur = *pphead;
	while (NULL != cur->next)
	{
		if (cur->next == pos)
		{
			cur->next = pos->next;
			free(pos);
			pos = NULL;
		}
		cur = cur->next;
	}
}

//销毁链表
void SListDestroy(SList** pphead)
{
	assert(pphead);
	SList* cur = *pphead;
	while (NULL != cur)
	{
		SList* prev = cur;
		cur = cur->next;
		free(prev);
		prev = NULL;
	}
	*pphead=NULL;
}

test.c的实现

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

void TestSList1()
{
	SList* plist = NULL;

	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);

	DisplaySList(plist);

	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);

	DisplaySList(plist);

}

void TestSList2()
{
	SList* plist = NULL;

	SListPushFront(&plist, 10);
	SListPushFront(&plist, 20);
	SListPushFront(&plist, 30);
	SListPushFront(&plist, 40);

	DisplaySList(plist);

	SListPopFront(&plist);

	DisplaySList(plist);

	SList* pos = SListFind(plist, 50);
	if (NULL != pos)
	{
		printf("%d\n", pos->data);
	}
	else
	{
		printf("找不到\n");
	}

}

void TestSList3()
{
	SList* plist = NULL;

	SListInsertAfter(&plist, NULL, 10);

	DisplaySList(plist);

	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);

	SList* pos = SListFind(plist, 4);

	SListInsertAfter(&plist, pos, 20);

	DisplaySList(plist);

	pos = SListFind(plist, 2);

	SListInsert(&plist, pos, 30);

	DisplaySList(plist);

	pos = SListFind(plist, 3);

	SListErase(&plist, pos);

	DisplaySList(plist);

	SListDestroy(&plist);

}

int main()
{
	//TestSList1();

	//TestSList2();

	TestSList3();

	return 0;
}