void bracket(stack *s,char *str) { int i=0,flag1=1,flag2;char e; 例3括号匹配的检验 括号匹配的检验 while(str[i]!='\0') { switch(str[i++]) { case ‘(’:push(s,‘(’);break; case ‘[’:push(s,‘[’);break; case ')':{pop(s,&e); if(e!='(') flag1=0;break;} case ']':{pop(s,&e); if(e!='[') flag1=0;break;} default: break; } if(!flag1) break; //出现不匹配，立即结束循环 出现不匹配， 出现不匹配 } flag2=stackempty(s); //flag2判断堆栈是否为空 判断堆栈是否为空 if(flag1 && flag2) printf("括号匹配 括号匹配!\n"); 括号匹配 else printf("括号不匹配 括号不匹配!\n"); 括号不匹配 }
例如: 例如 #4+ 2 × 3 − 10 / 5 #
/ –
进栈 退栈
× – + #
10 3 6 2 4
2×3=6 ×
OPTR
OPND
3.3 栈与递归的实现
1. 求n! 2. Hanoi塔问题 塔问题
用递归调用) 例1 求n! (用递归调用 用递归调用
1 fac= n (n-1)! n>0 main ( ) { int n=3; p= fac (n); printf("%d",p); } } n=0 int fac ( int n ) { int f; if ( n==0) fac=1; else f= fac(n-1) * n; return( f );
#
4
OPTR
OPND
算符间的优先级关系
θ1 + – * / （ ） # θ2 + > > > > < > < – > > > > < > < * < < > > < > < / < < > > < > < （ < < < < < < ） > > > > = > # > > > > > =
例如: 例如 #4+ 2 × 3 − 10 / 5 #
+
×
+ #
2 4
OPTR
OPND
算符间的优先级关系
θ1 + – * / （ ） # θ2 + > > > > < > < – > > > > < > < * < < > > < > < / < < > > < > < （ < < < < < < ） > > > > = > # > > > > > =
void lineedit(stack *s) //此处只编辑一行 此处只编辑一行 { char ch,*p;int n=1; //编辑多行自行思考 编辑多行自行思考 while((ch=getchar())!='\n') { if(ch=='@') clearstack(s); else if(ch=='#') {if(!stackempty(s)) pop(s);} else push(s,ch); } if(stackempty(s)) printf("没有可输出的字符 没有可输出的字符"); 没有可输出的字符 else { p=s->base; while(p!=s->top) {printf("%c",*p);p++;} } }
4 3 2 1
栈顶Top 栈底base 栈底
2. 栈的压入操作
void push(stack *s,int e)//进栈 进栈 { if(s->top-s->base>=M) {s->base=(int*)realloc(s->base,(s>stacksize+N)*sizeof(int)); s->top=s->base+s->stacksize; s->stacksize+=N; 栈顶Top } 栈顶Top *(s->top)=e; 栈底base 栈底 s->top++; }
用递归调用) 求n! (用递归调用 用递归调用
1 fac= n (n-1)! n>0 main ( ) { n=0 int fac ( int n ) { int f; if ( n==0) fac=1;
int n=3; 将所有的实参 返回地址等信息传递给 实参、 将所有的实参、返回地址等信息传递给 else 被调用函数保存 被调用函数保存； p= fac (n); 保存； f= fac(n-1) * n; 为被调用函数的局部变量分配存储区 分配存储区； 为被调用函数的局部变量分配存储区； printf("%d",p); 控制转移到被调用函数的入口 f ); 到被调用函数的入口。 将控制转移到被调用函数的入口。 return( } }
第三章 栈和队列
两种特殊的线性表
栈和队列
3.1 栈 3.2 栈的应用举例 3.3 栈与递归 3.4 队列
3.1 栈
定义
栈是仅限定在表的一端操作 的线性表。 的线性表。它的插入和删除都只 能在表的一端进行。 能在表的一端进行。
3.1.1 栈的类型定义
ADT Stack { 数据对象： 数据对象 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： 数据关系 R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： 基本操作： } ADT Stack
栈空的条件： 栈空的条件： S1.top == S1.base S2->top==S2->base 1.构造空栈 构造空栈 void init_stack(stack *s) {s->base=(int*)malloc(M*sizeof(int)); s->top=s->base; s->stacksize=M; }
例如: 例如 #4+ 2 × 3 − 10 / 5 #
–
× + #
3 2 4
OPTR
OPND
算符间的优先级关系
θ1 + – * / （ ） # θ2 + > > > > < > < – > > > > < > < * < < > > < > < / < < > > < > < （ < < < < < < ） > > > > = > # > > > > > =
基本操作： 基本操作：
InitStack(&S)
// 构造一个空栈 S
DestroyStack(&S) // 销毁栈 S GetTop(S, &e) // 弹出 S 栈顶元素。 栈顶元素。 Push(&S, e) //向栈内推入元素 e 向栈内推入元素
栈的表示和实现
栈的存储方式
顺序存储 链表存储
当 '#' : Pop(S,e) //弹出 当 '@': ClearStack(S)//清栈
i l h w
否则 入栈
while (ch != EOF) { //EOF为全文结束符 while (ch != EOF && ch != '\n') { switch (ch) { case '#' : Pop(S,e); break; case '@': ClearStack(S); break;// 重置S为空栈 default : Push(S, ch); break; } ch = getchar(); // 从终端接收下一个字符 } 将从栈底到栈顶的字符传送至调用过程的 数据区； ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar();
递归的要点： 递归的要点：
1. 由系统提供一个信息栈，保留函数调用时 由系统提供一个信息栈， 的相关信息（调用时的信息、返回地址、 的相关信息（调用时的信息、返回地址、 局部变量）； 局部变量）； 2. 每执行递归调用语句时，将有关信息送入 每执行递归调用语句时， 转入函数入口； 栈，转入函数入口； 3. 每当执行到返回语句时，保存计算结果， 每当执行到返回语句时，保存计算结果， 计算结果 释放被调函数的数据区，弹出返回地址 返回地址返 释放被调函数的数据区，弹出返回地址返 回。
例如: 例如 Exp = a × b + (c − d / e) × f 中缀式: #a × b + c − d / e × f#
