当前位置：首页 > news >正文

软考-软件设计师中级备考 4、数据结构

news 来源：原创 2025/5/24 9:35:29

1、数据结构三要素

要素	定义	分类	特点
逻辑结构	数据元素之间的逻辑关系，是从具体问题抽象出来的数学模型，与数据存储无关	1. 集合结构：数据元素同属一个集合，无其他特殊关系如一盒麦丽素豆子 2. 线性结构：元素存在一对一的线性关系如消息队列 3. 树形结构：元素存在一对多的层次关系如数据库部门列表，要有parentId 4. 图状（网状）结构：元素存在多对多的关系如角色与权限是多对多的网状结构，数据库设计要搞个关系表	只关注数据元素间的逻辑联系，不涉及数据在计算机中的存储方式
物理结构 (存储结构)	数据的逻辑结构在计算机中的存储表示，包括数据元素的表示和关系的表示	1. 顺序存储结构：逻辑上相邻的元素存储在物理上相邻的单元，元素间逻辑关系由存储单元邻接关系体现如数组 2. 链式存储结构：不要求元素物理位置相邻，通过指针表示元素间逻辑关系如链表 3. 索引存储结构：除存储数据元素外，建立附加索引表，通过索引项（关键字，地址）定位元素如聚集索引 4. 散列存储结构：根据关键字直接计算元素存储地址如哈希表	与计算机的存储设备和存储方式密切相关，直接影响数据操作的效率
数据的运算	施加在数据上的操作，包括运算的定义（针对逻辑结构）和实现（针对存储结构）	常见运算如插入、删除、查找、排序、遍历等	运算的定义基于逻辑结构，运算的实现依赖于存储结构

要素

定义

分类

特点

逻辑结构

数据元素之间的逻辑关系，是从具体问题抽象出来的数学模型，与数据存储无关

1. 集合结构：数据元素同属一个集合，无其他特殊关系如一盒麦丽素豆子
2. 线性结构：元素存在一对一的线性关系如消息队列
3. 树形结构：元素存在一对多的层次关系如数据库部门列表，要有parentId
4. 图状（网状）结构：元素存在多对多的关系如角色与权限是多对多的网状结构，数据库设计要搞个关系表

只关注数据元素间的逻辑联系，不涉及数据在计算机中的存储方式

物理结构

(存储结构)

数据的逻辑结构在计算机中的存储表示，包括数据元素的表示和关系的表示

1. 顺序存储结构：逻辑上相邻的元素存储在物理上相邻的单元，元素间逻辑关系由存储单元邻接关系体现如数组
2. 链式存储结构：不要求元素物理位置相邻，通过指针表示元素间逻辑关系如链表
3. 索引存储结构：除存储数据元素外，建立附加索引表，通过索引项（关键字，地址）定位元素

如聚集索引
4. 散列存储结构：根据关键字直接计算元素存储地址
如哈希表

与计算机的存储设备和存储方式密切相关，直接影响数据操作的效率

数据的运算

施加在数据上的操作，包括运算的定义（针对逻辑结构）和实现（针对存储结构）

常见运算如插入、删除、查找、排序、遍历等

运算的定义基于逻辑结构，运算的实现依赖于存储结构

2、线性表

对比项目	顺序存储结构	链式存储结构（以单链表为例，双链表、循环链表类似）
定义	把线性表的元素按逻辑顺序依次存放在一组连续的存储单元中	用指针将线性表的元素（节点）链接起来，每个节点含数据和指针
实现方式	一般使用数组实现	链表，由节点构成，节点包含数据域和指针域
存储特点	存储单元连续，逻辑相邻的元素物理位置也相邻	存储单元不一定连续，元素逻辑相邻通过指针体现
随机访问	可以随机访问，通过数组下标直接定位，时间复杂度为 O (1)	不能随机访问，需从表头开始顺序遍历，时间复杂度为 O (n)
插入操作	在中间位置插入元素时，需移动插入位置后的元素，平均时间复杂度为 O (n)	只需修改插入位置前一个节点的指针，时间复杂度为 O (1)（已知插入位置）
删除操作	删除中间位置元素时，需移动删除位置后的元素，平均时间复杂度为 O (n)	只需修改删除位置前一个节点的指针，时间复杂度为 O (1)（已知删除位置）
空间需求	需要预先分配一定大小的连续空间，可能会导致空间浪费（若分配过大）或溢出（若分配过小）	不需要预先分配大量连续空间，可动态申请和释放节点空间，空间利用率较高
应用场景	适合频繁进行随机访问，插入和删除操作较少的场景，如数组实现的线性表用于统计学生成绩等	适合频繁进行插入和删除操作，随机访问需求较少的场景，如操作系统中的进程调度链表
常见类型	无其他细分类型	单链表、双链表（节点有两个指针，可双向遍历）、循环链表（单循环链表尾指针指向头节点，双循环链表头尾节点相互连接）

