数据结构 day05

数据结构 day05

  • 5. 队列
    • 5.3. 链式队列
      • 5.3.1. 特征
      • 5.3.2. 代码实现
  • 6. 双向链表
    • 6.1. 特性
      • 6.2. 代码实现

5. 队列

5.3. 链式队列

5.3.1. 特征

逻辑结构：线性结构
存储结构：链式存储
操作：创建、入列、出列、判空、清空

5.3.2. 代码实现

头文件：linkqueue.h

#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__
typedef int datatype;
typedef struct node_t
{
   datatype data;
   struct node_t *next;
} linkqueue_node_t, *linkqueue_list_t;

typedef struct // 将队列头指针和尾指针封装到一个结构体里
{
   linkqueue_list_t front; // 相当于队列的头指针
   linkqueue_list_t rear;  // 相当于队列的尾指针
                           // 有了链表的头指针和尾指针，那么我们就可以操作这个链表
} linkqueue_t;
//1.创建一个空的队列，用有头链表。
linkqueue_t *createEmptyLinkQueue();
//2.入列 data代表入列的数据
int inLinkQueue(linkqueue_t *p, datatype data);
// 3. 出列
//思想：每次释放front所指节点，然后移动front到后一个节点返回当前节点数据
datatype outLinkQueue(linkqueue_t *p);
//4.判断队列是否为空
int isEmptyLinkQueue(linkqueue_t *p);
//5.求队列长度的函数
int lengthLinkQueue(linkqueue_t *p);
//6.清空队列
void clearLinkQueue(linkqueue_t *p);
#endif
  1. 创建一个空的队列，用有头链表。
linkqueue_t *createEmptyLinkQueue();
{
	// 申请空间存放队列结构
	linkqueue_list_t q = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
	if (q == NULL)
	{
		perror("Space opening failure!!");
		return -1;
	}
	// 初始化
	q->next = NULL;

	// 申请空间存放头尾指针
	linkqueue_t *p = (linkqueue_t*) malloc(sizeof(linkqueue_t));
	if(p == NULL)
	{
		perror("Space opening failure!!");
		free(q);
		return -1;
	}
	// 初始化
	p->front = q;
	p->rear = q;
	
	return p;
}
  1. 入列
int inLinkQueue(linkqueue_t *p, datatype data);
{
	// 开辟空间存放新节点，定义指针pnew指向新节点
	linkqueue_list_t pnew = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
	// 容错判断
	if(pnew == NULL)
	{
		perror("Space opening failure!!");
		return -1;
	}
	// 新节点初始化
	pnew->data = data;
	pnew->next = NULL;
	// 链接新节点
	p->rear->next = pnew;
	// 尾指针移动
	p->rear = pnew;
	
	return 0；
}
  1. 出列, 每次释放front所指下一个节点，然后移动front到后一个节点返回当前节点数据
datatype outLinkQueue(linkqueue_t *p);
{
	// 容错判断
	if(isEmptyLinkQueue(p))
	{
		perror("Linkqueue is empty!!");
		return -1;
	}
	// 定义指针pdel，指向被删除节点
	linkqueue_list_t pdel = p->front->next;
	// 定义变量，暂存出列数据
	datatype data = pdel->data;
	// 删除节点
	p->front->next = pdel->next;
	free(pdel);
	pdel = NULL;
	// 出列完成后，如果队列为空，那么召回rear
	if(p->front == NULL)
		p->rear = p->front;
	// 返回出列数据
	return data;
}
  1. 判断队列是否为空
int isEmptyLinkQueue(linkqueue_t *p);
{
	// 以队列的特性呈现
	return p->rear == p->front;
}

也可以使用p->front->next == NULL;来作为判断队列为空的条件，但这是链表特性的内容，作为队列的操作内容，尽量以队列的特性呈现

  1. 求队列长度的函数
int lengthLinkQueue(linkqueue_t *p);
{
	// 定义变量存放长度
	int len =0;
	// 定义头指针，头指针遍历链表
	linkqueue_list_t h = p->front;
	// 遍历链表
	while(h->next == NULL)
	{
		h = h->next;
		len ++;
	}
	return len;
}

多定义一个头指针的原因：通过地址找到的front，所以对于front来说，相当于地址传递，所以改变front的指向会影响队头的值

  1. 清空队列
