初阶数据结构之单链表详解

目录

一：单链表概念

二：单链表的基本操作

1.定义结点

2.创建链表（初始化链表）

3:新增结点

4.单链表尾插

 5.单链表头插

6.单链表尾删

7：单链表头删

8.打印单链表

9.查找单链表结点

10.单链表删除指定结点

11.单链表结点修改

12.单链表结点前插入结点

三：代码总结

SL List.h

SL Lish.c

开门见山，直接开始讲解。（如有错误请指出，一定改正）

如果对你有所帮助的话，不妨点个赞再走。

                      

一：单链表概念

单链表 是一种线性数据结构，其特点是数据元素以节点的形式存储在内存中，这些节点在物理上可能是不连续的（他们的地址可能离的很远）。每个节点由一个数据域和一个指针域组成，数据域用于存储数据，而指针域包含了指向下一个节点的指针（即他们在逻辑上是连续的）。

图示：

同时，单链表可以分为带头结点和不带头结点两种。带头结点的单链表通常有一个头结点，它的指针域指向链表的第一个有效节点（首元节点），这样的设计便于进行一些特殊操作，例如删除所有节点同时保留链表。不带头结点的单链表直接从第一个有效节点开始，没有额外的头结点。

如上图的plist就是链表的头节点。

二：单链表的基本操作

1.定义结点

在实现单链表的操作之前，我们应该把结点定义出来，已知结点内存储结点数据（data）和下一个结点的地址（即一个指向下一个结点的指针），因此我们可以用结构体来定义结点。

//定义结点
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;//数据域
	struct SListNode *next;//指针域

}SLNode;

2.创建链表（初始化链表）

可以把链表初始化为两种形式。一种是带头结点的，一种是不带头节点的。

带头结点：

void initList(SLNode*head)//head为单链表头节点的指针
{
    assert(head);
    head = (SLNode*)malloc(sizeof(SLNode));为头节点开辟空间
    head->next = NULL;
}

不带头结点：

void InitList(SLNode * head)
{
	assert(head);
	head=NULL;
}

3:新增结点

当我们在进行单链表的尾插和头插操作时，总要新增一个结点（即把新增加的数据转换成单链表结点类型），因此我们可以单独写一个新增结点的代码实现，当我们进行插入操作时直接引用即可。

//单链表的新增节点
 SLNode* AddList(SLTDataType x)//x为新增的结点数据
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));为新节点开辟空间
	if (newnode == NULL)
	{
		perror("开辟结点空间失败");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

4.单链表尾插

单链表尾插入结点之前，最后的一个结点是指向NULL的，因此只需要把最后一个结点由原来的指向NULL改为指向新插入的节点即可。

//单链表尾插结点
void PushBackList(SLNode**head,SLTDataType x)
{
	assert(head);
	SLNode* newnode = AddList(x);
	if (*head == NULL)
	{
		*head= newnode;
	}
	else
	{
	    SLNode* tail = *head;
		while (tail->next)
		{
		   tail = tail->next;
		}
		tail->next = newnode;
	}
}

关于这里为什么不传 SLNode*head 而是传 SLNode**head ？在此做一个解释。

首先，在主函数中创建一个指向头节点地址的结构体指针head：SLNode*head。

注意：地址就是指针，指针就是地址。

例如：head既是头结点head的地址，也是指向头节点head的指针。

那么此时我们如果传 head ，实际传给函数的就是head的地址，然后函数用SLNode*head这个一级指针来接收，并且只有当我们要对head的实际值进行修改等操作的时候才需要传给函数他的地址。

而如果我们传的是 &head（对指针取地址），那么我们实际传过去的就是 （指向head的指针的指针）也可以叫做（指向head地址的指针的地址），然后函数需要用SLNode **head这个二级指针来接收，并且只有当我们想要对（head的地址）或者说（指向head的指针）进行修改等操作的时候才需要传给函数&head，在函数中对地址进行操作不影响实际数据。

那么我们的插入操作实际上是要对谁进行操作的呢？

插入操作实际上是对指针（地址）进行操作，例如上面的代码中的 *head=newnode，就是把（新建立结点的地址）赋给了（指向head地址的指针），此时head指向的是newnode的地址。

因此，总的来说，是因为我们想要对指针（地址）进行操作，所以才用二级指针来接收。

希望你们可以理解哈哈。

 5.单链表头插

单链表头插就是创建一个新的链表结点，然后把让链表结点指向原来的头节点即可。

//单链表头插结点
void PushFrontList(SLNode** head, SLTDataType x)
{
	assert(head);
    SLNode*newnode=AddList(x);
	SLNode*newhead = newnode;
	newnode->next =*head;
	*head= newhead;
}

6.单链表尾删

单链表尾删就是把单链表最后一个结点空间free掉，然后让单链表倒数第二个结点指向NULL。

但是需要注意两点。

（一)：assert进行断言时，不仅需要断言head还要断言*head。

 断言*head是为了确保指向head地址不为空，即断言指向头结点的的指针是否存在（链表是否为空）。