3、栈和队列

对比项目	栈	队列
定义	只允许在一端进行插入和删除操作的线性表，这一端称为栈顶，另一端称为栈底	只允许在一端进行插入操作，在另一端进行删除操作的线性表。插入的一端称为队尾，删除的一端称为队头
操作特点	后进先出（Last In First Out，LIFO）	先进先出（First In First Out，FIFO）
实现方式	可以用顺序存储结构（数组）实现，也可以用链式存储结构（链表）实现	可以用顺序存储结构（数组）实现，也可以用链式存储结构（链表）实现
顺序存储实现	通常用一个数组和一个指向栈顶元素的指针来实现。入栈时，将元素放入栈顶指针指向的位置，然后栈顶指针加 1；出栈时，先取出栈顶指针指向的元素，然后栈顶指针减 1	用数组实现时，需要两个指针，一个指向队头，一个指向队尾。入队时，将元素放入队尾指针指向的位置，然后队尾指针加 1；出队时，取出队头指针指向的元素，然后队头指针加 1。为了避免数组空间的浪费，通常采用循环队列的方式，即当队尾指针到达数组末尾时，若数组前端还有空闲空间，则将队尾指针绕回到数组开头
链式存储实现	用链表实现栈时，栈顶指针指向链表的头节点。入栈操作在链表头部插入节点，出栈操作删除链表头部节点	用链表实现队列时，队头指针指向链表的头节点，队尾指针指向链表的尾节点。入队操作在链表尾部插入节点，出队操作删除链表头部节点
主要操作	入栈（Push）：将元素压入栈顶出栈（Pop）：将栈顶元素弹出获取栈顶元素（Top）：获取栈顶元素的值，但不弹出元素判断栈空（IsEmpty）：判断栈是否为空求栈的大小（Size）：获取栈中元素的个数	入队（Enqueue）：将元素加入队尾出队（Dequeue）：将队头元素移出队列获取队头元素（Front）：获取队头元素的值，但不出队判断队空（IsEmpty）：判断队列是否为空求队列的大小（Size）：获取队列中元素的个数
应用场景	函数调用栈：用于存储函数调用时的局部变量、参数等信息，按照后进先出的原则进行管理表达式求值：利用栈来处理运算符和操作数，实现表达式的计算括号匹配检查：检查表达式中的括号是否匹配，通过将左括号入栈，遇到右括号时与栈顶的左括号进行匹配	广度优先搜索（BFS）：在图的遍历中，用于存储待访问的节点，按照先进先出的顺序进行访问任务队列：在多任务处理系统中，用于存储待处理的任务，按照任务到达的先后顺序进行处理缓存系统：按照先进先出的原则淘汰最早进入缓存的数据

4、串、数组、矩阵和广义表

对比项目	串	数组	矩阵	广义表
定义	由零个或多个字符组成的有限序列，通常用于表示文本数据，如字符串	由一组具有相同数据类型的元素组成的数据结构，这些元素在内存中连续存储，通过下标来访问元素	一种特殊的二维数组，通常用于表示具有行列结构的数据，如数学中的矩阵运算、图像数据等	是线性表的推广，它的元素可以是原子（不可再分的数据元素），也可以是广义表
数据元素特点	元素为字符类型	元素类型相同	元素类型相同，通常为数值类型或其他基本数据类型	元素可以是不同类型的数据，包括原子和子表
存储结构	通常采用顺序存储结构，也可以采用链式存储结构	一般采用顺序存储结构，便于随机访问元素	通常采用二维数组进行存储，也可以采用特殊的存储方式，如压缩存储（针对稀疏矩阵）	可以采用链式存储结构，每个节点包含数据域和指针域，指针域用于指向子表或下一个元素
操作特点	主要操作包括串的比较、查找、替换、连接等	可以通过下标随机访问元素，进行元素的读取、修改等操作	支持矩阵的加法、乘法、转置等运算，以及对矩阵元素的访问和修改	对广义表的操作包括取表头、取表尾、求表深度、遍历等

相关文章：