发布时间 : 星期一 文章数据结构-朱二周更新完毕开始阅读
typedef struct { NODE *top; }LinkStack;
我们经常将链栈用下图的形式描述：
top ^ bottom
（4）栈的应用
【举例1】将从键盘输入的字符序列逆置输出。比如，从键盘上输入：tset a si sihT；算法将输出：This is a test。下面我们给出解决这个问题的完整算法。
typedef char ElemType ; void ReverseRead( ) {
STACK S; //定义一个栈结构S char ch;
InitStack(&S); //初始化栈 while ((ch=getchar())!=’\\n’)
//从键盘输入字符，直到输入换行符为止 Push(&S ,ch); //将输入的每个字符入栈
while (!StackEmpty(S)) { //依次退栈并输出退出的字符 Pop(&S,&ch); putchar(ch); }
putchar(‘\\n’); }
【举例2】十进制数值转换成二进制。使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。
比如：(692)10 = (1010110100)2，其展转相除的过程如图所示：
【举例3】检验表达式中的括号匹配情况。假设在一个算术表达式中，可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”和花括号“{”和“}”，并且这三种括号可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。
算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。 （a）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号； （b）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；
（c）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
（5）队列的定义
队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。如下图所示：
（6）队列的链式表示和实现
在用链式存储结构表示队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点。
入队需要执行下面三条语句：
s->next=NULL; rear->next=s;rear=s;
下面是在C语言中，实现队列链式存储结构的类型定义： type struct QNode { //链式队列的结点结构 ElemType data; //队列的数据元素类型
struct QNode *next; //指向后继结点的指针 } QNode ,*QueuePtr;
typedef struct { //链式队列
QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue;
（7）队列的顺序表示和实现
队列的顺序存储结构如下图所示：
队列的顺序存储结构：
(a) 用一组连续的存储单元依次存放从队列头到队列尾的元素之外，需设两
个指针front和rear分别指示队列头元素和尾元素的位置。
(b) 在C语言中为描述方便，约定：初始化建空队列时，令front=rear=0，
每插入新的队列尾元素时，尾指针增1，每删除队列头元素时，头指针增1。
(c) 在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾
元素的下一个位置。 （8）队列的应用 【举例1】汽车加油站。
随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加2个队列。 【举例2】模拟打印机缓冲区。
在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。
【举例3】CPU分时系统。.
在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。 （二）基本要求
(1) 了解线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方
法；
(2) 熟练掌握在线性表的两类存储结构（顺序存储和链式存储）上实现基本操作：
查找、插入和删除算法；
(3) 熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选
用适当的链表结构。
(4) 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点
及其适用场合。 （三）重点、难点
重点：
（1）栈和队列是本章的重点和难点，扎实的指针操作和内存动态分配技术
是学好本章的基本要求；
（2）栈和队列中的头、尾的区别；
（3）栈和队列的优缺点，在实际应用中加以合理的选用，。 （4）栈和队列插入和删除操作算法的时间和空间复杂度分析。 难点：
循环队列的构造、插入、删除及判断队列的满与空的操作。 （四）作业及课外学习要求：
(a) 栈和队列这两种数据结构的特性。
(b) 如何利用堆栈去模拟递归程序的运行。
(c) 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两
个栈，它们的栈底分别设在数组的两个端点。试编写算法实现这个双向栈tws的3个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈。
(d) 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针
域next），请给出这种队列的入队和出队操作的实现过程。
(e) 已知Q是一个非空队列，S是一个空栈。用队列和栈的基本操作函数和少量
工作变量，编写一个算法，将队列Q中的所有元素逆置。
本知识点的讲授和学习，可以支撑“毕业要求2问题分析”中的“指标点2.1--2.4：能够将数学与自然科学的基本概念运用到工程问题的适当表述之中；能够针对一个系统或者过程选择一种数学模型，并达到适当的精度要求；能够对于模型的正确性进行严谨的推理，并能够给出解；能从数学与自然科学的角度对解决途径进行分析，试图改进”，使学生掌握工程基础知识和本专业的基本理论知识，为学生进行系统的工程实践提供理论基础，并为后续课程的学习奠定理论基础。
第4章 串 ( 6学时) （一）基本内容： （1）串类型的定义
串是由零个或多个字符组成的有限序列。
串、子串的定义。