【数据结构初阶】单链表SLlist

描述

不同于顺序表，顺序表的数据是存储在一个连续的空间里的

而链表它是链接起来的结构体地址。

所以我们不用像顺序表一样先创建一块空间出来，而是创建一个能存数据节点和节点与下一个节点之间的连接；

所以：“一个能存数据节点”我们用int Data表示；

“与下一个节点之间的连接”：我们用指针连接起来。

组织

打印

为了方便测试，我们先写个打印单链表的函数；

1.这个打印函数需要断言吗？
不需要，即使结构体为空，也能打印,只不过是没有数据而已，这时打印出来的就是空的。如果能打印出来，但是却断言报错，不太合适。

2.怎么打印？
用一个指针cur指向结构体，用while循环打印出来，当cur指向的结构体为空时，停止打印。

3.while的判断条件可以是while(cur->next)吗？
不可以，因为这样最后一个的数据就打印不出来了。

4.在while循环中，让cur指向下一个结构体，可以用cur++吗？
不可以，不同于顺序表，顺序表的数据是存储在一个连续的空间里的，链表它是链接起来的结构体地址，是节点与节点之间的连接，cur++无法指向下一个节点。
 

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

1.尾插

每在插入一个数据之前，首先得为这个结构体开辟一个结点，

用malloc开辟，由于插入数据时我们都要进行开辟一个结点的操作，所以我们可以打包成一个函数：


进行尾插首先就是要找到尾节点，

找尾分两种情况：

1. 当*pphead本身为空时，就直接将newnode插入就可以了；

2. *pphead本身不为空时，只要找到tail->next为空的，那个就是结构体的尾了


当pphead不为空时，找尾while循环的判断条件可以写成这样tail！=NULL与插入结点时tail=newnode吗？
不可以，因为这样就无法保持链接状态了

尾插的本质是：原为节点中存储新的尾节点的地址。

SLTNode* SLTNewnode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("melloc fail");
		return NULL;
	}
	newnode->Data = x;
	newnode->next = NULL;
	
	return newnode;

}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//创建节点
	SLTNode* newnode = SLTNewnode(x);
	if (newnode == NULL)
	{
		return;
	}

	//情况一：pphead为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//情况二：pphead不为空
	else
	{
		//找到尾节点
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

2.尾删

1.尾删需要断言吗？
需要，因为如果链表为空，是删不了的；


2.尾删的思路
尾删分三种讨论：

1.如果链表为空，删不了，我们这里断言判断一下
2.链表中只有一个数据
3.链表中的数据为一个以上

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);

	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾置空
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}

}

3.头插

1.头插需要断言吗？
但是当链表为空的时候，可以插入数据，*pphead是不需要断言的。


2.头插的思路
首先先要创建一个结点，将结点的next与链表的第一个指针链接起来。最后要注意把链表的头给改成newnode。

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = SLTNewnode(x);
	if (newnode == NULL)
	{
		return;
	}

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


4.头删

1.头删需要断言吗？
空链表不能删除，所以*pphead也需要断言。

头删的思路：

void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	

	SLTNode* head = *pphead;
	*pphead = head->next;
	free(head);
	head = NULL;

}


5.查找

1.查找需要断言吗？
不需要，链表为空就返回NULL；


2.查找的思路
当链表的cur不为空，就继续逐一比对，找到了就返回cur，没找到就指向下一个,直到cur指向空;

如果还没找到，就返回NULL；

这里的phead用一级指针就可以了，因为不用修改里面的任何值；

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->Data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	//如果没找到就返回NULL
	return NULL;
}



6.指定位置后插入

1.需要断言吗？
指定的位置pos不能为空，所以需要断言；


2.思路
创建一个新结点newnode，然后先让newnode->next = pos->next;让newnode的后面链接起来，在让pos和newnode链接起来pos->next = newnode;；

反过来写的话，由于pos->next已经被改了，所以不能是pos与newnode链接，插入就会失败；


void SLTInsertAfter( SLTNode* pos, SLTDataType x)
{
	assert(pos);


	SLTNode* newnode = SLTNewnode(x);
	if (newnode == NULL)
	{
		return;
	}

	newnode->next = pos->next;
	pos->next = newnode;

}



7.指定位置后删除

1.需要断言吗？
指定的位置pos不能为空，所以需要断言；

