带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

03-01 1016阅读

带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

前言:

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨

🐻推荐专栏: 🍔🍟🌯 C语言进阶

🔑个人信条: 🌵知行合一

🍉本篇简介:>:讲解数据结构中链表的知识,;链表的分类,c语言实现单链表常见接口等.

金句分享:

✨山不向我走来,我便向山走去.✨

目录

  • 前言:
  • 一、链表介绍
    • 1.1 链表结构图:
    • 1.2 链表分类(图解分析)
    • 二、单链表实现:
      • 2.1 链表的"结点"声明:
      • 2.2 "插入"元素操作.
        • 单链表的"尾插":
        • 单链表的"头插"
        • 指定位置之后"插入"新节点
        • "申请新节点"函数
        • 2.3 "删除"元素操作.
          • 单链表的"尾删"
          • 单链表的"头删":
          • 单链表的"删除"指定的目标结点
          • 2.4 "查找"目标结点函数
          • 2.5 单链表的"打印"
          • 2.6 单链表的"销毁"
          • 总结:"链表"与"顺序表"的区别
          • 三、总代码
            • 测试区(test.c)
            • 接口实现区(SList.c)
            • 函数声明区(SList.h)

              一、链表介绍

              顺序表缺点：

              1. 中间/头部的插入删除，时间复杂度为O(N),因为需要移动数据.
              2. 增容需要申请新空间，特别是异地扩容,拷贝数据，释放旧空间。消耗不小。
              3. 增容不是一次增容到位,而是每次增容后判断是否符合要求，并且增容一般是2倍增容,一次次扩容消耗太大.
              4. 除此之外,还可能有一定的空间浪费。

                例如:当前容量为200，如果有201个待插入数据,势必要增容到400(原来容量的两倍),这样就浪费了199个空间.

              我们不妨来看一下链表的存储结构.

              链表的概念:

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

              🌰栗子

              单链表的结点声明:

              typedef int DateType;
typedef struct SListN0de
{
	DateType Date;//数据域
	struct SListN0de* next;//指针域
}SLTNode;

              结点:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              1.1 链表结构图:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              通过上图我们不难知道:

              1. 链表在逻辑上是连续的(next指针,指向下一个结点,链接在一起),而物理上可能连续,也可能不连续.
              2. 链表是由一个个结点链接在一起组成的,每个结点其实是malloc在堆区上申请的,所以地址可能连续,也可能不连续.

              1.2 链表分类(图解分析)

              共有八种链表,我们主要学习不带头单向链表与带头双向链表,学会这两种,其它的大同小异,写起来并不苦难.

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              单向、双向:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              不带头、带头:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              带头与不带头的区别在于:

              带头:链表是通过一个特殊的结点—头结点指向链表的第一个有效结点.

              不带头:通过结点指针指向链表的第一个有效结点.

              头结点作用:传送门

              不须换、循环:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              重点掌握:

              1. 无头单向非循环链表(本篇重点)：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多,因为单链表不能回头,可以考察的地方很多.
              2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这种结构的链表虽然结构复杂,但是优势也很明显,并且实现起来反而很简单.后续跟着学到了就可以理解了.

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              二、单链表实现:

              2.1 链表的"结点"声明:

              typedef int DateType;
