实用指南：考研408--数据结构--day1

（以下内容全部出自上述课程）

目录

• 数据结构的研究内容
• 基本概念和术语
• • 1. 数据（Data）
  • 2. 数据元素（Data element）
  • 3. 数据项
  • 4. 信息对象（Data Object）
  • • 素材元素与数据对象
  • 5. 数据结构（Data Structure）
  • • 数据结构的两个层次
    • 5.1 逻辑结构的种类
    • • 5.1.1 划分方法一
      • 5.2.2 划分方式二
    • 5.2 存储结构
    • • 5.2.1 顺序存储结构
      • 5.2.2 链式存储结构
      • 5.2.3 索引存储结构
      • 5.2.4 散列存储结构
  • 6. 数据类型和抽象数据类型
  • • 6.1 数据类型（Data Type）
    • 6.2 抽象数据类型(Abstract Data Type,ADT)
    • • 6.2.1 抽象数据类型的形式定义
      • 6.2.2 基本操作定义格式说明
  • 小结
• 抽象数据类型的表示与搭建
• • 1. 抽象数据类型的实现
  • 2. 抽象数据类型如何完成
  • 3. 用C语言真正实现抽象数据类型的定义
• 算法和算法分析
• • 1. 算法
  • • 1.1 算法的定义
    • 1.2 算法的描述
    • 1.3 算法与程序
    • 1.4 算法特性
    • 1.5 算法设计的要求
  • 2. 算法分析
  • • 2.1 算法时间效率的度量
    • 2.2 事前分析方法
    • 2.3 算法时间复杂度的渐进表示法
    • 2.4 算法时间复杂度定义
    • 2.5 算法的渐进时间复杂度
    • 2.6 分析算法时间复杂度的主要方法
  • 3. 例题
  • 4. 算法时间复杂度
  • • 4.1 算法时间复杂度计算
    • 4.2 算法时间效率比较
    • 4.3 渐进空间复杂度
    • 4.4 算数空间复杂度分析例题
    • 4.5 设计好算法的过程

数据结构的研究内容

早期，计算机核心用于数值计算。

随着计算机应用领域的扩展，计算机被越来越多地用于非数值计算。

• 操作对象：每位学生的信息(学号、姓名、性别、籍贯、专业…)。
• 操作算法：查询、插入、修改、删除等
• 操控对象之间的关系：线性关系
• 数据结构：线性数据结构、线性表。

类似的还有图书管理系统、人事管理系统、仓库管理系统、通讯录…

• 操作对象：若干行材料记录
• 操作算法：查询、插入、修改、删除等
• 操控对象之间的关系：线性关系
• 数据结构：线性数据结构、线性表。

之所以能对弈：策略已经输入计算机，可以根据当前棋盘格局来预测棋局发展的趋势，甚至最后结局。
计算机的运行对象：各种棋局状态，即描述棋盘的格局信息
计算机的算法:走棋，即选择一种策略使棋局状态发生变化(由一个格局派生出另一个格局)
操作对象之间的关系：非线性关系、树

• 挑战：找到图中两点之间的最短路径或最经济路径。
• 操作对象：各地点及路的信息。
• 计算机算法：设置信号灯，求出各个可同时通行的路的集合
• 对象之间的关系：非线性关系、网状结构

基本概念和术语

1. 数据（Data）

是能输入计算机且能被计算机处理的各种符号的集合

• 信息的载体
• 是对客观事物符号化的表示
• 能够被计算机识别、存储和加工

包括：

• 数值型的数据：整数、实数等
• 非数值型的信息：文字、图像、图形、声音
  

2. 信息元素（Data element）

• 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理
• 也简称为元素，或称为记录、结点或顶点。
• 一个数据元素可由若干个数据项组成(Data ltem)
  

3. 数据项

• 构成数据元素的不可分割的最小单位。
  
• 数据、数据元素、数据项三者之间的关系：
  数据 >内容元素>数据项
  例：学生表>个人记录> 学号、姓名…

4. 内容对象（Data Object）

是性质相同的数据元素的集合内容的一个子集。就是，
例如:

