考研笔记-计算机之数据结构:基础概览

逻辑：数据⊃数据对象∋数据元素∋数据项。

物理：结点∋ 数据域。

数据结构（逻辑）：集合、线性结构（表）、层次结构（树）、网状结构（图）；

存储结构（物理）：顺序存储结构（数组）、链式存储结构（链表）（数组和链表均是使用指针实现的）。

数据结构≔ 数据（数据元素的有限集）+结构（数据关系的有限集）。

数据类型≔ 值的集合+ 一组操作。

数据类型 =原子类型 +结构类型（原子类型也可看作特殊的结构类型）。

原子类型≔ 原子结构+ 一组操作。

结构类型≔ 数据结构+ 一组操作。

抽象数据类型≔ 数据类型的数学抽象。

抽象数据类型 =原子类型（固有数据类型）+ 结构类型（固定聚合类型+ 可变聚合类型）+ 多形数据类型。

抽象数据类型≔ 数据结构（数据对象+ 关系集）+ 基本操作。

ADT 抽象数据类型名{

数据对象；

数据关系：有序对<,>；

基本操作；

}ADT抽象数据类型名

递归函数

递归函数：一个直接调用自己或通过一系列的调用语句间接调用自己的函数，称为递归函数。

和第二数学归纳法类似，递归定义由基本项和归纳项两部分组成。

基本项：递归定义的基本项描述了一个或几个递归过程的终结状态。所谓终结状态是指不需要继续递归而可直接求解的状态。

归纳项：递归定义的归纳项描述了如何实现从当前状态到终结状态的转化。

递归设计的实质：当一个复杂的问题可以分解成若干子问题来处理时，其中某些子问题与原问题有相同的特征属性，则可利用和原问题相同的分析处理方法；反之，这些子问题解决了，原问题也就迎刃而解了。递归定义的归纳项就是描述这种原问题和子问题之间的转化关系。

设计递归函数时应注意的问题：由于递归函数的设计用的是归纳思维的方法，则在设计递归函数时应注意：①首先应书写函数的首部和规格说明，严格定义函数的功能和接口（递归调用的界面），对求解函数中所得的和原问题性质相同的子问题，只要接口一致，便可进行递归调用；②对函数中的每一个递归调用都看成只是一个简单的操作，只要接口一致，必能实现规格说明中定义的功能，切忌想得太远太深。正如用第二数学归纳法证明命题时，由归纳假设进行归纳证明时决不能怀疑归纳假设是否正确。

递归函数的定义中必有两个函数的退出（递归返回）点：①最内（底）层递归调用的返回点，即满足基本项成立条件；②中间层（除最内层）递归调用的返回点，即实现归纳项转换关系。

递归算法和非递归算法的转化

在实现同样功能的前提下，任何递归算法都可借助栈转为非递归算法，但不是所有的非递归算法都可转为递归算法。