typedef struct SListN0de
{
	DateType Date;//数据域
	struct SListN0de* next;//指针域
}SLTNode;

              单链表初始化:

              单链表是不需要初始化操作的,只需要创建一个结点指针就行.初始状态:指针指向NULL.

              头指针:

              SLTNode* plist=NULL;

              2.2 "插入"元素操作.

              我们需要插入数据时,只需要申请一个结点,将数据放入结点,然后将结点链接起来就行.

              单链表的"尾插":

              单链表的尾插步骤:

              1. 找尾:

                由于单链表的结点之间不一定是连续存储的,不支持向顺序表那样的随机访问,需要通过遍历才能找到目标结点.

              2. 将最后一个结点的next指向新节点.

              图解:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              那如果链表本身就是空链表呢?

              此时需要修改头指针,将头指针指向这个新节点.

              注意:

              1. 需要传二级指针:

                这点很重要,因为需要修改头指针,而头指针的类型是:SLTNode*,相信友友们学到这里应该知道,如果想要在函数中形参的改变影响实参,则需要传址调用,通过地址来影响实参.

                那么,指针的地址是?二级指针相信友友们应该没有忘记.😂😂😂

              2. 断言,这里需要灵活断言.

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              "尾插"函数声明:

              void PushBack(SLTNode** pphead, DateType x)

              pphead需要断言:

              pphead是指向 *pphead(一级指针/头指针)的指针,即值存储的是头指针的地址,只要头指针存在,则不为空.而头指针一定存在.

              *phead不能断言:

              *phead是头指针,头指针在链表为空时,头指针的值是NULL,所以不能断言.

              链表中有数据时,指向第一个结点,值是第一个结点的地址.

              1. 头指针是很重要的一个指针,我们都是通过头指针找到链表的,所以,除了头插需要修改头指针以外,其他插入都不能修改头指针,所以我们需要创建一个临时指针:SLTNode*tail = *pphead代替头指针找尾.

              代码:

              void PushBack(SLTNode** pphead, DateType x)
{
	assert(pphead);//如果头指针的地址为NULL,则报错.
	SLTNode*tail = *pphead;//创建一个指针代替头指针遍历
	SLTNode* newnode = BuyNode(x);
	//*pphead代表代表头指针,phead表示头指针的地址
	//如果*pphead指向NULL,说明为空链表
	if (*pphead == NULL)
	{
		//这里可以使用tail代替*phead吗?
		//不能,因为这里要改变的是,头结点的指针,需要用二级指针(解引用)来改变
		*pphead = newnode;//空链表是将头指针指向新节点
	}
	else
	{
		//找尾巴,画图解析
		//这里可以使用tail,是因为,要改变的是结构体的内容,只需要用结构体指针(解引用)就行
		while ( tail->next != NULL)//如果该节点的下一个节点是空指针则停止循环
		{
			tail = tail->next;
		}
		tail->next = newnode;//让尾节点的next指向新节点.
	}
}

              单链表的"头插"

              尾插是不是显得有些麻烦?那我们试着看一下头插.

              头插步骤:

              1. 创建一个新节点.
              2. 将新节点指向头指针指向的结点.
              3. 更新头指针(头指针指向新节点)

              图解:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              代码实现:

              //写法1
void PushFront(SLTNode** pphead, DateType x)
{
	assert(pphead);
	SLTNode* newnode = BuyNode(x);
	//下面两句的顺序不能变
	newnode->next = *pphead;
	*pphead = newnode;
}

              写法2:

              //写法2
void PushFront(SLTNode** pphead, DateType x)
{
	assert(pphead);
	SLTNode* newnode = BuyNode(x);
	SLTNode* phead = *pphead;//创建一个临时指针,保存一下头指针指向的头结点.
	//顺序随便改
	*pphead = newnode;
	newnode->next = phead;
}

              两种方法都比较好理解,也很简单,单链表的头插效率很高,不需要遍历,

              指定位置之后"插入"新节点

              该函数很简单,只需要通过查找目标结点函数找到目标结点的位置,然后将将新节点链接上去就行了.

              步骤:

              1. 将新节点的指针域(next)指向指定结点的下一个结点.
              2. 将指定位置的结点的指针域(next)指向新节点,

              图解:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              //使用此函数之前可以先使用,查找目标结点函数(SListFind),找到位置先
void SLTInsertBack( SLTNode* pos, DateType x)
{
	assert(pos);
	SLTNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

              "申请新节点"函数

              新节点都是使用malloc函数动态申请的.函数实现很简单,相信聪明的友友们可以理解,牛牛就不过介绍了.

              SLTNode* BuyNode(DateType x)//创建新结点
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);//防止申请结点失败
	newnode->Date = x;
	newnode->next = NULL;
	return newnode;
}

              2.3 "删除"元素操作.

              因为链表的结点都是动态申请的,所以链表的删除操作需要将目标结点释放,同时为了保护原有的链表结构,需要将受目标结点的其他结点也灵活修改.

              单链表的"尾删"

              "删除结点"步骤:

              1. 处理特殊情况,如果头指针指向NULL,空链表不能执行删除操作.
              2. 找倒数第二个结点,方法:tail->next->next != NULL因为最后一个结点的next=NULL;

                数据结构记得多画图哦,有助于我们理解.

              3. 先释放尾结点(tail->next),再将倒数第二个结点的next置空NULL
              4. 处理特殊情况:如果链表就只有一个结点,就不存在倒数第二个结点,此时直接释放头结点,并将头结点置空.

              图解:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              //尾删
