等级考试公共基础考点分析之数据结构与算法(6).docx

等级考试公共基础考点分析之数据结构与算法(6)线性表的删除运算是指将表的第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)且队尾指针等于队头指针时，说明循环队列已满，不能进展入队运算，这种状况称为“上溢”。