• 整数据对象是集合N={0，1，±2，….}
• 字母字符内容对象是集合C={‘A’，'B’，…，‘Z’}
• 学籍表也可看作一个数据对象

材料元素与数据对象

• 数据元素–组成数据的根本单位
  与数据的关系：是集合的个体
• 数据对象–性质相同的数据元素的集合
  与数据的关系是：集合的子集

5. 数据结构（Data Structure）

• 数据元素不是孤立存在的，它们之间存在着某种关系，材料元素相互之间的关系称为结构（Structure）
• 是指相互之间存在一种或多种特定关系的数据元素集合
• 或者说，数据结构是带结构的数据元素的集合

数据结构包括以下三个方面的内容:

1. 内容元素之间的逻辑关系，也称为逻辑结构。
2. 资料元素及其关系在计算机内存中的表示(又称为映像)，称为素材的物理结构或数据的存储结构。
3. 数据的运算和实现，即对资料元素可以施加的操作以及这些操作在相应的存储结构上的实现。

数据结构的两个层次

• 逻辑结构
  描述数据元素之间的逻辑关系
  与数据的存储无关，独立于计算机
  是从具体问题抽象出来的数学模型
• 物理结构(存储结构)
  数据元素及其关系在计算机存储器中的结构(存储方式)
  是数据结构在计算机中的表示
• 逻辑结构与存储结构的关系
  存储结构是逻辑关系的映象与元素本身的映象。
  数据结构的达成就是逻辑结构是数据结构的抽象，存储结构
  两者综合起来建立了数据元素之间的结构关系。

5.1 逻辑结构的种类

5.1.1 划分技巧一

1. 线性结构
   有且仅有一个开始和一个终端结点，并自所有结点都最多只有一个直接前趋和一个直接后继。
   例如:线性表、栈、队列、串
2. 非线性结构
   一个结点可能有多个直接前趋和直接后继例如:树、图
   

5.2.2 划分方法二

1. 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
2. 线性结构：结构中的数据元素之间存在着一对一的线性关系。
3. 树形结构：结构中的数据元素之间存在着一对多的层次关系。
4. 图状结构或网状结构：结构中的内容元素之间存在着多对多的任意关系。
   

5.2 存储结构

四种基本的存储结构:

• 顺序存储结构
• 链式存储结构
• 索引存储结构
• 散列存储结构

5.2.1 顺序存储结构

• 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
• C语言中用数组来实现顺序存储结构
  例:（bat，cat，eat，…）
  

5.2.2 链式存储结构

• 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示C语言中用指针来实现链式存储结构
• C语言中用指针来实现链式存储结构
  例：(bat, cat, eat,…mat)
  
  

5.2.3 索引存储结构

• 在存储结点信息的同时，还建立附加的索引表。
• 索引表中每一项称为一个索引项（Index）
• 索引项的一般形式是:(关键字，地址)
• 关键字是能唯一标识一个结点的那些数据项。
• 若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引(Dense Index)。若一组结点在索引表中只对应一个索引项，则该索引表称之为稀疏索引(Sparse Index)
  

5.2.4 散列存储结构

根据结点的关键字直接计算出该结点的存储地址。

得到的散列表如下：

6. 数据类型和抽象数据类型

• 在使用高级程序设计语言编写程序时，必须对应用中出现的每个变量常量或表达式，明确说明它们所属的数据类型
• 例如，C语言中:
  供应int，char, float, double等基本数据类型数组、结构、共用体、枚举 等构造数据类型
  还有指针、空(void)类型
  用户也可用typedef自己定义数据类型
• 一些最基本数据结构可以用数据类型来实现，如数组、字符串等
• 而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。
• 高级语言中的数据类型明显地或隐含地规定了在程序执行期间变量和表达的所有可能的取值范围，以及在这些数值范围上所允许进行的操作。
  例如，C语言中定义变量i为int类型，就表示i是[-min,max]范围的整数，在这个整数集上可能进行+、-、*、\、%等操作。
  

6.1 数据类型（Data Type）

定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
数据类型=值的集合+值集合上的一组管理

6.2 抽象数据类型(Abstract Data Type,ADT)

是指一个数学模型以及定义在此数学模型上的一组运行。

• 由用户定义,从问题抽象出数据模型(逻辑结构)
• 还包括定义在数据模型上的一组抽象运算(相关操作)
• 不考虑计算机内的具体存储结构与运算的具体实现算法

6.2.1 抽象数据类型的形式定义

一个抽象数据类型的定义格式如下：

其中：
数据对象、内容关系的定义用伪代码描述
基本操作的定义格式为:

• 基本操作名(参数表)
• 初始条件:〈初始条件描述)
• 操作结果:〈操作结果描述)

6.2.2 基本操作定义格式说明

• 参数表：赋值参数 只为运行供应输入值。
  引用参数 以&打头，除可提供输入值外，还将返回管理结果。
• 初始条件: 描述操作执行之前数据结构和参数应满足的条件，若不满足，则处理失败，并返回相应出错信息。若初始条件为空，则省略之
• 操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果。

定义举例：

小结

抽象数据类型的表示与实现

一个疑问抽象为一个抽象数据类型后，仅是形式上的抽象定义，还没有达到问题解决的目的，要建立这个目标，就要把抽象的变成具体的，即抽象数据类型在计算机上建立，变为一个能用的具体的数据类型。

1. 抽象数据类型的实现

2. 抽象数据类型如何实现

• 抽象数据类型允许通过固有的数据类型(如整型、实型、字符型等)来表示和搭建。
  即利用处理器中已存在的数据类型来说明新的结构，用已经建立的操作来组合新的操作。