(二)：尾删结点时要区分情况，一种是原链表只有1个结点的情况，一种是链表有多个结点的情况，因为如果链表只有一个结点，那么 while（tail->next）为空会导致进不去循环，导致头节点不能被删除。

//单链表尾删结点
void DelBackList(SLNode** head)
{
	assert(head&&*head);
	if ((*head)->next == NULL)
	{
		free(*head);
		*head = NULL;
	}
	else
	{
		SLNode* tail = *head;
		SLNode* prev = NULL;//创建prev用来保存倒数第二个结点的指针
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
        tail=NULL;
		prev->next = NULL;
	}
}

7：单链表头删

单链表头删其实就是把指向头节点的指针指向第二个结点，然后把原本的头节点的空间释放掉，那么第二个结点就成为了头节点。

//单链表头删
void DelFrontList(SLNode** head)
{ 
	assert(head && *head);
	SLNode* agohead = *head;
	*head = (*head)->next;
	free(agohead);
	agohead = NULL;

}

8.打印单链表

打印单链表十分简单，只需传单链表头节点的地址然后写个循环即可。

//打印单链表
void PrintList(SLNode* head)
{
	SLNode* p = head;
	while (p!=NULL)
	{
		printf("%d ", p->data);
		p= p->next;
	}
}

9.查找单链表结点

查找单链表结点就是输入结点的地址，然后遍历链表查找结点即可。

注意：因为我们只是对链表结点的地址进行比较，此时只需传head，用SLNode*head接收即可。

如果找到就返回结点的地址，如果没有找到就返回NULL。

//单链表查找数据
SLNode* FindList(SLNode* head, SLTDataType x)
{
	SLNode* find = head;
	while (find)
	{
		if (find->data == x)
		{
			printf("找到了");
            return find;
		}
		find = find->next;
	}
	printf("没找到");
	return NULL;
}

10.单链表删除指定结点

既然是要删除指定结点，那实际上是对结点地址进行删除，然后free空间，因此也是传&head，用SLNode**head接收。

//单链表删除指定位置结点
void EraseList(SLNode** head, SLNode* pos)
{
	assert(head && pos);
	if (pos == *head)//如果链表只有一个结点，则直接引入头删函数
	{
		DelFrontList(head);
	}
	else
	{
		SLNode* prev = *head;
        SLNode* phead= *head;
		while (phead != NULL)
		{ 
           if(phead==pos)
           {
              phead->next=prev->next;
           }
           prev=phead;
           phead=phead->next;
        }
    }
}

11.单链表结点修改

结点修改十分简单，只需找到结点然后修改他的data即可。

