数据结构和算法（Data Structure And Algorithms）

alt

迷宫问题

需要解决的问题

输入
- 迷宫地图
- 入口与出口
输出
- 入口到出口的路径
输入如何转换为输出
- 在已知迷宫地图寻找入口到出口路径的方法（算法）

思考

迷宫地图
- 如何表示给定空间和可行的路径？
- 如何表示入口和出口？
寻路过程
- 当有多条可行的路径时，如何选择？
- 当某条路径在某一点再没有可行之路时如何处理？
- 某点重复经过吗（避免兜圈子）？

思路

二维数组maze[m+2][n+2]来表示迷宫，解决迷宫地图的存储
一维数组DeltaXY[8]来记录8个探索方向的坐标增量，将8个探索方向数字化为0到7，并将向下一点前进的操作统一为当前的坐标+沿该探索方向的增量，即可得到下一点的坐标
当某点无路可通行时，需要从该点返回到前一点，再从前一点选择下一个方向继续探索，即需要知道前一点和前一点当前探索的方向，因此，我们需要保留依次到大的各点的坐标和到达该店的方向
为了防止重复到达某点，避免在迷宫中兜圈子，需要记录已到达过的点

小结

数据结构两大用途

用于存放要处理的数据，如迷宫地图
用于实现算法策略，如迷宫例子中探索方向增量数组、回溯的栈、避免重复走的标志数组或特殊标记

绪论

结论一

==杂乱的数据不能表达和交流信息==

结论二-电话号码查询

==数据之间是有联系的，这些联系常常影响算法的选择和效率，数据结构与算法就是要研究数据之间的联系及选择与设计高效率的算法==

结论三-人事管理系统

==数据之间是有结构的==，常见的有线性结构、树状结构（上下级关系，一对多）、图状结构（朋友关系，多对多且无向，相互的关系）

结论四-图书目录管理-增删改查

==在某种数据结构上可定义一组运算，《DS》就是要研究各类数据结构上的各种运算（算法）==

常见的数据结构

==数组、栈、队列、表、串、树、图和文件==

《数据结构与算法》主要研究内容

计算机要处理的数据本身
数据的各种逻辑关系（逻辑结构）和存储表示（物理结构）以及他们之间的相应关系
对每种结构定义相适应的各种运算
设计出相应的算法，分析算法效率
分析算法的效率

数据结构-相关术语

1. 数据（data）

所有能被计算机识别的符号集合，所谓的识别包括输入、输出、存储、处理、显示，而所谓的符号包括数字、字母、汉字、语音、图形、图像等。

2. 数据元素（Data Element）

是数据（集合）中的一个“个体”
是数据结构中讨论的基本单位

3. 数据项（Data Item）

是数据结构中讨论的最小单位，数据元素可以是一个或多个数据项的集合，比如

alt

4. 数据对象（Data Object）

数据对象是具有相同性质的数据元素的集合，是数据的一个子集，例如迷宫数据对象中的数据元素是一个个的点；电话簿数据对象中的数据元素是每个人的记录；图书目录数据对象中数据元素是一张张数目卡片

alt

5. 数据结构

带结构(描述数据元素之间的运算和运算规则)的数据元素的集合

用集合的形式描述，数据结构是一个二元组：

DS = （D，R）

其中：D是数据元素的集合，R是D上关系的集合

所以有时候，数据元素和其相互关系称为数据结构，但这个不太全面，所以有以下四元组表示

Data_Structure = (D，L，S，O)

其中：

D（Data）是数据元素的有限集，是存储和操作的对象；
L（Logic Structure）是数据元素集合D中数据元素之间客观存在的关系的有限集，称为逻辑结构；
S（Storage Structure）是数据元素集合D和数据元素之间的关系集合L在计算机当中的存储表示，称为存储结构或者物理结构；
O（Operation）是在数据元素集合D上规定的一组操作；

简而言之，数据结构包含了数据元素、数据元素之间的逻辑关系、逻辑关系在计算机的存储表示以及所规定的操作这四部分。

6. 逻辑结构(Logic Structure)

归结为以下四类

线性结构：表示数据元素之间存在着一对一的关系，可以用线性序列表示
树形结构：表示数据元素之间存在着一对多的关系
图形结构（网状结构）：数据元素之间存在着多对多的关系
集合结构：数据元素的关系是属于同一个集合，集合结构是数据元素之间关系极为松散的结构

==树形结构和图形结构称为非线性结构==

7. 存储结构（Storage Structure）

alt