注:在本门课程的学习过程中，我们使用的类C语(介于伪码和C语言之间)作为描述工具。
但上机时要用具体语言建立,如C或C++等

3. 用C语言真正实现抽象数据类型的定义

• 例如：抽象数据类型“复数”的完成
  
  
  注：Complex是我们定义的一个结构体类型
  带*：指针变量，它是指向Complex类型的指针
  不带*：Complex类型的普通变量
  

算法和算法分析

1. 算法

1.1 算法的定义

• 对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。
  

1.2 算法的描述

• 自然语言：英语、中文
  
• 流程图：传统流程图、NS流程图
  
• 伪代码：类语言：类C语言
• 程序代码：C语言程序、JAVA语言程序

1.3 算法与软件

• 算法是解决问题的一种办法或一个过程，考虑如何将输入转换成输出一个问题能够有多种算法
• 程序是用某种程序设计语言对算法的具体构建。
  

1.4 算法特性

• 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内搞定。
• 确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
• 可行性：算法是可执行的，算法描述的操作可以通过已经构建的基本操作执行有限次来构建。
• 输入：一个算法有零个或多个输入。
• 输出：一个算法有一个或多个输出。

1.5 算法设计的要求

• 正确性
  
• 可读性
  
• 健壮性
  
• 高效性
  

2. 算法分析

对于同一个问题，可以有许多不同的算法。究竟如何来评价这些异法的优劣程度呢?
–算法分析
算法分析的目的是看算法实际是否可行，并在同一障碍存在多的算法时可进行性能上的比较，以便从中挑选出比较优的算法。

• 一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。
• 算法效率以下两个方面来考虑,

1. 时间效率:指的是算法所耗费的时间
2. 空间效率:指的是算法执行过程中所耗费的存储空间

• 矛盾的。就是时间效率和空间效率有时候

2.1 算法时间效率的度量

• 通过算法时间效率能够用依据该算法编制的脚本在计算机上执行所消耗的时间来度量。
• 两种度量方法
• • 事后统计
    将算法搭建其时间和空间开销
    缺点:编写程序完成算法将花费较多的时间和精力;所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣
• • 事前分析
    对算法所消耗资源的一种估算方法。

2.2 事前分析方法

• 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作(如赋值、比较、移动等)所需的时间与算法中进行的简单操作次数乘积

• 算法运行时间=一个简单执行所需的时间x简单操作次数
  
  每条语句执行一次所需的时间，一般是随机器而异的。取决于机器的指令性能、速度以及编译的代码质量。是由机器本身软硬件环境决定的它写算法无关。
  所以，我们可假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和了。
  这就可以独立于不同机器的软硬件环境来分析算法的时间性能了。

• 例如：两个n*n矩阵相乘的算法可描述为：
  

• 我们把算法所耗费的时间定义为该算法中每条语句的频度之和，则上述算法的时间消耗为：
  

2.3 算法时间复杂度的渐进表示法

• 为了便于比较不同算法的时间效率，大家仅比较它们的数量级
  
• 若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)5O(f(n),称O(f(n))为算法的渐进时间复杂度(0是数量级的符号)，简称时间复杂度。
  
  一般情况下，不必计算所有管理的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模n的某个函数，用T(n)表示。

2.4 算法时间复杂度定义

算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作: T(n)=O(f(n))
它表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度

2.5 算法的渐进时间复杂度

• 若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作:
  T(n)=O(f(n))

称O(f(n))为算法的渐进时间复杂度(0是数量级的符号)，简称时间复杂度。
一般情况下，不必计算所有执行的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模n的某个函数，用T(n)表示。

2.6 分析算法时间复杂度的基本方法

1. 找出语句频度最大的那条语句作为基本语句
2. 计算基本语句的频度得到问题规模 n的某个函数 f(n)
3. 取其数量级用符号“O”表示
   
   

3. 例题

4. 算法时间复杂度

4.1 算法时间复杂度计算

注意：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。

• 最坏时间复杂度:指在最坏情况下，算法的时间复杂度。

• 平均时间复杂度:指在所有可能输入实例在等概率出现的情况下，算法的期望运行时间。

• 最好时间复杂度:指在最好情况下，算法的时间复杂度。

• 一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

• 对于艰难的算法，行将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度
  

4.2 算法时间效率比较

• 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊
  
  时间复杂度T(n)按数量级递增顺序为：
  

4.3 渐进空间复杂度

• 空间复杂度:算法所需存储空间的度量，
  记作:S(n)=O(f(n)
  其中n为问题的规模(或大小)
• 算法要占据的空间
  算法本身要占据的空间，输入/输出，指令，常数，变量等
  算法要使用的辅助空间

4.4 算数空间复杂度分析例题

4.5 设计好算法的过程