首页 > 其他分享 >【数据结构初阶】一篇文章带你超深度理解【单链表】

【数据结构初阶】一篇文章带你超深度理解【单链表】

时间：2024-07-24 20:57:34浏览次数：11  
标签：pphead 结点 单链 SLTNode SLTPrint next 初阶 数据结构 plist

 hi ！

目录

前言：

1、链表的概念和结构

2、单链表（Single List，简写SList）的实现

2.1   定义链表（结点）的结构

2.2  创建一个链表

2.3  打印链表

2.4  尾插

2.5  头插

2.6  尾删

2.7  头删

2.8  查找

2.9  在指定位置之前插入数据

2.10  在指定位置之后插入数据

2.11  删除pos结点

2.12  删除pos之后的结点

2.13  销毁链表

————————————————  《 你的名字 》  ————————————————

正文开始——

前言：

前面我们学习了顺序表，实现了对数组内容增删查改等操作，但是顺序表仍然存在一些缺陷。

  1. 中间/头部的插入删除，时间复杂度为O(N)；
  2. 增容需要申请新空间，拷贝数据，释放旧空间，这是不小的消耗；
  3. 增容一般是成2倍的增长，大概率会有一些空间的浪费。

那我们该如何解决上面的问题呢？下面我们来学习一下链表 。

1、链表的概念和结构

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

2、单链表（Single List，简写SList）的实现

上面我们了解了链表的概念和结构，链表又分为很多种，今天我们先学习链表之一单链表。

2.1   定义链表（结点）的结构

//定义链表（结点）的结构

typedef int SLTDataType;
typedef struct SListNode {
	SLTDataType data;  
	struct SListNode* next;
}SLTNode;

2.2  创建一个链表

这里申请空间使用 malloc，在链表里面不存在增容的操作，想插入数据直接申请一个新的结点即可！用 calloc 也可以，calloc会让申请空间的内容初始化为0。

【代码】

test.c

//创建一个链表
void creatSList()
{
	//链表是由一个一个的结点组成的

	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;

	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将结点之间连接起来
	node1->next=node2;
	node2->next=node3;
	node3->next=node4;
	node4->next = NULL;

}

2.3  打印链表

【思路图解】

【代码】 

//链表的打印

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

2.4  尾插

【思路图解】

【代码】 

SList.c

//申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		perror("malloc file!");
		exit(1);
	}
	node->data = x;
	node->next = NULL;

	return node;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请一个新结点
	SLTNode* newnode = SLTBuyNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* pcur = *pphead;

		//找尾结点
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
	}
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
    //plist为指向第一个结点的指针
	SLTPushBack(&plist,100);
	SLTPrint(plist);
}

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

【验证】 

【注意】

  1. 在 test.c 里面尾插时传的是&plist ，而不是 plist。我们希望形参的改变影响实参，所以我们取实参的地址。plist 作为参数传的是一个指针变量而不是一个地址，只有 &plist （有&）才算是真正的取地址使得形参的改变影响实参。用二级指针来接收。
  2. 找尾结点。循环的条件是 pcur->next，而不是 pcur。因为 pcur->next 为NULL跳出循环时，说明 pcur 为尾结点，当 pcur 为空跳出循环时，说明 pcur 是尾结点的下一个节点，而不是尾结点。
  3. pphead==&plist；*pphead==plist（指向第一个结点的指针） 。
  4. assert (pphead)；传过来的地址不能为空。

2.5  头插

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	//申请一个新结点
	SLTNode* newnode = SLTBuyNode(x);

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

test.c


void SListTest01()
{
    //验证尾插
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPushBack(&plist,100);
	SLTPrint(plist);
    
    //验证头插
	SLTPushFront(&plist, 200);
	SLTPrint(plist);
}

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

【验证】

2.6  尾删

各结点的地址应为0x0012FF...，在此纠正下面的错误。谅解哈~~~

【思路图解】

当链表内不止一个结点时

当链表内只有一个结点时 

【代码】

SList.c


