【数据结构】第三节:单链表

这篇具有很好参考价值的文章主要介绍了【数据结构】第三节:单链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言 

本篇要求掌握的C语言基础知识:指针、结构体

目录

前言 

单链表

概念

对比链表和顺序表

创建链表

实现单链表

准备工作

 打印链表

 创建节点并初始化

尾插

二级指针的调用

尾插代码 

头插

尾删

头删

查找(返回节点) 

 在指定位置(pos)之前插入数据

在指定位置(pos)之后插入数据

删除pos节点

删除pos之后的节点 

销毁链表


单链表

概念

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

对比链表和顺序表

顺序表

        1) 占用一大片连续内存空间

        2) 不需要额外空间存储逻辑关系,总空间需求最少

        4) 可顺序访问,支持随机访问

        5) 在C语言中,通过数组实现

        6) 数据元素的插入和删除操作通过移动元素完成

链表

        1) 不要求占用连续内存空间

        2) 不仅要存储数据,还要存储数据之间的关系,故总空间需求较大

        3) 通过指针反映逻辑关系

        4) 逻辑连续,物理可不连续

        5) 只可顺序访问,不支持随机访问

        6) 存在标记:头指针

        7) 数据元素的插入和删除操作通过修改指针完成:定位插入点/删除点的直接前驱/后

        从上文可以得知与顺序表不同的是,链表⾥的每节"⻋厢"都是独⽴申请下来的空间,我们称之为“结点/节点” ,节点的组成主要有两个部分:当前节点要保存的数据和保存下⼀个节点的地址(指针变量)。

【数据结构】第三节:单链表,数据结构与算法,c语言,数据结构

创建链表

//创建节点
typedef int SLTDataType;

typedef struct SLNode
{
	SLTDataType data;//数据域
	struct SLNode* next;//指针域
}SLTNode;

//创建节点
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;//尾指针置空

        其中数据域用于存放数据,指针域用于存放下一个结点的地址。上面的链表是手动创建节点,只是为了展示链表的形成,后续创建和链接单链表可以通过函数实现。

实现单链表

准备工作

在工程中一共包含三个文件

  • 定义文件SLNode.h:定义函数和结构体,头文件:stdio.h、stdlib.h、assert.h
  • 实现文件SLNode.c:实现函数具体功能,头文件:SLNode.h
  • 测试文件test.c:测试每一部分代码的正确性,头文件:SLNode.h

        在开始之前我们需要定义一个指向为空的结构体类型的节点(SLNode*)plist,作为链表的头节点。

SLNode* plist = NULL;

 打印链表

//打印
void SLTprint(SLTNode* phead)
{
	SLNode* pcur = phead;
	while (pcur != NULL)
	{
		printf("%d ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

 创建节点并初始化

//创建节点并初始化
SLNode* SLTbuyNode(SLTDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));//创建新节点
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);//表示非正常退出
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

尾插

二级指针的调用

        从这一部分开始就涉及到了二级指针传参的问题,在对单链表进行尾插时,如果此时头节点plist指向为空(即该单链表为空),就需要在函数内部改变头指针的指向,指向新插入的节点。

        这里举一个简单的例子,假如我要实现一个交换两个整形数据的函数,应该如何实现?

void Exchange(int a,int b)
{
    int tmp=a;
    a=b;
    tmp=b;
}

        如果仅仅将两个整形作为参数是无法成功的,因为在主函数中调用Exchange时在栈帧中又开辟了一块地址不同于主函数的函数栈帧,以上"传值调用"仅仅将形参里的内容进行交换,在函数执行结束时所占据的空间会被释放,同时形参也会因为被销毁而无法对实参产生影响。

        如果想要"形参影响实参",就要把"传值调用"改为"传址调用",即将变量的地址作为参数传给函数,对应的函数参数应为指针类型。

void Exchange(int* a,int* b)
{
    int* tmp=*a;
    *a=*b;
    *tmp=*b;
}

        这样就实现了交换两个数据的操作。

        同理,想要在函数内部改变一级头指针plist的指向,应该把plist的地址传入,用二级指针接收,也就是"传址调用",如果只传递一级指针(即链表的头指针),无法直接修改它所指向的地址,因为在函数内部对指针的修改不会影响到函数外部,最终只是将形参指针的指向改变而无法对实参造成影响。为了实现对链表头指针的修改,需要传递指向指针的指针,这样在函数内部就可以修改指针所指向的地址,从而改变链表的头指针。

 来一张图解释二级指针

【数据结构】第三节:单链表,数据结构与算法,c语言,数据结构

总结:只要头指针发生改变就需要用到二级指针

尾插代码 

void SLTpushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTbuyNode(x);
	if (*pphead == NULL)//链表为空
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* ptail = *pphead;
		while (ptail->next != NULL)//遍历链表找到尾节点
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

头插

       与尾插同理,头指针的指向发生改变,需要借助二级指针

void SLTpushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTbuyNode(x);
	newnode->next = *pphead;//*pphead是指向第一个节点的指针
	*pphead = newnode;
}