void clearLinkQueue(linkqueue_t *p);
{
	while(!isEmptyLinkQueue(p))
		outLinkQueue(p);
}

6. 双向链表

6.1. 特性

逻辑特性：线性结构
存储结构：链式存储
操作：增删改查
创建：模仿链式队列的形式创建
双向链表的创建结构图

6.2. 代码实现

头文件 doublelinklist.h

#ifndef __DOUBLELINKLIST_H__
#define __DOUBLELINKLIST_H__

// 双向链表的节点定义

typedef int datatype;
typedef struct node_t
{
   datatype data;        // 数据域
   struct node_t *next;  // 指向下一个节点的指针 next 先前的
   struct node_t *prior; // 指向前一个节点的指针 prior 下一个
} link_node_t, *link_node_p;

// 将双向链表的头指针和尾指针封装到一个结构体里
// 思想上有点像学的链式队列
typedef struct doublelinklist
{
   link_node_p head; // 指向双向链表的头指针
   link_node_p tail; // 指向双向链表的尾指针
   int len;          // 用来保存当前双向链表的长度
} double_list_t, *double_list_p;

//1.创建一个空的双向链表
double_list_p createEmptyDoubleLinkList();
// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_p p, int post, datatype data);
// 3.遍历双向链表
void showDoubleLinkList(double_list_p p);
// 4.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_p p);
// 5.删除双向链表指定位置数据
int deletePostDoubleLinkList(double_list_p p, int post);
//6.求双向链表的长度
int lengthDoubleLinkList(double_list_p p);
//7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_p p,datatype data);
//8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_p p,int post, datatype data)
// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
void deleteDataDoubleLinkList(double_list_p p, datatype data)；
#endif
  1. 创建一个空的双向链表
double_list_p createEmptyDoubleLinkList()
{
   // 申请空间存放头尾指针
   double_list_p p = (double_list_p)malloc(sizeof(double_list_t));
   if (p == NULL)
   {
       perror("Space opening failure!!");
       return NULL;
   }
   // 申请空间存放头节点
   link_node_p ph = (link_node_p)malloc(sizeof(link_node_t));
   if (ph == NULL)
   {
       perror("Space opening failure!!");
       free(p);
       p = NULL;
       return NULL;
   }
   // 头尾指针初始化，头节点初始化
   p->head = ph;
   p->tail = ph;
   p->len = 0;
   ph->next = NULL;
   ph->prior = NULL;

   return p;
}
  1. 向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_p p, int post, datatype data)
{
   // 容错判断
   if (post < 0 || post > p->len)
   {
       perror("post is err!!");
       return -1;
   }
   // 定义temp暂存head或tail
   link_node_p temp = NULL;
   // 定义pnew指向被插入节点
   link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));
   // 初始化
   pnew->data = data;
   pnew->prior = NULL;
   pnew->next = NULL;
   // 判断插入位置在前半段还是后半段
   if (post < p->len / 2)
   {
       temp = p->head;
       for (int i = 0; i < post; i++)
           temp = temp->next;
   }
   else
   {
       temp = p->tail;
       for (int i = p->len - 1; i > post; i--)
           temp = temp->prior;
   }
   // 建立链接
   pnew->next = temp->next;
   pnew->prior = temp;
   temp->next = pnew;
   if (post == p->len)
       // 尾指针移动
       p->tail = pnew;
   else
       pnew->next->prior = pnew;

   // 长度+1
   p->len++;
}
  1. 遍历双向链表
void showDoubleLinkList(double_list_p p)
{
   // 定义h，代替head移动遍历
   link_node_p temp = NULL;
   printf("正向遍历：");
   temp = p->head;
   while (temp->next != NULL)
   {
       temp = temp->next;
       printf("%-4d", temp->data);
   }
   printf("\n");
   printf("反向遍历：");
   temp = p->tail;
   while (temp != p->head)
   {
       printf("%-4d", temp->data);
       temp = temp->prior;
   }
   printf("\n");
}
  1. 判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_p p)
{
   return p->len == 0;
}
  1. 删除双向链表指定位置数据
