《数据结构域算法设计-第B章-栈和队列-2 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第B章-栈和队列-2 课件（31页珍藏版）》请在金锄头文库上搜索。
1、第B章 栈和队列一. 栈（Stack）第B章 栈和队列栈和队列是线性表中两种特殊的情况, 由于它们在应用中的重要地 位, 单独对它们进行讨论.u栈的定义 日常生活中栈的例子只能在一端进行插入和删除运算的线性表称为 栈. 又称作堆栈. 它的结构形式如右图.an a3 a2 a1n n-1 2 1 0栈顶栈底进栈 (入栈)出栈 (退栈)由于栈的这种操作特性, 将其称为后进先出表 (Last In First Out, 简称LIFO). 如子弹夹, 硬币夹, 叠放盘子 等. 用线性表表示进栈和出栈 设线性表(a,b,c), 元素c的一端为栈顶. 若d进栈: (a,b,c,d); 若c出栈: (a,b
2、). 若栈中没有元素 ,则称为空栈. u栈的抽象数据类型 假如栈的存储类型用StackType表示, 栈的元素类型为ElemType; 操作部分包括: 进栈、出栈、读取栈顶元素、检查栈是否为空 等.ADT STACK is Data: StackType S= ai | aiElemType, i=1,2,n, n0 Operations: void InitStack (StackType/ 初始化栈S, 将其置为空. void ClearStack (StackType / 清除栈中所有元素,使其成为空. intStackEmpty (StackType/ 栈S是否为空,若是,返回1,否则
3、0. intStackFull (StackType/ 栈S是否已满,若是,返回1,否则0. ElemType Peek (StackType/ 返回S的栈顶元素,但不移动栈顶. intPush (StackType / 将元素item 压到栈S中(进栈). 若成功返回1, 若栈已满返回0. ElemType Pop (StackType/ 删除S的栈顶元素并返回该元素. end STACK栈的数据存储采用顺序存储和链接存储结构.第B章 栈和队列二. 栈的顺序存储结构和操作实现u顺序存储的结构定义l采用静态数组存储元素 数组名: stack , 整型量top指示栈顶位置. 栈结构定义如下: s
4、truct Stack ElemType stackMaxSize; int top; ;栈S=(a,b,c,d)的 顺序存储结构.栈结构定义如下: struct Stack ElemType *stack;/ 动态数组的头指针 int top;/ 栈顶指针 int MaxSize;/ 动态数组的长度 ;l采用动态数组存储元素当top=-1时表示 栈空. 栈顶栈底d c b aS.stack :top=35 4 3 2 1 0MaxSize-1第B章 栈和队列u顺序存储栈的算法实现(动态数组)第B章 栈和队列l 初始化栈 (分配内存) void InitStack (Stack S.stack
5、=new ElemTypeS.MaxSize; S.top = -1; void ClearStack (Stack S.stack = NULL; S.MaxSize = 0; S.top = -1; l 清除栈中的元素, 释放内存l 向栈中插入元素l 检查栈是否为空 int StackEmpty (Stack void Push (Stack else S.MaxSize *= 2; int k = sizeof (ElemType); S.stack = (ElemType *) realloc ( S.stack, S.MaxSize * k); S.stack+S.top = ite
6、m; u顺序存储栈的算法实现(动态数组)(续 )第B章 栈和队列l删除栈顶元素并返回 ElemType Pop (Stack delete cp; l清除栈中的元素,使成为空栈第B章 栈和队列l检查栈是否为空 int StackEmpty (LNode* HS) return (HS = NULL); l向链栈中插入元素 void Push (LNode* pNew-data = item; pNew-next = HS; HS = pNew; u链接存储栈的算法实现（续）第B章 栈和队列l从链栈中删除元素并返回 ElemType Pop (LNode* ElemType temp = p-d
7、ata; delete p; return temp; l读取栈顶元素, 栈顶指针不变 ElemType Peek (LNode* HS) if (HS = NULL) cerrdata; u算法的时间复杂度进栈、出栈以及读取栈顶元素都是在栈顶进行操作, 因此, 时间复 杂度为O(1).四. 栈的简单应用举例第B章 栈和队列l例B.1 编写一个算法, 检查C+程序中 , , ( ) 是否配对,若能够 配对,返回1; 否则返回0. 注: 对 或“ “内的括号不进行匹配检查.#define LNLEN255 int BracketsCheck (char *fname) ifstream fin
8、(fname, ios : in | ios : nocreate); / 建立输入文件对象 if (! fin) cerr c; cout运算符读入一个字符c(空格字符自动跳过), 该字符只可能 是 + - * / . 09 中的一个, 否则表达式出错; 若c为09或.时, 退回该字符, 用输入实数, 并将其压入S栈; 若是某运算符,从S中弹出两实数, 作运算, 将结果压入S栈; 读入下一个字符, 直到字符为止. 最后结果在S栈中.u后缀表达式的求值的算法实现第B章 栈和队列/ 若求值成功, 返回该值, 并置flag为0; 否则,表达式错误, 置flag为-1. double EvArith
9、metic (char *str, int/ 存放操作数中间结果的链接栈(采用类模板). S.InitStack ( );flag = 0; istrstream ins (str);/ 把str定义为输入字符串流对象ins. char c;double x; ins c;/ 从ins对象读入一个字符. 注意,0是无法读到的. while (c != ) switch (c) case +:x = S.Pop( ) + S.Pop ( );break; case -:x = -S.Pop( ) + S.Pop ( );break; case *:x = S.Pop( ) * S.Pop ( )
10、;break; case /:x = S.Pop( ); if (x != 0.0) x = S.Pop( ) / x; else cerr x;/ 从输入流中读入一个浮点数. / end switch (c).u后缀表达式的求值的算法实现(续)第B章 栈和队列S.Push (x);/ 把操作数的中间结果压栈. ins c;/ 读入下一个字符. / end while (c).if (! S.StackEmpty ( )/ 如果栈S非空. x = S.Pop (); if (S.StackEmpty( ) return x; else cerr R;/ 存放运算符的栈. 采用参数为char的模
11、板类. R.InitStack ( ); R.Push (); int i = 0;/ 指示字符串s1的位置. int j = 0;/ 指示字符串s2的位置. char c = s1i, w; / 考虑单目运算符+, - 的情况 while (c = | c=t | c=n) c = s1+i;/ 跳过前导的空白符 if (c = + | c = -)/ 单目运算符 + 或 s2j+ = 0;s2j+ = ; R.Push (c);c = s1+i; / end: 单目运算符+, - while (c != 0 ) if (c = | c=t | c=n)c = s1+i; else if (
12、c = ( )/ 对于左括号,直接进栈. R.Push (c);c = s1+i; / 考虑单目运算符+, - 的情况u中缀转换成后缀表达式的实现(续-1)第B章 栈和队列while (c = | c=t | c=n) c = s1+i;/ 跳过前导的空白符 if (c = + | c = -)/ 单目运算符 + 或 s2j+ = 0;s2j+ = ; R.Push (c);c = s1+i; / end: 单目运算符+, - else if (c = ) ) / 对于右括号,将栈中的内容依次出栈,写入到s2中,直到 ( 为止. while (R.Peek (w) R.Pop ( );/ 删除
13、栈顶的左括号. c = s1+i; else if (c=+ | c=- | c=* | c=/) / 对四则运算,使栈中不低于c优先级的运算符依次出栈写入到s2中. R.Peek (w); while (Precede(w) = Precede(c) s2j+ = w;R.Pop ( );R.Peek (w); R.Push (c);c = s1+i; u中缀转换成后缀表达式的实现(续-2)第B章 栈和队列else if (c=0 const M=6, N=8;/ 迷宫的行数和列数. int mazeM+2N+2;/ 迷宫各位置的描述数据. int markM+2N+2;/ 迷宫各位置被访问
14、的标记. int SeekPath (int x, int y); void main (void) int i, j; cout mazeij; for (j=0; jN+2; j+) maze0j = mazeM+1j = 1; / 增加围墙数据. for (i=1; iM+1; i+) mazei0 = mazeiN+1 = 1; for (i=0; iM+2; i+) / 初始化mark 数组. for (j=0; jN+2; j+) markij = 0; mark11 = 1; / 从入口点(1,1)进入迷宫. if (SeekPath (1,1) cout “(1,1)“ end
15、l; elsecout “No Path !“ endl; l 例B.4 (续)第B章 栈和队列int SeekPath (int x, int y) / 定义东-南-西-北4个方向的行、列号的移动量. static int move42 = 0,1, 1,0, 0,-1, -1,0 ; if (x=M for (int i=0; i4; i+)/ 按四个方向搜索前进路径 int g = x + movei0;/ 下一个位置的行号 int h = y + movei1;/ 下一个位置的列号 if (mazegh=0 / 设置改位置已被访问的标记 if (SeekPath (g,h) cout “(“ g “,“ h “), “; return 1;
