数据结构（链表）

文章目录

  • 一、单链表
    • 1、单链表定义
    • 2、初始化单链表
      • 2.1、不带头结点的单链表
      • 2.2、带头结点的单链表
    • 3、单链表基本操作
      • 3.1、按位序插入（带头结点）
      • 3.2、按位序插入（不带头结点）
      • 3.3、指定结点的后插操作
      • 3.4、指定结点的前插操作
      • 3.5、按位序删除（带头结点）
      • 3.6、指定结点的删除
      • 3.7、按位查找
      • 3.8、按值查找
    • 4、单链表的建立
      • 4.1、尾插法
      • 4.2、头插法
  • 二、双链表
    • 1、双链表的初始化（带头结点）
    • 2、插入
    • 3、删除
    • 4、遍历
  • 三、循环链表
    • 3.2、循环双链表
  • 四、静态链表
    • 4.1、基本操作
  • 顺序表和链表的比较

一、单链表

1、单链表定义

在这里插入图片描述
typedef重命名数据类型
在这里插入图片描述
第二种声明方式可读性更强
在这里插入图片描述
LinkList和LNode*的不同用法
在这里插入图片描述

#include<stdio.h>

//定义单链表结点类型 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList; 

//查找单链表中的某一个位置的数
LNode* GetElem(LinkList L,int i){
	int j=1;
	LNode *p=L->next;
	if(i==0)
		return L;
	if(i<1)
		return NULL;
	if(p!=NULL&&j<i){
		p=p->next;
		j++;
	} 
	return p;
}

2、初始化单链表

2.1、不带头结点的单链表

在这里插入图片描述

//定义单链表结点类型 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList; 

//初始化一个空的单链表
bool InitList(LinkList &L){
	L=NULL;
	return true;
} 

//判断单链表是否为空
bool Empty(LinkList L){
	return(L==NULL);
}

2.2、带头结点的单链表

在这里插入图片描述

//定义单链表结点类型 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList; 

//初始化一个空的单链表
bool InitList(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));
	if(L==NULL)
		return false;
	L->next=NULL;
	return true;
} 

//判断单链表是否为空
bool Empty(LinkList L){
	return(L->next==NULL);
} 
int main(){
	LinkList L;
	InitList(L);
	return 0;
}

大多数情况使用带头结点的方式
在这里插入图片描述
在这里插入图片描述

3、单链表基本操作

3.1、按位序插入（带头结点）

在这里插入图片描述
带头结点插入位置1时
在这里插入图片描述
在这里插入图片描述

//插入操作
bool ListInsert(LinkList &L,int i,int e){
	if(i<1)
		return false;
	LNode *p;
	p=L;
	int j=0;
	//找到i-1位置 
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	//开拓新区域 
	 LNode *s=(LNode*)malloc(sizeof(LNode));
	 s->data=e;
	 s->next=p->next;
	 p->next=s;
	 return true;
}

在这里插入图片描述

3.2、按位序插入（不带头结点）

在这里插入图片描述

bool ListInsert(LinkList &L,int i,int e){
	if(i<1)
		return false;
	if(i==1){//不同的地方 
		LNode*s=(LNode*)malloc(sizeof(LNode));
		s->data=e;
		s->next=L;//因为L没有next所以直接等于
		L=s; //头指针指向新结点 
		return true; 
	}
	LNode *p;
	p=L;
	int j=0;
	//找到i-1位置 
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	//开拓新区域 
	 LNode *s=(LNode*)malloc(sizeof(LNode));
	 s->data=e;
	 s->next=p->next;
	 p->next=s;
	 return true;
}

3.3、指定结点的后插操作

在这里插入图片描述

在这里插入图片描述

bool InsertNextNode(LNode *p,int e){
	if(p==NULL)
		return false;
	//开拓新区域 
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;	
}

3.4、指定结点的前插操作

前面区域无法访问，只能把头结点传入
在这里插入图片描述
将p的值赋值给s，再将插入的值赋值给p
在这里插入图片描述

bool InsertPriorNode(LNode *p,int e){
	if(p==NULL)
		return false;
	//开拓新区域 
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->next=p->next;
	p->next=s;
	s->data=p->data;
	p->data=e;
	return true;	
}

3.5、按位序删除（带头结点）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