void PopBack(SLTNode** pphead)
{
	assert(pphead);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pphead);//防止空链表的删除操作
	SLTNode* tail = *pphead;//创建一个指针代替头指针遍历
	if (tail->next == NULL) {
		free(tail);
		tail= NULL;
	}
	else {
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

              单链表的"头删":

              同样,单链表的"头删"也是很简单的操作.

              步骤:

              1. 将头结点记录一下.
              2. 将头指针指向第二个结点.
              3. 释放头结点.
              void PopFront(SLTNode** pphead)
{
	assert(pphead);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pphead);//防止空链表的删除操作
	SLTNode* head = *pphead;
	*pphead = ( * pphead)->next;
	free(head);
}

              思考:

              需不需要单独去考虑,如果链表只有一个结点的特殊情况?

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              答案:

              不需要,因为如果链表只有一个结点,头删将头指针指向第二个结点,刚好是指向NULL,也是符合要求的.

              单链表的"删除"指定的目标结点

              步骤:

              1. 通过查找目标结点函数SListFind(下面牛牛讲了),找到目标结点的地址.
              2. 将目标结点的前驱结点指向目标结点的后继结点.
              3. 释放目标结点.
              4. 特殊情况:如果是头删,需要修改头结点,让其指向第二个结点.

              图解:

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              代码实现:

              //告诉位置(建议配合SListFind函数一起使用),删除第一个出现该值的节点
void SlitErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pphead);//防止空链表的删除操作
	assert(pos);
	SLTNode* cur = *pphead;//创建一个指针代替头指针遍历
	if (cur == pos) {//如果目标结点是头结点这种特殊情况
		SLTNode* next = cur->next;
		free(cur);
		*pphead = next;
	}
	else {
		while (cur->next != pos && cur->next != NULL)//遍历寻找目标结点
		{
			cur = cur->next;
		}
		cur->next = pos->next;//将目标结点的前驱指向目标结点的后继
		free(pos);
	}
}

              2.4 "查找"目标结点函数

              单链表查找目标结点只需要遍历一遍这个链表即可,如果目标结点有多个,则只返回第一个遇到的目标结点,找不到目标结点则返回NULL.

              函数很简单,牛牛不过多介绍了.

              SLTNode* SListFind(SLTNode* phead, DateType x)
{
	SLTNode* cur = phead;//代替头指针遍历链表
	while (cur)
	{
		if (cur->Date == x)
		{
			return cur;
		}
		cur = cur ->next;
	}
	return NULL;
}

              2.5 单链表的"打印"

              单链表的打印很简单,遍历打印就行了.

              void Print(SLTNode* phead)//链表的打印
{
	//assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->Date);
		cur = cur->next;
	}
	printf("NULL\n\n");
}

              2.6 单链表的"销毁"

              步骤:

              1. 创建next指针保存要删除节点的下一个结点.
              2. 将要删除的结点释放.
              3. 将要删除的结点更新到next
              4. 继续执行1
              //单链表的销毁
void SLTDestroy(SLTNode* phead)//这个函数不会将头指针置空,要使用该函数的人自己置空
{
	SLTNode* del = phead;
	SLTNode* next = phead;//用于记录下一个结点
	while (next)
	{
		next = next->next;
		free(del);
		del = next;
	}
	//保持习惯置空
	next == NULL;
	del = NULL;
}

              总结:"链表"与"顺序表"的区别

              顺序表链表区别
              物理上必定是连续的逻辑上连续,但是物理上不一定连续物理存储空间
              访问其中的某个结点支持随机访问( O(1) )不支持随机访问访问元素
              大多数情况下需要移动数据,效率低( O(N) )只需要改变目标指针的指向,但是需要找到该结点删除和插入新节点(任意位置)
              容量不够时,动态顺序表需要动态扩容,效率不高没有容量的概念不需要扩容,资源利用率高插入数据时
              元素的存储很高效+频繁访问频繁的对任意位置的插入和删除使用场景
              由于无物理上连续存在,利用率高利用率低缓存利用率

              希望这篇文章对大家有帮助。欢迎小伙伴们私信提意见和提问哦！

              最后，小伙伴们的点赞就是给牛牛最大的支持，能不能给牛牛来一个一键三连呢？谢谢支持。

              带你玩转数据结构-单链表(适合初学者的文章,讲解的很仔细哦)

              三、总代码

              测试区(test.c)

              //test.c 主函数区域,用于测试接口
#include "SList.h"
void test1()
{
	SLTNode* plist=NULL;
	printf("插入0,1,2,3,4,5,6,7,8,9之后:\n");
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	PushBack(&plist, 6);
	PushBack(&plist, 7);
	PushBack(&plist, 8);
	PushBack(&plist, 9);
	//头插
	PushFront(&plist, 0);
	Print(plist);
	printf("尾删一次后:\n");
	PopBack(&plist);
	Print(plist);
	printf("头删一次后:\n");
	PopFront(&plist);
	Print(plist);
	printf("删除第一次出现元素7的结点后:\n");
	SlitErase(&plist, SListFind(plist, 7));
	Print(plist);
	printf("在第一个出现5值的结点后面插入一个值为666的结点\n");
	SLTInsertBack(SListFind(plist, 5), 666);
	Print(plist);
	SLTDestroy(plist);
	plist == NULL;
}
int main()
{
	test1();
	return 0;
}

              接口实现区(SList.c)

              #include "SList.h"