尾删

void SLTpopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//*pphead为空说明整个链表为空
	if ((*pphead)->next == NULL)//链表中只有一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* ptail = *pphead;
		SLTNode* prev = *pphead;
		while (ptail->next != NULL)
		{
			prev = ptail;//prev指向的是尾节点的前一个节点
			ptail = ptail->next;
		}
		free(ptail);
		prev->next = NULL;//prev成为新的尾节点
		ptail = NULL;
	}
}

头删

void SLTpopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead) == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* p = *pphead;//此时p指向的是头节点
		*pphead = (*pphead)->next;
		free(p);
		p = NULL;
	}
}

查找(返回节点) 

SLNode* SLTfind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLNode* pcur = phead;
	while (pcur != NULL)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;//没有找到返回NULL
}

 在指定位置(pos)之前插入数据

void SLTinsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead && pos);
	SLTNode* pcur = *pphead;
	SLNode* newnode = SLTbuyNode(x);
	if (pos == *pphead)
	{
		SLTpushFront(pphead, x);
	}
	else
	{
		while (pcur->next != pos)//遍历到pos节点的前驱节点
		{
			pcur = pcur->next;
		}
		newnode->next = pos;
		pcur->next = newnode;
	}
}

在指定位置(pos)之后插入数据

void SLTinsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLNode* newnode = SLTbuyNode(x);
	if (pos->next == NULL)//如果pos是尾节点
	{
		pos->next = newnode;
		newnode->next = NULL;
	}
	else
	{
		SLNode* pafter = pos->next;//pcur是pos的后继节点
		newnode->next = pafter;
		pos->next = newnode;
	}
}

         在这里不调用二级指针的原因是头指针无需改变,需要改变的时pos节点内部next指针的指向,而对于next指针来说,pos指向的时next所在的节点,所以pos可以直接访问这个黑点,从而改变next的指向,换句话pos相对于next来说就是二级指针文章来源地址https://www.toymoban.com/news/detail-854604.html

删除pos节点

