---

软考2.0

考点

一 基本概念与三要素 二算法 三线性表 四栈和队列 五 串、数组、矩阵和广义表 六、树和二叉树 七、图 八、查找 九、排序

1、基本概念与三要素

数据结构在学什么？

如何用程序代码将现实世界的问题信息化

如何用计算机高效地处理这些信息从而创造价值

人类社会三次浪潮 第一次浪潮 农业阶段 第二次浪潮 工业阶段 第三次浪潮 信息化阶段

什么是数据？

数据是信息的载体 是描述客观事物属性的数、字符及所有能输入到计算机中并被程序识别和处理的符号的集合。 数据是计算机程序加工的原料。

1.1、基本概念 数据元素、数据项

数据元素是数据的基本单位 一个数据元素可由若干数据项组成 数据项是构成数据元素的不可分割的最小单位

1.2、数据结构三要素

数据结构是相互之间存在一种或多种特定关系的数据元素的集合

数据结构的三要素 逻辑结构 物理结构（存储结构） 数据运算

1.3、逻辑结构

逻辑结构包含 集合 线性结构 树形结构 图形结构

集合 各个元素同属一个集合 别无其他关系

线性结构 数据元素之间是一对一的关系 除了第一个元素 所有元素都有唯一前驱 除了最后一个元素 所有元素都有唯一后继

树形结构 数据元素之间是一对多的关系

图结构 数据元素之间是多对多的关系

1.4 、物理结构

物理结构包含

• 顺序存储 将逻辑上相邻的元素存储在物理位置上也相邻的存储单元
• 链式存储 逻辑上相邻的元素 物理位置上可以不相邻
• 索引存储 存储元素信息的同时 还建立附加的索引表
• 散列存储 根据元素的关键字直接计算出该元素的存储地址 又称哈希存储

2、算法

程序 = 数据结构 + 算法

数据结构 如何把现实世界的问题信息化 将信息存进计算机 实现对数据结构的基本操作

算法 如何处理这些信息 解决实际问题。

比如 海底捞排队

系统的数据结构 队列 （先进先出）

要实现的基本操作

1 队头元素出队

2 新元素入队

3 输出队列长度

4 交换第i号和 第 j号位置

现实问题 设计算法 带小孩顾客优先就餐 执行操作 2取号 对比前一桌信息 如果前一桌没有小孩 使用操作4交换位置

2.1、算法五个特性

有穷性 一个算法必须总在执行有穷步之后结束 且每一步都可在有穷时间内完成

确定性 算法中每条指令必须有确切的含义 对于相同的输入只能得到相同的输出

可行性 算法中描述的操作可以通过已经实现的基本运算执行有限次来实现

输入 一个算法有零个或多个输入 这些输入取自于某个特定的对象的集合

输出 一个算法有一个或多个输出 这些输出是与输入有某种特定关系的量

2.2、算法效率的度量

时间复杂度 时间开销与问题规模n之间的关系

空间复杂度 空间开销 内存开销 与问题规模n之间的关系

T1n = 3n + 3 ==> T1n = O(n)

T2n = n^2 + 3n + 900 ==> T2n = O(n^2)

T3n = n^3 + n^2 + 900 ==> T3n = O(n^3) 计算复杂度可以省略系数和常数

空间复杂度

无论问题规模怎么变 算法运行内存空间都是固定常量

算法空间复杂度 S(n) = O(1)

只关注存储空间大小与问题规模相关的变量

函数递归调用带来的内存开销

空间复杂度 等于递归调用的深度

O(1) < O(log2n) <O(n) < O(nlog2n) < O(n^2) <O(n^3) <O(2^n)<O(n!)<O(nn)

3、线性表

线性表包含 逻辑结构 存储结构[ 顺序表 顺序存储 链表 链式存储 （双向链表 循环链表 静态链表）] 插入删除操作

线性表定义

线性表是具有相同数据类型的n个数据元素的有限序列 其中 n为表长 当 n = 0时线性表是一个空表 若用 L 命名线性表

则一版表示为 L = （a1,a2,a3,…,ai,ai+1,…an）

a1是表头元素 an是表尾元素

顺序表

除第一个元素外 每个元素有且仅有一个直接前驱 除最后一个元素外 有且只有一个直接后继 n 等于0时 线性表为空表

链表

单链表 循环链表 双向链表

性能	项目	顺序存储	链式存储
空间性能	存储密度	=1	< 1
	容量分配	事先确定	动态改变 更优
时间性能	查找运算	O(n/2)	O(n/2)
	读运算	O(1)	O([n+1]/2) 最好情况1 最坏情况n
	插入运算	O(n/2) 最好0 最坏n	O(1)
	删除运算	O([n-1]/2)	O(1)

线性表的插入删除操作

顺序存储

插入元素前要移动元素挪出空的存储单元 然后再插入元素。删除元素时同样需要移动元素 填充被删除元素的存储单元

链式存储

​ 通过使用指针来链接分散存储在内存中的元素，每个元素（节点）不仅包含数据部分，还包含指向下一个节点的引用（或指针）。这样：

​ 插入操作：只需要调整相关节点的指针即可完成插入，不需要移动其他元素。具体来说，找到插入位置的前一个节点，改变其指针指向

新节点，并让新节点指向原位置的下一个节点。这种操作通常具有O(1)的时间复杂度（仅考虑指针调整时间），前提是已经定位到插入位

置。

​ 删除操作：只需更改待删除节点前后节点的指针连接关系，使其绕过待删除节点。这也是一种快速操作，时间复杂度一般为O(1)，不包

括查找待删除节点所需的时间。
总的来说，在链式存储中进行插入和删除操作比在顺序存储中更高效，因为它们避免了大量元素的移动。但是，链式存储可能会消耗更

多的内存用于指针存储，并且访问链表中的元素时不如数组那样直接有效。