全国计算机等级考试四级复习纲要：数据结构

　　数据对象是具有相同性质的数据元素的集合。通常，一个数据对象中的数据元素不是孤立的，而是彼此之间存在着一定的联系，这种联系就是数据结构。数据对象中数据元素之间的联系需要在对数据进行存储和加工中反映出来，因此，数据结构概念一般包括三方面的内容:数据之间的逻辑关系、数据在计算机中的存储方式、以及在这些数据上定义的运算的集合。

　　(1)数据的逻辑结构

　　数据的逻辑结构只抽象地反映数据元素之间的逻辑关系，它与数据的存储无关，是独立于计算机的。

　　数据的逻辑结构分为线性结构和非线性结构两大类，线性结构的逻辑特征是:有且仅有一个开始结点和一个终端结点，并且所有的结点都最多有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构。非线性结构的逻辑特征是:一个结点可能有多个直接前驱和直接后继。树、图等都是非线性结构。

　　2.算法

　　(1)算法及其特征

　　简单地说，一个算法就是一种解题方法，更严格地说，算法是由若干条指令组成的有穷序列，它必须具有以下特征:

　　①有穷性 一个算法必须在执行有穷步后结束。

　　②确定性 算法的每一步必须是确切地定义的，无二义性。

　　③可行性 算法中的所有待实现的运算必须在原则上能够由人使用笔和纸在做有穷次运算后完成。

　　④输入 一个算法具有0个或多个输入的外界量，它们是算法开始前对算法最初给出的量。

　　⑤输出 一个算法至少产生一个输出，它们是与输入有某种关系的量。

　　算法的含义与程序十分相似，但二者又有区别。一个程序不一定满足有穷性，操作系统就是如此，只要整个系统不被破坏，操作系统就永远不会停止，所以操作系统程序不是一个算法。另外，程序中的指令必须是机器可以执行的，而算法中的指令则无此限制。但是，一个算法如果用机器可执行的语言书写，则它就是一个程序。

　　对一个算法的描述可以采用自然语言、数学语言、约定的符号语言、以及图解等方式。

　　(2)算法的分析

　　求解同一个问题可以有多种不同的算法，评价一个算法的优劣除了正确性和简明性外，主要考虑两点:一是执行算法所耗费的时间，二是执行算法所耗费的存储空间，特别是辅助存储空间的耗费。就这两者而言，前者显得比后者更为重要，在数据结构中往往更注重对算法执行时间的分析。

　　一个算法所耗费的时间是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句执行次数(频度)与该语句一次执行所需时间的乘积。如果假定每条语句一次执行所需的时间均为单位时间，则一个算法的时间耗费就是该算法中所有语句的频度之和。

　　二、线性表

　　(1)线性表及其基本操作

　　线性表是n≥0个元素的一个有限序列:(a 1 ，a 2 ，a 3 ，…，a n- 1 ，a n ，)表中元素的个数n称为表的长度，长度n=0的表称为空表。表元素又称为结点，线性表的一个重要特性是可以按照诸元素在表中的位置确定它们在表中的先后次序。若n≥1，则a 1 ，为第一个元素，a n 为最后一个元素。元素a i-1 先于a i ，我们称a i-1 为a i 的前驱;a i 在a i-1 之后，a 1 为a i-1 的后继。除第一个元素外，每个元素都有一个且仅有一个直接前驱;除最后一个元素外，每个元素都有一个且仅有一个直接后继，下面所列的是其中一些常用的运算。

　　①查找运算

　　查找线性表的第i(0≤i≤n-1)个表元;

　　在线性表中查找具有给定键值的表元;

　　②插入运算

　　把新表元插在线性表的第i(0≤i≤n)个位置上;

　　把新表元插在具有给定键值的表元的前面或后面;

　　③删除运算

　　删除线性表的第i(0≤i≤n-1)个表元;

　　删除线性表中具有给定键值的表元;

　　④其他运算

　　统计线性表元的个数;

　　输出线性表各表元的值;

　　复制线性表;

　　线性表分析;

　　线性表合并;

　　线性表排序;

　　按某种规则整理线性表。

　　(2)线性表的存储

　　有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。

　　①线性表的顺序存储

　　线性表的顺序存储是最简单的存储方式。程序通常用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。即线性表的第i个结点存储在数组的第i(0≤i≤n-1)个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。用数组存储线性表的最大优点是能直接访问线性表中的任一结点。

　　用数组存储线性表的缺点主要有两个:一是程序中的数组通常大小是固定的，可能会与线性表的结点可以任意增加和减少的要求相矛盾;二是执行线性表的结点插、删操作时要移动存于数组中的其他元素，使插和删操作不够简便。

　　②线性表的链接存储

　　线性表链接存储是用链表存储线性表，最简单的用单链表。如从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。即线性表的第i个结点存储在链表的第i(0≤i≤n-1)个表元中。链表的每个表元除要存储线性结点的信息外，还要有一个成分用来存储其后继结点的指针。单链表就是通过链接指针来体现线性表中结点的先后次序关系。每个链表还要有一个指向链表的第一个表元，链表的最末一个表元的后继指针值为空。用链表存储线性表的优点是线性表的每个表元的后继指针就能完成插或删的操作，不需移动任何表元。

　　其缺点也主要有两条:一是每个表元增加了一个后继指针成分，要花费更多的存储空间;二是不便随机地直接访问线性表的任一结点。

　　(3)线性表上的查找

　　线性表上的查找运算是指在线性表中找某个链值的结点。根据线性表的存储形式和线性表本身的性质差异，有多种查找算法，如:顺序查找、二分法查找、分块查找、散列查找等。