数据结构之单链表（不带头单向非循环链表）

一.引言

上一节我们学过了顺序表，那么我们想想顺序表有没有问题呢？我们来讨论顺序表的问题及思考。

顺序表问题：

1.中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到

200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

由于我们上一章主要放在了动态顺序表，那么我们以其为主进行讨论：

动态顺序表要求：
1、插入数据，空间不够了.要增容
2、要求数据是依次存储的

因此就会有以下问题：
1、如果空间不够，增容。增容会付出一定性能消耗，其次可能存在一定的空间浪费
2、头部或者中部左右的插入删除效率低。 -》0(N)

如何解决:
1、空间上，按需给空间
2、不要求 物理空间连续，头部和中间的插入，就不需要挪动数据

我们引入链表概念。

二.链表介绍

概念：链表是一种 物理存储结构上 非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表

中的 指针链接 次序实现的

链表分类：

实际中链表的结构非常多样，常见有以下 8 种链表结构类型：

区分规则：单向/双向循环/不循环带头/不带头

1.不带头单向非循环链表

2.不带头单向循环链表

3.不带头双向不循环链

4.不带头双向循环链表

5. 带头单向非循环链表

6. 带头单向循环链表

7. 带头双向非循环链表

8.带头双向循环链表

接下来本文主要讲不带头单向非循环链表单链表，当然其他的也会在后面文章讲解：

三.不带头单向非循环链表的实现

我们还是分步骤来进行讲解：

第一步：

建立一个结构体：

//建立结构体
typedef int SLTDateType;//便于其他如char float类型转换
typedef struct SList
{
	SLTDateType date;
	struct SList* next;//注意不能写成struct SList next，这样写会一直调用该结构体，会一直循环
}SL;//重命名

这里我们再次强调一下：链表是通过地址将一个个数据联系起来的，因此我们在结构体中要有一个成员为struct类型，连接下个结构体数据，但是我们又不能直接写成结构体成员，理由里面写了，因此我们用结构体指针最好，可以直接指向下个结构体数据，正符合访址连接。

第二步：

我们开始实现接口，先实现打印接口

//打印单链表
void SListPrint(SL* phead)
{
	SL* cur = phead;//定义cur指向phead指向的地址
	while (cur != NULL)//当cur不为空指针时
	{
		printf("%d->", cur->date);//输出当前指向的结构体成员date的值
		cur = cur->next;//使cur指向下一个链表的位置
	}
	//当为NULL时
	printf("NULL\n");//结尾用NULL表示，便于理解
}

第三步：

开辟空间函数（重点）

// 动态申请一个结点
SL* BuySListNode(SLTDateType x)//注意：返回的是一个SL指针，形参为x
{
	SL* newnode = (SL*)malloc(sizeof(SL));//动态开辟一个SL结构体大小的内存空间，并且用newnode指针指向该空间
	if (newnode == NULL)//判断指向的空间是否为空
	{
		perror("malloc fail:");
		return 1;
	}
	//不为空时：
	newnode->date = x;//传值
	newnode->next = NULL;//将newnode指向的结构体中成员struct SList* next为空指针，即不指向其他位置
	return newnode;//返回该结构体地址
}

学会画图理解！！！

第四步：

实现头插，头删，尾删，尾插四个函数

我们先写个尾插函数，顺便检查前面写的有没有问题

