软件设计师 - 第3章 数据结构

概述

        按照存储结构来分,数据结构可以分成如下四种:

  • 线性结构:数据元素间呈现线性关系,有单一的前驱和后继
  • 表:可以看做是线性结构的推广,是多个线性结构的集合
  • 树:不同于线性结构,其元素可以有多个直接后继
  • 图:不同于线性结构和树,其元素可以有多个直接前驱和后继

线性结构

线性表

        线性表是n个元素的有序序列,非空线性表有如下特点:

  • 存在唯一的第一个元素
  • 存在唯一的最后一个元素
  • 除第一个元素外其余元素都有且只有一个前驱
  • 除最后一个元素外其余元素都有且只有一个后继

        线性表的存储方式有两种:顺序存储、链式存储。

顺序存储

       采用顺序存储时,就是平常使用的一维数组,可通过数组的索引直接访问对应元素,但进行插入和删除操作时会麻烦些。

// 声明一个固定长度为8,采用顺序存储的线性表 —— 数组
int array[8];
for (int i = 0; i < 8; i++) {array[i] = i;
}

访问操作

        对于采用顺序存储的线性表,若要访问位置n处的数据,只需使用下表即可,效率高。

// 访问位置5处的数据
int result = array[5];

插入操作

        对于采用顺序存储的固定长度的线性表,若所有位置均被使用,此时若要在位置n处插入新的数据需要重新申请一块空间,将原空间中前n-1个元素复制到新空间,在n处填入新数据,将原空间中n处及其后的数据复制到n+1处及其后;若原空间有剩余位置未被使用,只需将n处及其后的数据“后移”,在n处填入新数据即可。

        可见对于顺序存储的结构进行插入操作时需要进行大量的“移位”操作,效率低。

// 在位置5处插入数据6
int array2[9];
for (int i = 0; i < 5; i++) {array2[i] = array[i];
}
array2[5] = 6;
for (int i = 6; i < 9; i++) {array2[i] = array[i - 1];
}

删除操作

        对于采用顺序存储的线性表,若要删除位置n处的数据,需要将n+1及其后的数据“前移”。

        可见对于顺序存储的结构进行删除操作时需要进行大量的“移位”操作,效率低。

// 删除位置5处数据
for (int i = 5; i < 8 - 1; i++) {array[i] = array[i + 1];
}
array[7] = -1;

链式存储

        采用链式存储是,除了需要存储数据数据外还需要存后继/前驱节点指针,当节点信息中只存一种(前驱或后继)指针时称为单向链表,两者都存时称为双向链表。单向链表中最后节点的后继指向第一个节点时形成的链表称为循环链表,同理,单向链表中第一个节点的前驱指向最后节点时形成的链表称为循环链表,双向链表中第一个节点的前驱指向最后节点、最后节点的后继指向第一个节点时形成的链表称为循环链表。还有一种特殊的链表,其利用顺序储存方式存储指向数据的指针,该结构称为静态链表。采用链式存储是访问特定位置元素需要从头开始遍历,效率低,但删除/删除操作效率比顺序存储高。

// 定义链式存储中节点结构
typedef struct node {int data;struct node *next;
} NODE, *LinkList;// 声明一个采用链式存储的线性表
LinkList head = NULL, tail = NULL;
for (int i = 0; i < 8; i++) {NODE* newNode = (NODE*)malloc(sizeof(NODE));if (newNode == NULL) {printf("Memory allocation failed\n");exit(1);}newNode->data = i;newNode->next = NULL;if (head == NULL) {head = newNode;} else {tail->next = newNode;}tail = newNode;    
}

访问操作

        对于采用链式存储的线性表,若要访问位置n处的数据,需要从头开始遍历,直到遍历到位置n为止,效率低。

NODE* getNode(int index) {NODE *node = head;for (int i = 0; i < 5; i++) {if (node != NULL) {node = node->next;} else {return node;}}return node;
}// 访问位置5处的数据
NODE* node = getNode(5);
if (node == NULL) {printf("Linked List Index Out of Bounds\n");exit(1);
}
int result = node->data;

