数据结构栈和队列.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数据构造栈和队列,数据构造栈和队列数据构造栈和队列栈,栈,栈,的定义,栈的顺序存储构造及其根本运算实现,栈的链式存储构造及其根本运算的实现,栈,的应用例子,栈,3.1.1 栈的定义,栈是一种只能在一端进展插入或删除操作的线性表。表中允许进展插入、删除操作的一端称为栈顶。,栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。,当栈中没有数据元素时,称为空栈。,栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。,栈顶,栈底,出栈,进栈,栈示意图,例,3.1,设有,4,个元素,a,、,b,、,c,、,d,进栈,给出它们所有可能的出栈次序。,答,:,所有可能的出栈次序如下,:,abcd abdc acbd acdb,adcb bacd badc bcad,bcda bdca cbad cbda,cdba dcba,【例】,例3.2 设一个栈的输入序列为A,B,C,D,那么借助一个栈所得到的输出序列不可能是,(A)A,B,C,D (B)D,C,B,A,(C)A,C,D,B (D)D,A,B,C,答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以此题答案为D。,例3.3 一个栈的进栈序列是1,2,3,n,其输出序列是p1,p2,pn,假设p1=n,那么pi的值 。,(A)i (B)n-i,(C)n-i+1 (D)不确定,答:当p1=n时,输出序列必是n,n-1,3,2,1,那么有:,p2=n-1,p3=n-2,pn=1,推断出pi=n-i+1,所以此题答案为C。,例3.4 设n个元素进栈序列是1,2,3,n,其输出序列是p1,p2,pn,假设p1=3,那么p2的值 。,(A)一定是2(B)一定是1,(C)不可能是1 (D)以上都不对,答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,n,但一定不能是1。所以此题答案为C。,(1)初始化栈InitStack(&s):构造一个空栈s。,(2)销毁栈ClearStack(&s):释放栈s占用的存储空间。,(3)求栈的长度StackLength(s):返回栈s中的元素个数。,(4)判断栈是否为空StackEmpty(s):假设栈s为空,那么返回真；否那么返回假。,栈的几种根本运算,(5),进栈,Push(&S,e):,将元素,e,插入到栈,s,中作为栈顶元素。,(6),出栈,Pop(&s,&e):,从栈,s,中退出栈顶元素,并将其值赋给,e,。,(7),取栈顶元素,GetTop(s,&e):,返回当前的栈顶元素,并将其值赋给,e,。,(8),显示栈中元素,DispStack(s):,从栈顶到栈底顺序显示栈中所有元素。,栈的几种根本运算,假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,那么可用以下方式来定义栈类型SqStack:,typedef struct,ElemType dataMaxSize；,int top；/*栈指针*/,SqStack；,3.1.2 栈的顺序存储构造及其根本运算实现,顺序栈进栈和出栈示意图,在顺序栈中实现栈的根本运算算法:,(1),初始化栈,initStack(&s),建立一个新的空栈,s,实际上是将栈顶指针指向,-1,即可。对应算法如下,:,void InitStack(SqStack*&s),s=(SqStack*)malloc(sizeof(SqStack);,s-top=-1;,在顺序栈中实现栈的根本运算算法:,(2),销毁栈,ClearStack(&s),释放栈,s,占用的存储空间。对应算法如下,:,void ClearStack(SqStack*&s),free(s);,在顺序栈中实现栈的根本运算算法:,(3),求栈的长度,StackLength(s),返回栈,s,中的元素个数,即栈指针加,1,的结果。对应算法如下,:,int StackLength(SqStack*s),return(s-top+1);,在顺序栈中实现栈的根本运算算法:,(4),判断栈是否为空,StackEmpty(s),栈,S,为空的条件是,s-top=-1,。对应算法如下,:,int StackEmpty(SqStack*s),return(s-top=-1);,在顺序栈中实现栈的根本运算算法:,(5),进栈,Push(&s,e),在栈不满的条件下,先将栈指针增,1,然后在该位置上插入元素,e,。对应算法如下,:,int Push(SqStack*&s,ElemType e),if(s-top=MaxSize-1)return 0;,/*,栈满的情况,即栈上溢出*,/,s-top+;,s-datas-top=e;,return 1;,在顺序栈中实现栈的根本运算算法:,(6),出栈,Pop(&s,&e),在栈不为空的条件下,先将栈顶元素赋给,e,然后将栈指针减,1,。对应算法如下,:,int Pop(SqStack*&s,ElemType&e),if(s-top=-1)return 0;,/*,栈为空的情况,即栈下溢出*,/,e=s-datas-top;,s-top-;,return 1;,在顺序栈中实现栈的根本运算算法:,(7),取栈顶元素,GetTop(s),在栈不为空的条件下,将栈顶元素赋给,e,。对应算法如下,:,int GetTop(SqStack*s,ElemType&e),if(s-top=-1)return 0;,/*,栈为空的情况,即栈下溢出*,/,e=s-datas-top;,return 1;,在顺序栈中实现栈的根本运算算法:,(8),显示栈中元素,DispStack(s),从栈顶到栈底顺序显示栈中所有元素。对应算法如下,:,void DispStack(SqStack*s),int i;,for(i=s-top;i=0;i-),printf(%c,s-datai);,printf(n);,3.1.3 栈的链式存储构造及其根本运算的实现,采用链式存储的栈称为链栈,这里采用单链表实现。,链栈的优点是不存在栈满上溢的情况。,我们规定栈的所有操作都是在单链表的表头进展的,以下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、an。,链栈示意图,链栈中数据结点的类型,LiStack,定义如下,:,typedef struct linknode,ElemType data;,/*,数据域*,/,struct linknode*next;,/*,指针域*,/,LiStack;,s,链栈的根本运算,(1)初始化栈initStack(&s),建立一个空栈s。实际上是创立链栈的头结点,并将其next域置为NULL。对应算法如下:,void InitStack(LiStack*&s),s=(LiStack*)malloc(sizeof(LiStack);,s-next=NULL;,链栈的根本运算,(2),销毁栈,ClearStack(&s),释放栈,s,占用的全部存储空间。对应算法如下,:,void ClearStack(LiStack*&s),LiStack*p=s-next;,while(p!=NULL),free(s);,s=p;,p=p-next;,链栈的根本运算,(3)求栈的长度StackLength(s),从第一个数据结点开场扫描单链表,用i记录访问的数据结点个数,最后返回i值。对应算法如下:,int StackLength(LiStack*s),int i=0;,LiStack*p;,p=s-next;,while(p!=NULL),i+;p=p-next;,return(i);,s,链栈的根本运算,(4),判断栈是否为空,StackEmpty(s),栈,S,为空的条件是,s-next=NULL,即单链表中没有数据结点。对应算法如下,:,int StackEmpty(LiStack*s),return(s-next=NULL);,链栈的根本运算,(5),进栈,Push(&s,e),将新数据结点插入到头结点之后。对应算法如下,:,void Push(LiStack*&s,ElemType e),LiStack*p;,p=(LiStack*)malloc(sizeof(LiStack);,p-data=e;,p-next=s-next;/*,插入*,p,结点作为第一个数据结点*,/,s-next=p;,链栈的根本运算,(6),出栈,Pop(&s,&e),在栈不为空的条件下,将头结点后继数据结点的数据域赋给,e,然后将其删除。对应算法如下,:,int Pop(LiStack*&s,ElemType&e),LiStack*p;,if(s-next=NULL)return 0;/*,栈空的情况*,/,p=s-next;/*p,指向第一个数据结点*,/,e=p-data;,s-next=p-next;,free(p);,return 1;,链栈的根本运算,(7),取栈顶元素,GetTop(s),在栈不为空的条件下,将头结点后继数据结点的数据域赋给,e,。对应算法如下,:,int GetTop(LiStack*s,ElemType&e),if(s-next=NULL)return 0;/*,栈空的情况*,/,e=s-next-data;,return 1;,链栈的根本运算,(8)显示栈中元素DispStack(s),从第一个数据结点开场扫描单链表,并输出当前访问结点的数据域值。对应算法如下:,void DispStack(LiStack*s),LiStack*p=s-next;,while(p!=NULL),printf(%c,p-data);,p=p-next;,printf(n);,【例】括号配对,假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。,解:设置一个括号栈,扫描表达式：遇到左括号(包括(、和)时进栈,遇到右括号时,假设栈是相匹配的左括号,那么出栈,否那么,返回0。,假设表达式扫描完毕,栈为空,返回1表示括号正确匹配,否那么返回0。,【例】括号配对,int correct(char exp,int n),char stMaxSize;,int top=-1,i=0,tag=1;,while(i-1),tag=0;/*假设栈不空,那么不配对*/,return(tag);,【例】括号配对,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,【例】进制转换-十进制到二进制,算法思想如下：当N0时重复1，2,1 假设 N0，那么将N%r 压入栈s中，执行2;,假设N=0，将栈s的内容依次出栈，算法完毕。,2 用N/r 代替 N,高,低,算 法 一,【例】进制转换-十进制到二进制,typedef int datatype;,void conversion(int N，int r),SeqStack s;,datetype x;,Init_SeqStack(,while(N),Push_SeqStack(,N=N/r;,while (!Empty_SeqStack(&s),Pop_SeqStack(,printf(“%d，x);,算 法 二,【例】进制转换-十进制到二进制,#define L 10,void conversion(int N，int r),int sL,top;,int x;,top=-1;,while(N),s+top=N%r;,N=N/r;,while(top!=-1),x=stop-;,printf(“%d,x);,例,利用栈，将二进制转换为十进制数,分析：每个二进制数转换成相应的十进制数方法如下：,(X,n,X,n-1,X,3,X,2,X,1,),2,=X,1,*,20+X,2,*,21+X,n,*,2(n-1),由于栈具有后进先出的特性，输入二进制数11001001,1,0,0,1,0,0,1,1,base,top,例,利用栈，将二进制转换为十进制数,二进制到八进制,仔细观察二进制跟十六进制的对应关系,可见一个字节用两个十六进制数可以表示完整，也大大的节省了显示空间。,那八进制呢？因为早期的计算机系统都是三的倍数，所以用八进制比较方便。,在进展二进制到八进制的转换时，要将二进制数的每三位抓换成一个八进制数来表示，然后按顺序输出即可。,0,0,1,1,10,2,11,3,100,4,101,5,110,6,111,7,1000,8,1001,9,1010,A,1011,B,1100,C,1101,D,1110,E,1111,F,从二进制到八进制,1,0,0,1,0,0,1,1,base,top,1,001,1,base,top,从二进制到八进制,1,0,0,1,1,base,top,1,1,001,1,base,top,从二进制到八进制,1,1,base,top,3,1,1,11,3,base,top,参考例题,bin_dec.c,3.1.4 栈的应用例子-表达式求值,1.表达式求值,这里限定的表达式求值问题是:用户输入一个包含“+、“-、“*、“/、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。,3.1.4 栈的应用例子-表达式求值,中缀表达式:在程序语言中,运算符位于两个操作数中间的表达式.例如：,1+2*3,遵循“先乘除,后加减,从左到右计算,先括号内,后括号外的规那么。,因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。,例-表达式求值,后缀表达式:运算符在操作数的后面,如1+2*3的后缀表达式为123*+。,在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。,对后缀表达式求值过程是:从左到右读入后缀表达式,假设读入的是一个操作数,就将它入数值栈,假设读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个操作数),假设为x和y,计算x op y之值,并将计算结果入数值栈；对整个后缀表达式读入完毕时,栈顶元素就是计算结果。,例-表达式求值,算术表达式求值过程是,:,先将算术表达式转换成后缀表达式,然后对该后缀表达式求值。,假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组,str,中,其后缀表达式存放在字符型数组,exp,中,在将算术表达式转换成后缀表达式的过程中用一个字符型数组,op,作为栈。将算术表达式转换成后缀表示的方法如下,:,中缀表达式后缀表达式,while(从exp读取字符ch,ch!=0),假设ch为数字,将后续的所有数字均依次存放到postexp中,并以字符“#标志数值串完毕。,假设ch为左括号“(,那么将此括号进栈到运算符栈op中。,假设ch为右括号“),那么将运算符栈op中左括号“(以前的运算符依次出栈并存放到postexp中,然后将左括号“(删除。,假设ch运算符优先级小于或等于op栈顶运算符的优先级(除栈顶运算符为“(外)的优先级,那么依次出栈并存入到postexp中,然后将ch进栈。,假设字符串exp扫描完毕,那么将运算栈op中的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp。,对于表达式“(56-20)/(4+2),其转换成后缀表达式的过程 如下：,exp,操作过程,op,postexp,(56-20)/(4+2),遇到,ch,为,“,(,”,将此括号进栈,op,。,(,56-20)/(4+2),遇到,ch,为数字,将,56,存入,postexp,中,并插入一个字符,“,#,”,。,(,56#,-20)/(4+2),遇到,ch,为,“,-,”,由于,op,中,“,(,”,以前没有字符,则直接将,ch,进栈,op,中。,(-,56#,20)/(4+2),遇到,ch,为数字,将,20#,存入数组,exp,中。,(-,56#20#,exp,操作过程,op,postexp,)/(4+2),遇到,ch,为,“,),”,则将栈,op,中,“,(,”,以前的字符依次出栈并存入,postexp,中,然后将,“,(,”,删除。,56#20#-,/(4+2),遇到,ch,为,“,/,”,将将,ch,进栈,op,中。,/,56#20#-,(4+2),遇到,ch,为,“,(,”,将此括号进栈,op,中。,/(,56#20#-,4+2),遇到,ch,为数字,将,4#,存入数组,postexp,中。,/(,56#20#-4#,exp,操作过程,op,postexp,+2),遇到,ch,为,“,+,”,由于,op,栈顶运算符为,“,(,”,则直接将,ch,进栈,op,中。,/(+,56#20#-4#,2),遇到,ch,为数字,将,2#,存入,postexp,中。,/(+,56#20#-4#2#,),遇到,ch,为,“,),”,则将栈,op,中,“,(,”,以前的字符依次出栈并存放到,postexp,中,然后将,“,(,”,出栈。,/,56#20#-4#2#+,str,扫描完毕,则将栈,op,中的所有运算符依次弹出并存放到,postexp,中,得到后缀表达式。,56#20#-4#2#+/,将算术表达式,str,转换成后缀表达式,exp,void trans(char str,char exp),struct,char dataMaxSize;,/*,存放运算符*,/,int top;,/*,栈指针*,/,op;,/*,定义运算符栈*,/,char ch;,int i=0,t=0;,/*t,作为,exp,的下标,i,作为,str,的下标*,/,op.top=-1;,ch=stri;i+;,while(ch!=0),/*str,表达式未扫描完时循环*,/,switch(ch),case(:,/*,判定为左括号*,/,op.top+;op.dataop.top=ch;break;,case):,/*,判定为右括号*,/,while(op.dataop.top!=(),expt=op.dataop.top;,op.top-;t+;,op.top-;break;,case+:case-:,/*,判定为加或减号*,/,while(op.top!=-1&op.dataop.top!=(),expt=op.dataop.top;,op.top-;t+;,op.top+;op.dataop.top=ch;break;,case*:case,/:/*,判定为,*,或,/,号*,/,while(op.dataop.top=*|op.dataop.top=/),expt=op.dataop.top;,op.top-;t+;,op.top+;op.dataop.top=ch;break;,case :break;,/*,过滤掉空格*,/,default:,while(ch=0&ch=0&ch 、/、%+、-；,有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进展；,乘方连续出现时先算最右面的；,【例】中缀表达式求解,处理过程：,需要两个栈：对象栈s1和算符栈s2。,当自左至右扫描表达式的每一个字符时，假设当前字符是运算对象，入对象栈，是运算符时，假设这个运算符比栈顶运算符高那么入栈，继续向后处理，假设这个运算符比栈顶运算符低那么从对象栈出栈两个运算量，从算符栈出栈一个运算符进展运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到完毕符。,每个运算符栈内、栈外的级别如下：,算符 栈内级别 栈外级别,3 4,*、/、%2 2,+、-1 1,(0 4,-1 -1,【例】中缀表达式求解,进栈的原那么：,要保证栈顶的运算符的优先级最高，当遇到的运算符的优先级别假设高于栈顶运算符的优先级别时，那么进栈作为栈顶元素，否那么，将栈顶元素退栈输出，然后再把优先级低的运算符进栈。,对象栈,S1,算符栈,S2,A,A,*,A,*,(,A,*(,B,A B,*(,-,A B,*(-,C,A B C,*(-,),A B-C,*(,A*(B-C),【例】A*B-C+D 的中缀表达式求值过程,【,练习,】,中缀表达式求解,用中缀表达式法求表达式,3*24+2*2-*3-5 的值,3,3,(,3,入栈,s1,*,3,(*,*,入栈,s2,2,3,，,2,(*,2,入栈,s1,3,，,2,(*,入栈,s2,(,3,，,2,(*(,(,入栈,s2,4,3,，,2,，,4,(*(,4,入栈,s1,+,3,，,2,，,4,(*(+,+,入栈,s2,2,3,，,2,，,4,，,2,(*(+,2,入栈,s1,*,3,，,2,，,4,，,2,(*(+*,*,入栈,s2,2,3,，,2,，,4,，,2,，,2,(*(+*,2,入栈,s1,-,3,，,2,，,4,，,4,(*(+,做,2+2=4,，结果入栈,s1,3,，,2,，,8,(*(,做,4+4=8,，结果入栈,s2,3,，,2,，,8,(*(-,-,入栈,s2,3,，,2,，,8,，,1,(*(-,1,入栈,s1,*,3,，,2,，,8,，,1,(*(-*,*,入栈,s2,3,3,，,2,，,8,，,1,，,3,(*(-*,3,入栈,s1,),3,，,2,，,8,，,3,(*(-,做,1*3,，结果,3,入栈,s1,3,，,2,，,5,(*(,做,8-3,，结果,5,入栈,s2,3,，,2,，,5,(*,(,出栈,-,3,，,32,(*,做,25,，结果,32,入栈,s1,96,(,做,3*32,，结果,96,入栈,s1,96,(-,-,入栈,s2,5,96,，,5,(-,5,入栈,s1,结束符,91,(,做,96-5,结果,91,入栈,s1,3*24+2*2-*3-5,3,3,(,3,入栈,s1,*,3,(*,*,入栈,s2,2,3,，,2,(*,2,入栈,s1,3,，,2,(*,入栈,s2,(,3,，,2,(*(,(,入栈,s2,4,3,，,2,，,4,(*(,4,入栈,s1,+,3,，,2,，,4,(*(+,+,入栈,s2,2,3,，,2,，,4,，,2,(*(+,2,入栈,s1,*,3,，,2,，,4,，,2,(*(+*,*,入栈,s2,2,3,，,2,，,4,，,2,，,2,(*(+*,2,入栈,s1,-,3,，,2,，,4,，,4,(*(+,做,2+2=4,，结果入栈,s1,3,，,2,，,8,(*(,做,4+4=8,，结果入栈,s2,3,，,2,，,8,(*(-,-,入栈,s2,3,，,2,，,8,，,1,(*(-,1,入栈,s1,*,3,，,2,，,8,，,1,(*(-*,*,入栈,s2,3,3,，,2,，,8,，,1,，,3,(*(-*,3,入栈,s1,),3,，,2,，,8,，,3,(*(-,做,1*3,，结果,3,入栈,s1,3,，,2,，,5,(*(,做,8-3,，结果,5,入栈,s2,3,，,2,，,5,(*,(,出栈,-,3,，,32,(*,做,25,，结果,32,入栈,s1,96,(,做,3*32,，结果,96,入栈,s1,96,(-,-,入栈,s2,5,96,，,5,(-,5,入栈,s1,结束符,91,(,做,96-5,结果,91,入栈,s1,【例】逆波兰表达式,(1-2)*(4+5)，用逆波兰表示法：1 2 4 5+*,【例】逆波兰表达式,(1-2)*(4+5)，用逆波兰表示法：1 2 4 5+*,数字1和2进栈，遇到减号运算符那么弹出两个元素进展运算并把结果入栈。,2,1,base,top,-1,base,top,【例】逆波兰表达式,(1-2)*(4+5),，用逆波兰表示法：,1 2 4 5+,*,4,和,5,入栈，遇到加号运算符，,4,和,5,弹出栈，相加后将结果,9,入栈。,5,4,-1,base,top,9,-1,base,top,【例】逆波兰表达式,(1-2)*(4+5)，用逆波兰表示法：1 2 4 5+*,然后又遇到乘法运算符，将9和-1弹出栈进展乘法计算，此时栈空并无数据压栈，-9为最终运算结果！,9,-1,base,top,base,top,中缀表达式,-,逆波兰表达式,a+b a b+,a+(b-c)a b c-+,a+(b-c)*d a b c-d*+,a+d*(b-c)a d b c-*+,【例】中缀表达式转换为后缀表达式,【例】中缀表达式转换为后缀表达式,在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。,具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进展当前的计算，然后把结果再入栈，直到整个表达式完毕，这时送入栈顶的值就是结果。,对象栈,S1,输出,A,A,*,*,A,(,*(,A,B,*(,AB,-,*(-,AB,C,*(-,ABC,),*,ABC-,+,+,ABC-*,D,+,ABC-*D,完成,ABC-*D+,A*(B-C)+D,【例】中缀表达式转换为后缀表达式,【,练习,】,中缀表达式转换为后缀表达式,求3*24+2*2-*3-5 的后缀表达式法,3,入栈,3,，,入栈,3,，,2,，,4,入栈,3,，,2,，,4,，,2,入栈,3,，,2,，,4,，,2,，,2,入栈,3,，,2,，,4,，,4,计算，将结果入栈,3,，,2,，,8,计算，将结果入栈,3,，,2,，,8,，,1,入栈,3,，,2,，,8,，,1,，,3,入栈,3,，,2,，,8,，,3,计算，将结果入栈,3,，,2,，,5,计算，将结果入栈,3,，,32,计算,25,，将结果,32,入栈,*,96,计算,32,，将结果,96,入栈,5,96,，,5,5,入栈,-,96,计算,96-5,，结果入栈,结束符,空,结果出栈,3*24+2*2-*3-5,例求解迷宫问题,求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解的方法,即从入口出发,顺某一方向向前试探,假设能走通,那么继续往前走；否那么沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。,首先用如下图的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。,例求解迷宫问题,例求解迷宫问题,例求解迷宫问题,为了表示迷宫,设置一个数组,mg,其中每个元素表示一个方块的状态,为,0,时表示对应方块是通道,为,1,时表示对应方块为墙,如图所示的迷宫,对应的迷宫数组,mg,如下,:,int mgM+1N+1=/*M=10,N=10*/,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;,例求解迷宫问题,对于迷宫中的每个方块,有上下左右四个方块相邻,如图所示,第,i,行第,j,列的当前方块的位置为,(i,j),规定上方方块为方位,0,顺时针方向递增编号。在试探过程中,假设从方位,0,到方位,3,的方向查找下一个可走的方块。,为了便于回溯,对于可走的方块都要进栈,并试探它的下一可走的方位,将这个可走的方位保存到栈中,为此,将栈定义为,:,struct,int i;,/*,当前方块的行号*,/,int j;,/*,当前方块的列号*,/,int di;,/*di,是下一可走方位的方位号*,/,StackMaxSize;,/*,定义栈*,/,int top=-1;,/*,初始化栈指针*,/,例求解迷宫问题,求解迷宫(1,1)到(M-2,N-2)路径的过程是:,先将入口进栈(初始方位设置为-1),在栈不空时循环:取栈顶方块(不退栈),假设该方块是出口,那么输出栈中方块即为路径。否那么,找下一个可走的相邻方块,假设不存在这样的方块,那么退栈。假设存在这样的方块,那么将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈(初始方位设置为-1)。,为了保证试探的可走相邻方块不是已走路径上的方块,如(i,j)已进栈,在试探(i+1,j)的下一可走方块时,又试探到(i,j),这样可能会引起死循环,为此,在一个方块进栈后,将对应的mg数组元素值改为-1(变为不可走的相邻方块),当退栈时(表示没有可走相邻方块),将其恢复为0。,void mgpath()/*,路径为,:(1,1)-(M-2,N-2)*/,int i,j,di,find,k;,top+;/*,初始方块进栈*,/,Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;,while(top-1)/*,栈不空时循环*,/,i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;,if(i=M-2&j=N-2)/*,找到了出口,输出路径*,/,printf(,迷宫路径如下,:n);,for(k=0;k=top;k+),printf(t(%d,%d),Stackk.i,Stackk.j);,if(k+1)%5=0)printf(n);,printf(n);,return;,例求解迷宫问题,find=0;,while(direar+1)%MaxSize=q-front,队空条件仍为:,q-rear=q-front,队列的顺序存储方案三-循环队,循环队的入队和出队操作示意图,队列的顺序存储方案三-循环队,循环队的根本运算,(1),初始化队列,InitQueue(&q),构造一个空队列,q,。将,front,和,rear,指针均设置成初始状态即,0,值。对应算法如下,:,void,InitQueue(SqQueue*&q),q=(SqQueue*)malloc(sizeof(SqQueue);,q-front=q-rear=0;,循环队的根本运算,(2),销毁队列,ClearQueue(&q),释放队列,q,占用的存储空间。对应算法如下,:,void ClearQueue(SqQueue*&q),free(q);,循环队的根本运算,(3)判断队列是否为空QueueEmpty(q),假设队列q满足q-front=q-rear条件,那么返回1；否那么返回0。对应算法如下:,int QueueEmpty(SqQueue*q),return(q-front=q-rear);,循环队的根本运算,(4),入队列,enQueue(q,e),在队列不满的条件下,先将队尾指针,rear,循环增,1,然后将元素添加到该位置。对应算法如下,:,int enQueue(SqQueue*&q,ElemType e),if(q-rear+1)%MaxSize=q-front),/*,队满*,/,return 0;,q-rear=(q-rear+1)%MaxSize;,q-dataq-rear=e;,return 1;,循环队的根本运算,(5),出队列,deQueue(q,e),在队列,q,不为空的条件下,将队首指针,front,循环增,1,并将该位置的元素值赋给,e,。对应算法如下,:,int deQueue(SqQueue*&q,ElemType&e),if(q-front=q-rear)/*,队空*,/,return 0;,q-front=(q-front+1)%MaxSize;,e=q-dataq-front;,return 1;,【,思考,】,上溢现象和假溢出现象,什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？,答:在队列的顺序存储构造中,设头指针为front,队尾指针rear,队的容量(存储空间的大小)为MaxSize。当有元素参加到队列时,假设 rear=MaxSize(初始时rear=0)那么发生队列的上溢现象,该元素不能参加队列。,特别要注意的是队列的假溢出现象:队列中还有剩余空间但元素却不能进入队列,造成这种现象的原因是由于队列的操作方法所致。,解决队列上溢的方法,解决队列上溢的方法有以下几种:,(1)建立一个足够大的存储空间,但这样做会造成空间的使用效率降低。,(2)当出现假溢出时可采用以下几种方法:,采用平移元素的方法:每当队列中参加一个元素时,队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动)；,解决队列上溢的方法,每当删除一个队头元素时,那么依次移动队中的元素,始终使front指针指向队列中的第一个位置；,采用循环队列方式:把队列看成一个首尾相接的循环队列,在循环队列上进展插入或删除运算时仍然遵循“先进先出的原那么。,【例】,对于顺序队列来说,如果知道队首元素的位置和队列中元素个数,那么队尾元素所在位置显然是可以计算的。也就是说,可以用队列中元素个数代替队尾指针。编写出这种循环顺序队列的初始化、入队、出队和判空算法。,解:当队首元素的位置front和队列中元素个数count后:,队空的条件为:count=0,队满的条件为:count=MaxSize,计算队尾位置rear:,rear=(front+count)%MaxSize,对应的算法如下,:,typedef struct,ElemType dataMaxSize;,int front;,/*,队首指针*,/,int count;,/*,队列中元素个数*,/,QuType;,/*,队列类型*,/,void InitQu(QuType*&q),/*,队列,q,初始化*,/,q=(QuType*)malloc(sizeof(QuType);,q-front=0;,q-count=0;,int EnQu(QuType*&q,ElemType x),/*,进队*,/,int rear;,if(q-count=MaxSize)return 0;,/*,队满上溢出*,/,else,rear=(q-front+q-count+MaxSize)%MaxSize;,/*,求队尾位置*,/,rear=(rear+1)%MaxSize;,/*,队尾位置进,1*/,q-datarear=x;,q-count+;,return 1;,int DeQu(QuType*&q,ElemType&x),/*,出队*,/,if(q-count=0),/*,队空下溢出*,/,return 0;,else,q-front=(q-front+1)%MaxSize;,x=q-dataq-front;,q-count-;,return 1;,int QuEmpty(QuType*q),/*,判空*,/,return(q-count=0);,3.2.3 队列的链式存储及其根本运算的实现,链队组成,:,(1),存储队列元素的单链表,(2),指向队头和队尾指针的链队头结点,链列的入队和出队操作示意图,单链表中数据结点类型,QNode,定义如下,:,typedef struct qnode,ElemType data;,