第三章栈和队列(无答案)

5-2 单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,上页,下页,节,末页,结束,DataStructure,第三章 栈和队列,3.1,栈的抽象数据类型定义与实现,3.2,栈的应用举例,3.3,栈的应用,-,栈与递归,3.4,队列的抽象数据类型定义和实现,3.5,队列应用,-,离散事件模拟,1,、栈的相关概念,概念,:,栈,(Stack),是定义在线性结构上的抽象数据类型，其操作类似线性表操作，但元素的插入、删除和访问都必须在表的一端进行,为形象起见,称允许操作端为,栈顶,(Top),另一端为,栈底,(base),注意,Top,指向,待插入位置,特性,:Last In First Out,后进先出,/,总是访问最近插入的一个,/,按插入顺序倒着访问,3.1,栈,(Stack),待插入,top,base,入栈,Push,出栈,Pop,栈顶,元素,2,、栈的,ADT,定义,ADT Stack,数据对象,：,D=a,i,|a,i,ElemSet,i=1,2,n,n=0,数据关系,：,R=|a,i-1,a,i,D,，约定,an,为栈顶元素,基本操作,：,InitStack(&S),操作结果,:,构造一个空栈,DestroyStack(&S),初始条件,:,栈,S,已存在,操作结果：销毁栈,S,ClearStack(&S),初始条件,:,栈,S,已存在,操作结果,:,将,S,清为空栈,Push(&S,e),初始条件,:,栈,S,已存在,操作结果：插入,e,到栈顶,Pop(&S,&e),初始条件,:,栈,S,已存在且非空,操作结果：删除栈顶元素用,e,返回其值,ADT Stack,StackEmpty(S),初始条件,:,栈,S,已经存在,操作结果,:,空栈返回,TRUE,否则返回,FALSE,StackLength(S),初始条件,:,栈,S,已经存在,操作结果,:,返回,S,中元素的个数,GetTop(S,&e),初始条件,:,栈,S,存在且非空,操作结果,:,用,e,带回,S,栈顶元素的值,栈顶不变,StackTraverse(S,visit(),初始条件,:,栈,S,存在且非空,操作结果,:,从栈底到栈顶对,S,中各元素执行,visit,操作，一般用于输出栈元素,待插入,top,base,入栈,Push,出栈,Pop,栈顶,元素,3,、顺序栈的定义,#define STACK_INIT_SIZE 100,#define STACKINCREMENT 10,typedef?SElemType;,/,栈元素类型,typedef struct,SElemType*base;/,栈底指针,SElemType*top;/,栈顶指针,int stacksize;/,栈容量,SqStack,/,如何判栈空、求栈长、判栈满？,待插入,top,base,入栈,Push,出栈,Pop,顺序栈基本操作的实现,初始化,/,销毁,/,置空,Status InitStack(SqStack&S),/,构造空栈,S,S.base=(SElemType*)malloc(,STACK_INIT_SIZE*sizeof(SElemType),);,if(!S.base)exit(OVERFLOW);/,存储分配失败,S.top=S.base;/,空栈,S.stacksize=STACK_INIT_SIZE;,return(OK);,/InitStack,复杂度,”O(1)”,Status DestroyStack(SqStack&S),/,销毁栈,S,free(S.base);,S.base=NULL;,S.top=NULL;,S.stacksize=0;,return OK;,/,复杂度,O(1),Status ClearStack(SqStack&S),/,置,S,为空栈,S.top=S.base;return OK;,/,复杂度,O(1),待插入,top,bottom,入栈,Push,出栈,Pop,Status Push(SqStack&S,SElemType e),/,插入,e,为栈顶元素,if(S.top-S.base=S.stacksize)/,栈满则应重新分配空间,S.base=(SElemType*),realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);,if(!S.base)exit(OVERFLOW);,S.top=(S.base+S.stacksize);,/,使得,S.top,重新指向栈顶,因,realloc,S.stacksize+=STACKINCREMENT;,*S.top+=e;/top,指向待插入位置,return(OK);,/Push,复杂度,O(1),Status Pop(SqStack&S,SElemType&e),/,若栈不空则栈顶元素出栈并用,e,带回其值,if(S.top=S.base)return ERROR;,e=*(-S.top);/,栈顶元素为*,(S.top-1),return OK;,/,复杂度,O(1),待插入,top,bottom,入栈,Push,出栈,Pop,入栈与出栈,Status StackEmpty(SqStack S),if(S.top=S.base)return TRUE;else return FALSE;,int StackLength(SqStack S)return(S.top-S.base);,Status GetTop(SqStack S,SElemType&e),if(S.top=S.base)return ERROR;,e=*(S.top-1);/,注意,top,指向待插入位置,return OK;,Status StackTraverse(SqStack S,Status(*visit)(ElemType),/,从栈底元素到栈顶元素依次执行,visit函数,常用于输出栈中元素,ElemType*p=S.base;,if(S.base=S.top)printf(,空栈,n);,elsewhile(pdata=e;p-next=S,；,S=p;,Status Pop(LinkStack&S,，,SElemType&e),/,删除栈顶元素并用,e,返回,if(S=NULL)return ERROR;,e=S-data;,p=S;,S=S-next;,free(p);p=NULL;,/,其余操作自行实现,遍历,/,销毁,/,清空,/,求表长均,O(n),，其余,O(1),3.2,栈的应用,1,、十进制整数转换为八进制,n n div 8 n mod 8,1348 168 4,168 21 0,21 2 5,2 0,2,0,各余数按计算,次序,先后求得,之后,“,倒,”,排序,0,5,2,4,void conversion(),scanf(“%d”,Initstack(S);,while(n),Push(S,n%8);,n=n/8;,while(!StackEmpty(S),Pop(s,e);,printf(“%d”,e);,充分利用栈后进先出的特性,比用数组更易读易写抽象层次更高,回顾,:,栈的概念,:,栈 栈底指针 栈顶指针 栈顶元素,栈的两种存储结构定义及各自适用场合，及栈的操作在两种结构下的,实现,栈的应用,-,Last In First Out,后进先出,/,总是访问最近插入的一个,/,按插入顺序倒着访问,待插入,top,base,入栈,Push,出栈,Pop,S,a1,a2,a,n-1,a,n,#define STACK_INIT_SIZE 100,#define STACKINCREMENT 10,typedef?SElemType;,typedef struct,SElemType*base;/,栈底指针,SElemType*top;/,栈顶指针,int stacksize;/,栈容量,SqStack;,SqStack S1,S2;,typedef struct SNode,datatype data;,struct SNode*next;,SNode,*,LinkStack;,LinkStack S3;/,栈名,S,为栈顶元素指针,2,、括号匹配检验,正确：,(),错误：,()()(),Status match(),initstack(S);hasErr=0;,while(c=getchar()!=n&hasErr=0),switch(c),case(:,case:,case:,push(S,c);break;,case:,if(StackEmpty(S)hasErr=1;break;,else,pop(S,e);,if(e!=)hasErr=1;break;,case/,类似处理,),与,/switch,if(hasErr=0&StackEmpty(S),Return TRUE;,else return FALSE;,编译过程中尚需报告出错行数、忽略注释,/,字符串和字符常量等,思路,:,依次扫描各符号,每遇一结束符都找,最近,的开始符来匹配,不匹配或未找到则报错,.,最后应左右括号完全匹配毕,初始化一个空栈,逐个扫描符号,如果当前符号是开始符则入栈,如果是结束符号则分三种情况,如果栈空则报告出错,/,右多,否则,出栈,若弹出元素与当前元素不匹配则报告出错,/,不匹配,否则无动作，扫描下一符号,扫描结束,若栈不空则出错,/,左多,3,、行编辑程序,whli#ilr#e(s#*s),/while(*s),outchaputchar(*s=#+),/putchar(*s+);,思路,:,为提高数据输入效率设置输入缓冲区,.,对于输入的,一行数据,行结束时方将缓冲区的数据存入用户数据区,中间过程允许编辑,;,若,最近,的一个字符出错则用退格符,#,表示删去,若当前行不要则用退行符,则将,当前行,清空,.,遇到,行结束符,前，每遇一个符号，若它不是,#,或,则入栈,若是,#,则出栈,若是,则清空栈，一旦遇到行结束符或全文结束符则将缓冲区中数据保存到用户数据区,如此重复直到全文结束,void LineEdit(),InitStack(S);ch=getchar();,while(ch!=EOF)/,全文未结束,while(ch!=n&ch!=EOF)/,行未结束,switch(ch),case#:Pop(S,c);break;,case:ClearStack(S);break;,default:Push(S,ch);,/switch;,ch=getchar();,/,行结束,Save(S)/,传送栈中数据到用户数据区,ClearStack(S);,if(ch=n)ch=getchar();/,行尾非,EOF,4,、迷宫求解,令,curPos,指向入口,curStep,为,1,重复,while(TRUE),若当前位置通,则将其纳入路径,(,栈,).,是出口停,非出口重置,curPos,为右邻，开始下次循环,若当前位置不通,看,上一步,，若其四周,均已访问过,，则将其从路径中删除，如此重复直至找到一个曾经访问之位置，其四个方向至少有一个未曾访问过；此时重置,curPos,为此未访问邻块，开始下次循环。若栈空任然未找到则退出。,typedef,int,Maze,1010,;Maze maze;/,或,int maze1010;,typedef struct int x;int y;PosType;/,迷宫中的位置类型,typedef structint ord;PosType,seat;int di,;SElemType,;,/,栈元素类型,typedef structSElemType*base;SElemType*top;int stacksize;,Stack;/,栈类型,Status PassMaze(MazeType&maze,PosType s