1. 绪论
1.1基本术语
-
数据：客观事物的符号表示，是所有能输入计算机中并被计算机程序处理的符号的总称。
-
数据元素：数据的基本单位。
-
数据项：组成数据元素的、有独立含义的、不可分割的最小单位。
数据>数据元素>数据项
-
数据对象：数据相同的数据元素的集合，是数据的一个子集。
1.2数据结构
指数据在计算机里的组织方式。
1.2.1逻辑结构
从逻辑关系上描述数据，它与数据的存储无关，是独立与计算机的。
关注元素之间的逻辑关系，决定数据如何组织关联。
集合结构：
数据元素之间除了“属于同一集合”的关系外，别无其它关系。
线性结构：
数据之间存在一对一的关系。
树结构：
数据之间存在一对多的关系。
图结构或网状结构：
数据之间存在多对多的关系。
1.2.3 存储结构
数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。
关注数据之间在计算机内存中的物理存放方式。
顺序存储结构：
数据在物理位置上是连续的。
是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。
链式存储结构：
数据在物理位置上不一定是连续的。
每个数据元素包含两部分：
-
数据本身的信息。
-
一个或多个指向其他数据元素的指针（或引用）
与顺序存储结构不同的是无需占用一整片存储空间。但为了表示节点间的关系，需要给每个节点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
1.3算法
是为了解决某些问题而规定的一个有限长的操作序列。
1.3.1特性
(1)有穷性
一个算法总是执行有穷步骤后结束，且每一步都必须在有穷时间内完成。
(2)确定性
对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，算法的执行者或阅读者都能明确其含义及如何执行。
(3)可行性
算法中的所有操作都可以通过将已经实现的基本操作运算执行有限次来实现。
(4)输入
一个算法有0个或多个输出。当用函数描述算法时，输入往往通过形参表示，他在被调用时通过主函数获取输入值。
(5)输出
一个算法有一个或多个输出，….，无输出的算法没有任何意义。用函数描述算法时，输出多用返回值或引用类型形参表示。
1.4评价算法优劣的基本标准
一个算法的优劣应该从以下几方面来评价。
(1)正确性:
在合理的数据输入下，好的算法能够在有限的运行时间内得到正确的结果。
(2)可读性：
一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且难于调试和修改。
(3)健壮性：
当输人的数据非法时，好的算法能适当地做出正确反应或行相应处理,而不会产生一一些莫名其妙的输出结果。
(4)高效性：
高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高,可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。
1.5时间复杂度
不考虑计算机软硬件等因素，影响算法时间代价的主要因素是问题规模。
一条语句重复执行次数称作语句频度。
最好时间复杂度
最坏时间复杂度
平均时间复杂度