3．线性表的基本操作 1）顺序表的插入运算
在顺序存储结构的线性表中插入一个元素。
注意：找到插入位置后，将插入位置开始的所有元素从最后一个元素开始顺序后移。另外，在定义线性表时，一定要定义足够的空间，否则，将不允许插入元素。 2）顺序表的删除运算
在顺序在存储结构的线性表中删除一个元素。
注意：找到删除的数据元素后，从该元素位置开始，将后面的元素一一向前移动，在移动完成后，线性表的长度减1 （四）栈和队列 1．栈及其基本运算 1）栈
栈是一种特殊的线性表，它是限定在一端进行插入和删除的线性表。它的插入和删除只能在表的一端进行，而另一端是封闭的，不允许进行插入和删除操作。
在栈中，允许插入和删除操作一端称为栈顶，不允许插入和删除操作的一端则称为栈底。栈顶的元素总是最后被插入的元素，也是最先被删除的元素。它遵循的原则是：先进后出或后进先出。
堆栈指针总是指向栈顶元素的。 2）栈的顺序存储及其运算
在栈的顺序存储空间S（1：m）中，S（bottom）通常为栈底元素，S（top）为栈顶元素。Top=0表示栈空；top=m表示栈满。
1）入栈运算
即在栈的顶部插入一个新元素。操作方式是：将栈顶指针加1，再将元素插入至指针所指的位置。
2）退栈运算
退栈运算即将栈顶元素取出并赋给一个指定的变量。操作方式是：先将栈顶元素赋给指定的变量，再将栈顶指针减1。
3）读栈顶元素
将栈顶元素赋给某一指定变量，但栈顶指针不变。 2．队列及其基本运算 1）队列
队列即是允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个尾指针指向队尾；允许删除的一端称为队首，通常用一个队首指针指向排队元素的前一个位置。
队列遵循的规则是：先进先出或后进后出
2）循环队列及其运算
队列的顺序存储结构一般采用循环队列的形式。 循环队列，即是次队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置到队尾指针rear指向的位置之间所有的元素均为队列中的元素。
循环队列的初始状态为空，即rear=front=m。这里m即为队列的存储空间。 循环队列的基本运算：入队运算和退队运算。
入队运算：每进行一次入队运算，队尾指针加1。当队尾指针rear=m+1时，即表示队列空间的尾部已经放置了元素，则下一个元素应该旋转到队列空间的首部，即rear=1
退队运算：每退队一个元素，排头指针加1。当排头指针front=m+1时，即排头指针指向队列空间的尾部，退队后，排头指针指向队列空间的开始，即front=1。
在队列操作时，循环队列满时，front=rear，队列空时，也有rear=front，即在队列空或满时，排头指针和队尾指针均指向同一个位置。要判断队列空或满时，还应增加一个标志，s值的定义：
?0s???1表示队列空表示队列满
判断队列空与队列满的条件下： 队列空的条件：s=0
队列满的条件：s=1、front=rear （1）入队运算
即在队尾加入一个新元素。这个运算有两个基本操作：首先，将队尾指针加1，即rear=rear+1，当rear=m+1时，置rear=1，然后，将新元素插入到队尾指针指向的位置。
当循环队列非空（s=1），且front=rear时，队列满，不能进行入队操作。此情况称“上溢”。
（2）退队操作
即将队首的元素赋给一个指定的变量。该运算也有两个基本操作：首先，将排头指针加1，即front=front+1，当front=m+1时，置front=1，然后，将排头指针指向的元素赋给指定的变量。
当循环队列为空（s=0）时，不能进行退队运算。此种情况称为“下溢”。 （五）线性链表 1．基本概念
前面的线性表均是采用顺序存储结构及在顺序存储结构下的运算。 1）顺序存储的优点：
? 结构简单 ? 运算方便 2）顺序存储结构的缺点：
? 要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除
后的线性表仍然为顺序存储。在插入或删除元素时，需要移动大量的数据元素，因此运算效率较低。
? 如果一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要
插入元素时，会发生“上溢”错误。 ? 在实际应用时，可能有多个线性表同时使用存储空间，这样给存储空间的分配带来
问题，有可能使有的队列空间不够或过多造成浪费。 基于上述情况，对于大的线性表或元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。 3）链式存储结构
假设每一个数据结点对应一个存储单元，该存储单元称为存储结点，简称结点。
在链式存储方式中，要求每一个结点由两部分组成：一部分用于存放数据元素，你为数据域；另一部分用于存放指针，称为指针域。该指针用于指向该结点的前一个或后一个结点。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储结构既可以用于线性结构，也可用于非线性结构。 4）线性链表
线性表的链式存储结构称为线性链表。
将存储空间划分成若干的小块，每块占用若干个字节，这些小块称为存储结点。
将存储结点分为两个部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储元素之间的前后件关系，即存放下一个元素在存储序号（即存储地址），即指向后件结点，称为指针域。
在线性链表中用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放第一个元素的地址）。线性表中最后一个元素没有后件，因此，线性链表中的最后一个结点的指针域为空（用Null或0表示），表示链终结。
在线性链表中，各元素的存储序号是不连续的，元素间的前后件关系与位置关系也是不一致的。在线性链表中，前后件的关系依靠各结点的指针来指示，指向表的第一个元素的指针HEAD称为头指针，当HEAD=NULL时，表示该链表为空。
对于线性链表，可以从头指针开始，沿着各结点的指针扫描到链表中的所有结点。 这种线性链表称为线性单链表，即可以从表头开始向后扫描链表中的所有结点，而不能从中间或表尾结点向前扫描位于该结点之前的元素。
这种链表结构的缺点是不能任意地对链表中的元素按下同的方向进行扫描。在某些应用时，如果对链表中的元素设置两个指针域，一个为指向前件的指针域，称为左指针（LLink），一个为指向后件的指针域，称为右指针（RLink）。则这种链表是双向链表。 5）带链的栈
带链的栈即是用来收集计算机存储空间中的所有空闲的存储结点，这种带链的栈称为可利用栈。
当需要存储结点时，即从可利用的栈的顶部取出栈顶结点；当系统要释放一个存储结点时，将该结点空间放回到可利用栈的栈顶。
即在计算机中所有空闲的空间，均可以以结点的方式链接到可利用栈中，随着其他线性链表中结点的插入与删除，可利用栈处于动态变化之中，即可利用栈经常要进行退栈和入栈操作。
6）带链的队列
队列也是线性表，也可利用链式存储结构来进行保存。 2．线性链表的基本运算
线性链表包括的基本运算：
? 在链表中包含指定元素的结点之前插入一个新元素 ? 在链表中删除包含指定元素的结点
? 将两个线性链表按要求合并成一个线性链表 ? 将一个线性链表按要求进行分解 ? 逆转线性链表 ? 复制线性链表 ? 线性链表的排序 ? 线性链表的查找 1）线性链表中查找指定的元素
在线性链表中查找元素X：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为X为止。
元素的查找，经常是为了进行插入或删除操作而进行的，因此，在查找时，往往是需要记录下该结点的前一个结点。 2）线性链表的插入
线性链表的插入即在链式存储结构的线性表中插入一个新元素。 在线性链表中包含元素x的结点之前插入新元素b，插入过程：
（1）从可利用栈中取得一个结点，设该结点号为p，即取得的结点的存储序号存放在变量p中。并置结点p的数据域为插入的元素值b。
（2）在线性链表中寻找包含元素x的前一个结点，该结点的存储序号为q。 （3）将结点p插入到结点q之后。具体的操作：首先，使结点p插入到结点q之后（即结点q的后件结点），然后，使结点q的指针域 内容改为指向结点p。
线性链表的插入操作，新结点是为来自于可利用栈，因此不会造成线性表的溢出。同样，由于可利用栈可被多个线性表利用，因此，不会造成存储空间的浪费，大家动态地共同使用存储空间。 3）线性链表的删除
线性链表的删除，即是在链式存储结构下的线性表中删除指定元素的结点。 操作方式：
（1）在线性表中找到包含指定元素x的前一个结点p
（2）将该结点p后的包含元素x的结点从线性链表中删除，然后将被删除结点的后一个结点q的地址提供给结点p的指针域，即将结点p指向结点q。
（3）将删除的结点送回可利用栈。
从以上的删除操作可见，删除一个指定的元素，不需要移动其他的元素即可实现，这是顺序存储的线性表所不能实现的。同时，此操作还可更有效地利用计算机的存储空间。 3．循环链表及其基本操作
在线性链表中，虽然对数据元素的插入和删除操作比较简单，但由于它对第一个结点和
空表需要单独处理，使得空表与非空表的处理不一致。
循环链表，即是采用另一种链接方式，它的特点如下：
（1）在循环链表中增加一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
（2）循环链表中最后一个结点的指针域不是空的，而是指向表头结点。在循环链表中，所有结点的指针构成一个环状链。
在循环链表中，只要指出表中任何一个结点的位置，均可以从它开始扫描到所有的结点，而线性链表做不到，线性链表是一种单向的链表，只能按照指针的方向进行扫描。
循环链表中设置了一个表头结点，因此，在任何时候都至少有一个结点，因此空表与非空表的运算相统一。 （六）树与二叉树 1．树的基本概念
树是一种简单的非线性结构。在树结构中，数据元素之间有着明显的层次结构。在树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。
A B E J M K N F L C G D H I
在树结构中，每一个结点只有一个前件，称为父结点。如A即为结点B、C、D的父结点。 没有父结点的结点只有一个，称为根结点。如上图所示，结点A即为根结点。
每一个结点可以有多个后件，它们均称为该结点的子结点。如结点G、H、I是结点D的子结点。
没有后件的结点，称为叶子结点。上图中，叶子结点有：J、M、N、L、C、G、H、I。 在树结构中，一个结点所拥有的后件结点个数称为该结点的度。例如，结点D的度为3，结点E的度为1等，按此原则，所有叶子结点的度均为0。
在树中，所有结点中最大的度称为该树的度。上图所示的树中，所有结点中最大的度是3，所以该树的度为3。
树分层，根结点为第一层，往下依次类推。同一层结点的所有子结点均在下一层。如上图：A结点在第1层，B、C、D结点在第2层；E、F、G、H、I在第3层；J、K、L在第4层；M、N在第5层。
树的最大层次称为树的深度。上图树的深度为5。
在树中，某结点的一个子结点为根构成的树称作该结点的子树。叶子结点没有子树。 在计算机中，可以用树来表示算术表达式。原则如下：
（1）表达式中每一个运算符在树中对应一个结点，称为运算符结点
（2）运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）