数据结构导论-基本概念

数据（data）/ 原始数据: 所有能被计算机处理的的集合
数据元素（Data Element）: 是数据这个集合中的一个个体，即数据的
数据项（Data Item）: 数据元素常常还可分为若干个数据项，数据项是数据具有意义的, 又称

数据结构

是计算机和的方式
是指一组相互之间存在一种或多种特定关系的数据和在计算机内的，以及定义在该组数据上的

计算机解决问题的步骤

建立数学模型 =》 设计算法 =》 编程实现算法

数据的逻辑结构

数据及数据的组织方式

数据结构、算法和程序的关系

算法+数据结构 = 程序
(1976年瑞士计算机科学家尼克劳斯维尔特提出)

数据结构的组成部分

1. 数据的逻辑结构
2. 数据的存储结构
3. 数据的基本运算

1. 数据的逻辑结构

逻辑结构： 指数据元素之间的结构关系,
与以下三种无关：数据元素的形式、数据元素的相对位置、所含结点个数

逻辑结构的分类

1. 集合： 数据元素同属于一个集合
   • 任意两个节点之间都没有邻接关系，组织形式松散
2. 线性结构： 即除起始节点和终端节点外，每个节点有一个前驱和一个后继
   • 结点逻辑关系依次排列形成一条链 结点之间一个一个依次相邻接
3. 树状结构： 构成树，即每个元素最多有一个前驱，可以有多个后继
   • 具有分支、层次特性，上层节点可以和下层多个节点想邻接，但下层结点只能和上层一个节点相邻接
4. 图状结构： 构成一个图
   • 最复杂、任何两个结点都可以相邻接

image.png

2. 数据的存储结构

物理结构/存储结构：指数据结构在计算机内的表示，数据的逻辑结构在计算机中实现

存储结构的主要部分：

1. 存储结点(每个存储结点上存放一个数据元素)
2. 数据元素之间关联方式的表示
3. 数据结构的存储= 数据元素的存储 + 元素逻辑关系的存储

image.png

顺序结构

顺序存储方式：借助数据元素的来表示数据的逻辑结构
线性表的顺序存储方法：将表中的节点一次存放在计算机内存中一组连续的存储单元中
顺序的方法：将元素存储到一片连续的存储区中

特点

• 预先分配好长度，需要预估存储数需要的存储量
• 插入和删除需要移动其他元素
• 存取快捷、是随机存取结构

链式结构

链式存储方式：借助数据元素地址的表述数据的逻辑结构
这种结构是给结点附加一个指针字段，指出其后继节点的位置，即存放结点的存储单元分为两部分： 数据项|指针项
特点
* 动态分配，不需要预先确定内存分配
* 插入和删除不需要移动其他元素
* 非随机存储结构

索引存储方式：借助索引表中的索引指示各存储结点的存储位置

散列存储方式：用散列函数指示各节点的存储位置

---

运算

指在某种逻辑结构上施加的操作，即对逻辑结构的加工
加工型运算：其操作改变原逻辑结构的值： 如：结点个数，结点内容等
引用型运算： 其操作不改变原逻辑结构的值

基本运算
建立、查找、读取、插入、删除

---

3. 算法及描述

算法：算法规定了求解给定类型问题所需的所有和,使给定类型问题能在$\color{有限时间}内被机械的求解

算法必须使用某种语言描述：

1. 程序
2. 介于自然语言和程序设计语言的伪代码
3. 非形式算法(自然语言)
4. 框图(N-S)

一个算法是对特定问题求解步骤的一种描述：它是指令的有穷序列

算法具有以下特性：

1. 有穷性 一个算法总是在执行有穷步后结束
2. 确定性 算法的每一步都必须是明确的定义的
3. 可行性：算法中的每一步都是可以通过已经实现的操作来完成
4. 输入：
5. 输出：

4. 算法分析

算法的设计应满足：
1. 正确性：对于合法的输入产生符合要求的输出
2. 易读性：算法应该易读、便于交流，这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法
3. 健壮性： 当输入非法数据时，算法还能做出适当的 反应而不会崩溃，如输出错误信息，算法中应该考虑适当的错误处理
4. 时空性：指算法的时间复杂度和空间复杂度、算法分析主要分析算法的时间复杂度和空间复杂度，目的是提高算法的效率

选择最优算法的两个度量

1. 时间复杂度： 算法运行时需要的总步数，通常是问题规模的函数
2. 空间复杂度： 算法执行时所占用的存储空间，通常是问题规模的函数

确定算法的计算量：

1. 合理地选择一种或几种操作作为 “标准操作”
2. 无特殊说明，默认以赋值语句作为标准操作
   确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量

4.1 时间复杂度

算法的最坏情况时间复杂度： 以算法在所有输入下的计算量的最大值作为算法的计算量
算法的平均情况时间复杂度：以算法在所有输入下的计算量的加权平均值作为算法的计算量
最坏情况的时间复杂度和平均情况时间复杂度统称为时间复杂度

将时间复杂度记为输入数据规模n的函数，若求解问题需要执行n^{2次操作，则记作O(n}2)

image.png image.png

4.2 空间复杂度

是对一个算法在运行过程中临时占用存储空间大小的量度

一个算法在执行期间所需要的存储空间量包括以下部分：

1. 程序代码所占用的空间
2. 输入数据所占用的空间
3. 辅助变量所占用的空间

估算算法空间复杂度时，一般只分析辅助变量所占用的空间