void SListEraseAfter( SLTNode* pos)
{
	assert(pos);

	if (pos->next == NULL)
	{
		printf("已是最后一个,不能删\n");
		return;
	}

	SLTNode* cur = pos->next;
	pos->next = pos->next->next;
	free(cur);
	cur= NULL;
}

8.链表的销毁

思路
结点逐一free，最后记得把*pphead改为最后的cur。

void SLTDel(SLTNode** pphead)
{
	assert(*pphead);

	SLTNode* cur = *pphead;
	SLTNode* prev = cur;
	while (cur)
	{
		prev = cur->next;
		free(cur);
		cur = prev;
	}
	*pphead = cur;
}

关于其他的一些细节问题

为什么不像顺序表一样写初始化函数？

可写可不写，这里结构体里面的数据比较少，我们在测试代码的时候直接用指针指向了一块空间。

为什么要传二级指针？

想要改变变量的数值而不会因为栈帧的销毁而销毁，就得取到该变量的地址；

什么时候要传二级指针，什么时候要传一级指针？

想要改变变量里的数值就要传址调用，二级指针用来接收一级指针；

如果只是简单的访问就用传值调用；

整个程序

.h文件

#define _CRT_SECURE_NO_WARNINGS 1

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


typedef int SLTDataType;

typedef struct SLTlist
{
	SLTDataType Data;	
	struct SLTlist * next;

}SLTNode;

void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopFront(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
void SLTInsertAfter( SLTNode* pos, SLTDataType x);
void SListEraseAfter( SLTNode* pos);
void SLTDel(SLTNode** pphead);

.c文件

#include"SLlist.h"

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

SLTNode* SLTNewnode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("melloc fail");
		return NULL;
	}
	newnode->Data = x;
	newnode->next = NULL;
	
	return newnode;

}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//创建节点
	SLTNode* newnode = SLTNewnode(x);
	if (newnode == NULL)
	{
		return;
	}

	//情况一：pphead为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//情况二：pphead不为空
	else
	{
		//找到尾节点
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);

	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾置空
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}

}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = SLTNewnode(x);
	if (newnode == NULL)
	{
		return;
	}

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

void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	

	SLTNode* head = *pphead;
	*pphead = head->next;
	free(head);
	head = NULL;

}

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->Data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	//如果没找到就返回NULL
	return NULL;
}

void SLTInsertAfter( SLTNode* pos, SLTDataType x)
{
	assert(pos);


	SLTNode* newnode = SLTNewnode(x);
	if (newnode == NULL)
	{
		return;
	}

	newnode->next = pos->next;
	pos->next = newnode;

}

void SListEraseAfter( SLTNode* pos)
{
	assert(pos);

	if (pos->next == NULL)
	{
		printf("已是最后一个,不能删\n");
		return;
	}

	SLTNode* cur = pos->next;
	pos->next = pos->next->next;
	free(cur);
	cur= NULL;
}

void SLTDel(SLTNode** pphead)
{
	assert(*pphead);

	SLTNode* cur = *pphead;
	SLTNode* prev = cur;
	while (cur)
	{
		prev = cur->next;
		free(cur);
		cur = prev;
	}
	*pphead = cur;
}

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

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

相关文章

2023年11月界面制作软件合集，新手也能学会！

2023年11月界面制作软件合集，新手也能学会！

在今天的互联网时代&#xff0c;有各种界面制作软件可供选择。这些软件可以帮助新手和专业人士创建精美且高效的界面设计。从最基础的拖拽操作到复杂的编程接口&#xff0c;不同的软件提供了一系列的功能和特性&#xff0c;满足了各种需求。我们将在本文中探讨8大神器&#xff…
阅读更多...
MySql操作

MySql操作

Mysql数据库项目学习笔记 1.条件查询后排序 (SELECT counter : 0) temp设定临时变量ORDER BY id ASC用于将id以升序形式进行排列 SELECTcounter : counter 1 AS ROW,username,type,content FROMtest_info,( SELECTcounter : 0 ) temp WHEREusername 2 AND type 3 ORDER BYi…
阅读更多...
JAXB：用XmlElement注解复杂类型的Java属性，来产生多层嵌套的xml元素

JAXB：用XmlElement注解复杂类型的Java属性，来产生多层嵌套的xml元素