插入操作

        对于采用链式存储的线性表,若要在位置n处插入新数据只需要修改n-1处的指针即可。

// 在位置5处插入数据6
NODE* node = getNode(5 - 1);
if (node == NULL) {printf("Linked List Index Out of Bounds\n");exit(1);
}
NODE* newNode = (NODE*)malloc(sizeof(NODE));
if (newNode == NULL) {printf("Memory allocation failed\n");exit(1);
}
newNode->data = 6;
newNode->next = node->next;
node->next = newNode;

删除操作

        对于采用链式存储的线性表,若要删除位置n处数据只需要修改n-1处的指针即可。

// 删除位置5处数据
NODE* node = getNode(5 - 1);
if (node == NULL) {printf("Linked List Index Out of Bounds\n");exit(1);
}
if (node->next != null) {NODE* temp = node->next;node->next = temp->next;free(temp);
}

        栈是一种线性结构,只能访问一端,修改栈内数据时只能是后进先出(Last In First Out, LIFO),栈的一端称为栈顶,另一端称为栈底,没有数据时称为空栈。一般支持如下运算:

  • 初始化:创建一个空栈
  • 判空:判断栈是否为空栈
  • 入栈:将数据放入栈顶,更新栈顶指针
  • 出栈:将栈顶数据删除,更新栈顶指针
  • 读栈顶数据:只读栈顶数据,不删除,不更新栈顶指针

        栈的应用场景有很多,常见的如下:

  • 表达式求值
  • 括号匹配

队列

        队列是一种线性结构,是一种先进先出(First In First Out, FIFO)的结构,只允许在一端插入数据,该端称为对尾,在另一端删除数据,该端称为对头。一般支持如下运算:

  • 初始化:创建一个空队列
  • 判空:判断队列是否为空栈
  • 入队:将数据放入队尾,更新队尾指针
  • 出对:将对头数据删除,更新对头指针
  • 读对头数据:只读对头数据,不删除,不更新对头指针

        队列的应用场景有很多,常见的如下:

  • 任务队列
  • 消息队列

        当队列采用顺序存储时会有些问题,下面举例说明

// 使用数组模拟队里,此时队列为空
int array[8];
int *front = array;
int *rear = array;
// 连续队列5个数据
for (int i = 0; i < 5; i++) {*rear = i;rear = rear + 1;
}
// 连续出队4个数据
for (int i = 0; i < 4; i++) {*front = -1;front = front + 1;
}
// 此时队列中只有一个元素,但此时队尾只能添加3个元素

        由于上述问题的存在,所有在使用顺序结构作为队列时使用了循环队列的概念,即队尾逻辑上下一个元素是队头,此时便可利用出队的空间。

#define SIZE 8int array[SIZE];
int *front = array;
int *rear = array;
// 记录队列中的元素数量
int count = 0;// 判断队列是否满,只有在限制队列长度时才需要判断,比如本例中队列长度为8
bool isFull() {return count == SIZE;
}// 判断队列是否为空,此时front与rear指向同一个位置
bool isEmpty() {return count == 0;
}// 入队
void enqueue(int value) {if (isFull()) {printf("Queue is full\n");return;}*rear = value;// 如此时rear已经是顺序结构的最后一个元素,则指向第一个元素rear = (rear == array + SIZE - 1) ? array : rear + 1;count++;
}// 出队
void dequeue() {if (isEmpty()) {printf("Queue is empty\n");return;}// 如此时front已经是顺序结构的最后一个元素,则指向第一个元素front = (front == array + SIZE - 1) ? array : front + 1;count--;
}

        是一种特殊的线性表,数据元素是字符,有几个概念:空串,空格串,子串,串相等,串比较等,有如下几个基本操作:

  • 赋值操作
  • 连接操作
  • 求长度操作
  • 串比较操作
  • 求子串操作

        子串的定位操作通常称为串的模式匹配,子串也称模式串。

朴素的模式匹配算法

        该算法也称布鲁特-福斯算法,基本思想是从主串的第一个字符开始匹配子串,若相同则匹配下一个字符,完全匹配成功则返回,否则从主串的第二个字符还是匹配,……。

        主串长度n,匹配串长度m。最好情况匹配成功实践复杂度O(n+m),最坏情况的时间复杂度O(n*m)。

