三、栈和队列
栈的概念
栈是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时成为空栈。
栈的进出顺序判断：
栈的基本操作：
顺序栈
顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top来动态地指示栈顶元素的顺序栈中的位置。通常以top=0表示空栈。
链栈：采用链表作为存储结构实现的栈。为便于操作，采用带头结点的单链表实现栈。因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。
顺序栈和链式栈的比较：实现链式栈和顺序栈的操作都是需要常数时间，即时间复杂度为O（1），主要从空间和时间两个方面考虑。初始时，顺序堆栈必须说明一个固定的长度，当堆栈不够满时，造成一些空间的浪费，而链式堆栈的长度可变则使长度不需要预先设定，相对比较节省空间，但是在每个节点中设置了一个指针域，从而产生了结构开销。
队列的概念
队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入数据一端成为队尾（rear），允许删除的那一端称为队头（front）。
顺序队列
顺序队列利用一组地址连续的存储单元依次存放自队首到队尾的数据元素，同时由于队的操作的特殊性，还必须附两个位置指针front和rear来动态地指示队首元素和队尾元素在顺序队列中的位置。通常front=rear表示空队列。
队列同堆栈一样也有上溢和下溢现象。以外，队列中还存在“假溢出”现象。所谓“假溢出”是指在入队和出队操作中，头尾指针不断增加而不减小或只减小而不增加，致使被删除元素的空间无法重新利用，最后造成队列中有空闲空间，但是不能够插入元素，也不能够删除元素的现象。
链式队列：采用链表作为存储结构实现的队列。为便于操作，采用带头结点的单链表实现队列。因为队列的插入和删除操作位置不同，所以链表需要设置表头指针和表尾指针分别指队首和队尾。
循环队列
假设向量的空间是m,只要在入出队列时，将队首和队尾的指针对m做求模运算即可实现队首和队尾指针的循环，即队首和队尾指针的取值范围是0到m-1之间。
判断队空和队满的方法
四、数组和广义表
数组的定义
数组是我们熟悉的数据类型，数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。
任何数组A都可以看作一个线性表。数组维数确定后，数据元素个数和元素之间的关系不再发生改变，适合顺序存储。
数组的基本操作
数组的顺序表示和实现
行优先顺序
列优先顺序 
有些特殊矩阵，非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，会占用许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，对这类矩阵进行压缩存储——即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
特殊矩阵：所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，如对称矩阵、三角矩阵、对角矩阵等等。 
对称矩阵
对称矩阵中元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样能节约近一半的存储空间。
n2 个元素可以压缩到 n（n+1）/2个空间中。
三角矩阵
以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵它的下三角中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数。
稀疏矩阵
除了记录非零元素的值之外，还必须同时几下它所在的行和列的位置。稀疏矩阵的存储方法一般有三种：三元组法、行逻辑连接顺序表和十字链表法。
广义表
是由零个或多个原子或子表组成的优先序列，是线性表的推广。
广义表的存储结构
广义表中的数据元素可以具有不同的结构，因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个节点表示。由于广义表中有两种数据元素，因此需要有两种结构的节点——一种是表结点，一种是原子结点。
表结点由三个域组成：标志域、指示表头的指针的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。
表结点由三个域组成：标志域、指示表头的指针域和指向下一个元素的指针；原子结点的三个域为：标志域、值域和指向下一个元素的指针。
全部评论