//单链表结点修改
void ModifyList(SLNode* head, SLNode* pos, SLTDataType x)
{
	assert(head && pos);
	SLNode* phead = head;
	while (phead != pos)
	{
		phead = phead->next;
	}
	phead->data=x;
}

12.单链表结点前插入结点

需要分情况讨论。

一种为链表中的头节点，这个结点刚好就是想要插入的那个结点，那么只需直接调用单链表头插函数即可。

另一种情况就是要寻找的结点在其他的位置。

//单链表结点前插
void InsertHeadList(SLNode** head, SLNode* pos, SLTDataType x)
{
	assert(head && pos);
	SLNode* prev = *head;
	SLNode* phead = *head;
	if (phead == pos)
	{
		PushFrontList(phead,x);
	}
	else
	{
		while (phead != pos)
		{
			prev = phead;
			phead = phead->next;
		}
		prev->next = AddList(x);
		AddList(x)->next = phead;
	}
}

13.单链表结点后插入结点

//单链表结点后插
void InsertBackList(SLNode** head, SLNode* pos, SLTDataType x)
{
	assert(head && pos);
	SLNode* phead = *head;
	SLNode* newnode = AddList(x);
	while (phead != pos)
	{
		phead = phead->next;
	}
	newnode->next = phead->next->next;
	newnode = phead->next;

}

14.单链表销毁

因为链表在逻辑结构上并不是连续的，因此我们需要一个节点一个结点地去销毁。

//销毁单链表
void DesTructList(SLNode** head)
{
	assert(head);
	SLNode* phead = *head;
	while (phead != NULL)
	{
		SLNode* next = phead->next;
		free(phead);
		phead=next;
	}
	*head = NULL;

}

三：代码总结

SL List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义结点
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;//数据域
	struct SListNode *next;//指针域

}SLNode;  

//单链表初始化
void InitList(SLNode* head);

//单链表的新增节点(把新增的数据转换为结点结构体类型)
SLNode* AddList(SLTDataType x);

//单链表尾插结点
void PushBackList(SLNode**head,SLTDataType x);

//单链表头插结点
void PushFrontList(SLNode**head, SLTDataType x);

//打印单链表
void PrintList(SLNode* head);

//单链表尾删结点
void DelBackList(SLNode** head);

//单链表头删
void DelFrontList(SLNode** head);

//单链表查找数据
SLNode* FindList(SLNode* head,SLTDataType x);

//单链表删除指定位置结点
void EraseList(SLNode** head, SLNode* pos);

//单链表结点前插
void InsertHeadList(SLNode** head, SLNode* pos,SLTDataType x);

//单链表结点后插
void InsertBackList(SLNode**head,SLNode*pos,SLTDataType x);

//单链表结点修改
void ModifyList(SLNode** head, SLNode* pos, SLTDataType x);

//销毁单链表
void DesTructList(SLNode** head);

SL Lish.c

#include"SL List.h"

//单链表初始化
void InitList(SLNode* head)//head为单链表头节点的指针
{
	assert(head);
	head = NULL;
}