改进的模式匹配算法

        改进的模式匹配算法又称KMP算法。待补充

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

软间隔支持向量机支持向量的情况以及点的各种情况

软间隔支持向量 ​ 这一节我们要回答的问题是&#xff1f;如何判断一个点是软间隔支持向量机中的支持向量&#xff0c;在硬间隔支持向量机中&#xff0c;支持向量只需要满足一个等式&#xff1a; y i ( w T x i b ) − 1 0 y_i(w^Tx_i b) -1 0 yi​(wTxi​b)−10 ​ 在软间…

界面控件DevExpress Blazor UI v24.1新版亮点 - 全新PDF Viewer等组件

DevExpress Blazor UI组件使用了C#为Blazor Server和Blazor WebAssembly创建高影响力的用户体验&#xff0c;这个UI自建库提供了一套全面的原生Blazor UI组件&#xff08;包括Pivot Grid、调度程序、图表、数据编辑器和报表等&#xff09;。 DevExpress Blazor控件目前已经升级…

defaultdict()语法

一、defaultdict产生的原因&#xff1a; 当我使用普通的字典时&#xff0c;用法一般是dict{},添加元素的只需要dict[element] value即&#xff0c;调用的时候也是如此&#xff0c;dict[element] xxx,但前提是element字典里&#xff0c;如果不在字典里就会报错。 defaultdict的…

[HE phy]

前导码 5G OFDM分为两部分&#xff0c;前导码Legacy preamble和数据data 前导码类型&#xff1a; 其中前导码Legacy preamble分为&#xff1a;Legacy Short Traing (L-STF), L_LTF, L-SIG。 如果数据是HT/VHT/HE&#xff0c;则还有其对应格式的前导码。 各类型作用&#xff…

【matlab】数据类型01-数值型变量(整数、浮点数、复数、二进制和十六进制)

文章目录 一、 整数1.1 整数的最值1.2 大整数1.3 当整数值超过了uint64最大值1.4 和其它类型数值运算 二、 浮点数2.1 双精度和单精度2.2 浮点数的存储2.3 浮点数的最值2.4 浮点数的“四舍五入”2.5 浮点数的算术运算2.6 意外&#xff1a;舍入误差、抵消、淹没和中间转换 三、复…

Tessy学习笔记—requirement(需求)的管理

1&#xff1a;什么是需求 Tessy中的requirement&#xff08;需求&#xff09;是&#xff0c;我们还是跟着Tessy官方的文档&#xff0c;继续学习&#xff0c;打开官方自带的工程Is Value In Range Requirement.project。 按照官方自带的操作手册&#xff0c;导入txt类型的需求…

关于10款PDF编辑工具我的使用体验!!!!!

如今&#xff0c;pdf的使用已经见怪不怪。在我们的工作、学习和生活中都已经离不开PDF文档了。那我么&#xff0c;随之而来的问题也就是我们经常需要对PDF文件进行编辑。市面上已经出现了许多PDF编辑软件。下面&#xff0c;我将与大家分享一下这几款PDF编辑器的个人使用经历。 …

unity小:shaderGraph不规则涟漪、波纹效果

实现概述 在本项目中&#xff0c;我们通过结合 Sine、Polar Coordinates 和 Time 节点&#xff0c;实现了动态波纹效果。以下是实现细节&#xff1a; 核心实现 Sine 波形生成&#xff1a; 使用 Sine 节点生成基本的波形。该节点能够创建周期性变化&#xff0c;为波纹效果提供…

针对gitgitee的使用

1.下载git 链接 打开终端&#xff0c;桌面鼠标右键 2.配置密钥 登录gitee。 设置密钥 查看官方文档 跟着教程 复制最后的输出进行密钥添加 验证是否添加成功 3.创建&连接远程仓库 创建仓库 git终端进行配置 远程仓库克隆到本地 桌面终端clone,克隆他人|自己的仓库到本地…

