1.3.1  基本数据结构与算法

1．算法的基本概念及特征
算法的概念是考试的重点，是指解题方案的准确而完整的描述，它由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。
算法具有可行性、确定性、有穷性、拥有足够的情报等特征。其中，确定性和有穷性是考试的重点。
算法的确定性，是指算法中的每一步骤都必须有明确定义，不允许有模棱两可的解释，也不允许有多义性。
算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
2．算法复杂度的概念和意义

一个算法质量的好坏可从算法的时间复杂度和空间复杂度两个方面来衡量。算法的复杂度也是每次考试的重点，要注意明确有关概念。
算法的时间复杂度是指算法所需要的计算工作量；算法的空间复杂度是指执行这个算法所需要的内存    空间。

3．数据结构的定义
数据结构主要研究和讨论以下三个方面的问题：
① 数据集合中各元素之间所固有的逻辑关系，即数据的逻辑结构。
② 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。
③ 对各种数据结构进行的运算。
要注意数据的逻辑结构与存储结构的区别与联系。

4．线性结构与非线性结构
根据数据结构中各元素之间前后件关系的复杂程度，一般数据结构分为两大类型：线性结构与非线性结构。要注意这两种结构的特征、它们之间的区别以及常见的有关结构。
（1）线性结构（或称线性表）有以下主要特征：
① 有且只有一个根结点，它无前件。
② 有且只有一个终结点，它无后件。
③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数称为线性表的长度，当结点个数为0时，该线性表为空表。
常见的线性结构有：线性表、栈、队列等。

（2）如果一个数据结构不是线性结构，则称之为非线性结构，常见的非线性结构有：树、二叉树、图等。
5．线性表的顺序存储结构（顺序表）及其插入与删除运算
线性表既可以采用顺序存储结构，又可以采用链式存储结构进行存储。要注意掌握二者在存储数据方面的方式与特点。
（1）线性表的顺序存储结构的特点

① 线性表中所有元素所占的存储空间是连续的。
② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
由此可见，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
（2）线性表在顺序存储结构下的插入与删除运算
线性表在顺序存储结构下，若在第i（1?i?n，n为线性表中元素的个数）个位置上插入一个新元素，则首先从最后一个（即第n个）元素开始，直到第i个元素之间共有n–i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i个位置。插入结束后，线性表的长度增1。
显然，在最好的情况下，插入位置在线性表的末尾进行，即在第n个元素之后插入运算，此时，不需要移动表中的元素。而在最坏的情况下，插入位置在第1个元素上，此时需要移动表中所有的元素。在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。

同理，线性表在顺序存储结构下的删除运算，也需要移动表中的元素，只不过是向前移动，在最好的情况下，删除运算在线性表的末尾进行，即删除第n个元素，此时，不需要移动表中的元素。而在最坏的情况下，删除位置在第1个元素上，此时需要移动表中所有的元素。在平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素。
线性表的顺序存储结构的特点，以及在顺序存储结构下插入与删除运算的效率是考试的重点。

6．栈与队列
要深刻领会二者的概念，以及对二者进行插入、删除运算的特点，这是考试的重点。
栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只在线性表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。允许插入与删除运算的一端称为栈顶，而不允许插入与删除运算的一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈是按照“先进后出”（First In Last Out，FILO）或“后进先出”（Last In First Out，LIFO）的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。对栈常可以进行进栈、出栈、读取栈顶元素的运算。

队列是指允许在一端进行插入运算、而在另一端进行删除运算的线性表。允许插入运算的一端称为队尾，通常用一个称为队尾指针的指针指向队尾元素，即队尾指针总是指向最后被插入的元素。允许删除运算的一端称为队头，通常也用一个队头指针指向队头的元素。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”（First In First Out，FIFO）或“后进后出”（Last In Last Out，LILO）的线性表。对队列可以进行入队、退队运算。

7．循环队列
重点注意循环队列的概念、存储方式。
循环队列是队列顺序存储结构的一种，它将m个物理上连续的存储单元，在逻辑上形成一个环状，供队列循环使用。
具体来说，在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置，因此，从队头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。

8．线性表的链式存储结构（线性链表）
（1）线性表的链式存储结构及其有关运算
在线性表的链式存储结构中，一个元素用一个结点来存储，每个结点含有两个域，一个数据域用于存放数据元素值，一个指针域，用于存放指针，该指针用于指向该结点的前一个或后一个结点（即前件或后件）。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序（即存储空间位置）与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。要特别注意，线性表的链式存储结构与顺序存储结构方式的不同。

线性表的链式存储结构又称为线性链表。
对线性链表的运算主要包括：查找指定元素、插入、删除运算等。不像顺序存储结构那样，对线性链表的插入与删除运算不需要移动数据元素，而只需改变有关结点的指针即可。