bool ListDelete(LinkList &L,int i,int &e){
	if(i<1)
		return false;
	LNode *p;
	p=L;
	int j=0;
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	if(p->next==NULL)
		return false;
	LNode *q=p->next;//q指向被删除的结点 
	e=q->data;//保存删除的值 
	p->next=q->next;//断开q 
	free(q);//销毁q 
	return true; 
}

3.6、指定结点的删除

如果删除最后一个元素，就会出错
在这里插入图片描述
在这里插入图片描述

3.7、按位查找

在这里插入图片描述

LNode *GetElem(LinkList L,int i){
	if(i<1)
		return false;
	LNode *p;
	p=L;
	int j=0;
	while(p!=NULL&&j<i-1){
		p=p->next;
		j++; 
	}
	return p;
}

在这里插入图片描述

3.8、按值查找

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

4、单链表的建立

在这里插入图片描述

4.1、尾插法

请添加图片描述

LinkList List_TailInsert(LinkList &L){
	int x;
	L=(LNode*)malloc(sizeof(LNode));
	L->next=NULL;
	LNode *s,*r=L;
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		r->next=s;
		s->data=x;
		r=s;
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
}

4.2、头插法

链表的逆置
在这里插入图片描述

LinkList List_TailInsert(LinkList &L){
	LNode *s;
	int x;
	L=(LNode*)malloc(sizeof(LNode));
	L->next=NULL;
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);
	}
	return L;
}

二、双链表

1、双链表的初始化（带头结点）

在这里插入图片描述
在这里插入图片描述

bool InitDLinkList(DLinkList &L){
	L=(DNode*)malloc(sizeof(DNode));
	L->next=NULL;
	L->prior=NULL;
	return true;
}

2、插入

在这里插入图片描述
在这里插入图片描述

bool InsertNextDNode(DNode *p,DNode *s){
	s->next=p->next;
	if(p->next!=NULL)
		p->next->prior=s;
	s->prior=p;
	p->next=s;
}

3、删除

在这里插入图片描述

4、遍历

在这里插入图片描述
在这里插入图片描述

三、循环链表

在这里插入图片描述
在这里插入图片描述

3.2、循环双链表

在这里插入图片描述
在这里插入图片描述
双链表，在尾部插入数据时，双链表会在第二行p->next->prior=s出错，因为p->next为空，但是循环后就不为空了
在这里插入图片描述
在这里插入图片描述

四、静态链表

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

#include<stdio.h>
#define MaxSize 10

//常规 
struct Node{
	int data;
	int next;
}; 
//课本 
typedef struct{
	int data;
	int next;
}SLinkList[MaxSize];

int main(){

	struct Node x;
	printf("%d\n",sizeof(x));
	//常规
	struct Node a[MaxSize];
	printf("%d\n",sizeof(a)); 
	SLinkList b;
	printf("%d\n",sizeof(b)); 	
}

4.1、基本操作

在这里插入图片描述
在这里插入图片描述
优点：
增、删操作不需要大量移动元素
缺点：
不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
适用场景：
①不支持指针的低级语言；
②数据元素数量固定不变的场景（如操作系统的文件分配表FAT)

顺序表和链表的比较

存储结构
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
表长难以预估、经常要增加/删除元素——链表
表长可预估、查询(搜索)操作较多——顺序表

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

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

相关文章

python222网站实战(SpringBoot+SpringSecurity+MybatisPlus+thymeleaf+layui)-系统属性管理实现

python222网站实战(SpringBoot+SpringSecurity+MybatisPlus+thymeleaf+layui)-系统属性管理实现

锋哥原创的SpringbootLayui python222网站实战&#xff1a; python222网站实战课程视频教程&#xff08;SpringBootPython爬虫实战&#xff09; ( 火爆连载更新中... )_哔哩哔哩_bilibilipython222网站实战课程视频教程&#xff08;SpringBootPython爬虫实战&#xff09; ( 火…
阅读更多...
Linux 文件和文件夹的创建与删除

Linux 文件和文件夹的创建与删除

目录 一. 新建1.1 mkdir 新建文件夹1.2 touch 新建空文件1.3 vi命令创建文件1.4 > 和 >> 新建文件 二. 删除 一. 新建 1.1 mkdir 新建文件夹 -p&#xff1a;递归的创建文件夹&#xff0c;当父目录不存在的时候&#xff0c;会自动创建 mkdir -p test1/test2/test31.…
阅读更多...
【HTML 基础】介绍