例如&#xff0c;下面这段请求的xml代码&#xff0c;在元素body下面又多了一层&#xff0c;嵌套了4个元素&#xff1a; <?xml version"1.0" encoding"UTF-8"?><request><reqtype>04</reqtype><secret>test</secret>…
阅读更多...
庖丁解牛：NIO核心概念与机制详解 01 _ 入门篇

庖丁解牛：NIO核心概念与机制详解 01 _ 入门篇

文章目录 Pre输入/输出Why NIO流与块的比较通道和缓冲区概述什么是缓冲区&#xff1f;缓冲区类型什么是通道&#xff1f;通道类型 NIO 中的读和写概述Demo : 从文件中读取1. 从FileInputStream中获取Channel2. 创建ByteBuffer缓冲区3. 将数据从Channle读取到Buffer中 Demo : 写…
阅读更多...
Idea 中 Git 不提交当前分支修改代码并切换分支

Idea 中 Git 不提交当前分支修改代码并切换分支

1、当前分支修改代码切换分支 日常开发中&#xff0c;我们可能会碰到我们正在修改当前 01 分支的代码&#xff0c;突然要去修改另外一个 02 分支的代码情况&#xff0c;而我们 01 分支写的代码还未经过测试&#xff0c;并不能马上提交&#xff0c;这个时候我们切换到 02 分支就…
阅读更多...
记一次线上bug排查-----SpringCloud Gateway组件 请求头accept-encoding导致响应结果乱码

记一次线上bug排查-----SpringCloud Gateway组件 请求头accept-encoding导致响应结果乱码

基于公司的业务需求&#xff0c;在SpringCloud Gateway组件的基础上&#xff0c;写了一个转发服务&#xff0c;测试开发阶段运行正常&#xff0c;并实现初步使用。但三个月后&#xff0c;PostMan请求接口&#xff0c;返回异常&#xff0c;经排查&#xff0c;从日志中获取到转发…
阅读更多...
使用Docker/K8S/Helm部署项目流程

使用Docker/K8S/Helm部署项目流程

假设项目已经开发完成&#xff0c;部署流程如下&#xff1a; 一、制作镜像&#xff1a; 1、创建nginx配置文件default.conf server {listen 80;server_name localhost; # 修改为docker服务宿主机的iplocation / {root /usr/share/nginx/html;index index.html ind…
阅读更多...
element-ui中怎样使用iconfont的图标

element-ui中怎样使用iconfont的图标

1 登录 https://www.iconfont.cn/ 2 搜索合适的图 这里可以找到这个图所在的图库。这样就可以一次查找到对应的所有同款图标 3 选择同款加入购物车 4 将购物车的icon加入项目&#xff0c;注意是新建项目&#xff0c;除非你是确定需要前面已经加过的icon 5 下载icon 选择fon…
阅读更多...
日期相关整理

日期相关整理

3214. 节日 有一类节日的日期并不是固定的&#xff0c;而是以“a 月的第 b 个星期 c ”的形式定下来的&#xff0c;比如说母亲节就定为每年的五月的第二个星期日。 现在&#xff0c;给你 a,b,c 和 y1,y2&#xff0c;希望你输出从公元 y1 年到公元 y2 年间的每年的 a 月的第 b 个…
阅读更多...
为什么越来越多人选择学习Python？

为什么越来越多人选择学习Python？

今天我要和大家聊聊一个很热门的话题&#xff1a;为什么那么多人学习Python&#xff1f; 最近小编发现一个有趣的现象&#xff0c;高中生们居然在学校课程里学Python&#xff0c;这不仅给我们这些已经毕业多年的人当头一棒&#xff0c;更是彻底颠覆了传统观念。现在的高中生竟…
阅读更多...
Embedding技术与应用(4): Embedding应用工程探析

Embedding技术与应用(4): Embedding应用工程探析

编者按&#xff1a;随着互联网内容数量的急剧增长&#xff0c;个性化推荐已成为各大科技公司的核心竞争力之一。那么&#xff0c;如何构建一个可靠、高效的基于嵌入技术的推荐系统&#xff0c;使其能够在实际生产环境中正常运行呢&#xff1f;这是所有从业者都关心的问题。 本文…
阅读更多...
（一）RISC-V 指令集及寄存器介绍