int deletePostDoubleLinkList(double_list_p p, int post)
{
   // 容错判断
   if (isEmptyDoubleLinkList(p) || post < 0 || post > p->len - 1)
   {
       perror("deletePostDoubleLinkList err");
       return -1;
   }
   // 定义一个pdel指向被删除节点
   link_node_p pdel = NULL;
   // 判断前半段还是后半段
   if (post < p->len / 2)
   {
       pdel = p->head;
       for (int i = 0; i <= post; i++)
           pdel = pdel->next;
   }
   else
   {
       pdel = p->tail;
       for (int i = p->len - 1; i >= post; i--)
           pdel = pdel->prior;
   }
   // 删除操作
   pdel->prior->next = pdel->next;
   if (pdel->next == NULL)
       p->tail = pdel->prior;
   else
       pdel->next->prior = pdel->prior;

   return 0;
}
  1. 求双向链表的长度
int lengthDoubleLinkList(double_list_p p)
{
   return p->len;
}
  1. 查找指定数据出现的位置 data被查找的数据
// 7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_p p, datatype data)
{
   // 定义temp指向头指针，代替头指针移动
   link_node_p temp = p->head;
   // 定义变量post，保存位置
   int post = 0;

   while (temp->next == NULL)
   {
       temp = temp->next;
       if (temp->data == data)
           return post;
       post++;
   }

   return -1;
}
  1. 修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_p p,int post, datatype data)
{
   // 容错判断
   if (isEmptyDoubleLinkList(p) || post < 0 || post > p->len - 1)
   {
       perror("changeDataDoubleLinkList err");
       return -1;
   }
   // 定义一个temp，代替头尾指针移动
   link_node_p temp = NULL;
       if (post < p->len / 2)
   {
       temp = p->head;
       for (int i = 0; i <= post; i++)
           temp = temp->next;
   }
   else
   {
       temp = p->tail;
       for (int i = p->len - 1; i >= post; i--)
           temp = temp->prior;
   }
   // 修改数据
   temp->data = data;
   return 0;
}
  1. 删除双向链表中的指定数据 data代表删除所有出现的data数据
void deleteDataDoubleLinkList(double_list_p p, datatype data)
{
   // 定义pdel遍历，暂存被删除节点
   link_node_p pdel = p->head->next;
   // 遍历链表，直到pdel指向最后一个节点时停止
   while (pdel == p->tail)
   {
       if (pdel->data == data)
       {
           pdel->prior->next = pdel->next;
           pdel = pdel->prior;
           free(pdel->next->prior);
           pdel->next->prior = pdel;
           p->len--;
       }
       pdel = pdel->next;
   }
   // 判断最后一个节点数据是否匹配，匹配删除，不匹配就结束遍历
   if (pdel->data == data)
   {
       p->len--;
       p->tail = pdel->prior;
       p->tail->next = NULL;
       free(pdel);
   }
   pdel = NULL;
}

从头节点后节点开始用指针pdel遍历，相当于遍历无头链表，遇到需要删除节点的就用pdel指向它然后删除，如果不需要删除则pdel继续往后走一个节点。

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

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

相关文章

【深度解析】图解Deepseek-V3模型架构-混合专家模型（MoE）

【深度解析】图解Deepseek-V3模型架构-混合专家模型（MoE）

一、引言 最近非常火爆的DeepSeek-V3模型&#xff0c;是一个包含6710亿总参数的强大混合专家模型&#xff08;MoE&#xff09;&#xff0c;其中每个token激活370亿参数。该模型在DeepSeek-V2验证有效的核心架构基础上&#xff0c;采用多头潜在注意力&#xff08;MLA&#xff0…
阅读更多...
内容中台驱动企业数字化内容管理高效协同架构

内容中台驱动企业数字化内容管理高效协同架构

内容概要 在数字化转型加速的背景下&#xff0c;企业对内容管理的需求从单一存储向全链路协同演进。内容中台作为核心支撑架构&#xff0c;通过统一的内容资源池与智能化管理工具&#xff0c;重塑了内容生产、存储、分发及迭代的流程。其核心价值在于打破部门壁垒&#xff0c;…
阅读更多...
多模态本地部署ConVideoX-5B模型文生视频

多模态本地部署ConVideoX-5B模型文生视频

文章目录 一、多模态概念1.多模态学习2. 人机交互3. 健康医疗4. 内容创作和娱乐 二、模型介绍三、环境安装1. 安装工具包2. 模型下载 四、运行代码五、代码解析六、效果生成七. 总结1. 模型介绍2. 部署环境3. 部署步骤4. 生成视频5. 应用场景 一、多模态概念 多模态&#xff0…
阅读更多...
关于post和get的请求参数问题

