第2章受限的线性表

在[绪论](http://blog.csdn.net/u013595419/article/details/50461536)中，我们介绍了数据结构三要素， [第1章](http://blog.csdn.net/u013595419/article/details/50461712)中，讲解了逻辑结构分类中线性结构的第一个部分——一般线性表，这章开始讲解逻辑结构线性结构的第二个部分——受限的线性表。这里先巩固下逻辑结构的分类，如下图所示：  受限线性表最简单直白的理解便是插入，删除，查找等操作时，不能随心所欲的进行，必须遵循一定的限制（规则）。 ## 一.栈 ### 1.1定义 栈（stack）是一种只允许在一端进行插入或删除操作的线性表。 一般规定，栈只能在栈顶进行插入，删除操作。因此访问元素的顺序是先进后出。 如下图所示：  这里介绍几个重要的概念： > - 栈顶（top）：栈的操作中，仅允许插入和删除的那一端。 > - 栈底（bottom）：固定的，不允许进行插入和删除操作的那一端。 > - 空栈：不含有任何元素的空线性表。 ### 1.2基本操作 ~~~ InitStack(&S) //初始化一个空栈S StackEmpty(S) //判断一个栈是否为空 Push(&S,x) //入栈，若栈未满，则将x加入使之称为新栈顶 Pop(&S,x) //出栈，若栈非空，则弹出栈顶元素，并用x返回 GetTop(S,&x) //读取栈顶元素，若栈S非空，则用x返回栈顶元素 ClearStack(S) //销毁栈，并释放栈S占用的存储空间 ~~~ ## 二.队列 ### 2.1定义 队列（Queue）简称队，只允许在线性表的一端进行插入，另一端进行删除。 一般规定，只能在队尾进行插入操作，队头进行删除操作。因此访问时的顺序是先进先出。 如下图所示：  介绍几个重要的概念： > - 队头：允许删除的一端，又称为队首。 > - 队尾：允许插入的一端。 > - 空队列：不含任何元素的空表。 ### 2.2基本操作 ~~~ InitQueue(&Q) //初始化队列，构造一个空队列 QueueEmpty(&Q) //判断队列是否为空 EnQueue(&Q,x) //入队，若队列Q未满，将x加入，使之称为新的队尾 DeQueue(&Q,&x) //出队，若队列Q非空，删除队头元素，并用x返回 GetHead(Q,&x) //读取队头元素，若队列非空，则将队头元素赋值给x ~~~ ## 三.串 ### 3.1定义 字符串（string）简称串，是由零个或多个字符组成的有穷序列。 介绍几个重要概念： > - 串长：串中所含字符的个数 > - 子串：一个串中任意个连续字符组成的子序列(含空串,但不含串本身) > - 主串：包含子串的串 > - 空串：含零个字符的串，通常用 Φ 表示。 ### 3.2基本操作 ~~~ StrAssign(&T,chars) //由字符串常量chars生成字符串T的操作。 StrCopy(&T,S) //由串S复制生成串T的操作。 StrCompare(S,T) //若S=T返回0，S>T返回正数，S ';