数据结构——链表（单链表）

大家好，又是我（小锋），今天给大家带了一个比较有挑战的章节（链表），但是不用担心，小锋会陪大家一起度过。

顺序表的思考与问题

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

我们在进行一些插入删除操作时我们会先内存覆盖然后再进行操作，覆盖内存的时间复杂度为O(N)。

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

当我们进行扩容时我们是不是要用realloc函数，而realloc函数再扩容时分为异地扩容，和原地扩容，当我们异地扩容时又有一系列的操作这又加大了消耗。

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

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

我们增加容量后可能用不完，这就会造成空间的浪费，以及顺序表的空间是连续的我们要释放就必须全部释放。

那我们今天讲到链表就不会出现上面的问题，但也不是说链表就没有缺点，不论是顺序表还是链表都有优缺点，重点在于我们怎么运用。

链表

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

中的指针链接次序实现的。

我们这节主要讲解单链表

这个就是链表的逻辑结构了，一个节点中有指向下一个节点的指针，这样走下去最后一个节点中放的是空指针NULL，像链条一样一环扣一环。

我给大家画一个物理结构方便大家理解

我们可以形象看出链表的基本结构

那我们来创建一个链表

我们先来实现一个打印链表内容的函数

单链表打印

//链表输出
 void LBexport(LBbiao* att) {
	 assert(att);
	 LBbiao* ps = att;
	 while (ps!= NULL) {
		 printf("%d->", ps->SZ);
		 ps = ps->next;
	 }
	 printf("NULL\n");
 }

这里大家可以画图一步一步的理一下理解会更加深刻主要注意循环的判断条件。

我们下面来实现一个插入函数

单链表头插数据

我们想一想在链表的头部插入数据我们只需要开辟一个链表空间mon然后另它的next指向当前链表的表头的地址，并将mon的地址交给表头的指针是不是就可以插入数据并且将链表连接起来了？

大家可以看看大致原理如图

我们还要注意要进行断言防止出现错误

//链表头插数据
 void LBcutin(LBbiao** att,CMMlet n) {
	 assert(att);
	 LBbiao* pt = LBopen();
	 if (*att == NULL) {
		 *att = pt;
	 }
	 else {
		 pt->next = *att;
		 *att = pt;
	 }
	 pt->SZ = n;
 }

这里开辟一个新的链表空间我们还会用到所有我们用一个函数来实现

//开辟链表
 LBbiao* LBopen() {
	 LBbiao* mon = (LBbiao*)malloc(sizeof(CMMlet) + sizeof(LBbiao*));
	 if (mon == NULL) {
		 printf("开辟失败：%s",strerror(errno));
		 return NULL;
	 }
	 mon->next = NULL;
	 mon->SZ = 0;
	 return mon;
 }

我们这里可以用老方法，分装一个函数来验证

单链表头删数据

还是我们用图来演示

//链表头删数据
 void LBdelete(LBbiao**att) {
	 assert(*att != NULL);
	 assert(att != NULL);//断言
	 LBbiao* ps = *att;
	 *att = ps->next;
	 ps->next = NULL;
	 free(ps);
 }

我们验证试试

单链表尾删数据

我们还是画图演示原理

我们可以看见尾删数据直接将倒数第二个节点的next为空就行了,当然我们还要断言一些情况

并且我们还要分情况当链表只有一个节点时该怎么删。

//链表尾删数据
 void LBweishan(LBbiao*att) {
	 assert(att != NULL);//断言
	 LBbiao* ps = att;
	 while (ps->next->next != NULL) {
		 ps = ps->next;
	 }
	 free(ps->next);
	 ps->next = NULL;
 }

单链表尾插数据

老规矩画图理解

我们通过图可以看出尾插数据要开辟一个新的节点然后让原链表的最后一个节点的next指向新开辟出来的节点并将新开辟的节点的next为空。同样我们要分情况讨论

//链表尾插数据
 void LBweicha(LBbiao** att,CMMlet n) {
	 LBbiao* ps = *att;
	 LBbiao* pt = LBopen();
	 if (ps == NULL) {
		 *att = pt;
	 }
	 else {
		 while (ps->next != NULL) {
			 ps = ps->next;
		 }
		 ps->next = pt;
	 }
	 pt->SZ = n;
 }

单链表查找

我们可以直接遍历链表如果遇到我们就返回该数据的节点地址，如果没找到我们返回NULL。

//链表查找
 LBbiao* LBchazhao(LBbiao* att, CMMlet n) {
	 assert(att);
	 LBbiao* ps = att;
	 while (ps != NULL) {
		 if (ps->SZ == n) {
			 return ps;
			 break;
		 }
		 ps = ps->next;
	 }
	 return NULL;
 }

我们可以测试一下

单链表在pos位置之后插入x

与头插类似我们主要注意的是要不要分情况讨论，以及断言的内容，具体插入的过程我们大家可以自己画图试试

接下来我们来实现一下这个函数

//链表在pos位置后插入x

 void LBporcr(LBbiao* pos, CMMlet x) {
	 assert(pos);
	 LBbiao* ps = pos;
	 LBbiao* pt = LBopen();
	 if (pos->next == NULL) {//相当于尾插数据
		 LBweicha(&pos, x);
	 }
	 else {
		//一般情况
		 pt->next=ps->next;
		 ps->next = pt;
		 pt->SZ = x;
	 }

 }