void SLTerase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead && pos && pphead);
	if (pos->next == NULL)//如果pos是尾节点
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = NULL;
		free(pos);
		pos = NULL;
	}
	else if (*pphead == pos)//如果pos是头节点
	{
		SLTNode* next = (*pphead)->next;
		free(*pphead);
		(*pphead) = next;
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

删除pos之后的节点 

void SLTeraseAfter(SLTNode* pos)
{
	assert(pos->next && pos);
	SLTNode* next = pos->next;
	pos->next = pos->next->next;
	free(next);
	next = NULL;
}

销毁链表

void SLTdestroy(SLTNode** pphead)
{
	assert(*pphead && pphead);
	SLTNode* pcur = *pphead;
	while (pcur != NULL)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

到了这里,关于【数据结构】第三节:单链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C语言】数据结构-单链表

    主页:114514的代码大冒险 qq:2188956112(欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ ) Gitee:庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com 文章目录 目录 文章目录 前言(链表的优势) 一、单链表是什么 二、单链表操作的具体代码实现 1.准备工作 2.打印链表 2.尾插(在链表末端添加数据) 3、头插(

    2024年02月02日
    浏览(45)
  • 单链表(数据结构)(C语言)

    这里特指无哨兵位单向非循环链表 目录 背景 概念 单链表的实现 前景提示 单链表的结构体定义 单链表的打印 关于为什么不断言phead 关于单链表的逻辑结构和物理结构 单链表的尾插 关于为什么要用到二级指针 关于尾插的本质 关于找尾整个过程的解释 关于为什么打印单链表

    2023年04月22日
    浏览(74)
  • 单链表——“数据结构与算法”

    各位CSDN的uu们你们好呀,今天,小雅兰的内容终于是我们心心念念的单链表啦,这一块呢,是一个很重要的部分,也是一个对目前的我来说,比较困难的部分,下面,就让我们进入单链表的世界吧 之前小雅兰写过顺序表的内容: 顺序表(更新版)——“数据结构与算法”_认

    2023年04月26日
    浏览(42)
  • 单链表—C语言实现数据结构

    本期带大家一起用C语言实现单链表🌈🌈🌈 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的;简单来说,线性表的链式存储结构生成的表,称作“链表”。 每个元素本身由两部分组成: 1、本身的信息,称为

    2024年02月07日
    浏览(81)
  • 【算法基础】(二)数据结构 --- 单链表

    ✨个人主页:bit me ✨当前专栏:算法基础 🔥专栏简介:该专栏主要更新一些基础算法题,有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下,互相监督打卡学习 🌹 🌹 🌹 实现一个单链表,链表初始为空,支持三种操作: 向链表头插入一个数; 删除第 k 个插

    2023年04月17日
    浏览(88)
  • C语言:数据结构之单链表(三)

    上篇谈了谈尾插法和头插法,这篇谈谈中间插入元素和删除。 1、中间插入元素 既然谈到了要从中间插入那就得确定插入的位置是否合法了,我总不能链表总长为5,但是插入的位置是60,这就不对了。所以得先确定这个链表的长度为多少。这个比较简单,就是在寻找尾部的过

    2024年02月13日
    浏览(42)
  • C语言:数据结构之单链表(二)

    上一篇随笔谈了谈单链表是什么东西,然后进行了初始化,这篇随笔就开始对其进行操作了,首先是增,删,改,查的增。 增,顾名思义就是要增加新的元素,单链表是链式的,那就要考虑怎么去加新元素,有三种,从头部添加,从尾部添加,从中间添加。先说说从尾部添加

    2024年02月12日
    浏览(39)
  • C语言:数据结构之单链表(一)

    当初刚开始学单链表学的是一头雾水,简直就是彻头彻尾灾难,一塌糊涂,过段时间后经过自己的重新认真思考再结合小练习明白了它是怎么个回事儿。 1、首先从它的逻辑上入手,对他有大体认知。 简单来说就是一个一个有方向小块儿连在一起,好像疫情期间大家排队做核

    2024年02月12日
    浏览(75)
  • C语言:数据结构之单链表(四)

    本篇谈一谈单链表的 改 ,具体操作就是找到他,然后修改元素即可,上一篇有相关代码,可以参考。 改函数代码如下: main函数如下:(修改第6,8,3位) 结果如下:   至此,单链表的增删改查就谈完了,只需理解它的本质是干什么,代码就很好写了。 总结:①改比较简单,

    2024年02月16日
    浏览(41)
  • <数据结构> 链表 - 单链表(c语言实现)

    哨兵位结点也叫哑节点。哨兵位结点 也是头结点 。该节点 不存储有效数据,只是为了方便操作 (如尾插时用带哨兵位的头结点很爽,不需要判空)。 有哨兵位结点的链表,第一个元素应该是链表第二个节点(head - next,head为哨兵位结点)对应的元素。 有哨兵位结点的链表

    2023年04月11日
    浏览(123)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包