|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头（front）。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（FIFO，first in first out）的原则组织数据的，因此，队列也被称为“先进先出”表。下面用C语言描述队列类型为：
|
|
|
|
|
|
队列分为链队列和循环队列。链队列主要采取顺序存储方式，下面主要介绍链队列的顺序存储。队列的顺序存储在c语言中可以用一维数组表示，为了标识队首和队尾，需要附设两个指针front和rear，front指示的是队列中最前面，即队首结点在数组中元素的下标，rear指示的是队尾结点在数组中元素的下标的下一个位置，也就是说rear指示的是即将插入的结点在数组中的下标。下图所示的是队列的几种状态：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
链队列还有链式存储结构，与顺序表的链式存储结构类似。循环队列的操作与链队列相似，这里就不再累述了。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
栈（Stack）是一种特殊的线性表，是限定仅在表尾进行插入或者删除操作的线性表。进行插入和删除的那一端称为栈顶（top），另一端称为栈底（bottom）。栈的插入操作和删除操作也分别简称进栈和出栈。
|
|
|
|
如果栈中有n个结点｛k0，k1，k2，…, kn-1｝，k0为栈底，kn-1是栈顶，则栈中结点的进栈顺序为k0, k1, k2，…，kn-1，而出栈的顺序为kn-1, kn-2，…, k1,k0，如下图所示。
|
|
|
|
|
|
|
|
栈的主要操作是桟的初始化、插入和删除运算、判断栈是否为空以及读取栈顶结点的值等操作。栈的类型的描述如下：
|
|
|
|
|
|
和顺序表类似，栈的实现方式一般也有两种：顺序存储和链式存储。下面主要介绍顺序栈。由于栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制，使得它们仅能在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。一般地，可以设定一个足够大的一维数组存储栈，数组中下标为0的元素就是栈底，对于栈顶，可以设一个指针top指示它。为了方便，设定top所指的位置是下一个将要插入的结点的存储位置，这样，当top=0时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
顺序存储栈的几个基本操作的具体实现，具体如下所示：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
根据数据元素之间关系的不同特性，通常有下列4类基本的逻辑结构，即集合结构、线性结构、树形结构、图形结构。
|
|
|
|
|
|
线性表是最常用且最简单的一种数据结构。线性表中除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，每个元素都只有一个直接后继。
|
|
|
|
栈是限定仅在表尾进行插入或删除操作的线性表，是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。
|
|
|
|
队列是一种先进先出（FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。
|
|
|
|
|
|
树是n（n≥0）个互不相交的有限集，当n=0时称为空树。在一棵非空树中，有且仅有一个节点称为根节点；当n>1时，其余的节点可分为若干个不相交的集合，其中每一个集合本身又是一棵树，这些集合称为根节点的子树。
|
|
|
|
|
|
图是由两个集合V和E组成的二元组，记为G=（V, E），其中V是顶点的非空有限集合，E是图中边的有限集合。
|
|
|
|
|
|
|
|
|
|
|
|
|