//单链表的新增节点
SLNode* AddList(SLTDataType x)//x为新增的结点数据
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("开辟结点空间失败");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//单链表尾插结点
void PushBackList(SLNode** head, SLTDataType x)
{
	assert(head);
	SLNode* newnode = AddList(x);
	if (*head == NULL)
	{
		*head = newnode;
	}
	else
	{
		SLNode* tail = *head;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//单链表头插结点
void PushFrontList(SLNode** head, SLTDataType x)
{
	assert(head);
	SLNode* newnode = AddList(x);
	SLNode* newhead = newnode;
	newnode->next = *head;
	*head = newhead;
}

//打印单链表
void PrintList(SLNode* phead)
{
	SLNode* p = phead;
	while (p!=NULL)
	{
		printf("%d ", p->data);
		p= p->next;
	}
}

//单链表尾删结点
void DelBackList(SLNode** head)
{
	assert(head && *head);
	if ((*head)->next == NULL)
	{
		free(*head);
		*head = NULL;
	}
	else
	{
		SLNode* tail = *head;
		SLNode* prev = NULL;//创建prev用来保存倒数第二个结点的指针
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

//单链表头删
void DelFrontList(SLNode** head)
{
	assert(head && *head);
	SLNode* agohead = *head;
	*head = (*head)->next;
	free(agohead);
	agohead = NULL;

}

//单链表查找数据
SLNode* FindList(SLNode* head, SLTDataType x)
{
	SLNode* find = head;
	while (find)
	{
		if (find->data == x)
		{
			printf("找到了");
			return find;
		}
		find = find->next;
	}
	printf("没找到");
	return NULL;
}

//单链表删除指定位置结点
void EraseList(SLNode** head, SLNode* pos)
{
	assert(head && pos);
	if (pos == *head)//如果链表只有一个结点，则直接引入头删函数
	{
		DelFrontList(head);
	}
	else
	{
		SLNode* prev = *head;
		SLNode* phead = *head;
		while (phead != NULL)
		{
			if (phead == pos)
			{
				phead->next = prev->next;
			}
			prev = phead;
			phead = phead->next;
		}
	}
}

//单链表结点前插
void InsertHeadList(SLNode** head, SLNode* pos, SLTDataType x)
{
	assert(head && pos);
	SLNode* prev = *head;
	SLNode* phead = *head;
	if (*head == pos)
	{
		PushFrontList(head, x);
	}
	else
	{
		while (phead != pos)
		{
			prev = phead;
			phead = phead->next;
		}
		prev->next = AddList(x);
		AddList(x)->next = phead;
	}
}

//单链表结点后插
void InsertBackList(SLNode** head, SLNode* pos, SLTDataType x)
{
	assert(head && pos);
	SLNode* phead = *head;
	SLNode* newnode = AddList(x);
	while (phead != pos)
	{
		phead = phead->next;
	}
	newnode->next = phead->next->next;
	newnode = phead->next;

}

//单链表结点修改
void ModifyList(SLNode** phead, SLNode* pos, SLTDataType x)
{
	assert(phead && pos);
	SLNode* pa = *phead;
	while (pa != pos)
	{
		pa = pa->next;
	}
	pa = AddList(x);
}

//销毁单链表
void DesTructList(SLNode** head)
{
	assert(head);
	SLNode* phead = *head;
	while (phead != NULL)
	{
		SLNode* next = phead->next;
		free(phead);
		phead=next;
	}
	*head = NULL;

}

至此，初阶数据结构之单链表已讲解完毕。

完结撒花。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/605172.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C语言】static关键字用法

【C语言】static关键字用法

目录 一、static修饰局部变量 二、static修饰全局变量 三、static修饰函数 一、static修饰局部变量 首先我们来看两段代码: 代码1&#xff08;不加static&#xff09; #include <stdio.h> void test() {int i 0;i;printf("%d ", i); } int main() {int i…
阅读更多...
UE5材质基础（2）——数学节点篇

UE5材质基础（2）——数学节点篇

UE5材质基础&#xff08;2&#xff09;——数学节点篇1 目录 UE5材质基础&#xff08;2&#xff09;——数学节点篇1 Add节点 Append节点 Abs节点 Subtract节点 Multiply节点 Divide节点 Clamp节点 Time节点 Lerp节点 Add节点 快捷键&#xff1a;A鼠标左键 值相加…
阅读更多...
C++学习第十二天（继承）

C++学习第十二天（继承）

1、继承的概念以及定义 继承的概念 继承机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保持原有类特性的基础上进行拓展&#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称派生类。继承呈现了面向对象程序设计的层次结构&#x…
阅读更多...
EditReady for Mac激活版：专业视频转码工具

EditReady for Mac激活版：专业视频转码工具

对于视频专业人员来说&#xff0c;一款高效的视频转码工具是不可或缺的。EditReady for Mac正是这样一款强大的工具&#xff0c;它拥有简洁直观的操作界面和强大的功能&#xff0c;让您的视频处理工作事半功倍。 EditReady for Mac支持多种视频格式的转码&#xff0c;并且支持常…
阅读更多...
多线程学习Day09

多线程学习Day09

10.Tomcat线程池 LimitLatch 用来限流&#xff0c;可以控制最大连接个数&#xff0c;类似 J.U.C 中的 Semaphore 后面再讲 Acceptor 只负责【接收新的 socket 连接】 Poller 只负责监听 socket channel 是否有【可读的 I/O 事件】 一旦可读&#xff0c;封装一个任务对象&#x…
阅读更多...
阿里云VOD视频点播流程（2）

阿里云VOD视频点播流程（2）

二、视频点播 1、入门代码 基于OSS原生SDK上传 &#xff0c;参考文档&#xff1a;https://help.aliyun.com/zh/vod/user-guide/upload-media-files-by-using-oss-sdks?spma2c4g.11186623.0.0.1f02273fj4lxNJ 视频点播面向开发者提供了丰富的上传方式&#xff0c;其中上传SDK&…
阅读更多...
软件测试实战项目(含电商、银行、APP等)

软件测试实战项目(含电商、银行、APP等)

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 关注公众号【互联网杂货铺】&#xff0c;回复 1 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 今天给大家带来几个软件测试项目的实战总结及经验&#xff0c;适…
阅读更多...
ps5电玩计时收费系统软件教程，电玩店适合的计时器，电脑定时语音提醒

ps5电玩计时收费系统软件教程，电玩店适合的计时器，电脑定时语音提醒

ps5电玩计时收费系统软件教程&#xff0c;电玩店适合的计时器&#xff0c;电脑定时语音提醒 一、前言 以下软件操作教程以&#xff0c;佳易王电玩计时计费管理软件为例说明 软件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 1、计时计费功能&#xff1a;只…
阅读更多...
PHPStudy 访问网页 403 Forbidden禁止访问

PHPStudy 访问网页 403 Forbidden禁止访问

涉及靶场 upload-labd sqli-labs pikachu dvwa 以及所有部署在phpstudy中的靶场 注意&#xff1a;一定要安装解压软件 很多同学解压靶场代码以后访问报错的原因是&#xff1a;电脑上没有解压软件。 这个时候压缩包看起来就是黄色公文包的样子&#xff0c;右键只有“全部提取…
阅读更多...
SpringCloud Alibaba Sentinel 修改Dashboard用户名和密码

SpringCloud Alibaba Sentinel 修改Dashboard用户名和密码

目录 一、下载Sentinel的Jar包 二、在启动时修改用户名和密码的命令 三、测试登录成功 在网上找到了一大堆文章&#xff0c;没一个有用的&#xff0c;最终还是通过不断测试找到了这个方法。 一、下载Sentinel的Jar包 Releases alibaba/Sentinel GitHub 二、在启动时修改…
阅读更多...
设计模式：命令模式

设计模式：命令模式

文章目录 一、什么是命令模式二、命令模式结构三、命令模式实现步骤四、命令模式应用场景 一、什么是命令模式 它允许将请求封装为对象&#xff0c;一个请求对应于一个命令&#xff0c;将发出命令的责任和执行命令的责任分割开。每一个命令都是一个操作&#xff1a;请求的一方…
阅读更多...
【管理咨询宝藏93】大型制造集团数字化转型设计方案

【管理咨询宝藏93】大型制造集团数字化转型设计方案

【管理咨询宝藏93】大型制造集团数字化转型设计方案 【格式】PDF版本 【关键词】国际咨询公司、制造型企业转型、数字化转型 【核心观点】 - 235页大型制造型集团数字化转型方案设计&#xff01;细节非常详尽&#xff0c;图表丰富&#xff01; - 系统架构必须采用成熟、具有国…
阅读更多...
JS数组操作基础

JS数组操作基础

1、JS数组常用方法 2、函数使用实例 2.1 concat() 功能&#xff1a;可以合并一个或多个数组&#xff0c;返回合并数组之后的数据&#xff0c;不会改变原来的数组 var str1 [12,3,"hello"]; var str2 ["world",123]; console.log(str1,concat(str2)); …
阅读更多...
leetcode--560和为k的子数组

leetcode--560和为k的子数组

问题 给你一个整数数组 nums 和一个整数 k &#xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1&#xff1a; 输入&#xff1a;nums [1,1,1], k 2 输出&#xff1a;2示例 2&#xff1a; 输入&#xff1a;nums [1,2…
阅读更多...
IP协议，网络层

IP协议，网络层

一、IP协议报文 在网络层最主要的协议是IP协议&#xff0c;网络层的主要任务是进行&#xff1a;1.地址管理 2.路由选择 地址管理&#xff1a;使用一套地址体系&#xff0c;描述互联网中每个设备所处的位置。 IP地址有两个版本&#xff0c;1.IPV4 2.IPV6 &#xff0c;IP…
阅读更多...
基于STM32F103ZE平台分析FreeRtos（九）——协程

基于STM32F103ZE平台分析FreeRtos（九）——协程

目录 一、协程简介 二、协程工作机制 2.1 协程控制块结构 2.2 协程管理方式 2.3 协程调度方式 2.4 协程通信机制 三、协程状态及状态切换 3.1 协程状态 3.2 状态切换 四、协程创建 五、协程调度分析 5.1 源码分析 5.2 逻辑图分析 六、协程通信 6.1 协程发送消息…
阅读更多...
Edge的使用心得和深度探索-Sider: ChatGPT 侧边栏

Edge的使用心得和深度探索-Sider: ChatGPT 侧边栏

作为一款备受欢迎的网络浏览器&#xff0c;Microsoft Edge在用户体验和功能方面都有着诸多优势。在长期的使用中&#xff0c;我总结出了三条使用心得&#xff0c;同时也发现了三个能够极大提高效率的功能。让我们一起深度探索Edge的潜力吧&#xff01; 使用心得&#xff1a; 界…
阅读更多...
Android 10.0 Launcher3定制folder文件夹2x2布局之一xml文件配置和解析相关属性

Android 10.0 Launcher3定制folder文件夹2x2布局之一xml文件配置和解析相关属性

1.前言 在10.0的系统rom产品定制化开发中，在对Launcher3的folder文件夹功能定制中，要求folder文件夹跨行显示，就是 2x2布局显示，默认的都是占1格的，现在要求占4格显示，系统默认是不支持显示4格的，所以接下来需要分析相关的 功能，然后来实现这个功能 2.Launcher3定制fo…
阅读更多...
C# WCF服务（由于内部错误，服务器无法处理该请求。）

C# WCF服务（由于内部错误，服务器无法处理该请求。）

由于内部错误&#xff0c;服务器无法处理该请求。有关该错误的详细信息&#xff0c;请打开服务器上的 IncludeExceptionDetailInFaults (从 ServiceBehaviorAttribute 或从 <serviceDebug> 配置行为)以便将异常信息发送回客户端&#xff0c;或打开对每个 Microsoft .NET …
阅读更多...
Windows+Linux的虚拟串口工具

Windows+Linux的虚拟串口工具

文章目录 1.Windows虚拟串口工具1.1 安装教程1.2 使用方法 2.Linux系统虚拟串口工具2.1 socat安装2.2 开启虚拟串口2.3 测试2.3.1 命令测试2.3.2 Cutecom工具测试 2.4 关闭虚拟串口 3.参考资料 1.Windows虚拟串口工具 下载地址&#xff1a;https://www.downxia.com/downinfo/4…
阅读更多...
最新文章

Copyright @ 2022~2023