共享栈的基本操作如下
相关代码请看配套资源
2-共享栈.c
int main(){ Dupsqstack* d; InitDupStack(d); int l0=1; int r0=2; PushDupSrack(d,'L',l0); PushDupSrack(d,'R',r0); int l=GetDupsqTop(d,'L'); int r=GetDupsqTop(d,'R'); printf("%d",l); printf("%d",r); }
运行结果如下
略
3.2.3栈的链式存储结构
栈也可以采用链式存储结构表示，这种结构简称为“链栈”。
在一个链栈中,栈底就是结表的最后一个结点,而栈顶总是链表的第一个结点。采用带头结点的单链表实现栈。因为栈的插入和删除操作仅限制在表头位置进行,所以链表的表头指针top就作为栈顶指针,top始终指向当前栈顶元素前面的头结点,即top->next为栈顶元素,当top->next==NULL,则代表栈空。
1）链栈定义
//链栈的C语言定义如下。 typedef int DataType; typedef struct Stacknode{ DataType data; struct Stacknode * next; }slStacktype;
2）链栈操作
相关代码请看配套资源
3-链栈.c
int main(){ slStacktype *sl=Init(); int x=1; PushLstack(sl,x); int y=GetLsPop(sl); printf("%d",y);//1 int z=PopLstack(sl); printf("%d",z);//1 }
运行结果如下
(3)多个链栈的操作
可将多个单链栈的栈顶指针放在一个一维数组中统一管理。
设一维数组top[M]：
slStacktype* top[M]
其中top[0] ,top[1],…,top[i],…,top[M-1]指向M个不同的链栈,分别是M个链栈的 栈顶指针,这样只需确定链栈号i,然后以top[i]为栈顶指针进行栈操作,即可实现各种操价。多个链栈示意图如图3-6所示。
多个链栈的基本操作
相关代码请看配套资源
4-多个链栈.c
int main(){ slStacktype * top[M]; int x1=1; PushDupLs(top,1,x1); int x11=GetTopDupLs(top,1); printf("%d",x11);//1 int x2=2; PushDupLs(top,2,x2); int x22=GetTopDupLs(top,2); printf("%d",x22);//2 }
运行结果如下
在上面的两个算法中,当指定栈号i(0<=i<=M-1)时,则只对第i个链栈操作,不会影响其他链栈。
3.2.4栈的应用
0. 括号匹配
判断都是括号所构成的字符串是否括号都是一一对应的
相关代码请看配套资源
5-括号匹配
int main(){ char str[10]; gets(str); printf("%s",str); BracketMatch(str); }
运行结果如下
1. 算术表达式求值(上机)
表达式求值是程序设计语言编译中的一个最基本问题,它的实现方法是栈的一个典型的应用实例,
在计算机中,任何一个表达式都是由操作数(operand)、运算符(operalor)和界限符(delimiter)组成的。其中操作数可以是常数,也可以是变量或常量的标识符;运算符可以是算术运算符、关系运算符和逻辑运算值；界限符为左右括号和标识表达式结束的结束符。在本节中,仅讨论简单算术表达式的求值问题。假设在这种表达式中只含加、减、乘、除四则运算,所有的运算对象均为整型常数,表达式的结束符为“#”,即仅含符号+、一、*、/、(、)和#。
算术四则运算的规则如下。
①先乘除、后加减。
②同级运算时先左后右。
③先括号内,后括号外。
3.3 队列
3.3.1队列的概念及其运算
队列(queue)是另一种限定性线性表,它只允许插人在表的一端进行,而删除在表的另一端进行,允许插人的一端叫队尾(rear),而允许删除的一端叫队头(front)。
队列的插人操作通常为“入队”或“进队”,而队列的删除操作则称为“出队”或“退队”。当队列中无数据元素时,所“空队列”。
根据队列的定义可知，队头元素总是最先进队列,也总是最先出队列;队尾元素总最后进队列,因而也是最后出队列。这种表是按照先进先出（First In First Out,FIFO)的原则组织数据的,因此,队列也被称为“先进先出”表。
在队列上进行的基本操作如下。
①队列初始化:InitQutoe(ql 相始条件:队列q不存在， 操作结果:构造了一个空队列: ②人队操作:InQuene(q.x) 初始条件:队列q存在。 操作结果:对已存在的队列q,插人一个元素x到队尾。操作成功,返回值为TRUE,否则返回值为FALSE ③出队操作:OutQueue(q.x) 初始条件:队列g存在且非空。 操作结果:删除队首元素,并返回其值。操作成功,返回值为TRUE,否则返回值为FALSE ④读队头元素:FrontQueue(q,x) 初始条件:队列q存在且非空。 操作结果:读队头元素,并返回其值,队列不变。操作成功,返回值为TRUE,否则返回值为FALSE. ⑤判队空操作:EmptyQueue(q) 初始条件:队列q存在 操作结果:若q为空队列则返回为TRUE,否则返回为FALSE.
队列的顺序存储结构可以 简称为“顺序队列”,另外再设立两个指示器:一个为指向队头元素位置的指示器front,另一个为指向队尾元素位置的指示器rear。
C语言中,数组的下标是从0开始的,因此为了算法设计的方便,在此约定:初始化队列时，空队列的front=rear=-1,当插人新的数据元素时,尾指示器rear加1,而当队头元素出队列时,头 指示器front加1。另外还约定,在非空队列中,头指示器front总是指向队列中实际队头元素的 前面一个位置,而尾指示器rear总是指向队尾元素(这样的设置是为了某些运算的方便,并不是唯一的方法)。
顺序队列的类型定义如下
define MAXSIZE<最大元素数>//队列的最大容量 vypedef struct{ ElemType elem[MAXSIZE];//队列元素的存储空间 int rear,front;//队尾、队头指针 }SeQueue;
定义一个指向队列的指针变量：SeQueue *sq;
申请一个顺序队列的存储空间：sq=(SeQueue*)malloc(sizeof(SeQueue));
存在“假溢出”的问题
3.3.2循环队列
解决假溢出的方法之一是将队列的数据区elem[0~MAXSIZE-1]看成头、尾相接的循环结构，即规定最后一个单元的后维为第个单元,这样整个数据区就像一个环,我们形象地称之为循环队列
入队时队尾指针加1操作修改为
sq->rear=(sq->rear+1)%MAXSIZE
出队时队尾指针加1操作修改为
sq->rear=(sq->front+1)%MAXSIZE
又产生一个新问题队空和队满的条件相同都为front==rear
解决的方法之一是少用一个元素空间，把如图所示视为队满。
队满的条件是(rear+1)%MAXSIZE==front
就能和队空区别开。
另外一种方法是附设一个存储队列中元素个数的变量，如num，当num == 0时队空，当num==MAXSIZE时队满
还有一种在习题（8）中
下面的循环队列及操作依据少用一个元素空间来实现的。
