《数据结构栈与队列概要》由会员分享，可在线阅读，更多相关《数据结构栈与队列概要（58页珍藏版）》请在金锄头文库上搜索。
1、数据结构-第三章 栈和队列,1,第三章 栈和队列,栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其插入、删除元素时的运算规则受到更多的限制。 3.1 栈 3.2 栈与递归的实现 3.3 队列 本章学习要点 习题与上机作业,数据结构-第三章 栈和队列,2,线性表,插 入 删 除,Insert(L, i, x) Delete(L, i) (1 i n+1) (1 i n) Insert(L, n+1, x) Delete(L, n) Insert(L, n+1, x) Delete(L, 1),栈 队 列,数据结构-第三章 栈和队列,3,3.1 栈,3.1.1 栈的定义 栈 是一种特
2、殊的线性表，限定插入和删除操作只能在表尾进行。具有后进先出(LIFOLast In First Out )的特点。,an a2 a1,数据结构-第三章 栈和队列,4,定义在栈结构上的基本运算,(1) 生成空栈 InitStack(&S) (2) 销毁已存在的栈 DestroyStack(&S) (3) 清空已存在的栈 ClearStack(&S) (4) 判栈空与否 StackEmpty(S) (5) 求当前栈元素个数(栈长) StackLength(S) (6) 取栈顶元素 GetTop(S，&e) (7) 数据元素入栈 Push(&S, e) (8) 数据元素出栈 Pop(&S, &e)
3、(9) 遍历栈元素 StackTraverse( S, visit(),数据结构-第三章 栈和队列,5,抽象数据类型 栈 的定义,ADT Stack 数据对象：D=ai | ai ElemSet, i=1,2, , n, n0 数据关系：R1= , ai D, i=2, , n 约定an端为栈顶， a1端为栈底 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：销毁栈S。 ADT List,数据结构-第三章 栈和队列,6,3.1.2 栈的顺序存储结构以及操作的实现,一个栈独占一组地址连续的存储单元 类型定义
4、空间基址+栈顶指示+栈容量,Typedef struct SElemType * base; SElemType * top; int stacksize; SqStack;,栈不存在： base=NULL 栈空： top=base 可不用最后一个结点以保证指针正确,数据结构-第三章 栈和队列,7,基本运算实现示例,# define STACK_INIT_SIZE 100; Status InitStack(SqStack /InitStack P47,Status StackEmpty(SqStack S) if (S.top=S.base) return TRUE ; else retur
5、n FALSE; /StackEmpty,(1),(4),数据结构-第三章 栈和队列,8,(5),int StackLength(SqStack S) return S.top-S.base; /StackLength,(6),Status GetTop(SqStack S, SElemType /GetTop P47,(S.top-S.base)/sizeof(SElemType),数据结构-第三章 栈和队列,9,(7),#define STACK_INCREMENT 50 ; Status Push(SqStack return OK /Push,S.top,S.base,栈满状态,数据结
6、构-第三章 栈和队列,10,Status Pop(SqStack /Pop P47,(8),S.top,S.base,S.top,S.base,数据结构-第三章 栈和队列,11,两个栈共享一组地址连续的存储单元,类型定义 数组(栈空间) + 两个栈顶指示,#define DUSTACK_SIZE 100 /两栈的总允许容量 typedef struct SElemType *base; SElemType * top1, * top2; int dustacksize ; DuStack,数据结构-第三章 栈和队列,12,3.1.3 栈的链式存储结构以及操作的实现,类型定义 栈顶指针(链首指针
7、),typedef struct SNode SElemType data; struct SNode * next; SNode, * LinkStack;,LinkStack top ; /栈变量定义,栈空： top=NULL,数据结构-第三章 栈和队列,13,基本运算实现示例,Status Push_LinkStack(LinkStack /Push_LinkStack,p,数据结构-第三章 栈和队列,14,Status Pop_LinkStack(LinkStack /Pop_LinkStack,p,数据结构-第三章 栈和队列,15,3.1.4 栈的应用例,3.1.4.1 数制转换,例
8、 24510= 382+681+580 =3658,分析规律 第一位： N mod 8 245 mod 8 = 5 第二位： 245/8 =30, 30 mod 8=6 第三位： 30/8 =3 , 3 mod 8=3 第四位： 3/8 =0 , 结束,数据结构-第三章 栈和队列,16,void conversion(int N, int B) /对于非负十进制整数N，输出其等值的B进制数 InitStack(S); /初始化栈s while (N) /从右向左产生B进制数的各位 Push(S, N % B); /数字，并将其进栈 N=N/B; while (! StackEmpty(S) /
9、栈非空时退栈输出 Pop(S, e); printf(e); /conversion P48-3.1,算法描述,数据结构-第三章 栈和队列,17,前提假设 表达式语法正确； 表达式结束符为# 算法思想 OPTR栈寄存运算符 OPND栈寄存操作数 1)放入起始符#作为OPTR栈底元素 2)依次读入表达式字符， 操作数：进OPND栈； 运算符：与OPTR.top元素比较优先级后做相应操作； 直至读入#且OPTR栈只剩# 3)OPND栈底所留元素即为所求 例 5+3*(7-2)+11#,OPTR OPND 运算符 操作数,#,5,3,(,7,-,2,+,*,5,15,20,+,11,31,3.1.4
10、.2 整型数简单表达式求值,数据结构-第三章 栈和队列,18,int EvaluateExpression( ) InitStack(OPTR); Push(OPTR,#); InitStack(OPND); scanf(w ); while ( w != # | GetTop (OPTR) != # ) if w整型数 Push(OPND, w); scanf(w); else switch precede(GetTop(OPTR), w) case : Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, operate(a, t
11、heta, b); break; / switch return GetTop(OPND); /EvaluateExpression 算符间的优先关系参下页,数据结构-第三章 栈和队列,19,算符间的优先关系,数据结构-第三章 栈和队列,20,表达式的三种表示方法,设 Exp = S1 OP S2 OP S1 S2 前缀表示法 S1 OP S2 中缀表示法 S1 S2 OP 后缀表示法,例如: Exp = a b + (c d / e) f 前缀式: + a b c / d e f 中缀式: a b + c d / e f 后缀式: a b c d e / f +,数据结构-第三章 栈和队列,
12、21,后缀式的运算规则 运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现 且紧靠它的两个操作数构成一个最小表达式。 先找运算符 再找操作数,例如： a b c d e / f +,ab,d/e,c-d/e,(c-d/e)f,数据结构-第三章 栈和队列,22,从中缀表达式求后缀式,中缀式: a + b c d / e f 后缀式: a b c + d e / f ,在后缀式中，优先权高的运算符领先于优先权低的运算符出现。,设立暂存运算符的栈; 设表达式的结束符为“#”, 予设运算符栈的栈底为“#” 若当前字符是操作数，则直接发送给后缀式; 若当前运算符的优先数高于栈顶运算符，
13、则进栈; 否则，退出栈顶运算符发送给后缀式; “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符,数据结构-第三章 栈和队列,23,a ( b ( c + d / e ) - f ) #,#,a,(,b,(,c,+,d,/,e,/,/,+,+,-,f,-,#,数据结构-第三章 栈和队列,24,void Transform(char suffix , char exp ) InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, c
14、h); else if ( ch!= # ) p+; ch = *p; / while / Transform,switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c) / switch,数据结构-第三章 栈和队列,25,3.1.4.3 迷宫问题,穷举求解,数据结构-第三章 栈和队列,26,数据结构-第三章 栈和队列,27,0 1 2 3 4 5 6 7 8 9 10,求解方法：从入口出发，沿某一方向搜索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直