（一）RISC-V 指令集及寄存器介绍

1. RISC-V指令集介绍 RISC-V 念作 “risk-five”&#xff0c;代表着 Berkeley 所研发的第五代精简指令集。 该项目 2010 年始于加州大学伯克利&#xff08;Berkeley&#xff09;分校&#xff0c;希望选择一款 ISA用于科研和教学。经过前期多年的研究和选型&#xff0c;最终决定…
阅读更多...
UE TransformVector 学习笔记

UE TransformVector 学习笔记

假如算现在枪的位置&#xff0c;那么就是先拿人的位置再拿枪在本地的相对位置相加&#xff0c;就是枪的位置&#xff0c;也就是枪在场景中的位置&#xff0c;那么这里还可以写成Actor的变化和枪的相对位置连在TransformVector上&#xff0c;返回的就是枪的场景位置 这里做反算&…
阅读更多...
统一身份认证平台之SSO建设

统一身份认证平台之SSO建设

前言 上篇说道Passwordless无密码技术&#xff0c;也提到了数字时代密码管理的难度&#xff0c;其实在日常的生活中&#xff0c;很多用户也会因为忘记某些网站的登录密码而烦恼。为了方便记忆&#xff0c;很多人都在不同的站点使用相同的用户名和密码&#xff0c;虽然也可以减少…
阅读更多...
PS太难学，这款软件更简单！——Lightroom

PS太难学，这款软件更简单！——Lightroom

今天&#xff0c;我们来谈谈Adobe Photoshop Lightroom软件&#xff0c;它是当今数字拍摄工作流程中不可或缺的一部分。现在您可以快速导入、处理、管理和展示图像 — 从一张照片到所有照片。增强的校正工具、强大的组织功能以及灵活的打印选项可以帮助您加快速度。 Adobe Pho…
阅读更多...
redis集群（Cluster）

redis集群（Cluster）

文章目录 前言一、资源准备二、redis安装二、启动redis三、构建集群 前言 redis 集群三种方式&#xff1a;主从复制&#xff0c;哨兵模式&#xff0c;Cluster集群。 本文只介绍Cluster集群部署方案。 一、资源准备 服务器1台&#xff08;正常应该是3台,每台2个节点&#xff…
阅读更多...
源启容器平台KubeGien 打造云原生转型的破浪之舰

源启容器平台KubeGien 打造云原生转型的破浪之舰

云原生是应用上云的标准路径&#xff0c;也是未来发展大的趋势。如何将业务平滑过渡到云上&#xff1f;怎样应对上云期间的各项挑战呢&#xff1f;中电金信基于金融级数字底座“源启”打造了一款非常稳定可靠、多云异构、安全可控、开放灵活的容器平台产品——源启容器平台Kube…
阅读更多...
Threejs_03 全屏+响应式画布实现

Threejs_03 全屏+响应式画布实现

咋控制全屏呢&#xff1f; 1.做一个用来点击的按钮 var btn document.createElement("button"); btn.innerHTML "点击全屏"; btn.style.position "absolute"; btn.style.top "10px"; btn.style.left "10px"; btn.sty…
阅读更多...
纯JS,RSA，AES,公钥，私钥生成及加解密

纯JS,RSA，AES,公钥，私钥生成及加解密

通过网络找的JS源文件&#xff0c;修改后使用&#xff0c;包含RSA 密匙对生成 及AES 加解密 涉及的JS源文件 下载 GitHub - cgrlancer/RSA-AES: 纯js,RSA,AES前端加解密 前端引用 import {generateRsaKeyWithPKCS8,encryptByRSA,decryptByRSA,encrypt,decrypt,testRsa} fr…
阅读更多...
【Java程序员面试专栏 专业技能篇】Java SE核心面试指引（一）：基础知识考察

【Java程序员面试专栏 专业技能篇】Java SE核心面试指引（一）：基础知识考察

关于Java SE部分的核心知识进行一网打尽，包括四部分：基础知识考察、面向对象思想、核心机制策略、Java新特性，通过一篇文章串联面试重点，并且帮助加强日常基础知识的理解，全局思维导图如下所示 本篇Blog为第一部分：基础知识考察，子节点表示追问或同级提问 基本概念 …
阅读更多...
最新文章

Copyright @ 2022~2023