数据结构授课教案-第3章.doc

山东轻工业学院教师授课教案课程名称:数据结构(计科)课程代码:学分::必修开课单位:信息科学与技术学院授课班级:授课教师:杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第三章栈和队列第一节栈栈的定义、结构特性和基本操作,栈的顺序存储结构表示和实现,栈的链式存储结构表示和实现。第二节栈的应用举例数制转换,括号匹配的检验,迷宫求解,表达式求值等。第三节栈与递归递归的概念,递归过程和递归工作栈;第四节队列队列的定义、结构特性和基本操作;链队列的类型定义、插入和删除;循环队列的类型定义、判空和满的条件、插入和删除。目的要求目的:理解栈和队列的定义和实现,理解它们的应用。基本要求:理解栈和队列的表示和实现、栈和队列的应用、递归的概念和递归过程;掌握栈和队列的概念和结构特性。重点栈和队列的结构特性;栈和队列的应用;递归的执行过程。难点循环队列判空和满的方法;递归的执行过程。(C语言版),严蔚敏,清华大学出版社,2002。、算法与应用-C++语言描述,(美)SartajSahni著,汪诗林等译,***出版社,2002。课型理论课学时分配复****分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例指导分钟教学手段板书、课件总结分钟备注共8学时,其中2学时为****题课注:课型一栏填写理论课、实验课****题课等授课内容备注第三章栈和队列栈和队列是操作受限的线性表,在计算机科学和程序设计中有广泛的应用。(stack)是限定在表的同一端进行插入或删除操作的线性表。进行插入或删除操作的一端称为栈顶(top),另一端称为栈底(bottom)。当表中没有元素时称为空栈。栈的操作特性:后进先出(lastinfirstout)设栈S=(a1,a2,…,an)。栈中元素按a1,a2,…,an的次序进栈,则退栈的第一个元素为an。栈是又称为后进先出(lastinfirstout)的线性表(简称LIFO结构)。例:1)火车调度,如进栈的车厢序列为1、2、3,则可能的出栈序列有哪些?2)已知一个栈的入栈序列为1,2,3…,n,其输出序列为p1,p2,…,pn,若p1=n,则pi为?,InitStack(S);判断栈是否为空栈,StackEmpty(S);往栈中插入(或称推入)一个元素(入栈),push(S,e);从栈中删除(或称弹出)一个元素(删除),pop(S);求栈顶元素的值,GetTop(S)。()表示栈,附设top指向栈顶位置。定义1:#defineMAXSIZE1024typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;定义2:ElemTypes[MAXSIZE];inttop;⑴置空栈:首先建立栈空间,然后初始化栈顶指针。voidinitStack(SqStack&s){=0;}⑵判空栈boolStackEmpty(SeqStacks){if(==0)returntrue;elsereturnfalse;}⑶入栈intPush(SeqStack&s,elemtypex){if(==MAXSIZE-1