关于post和get的请求参数问题

今天在和泓宇交流的时候&#xff0c;谈到了关于postman测试接口的问题。我昨天在postman测试的时候&#xff0c;对于条件查询不知道怎么测试&#xff0c;脑子里很混乱。今天&#xff0c;泓宇借着条件查询这个机会给我讲了讲get和post的请求参数的知识&#xff0c;趁着现在有记忆…
阅读更多...
分布式光纤传感：为生活编织“感知密网”

分布式光纤传感：为生活编织“感知密网”

分布式光纤测温技术虽以工业场景为核心&#xff0c;但其衍生的安全效益已逐步渗透至日常生活。 分布式光纤测温技术&#xff08;DTS&#xff09;作为一种先进的线型温度监测手段&#xff0c;近年来在多个领域展现了其独特的优势。虽然其核心应用场景主要集中在工业、能源和基础…
阅读更多...
ICLR2022 | SETR | 提高视觉Transformers的对抗迁移性

ICLR2022 | SETR | 提高视觉Transformers的对抗迁移性

On Improving Adversarial Transferability Of Vision Transformers 摘要-Abstract引言-Introduction背景和相关工作-Background And Related Work增强ViTs的对抗迁移能力-Enhancing Adversarial Transferability Of ViTs实验-Experiments结论-Conclusion 论文链接 本文 “On …
阅读更多...
Python的那些事第二十三篇：Express（Node.js）与 Python：一场跨语言的浪漫邂逅

Python的那些事第二十三篇：Express（Node.js）与 Python：一场跨语言的浪漫邂逅

摘要 在当今的编程世界里，Node.js 和 Python 像是两个性格迥异的超级英雄，一个以速度和灵活性著称，另一个则以强大和优雅闻名。本文将探讨如何通过 Express 框架将 Node.js 和 Python 结合起来，打造出一个高效、有趣的 Web 应用。我们将通过一系列幽默风趣的实例和表格，展…
阅读更多...
学习笔记之debian的thonny开发（尚未验证）--从stm32裸机到linux嵌入式系统

学习笔记之debian的thonny开发（尚未验证）--从stm32裸机到linux嵌入式系统

这应该算 stm32裸机用户 转 linux嵌入式系统 的入门学习笔记。 【鲁班猫】39-vnc远程桌面连接鲁班猫_哔哩哔哩_bilibili 本集的鲁班猫的视频介绍中&#xff0c;没有清晰明确指出需要linux开发板接入网络&#xff0c;接入网络可以使用有线网口或者wifi路由&#xff0c;有些提示…
阅读更多...
基于SSM安居房地产房屋销售系统数据库源代码

基于SSM安居房地产房屋销售系统数据库源代码

源代码数据库LW文档&#xff08;1万字以上&#xff09;开题报告答辩稿 部署教程代码讲解代码时间修改教程 一、开发工具、运行环境、开发技术 开发工具 1、操作系统&#xff1a;Window操作系统 2、开发工具&#xff1a;IntelliJ IDEA或者Eclipse 3、数据库存储&#xff1a…
阅读更多...
CNN-LSSVM卷积神经网络最小二乘支持向量机多变量多步预测，光伏功率预测

CNN-LSSVM卷积神经网络最小二乘支持向量机多变量多步预测，光伏功率预测

代码地址&#xff1a;CNN-LSSVM卷积神经网络最小二乘支持向量机多变量多步预测&#xff0c;光伏功率预测 CNN-LSSVM卷积神经网络最小二乘支持向量机多变量多步预测&#xff0c;光伏功率预测 一、引言 1、研究背景和意义 光伏发电作为可再生能源的重要组成部分&#xff0c;近…
阅读更多...
uniapp二次封装组件（py组件）

uniapp二次封装组件（py组件）

1.前言 根据自己的使用情况&#xff0c;为了提高开发效率&#xff0c;对已有组件进行了二次封装&#xff0c;文章中二次封装的组件简称为py组件。有些element-ui中表单组件&#xff08;Form&#xff09;想在uniapp中进行使用&#xff0c;py组件封装了一些实现起来比较复杂的组…
阅读更多...
MySQL智障离谱问题，删了库确还存在、也不能再创建同名库