【HTML 基础】介绍

文章目录 定义作用基本概念1. 标签&#xff08;Tags&#xff09;2. 元素&#xff08;Elements&#xff09;3. 属性&#xff08;Attributes&#xff09;4. 文档结构 总结 HTML&#xff08;HyperText Markup Language&#xff09;是构建世界各地互联网页面的基本构建块之一。作为…
阅读更多...
【Demo】基于CharacterController组件的角色控制

【Demo】基于CharacterController组件的角色控制

项目介绍 项目名称&#xff1a;Demo1 项目版本&#xff1a;1.0 游戏引擎&#xff1a;Unity2020.3.26f1c1 IDE&#xff1a;Visual Studio Code 关键词&#xff1a;Unity3D&#xff0c;CharacterController组件&#xff0c;角色控制&#xff0c;自定义按键&#xff0c;Scrip…
阅读更多...
基于springboot的美发管理系统

基于springboot的美发管理系统

文章目录 项目介绍主要功能截图&#xff1a;部分代码展示设计总结项目获取方式 &#x1f345; 作者主页&#xff1a;超级无敌暴龙战士塔塔开 &#x1f345; 简介&#xff1a;Java领域优质创作者&#x1f3c6;、 简历模板、学习资料、面试题库【关注我&#xff0c;都给你】 &…
阅读更多...
报错：npm ERR code EPERM

报错：npm ERR code EPERM

1 完整错误 npm ERR! code EPERM npm ERR! syscall open npm ERR! path D:\NodeJS\node_cache\_cacache\tmp\7bbab18e npm ERR! errno EPERM npm ERR! FetchError: Invalid response body while trying to fetch https://registry.npmjs.org/webpack: EPERM: operation not pe…
阅读更多...
智慧文旅：提升旅游体验与推动经济发展的新动力

智慧文旅：提升旅游体验与推动经济发展的新动力

一、智慧文旅的定义与意义 智慧文旅&#xff0c;即智慧文化旅游&#xff0c;是一种以当地特色文化元素为核心驱动&#xff0c;利用现代科技手段实现旅游景区全面智慧升级的旅游模式。其意义在于为游客提供高效便捷的旅游信息化服务&#xff0c;提升旅游体验&#xff0c;同时推…
阅读更多...
ETCD高可用架构涉及常用功能整理

ETCD高可用架构涉及常用功能整理

ETCD高可用架构涉及常用功能整理 1. etcd的高可用系统架构和相关组件1.1 Quorum机制1.2 Raft协议 2. etcd的核心参数2.1 常规配置2.2 特殊优化配置2.2.1 强行拉起新集群 --force-new-cluster2.2.2 兼容磁盘io性能差2.2.3 etcd存储quota 3. etcd常用命令3.1 常用基础命令3.1.1 列…
阅读更多...
【DDD】学习笔记-建立统一语言

【DDD】学习笔记-建立统一语言

统一语言是提炼领域知识的产出物&#xff0c;获得统一语言就是需求分析的过程&#xff0c;也是团队中各个角色就系统目标、范围与具体功能达成一致的过程。 使用统一语言可以帮助我们将参与讨论的客户、领域专家与开发团队拉到同一个维度空间进行讨论&#xff0c;若没有达成这…
阅读更多...
ThreadLocal内存泄漏示例

ThreadLocal内存泄漏示例

ThreadLocal内存泄漏是老生常谈的问题了&#xff0c;原理就不多说了&#xff0c;这里只简单回顾下 Thread类有个属性threadLocals&#xff0c;其实就是个map。 这个map的结构如下&#xff0c;key是ThreadLocal对象&#xff0c;是一个弱引用&#xff0c;value是调用threadLocal…
阅读更多...
机器学习周报第30周

机器学习周报第30周

目录 摘要Abstract一、文献阅读1 论文标题2 论文摘要3 过去方案4 论文方案5 相关代码 摘要 Abstract 一、文献阅读 1 论文标题 Accurate one step and multistep forecasting of very short-term PV power using LSTM-TCN model - ScienceDirect 2 论文摘要 准确的光伏功…
阅读更多...
翻译: GPT-4 with Vision 升级 Streamlit 应用程序的 7 种方式二

翻译: GPT-4 with Vision 升级 Streamlit 应用程序的 7 种方式二

