行各种运算，特别是插入运算。在线性表的顺序存储结构下，可以对线性表做以下运算： (l)在线性表的指定位置处加入一个新的元素(即线性表的插入)； (2)在线性表中删除指定的元素(即线性表的删除)；
(3)在线性表中查找某个(或某些)特定的元素(即线性表的查找)； (4)对线性表中的元素进行整序(即线性表的排序)；
(5)按要求将一个线性表分解成多个线性表(即线性表的分解)； (6)按要求将多个线性表合并成一个线性表(即线性表的合并)； (7)复制一个线性表(即线性表的复制)； (8)逆转一个线性表(即线性表的逆转)等。
考点8 顺序表的插入运算
线性表的插入运算是指在表的第i(1≤i≤n+l)个位置上，插入一个新结点x，使长度为n的线性表
(a1，?，ai-1，ai，?，an) 变成长度为n+1的线性表
(a1，?，ai-1，x，ai，?，an)
现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环结点后移语句上，该语句的执行次数(即移动结点的次数)是n-i+1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。
当i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O(1)；
当i=1时，结点后移语句，将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O(n)。
由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度。 在长度为n的线性表中第i个位置上插入一个结点，令Eis ( n )表示移动结点的期望值(即移动的平均次数)，则在第i个位置上插入一个结点的移动次数为n-i+1。故 不失一般性，假设在表中任何位置(1≤i≤n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=pn+1=1/(n+1) 因此，在等概率插入的情况下，
也就是说，在顺序表上做插入运算，平均要移动表上一半的结点。当表长n较大时，算法的效率相当低。虽然Eis ( n )中n的的系数较小，但就数量级而言，它仍然是线性级的。因此算法的平均时间复杂度为O(n)。 考点9 顺序表的删除运算
线性表的删除运算是指将表的第i(1≤i≤n)个结点删除，使长度为n的线性表： (a1，?，ai-1，ai，ai+1，?，an) 变成长度为n-l的线性表
(a1，?，ai-1，ai+1，?，an)
该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若i=1，则前移语句将循环执行n一1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。
删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故
式子中，pi表示删除表中第i个结点的概率。在等概率的假设下， p1=p2=p3=…=pn=1/n 由此可得：
即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。
1.4 栈和队列
考点10 栈及其基本运算 1什么是栈
栈实际也是线性表，只不过是一种特殊的线性表。栈(Stack)是只能在表的一端进行插入和删除运算配线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈(栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。
假设栈S=(al，a2，a3，?，an)，则a1，称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，?，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为先进后出表(FILO，First In Last Out)，或“后进先出”表(LIFO，Last In First Out)，如图1-7所示。
2栈的顺序存储及其运算
(l)入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即top加1)，然后将元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误。如图1-8所示。
(2)退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针减一(即t叩减1)。当栈顶指针为。时，说明栈空，不可进行退栈操作。这种情况称为栈的“下溢”错误。 (3)读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。 考点11 队列及其基本运算 1什么是队列
队列(queue)是只允许在一端删除，在另一端插入的顺序表，允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)，
当队列中没有元素时称为空队列。在空队列中依次加入元素a1，a2，?，an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1，a2，?，an也就是说队列的修改是依先进先出的原则进行的。因此队列亦称作先进先出(FIFO，First In First Out)的线性表，或后进后出(LILO，Last In Last Out)的线性表。往队列队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算，如图1-10所示。 一个队列币。删除个儿素后的队列间插入元素E后的队列 2循环队列及其运算
在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间
在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。
可以将向量空间想象为一个首尾相接的圆环，如图1-12所示，并称这种向量为循环向量，存储在其中的队列称为循环队列( Cireular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界(Queuesize-l)时，其加1操作的结果是指向向量的下界0。
由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。
在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志、，、值的定义如下：当s=0时表示队列空；当s=1时表示队列非空。 (l)入队运算
入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进一(即rear=rear+1)，并当rear=m+l时置rear=1；然后将新元素插入到队尾指针指向的位置。当循环队列非空(s=l)且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。 (2)退队运算
退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针一进一(即from=front +1)，并当front = m+1时，置front=1然后将排头指针指向的元素赋给指定的变量。当循环队列为空(s =0)时，不能进行退队运算，这种情况称为“下溢”。转贴于：计算机二级考试_考试大【责编:daiy 纠错】 1.5 线性链表
考点12 线性单链表的结构及其基本运算 1什么是线性链表
(l)线性表顺序存储的缺点 ①在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。因此采用顺序存储结构进行插入或删除的运算效率很低； ②当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时栈会发生“上溢”错误；
③计算机空间得不到充分利用，并且不便于对存储空间的动态分配。 (2)线性表链式的基本概念 在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。如图1-13所示。 2线性单链表的存储结构
用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后件结点的地址(或位置)信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构，
链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起。由于上述链表的每一个结点只有一个链域，故将这种链表称为单链表(Single Linked)。
显然，单链表中每个结点的存储地址是存放在其前驱结点Next域中，而开始结点无前驱，故应设头指针HEAD指向开始结点。同时，由于终端结点无后件，故终端结点的指针域为空，即NULL。
3带链的栈与队列
(1)栈也是线性表，也可以采用链式存储结构。在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈 (2)队列也是线性表，也可以采用链式存储结构， 考点13 线性链表的基本运算
线性链表的运算主要有以下几个：
(l)在线性链表中包含指定元素的结点之前插入一个新元素； (2)在线性链表中删除包含指定元素的结点； (3)将两个线性链表按要求合并成一个线性表； (4)将一个线性链表按要求进行分解； (5)逆转线性链表； (6)复制线性链表； (7)线性链表的排序； (8)线性链表的查找。 1在线性镬表中查找指定元素
在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个结点。
在线性链表中，即使知道被访问结点的序号a，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域Next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。
在链表中，查找是否有结点值等于给定值x的结点，若有的话，则返回首次找到的其值为x的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值x作比较。 2线性链表的插入
线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。
插入运算是将值为X的新结点插入到表的第i个结点的位置上，即插入到ai-1，与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点，p的指针域指向新结点，新结点的指针域指向结点ai
由线性链表的插入过程可以看出，由于插入的新结点取自于可利用栈，因此，只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只要改变有关结点的指针即可，从而提高了插入的效率。 3多线性链表的删除
线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的结点。 删除运算是将表的第i个结点删去。因为在单链表中结点a的存储地址是在其直接前趋结点ai-1，的指针域Next中，所以我们必须首先找到ai-1的存储位置p。然后令p->Next指向ai的直接后件结点，即把ai从链上摘下。最后释放结点a的空间。 从线性链表的删除过程可以看出，从线性链表中删除一个元素后，不需要移动表中的数据元素，只要改变被删除元素所在结点的前一个结点的指针域即可。另外，由于可利用栈是用于收集计算机中所有的空闲结点，因此，当从线性链表中删除一个元素后，该元素的存储结点就变为空闲，应将空闲结点送回到可利用栈。 考点14 线性双向链表的结构及其基本运算 1什么是双向链表
在单链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度为O(1)，但无法直接找到它的互接前件；在单循环链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度仍为O(1)，直接找到它的直接前件，时间复杂度为O(n)。有时，希望能快速找到一个结点的直接前件，这时，可以在单链表中的结点中增加一个指针域指向它的直接前件，这样的链表，就称为双向链表(一个结点中含有两个指针)。如果每条链构成一个循环链表，则会得到双向循环链表 2双向链表的基本运算
(l)插入：在HEAD为头指针的双向链表中，在值为Y的结点之后插入值为X的结点，插入结点的指针变化。如图1-20所示(若改为在值为Y的结点之前插入值为X的结点，可以做类似分析)。
(2)删除：在以HEAD为头指针的双向链表中删除值为X的结点，删除算法的指针变化，如图1-21所示。
考点15 循环链表的结构及其基本运算
单链表上的访问是一种顺序访问，从其中的某一个结点出发，可以找到它的直接后件，但无法找到它的直接前件。
在前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。
因此，我们可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存贮空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活。从单链表可知，最后一个结点的指针域为NULL，表示单链表已经结束。如果将单链表最后一个结点的指针域改为存放链表中头结点(或第一个结点)的地址，就使得整个链表构成一个环，又没有增加额外的存储空间
循环链表具有以下两个特点：
(1)在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点；
(2)循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。 在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。
由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表的运算统一。 1.6 树与二叉树 考点16 树的定义
树是由n( n≥0)个结点组成的有限集合。若n =0，称为空树；若n>0，则： (1)有一个特定的称为根(root)的结点。它只有直接后件，但没有直接前件；
(2)除根结点以外的其他结点可以划分为m(m≥0)个互不相交的有限集合T0，T1，?，Tm-1，每个集合Ti(i=0，1，?，m-l)又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前件，但可以有0个或多个直接后件。 树型结构具有如下特点：
(1)助每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根；
(2)每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点；