什么是数据结构
在编程程序时，往往会遇到数据的存储问题。在一般情况下，都会使用数组存储一系列数据，然而仅仅使用数组并不能有效地组织复杂的数据。考虑以下几个典型的应用场景：
在以分类表示数据时，一个类别可能包括众多子类别。如果仅以数组存储数据，那么类别之间就很难建立联系，如果需要按类别筛选数据，不便于查找子类别中的数据。
在地图中存储各个地点的信息时，地点间存在空间上的关联，而数组难以体现这种关联，不方便规划路径。
这些时候，就需要使用数据结构(data structure)。当数据量较小的时候，使用数据结构的优势并不明星；但当数据量开始变大时，数据结构的优势便体现出来。一个合适的数据结构可以在数据量很大时，将数据以规则的形式组织起来，使数据的管理更加方便高效。
抽象数据类型(Abstract Data Type, ADT)是在一个模型定义下的操作集合，操作效果只取决于特性，而与具体的数据类型无关。例如，对于数组 ADT ，它所具有的操作有获取索引值位置元素、修改索引值位置元素等，这个数组可以是整型数组、字符数组、结构数组或更复杂的嵌套数组等，但只要它是数组，就拥有这些操作或特性。
在后续研究的数据结构都属于 ADT ，因为往往需要使用不同的数据类型来适应不同的场合。例如在使用数组时，如果要处理一系列实验数据，可以使用浮点数数组，如果要处理一段文本，可以使用字符数组，只需要研究数组本身的特性，就可以将其应用到不同的场合中。
在第一节中，暂时只研究数组这种比较熟悉的数据结构，并分析其优缺点。这里研究的数组指的不仅仅是C语言中的数组，而是更广义的线性存储结构，一般称为线性表。
线性表
线性表的概念
线性表(linear list)是一组数据组成的有限序列，其中每个数据项含义相似。本节研究顺序存储结构的线性表，它常在内存中以一块地址连续的存储单元依次存储，非常类似C语言中数组的特征，因此可以使用C语言中的数组来表示线性表。
采用以下定义实现线性表：
在第一行中定义了 elemtype 类型，由于这里仅研究线性表 ADT ，因此不关心实际的数据项类型，它可以是任意有效的类型。C语言没有泛型，因此这里只能通过 typedef 用整型暂时模拟通用数据项类型。
由于C语言中数组的功能偏弱，因此除了使用数组存储数据外，为了方便后期处理表中的数据，线性表还需要实时记录以下 2 项信息：
- 线性表申请的存储容量
- 线性表的长度，也就是表中存储数据元素的个数
为了确保拥有合适的空间存储数据，线性表申请的存储容量应大于期望存储的数据长度。当达到最大存储容量时，应该不能再对线性表添加新元素。
这里采用结构的形式描述线性表，这是因为在程序中可能同时存在许多不同的线性表，使用结构易于批量生产线性表。
在结构内存储实际数据的字段 body 字段是一个指针。它的用途是：通过 malloc() 函数动态申请到足够的存储空间，然后将其作为一个数组使用。
因此，新创建一个顺序表的步骤为：
- 给
body指针申请足够的内存空间 - 给
length和size字段赋一个合适的初始值
相应的C语言实现如下：
线性表项操作
得到一个线性表后，就可以对线性表做一些操作。对线性表的操作主要是对线性表内的元素做一些改动。
首先是插入。线性表可以向任意位置插入元素，不过如果向中间位置插入元素，需要将线性表的后续元素整体后移，为插入的元素空出位置。下图展示了这种情况：
因此，线性表插入数据元素的代码实现如下：
在插入前，需要做两次判断：插入数据的位置是否合适，以及是否还有多余的空间让数据插入。
具体插入的方式为从最后一个元素开始，从后向前逐个将元素后移，直到将待插入位置的元素也后移了为止，这样便可以空出一个位置让数据插入。
与插入相反的操作是删除。删除某个位置的元素只需要将目标元素的后续元素整体前移即可，待删除元素便会被直接覆盖：
如果找到了相应的元素，它会返回该元素的索引值；如果没有找到相应的元素，则返回 -1 。
如果能成功查找到一个元素，凭借返回的索引值，就能轻松修改该元素的值。
算法分析
算法(algorithm)是对求解特定问题所做的一些步骤的描述。如果能够确认该步骤是有效的，那么就需要分析该算法的效率如何。例如，如果需要求解一个等差数列连续若干项的和，一种算法是逐个计算每项的值再累加，得到的结果也是正确的；也可以采取累加公式，直接由所给定的基本信息代入公式即可一步计算出结果，更加省时省力。
因此，对一个算法最主要的评估标准就是执行的时间资源和存储中间结果的额外空间资源。
算法的复杂度
一般来说，使用某种数据结构处理某个实际问题时，随着数据项的个数变多，算法的执行时间和占用的额外空间往往也会受到变化。例如，从一个简单的记事本中查找一段文本，和从一篇很长的小说中查找一段文本，两者消耗的时间也是不同的。如果搜索的文本重复率较高，那么需要的空间资源也会更多。
虽然不可能精确得知算法执行消耗的时间，也比较难计算占用内存的实际大小，但是可以从算法的某些特征中估算出算法的性能：当数据项个数变多时，算法消耗的资源呈什么增长率变化。
例如，如果需要查找线性表内的某个元素，由于它可能出现在线性表内的任意位置，需要遍历线性表。重新展示代码如下：
如果线性表内有 \\( n \\) 个元素，那么在最坏的情况下，算法需要做 \\( n \\) 次判断，然后才返回一个值。如果使用数学函数表示算法的性能，参数 \\( n \\) 表示数据结构内包含的元素个数，计算结果为每个基本操作执行的次数，那么随着数据结构内包含的元素个数增多，在最久的情况下，需要执行的操作次数为：
每增加一项数据，就需要判断其值是否满足要求，还需要 for 多循环一次。如果假定每个操作执行的时间差不多，那么只需要知道该函数对应关系，就可以估算出一定数据量下，算法执行的大致时间。
不过一般来说无需计算得这么详细，只需要知道算法执行时间的增长变化趋势即可，或者说算法中基本操作重复执行的次数与数据规模 \\( n \\) 呈什么函数关系变化。算法的时间度量记作：
大写字母 O 表示随数据规模 \\( n \\) 增大，算法执行时间的增长率主要由 \\( f(n) \\) 的增长率主导，称为算法的渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。
在以上查找算法中，随着数据规模增大，查找所消耗的时间也普遍呈线性规模增长，因此查找时间复杂度为：
只需关心函数是线性变化的，至于线性系数和低项都可以省略。
之所以时间复杂度只关心最高项，主要是为了对比各算法的执行效率。当 \\( n \\) 足够大的时候，消耗恒定时间的返回语句对算法的时间影响可以不计，而线性系数对时间的影响远不如更换算法对时间的影响大。
例如，以下是二分查找(binary search)算法的代码实现。二分查找算法的原理是如果数组是有序的，那么为了查找某一个值是否在数组内，只需将其与数组中间位置的元素做比较：如果数组中间位置的元素比待查找的值大，那么由于数组是有序的，数组后半部分的元素都比该值大，待查找的值不可能出现在这半部分中，那么只需再用这种方法在前半部分查找即可：
这种查找算法每一次判断都可以剔除剩余的一半查找范围，使待查找的范围呈指数级递减。运气最差的情况下，当查找 \\( log_2 n \\) 次左右便可以将搜索范围缩减到零，此时就可以判断值是否出现在数组中了。因此，该算法的时间复杂度为：
当 \\( n \\) 足够大时，根据极限的等价无穷小概念可知，该算法的执行时间是明显优于普通的查找算法的。可以通过绘制时间复杂度的函数图像比较两个算法的运行时间：
不过为了能够实现快速查找，二分搜索法要求数组必须是有序的。
接下来再看一个示例，选择排序(selection sort)是一种简单的排序算法，用于使数组内的每个元素从小到大排列。该算法的基本原理为：先找出数组的最小元素并移动到数组的起始位置，然后每次都从剩余未排序元素中查找最小元素并放到已排序序列的末尾，直到没有待排序元素为止。
选择排序的算法实现如下：
在这个算法中，for 循环内又嵌套了一层 for 循环。如果数据规模为 \\( n \\) ，那么外层循环一共执行 \\( n-1 \\) 次，内层循环的额执行次数也与 \\( n \\) 有关，总的执行时间是两者的乘积，即时间复杂度为：
显然，当 \\( n \\) 足够大的时候，它消耗的时间远比线性的时间复杂度多。因此选择排序效率较低，一般不用于排序很大的数据。选择排序的时间复杂度比普通的查找大，因此没有必要为了二分查找法的速度优势而特地为数组排序。
排序是算法的一个重要话题，后续会专门花费一节介绍排序算法，许多精彩的思想都可以有效降低排序的时间复杂度。
空间复杂度与时间复杂度类似，也可以使用类似的方法估计并对比算法花费的空间资源。不过只要不是太过夸张，一般对空间的需求并没有时间那么首要，并且大多数情况下空间复杂度都易于分析，因此较少研究算法的空间复杂度。
线性表的复杂度分析
使用顺序存储结构的线性表在其中某个位置插入或删除一个数据元素时，为了保证线性表的连续性，必须要移动表中的一系列元素。
如果插入或删除开头位置的元素，则整个线性表的元素都要发生移动；如果删除末尾位置的元素，则可以不用移动元素。假设插入和删除的位置是随机的，那么每次操作平均会移动约一半元素，也就是说操作的时间复杂度为 \\( O(n) \\) 。
使用顺序存储结构的线性表时，其优势在于获取表的长度和取确定位置的元素时间复杂度都为 \\( O(1) \\) ，也就是说不管线性表多长，要取哪一个位置的元素，都只需要常数级的时间。如果需要频繁地访问元素的话，使用线性表是不错的选择。
由于顺序存储结构的线性表在应对大量数据的增加或修改时表现并不是很好，表的一部分需要经常移来移去。下一节介绍链表，链表是一种非连续的存储，在插入和删除时表的整体或部分无需全部移动。