3.1.3栈与递归的实现

if(S->top==-1) /*栈为空*/
return(FALSE);
else
{*x = S->elem[S->top];
return(TRUE);
}
返回主目录}[注意]：在实现GetTop操作时，也可将参数说明SeqStack *S 改为SeqStack S，也就是将传地址改为传值方式。传 值比传地址容易理解，但传地址比传值更节省时间、 空间。
返回主目录
算法:
void BracketMatch(char *str) {Stack S; int i; char ch; InitStack(&S); For(i=0; str[i]!='\0'; i++) {switch(str[i])
{case '(': case '[': case '{':
3.1.3 栈的应用举例
1. 括号匹配问题
思想：在检验算法中设置一个栈，若读入的是左括号， 则直接入栈，等待相匹配的同类右括号；若读入的是 右括号，且与当前栈顶的左括号同类型，则二者匹配， 将栈顶的左括号出栈，否则属于不合法的情况。另外， 如果输入序列已读尽，而栈中仍有等待匹配的左括号， 或者读入了一个右括号，而栈中已无等待匹配的左括 号，均属不合法的情况。当输入序列和栈同时变为空 时，说明所有括号完全匹配。
return(TRUE);
}
返回主目录
【思考题】
如果将可利用的空闲结点空间组织成链栈来管理，则申 请一个新结点（类似C语言中的malloc函数）相当于链 栈的什么操作？归还一个无用结点（类似C语言中的 free函数）相当于链栈的什么操作？试分别写出从链栈 中申请一个新结点和归还一个空闲结点的算法。

LinkQueue q;
QElemType eq;
if(newcolor==g[e.row][e.col]) return ERROR; oldcolor= g[e.row][e.col];
DeQueue(q, eq); i=eq.row; j=eq.col; g[i][j]=newcolor; if((i-1>=0)&&(g[i-1][j]=oldcolor) { e.row=i-1; e.col=j; EnQueue(q, e); } if((i+1<=m-1)&&(g[i+1][j]=oldcolor) {e.row=i+1; e.col=j; EnQueue(q, e); } ....................... }\*while return OK; }\*Change_Color
\*栈满
●出栈
Status Pop(SqStack &S, SElemType &e) { if (S.top==S.base) return ERROR; e=*--S.top; rபைடு நூலகம்turn OK; }
●链式存储结构：图3.3(P47) 栈空：S为空指针；栈满：动态分
配，除非溢出。 data next
3．2栈的应用举例 3.2.1 数制转换 十进制N和其它进制数的转换是计算机实现计算 的基本问题,其解决方法很多,其中一个简单算法基 于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2

n>=0}
数据关系：R1={< ai-1， ai > | ai-1，ai ∈ D, i = 1,2,…,n}
约定an端为栈顶， a1端为栈底。 基本操作：
InitStack(&S)//初始化栈
操作结果：构造一个空栈s (不含任何元素)。
DestroyStack(&S) 初始条件：栈s已存在。 操作结果：栈s被销毁。 ClearStack(&S) 初始条件：栈s已存在。 操作结果：将s清为空栈。 StackEmpty(S) //判栈空 初始条件：栈s已存在。 操作结果：若栈S为空栈，则返回TRUE， 否则FALSE。
顺序栈基本操作算法描述
1、构造一个空栈
Status InitStack( SqStack &s ) {// 初始化顺序栈, 构造一个空栈 s.base = (SElemType *)malloc( STACK_INIT_SIZE * sizeof( SElemType)); if( !s.base ) exit( OVERFLOW); s.top = s.base; s.stacksize = STACK_INIT_SIZE; return OK; }// InitStack
链栈的出栈算法
int Pop (LinkStack &s, ElemType &e) { SNode *p; if (s->next==NULL) return 0; p＝s->next; e＝p->data; s->next＝p->next; free(p); return 1; }
作业4
1、有5个元素，其进栈次序为A、B、C、D、E，在各种可能的 出栈次序中，以元素C、D最先出栈（即C第一且D第二个出 栈）的次序有哪几个？ 2、假设以I和O分别表示进栈和出栈操作，栈的初态和终态均 为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。 （1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（1）的分析，写出一个算法判定所给的操作序列 是否合法。若合法返回1；否则返回0（假设被判定的操作序 列已存入一维数组中）。 3、假设表达式中允许包含三种括号：圆括号、方括号和大括号。 编写一个算法，判定表达式中的括号是否正确配对。

Elemtype pop(sqstack *s) { /*若栈s不为空，则删除栈顶元素*/ Elemtype x; if(s->top<0) return NULL; /*栈空*/ x=s->stack[s->top]; s->top--; return x; }
13
（4）取栈顶元素操作
Elemtype gettop(sqstack *s) { /*若栈s不为空，则返回栈顶元素*/ If(s->top<0) return NULL; /*栈空*/ return (s->stack[s->top]); }
。
29
算术表达式求值
在计算机中，任何一个表达式都是由: 操作数（operand）、运算符（operator）和 界限符（delimiter）组成的。 其中操作数可以是常数，也可以是变量或常量的 标识符；运算符可以是算术运算体符、关系运算符和 逻辑符；界限符为左右括号和标识表达式结束的结束 符。
30
6
存储结构
栈是一种特殊的线性表，有两种存储方式: 顺序存储结构存储
链式存储结构存储。


7
顺序栈的数组表示
与第二章讨论的一般的顺序存储结构的线性表 一样，利用一组地址连续的存储单元依次存放自 栈底到栈顶的数据元素，这种形式的栈也称为顺 序栈。 使用一维数组来作为栈的顺序存储空间。 设指针top指向栈顶元素的当前位置，以数组 小下标的一端作为栈底。 top=0时为空栈，元素进栈时指针top不断地 加1，当top等于数组的最大下标值时则栈满。
5）假如读出的运算符的优先级不大于运算符栈栈顶运算符
的优先级，则从操作数栈连续退出两个操作数，从运算符栈中 退出一个运算符，然后作相应的运算，并将运算结果压入操作 数栈。此时读出的运算符下次重新考虑（即不读入下一个符号 ）。