第一章 绪论
《数据结构》主要研究内容：
1、数据的各种逻辑结构和物理结构，以及他们之间的相应关系
2、并对每种结构定义相适应的各种运算
3、设计出相应的算法
4、分析算法的效率
常见的数据结构有：数组、栈、队列、表、串、树、图、和文件等。
1.3 基本术语
数据（Data）： 所有能被计算机处理的符号的集合。
数据元素（Data Element）： 是数据这个集合中的一个个体。
设给定数据集合为：
D = {d1，d2，....， dn} 则di属于D，并称为di为数据元素。
数据项（Data Item）： 数据元素常常由若干个数据项组成，是数据的不可分割的最小单位。
数据对象（Data Object）： 具有相同性质的数据元素的集合。
数据结构（Data Structure）：是相互之间存在一种或多种特定关系的数据元素的集合。
形式定义为：数据结构是一个二元组 Data_Structure = （D，S）
其中：D是数据元素的有限集，S是D上关系的有限集。
逻辑结构（Logical Structure）：指数据元素之间的结构关系。
（任何一个算法的设计取决于选定的数据（逻辑）结构）
物理结构（Physical Structure）： 指数据结构在机内的表示（存储结构）。
（算法的实现依赖于采用的存储结构）
1.4 算法描述和算法分析
1、算法的概念：算法是一个有限的指令集，遵循指令流可以完成特定的功能。
2、算法的基本特性：
有穷性：操作步骤有穷，每个步骤的运行时间有穷；
确定性：下一步必须是明确的；
可行性：每一步是可执行的；
输入：零个或多个输入；
输出：一个或多个输出。
3、算法设计的要求：正确性、可读性、健壮性、高效率和低存储量需求。
4、算法与程序的区别：
算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
程序是用某种程序设计语言对算法的具体实现。
主要区别：有穷性、正确性和描述方法
程序可以是无穷的，例如OS，算法是有穷的；
程序可以是错误的，算法必须是正确的；
程序是用程序设计语言描述，在机器上可以执行； 算法还可以用框图、自然语言等方式描述。5、算法的度量方法：事后统计方法（不科学、不准确）、事前分析估算方法。6、函数的渐进增长：给定两个函数 f(n) 和 g(n), 如果存在一个整数N，使得对所有的 n > N， f(n) 总是比 g(n)， 那么，我们说 f(n) 的增长渐进快于 g(n)。
7、算法时间复杂度
在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数， 进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。
算法的时间复杂度，也就是算法的时间度量，记作： T(n) = O(f(n))。它表示随问题规模 n 的增大， 算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 f(n) 是问题规模 n的某个函数。（f(n) 是运行时间随 n 增大时的增长率 ）
这样用大写O() 来体现算法时间复杂度的记法，我们称之为大O记法。
8、算法空间复杂度：指空间需求。
9、推导大O阶
> 用常数1取代运行时间中的所有加法常数。
> 在修改后的运行次数函数中，只保留最高阶项。
> 如果最高阶项存在且不是1,则去除与这个项相乘的常数。
得到的结果就是大O阶。
常见的时间复杂度所耗时间的大小排列：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