顺序存储结构（随机存取结构）：把逻辑上相邻的元素存储在物理位置相邻的存储单元中，特点就是借助数据元素在存储器中的相对位置来表示书库元素之间的逻辑关系，通常用程序语言中的数组类型实现。
链式存储结构：在数据元素中添加一些地址域或辅助结构，用于存放数据元素之间的关系。特点就是借助数据元素中的指针表示数据元素之间的逻辑关系，通常用程序语言中的指针类型或索引结构实现。

alt

8. 数据结构的操作（Operation）

数据元素的查找、插入、删除、遍历和排序等基本操作

9. 数据类型（Data Type）

数据类型：是程序设计语言中用来刻画操作对象的特性的一个值的集合和定义在此集合上的一组操作的总称。

可以利用程序设计语言中的数据类型实现自己的数据结构，数据类型就是程序设计语言已经成型的数据结构。

10. 抽象数据类型（Abstract Data Type ，ADT）

ADT一般包含数据元素、数据元素之间的关系及操作三要素（D，R，O），其中

D是数据元素集
R是D上的关系集合
O是对D的基本操作集

ADT特点：

抽象性
扩展性

算法分析

算法是满足下述性质的指令序列

输入：有零个或者多个外部量作为算法的输入
输出：算法产生至少一个量作为输出
确定性：组成算法的每条指令清晰、无歧义
有限性：算法中的每条指令的执行次数有限，执行每条指令的时间也有限

人用计算机解决问题的步骤

问题的理解：清楚问题的输入、要求和输出；
数据结构设计：一方面要选择或设计能有效表示和存储应用问题中所涉及的数据对象的数据结构，同时还要选择或设计能支持算法策略实现的数据结构；
算法设计：包括选择算法策略、用适当的方式描述和逐步细化算法步骤；
算法分析：发现有改进完善之处，返回第二步，重新选择或设计数据结构、重新设计算法；
程序实现：用程序设计语言定义数据结构、编写实现算法的代码，在计算机上调试和运行程序。

alt

优秀的算法的特性

正确性：正确性是对算法能否正确求解问题的评价，是首要和最基本的特性；
可读性：可读性是对算法描述的思路、层次的评价。好的算法应该是思路清晰、层次分明、阅读和修改容易；
健壮性：健壮性是对算法在异常情况下处理能力的评价。好的算法在出现异常或者非法数据、在操作不当时，都能作出适当处理；
高效性：算法的效率是对求解同样问题的不同算法所占用的时间或者空间的评价。好的算法应该是高效的，即求解问题所占存储空间少，执行时间少；

算法性能比较方法

编程后测试运行时间：运行时间比较算法效率是很难做到准确的，只能做定性分析；
编程前分析可能的运行时间

算法复杂性分析

算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性；
这个量应该只依赖于算法要解问题的规模、算法的输入和算法本身的函数；
如果分别用N、I、A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么应该有C=F(N,I,A);
一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)；
通常让A隐含在复杂性函数名当中；

复杂性函数F具体化

根据T(N,I)的概念，它应该是算法在一台抽象的计算机上运行所需要的时间：

设此抽象的计算机所提供的的元运算有k种，分别记作O1，O2，...Ok；
又设每次执行一次这些元运算的时间分别为t1,...tk;
对于算法A，设统计用到的元运算Oi的次数为ei，则

alt

一个算法花费的时间与算法中语句的执行次数成正比。一个算法中的语句执行次数（计算步）称为语句频度或时间频度，记作T(n)。
一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，因此算法的时间复杂度记作：T(n)=O(f(n));
分析：随着模块n的增大，算法执行的时间的增长率和f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。

渐进性分析

复杂性渐进性形态：

当N单调增加趋于∞时，T(N)也单调增加趋于∞；

如果存在T`(N)当N->∞时，有(T(N)-T`(N))/T(N)->0，那么称T`(N)是T(N)的渐进性形态；

直观上T`(N)是T(N)中省略去低阶项所留下来的主项，同阶无穷大的味道。

所以可以采用渐进复杂性分析代替详细数学分析来比较算法效率！

渐近分析的符号

渐近上界记号 Ο
渐近下界记号 Ω
紧渐近界记号 Θ

记号	含义	通俗理解
(1)Θ（西塔）	紧确界。	相当于"="
(2)O （大欧）	上界。	相当于"<="
(3)o（小欧）	非紧的上界。	相当于"<"
(4)Ω（大欧米伽）	下界。	相当于">="
(5)ω（小欧米伽）	非紧的下界。	相当于">"