数据结构第一章概论

1.1 数据结构的定义和分类

1.1.1 数据结构的定义

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

数据结构是带有结构的数据元素的集合，数据元素之间的相互关系，即数据的组织形式。数据的组织方法与效率密切相关，采用不同数据的组织方法其处理效率也不同，对问题找出合适的数据组织方法十分重要。

1.1.2 数据结构包括的内容

（1）逻辑结构：数据元素之间的逻辑关系。
（2）存储结构：数据元素及其关系在计算机存储器内的表示。
（3）操作：数据的运算（检索、排序、插入、删除、修改）。

1.2 为什么学习数据结构

1.2.1 学习数据结构的作用

（1）计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。
（2）同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。
（3）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。

1.2.2 电话号码查询问题

（1）要写出好的查找算法，取决于这张表的结构及存储方式。
（2）电话号码表的结构和存储方式决定了查找（算法）的效率。

求解方法：
（1）顺序表法：数组存储，一次查找结构简单，但效率偏低。
（2）索引结构法：按姓氏索引定位，支持快速查找。

1.3 数据结构的基本概念

数据结构分为逻辑结构和存储结构：

逻辑结构定义了数据元素之间的逻辑关系。
存储结构是逻辑结构在计算机中的实现。

一种逻辑结构可以采用不同存储方式存放在计算机中，但都必须反映出要求的逻辑关系。

1.3.1 基本逻辑结构

（1）集合结构：结构中的数据元素之间除了同属于一个集合的关系外无任何其他关系。
（2）线性结构：结构中的数据元素之间存在着一对一的线性关系。
（3）层次结构：结构中的数据元素存在着一对多的层次关系。
（4）网状结构：结构中的数据元素存在着多对多的任意关系。

1.3.2 基本存储结构

存储结构（又称物理结构），数据元素之间关系在计算机中的表示方法：
（1）顺序结构：一组连续单元（顺序存储结构，如数组）
（2）非顺序结构：一组任意存储单元（非顺序存储结构，如链表）

1.4 算法

1.4.1 算法的概念和特点

算法是由若干条指令组成的有穷序列，是为解决特定问题而规定的有限集合。

算法具有以下的特点：

输入：具有0个或多个输入的外界量。
输出：至少产生1个输出。
有穷性：每一条指令的执行次数必须是有限的。
确定性：每条指令的含义都必须明确，无二义性。
可行性：每条指令的执行时间都是有限的。

1.4.2 算法的定义

1.4.2.1 正确性

算法的正确性具有以下三个层次：

所设计的程序对于几组输入数据能够得出满足要求的结果。
所涉及的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。
程序对于一切合法的输入数据都能产生满足要求的结果。

1.4.2.2 可读性

一个好的算法首先应该便于人们理解和相互交流，其次才是机器可执行。可读性好的算法有助于人们对算法的理解，难懂的算法易于隐藏错误且难于调试和修改。

1.4.2.3 健壮性

即对非法输入的抵抗能力。它强调即使输入非法数据，算法应能加以识别并作出处理，而不是产生误动作或陷入瘫痪。

1.4.2.4 高效率和低存储量

算法的效率通常是指算法的执行时间。对于一个具体的问题的解决通常可以有多给算法，对于执行时间短的算法其效率就高。

所谓的存储量要求，是指算法在执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

1.4.3 算法与程序的区别

（1）一个程序不一定满足有穷性，但算法一定。
（2）程序中的指令必须是机器可执行的，而算法无此限制。
（3）一个算法若用机器可执行的语言来描述，则它就是一个程序。

1.5 算法描述

算法描述采用类语言，类语言接近于高级语言而又不失严格的高级语言。它具有高级语言一般的语句格式，撇掉语言中的细节，把注意力主要集中在算法处理步骤本身的描述上。

算法描述的要点如下：

加上必要的注释（注明功能和参数）
避免函数返回值隐含说明（全程量隐接口）
预定义常量和类型
使用有意义的函数名与变量名
避免可能出现的二义性表达
规范多分支转向
简化输入、输出描述
注意不同的退出语句区别

1.6 算法分析

算法评价的标准主要是其执行占用机器资源在执行时间和存储空间上的表现。

1.6.1 时间复杂度

算法的执行时间 = 其所有语句执行时间的总和。

语句的执行时间 = 该条语句的执行次数 * 执行一次所需时间。

语句频度：指该语句在一个算法中重复执行的次数。

时间复杂度是以语句频度刻画随问题规模 n 增加的函数 f(n) 执行时间度量，记作 $T(n)=O(f(n))$ 。

常见函数的时间复杂度按数量递增排列及增长率：

常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(n log2n)
平方阶O(n2)
立方阶O(n3)
……
k次方阶O(nk)
指数阶O(2n)

例如分析以下 x=x+1 语句的时间复杂度：

（1）时间复杂度为 $O(1)$ ，称为常数阶。

x=x+1;

（2）时间复杂度为 $O(n)$ ，称为线性阶。

1
2
3

for(i=1; i<=n; i++){
    x=x+1; 
}

（2）时间复杂度为 $O(n^2)$ ，称为平方阶。

for(i=1; i<=n; i++){
    for(j=1; j<=n; j++){
        x=x+1; 
    }
}

1.6.2 空间复杂度

空间复杂度是指算法在计算机内执行时所需存储空间的度量，以存储单元个数刻画随问题规模增加的函数 f(n) 存储空间量度，记作： $S(n) = O(f(n))$ 。

1.6.3 算法分析的目的

目的在于选择合适算法和改进算法。

1.7 例题

1.7.1 例1

for (i=1; i < n; i++ ) {      
    y = y+1;  //语句1
    for (j=0; j <= (2*n); j++ )
        x++;  //语句2 
}

解：

语句1频度为 (n-1)；语句 2 频度为 $(n-1) \ast (2n+1)=2n^2-n-1$ ，因此时间复杂度 $T(n)=O(n^2)$ 。

1.7.2 例2

i=1;  //语句1
while(i<=n) {
    i=i*2;  //语句2
}

解：

语句1频度为1；设语句2频度为 $f(n)$ ，则有 $2f(n)<=n$ ，即 $f(n) <= log2n$ ，去极大值， $f(n) = \log_2n$ ，因此时间复杂度 $T(n)=1 + \log_2n= O(\log_2n)$ 。

数据结构 第一章 概论