MySQL智障离谱问题，删了库确还存在、也不能再创建同名库

1、问题 今天跟后端朋友接毕设单子的时候&#xff0c;后端穿过来的【weather.sql】这个文件没弄好&#xff0c;导致这个【weather】数据库的数据是错的&#xff0c;因此我用datagrip的GUI界面直接右键删除&#xff0c;结果就是tmd删不掉&#xff0c;ok&#xff0c;我只能在那新…
阅读更多...
【区块链】零知识证明基础概念详解

【区块链】零知识证明基础概念详解

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 零知识证明基础概念详解引言1. 零知识证明的定义与特性1.1 基本定义1.2 三个核心…
阅读更多...
Vript-Hard——一个基于高分辨率和详细字幕的视频理解算法

Vript-Hard——一个基于高分辨率和详细字幕的视频理解算法

一、概述 多模态学习的最新进展促进了对视频理解和生成模型的研究。随之而来的是&#xff0c;对高分辨率视频和详细说明所建立的高质量数据集的需求激增。然而&#xff0c;由于时间因素的影响&#xff0c;视频与文本的配对不像图像那样容易。准备视频和文本配对是一项困难得多…
阅读更多...
如何通过AI让PPT制作更轻松：从AI生成PPT到一键智能生成

如何通过AI让PPT制作更轻松：从AI生成PPT到一键智能生成

如何通过AI让PPT制作更轻松&#xff1a;从AI生成PPT到一键智能生成&#xff01;在这个信息爆炸的时代&#xff0c;PPT几乎成了每个人办公必备的工具。但说到制作PPT&#xff0c;很多人头疼不已——排版、设计、内容的整理&#xff0c;时间一不小心就被浪费掉了。有没有一种方法…
阅读更多...
Docker拉不下来镜像问题解决法案

Docker拉不下来镜像问题解决法案

打开docker的设置界面 配置如下&#xff1a; vi /etc/docker/daemon.json {"builder": {"gc": {"defaultKeepStorage": "20GB","enabled": true}},"experimental": false,"registry-mirrors": ["…
阅读更多...
数据守护者：备份文件的重要性及自动化备份实践

数据守护者：备份文件的重要性及自动化备份实践

在信息化社会&#xff0c;数据已成为企业运营和个人生活的重要组成部分。无论是企业的核心业务数据&#xff0c;还是个人的珍贵照片、重要文档&#xff0c;数据的丢失或损坏都可能带来无法估量的损失。因此&#xff0c;备份文件的重要性愈发凸显&#xff0c;它不仅是数据安全的…
阅读更多...
分类预测 | MFO-LSSVM飞蛾扑火算法优化最小二乘支持向量机多特征分类预测Matlab实现

分类预测 | MFO-LSSVM飞蛾扑火算法优化最小二乘支持向量机多特征分类预测Matlab实现

分类预测 | MFO-LSSVM飞蛾扑火算法优化最小二乘支持向量机多特征分类预测Matlab实现 目录 分类预测 | MFO-LSSVM飞蛾扑火算法优化最小二乘支持向量机多特征分类预测Matlab实现分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.Matlab实现MFO-LSSVM飞蛾扑火算法优化最小二…
阅读更多...
2025 docker可视化管理面板DPanel的安装

2025 docker可视化管理面板DPanel的安装

1.什么是 DPanel &#xff1f; DPanel 是一款 Docker 可视化管理面板&#xff0c;旨在简化 Docker 容器、镜像和文件的管理。它提供了一系列功能&#xff0c;使用户能够更轻松地管理和部署 Docker 环境。 软件特点&#xff1a; 可视化管理&#xff1a;提供直观的用户界面&#…
阅读更多...
游戏引擎学习第106天

游戏引擎学习第106天

仓库:https://gitee.com/mrxiao_com/2d_game_2 回顾我们当前的情况 编写一个完整的游戏&#xff0c;没有使用任何库或引擎&#xff0c;完全依靠传统的编程方式进行开发。目前&#xff0c;我们已经完成了渲染、实体存储等很多基础工作&#xff0c;接下来可能会开始做一些性能优…
阅读更多...
最新文章

Copyright @ 2022~2023