章节结构
- 什么是数据结构
- 基本概念和术语
- 结构的分类
- 数据结构的形式定义
- 逻辑结构
- 物理结构（又称为存储结构）
- 数据元素在计算机中的表示
- 数据元素之间的关系在计算机中的表示
- 抽象数据类型的表示与实现
- 算法和算法分析
- 算法
- 算法设计的要求
- 算法效率的度量
- 算法的存储空间需求
什么是数据结构
用计算机解决一个具体问题时，大致需要经过下列几个步骤：
-
首先要从具体问题抽象出一个适当的数学模型，
-
然后设计一个解此数据模型的算法
-
编出程序，
-
进行测试、调整直至得到最终解答。
寻求数学模型的实质是分析问题，
- 从中提取操作的对象，
- 并找出这些操作对象之间含有的关系，
- 然后用数学的语言加以描述
基本概念和术语
数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素：数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。（比如C语言中的基本数据类型）
数据项：数据的不可分割的最小单位。一个数据元素可以由若干个数据项组成。
如，一本书的书目信息是一个数据元素，书目信息中的每一项（如书名、作者名等）为一个数据项。
数据对象：性质相同的数据元素的集合。是数据的一个子集
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
结构：数据元素相互之间的关系
结构的分类
根据数据元素之间关系的不同特性，通常有下列4类基本结构：
- （1）集合 ：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系
- （2）线性结构：结构中的数据元素之间存在一对一的关系
- （3）树形结构：结构中的数据元素之间存在一对多的关系
- （4）图状结构或网状结构：结构中的数据元素之间存在多对多的关系
由于“集合”是数据元素之间关系极为松散的一种结构，因此也可用其他结构来表示它
数据结构的形式定义
数据结构是一个二元组：
Data_Structure = (D,S)
D是数据元素的有限集
S 是D上关系的有限集
逻辑结构
对操作对象的数学描述就是在对数据结构的定义，数学形式上的数据结构定义，就是从操作对象抽象出来的数学模型。
这种离散数学形式的结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。
（这里要注意的是谈论数据结构是为了在计算机中实现对它的操作，因此还需研究如何在计算机中表示它）
物理结构（又称存储结构）
数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称为存储结构。
它包含数据元素的表示和关系的表示。
数据元素在计算机中的表示
（1）在计算机中表示信息的最小单位是二进制数的一位，叫做位（bit）
（2）数据元素在计算机中的表示：在计算机中用一个由若干位组合起来形成的一个位串表示一个数据元素
如用一个字长的位串表示一个整数，用8位二进制数表示一个字符等）
（3）这个位串又称为元素或结点。
（4）数据域：当数据元素由若干数据项时，位串中对应于各个数据项的子位串称为数据域
（5）元素（或称为结点）可看成是数据元素在计算机中的映像。
数据元素之间的关系在计算机中
数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。
并因此得到两种不同的存储结构：顺序存储结构和链式存储结构
顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系
数据的逻辑结构和物理结构之间的关系
任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。
如何描述存储结构
存储结构涉及数据元素及其关系在存储器中的物理位置。本书是在高级程序语言的层次上讨论数据结构的操作，因此不能直接以内存地址来描述存储结构，但可以借用高级程序语言中提供的“数据类型”来描述。
- 顺序存储结构：在所有高级程序语言中都有的“一维数组”类型来描述
- 链式存储结构：在C语言提供的“指针”来描述链式存储结构。
数据类型的概念
数据类型是一个值的集合和定义在这个值集上的一组操作的总称，用来刻画（程序）操作对象的特性。
- 在用高级程序语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。
- C语言中的整型变量，其值集为某个区间上的整数（区间大小依赖于不同的机器），定义在其上的操作为加、减、乘、除和取模等算是运算。
数据类型的分类
按“值”的不同特性，高级程序语言中的数据类型可为两类：
- 非结构的原子类型
属于原子类型的变量的值是不可分解的
C语言中的基本类型（整型、实型、字符型和枚举类型）、指针类型、空类型
- 结构类型
结构类型的值是由若干成分按某种结构组成，因此是可以分解的。其成分可以是非结构的，也可以是结构的。
在C语言中基本类型：整型、实型、字符型、枚举型、指针类型、空类型
数据结构VS结构类型
在某种意义上，
- (1)数据结构可以看成是一组具有相同结构的值
- (2)结构类型可以看成由一种数据结构和定义在其上的一组操作组成
抽象数据类型
抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。
抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关， 即无论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。
抽象数据类型VS数据类型
-
抽象数据类型和数据类型实质上是一个概念。各个计算机都拥有“整数”类型是一个抽象数据类型，尽管它们在不同处理器上实现的方法可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。
-
抽象数据类型的范畴更广，它不再局限于前述各处理器中已定义并实现的数据类型（也可以称这类数据类型为固有数据类型），还包括用户在设计软件系统时自己定义的数据类型。
一个含抽象数据类型的软件模块
一个含抽象类型的软件模块通常应包含3个部分：定义、表示、实现
抽象数据类型的定义
抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。
抽象数据类型的分类
按值的不同特性，可分为3种类型
-
原子类型，属于该类型的变量，其值不可分解的
-
固定聚合类型，属于该类型的变量，其值由确定数目的成分按某种结构组成
-
可变聚合类型，和固定聚合类型相比较，构成可变聚合类型“值”的成分的数目不确定
其中固定聚合类型和可变聚合类型统称为结构类型
抽象数据类型的表示
- 抽象数据类型可以用三元组表示(数学)
(D,S,P)
其中，D 是数据对象，S 是D 上的关系集，P 是对D的基本操作集。
- 这本书采用以下格式定义抽象数据类型（计算机）
ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT抽象数据类型名
数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：
基本操作名<参数表>
初始条件：<初始条件描述>
操作结果：<操作结果描述>
说明：
- （1）基本操作有两种参数：赋值参数和引用参数
- 赋值参数只为操作提供输入值；
- 引用参数以&打头，除可提供输入值外，还将返回操作结果。
- （2）初始条件：描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息
- (3)操作结果：说明了操作正常完成之后，数据结构的变换状况和应返回的结果。若初始条件为空，则省略之。
抽象数据类型三元组定义：
伪代码
基本操作：初始化、销毁、查、改、排序、最值、增加
ADT Triplet{
数据对象：D={e1,e2,e3|e1,e2,e3 ElemSet(定义了关系运算的某个集合)}
数据关系：R1={<e1,e2>,<e2,e3>}
基本操作：
InitTripleet(&T,v1,v2,v3)
操作结果：构造了三元组T，元素e1,e2和e3分别被赋以参数v1，v2和v3的值
DestroyTriplet(&T)
操作结果：三元组T被销毁
Get(T,i,&e)
初始条件：三元组已存在，1<= i <= 3
操作结果：用e返回T的第i元的值
Put(&T,i,e)
初始条件：三元组已存在，1<= i <= 3
操作结果：改变T的第i元的值为e
IsAscending(T)
初始条件：三元组T已存在
操作结果：如果T的3个元素按升序排列，则返回1，否则返回0
IsDescending(T)
初始条件：三元组T已存在
操作结果：如果T的3个元素按降序排列，则返回1，否则返回0
Max(T,&e)
初始条件：三元组T已存在
操作结果：用e返回T的诸多元素中的最大值
Min(T,&e)
初始条件：三元组T已存在
操作结果：用e返回T的诸多元素中的最小值
}ADT Triplet
多形数据类型
多形数据类型是指其值的成分不确定的数据类型。
多型数据类型是指包含的数据元素的类型并不确定。 比如栈可以是整数栈、字符栈、对象栈等等。 但是字符串，它的元素必然是字符。
多形数据类型的特点：其值的成分不确定，但只要能进行关系运算即可，无论其元素具有何种特性，元素之间的关系相同，基本操作也相同。
从抽象数据类型的角度来看，具有相同的抽象特性，因此称之为多形数据类型。
抽象数据类型的表示与实现
抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明心的结构，用已经实现的操作来组合新的操作。
算法和算法分析
算法
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一个指令表示一个或多个操作；
算法的重要特性（5种）
- （1）有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，切每一步都可在有穷时间内完成。
- （2）确定性：一个算法每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
- （3）可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
- （4）输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
- （5）输出一个算法有一个或多个的输出，这些输出是同输入有着特定关系的量。
算法设计的要求
一个“好”的算法应达到以下目标
- （1）正确性： 算法应该满足具体问题的需求
- （2）可读性：算法主要是为了人的阅读与交流，其次才是机器执行
- （3）健壮性：当输入数据非法时，算法也能适当的做出反应或进行处理，而不会产生莫名其妙的输出结果。
- （4）效率与低存储量需求：
- 通俗的说，效率就是算法执行的时间
- 存储量需求指的是算法执行过程中所需要的最大存储空间
算法效率的度量
度量一个程序的执行时间通常有两种方法
- 事后统计的方法
- 事前分析估算的方法
一个用高级程序语言编写的程序在计算机上运行时，所消耗的时间取决于下列因素：
- (1)依据的算法选用何种策略
- (2)问题的规模
- (3)书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越底
- (4)编译程序所产生的机器代码的质量
- (5)机器执行指令的速度
一个算法是由控制结构(顺序、分支和循环3这种)和原操作(指固有数据类型的操作)构成的，因此算法时间取决于两者的综合效果。
为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重发执行的次数作为算法的时间量度。
问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作
多数情况下，它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。
语句的频度：指的是该语句重复执行的次数。
一般频度的值为1、n、n的平方，则时间复杂度分别为O(1)、O(n)、O(n^2)，分别称为常量阶、线性阶、平方阶。
算法还可能呈现的时间复杂度有对数阶O(log n)、指数阶O(2^n)等。
尽可能选用多项式阶O(n^k)**的算法，而不选用指数阶的算法
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作 T(n) = O(f(n)) 塔表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作渐进时间复杂度，简称为时间复杂度。
如何找到影响算法的时间
算法的存储空间需求
空间复杂度作为算法所需存储空间的度量，记作S(n) = O(f(n))。
n是问题规模的大小
