数据结构的案例教学——栈在“迷宫问题”中的应用_论文

科技信息.   高校 理科 研 究  数据 结 构 嘲案 例 教 学  麓 在 “ 宫橱陋 "l 应 用  迷 【昀 】 慧  陈 兴  扬 州大 学能 源与动 力 工程 学院  许 [ 摘 要] 随着计算机在 各行各业中的应用 ,数据 结构》 《 不再仅仅是计算机 专业的基础课 , 同时也是其他理 工科 专业的重要课程 , 它  对学生软件开发能力的培养至关重要 。 是非计算机专业的学生对这 门课程重视不够 , 但 加上课 程本身理论性 强, 比较抽 象, 就会使 学  生 产 生厌 学 情 绪 。 文 以栈 在 迷 宫 问题 中的 应 用 为例 来讲 述栈 的 相 关知 识 , 本 收到 了很 好 的 效果 。 而说 明 , 对 非计 算机 专 业 的教 学  从 在 中引 入 案例 教 学 法 是 十 分 必要 的 。   [ 关键 词 ] 据结构  案例教 学法  栈  迷 宫问题  数 1 引 言  . 21 .. 式 栈   2链 由于计 算机技术的高速发展 ,使其在 工农 商各个行业 中得到 了广  泛应用。这就要求非计算机专业的学生也要 掌握一定的计算机软硬件  知识 , 其是需要 具有 一定的软件开发 能力 , 尤 这样 有助于本专业的相关  软件 知识的掌握。目前 , 理工科专业大 多要学 习《 软件技术基础》 门课  这 程, 该课程 涵盖 了数据结构 、 操作 系统 、 数据库 、 算机 网络 、 计 软件工程  等相关知识 , 其中数据结构部分对学生软件 开发能力的培养至关重要 。   数据结构 主要讨论抽象数 据关系 和算 法在计算机 中的表示 和实现 , 课  程的理论性 强 、 概念 多 , 学生学 习起来 难度较 大 , 非计算机 专业的学 生  更容易产生厌学情 绪。因此 , 需要在教学过程 中引入案例教学法 , 在提  升 兴 趣 的 同 时 , 学 生 更 直 观 地 了解 学 习 这 门 课程 的 目的 。 使   所谓案 例教学法 , 就是教师根据教学 目的和教 学内容的需要 , 运用  典型案例 , 让学 生积极 思考 、 主动探索 , 以提高他们 运用所学知识分析 、   解决问题能力的一种教学方法。 案例 教学法 是一种具有较 强沟通性 , 针  对性 , 实践性等特点的教 学模 式【 l 1 。在对非计算机 专业 的《 数据结构》 课  堂教 学中引入案例式教学模 式 , 针对理论教学 内容 , 将知识融人案例 之  中, 引导学生主动学习 , 激发学习兴趣 , 从而达 到提高教学质量 的 目的。   本文以栈在迷宫问题中的应用为例来讲述 栈的相关知识 ,提高 了课 堂  教学 的 趣 昧性 , 到 了 很 好 的效 果 。 收   2背 景 知 识   . 在讲述栈的相关知识之前 , 首先用演示 软件给出一个简单 的迷宫 ,   让学生找出通道。进而引导学生思考 , 如果把解 题过 程编写成计算 机程  序的话 , 需要什么样的数据结 构? 让学生带着 问题来学 习栈 的定 义和特  性等相关知识。   21 的 相 关 知识   .栈 所 谓 链 栈 就 是 用 链 表 作 为 栈 的 存 储 结 构 。选 取 链 表 的 头 指 针 作 为  栈 顶 指针 tp 指 示 栈 顶 元 素位 置 。链 栈 一 般 不 会 产 生 “ 溢 ” 除 非 内  o, 上 , 存 中已不存在 可用空间 。由于栈 的操作是线性表操作 的子集 , 以链栈  所 的操作很容 易实现 。   22迷宫 问题  . 栈是限定只能在表尾进 行插入 或删除操作的线性表[ 所 以说 栈也  2 1 。 是线性 表 , 它是操作上受限的线性表 , 因此 , 称为限定性 的数据结构 。 可   对栈来说 , 表尾端 有其特殊含 义, 称为栈 顶(p , t )相应地 , o 表头称为栈 底  (oo ) 不含元素的空表称为空栈 。 bt m 。 t 如图 1a (所示 , ) 假设栈 s (,2 a, =a a, r 。 …, )   则称 a为栈底元 素 , 为栈顶元素 。栈中元素按 a,, a 次序依次进  ,   l2   a …, 栈, 退栈 的第~个元素应为栈顶元素 。换句话 说 , 栈的修改是按后进 先  出的原则进行的。因此 , 栈又称为“ 后进先出” 线性表。正是栈 的这一特  点使得它成为解决迷宫问题的数据结构。   栈跟所有 的线性表一样具 有顺序存 储和链式存储 两种存储 结构 ,   耶么在迷宫问题中我们应该选取 哪种结构的栈呢?   211 .. 顺序栈  顺 序栈 ,即栈的顺 序存储结构 是利用 一组 地址连续的存储单元 依  次存 放 自栈 底 到 栈 顶 的 数 据 元 素 , 时 附设 指 针 t 同 o 示栈顶元素在顺  p指 序 栈 中 的 位 置 。通 常 的 习 惯 做 法 是 以 t = o O表 示 空 栈 。 p   进栈\  /  学习了栈 的基本知识后 , 我们再 回到迷宫 问题上 。 迷宫最早 出现在  古希腊神话 中。 史上 , 历 人们认 为迷宫具有魔力 ,一 进入就很难走 出    后来 , 迷宫成 为游戏 。而今借 助于计算机 , 迷宫 又以游戏程序的形式 呈  现 在 我们 日常使 用 的 电脑 上 。   迷宫 问题 是 一 个 经 典 的 程 序 设 计 问 题 。计 算 机解 迷 宫 问 题 的基 本  思想是 “ 穷举求解” 。即从人 口出发 , 法 顺某一方 向探索 , 若能走通 , 则继  续探 索 ; 否则沿 原路退 回 , 一个方 向再继续探索 , 换 直至所有 可能的通  路都探索 到为止 。为了保证在任何位置 上都能沿原路退 回。 显然需要  用 一个后进先 出的结构保存从入 口到 当前位置 的路径 。因此 , 在求迷宫  通路 的算法 中应用 “ ” 栈 也就是 自 然而然 的事

相关文档

数据结构线性单链表结构案例教学——双指针法的应用
浅谈案例教学在数据结构课程中的实践应用
数值模拟试验在岩土工程实验及工程案例教学中的应用
数据库案例教学在计算机专业专科教育职业化改革中的应用与研究
数据结构与算法课程的入门教学范例——迷宫问题
《数据库基础与应用》课程网上案例教学初探
《数据结构》案例教学的探讨
数值模拟在岩石力学案例教学中的应用
电脑版