注：整理自高教版《全国计算机等级考试二级教程——公共基础知识》和人邮版《全国计算机等级考试教程 二级公共基础知识》
线性表及其顺序存储结构
线性表的基本概念
线性表是最简单、最常用的一种数据结构。
线性表是由n（n＞0）个数据元素a1,a2,……an组成的一个优先序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为：
(a1,a2,a3,……,ai,……,an)
其中ai（i=1,2，……，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。
线性表由一组数据元素构成。数据元素的含义很广泛，在不同的具体情况下，它可以有不同的含义。
数据元素可以是简单的项（例如数，字母，季节等），在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。在这种复杂的线性表中，由若干数据项组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
显然，线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。
非空线性表有如下一些结构特征：
- 有且只有一个根结点a1，它无前件；
- 有且只有一个终端结点an，它无后件；
- 除根结点与终端结点外，其他所有的结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。
线性表的顺序存储结构
线性表的顺序存储结构具有以下两个基本特点：
- 线性表中所有元素所占的存储空间是连续的；
- 线性表中各元素在存储空间中是按逻辑顺序依次存放的。
在顺序表中，其前、后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
假设线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为ADR（a1），每一个数据元素占k个字节，则线性表中第i个元素ai在计算机存储空间中的存放地址为：
ADR(ai)=ADR（a1）+（i - 1）k
即在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。
从这种表示方法可以看到，它是用元素在计算机内物理位置上的相邻关系来表示元素之间逻辑上的相邻关系。只要确定了首地址，线性表内任意元素的地址都可以方便地计算出来。
在程序设计语言中，通常定义一个一维数组来表示线性表的存储空间。因为程序设计语言中的一维数组与计算机中实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。
在线性表的顺序存储结构下，可以对线性表进行各种处理，主要的运算有以下几种：
- 在线性表的指定位置处加入一个新的元素（线性表的插入）；
- 在线性表中删除指定的元素（线性表的删除）；
- 在线性表中查找某个（或某些）特定的元素（线性表的查找）；
- 对线性表中的元素进行整序（线性表的排序）；
- 按要求将一个线性表分解成多个线性表（线性表的分解）；
- 按要求将多个线性表合并成一个线性表（线性表的合并）；
- 复制一个线性表（线性表的复制）；
- 逆转一个线性表（线性表的逆转）等。
顺序表的插入运算
在一般情况下，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。
可以归纳为三个步骤：
- 把原来第n个节点至第i个节点依次往后移一个元素位置。
- 把新节点放在第i个位置上。
- 修正线性表的节点个数。
一般情况下，在第i（1≤i≤n）个元素之前插入一个元素时，需将第i个元素之后(包括第i个元素）的所有元素向后移动一个位置。
如果要在第1个位置处插入一个新元素，则需要移动表中所有的元素。
线性表的插入运算，其时间主要花费在节点的移动上，所需移动节点的次数不仅与表的长度有关，而且与插入的位置有关。
顺序表的删除运算
在一般情况下，要删除第i（1≤i≤n）个元素时，则要从第i+1个元素开始，直到第n个元素之间共i-1个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。
可以归纳为两个步骤：
- 把第i个元素之后（不包括第i个元素）的n-i个元素依次前移一个位置。
- 修正线性表的节点个数。
显然，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动线性表中的元素。
如果要删除第1个元素，则需要移动表中所有的元素。
在一般情况下，如果删除第i（1≤i≤n）个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。
由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储结构比较简单。但这种顺序存储方式对于元素经常需要变动的大线性表就不太合适了，因为插入与删除的效率比较低。
栈和队列
栈及其基本运算
什么是栈
栈实际上也是线性表，只不过是一种特殊的线性表。
栈是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。
即：栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。
由此也可以看出栈具有记忆作用。
通常用指针top来指示栈顶的位置，用指针bottom指向栈底。
栈的顺序存储及其运算
与一般的线性表一样，在程序设计语言中，用一维数组S（1：m）作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈底指针指向栈空间的低地址一端（即数组的起始地址这一端）。
在栈的顺序存储空间S（1:m）中，S（bottom）通常为栈底元素（在栈非空的情况下），S（top）为栈顶元素。top=0表示栈空，top=m表示栈满。
栈的基本运算有三种：入栈，退栈与读栈顶元素。
入栈运算
入栈运算是指在栈顶位置插入一个新元素。操作过程如下：
- 首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（“上溢”错误），算法结束。
- 然后将栈顶指针进1（即top加1）。
- 最后将新元素x插入栈顶指针指向的位置。
退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：
- 首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（“下溢”错误），算法结束。
- 然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
- 最后将栈顶指针退1（即top减1）。
读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：
- 首先判断栈顶指针是否为0.如果是，则说明栈空，读不到栈顶元素，算法结束。
- 然后将栈顶元素赋给一个指定的变量。
这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。
队列及其基本运算
什么是队列
队列也是一种特殊的线性表。
队列是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为队尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针（front）指向排头元素的前一个位置。
显然，在这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”或“后进后出”的线性表。
往队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。入队运算只涉及队尾指针（rear）的变化，而退队运算只涉及排头指针（front）的变化。
与栈类似，在程序设计语言中，用一维数组作为队列的顺序存储空间。
循环队列及其运算
在实际应用中，队列的顺序存储结构一般采用循环队列的形式。
所谓的循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。
在循环队列中，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。
循环队列主要有两种基本运算：入队运算与退队运算。
每进行一次入队运算，队尾指针就进1。当队尾指针rear=m+1时，则置rear=1。
每进行一次退队运算，排头指针就进1。当排头指针front=m+1时，则置front=1。
当循环队列满或空时都有front=rear，不能确定队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需要增加一个标志s，s值的定义如下：
s=0 表示队列空
s=1 表示队列非空
- 队列空的条件：s=0；
- 队列满的条件：s=1且front=rear。
入队运算
入队运算是指在循环队列的队尾加入一个新的元素。操作过程如下：
- 首先判断循环队列是否满。当循环队列非空（s=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算（“上溢”错误），算法结束。
- 然后将队尾指针进1（rear=rear+1），并当rear=m+1时置rear=1。
- 最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。
退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：
- 首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退队运算（“下溢”错误），算法结束。
- 然后将排头指针进1（front=front+1），并当front=m+1时置front=1。
- 再将排头指针指向的元素赋给指定的变量。
- 最后判断退队后循环队列是否为空。当front=rear时置循环队列空标志（s=0）。