//尾删
void SLTPopBack(SLTNode** pphead)
{
	//链表为空，不可删除
	assert(pphead && *pphead);

	//处理只有一个结点的情况，要删除的就是头结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找 ptail 和 prev
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}

test.c


void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPushBack(&plist,100);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	SLTPopBack(&plist);
	SLTPrint(plist);
}

int main()
{
	/*createSList();*/
	SListTest01();
	return 0;
}

【验证】

2.7  头删

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//头删
void SLTPopFront(SLTNode** pphead)
{
	//链表不为空
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPushBack(&plist,100);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	SLTPopFront(&plist);
	SLTPrint(plist);

}

int main()
{
	/*createSList();*/
	SListTest01();
	return 0;
}

【验证】

2.8  查找

各结点的地址应为0x0012FF...，在此纠正下面的错误。

思路简单，直接上代码：

SList.c

//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

【注意】SLTNode* pcur = phead，重新定义一个指针变量 pcur 指向第一个结点，让 pcur 来遍历链表，防止头结点丢失。

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPushBack(&plist,100);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTNode* find = SLTFind(plist, 2);
	if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	}
}

【验证】

2.9  在指定位置之前插入数据

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c


//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//申请一个新的结点
		SLTNode* newnode = SLTBuyNode(x);

		//找pos的前一个结点prev
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 2);
	/*///*if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	//}*/

	SLTNode* find = SLTFind(plist, 2);
	SLTInsert(&plist, find, 100);
	SLTPrint(plist);

}

【验证】

2.10  在指定位置之后插入数据

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 2);
	/*///*if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	//}*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsert(&plist, find, 100);
	SLTPrint(plist);*/

	SLTNode* find = SLTFind(plist, 2);
	SLTInsertAfter(find, 100);
	SLTPrint(plist); 

}

【验证】

2.11  删除pos结点

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//删除pos结点
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
	assert(pphead && *pphead);
    //这里对pos进行限制，链表中必须有pos这个结点，在查找中若没有pos结点则返回NULL
	assert(pos);

	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//找到prev：pos的前结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 2);
	/*///*if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	//}*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsert(&plist, find, 100);
	SLTPrint(plist);*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsertAfter(find, 100);
	SLTPrint(plist); */

	SLTNode* find = SLTFind(plist, 2);
	SLTErase(&plist, find);//这里的find由pos接收，SLTFind若没找到存储2这个结点则返回NULL
	SLTPrint(plist); 

}

【验证】

2.12  删除pos之后的结点

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

test.c

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist,1);
	SLTPushBack(&plist,2);
	SLTPushBack(&plist,3);
	SLTPushBack(&plist,4);
	SLTPrint(plist);

	/*SLTPushFront(&plist, 200);
	SLTPrint(plist);*/

	/*SLTPopBack(&plist);*/
	/*SLTPrint(plist);*/

	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 2);
	/*///*if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	//}*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsert(&plist, find, 100);
	SLTPrint(plist);*/

	/*SLTNode* find = SLTFind(plist, 2);
	SLTInsertAfter(find, 100);
	SLTPrint(plist); */

	//SLTNode* find = SLTFind(plist, 2);
	//SLTErase(&plist, find);
	//SLTPrint(plist); 

	SLTNode* find = SLTFind(plist, 2);
	SLTEraseAfter(find);
	SLTPrint(plist); 

}

【验证】

2.13  销毁链表

各结点的地址应为0x0012FF...，在此纠正下面的错误。

【思路图解】

【代码】

SList.c

//销毁链表
void SListDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
    //*pphead=plist，链表为空，也要把*pphead置为空
	*pphead = NULL;
}

【验证】

今天单链表的深度学习就结束啦，拜拜~~~

完——

————————————————  《 你的名字 》  ————————————————

 重要的人，不能忘记的人，不想忘记的人，你，是谁？

 不管在哪里，不管过多久，不管是要跨过高山，还是跨过湖海，我一定会去见你一面。

