程序设计教案 程序设计——数据结构.doc
《程序设计教案 程序设计——数据结构.doc》由会员分享,可在线阅读,更多相关《程序设计教案 程序设计——数据结构.doc(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 程序程序设计设计数据数据结结构构 第 1 页栈和队列基本概念及应用文档编号完 成 人 张 昱完成时间修改时间第 1 页目 录3.1 栈的基本概念 .1 3.1.1 栈的抽象数据类型定义 .1 3.1.2 顺序栈 .2 3.1.3 链栈 .3 3.2 栈的应用 .3 3.2.1 数制转换:将十进制数 N 转换成其他 d 进制数.3 3.2.2 括号匹配的检验 .4 3.2.3 行输入处理程序 .4 3.2.4 迷宫求解 .4 3.2.5 表达式求值 .4 3.3 栈与递归的实现 .5 3.4 队列的基本概念 .6 3.4.1 队列的抽象数据类型定义 .6 3.4.2 链队列 .7 3.4.3
2、循环队列 .7 3.5 队列与栈的应用 .8 3.5.1 离散事件模拟 .8程序程序设计设计数据数据结结构构 第 2 页栈和队列基本概念及应用文档编号完 成 人 张 昱完成时间修改时间第 2 页第 3 章 栈和队列3.1 栈的基本概念3.1.1 栈栈的抽象数据的抽象数据类类型定型定义义1、栈的逻辑特征1)限定在表尾进行插入或删除操作的线性表; 2)栈顶表尾端;栈底表头端 3)后进先出的线性表2、抽象数据类型的定义 ADT Stack 数据对象数据对象:D=ai |aiElemSet, i=1,2,n, n0 数据关系数据关系:R=R1,R1=|ai-1,aiD, i=2,3,n 基本操作基本操
3、作: InitStack( /* 栈底指针*/ ElemType*top; /* 栈顶指针(栈顶元素的下一个位置) */ intstacksize;/* 当前分配的存储容量*/ SqStack; 1)和顺序表一样采用增量式的空间分配; 2)操作和栈顶相关: 插入操作(入栈):将待插元素插入到栈顶元素的下一个位置; 删除操作(出栈):删除栈顶元素; 取元素操作:取栈顶元素的值。 各操作的操作位置与栈顶元素的位置或其下一个位置相关,希望在 O(1)时间内能获取 操作位置,故可设置专门的栈顶指针 top。 3)约定:约定:top 指向栈顶元素的下一个位置(便于表示空栈) 。 4)栈顶的初始化:S.t
4、op = S.base(在上述 3)约定下的空栈形式), 5)栈空:S.base = S.top,栈满:S.top - S.base = S.stacksize 6)入栈:*S.top + = e,出栈:e = *-S.top 注意注意:4), 5), 6)步受 3)制约。约定不同,相应的判定和处理也不一样。 如假设 top 就指向栈顶元素,此时 4),5),6)如何?2、取栈顶元素 GetTop_Sq1)算法设计参数:顺序栈 S、取得的栈顶元素 e = *( S.top -1); return OK; 3、入栈操作 Push_Sq1)算法设计参数:顺序栈 算法算法 2 2 Status Pu
5、sh_Sq( SqStack if ( S.base = NULL ) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK; 2)算法分析时间 T(n) = O(1)4、出栈操作 Pop_Sq1)算法设计参数:顺序栈 e = *( -S.top);/* 注意与 GetTop( )的区别 */ return OK; 2)算法分析时间 T(n) = O(1)3.1.3 链栈链栈与链表类似,只是链表的头指针即为栈顶指针。因其操作均在栈顶进行,故可以不引入
6、头 结点。 思考:在链栈下的入栈、出栈以及取栈顶元素的操作的算法如何写?3.2 栈的应用3.2.1 数制数制转换转换:将十:将十进进制数制数 N 转换转换成其他成其他 d 进进制数制数算法思想:N = ( N div d )d + N mod d 1)将 N%d 的结果保存, 2)N=N/d, 3)若 N=0 结束,否则继续 1) 。 保存的余数从先到后依次表示转换后的 d 进制数的低位到高位,而输出是由 高位到低位的,因此必须定义先进后出的线性表栈来保存;当全部的余数 求出后,通过逐个出栈输出 d 进制数。3.2.2 括号匹配的括号匹配的检验检验算法思想:从左至右扫描表达式,遇左括号入栈,遇
7、右括号与栈顶元素比较:若左右括号 匹配,则继续扫描;否则说明不匹配,结束。在上述操作中,若栈为空,或扫 描结束后栈不为空,均说明不匹配。3.2.3 行行输输入入处处理程序理程序处理规则:遇#退一格;遇退一行 算法思想:引入栈,保存终端输入的一行字符(逐行处理) ;程序程序设计设计数据数据结结构构 第 5 页栈和队列基本概念及应用文档编号完 成 人 张 昱完成时间修改时间第 5 页遇#退一格出栈一次 遇退一行清栈 步骤:1)初始化栈 S 2)读入字符 ch 3)ch!=EOF3.1) ch!=EOF B. 从各方块出发已探索的方向,注意不能重复(可约定按东、南、西、北的方向 顺次探索) ; C.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序设计 教案 数据结构
限制150内