八.顺序表的插入运算

线性表的插入运算是指在表的第I个位置上，插入一个新结点x，使长度为n的线性表（a1,a2 …ai…an）变成长度为n+1的线性表(a1,a2…x,ai…an).

该算法的时间主要花费在循环的结点后移语句上，执行次数是n-I+1。

当I=n+1,最好情况，时间复杂度o(1) 当I=1, 最坏情况，时间复杂度o(n)

算法的平均时间复杂度为o(n)

九.顺序表的删除运算

线性表的删除运算是指在表的第I个位置上，删除一个新结点x，使长度为n的线性表（a1,a2 …ai…an）变成长度为n-1的线性表(a1,a2…ai-1,ai+1…an).
当I=n,时间复杂度o(1),当I=1,时间复杂度o(n) ,平均时间复杂度为o(n)

十.栈及其基本运算

1.什么是栈？ 栈实际上也是一个线性表，只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶（TOP），另一端为栈底（BOTTOM）。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。

假设栈S=（a1,a2,a3,……an），则a1 称为栈底元素，an称为栈顶元素。栈中元素按a1,a2,a3……an的次序进栈，退栈的第一个元素应该是栈顶元素。即后进先出。

2.栈的顺序存储及其运算

用S（1：M）作为栈的顺序存储空间。M为栈的最大容量。

栈的基本运算有三种：入栈、退栈与读栈顶元素。

入栈运算：在栈顶位置插入一个新元素。

首先将栈顶指针进一（TOP+1），然后将新元素插入到栈顶指针指向的位置。

退栈运算：指取出栈顶元素并赋给一个指定的变量。

首先将栈顶元素赋给一个指定的变量，然后将栈顶指针退一（TOP-1）

读栈顶元素：将栈顶元素赋给一个指定的变量。栈顶指针不会改变。

十一.队列及其基本运算

1.什么是队列

队列是只允许在一端删除，在另一端插入的顺序表，允许删除的一端叫做对头，允许插入的一端叫做对尾。

队列的修改是先进先出。往队尾插入一个元素成为入队运算。从对头删除一个元素称为退队运算。

2.循环队列及其运算

在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

在循环队列中，，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针 rear指向的位置之间所有的元素均为队列中的元素。

在实际使用循环队列时，为了能区分队满还是队列空，通常需要增加一个标志S：
队列空，则S=0，rear=front=m     队列满，则S=1，rear=front=m
循环队列主要有两种基本运算：入队运算和退队运算
n      入队运算

指在循环队列的队尾加入一个新元素，首先rear=rear+1,当rear=m+1时，置rear=1,然后将新元素插入到队尾指针指向的位置。当S=1，rear=front,说明队列已满，不能进行入队运算，称为“上溢”。
n      退队运算

指在循环队列的排头位置退出一个元素并赋给指定的变量。首先front=front+1,并当front=m+1时，置front=1,然后将排头指针指向的元素赋给指定的变量。当循环队列为空S=0，不能进行退队运算，这种情况成为“下溢”。