スパークル_RADWIMPS_高音质在线试听_スパークル歌词|歌曲下载_酷狗音乐酷狗音乐为您提供由RADWIMPS演唱的高清音质无损スパークルmp3在线听,听スパークル,只来酷狗音乐!icon-default.png?t=N7T8https://t4.kugou.com/song.html?id=avhoFadCPV2

至此结束——

再见——

标签：pphead,结点,单链,SLTNode,SLTPrint,next,初阶,数据结构,plist
From： https://blog.csdn.net/lrq13965748542/article/details/140621731

相关文章

  • 【数据结构】树和二叉树
    目录1.前言2.树2.1树的概念2.2树中的重要概念2.3树的表示形式 2.4树的应用3.二叉树3.1概念3.2两种特殊的二叉树3.3二叉树的性质3.4二叉树的存储3.5二叉树的遍历方式3.5.1创建二叉树3.5.2二叉树的遍历3.6二叉树的基本操作4.总结1.前言二叉树是数据结构中......
  • 数据结构与算法，剑指Offer 50题
    队列队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。对列的添加insertappend队列的取值列表[-1]列表[0]队列的删......
  • 最全数据结构个人笔记【单向链表】
    1.链表基本概念链式存储的线性表，简称链表链表其实是由一个或者多个结构体通过指针指向的关系构成我们把每个结构体的变量称为节点,节点里面由两个成员组成一个是数据域，另外一个是指针域，指针域是用于存放下一个节点的地址以此类推，我们把这种存储方式称为链式存储2.链......
  • PART1-Oracle关系数据结构-索引和索引组织表
    3.索引组织表3.1.索引概述索引是与表或表簇关联的可选结构，有时可以加快数据访问速度。通过在表的一个或多个列上创建索引，在某些情况下，您可以从表中检索一小部分随机分布的行。索引是减少磁盘I/O的众多方法之一。如果堆组织表没有索引，那么数据库必须执行全表扫描才能找到一个......
  • 数据结构（Java）：Map集合&Set集合&哈希表
    目录1、介绍1.1 Map和Set1.2模型2、Map集合2.1Map集合说明2.2 Map.Entry<K，V>2.3Map常用方法2.4Map注意事项及实现类 3、Set集合3.1Set集合说明 3.2 Set常用方法 3.3Set注意事项及其实现类4、TreeMap&TreeSet4.1集合类TreeMap（Key-Value模型）4.1.1底......
  • 【数据结构】：用Java实现链表
    在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。概念顺序表是物理上连续，逻辑上也是连续的链表......
  • 【数据结构】队列详解和模拟实现
    大家好，今天我们学习队列，本篇博客主要涉及一般队列，环形队列和双端队列，每个队列应用场景均有所差异，下面我们一起来看看吧。队列(Queue)一，概念队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性入队列：进行插入操作的一端称为队尾（Ta......
  • 数据结构实验二——单链表的基本操作（2021级zzu）
    ps:滴~打卡第二天，好困啊~~~~~~数据结构实验二——单链表的基本操作一、实验目的二、实验内容（选其中之一写实验报告）三、问题描述四、数据结构定义五、算法思想及算法设计5.1实验内容（1）5.1.1理论实现和代码实现5.2实验内容（2）5.2.1代码实现六、运行示例七、实验代......
  • [杂项] [算法] [数据结构] 暑期专题狂补
    或曰，有学长两天授吾以十专题，吾顿感日月之紧迫，以专题竟不能以吾之所有，遂成此文，以记之语文确实没学好本文可能涵盖多个知识点，故每个的讲解比较简略，仅供参考一.2-SAT$2-SAT$用于求解一个变量只有两种情况的适应性问题（就是有没有解以及输出一种方案）；其实可以类比二分图最大......
  • 【数据结构与算法—基础篇1】
    1、基础知识1、数据结构三要素：逻辑结构、存储结构、数据的运算；其中逻辑结构包括线性结构（线性表、栈、队列）和非线性结构（树、图、集合）2、数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。3、数据元素是数据的基本......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99