// 单链表尾插
void SListPushBack(SL** pphead, SLTDateType x)
{
	//传的是指针的地址，因此用二级指针接收
	//开辟空间
	SL* newnode =BuySListNode(x);
	//判断*pphead是否为空指针
	if (*pphead == NULL)
	{
		*pphead = newnode;//当为空时，将newnode指向的结构体空间赋给*pphead
	}
	else//否者，进行将newnode指向的空间连接到后面
	{
		SL* tail = *pphead;
		while (tail->next!=NULL)//注意这样写可以保证tail的位置是链表的最后位置
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

接下来我们检测下：

非常完美，没问题，那么我们就快速实现其他几个函数吧！

//单链表头插
void SListPushFront(SL** pphead, SLTDateType x)
{
	//开辟空间
	SL* newnode = BuySListNode(x);
	//判断是否开辟成功
	if (newnode == NULL)
	{
		perror(newnode);
		return 0;
	}
	//成功
	newnode->next =*pphead;//将开辟的结构体成员struct SList* next指向原链表的第一个数据
	*pphead = newnode;//将原指向开头链表的指针指向newnode
}

//单链表尾删定义
void SListPopBack(SL** pphead)
{
	SL* fast = *pphead;
	//情况一：*pphead直接为空指针
	if (*pphead == NULL)
	{
		perror(*pphead);
		return 1;
	}
	//情况二：链表只有一个结构体成员
	if (fast->next==NULL)
	{
		free(*pphead);
		free(fast);
		pphead = NULL;
		return 0;
	}
	//对于尾删，我们可以利用双指针法
	//fast指针比slow指针快，这样便于留住要的地址
	SL* slow = NULL;//
	while (fast->next != NULL)//画图理解会简单点
	{
		//如果fast指针指向的结构体存在
		slow = fast;//将slow指针移动到fast位置
		fast = fast->next;//fast指针前移
	}
	//此时slow指针为链表倒数第二个值
	free(fast);//fast指针可以释放了
	slow->next = NULL;//将链表倒数第二个结构体指向NULL，防止野指针
}

尾删还是有点难度的，需要画图仔细理解一下，同时要注意考虑全面！！！

//单链表头删定义
void SListPopFront(SL** pphead)
{
	//头删步骤：1,保留链表第二个结构体，2.free第一个结构体，3.将*pphead指向第二个结构体
	SL* next = (*pphead)->next;//步骤1
	free(*pphead);//步骤二
	*pphead = next;//步骤三
}

打印观察上面的程序：

#include "SList.h"

void Test1()
{
	//调用函数
	SL* plist= NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	//打印观察
	SListPrint(plist);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPushFront(&plist, 7);
	//打印观察
	SListPrint(plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	//打印观察
	SListPrint(plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	//打印观察
	SListPrint(plist);
}

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

结果：

可见，上述代码没有问题！

第五步：

实现一些特殊接口：查找接口，随机删除接口，随机插入接口

//单链表寻找定义
SL* SListFind(SL* phead, SLTDateType x)
{
	SL* cur = phead;//定义一个cur指针指向链表第一个结构体
	while (cur != NULL)//等价于while(cur)，如果cur指向的结构体不为空
	{
		//判断关系
		if (cur->date == x)//如果相等
		{
			return cur;//返回cur指针
		}
		cur = cur->next;//否者，指针指向下一个结构体
	}
	//如果走完了还没有找到，返回NULL
	return NULL;
}

//单链表随机插入定义(本质上是在pos前插入)
void SListinsert(SL** pphead,SL* pos, SLTDateType x)
{
	//判断是否存在节点
	if (pos == *pphead)
	{
		//无节点情况
		//此时直接等价于头插
		SListPushFront(pphead,x);//这里直接写pphead，原因是因为直接传pphead，可以直接接收
	}
	else 
	{
		//插入要开辟空间
		SL* newnode = BuySListNode(x);
		SL* prev = *pphead;//定义一个指针指向链表第一个结构体
		while (prev->next != pos)//不满足
		{
			prev = prev->next;//继续
		}
		//满足,进行插入操作
		prev->next = newnode;
		newnode->next = pos;
	}
}

检查这两个：

void Test2()
{
	SL* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SL* pos = SListFind(plist, 3);
	if (pos)
	{
		SListinsert(&plist,pos,30);
		SListinsert(&plist, pos, 40);
		pos = pos->next;
		SListinsert(&plist, pos, 30);
	}
	//打印观察
	SListPrint(plist);
}
int main()
{
	Test2();
	return 0;
}

结果：

下面来实现随机删除：

//单链表随机删除定义（本质上是删除pos位置的结构体)
void SListErase(SL** pphead, SL* pos)
{
	//判断
	//如果链表无成员
	if (pos == *pphead)
	{
		//此时直接等价于头删
		SListPopFront(pphead);//注意：这里是pphead
	}
	SL* prev = *pphead;//定义一个指针指向链表第一个结构体
	while (prev->next!=pos)//判断指针的下一个节点是否为pos位置
	{
		prev = prev->next;//后移
	}
	//如果是pos位置
	prev->next = pos->next;//将指针prev指向的位置改成pos指针指向的位置
	free(pos);//释放pos指针
}

检查：

void Test2()
{
	SL* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SL* pos = SListFind(plist, 3);
	if (pos)
	{
		SListinsert(&plist,pos,30);
		SListinsert(&plist, pos, 40);
		pos = pos->next;
		SListinsert(&plist, pos, 50);
		
	}
	//打印观察
	SListPrint(plist);
	SL* pos2 = SListFind(plist, 30);
	if (pos2)
	{
		SListErase(&plist, pos2);
	}
	//打印观察
	SListPrint(plist);
}
int main()
{
	Test2();
	return 0;
}

结果：

no err

接下来，我们实现最后一个函数：销毁函数

//单链表销毁定义
void SListDestory(SL* phead)
{
	free(phead->next);
	phead->date = 0;
}

最后：在这里感谢大家的支持，让我们继续前行，加油！