基于yolov8、yolov5的玉米病害检测识别系统(含UI界面、训练好的模型、Python代码、数据集)

项目介绍 项目中所用到的算法模型和数据集等信息如下&#xff1a; 算法模型&#xff1a;     yolov8、yolov8 SE注意力机制 或 yolov5、yolov5 SE注意力机制 &#xff0c; 直接提供最少两个训练好的模型。模型十分重要&#xff0c;因为有些同学的电脑没有 GPU&#xff0…

省级生活垃圾无害化处理率面板数据(2004-2022年)

生活垃圾无害化处理率是指经过处理的生活垃圾中&#xff0c;达到无害化标准的垃圾所占的比例。这一指标的提高&#xff0c;意味着城市在垃圾处理方面的能力增强&#xff0c;能够有效减少环境污染&#xff0c;提升居民生活质量&#xff0c;同时也是城市可持续发展的重要保障。 …

NTIRE2024 | 修复一切图像RAIM: Restore All Image Model Challenge报告分析

论文/报告地址&#xff1a;NTIRE 2024 Restore Any Image Model (RAIM) in the Wild Challenge 0、写在前面 马上CVPR2024就要开幕&#xff0c;各大挑战赛的排名和详细报告也都出炉。近期留意到这个名字很屌的赛道&#xff0c;修复一切图像的模型&#xff0c;小米的团队的拿了…

【Visual Studio】设置文件目录

打开属性 输出目录&#xff1a;$(SolutionDir)bin\$(Platform)\$(Cinfiguration)\ 中间目录&#xff1a;$(SolutionDir)bin\intermediates\$(Platform)\$(Cinfiguration)\

基于Java的校园菜鸟驿站管理系统

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据…

Photoshop(PS)——人像磨皮

1.新建一个文件&#xff0c;背景为白色&#xff0c;将图片素材放入文件中 2.利用CtrlJ 复制两个图层出来&#xff0c;选择第一个拷贝图层&#xff0c;选择滤镜---杂色---蒙尘与划痕 3.调整一下数值&#xff0c;大概能够模糊痘印痘坑&#xff0c;点击确定。 4.然后选择拷贝2图层…

Yocto - 使用Yocto开发嵌入式Linux系统_13 创建定制层

Creating Custom Layers 除了使用社区或供应商提供的现有图层外&#xff0c;我们还将在本章中学习如何为我们的产品创建图层。此外&#xff0c;我们还将了解如何创建机器定义和分布&#xff0c;并从中获益&#xff0c;从而更好地组织我们的源代码。 In addition to using exist…

第5章-总体设计 5.2 需求转化为规格

5.2 需求转化为规格 1.框式产品&#xff08;1&#xff09;业务规格&#xff0c;这需要满足客户期望、有市场竞争力、颗粒度最合理。&#xff08;2&#xff09;整框规格&#xff0c;包括电源、功耗、散热、可靠性的规格&#xff0c;要保证整款满足环境应用要求。&#xff08;3&a…

kali上安装docker,并且生成centos7容器和创建apache容器后台运行

声明&#xff01; 学习视频来自B站up主 泷羽sec 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&#…

4. Spring Cloud Ribbon 实现“负载均衡”的详细配置说明

4. Spring Cloud Ribbon 实现“负载均衡”的详细配置说明 文章目录 4. Spring Cloud Ribbon 实现“负载均衡”的详细配置说明前言1. Ribbon 介绍1.1 LB(Load Balance 负载均衡) 2. Ribbon 原理2.2 Ribbon 机制 3. Spring Cloud Ribbon 实现负载均衡算法-应用实例4. 总结&#x…

约克VRF中央空调新天氟地水/天氟热水,做冬日生活的温暖守护者

随着冬季的悄然降临,现代人对居家环境的舒适性要求愈发提升,如何在寒冷的季节里营造一个温暖、静谧且健康的居住空间,成为了时下关注的焦点。面对冬日空气干燥、寒气侵袭的挑战,约克VRF中央空调凭借其氟系统和水系统的跨界融合,为家庭带来了纵享四季的恣意体验,让温暖与舒适触手…