《数据结构域算法设计--数据结构-栈与队列 教案》由会员分享，可在线阅读，更多相关《数据结构域算法设计--数据结构-栈与队列 教案（9页珍藏版）》请在金锄头文库上搜索。
1、Thanks Wangqiong of Zhongbei college attaching to Nanjing Normal University3-1第三章第三章 栈栈与与队队列列 栈栈与与队队列：列：限定操作的线性表。第一第一节节 栈栈 一、一、逻辑结逻辑结构构 1 1、 、栈栈的定的定义义 限定只能在表的一端进行插入、删除的线性表。栈顶栈顶 toptop，栈栈底底 bottombottom。后后进进先出先出 LIFO 表(Last In First Out) 实例：“进制数转换”、“表达式求值”、“函数调用关系”、“括号匹配问题”、 “汉诺塔问题”、“迷宫问题” 2 2、基本操作、基
2、本操作 进栈 Push/出栈 Pop 取栈顶元素 GetTop 判别栈空 StackEmpty/栈满 StackFull3 3、 、栈栈的的应应用背景用背景 许多问题的求解分为若干步骤，而当前步骤的解答，是建立在后继步骤的解答基础上的。=问题分解的步骤和求解的步骤次序恰好相反。Thanks Wangqiong of Zhongbei college attaching to Nanjing Normal University3-2二、二、顺顺序存序存储结储结构构 动态顺动态顺序存序存储结储结构：构：存储空间随栈的大小而变化。 #define STACK_INIT_SIZE 100 /初始化时分
3、配的空间 typedef struct /定义栈类型 ElemType *base,*top; /栈底、栈顶指针int stacksize; /栈的存储空间大小 SqStack; SqStack S; /定义一个栈结构1 1、初始化、初始化栈栈 Status SqStack_Init(SqStack if(!S.base) return(OVERFLOW);S.top=S.base; S.stacksize=STACK_INIT_SIZE;return(OK); 栈空： S.top=S.base 栈满： S.top=S.base+S.stacksize2 2、 、进栈进栈 Status SqS
4、tack_Push(SqStack S.top=e;S.top=e; S.top+;S.top+;return(OK); 3 3、出、出栈栈算法算法 Status SqStack_Pop(SqStack S.top-;S.top-; e=S.top;e=S.top;Thanks Wangqiong of Zhongbei college attaching to Nanjing Normal University3-3return(OK); 缺点：空缺点：空间间浪浪费费 思考：二思考：二栈栈合用同一合用同一顺顺序空序空间间？#define maxsize=100 int stackmaxsiz
5、e, top0=0, top1=maxsize-1; int push0(int e) if(top0 top1) return(0);stacktop0=e; top0+;return(1); int push1(int e) if(top0 top1) return(0);stacktop1=e; top1-;return(1); int pop0(int *e) if(top0=0) return(0);top0-; *e=stacktop0;return(1); int pop1(int *e) if(top0=0) return(0);top0+; *e=stacktop1;retu
6、rn(1); 三、三、链栈链栈 typedef struct linknode / 栈中结点类型 ElemType data; struct linknode *link; LinkNode; typedef struct / 定义栈类型 LinkNode *top; / 栈顶指针int stacksize; / 栈的大小(可选) LinkStack; Thanks Wangqiong of Zhongbei college attaching to Nanjing Normal University3-4LinkStack S; 初始化: S.top=NULL; S.stacksize=0
7、栈 空：S.top=NULL 栈 满：系统内存不够 1 1、 、进栈进栈 Status LinkStack_Push(LinkStack p=(LinkNode *)malloc(sizeof(LinkNode); if(p=NULL) return(OVERFLOW); /上溢p-data=e; p-link=S.top; S.top=p; return(OK); 2 2、出、出栈栈 Status LinkStack_Pop(LinkStack if(S.top=NULL) return(UNDERFLOW);p=S.top;e=S.top-data; S.top=S.top-link; f
8、ree(p);return(OK); 3 3、特殊、特殊头结头结点的点的讨论讨论 进栈、出栈是最常用的操作 =链栈的头指针频繁变更 =参数传递的负担 =应约定链栈具有特殊头结点。第二第二节节 栈栈的的应应用用Thanks Wangqiong of Zhongbei college attaching to Nanjing Normal University3-51 1、函数、函数调调用用栈栈f(n)=f(n-1)+f(n-2) int f(int n) int x,y;if(n=1 | n=2) return(1);x=f(n-1);y=f(n-2);return(x+y); main() p
9、rintf(“%dn“,f(5); 2 2、将十、将十进进制数制数转换为转换为八八进进制数。制数。 例如 (1348)10=(2504)8，除 8 取余的过程： nn / 8n mod 8 13481684 168210 2125 202 void Conversion(int dec,int oct) InitStack(S);for(; dec!=0; dec=dec/8)push(S, dec%8); /* 进栈次序是个位、十位. */for(i=0; !StackEmpty(S); i+)octi=pop(S); /* 先出栈者是高位，最后是个位 */ 3 3、括号匹配的、括号匹配的检
10、验检验 Equal( “(a)(b) “ ) : 0 Equal( “(a)(b)“ ) : 1 Equal( “(a)(b)“ ) : -1 int Equal(char s)Thanks Wangqiong of Zhongbei college attaching to Nanjing Normal University3-6 int i=0;for(i=0; si; i+)switch(si) case (: push(si); break;case ): if(StackEmpty(S) return(-1); / )多pop(); break;if(!StackEmpty(S) r
11、eturn(1); / (多return(0); / 完全匹配 4 4、 、进栈进栈出出栈栈的的组组合合问题问题已知操作次序：push(1); pop(); push(2); push(3); pop(); pop( ); push(4); pop( ); 请写出出栈序列。5 5、中、中缀缀表达式求表达式求值值的算法的算法 如： 1 + 2 *（3 + 4 *（5 + 6） 分析：先乘除，后加减；从左到右；先括号内，再括号外。 后算符 前算符( () )# # ( ( # #: / pre_op c 执行 pre_opb=Pop2( a=Pop2( Pop1(Push2(return(GetT
12、op2( / 优先级的处理技巧+ - * / ( ) # int priority77=, , , , / +, , , , / -, , , , , , / *, , , , , , / /, , , , , , , / ), , , , , , =, / #Thanks Wangqiong of Zhongbei college attaching to Nanjing Normal University3-9int OpID(char op) switch (op) case + : return(0);case - : return(1);case * : return(2);case / : return(3);case ( : return(4);case ) : return(5);case # : return(6); char Precede(char op1, char op2) return(priorityOpID(op1)OpID(op2); 测试案例：“#“， “3#“，“3+5#“，“3+5+2#“ “3*5+2#“， “3+5*2#“，“(3+5)*2#“，“(3+5)*(2+1)#“，“(3+5)/2+1)*2#“ 作作业业与上机与上机： 1、表达式求值
