1 数据结构的基本概念
1.1 数据结构的含义
数据结构和算法是程序设计最重要的两个内容。
简单的说，数据结构是数据的组织，存储和运算的总和。它是信息的一种组织方式，是以数据按某种组织关系起来的一批数据，其目的是为了提高算法的效率，然后用一定的存储方式存储到计算机中，并且它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。
在计算机处理的大量数据中，它们都是相互关联，彼此联系的。
数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作，因此，主要有三个方面的内容，数据的逻辑结构，数据的物理结构，对数据的（或算法），通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。
1.2 数据结构的基本术语
1. 数据（Data）
数据即信息的载体，是对客观事物的符号表示，指能输入到计算机中并被计算机程序处理的符号的总称。如整数，实数，字符，文字，声音，图形，图像等都是数据。
2. 数据元素（Data Element）
数据元素是数据的基本单位，它在计算机处理和程序设计中通常作为独立个体考的对象。数据元素一般由一个或多个数据项组成，一个数据元素包含多个数据项时，常称为记录，结点等。数据项也称为域，字段，属性，表目，顶点。
3. 数据对象（Data Object）
数据对象是具有相同特征的数据元素的集合，是数据的一个子集。
4. 数据结构（Data Structure）
数据结构简称 DS，是数据元素组织形式，或数据元素相互之间存在一种或多种特定关系的集合。任何数据都不是彼此孤立的，通常把相关联的数据按照一定的逻辑关系组织起来，按照计算机语言的语法，语义的规定相应的存储结构或形式，并且为这些数据指定一组去处操作，这样就形成了一个数据结构。
数据结构通常有四类基本形式：集合形式，线性结构，树型结构，图形结构或网状结构。
5. 数据的逻辑结构（Logical Structure）
是指数据结构中数据元素之间的逻辑关系，它是从具体问题中抽象出来的数学模型。是独立于计算机存储器的（与具体的计算机无关）。
6. 数据的存储结构（PhysicalStructure）
数据的存储结构是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。数据存储结构的实现要用计算机语言来实现，因而是依赖于具体的计算机语言。数据存储结构有顺序和链式两种不同的方式，诉特点是要数据元素在存储器的相对位置来体现数据元素相互间的逻辑关系。顺序存结构通常用高级编程语言中的 一维数组 来描述或实现。而链式存储结构则通常用链表来实现。
在有顺序存储结构的基础上，又可延伸变化出另外两种存储结构，即索引存储，和散列存储。
索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时查找效率，避免盲目查找。
散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查找时同样可以大大提高效率。
7. 数据类型（Data Type）
数据类型是一组具有相同性质的操作对象以及该组操作对象以及该组操作对象上的运算方法的集合。如整数类型，字符类型等。每一种数据类型都有自身特点的一组操作方法（即运算规则）。
8. 抽象数据类型（Abstract Data Type）
抽象数据类型是指一个数据模型以及在该模型上定义的一套运算规则的集合。在对抽象数据类型进行描述时，要考虑到完整性的广泛性，完整性就是要能体现所描述的抽象数据类型的全部特性，广泛性就是所定义的抽象数据类型适用的对象要广。在大型程序设计和系统软件开发中，对抽象数据类型用的较多。
1.2 算法评介
1.2.1 算法的定义及表示
1. 算法的定义
做任何事情都有一定的步骤，这些步骤都是有顺序的，而且缺一不可，所以广义地说，算法就是为解决问题而采取的步骤和方法，在程序设计中，算法是在有限步骤内求解某一问题所使用的一组定义明确的指令序列，通俗点说，就是计算机解题的过程。每条指令表示一个或多个操作。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法，前者是算法实现的逻辑推理，后者是算法实现的具体操作。
2. 算法的表示
为了表示一个算法，可以用多种不同的应运。常用的有自然语言，传统流程图，结构化流程图，N-S图，伪代码，计算机语言表示法等。
1.2.2 算法的特征及评价方法
1. 算法的特征
（1）有穷性，一个算法必须保证在执行有限步骤后结束，而不是无限的。
（2）确定性，算法中每一条指令必须有明确的含义，而不能是含糊不清的有歧义。
（3）可行性，每一个操作步骤都必须在有限的时间内完成。
（4）输入，一个算法可以有多个输入，也可以没有输入。
（5）输出，一个算法可以有一个或多个输出，没有输出的算法是没有实际意义的。
2. 算法的评价（算法的设计要求）
（1）正确性，分为以下四个层次
a. 程序不含语法错误。
b. 程序对于随意的几组合法输入数据能够得出满足符合要求的结果。
c. 程序对于精心设计的典型合法数据输入能够得出符合要结果。
d. 程序对于所有合法的输入数据都能得出符合要的结果。
（2）易读性
一个好的算法往往是与他人共享的，晦涩难懂的算法既不易与人交流，也会造成修改调试的维护的极大困难。
（3）高效性
如同人们的交往，办事效率的人，人人都愿同他共事，算法也一样，运行时间越少，其效率越高，特别是在大型程序设计中，如果每个算法都具有高效性，那么对于缩短整个程序运行时间是非常有帮助的。算法的效率主要从时间复杂和空间复杂度两个方面来衡量。
（4）可维护性
一个好的算法应该对于后期维护保持较低的投入。
1.3 算法分析
算法分析主要是指分析算法的效率，算法效率的试题主要从两个方面，算法运行时间和算法所需的存储空间。
在算法分析中，算法整个运行过程所耗费的时间，称为算法的时候复杂度，算法整个运行过程所占用的空间称算法的空间复杂度。
1.3.1 算法的时间复杂度分析
1. 算法运算埋单的度量
度量算法执行时间通常有两种方法：
（1）事后统计的方法
因为很多计算机内部有计时功能，有的甚至可以精确到毫秒级，不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两个缺陷：一是必须先运行依据算法编制的程序，二是所得时间的统计量依赖于计算机硬件，软件等环境因素，因此人们常采用另一种事前分析估算方法。
（2）事前分析估算的方法
通过对算法中不同语句序列的分析，得出算法中所有语句执行次数的相对大小，从而判断算法的运行时间长短。这只是一个相对概念，不是绝对大小。
2. 算法运行时间的分析规则
影响程序运行时间的因素是多方面的，如机器的运行速度，编译程序产生的目标代码的质量，程序的输入等。通常把一个程序的运行时间定义一个 T(n)，其中 n 是该程序输入数据的规模，而不是某一个具体的输入。T(n) 的单位是不确定的，一般把它看起在一个特定计算机上执行的指令条数。
当讨论一个程序的运行时间 T(N) 时，注重的不是 T(n) 的具体值，而是它的增长率。 T(n) 的增长率与算法中数据的输入规模是紧密相关。而数据输入规模往往用算法中某个变量的函数来表示，通常用 f(n) 表示。随着数据输入规模的增大，f(n) 的增长率与 T(n) 的增长率相近，因此 T(n) 同 f(n) 在数量级上是一致的表示为 T(n) = O(f(n))。
一个程序运行时间的增长率将最终决定该程序在计算机上能解决多大规模的问题。
根据语句序列之间的逻辑关系，增长的统计可分为线型累加规则和几何累加规则两种。设 T1(n) = O(f(n)), T2(n)=O(g(n)) 则：
（1）用线性累加规则，设 T1(n) 和 T2(n) 是程序段 p1 和 p2 运行时间，则执行 p1 之后紧接着执行 p2 的运行时间 T1(n) + T2(n) 是：
T1(n) + T2(n) = O(max{f(n), g(n)})
（2）用几何累加规则是：
T1(n) . T2(n) = O(f(n) . g(n))
一般来说，分析程序的时间复杂度是逐步进行的，先求出程序中各语句和各模块的运行时间，再求整个程序的运行时间。一组语句的运行时间（它作为整个程序运行时间的一部分），可以表示成几个变量或输入数据的规模 n 的函数。整个程序的运行时间一般表示成惟一参数（输入数据的规模 n 的函数）。
在分析的过程中，我们会遇到各种语句和各种模块，具体分析大致有以下6种情形：
a. 每个赋值语句或读/与语句的运行时间通常是O(1)。但有些例外情况，如赋值语句右部表达式可能出现函数调用，这时就要考虑计算函数值所耗费的时间。
b. 顺序语句的运行时间由纯属规则确定，即为该序列中耗费时间最多的语句的运行时间。
c. 语句 if 的运行时间为条件语句测试时间（通常取O(1)）加上分支语句的运行时间，语句 if - else - if 的运行时间为条件测试时间加上分支语句的运行时间。
d. 循环语句的运行时间是 n 次重复执行循环体所耗费时间的总和，其中 n 是重复的次数。而每次重复循环终止条件和跳回循环开头所花费的时间，后一部分通过取 O(1) ，将常数因子忽略不计，通常认为上述时间是循环次数 n 和 m 的乘积，其中 m 是 n 次执行循环体当中时间耗费最多的那一次的运行时间，进而可以按几何累加规则计算这个乘积。
遇到多层循环时，要由内层向外层逐层分析，因此，当分析外层循环的运行时间时，内层循环的运行时间应该是已知的，这时可以把内层循环看成是外层循环的一部分。
e. 当算法运行次数无法确定时。
在上面的几种情况下，算法的运行次数是可以确定的，但在某些情形下，算法的运行次数可能是无法确定的，如在一给记录中查找某个关键字，查找过程是从第一个记录开始，有可能一次就找到，也可能最后一次才可能找到，还有可能根本找不到。
如果不能查找成功，当然它的运算次数是 n （n 是被查找的记录个数）。时间复杂度当然是 O(n)。如果能够查找成功，对于这一类算法就要求它的平均运算次数，用平均运算次数表示整个算法的运算次数。
平均值 = 总的运算次数 / 被运算的记录数
在查找和排序算法中，都可用此方法。
1.3.2 算法的空间复杂度分析
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。算法在计算机存储器内占用的存储空间主要分为三部分：算法源代码本身占用的存储空间，算法输入输出数据所占用的存储空间，算法运行过程中临时占用的存储空间。
算法输入输出数据所占用的存储空间是由算法所要解决问题的数据输入规模大小来决定的，它不随算法的不同而改变。
算法源代码本身所占用的存储空间与算法书写的长短成正比，要想缩小这部分空间就得编写简捷的算法源代码。
算法在运行过程中临时占用的存储空间则随算法不同而有所区别。有的算法占用的临时存储空间大，有的算法占用临时存储空间小，好的算法在程序运行过程中占用的临时存储空间不随数据输入规模的不同而不同。
在对一个算法进行时间复杂度和空间复杂度的分析时，往往二者不能兼顾，考虑好的时间复杂度，就得牺牲空间复杂度的性能，反之亦然。因此二者要从算法使用的频率，处理的数据的规模等多方面综合协调。