验证试试

单链表删除pos位置之后的值

我们还是用图说话

分析后我们发现我们只需要将pos位置的next指向pos->next->next就ok了，最后还要注意一下特殊情况以及断言

//链表在pos位置后删除x
 void LBpossc(LBbiao* pos) {
	 assert(pos&&pos->next!=NULL);
	 if (pos->next->next == NULL) {//相当于尾删
		 free(pos->next);
		 pos->next = NULL;
	 }
	 else {
		 LBbiao* ps = pos->next;
		 pos->next = pos->next->next;
		 ps->next = NULL;
		 free(ps->next);

	 }
 }

我们可以测试一下

我们的单链表就讲解完了是不是畅快淋漓呢？

这是我们本节的所有代码大家可以自己试试

# define _CRT_SECURE_NO_WARNINGS 1
# include<stdio.h>
# include<assert.h>
# include<string.h>
# include<errno.h>
# include<stdlib.h>



//类型重命名
//方便后期修改
typedef struct LBbiao LBbiao;
typedef int CMMlet;
//链表创建
 struct LBbiao{
	CMMlet SZ;//链表存储的数据
	struct LBbiao* next;//指向下一个节点

 };


 //开辟链表
 LBbiao* LBopen() {
	 LBbiao* mon = (LBbiao*)malloc(sizeof(CMMlet) + sizeof(LBbiao*));
	 if (mon == NULL) {
		 printf("开辟失败：%s",strerror(errno));
		 return NULL;
	 }
	 mon->next = NULL;
	 mon->SZ = 0;
	 return mon;
 }

 //链表输出
 void LBexport(LBbiao* att) {
	 assert(att);
	 LBbiao* ps = att;
	 while (ps!= NULL) {
		 printf("%d->", ps->SZ);
		 ps = ps->next;
	 }
	 printf("NULL\n");
 }

 //链表头插数据
 void LBcutin(LBbiao** att,CMMlet n) {
	 assert(att);
	 LBbiao* pt = LBopen();
	 if (*att == NULL) {
		 *att = pt;
	 }
	 else {
		 pt->next = *att;
		 *att = pt;
	 }
	 pt->SZ = n;
 }

 //链表头删数据
 void LBdelete(LBbiao**att) {
	 assert(*att != NULL);
	 assert(att != NULL);//断言
	 LBbiao* ps = *att;
	 *att = ps->next;
	 ps->next = NULL;
	 free(ps);
 }

 //链表尾删数据
 void LBweishan(LBbiao**att) {
	 assert(att != NULL);//断言
	 assert(*att != NULL);

	 LBbiao* ps = *att;
	 if (ps->next == NULL) {
		 *att = NULL;
		 free(ps);
	 }
	 else {
		 while (ps->next->next != NULL) {
			 ps = ps->next;
		 }
		 free(ps->next);
		 ps->next = NULL;
	 }
 }

 //链表尾插数据
 void LBweicha(LBbiao** att,CMMlet n) {
	 LBbiao* ps = *att;
	 LBbiao* pt = LBopen();
	 if (ps == NULL) {
		 *att = pt;
	 }
	 else {
		 while (ps->next != NULL) {
			 ps = ps->next;
		 }
		 ps->next = pt;
	 }
	 pt->SZ = n;
 }
 //链表查找
 LBbiao* LBchazhao(LBbiao* att, CMMlet n) {
	 assert(att);
	 LBbiao* ps = att;
	 while (ps != NULL) {
		 if (ps->SZ == n) {
			 return ps;
			 break;
		 }
		 ps = ps->next;
	 }
	 return NULL;
 }




 //链表在pos位置后插入x

 void LBporcr(LBbiao* pos, CMMlet x) {
	 assert(pos);
	 LBbiao* ps = pos;
	 LBbiao* pt = LBopen();
	 if (pos->next == NULL) {//相当于尾插数据
		 LBweicha(&pos, x);
	 }
	 else {
		//一般情况
		 pt->next=ps->next;
		 ps->next = pt;
		 pt->SZ = x;
	 }

 }


 //链表在pos位置后删除x
 void LBpossc(LBbiao* pos) {
	 assert(pos&&pos->next!=NULL);
	 if (pos->next->next == NULL) {//相当于尾删
		 free(pos->next);
		 pos->next = NULL;
	 }
	 else {
		 LBbiao* ps = pos->next;
		 pos->next = pos->next->next;
		 ps->next = NULL;
		 free(ps->next);

	 }
 }



 //测试链表1
 void ceshi1() {
	 LBbiao* arr = NULL;
	 LBweicha(&arr, 1);
	 LBweicha(&arr, 2);
	 LBweicha(&arr, 3);
	 LBweicha(&arr, 4);
	 LBexport(arr);
	 LBporcr(arr, 0);
	 LBexport(arr);
	 LBpossc(arr);
	 LBexport(arr);


 }

 int main() {
	 ceshi1();


	 return 0;
 }

以上就是全部内容了，如果有错误或者不足的地方欢迎大家给予建议。