GPT-4 Vision 系列: 翻译: GPT-4 with Vision 升级 Streamlit 应用程序的 7 种方式一 GPT-4 Vision 的 7 个实际用例 Pre-requisites:先决条件&#xff1a; 订阅 ChatGPT Plus 以访问 GPT-4 Vision。如果您不熟悉 Streamlit&#xff0c;请按照安装步骤操作。 1. 绘制您的应…
阅读更多...
Java多线程编程中的异常处理策略

Java多线程编程中的异常处理策略

第1章&#xff1a;引言 大家好&#xff0c;我是小黑&#xff0c;咱们今天聊聊异常处理。想必大家在写代码的时候都遇到过各种各样的异常吧&#xff1f;有时候&#xff0c;一个小小的异常如果处理不当&#xff0c;就可能导致整个程序崩溃。特别是在多线程环境下&#xff0c;异常…
阅读更多...
java关键字概述——final及常量概述

java关键字概述——final及常量概述

前言&#xff1a; 打好基础&#xff0c;daydayup! final final概述 final关键字是最终的意思&#xff0c;可以修饰&#xff08;类&#xff0c;方法&#xff0c;变量&#xff09; final作用 修饰类&#xff1a;该类被称为最终类&#xff0c;特点为不能被继承 修饰方法&#xff…
阅读更多...
python 基础知识点（蓝桥杯python科目个人复习计划26）

python 基础知识点（蓝桥杯python科目个人复习计划26）

今日复习内容&#xff1a;基础算法中的前缀和 1.定义&#xff1a; 前缀和&#xff1a;对于一个长度为n的列表a&#xff0c;前缀和为&#xff1a; sum[i] a[1] ...a[i];例如&#xff1a;a [1,2,3,4,5],则它的前缀和数组sum为&#xff1a;[1,3,6,10,15]。 2.前缀和的性质 …
阅读更多...
【计算机网络】IP协议及动态路由算法

【计算机网络】IP协议及动态路由算法

对应代码包传送门 IP协议及动态路由算法代码包及思科模拟器资料说明 相关文章 【计算机网络】中小型校园网构建与配置 【计算机网络】Socket通信编程与传输协议分析 【计算机网络】网络应用通信基本原理 目的&#xff1a; 1、掌握IP协议&#xff0c;IP分片&#xff0c;DH…
阅读更多...
laravel框架项目对接小程序实战经验回顾

laravel框架项目对接小程序实战经验回顾

一.对接小程序总结 1.状态转换带来的问题&#xff0c;如下 问题原因&#xff1a;由于status 传参赋值层级较多&#xff0c;导致后续查询是数组但是传参是字符串&#xff0c; 解决方案&#xff1a;互斥的地方赋值为空数组&#xff0c;有状态冲突的地方unset掉不需要的参数 2参…
阅读更多...
循环的乐章与爱情的旋律

循环的乐章与爱情的旋律

循环的乐章与爱情的旋律 The Rhapsody of Loops and the Melody of Love 在一个阳光明媚的Java编程课上&#xff0c;男主角林浩然&#xff0c;一个热衷于代码逻辑和算法谜题的大二学生&#xff0c;正沉浸在他的Java世界里。而女主角杨凌芸&#xff0c;则是班级中出了名的“程序…
阅读更多...
【AI量化分析】小明在量化中使用交叉验证原理深度分析解读

【AI量化分析】小明在量化中使用交叉验证原理深度分析解读

进行交叉验证好处 提高模型的泛化能力&#xff1a;通过将数据集分成多个部分并使用其中的一部分数据进行模型训练&#xff0c;然后使用另一部分数据对模型进行测试&#xff0c;可以确保模型在未见过的数据上表现良好。这样可以降低模型过拟合或欠拟合的风险&#xff0c;提高模…
阅读更多...
多维时序 | Matlab实现DBO-LSTM蜣螂算法优化长短期记忆神经网络多变量时间序列预测

多维时序 | Matlab实现DBO-LSTM蜣螂算法优化长短期记忆神经网络多变量时间序列预测

多维时序 | Matlab实现DBO-LSTM蜣螂算法优化长短期记忆神经网络多变量时间序列预测 目录 多维时序 | Matlab实现DBO-LSTM蜣螂算法优化长短期记忆神经网络多变量时间序列预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab实现DBO-LSTM多变量时间序列预测&#x…
阅读更多...
最新文章

Copyright @ 2022~2023