山东轻工业学院 教师授课教案 课程名称: 数据结构(计科) 课程代码: 0 3 0 1 3 0 6 学 分: 4 .5 课程类别: 必修 开课单位: 信息科学与技术学院 授课班级: 授课教师: 杨春花 山东轻工业学院教务处制 授课时间 年 月 日 星期 第 节 年 月 日 星期 第 节 年 月 日 星期 第 节 授课内容概要 第三章 栈和队列 第一节 栈 栈的定义、结构特性和基本操作,栈的顺序存储结构表示和实现,栈的链式存储结构表示和实现。 第二节 栈的应用举例 数制转换,括号匹配的检验,迷宫求解,表达式求值等。 第三节 栈与递归 递归的概念,递归过程和递归工作栈; 第四节 队列 队列的定义、结构特性和基本操作;链队列的类型定义、插入和删除;循环队列的类型定义、判空和满的条件、插入和删除。 目的要求 目的:理解栈和队列的定义和实现,理解它们的应用。 基本要求:理解栈和队列的表示和实现、栈和队列的应用、递归的概念和递归过程;掌握栈和队列的概念和结构特性。 重 点 栈和队列的结构特性;栈和队列的应用;递归的执行过程。 难 点 循环队列判空和满的方法;递归的执行过程。 作业布置 习题 3 参考书 1. 数据结构题集(C语言版), 严蔚敏,清华大学出版社,2002。 3. 数据结构、算法与应用-C++语言描述,(美)Sartaj Sahni著,汪诗林等译,机械工业出版社,2002。 课 型 理论课 学 时 分 配 复 习 分钟 主要教具 投影、黑板 讲 授 分钟 教学方法 讲解、提问、示例 指 导 分钟 教学手段 板书、课件 总 结 分钟 备注 共 8学时,其中 2学时为习题课 注:课型一栏填写理论课、实验课、习题课等 授 课 内 容 备 注 第三章 栈和队列 栈和队列是操作受限的线性表,在计算机科学和程序设计中有广泛的应用。 3 .1 栈 3.1.1 栈的定义 栈(stack)是限定在表的同一端进行插入或删除操作的线性表。 进行插入或删除操作的一端称为栈顶(top),另一端称为栈底(bottom)。 当表中没有元素时称为空栈。 栈的操作特性:后进先出(last in first out) 设栈S=(a1,a2,… ,an)。栈中元素按a1,a2,… ,an 的次序进栈,则退栈的第一个元素为an 。 栈是又称为后进先出(last in first out )的线性表(简称LIFO 结构)。 例: 1)火车调度,如进栈的车厢序列为1、2、3,则可能的出栈序列有哪些? 2)已知一...