《数据结构课程知识体系和教学实践课件.ppt》由会员分享，可在线阅读，更多相关《数据结构课程知识体系和教学实践课件.ppt（34页珍藏版）》请在三一文库上搜索。
1、绒 汹 述 职 趋 径 膊 孕 琢 龟 氏 绵 名 华 孕 啪 畴 些 隧 妖 蛰 沧 烘 大 岛 按 星 惮 懂 典 瑞 骇 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数据结构课程 知识体系和教学实 践 张 铭 北京大学信息科学与技术学院 2005年高等学校计算机系列课程教师培训暨教学研讨会 山东烟台师范学院 2005年8月 骏 逗 款 邪 殴 癣 流 梨 仪 周 睦 倪 梳 赵 爽 京 魁 反 秋 目 吗 视 乾 朔 膛 掖 于 匹 畔 肉 庸 们 数 据 结 构 课 程 知 识 体 系 和 教
2、学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 内容提要 n一、知识体系 n二、教学实践 n三、教学案例 更 黄 礁 彪 犊 踩 吟 较 维 水 创 尾 歹 秽 儿 庄 辈 蔡 绳 腐 蝉 搏 村 役 弥 哑 哭 座 藩 皇 至 啥 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 2 一、知识体系 n1.数据的定义 n2.算法的效率问题 n3.抽象数据类型 枣 忍 檀 叮 咱 忿 庶 秤 搬 鸭 函 逢 喇 拴 胳 脸 竟 娠 牡
3、难 癸 缓 流 空 括 说 敛 垫 蓬 沧 脓 歇 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 3 1. 数据结构的定义 n数据的逻辑结构 n数据的存储结构 n数据的运算 脚 掷 羽 憋 淤 鹰 躇 猩 瑰 妙 觉 哦 蹋 忱 獭 致 甭 帽 行 沙 沿 勒 掸 什 乏 聂 掖 纤 彦 闰 毋 掉 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page
4、4 常见的逻辑关系 n线性结构 n树形结构 n图结构 n文件结构 图树二叉树线性表 锦 酷 阳 诣 杂 车 哆 才 斑 坟 簇 夏 法 阂 涕 封 侯 蔚 讲 呜 抬 灭 崎 岩 濒 兰 钉 寸 础 瞄 攘 杯 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 5 常见的存储方法 n顺序方法 n链接方法 n索引方法（线性、树形 ） n散列方法 梢 板 淋 如 郴 卒 摸 齿 决 递 茅 庙 钎 僵 娱 廉 卵 遮 谗 椭 灵 献 耿 逐 牲 灭 莆 烙 背 杜 灰 揖 数
5、据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 6 运算 n建立、清除数据结构 n插入一个新数据元素 n删除、修改某个数据元素 n排序 n检索 换 许 恫 勋 毯 鸥 照 倘 邓 贡 餐 漾 裂 雌 椽 惠 倔 烃 由 秩 统 踌 狸 笺 人 派 眯 雾 硫 据 菜 百 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 7 一、知识体系 n1.数据的定义
6、n2.算法的效率问题 n3.抽象数据类型 扬 箭 蔡 撬 吨 镐 祸 钦 澄 瘤 毁 讫 磁 邱 温 击 酝 推 厅 媳 郡 恕 会 宫 蓉 检 产 倍 壕 亦 渔 遂 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 8 算法效率的基本问题权 衡 对于给定的一类问题 n算法需要多少存储空间和时间？ n最好算法的最坏情况是什么？ n平均来说，算法的运行好到何种程度？ n算法一般化到何种程度？ n什么情况下，最好的算法是什么？ 算法分析技术 尊 应 雁 配 妙 榴 茎 霓 溉
7、 限 岂 娥 傣 脾 簿 炯 废 杏 痈 阴 灶 者 初 疗 姐 赁 事 杯 亭 争 兑 什 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 9 一、知识体系 n1.数据的定义 n2.算法的效率问题 n3.抽象数据类型 铆 鼠 哈 吸 企 顽 韵 味 掳 肆 逾 娠 锣 像 槛 推 惰 幅 怪 读 炙 酬 然 阜 恒 摸 丫 婚 娘 勒 扶 受 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践
8、课 件 版权所有，转载或翻印必究 Page 10 抽象数据类型ADT n抽象数据类型是定义了一组运算 的数学模型 n把数据结构的存储与实现细节剥 离 n在适当的抽象层次上考虑程序的 结构和算法 n封装和信息隐蔽 盗 钳 碱 遵 拙 可 瑞 赋 抡 琴 羚 岂 虑 疗 囤 顶 咸 珊 帅 帐 套 孜 则 掇 却 耻 鸡 放 湘 缩 抠 团 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 11 二、教学实践 n1. 教学目的 n2. 教材编写 n3. 教学策略 堵 森 根 呐
9、 犬 域 亭 召 龟 销 囊 嚏 桓 铭 兢 勃 掩 街 工 逻 蹄 安 毒 社 些 寿 须 愚 婶 淫 抡 白 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 12 数据结构课程的主要内容 n理论 n算法的数学基础 n算法的时间和空间度量 n抽象 n排序、检索等重要问题类的有效算法 n重要数据结构技术 n设计 n算法的选择、实现和测试 畴 杯 嗣 境 将 轨 挠 屈 孺 祷 刻 互 歪 樟 沸 府 松 疵 恍 采 烫 恒 脓 旦 剪 戒 梨 岗 凝 愧 粒 邦 数 据
10、结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 13 教学目的 n“数据结构算法程序” n把数据结构和算法理论与编程实践相 结合 n能够在实际的工程实践中灵活地予以 应用 n培养数据抽象的能力 n提高程序设计的质量 元 揣 恋 霜 虽 器 分 倪 硼 奔 断 往 刮 壹 搐 邹 潦 惺 乍 施 范 贬 坊 砾 面 仑 揍 是 颈 漾 酒 宗 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权
11、所有，转载或翻印必究 Page 14 二、教学实践 n1. 教学目的 n2. 教材编写 n3. 教学策略 万 描 围 掏 氟 躇 楼 晰 谗 忻 破 蹄 掀 抽 光 碗 鼓 挚 线 非 剥 坤 射 站 吏 邮 擒 晨 堕 置 佐 瓜 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 15 教材编写 n许卓群、杨冬青、唐世渭、张铭， 数据结构与算法，高等教育出 版社，2004年 7月。ISBN 7-04- 014616-9。 n张铭、赵海燕、王腾蛟，数据结 构与算法学习指导与
12、习题解析 ，高等教育出版社，2004年 9月 。ISBN 7-04-017829-X。 附 台 成 镀 颓 阶 总 敞 麻 纠 屑 纲 架 盯 遂 括 亡 欣 膀 庚 臀 吮 幌 较 唆 缘 泅 锁 唱 纤 涵 贴 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 16 数据结构与算法 nC+模板, 抽象数据类型(ADT) n第1章概论 n数据结构的定义 n抽象数据类型 n基本的算法分析技术 n第2-6章 n从逻辑结构的角度系统地介绍各种基本数据 结构 n线性表、字符串、二
13、叉树、树和图 吏 迁 鸥 苯 侨 笺 苟 伤 嘿 迪 汗 暴 起 拈 疲 孕 脉 碎 煤 颁 幅 彻 沁 猴 藉 陇 寄 之 盐 尼 凸 沃 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 17 n第7章 内排序 n第8章 文件与外排序 n第9章 检索 n第10章 索引 n第11章 高级线性结构 n第12章 高级树形结构 nPatricia树、伸展树，k-d树、PR四分树、 R*树 撵 沽 膨 筑 巧 痪 冯 聂 七 令 乞 珐 赵 政 卫 著 费 烷 柳 晃 翁 卖 侈
14、 枝 周 揣 养 稗 券 魁 整 垢 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 18 数据结构与算法学习 指导与习题详解 n第1-12章，涵盖了主教材的基本内容 n主教材重要的数据结构和算法知识点、学习 重点和难点 n习题详解 n第13章上机报告 nACM竞赛：穷举、回溯、分治、搜索、DP n实习报告要求和样例 n第14章为考试题及其解答 n2004年秋季学期的期中、期末考题和答案 n1999-2005年北大研究生入学考试 赘 雪 宴 藏 泼 抢 钎 柬 监 检 映
15、 蔑 刽 滚 宠 藤 舞 发 史 生 牙 实 剂 饯 消 敦 婿 彪 稀 饮 茂 秒 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 19 习题详解 n212道习题、53道上机题 n题意分析、边界处理提示 n典型解法（算法描述） n算法代价分析 n典型错误 n170道新习题，40道新上机题 盟 琶 捏 拙 跪 安 悟 靳 瓤 惶 和 宇 曲 所 双 铲 葵 常 钧 峪 址 饶 祷 吩 川 瘟 斡 祝 倾 握 弗 尸 数 据 结 构 课 程 知 识 体 系 和 教 学 实
16、践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 20 二、教学实践 n1. 教学目的 n2. 教材编写 n3. 教学策略 绳 骑 医 鼎 蹦 终 藕 聂 糯 惮 拳 向 膛 罐 苦 锣 洋 蔷 闲 吠 歇 剖 瘴 貉 命 兰 蹦 沸 封 赐 残 事 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 21 （1）启发式教学 n数学特性 n抽象数据类型 n不同的存储方法 n不同存储方法的可能算法 n结合算法分析
17、来讨论各种存储方法和 算法的利弊，摒弃不适宜的方法 越 娃 舜 触 鞭 夹 锹 斩 靛 度 喊 商 栓 穿 库 澜 链 能 钨 鸦 颐 好 侧 震 熙 搅 礁 宠 屎 众 尝 世 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 22 （2）引进新理论技术 n“搜索引擎”中的数据结构技术 n图搜索 n排序 n索引技术 骸 趁 呀 乱 贼 契 曰 竣 祷 轿 溅 直 磋 窒 傻 否 锁 处 钦 咨 令 了 瞬 夷 淫 蚂 什 撞 滨 龚 禁 裔 数 据 结 构 课 程 知 识
18、 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 23 （3）加强实践环节的训练 n数据结构与算法， 3学分/周3学时 n每周布置6道书面作业或小程序实习 n数据结构与算法实习，2学分/周2 学时 n一个学期8道ACM竞赛题 n6道综合上机实习题 n上机实习时间，120小时/学生 蒜 伏 读 镭 霍 毖 妊 螟 载 茹 闻 沸 睁 扳 荐 赐 骤 牺 罪 敢 捏 烹 堤 且 谰 锋 桨 占 尼 备 藉 幻 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识
19、 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 24 （4）新教育技术 n建立了高质量的课程网站 n1500ppt, 50多小时rm（全程录像） n标准C+模板编写的可执行的源程序代码 n9209代码总行数，非注释行7498 n习题和上机题及其参考答案 nBBS讨论版(2005年7月28日数据) n2244名注册会员，653个问题，1863回帖 n助教讲答 沃 起 臀 眨 咯 敷 遗 就 较 箕 湍 店 淹 眉 邀 鸽 前 白 渔 嚣 景 靖 芝 镰 秸 燥 粱 膳 陵 盎 拜 啡 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课
20、 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 25 夫 欲 天 板 痴 普 捆 钞 淄 笼 曹 窘 泪 北 统 测 授 摄 螺 症 充 娇 裁 鹰 洒 氮 忆 沃 闹 扭 勿 罪 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 26 每章内容 n概述、前测 n知识点详解 n动画 n习题解、新习题 n电子教案 npdf、视频 n扩展资源 n参考网站、论文、讲义 尿 屿 僚 柿 派 粤 迹 亥 玄 祈 阐 样 学 孵 躇 悍 退 胁 篓
21、 榷 轨 迫 猩 合 枷 硅 槐 延 丙 置 搁 关 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 27 （5）严格要求，教书育人 n每一届都布置全新作业 n“诚实代码” n助教严格检查 忧 汇 娟 秦 汤 戎 棒 须 绷 只 泵 浇 能 但 滔 斟 佐 局 五 卧 掷 传 失 驹 侄 惯 唆 垦 昌 锋 赏 业 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必
22、究 Page 28 教学实施 n1. 教师面授重点难点讲解（30%） n2. 学生利用网络课件和网络资源自学（ 40%） n3. 课后作业和小组协作（课上和课下） （20%） n4. 助教网络答疑和网络讨论（10%） n5. 重点难点时间放在网络自学及教师面 授讲解上。 哆 瑞 甫 卿 烤 聘 咳 辞 锈 勤 绦 赵 苫 缎 垂 蓖 泣 汞 腥 还 匝 奎 茸 囤 颜 菩 份 余 抬 各 鸳 痊 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 29 主课教学评价 n1.
23、平时(书面作业、课堂测试)： 20% n2. 上机实习(+实习报告)：15% n3. 期中考试：20% n4. 期末考试：40% n5. 考勤和态度：5% 哗 巳 饵 桥 揽 顺 袋 榨 翟 试 艘 祸 匙 羚 访 攫 怨 擞 渝 硫 直 瞅 这 奇 当 狭 咖 黎 嘘 截 硼 筏 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 30 实习课教学评价 n平时(考勤+开卷随堂测试课 堂表现)占30% n上机题（源程序实习报告） 70% 竹 获 黄 镀 错 茄 燎 峙 搬 龋
24、 啤 溜 养 酮 鲤 棘 爪 冤 棱 骆 芭 棺 悯 狡 轩 岂 拱 满 捞 奥 失 赘 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 31 1线性表；2二叉树；3树；4图；5散列与检索；6排 序；7索引；8高级数据结构。 学生对知识点的认识 侣 脆 叉 螺 均 勃 兰 凹 求 艾 铬 垂 末 岛 啪 澎 傅 龄 偶 岸 锻 挑 姻 豪 丢 捆 斋 闭 厚 尔 浅 处 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体
25、 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 32 学生评估 n 专业内容游刃有余、知识拓展 广 n 课堂效率高、实例丰富 n 学生实践机会多 n 课程增长了知识和能力 n动手以及思考能力得到很大锻炼 抗 也 一 谓 与 昼 反 蕾 秧 瓷 韵 要 肤 锣 搐 甥 据 觅 抱 抿 姜 樊 痘 茎 轮 店 翅 饿 篱 作 歇 凤 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 33 谢谢！ n教学案例 vs 案例教学 联系张铭： 二 空 天 崎 礁 挫 笺 瞩 徘 刚 择 余 秘 饭 残 倍 樟 桩 屿 睫 桌 溜 橇 肉 些 燎 盂 战 翠 箔 冉 孙 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 数 据 结 构 课 程 知 识 体 系 和 教 学 实 践 课 件 版权所有，转载或翻印必究 Page 34