SLTNode* BuyNode(DateType x)//创建新结点
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->Date = x;
	newnode->next = NULL;
	return newnode;
}
void PushBack(SLTNode** pphead, DateType x)
{
	assert(pphead);
	SLTNode*tail = *pphead;//创建一个指针代替头指针遍历
	SLTNode* newnode = BuyNode(x);
	//cur代表代表头指针,phead表示头指针的地址
	//如果cur指向NULL,说明为空链表
	if (*pphead == NULL)
	{
		//这里可以使用tail代替*phead吗?
		//不能,因为这里要改变的是,头结点的指针,需要用二级指针(解引用)来改变
		*pphead = newnode;//空链表是将头指针指向新节点
	}
	else
	{
		//找尾巴,画图解析
		//这里可以使用tail,是因为,要改变的是结构体的内容,只需要用结构体指针(解引用)就行
		while ( tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
//头插(错误示例)
//void PushFront(SLTNode** pphead, DateType x)
//{
//	assert(pphead);
//	SLTNode* phead = *pphead;
//	SLTNode* newnode = BuyNode(x);
//	//下面两句的顺序不能变,除非再创一个结点保phead
//	newnode->next = phead;
//	phead= newnode;
//}
// 
正确写法1
//void PushFront(SLTNode** pphead, DateType x)
//{
//	assert(pphead);
//	SLTNode* newnode = BuyNode(x);
//	//下面两句的顺序不能变,除非再创一个结点保phead
//	newnode->next = *pphead;
//	*pphead = newnode;
//}
//写法2
void PushFront(SLTNode** pphead, DateType x)
{
	assert(pphead);
	SLTNode* newnode = BuyNode(x);
	SLTNode* phead = *pphead;
	//顺序随便改
	*pphead = newnode;
	newnode->next = phead;
}
//尾删
void PopBack(SLTNode** pphead)
{
	assert(pphead);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pphead);//防止空链表的删除操作
	SLTNode* tail = *pphead;//创建一个指针代替头指针遍历
	if (tail->next == NULL) {
		free(tail);
		tail= NULL;
	}
	else {
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
void PopFront(SLTNode** pphead)
{
	assert(pphead);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pphead);//防止空链表的删除操作
	SLTNode* head = *pphead;
	*pphead = ( * pphead)->next;
	free(head);
}
SLTNode* SListFind(SLTNode* phead, DateType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->Date == x)
		{
			return cur;
		}
		cur = cur ->next;
	}
	printf("找不到:\n");
	return NULL;
}
void SlitErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pphead);//防止空链表的删除操作
	assert(pos);
	SLTNode* cur = *pphead;//创建一个指针代替头指针遍历
	if (cur == pos) {//如果目标结点时头结点
		SLTNode* next = cur->next;
		free(cur);
		*pphead = next;
	}
	else {
		while (cur->next != pos && cur->next != NULL)//遍历寻找目标结点
		{
			cur = cur->next;
		}
		cur->next = pos->next;//将目标结点的前驱指向目标结点的后继
		free(pos);
	}
}
void SLTInsertBack( SLTNode* pos, DateType x)
{
	assert(pos);
	SLTNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void Print(SLTNode* phead)//链表的打印
{
	//assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->Date);
		cur = cur->next;
	}
	printf("NULL\n\n");
}
void SLTDestroy(SLTNode* phead)//这个函数不会将头指针置空,要使用该函数的人自己置空
{
	SLTNode* del = phead;
	SLTNode* next = phead;//用于记录下一个结点
	while (next)
	{
		next = next->next;
		free(del);
		del = next;
	}
	//保持习惯置空
	next == NULL;
	del = NULL;
}

              函数声明区(SList.h)

              #pragma once
#include 
#include 
#include 
typedef int DateType;
typedef struct SListN0de
{
	DateType Date;
	struct SListN0de* next;
}SLTNode;
//尾插
void PushBack(SLTNode** pphead, DateType x);
//尾删
void PopBack(SLTNode** pphead);
//头插
void PushFront(SLTNode** pphead, DateType x);
//头删
void PopFront(SLTNode** pphead);
//告诉值,返回结点的地址
SLTNode* SListFind(SLTNode* phead, DateType x);
//告诉位置(建议配合SListFind函数一起使用),删除第一个出现该值的节点
void SlitErase(SLTNode** pphead, SLTNode* pos);
//告诉位置,在位置后面插入
void SLTInsertBack( SLTNode* pos, DateType x);
struct SListN0de* BuyNode(DateType x);//创建新节点
void Print(SLTNode* phead);//链表的打印
// 单链表的销毁
void SLTDestroy(SLTNode* phead);
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]