北京大学：《数据结构与算法》课程教学资源（实验班讲义）课程简介、概论

教学目的 “数据结构十算法=程序 数据结构与算法 基本数据结构的ADT及其应用 理组织数据,有效表示数据,有效处 张铭 http:/db.pku.edu.cn/mzhang/ds/ 算法的设计分析技术 北京大学信息科学与技术考 抽象能力 数据结构与算法教学小组 ■问题—数据——算法 2007年9月10日 提高程序设计的质量 ⊙版权所有,转蒙或印必兜 北大息_张铭写 课程的主要内容 实习课目的 论 配合“数据结构与算法”主课,提高实际动 算法的数学基础 手能力和程序设计的质量 算法的时间和空间度量 ■基本数据结构 线性表向量、串、栈和队列)、二叉树、 排序、检索等盒要问题类的有效算法 ADT、STL 黛要数据结构技术 ■综合应用程序 设计 排序、检索、文件、索引等技术 算法的选择、实现和测试 程序设计实践和技巧 北大影_歌张写 权质有轨国邮究 真大_息 张铭编写 有,神剑究 实习课程内容(1/2) 实习课程内容(2/2) ■C++编程技术补充 基本算法 标准模板库STL的基本概念 ■枚举法、贪心法 C++流处理 递归、回溯、搜索与分支限界 程序设计实践和技巧 分治法、动态规划 ■风格、设计和实现 ■问题建模 界面、排错 数学建模、软件模型 测试、性能和可扩展性 m数据结构的应用 北大张写 权所有轨康■命邮 盒大带张铭写

1 数据结构与算法 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 2007年9月10日 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 教学目的… „ “数据结构＋算法＝程序” „ 基本数据结构的ADT及其应用 „ 合理组织数据, 有效表示数据, 有效处 理数据 „ 算法的设计分析技术 „ 抽象能力 „ 问题——数据——算法 „ 提高程序设计的质量 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 课程的主要内容 „ 理论 „ 算法的数学基础 „ 算法的时间和空间度量 „ 抽象 „ 排序、检索等重要问题类的有效算法 „ 重要数据结构技术 „ 设计 „ 算法的选择、实现和测试 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 实习课目的 配合“数据结构与算法”主课，提高实际动 手能力和程序设计的质量 „ 基本数据结构 „ 线性表(向量、串、栈和队列)、二叉树、 树、图等 „ ADT、STL „ 综合应用程序 „ 排序、检索、文件、索引等技术 „ 程序设计实践和技巧 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 实习课程内容(1/2) „ C++编程技术补充 „ 标准模板库 STL的基本概念 „ C++流处理 „ 程序设计实践和技巧 „ 风格、设计和实现 „ 界面、排错 „ 测试、性能和可扩展性 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 实习课程内容(2/2) „ 基本算法 „ 枚举法、贪心法 „ 递归、回溯、搜索与分支限界 „ 分治法、动态规划 „ 问题建模 „ 数学建模、软件模型 „ 数据结构的应用

主题 组长组员 面向对象技术 毛琛吴迪 钱昊巨程 实习课程进度(1/2 调试和测试技术 赖博彦陈学轩丁羽 陈醒王瑞超 9月12日第一周数据结构与算法实习简介 9月19日第二周算法(一):穷举法 递归和回溯 9月26日 周算法(二):回溯法 图、搜索、剪枝姚金字黄柏彤陈琪 10月3日第四周国庆放 10月10日第五周算法(三):贪心法,算法优 动态规划 杨涛金鑫李昂周 日第六周程序设计实践(一):风格 金果 算法优化 李森贾由 和2用*覆序设计实政(=),5的源本 数学建模技术 汪瑜雷涛罗睿辞 10月31日第八周算法(四):分治法 王尧 改据续控与算法的应用陈志态冯黑张 北大息_张铭写 实习课程进度(2/2) 主课教学考核 11月7日第九周算法(五):动态规划 第十周习题讨论,布置大实习,讨 期中20% 期末20% 11月21日第十一周程序设计实践(三):界 高级数据结构20% 震性序设计实践(四):测 平时(考勤+课堂)20% 12月5日第十三周问题建模专题讨论 书面作业、上机作业15 12月12日第十四周图的应用 态度5% 12月19日第十五周数据结构应用 ■12月26日第十六周上机题讲评,期末总复习 北大影_歌张写 权质有轨国邮究 真大影张帖写 叔新有,量究 考勤 作业要求 不要迟到早退、旷课 1.主课只有书面作业(每周4道) ◆有事提前请假 我保证本次作业由我本人独立完成, ■中请“课堂免修”(自学)? 不需要调试 ◆同样交作业、上机题、考试 ■2.实习课3道大综合实习,7道AcM ◆不建议 ■“诚实代码 学习需要环境 要调 ◆考勤措施:随堂小测试 ■要提交上机报告 北真大学张铭编写 聊张帖写 权新有,究

2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 数据结构与算法的应用 陈志杰 冯熙铉 张策 雷涛 罗睿辞 王尧 数学建模技术 汪瑜婧 算法优化 李森 贾由 金鑫 李昂 周 金果 动态规划 杨涛 图、搜索、剪枝 姚金宇 黄柏彤 陈琪 递归和回溯 王子琪 谭裕韦 陈学轩 丁羽 陈醒 王瑞超 调试和测试技术 赖博彦 STL和C++ 钱昊 巨程 面向对象技术 毛琛 吴迪 主题 组长 组员 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 实习课程进度(1/2) „ 9月12日 第一周 数据结构与算法实习简介 „ 9月19日 第二周 算法（一）：穷举法 „ 9月26日 第三周 算法（二）：回溯法 „ 10月3日 第四周 国庆放假 „ 10月10日 第五周 算法（三）：贪心法, 算法优化 „ 10月17日 第六周 程序设计实践（一）：风格、设计 和实现，面向对象技术 „ 10月24日 第七周 程序设计实践（二）：STL的基本 概念和常用容器 „ 10月31日 第八周 算法（四）：分治法 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 实习课程进度(2/2) „ 11月7日 第九周 算法（五）：动态规划 „ 11月14日 第十周 习题讨论，布置大实习，讨 论项目管理 „ 11月21日 第十一周 程序设计实践（三）：界 面和排错 „ 11月28日 第十二周 程序设计实践（四）：测 试、性能和可扩展性 „ 12月5日 第十三周 问题建模专题讨论 „ 12月12日 第十四周 图的应用 „ 12月19日 第十五周 数据结构应用 „ 12月26日 第十六周 上机题讲评，期末总复习 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 主课教学考核 „ 期中20 % „ 期末20 % „ 高级数据结构20% „ 平时(考勤+课堂)20 % „ 书面作业、上机作业15 % „ 态度5% 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 考 勤 „ 不要迟到早退、旷课 ‹有事提前请假 „ 申请“课堂免修”（自学）？ ‹同样交作业、上机题、考试 ‹不建议 ‹学习需要环境 ‹考勤措施：随堂小测试 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 作业要求 „ 1. 主课只有书面作业(每周4道) „ “我保证本次作业由我本人独立完成， 没有抄袭他人作业” „ 不需要调试 „ 2. 实习课3道大综合实习，7道ACM „ “诚实代码” „ 要调试 „ 要提交上机报告

按时提交作业,严禁抄袭 作业提交期限的说明 每周第一次课课间交书面作业(或之前 ftp提交电子版) 1.有利于助教及时批改、讲解 计分标准10分,期末加权。规则: 2.有利于同学及时讨论复习 1.准时提交,满分可达10分(个别加 分) 2.延迟3天之内提交,满分可达7分; ■破例申请—要在 deadline前提出 3.延迟7天之内提交,满分可达3分 1.个别有困难的同学 4.7天之后提交或不交,得分-5分。 2.生病或事假 5.抄袭得-20分。 举位▲张倍墙写 北大单张铭写 叔新有,命邮 诚信 书面作业提交要求 ■端正学习态度、调动学习兴趣 写学号、名字 ◆提倡讨论,但严禁抄袭 写“XX保证没有抄袭他人作业”的诚实 ◆可以讨论思路 保证 ◆但要亲自动手实现 写算法分析、注释 现抄袭,严肃查处 注意算法格式(层次嵌套、不同功能块 效密馩和棼抄部喜杏或上机题计 留空) ◆以后的作业题会得到重点检查 否则,计零分或根据抄袭情况倒扣分 北真大脆张写 叔新有,量究 学习过程中的问题 学习过程中的问题 ■问题1:进度快,听不懂 问题2:算法思想能懂,但代码不懂 别人是牛人,自己是菜鸟 没有入门,经验不够 同学发言听不懂 建议:多读代码 ■建议:主动学习 先弄懂思想,再看代 建立信心我是精英,我能行 预习—聪明鸟先飞 再总皓算法的主 ,物例检测边界—具体 提问式学习——量疑、创新 经典算法代码不仅要恒,还要自己能写出来 复习—总结、提高、实践应用 不是背,是用自己的风格写 以考题的形式来看书,做习题 对经典算法的灵活 售改问题条件,仿写 北真大学张铭编写 聊张帖写 权新有,究

3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 按时提交作业，严禁抄袭 „ 每周第一次课课间交书面作业(或之前 ftp提交电子版) „ 计分标准10分，期末加权。规则： 1. 准时提交，满分可达10分（个别加 分）； 2. 延迟3天之内提交，满分可达7分； 3. 延迟7天之内提交，满分可达3分； 4. 7天之后提交或不交，得分 - 5分。 5. 抄袭得 – 20分。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 作业提交期限的说明 „ 1. 有利于助教及时批改、讲解 „ 2. 有利于同学及时讨论复习 „ 破例申请——要在deadline前提出 „ 1. 个别有困难的同学 „ 2. 生病或事假 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 诚 信 „端正学习态度、调动学习兴趣 ‹提倡讨论，但严禁抄袭 ‹可以讨论思路 ‹但要亲自动手实现 ‹发现抄袭，严肃查处 ‹抄袭者和被抄袭者本次作业或上机题计 双倍倒扣分，即得 - 20分 ‹以后的作业题会得到重点检查 ‹严重的期评将给予不及格处理 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 书面作业提交要求 „ 写学号、名字 „ 写“XX保证没有抄袭他人作业”的诚实 保证。 „ 写算法分析、注释 „ 注意算法格式(层次嵌套、不同功能块 之间留空) „ 否则，计零分或根据抄袭情况倒扣分。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 学习过程中的问题 „ 问题1：进度快，听不懂 „ 别人是牛人，自己是菜鸟 „ 同学发言听不懂 „ 建议：主动学习 „ 建立信心——我是精英，我能行 „ 预习——聪明鸟先飞 „ 提问式学习——置疑、创新 „ 复习——总结、提高、实践应用 „ 以考题的形式来看书，做习题 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 学习过程中的问题 „ 问题2：算法思想能懂，但代码不懂 „ 还没有入门，经验不够 „ 建议：多读代码 „ 先弄懂思想，再看代码 „ 抽象——具体——抽象 „ 弄懂算法的大框架——抽象 „ 要多用实例走几遍，特例检测边界——具体 „ 再总结算法的主要功能块——抽象 „ 经典算法代码不仅要懂，还要自己能写出来 „ 不是背，是用自己的风格重写 „ 对经典算法的灵活 „ 修改问题条件，仿写

学习过程中的问题 学习过程中的问题 ■问题3:编写的算法质量不高 数学模型建立 问题4:不能独立完成作业 质上是散学思能力,抽像能力 抄同学的——作弊 不深入考虑,就问—没有收获 理不周到 有思想写不出代码 n翻书,照着代码修改—考试有问题 ■建议;多写代码 建议:独立完成作业 事先想明白算法思想 先看一遍敦材、或讲义 编写结构清晰的程序 顺序、条件选 不懂的地方找同学请教,或看视频 不要过于依赖拿 还不懂,在bbs上提问,或找责任助教 举位▲张倍墙写 北大单张铭写 叔新有,命邮 学习过程中的问题 学习过程中的问题 ■问题5:不好意思与同学交流 问题6:不善于利用资源 怕打搅 课程网站、课程讨论bbs 怕抄袭嫌疑 助教、同学 建议:主动交流、普于交流 推荐作业 ■沟通、交流是雪要的情商 ■建议:高效调动资源 增进感情、为将来的合作打基础 多看参考资源 能加深对问题的理解,提高作业质量 多请教、讨论 只要不直接看答案,思想类似不会构成抄袭 推荐作业 重要前提:一定要自己先思考,否则效率低 研究复习大纲 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 课程资源 实验班资源 数据结构与算法(信息学院 .httpldbpku.edu.cn/mzhang/ds/ .http://db.pku.edu.cn/mzhang/ds/honor 数据结构实习(计算机和智能专业强化) ■实验班作业提交 .http:ldbpku.edu.cn/mzhang/ds/shixi/i ftp:dshonordsoZhonor@fusiongrids.cn ■课程答疑 用户名: ds honor .http:Idbcs.pku.edu.cn/mzhang/ds/bbs/ 密码:ds07 honor ◆注册:h学号Xxx 北真大学张铭编写 聊张帖写 权新有,究

4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 学习过程中的问题 „ 问题3：编写的算法质量不高 „ 数学模型建立不了 „ 本质上是数学思维能力，抽象能力 „ 递归思想 „ 边界处理不周到 „ 有思想写不出代码 „ 建议：多写代码 „ 事先想明白算法思想 „ 编写结构清晰的程序 „ 顺序、条件选择、循环、函数 „ 不要过于依赖编译器 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 学习过程中的问题 „ 问题4：不能独立完成作业 „ 抄同学的——作弊 „ 不深入考虑，就问——没有收获 „ 翻书，照着代码修改——考试有问题 „ 建议：独立完成作业 „ 先看一遍教材、或讲义 „ 不懂的地方找同学请教，或看视频 „ 还不懂，在bbs上提问，或找责任助教 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 学习过程中的问题 „ 问题5：不好意思与同学交流 „ 怕打搅 „ 怕抄袭嫌疑 „ 建议：主动交流、善于交流 „ 沟通、交流是重要的情商 „ 增进感情、为将来的合作打基础 „ 能加深对问题的理解，提高作业质量 „ 只要不直接看答案，思想类似不会构成抄袭 „ 重要前提：一定要自己先思考，否则效率低 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 学习过程中的问题 „ 问题6：不善于利用资源 „ 课程网站、课程讨论bbs „ 助教、同学 „ 推荐作业 „ 建议：高效调动资源 „ 多看参考资源 „ 多请教、讨论 „ 推荐作业 „ 研究复习大纲 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 课程资源 „ 数据结构与算法（信息学院） ‹ http://db.pku.edu.cn/mzhang/DS/ „ 数据结构实习（计算机和智能专业强化） ‹ http://db.pku.edu.cn/mzhang/DS/shixi/i ndex.htm „ 课程答疑 ‹ http://db.cs.pku.edu.cn/mzhang/ds/bbs/ ‹ 注册：h-学号xxx 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 实验班资源 „ http://db.pku.edu.cn/mzhang/ds/honor „实验班作业提交 ftp://ds_honor:ds07honor@fusion.grids.cn „ 用户名: ds_honor „ 密码: ds07honor

教材 参考书目 ■许卓群、杨冬青、唐世渭、张 ■张铭、刘晓丹译,《数据结构与算法分 铭,《数据结构与算法》,高等 析》(C++第二版、Java版),电子工业 教育出版社,2004年7月。 出版社,2002年。(用1998年的第 ■张铭、赵海燕、王腾蛟,《数据 版也可以,也可以直接用英文原版) 结构与算法一一学习指导与习题 ■许卓群,《数据结构》,高等教育出版 社,1988。 解 高等教育出版社, 2005年10月 举位▲张倍墙写 北大单张铭写 叔新有,命邮 教学参考书 教学参考书(续) Donald e Knuth, The Art of Computer rogramming, Addison Wesley. vol 1 跌与昆+努结华大图鞋 vol3.国防工业出版社影印。(苏运霖译 Thomas H Cormen charles e Leiserson 德径〈等桉; c++ donald L. Rivest, Clifford Stein 育出版 production to Algorithms, MIT Press. 5 等教育出版社影印 蔚 和语言版 哥据结+笑学图社1 (Data Structure with 大学出版社 严蔚敏,《数据结构题集》,清华大学 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 主课助教 第一章概论 ■王位春:学院课程总助教 ■为竹么县啪习教据构 13810026968 ■么是教据施构 ■黄燕京 吴定明 抗法的兮性及分 ■的敦度量 ■邢国峰(实习课总助教 拇枘的辑和评价 总綰 北真大学张铭编写 聊张帖写 权新有,究 5

5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 教材 „ 许卓群、杨冬青、唐世渭、张 铭，《数据结构与算法》，高等 教育出版社， 2004年 7月。 „ 张铭、赵海燕、王腾蛟，《数据 结构与算法－－学习指导与习题 解析》，高等教育出版社， 2005年 10月。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 参考书目 „ 张铭、刘晓丹译, 《数据结构与算法分 析》(C++第二版、Java版)，电子工业 出版社，2002年。（用1998年的第一 版也可以，也可以直接用英文原版） „ 许卓群，《数据结构》，高等教育出版 社，1988。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 教学参考书 „ Donald E. Knuth, The Art of Computer Programming, Addison Wesley. Vol. 1， Vol 3. 国防工业出版社影印。（苏运霖译） „ Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MIT Press. 高 等教育出版社影印。 „ William Ford，《Data Structure with C++》，清华大学出版社 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 教学参考书(续) „ 殷人昆，《数据结构——用面向对象方 法与C++描述》，清华大学出版社， 1999。 „ 张乃孝，裘宗燕，《数据结构——C++ 与面向对象的途径》，高等教育出版 社，2001。 „ 严蔚敏，《数据结构》 第二版(Pascal 和语言版都可以)，清华大学出版社。 „ 严蔚敏，《数据结构题集》，清华大学 出版社 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 主课助教 „ 王位春：学院课程总助教 „ 13810026968 „ 黄燕京 „ 吴定明 „ 邢国峰(实习课总助教) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 第一章 概论 „ 为什么要学习数据结构 „ 什么是数据结构 „ 抽象数据类型 „ 算法的特性及分类 „ 算法的效率度量 „ 数据结构的选择和评价 „ 总结

什么是数据结构 为什么要学习数据结构 data structure) 计算机软件与理论学科的专业基础课程 ■后续专业课程学习的必要知识与技能准备 ■数据逻辑结构 编译技术要使用栈、散列表及语法树 数据的存储结构 逻辑/数据存储 操作系统中用队列、存储管理表及目录树 数据库系统运用线性表、多链表、及索引树 k结构 数据的运算 运算 ■增强求解复杂问题的能力 举位▲张倍墙写 北大单张铭写 叔新有,命邮 数据的逻辑结构 常见的逻辑关系 二元组:(K,R) 线性结构 K是由有限个结点组成的集合 ■树形结构 ■R是定义在集合K上的一组关系,其中 图结构 每个关系( relation)r(r∈R)都是 ■文件结构 K×K上的二元关系 数据结构中,只讨论R={ 图二树二二叉树线性表 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 结点的类型 结点的类型 基本数据类型 ■基本数据类型 整数类型( integer) 字符类型(char):用单个字节(8bt,最高位 bt为0)表示ASCI字符集中的字符。 实数类型(rea) 汉字符号需要使用2个字节〔每个字节的最高位 ■布尔类型( boolean) 在C++语言中一般使用整数0表示 Unicode, GB, Big5, HZ false,用非0衰示true 北真大学张帖精写 聊张帖写 权新有,究 6

6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 为什么要学习数据结构 „ 计算机软件与理论学科的专业基础课程 „ 后续专业课程学习的必要知识与技能准备 „ 编译技术要使用栈、散列表及语法树 „ 操作系统中用队列、存储管理表及目录树 „ 数据库系统运用线性表、多链表、及索引树 „ …… „ 增强求解复杂问题的能力 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 什么是数据结构 (data structure) „ 数据逻辑结构 „ 数据的存储结构 „ 数据的运算 数据 存储 结构 逻辑 运算 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 数据的逻辑结构 „ 二元组：( K ，R ) „ K是由有限个结点组成的集合 „ R是定义在集合K上的一组关系，其中 每个关系(relation) r（r∈R）都是 K×K上的二元关系 „ 数据结构中，只讨论R={r} 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 常见的逻辑关系 „ 线性结构 „ 树形结构 „ 图结构 „ 文件结构 图⊇树⊇二叉树⊇线性表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 结点的类型 „ 基本数据类型 „ 整数类型(integer) „ 实数类型(real) „ 布尔类型(boolean) „ 在C++语言中一般使用整数0表示 false，用非0表示true 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 结点的类型 „ 基本数据类型 „ 字符类型(char)：用单个字节（8bit，最高位 bit为0）表示ASCII字符集中的字符。 „ 汉字符号需要使用2个字节（每个字节的最高位 bit为1）的编码 „ Unicode，GB，Big5，HZ

结点的类型 结点的类型 基本数据类型 复合数据类型 指针类型( pointer):指向某一内存单元的地址 32bit机器,4个字节表示一个指针 基本数据类型/复合类型 64bit的机器,8指针 指针操作 数组intA[100] 分配地址 賦值(另一个指针的地址值,NUL空值) 比较两个指针地址 结构 typedef struct{}B 指针增减一个数量 class cifi 举位▲张倍墙写 北大单张铭写 叔新有,命邮 结点和结构 结构的分类 数据结构的设计一层一层地进行 ■对(KR)的分类,用R的性 先明确数据结点,及其主要关系r 质来刻划 ■对于复杂情况,再分析下一层次 线性结构( linear 的逻辑结构 structure) 自顶向下的分析设计方法 m树型结构( tree structure) a图结构( graph structure 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 线性结构 线性结构 应用最广泛,关系r是一种线性关系 ■图示法(注意与链表的图示区别开 大小关系 来) 关系r有向,全序性和单索性等约束条件 全序性:全部结点两两皆可以比较前后(关系r) 单索性:每一个结点y都存在唯一的直接后继结点z [[。区。区 北真大学张铭编写 聊张帖写 权新有,究

7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 结点的类型 „ 基本数据类型 „ 指针类型(pointer)：指向某一内存单元的地址 „ 32 bit机器，4个字节表示一个指针 „ 64bit的机器， 8指针 „ 指针操作 „ 分配地址 „ 赋值（另一个指针的地址值，NULL空值） „ 比较两个指针地址 „ 指针增减一个整数量 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 结点的类型 „ 复合数据类型 „ 基本数据类型/复合类型 „ 数组 int A[100]; „ 结构 typedef struct {} B; class C { }; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 结点和结构 „ 数据结构的设计一层一层地进行 „ 先明确数据结点，及其主要关系r „ 对于复杂情况，再分析下一层次 的逻辑结构 „ 自顶向下的分析设计方法 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 结构的分类 „ 对（K,R）的分类，用R的性 质来刻划 „线性结构（linear structure） „树型结构（tree structure） „图结构（graph structure） 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 线性结构 „ 应用最广泛，关系r 是一种线性关系 „ ‘前后关系’ „ ‘大小关系’ „ 关系r有向，全序性和单索性等约束条件 „ 全序性：全部结点两两皆可以比较前后（关系r） „ 单索性：每一个结点y都存在唯一的直接后继结点z „ y -> z „ x -> … -> z „ 则x -> … y-> z „ x = y ？ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42 线性结构 „ 图示法（注意与链表的图示区别开 来） k0 Kn-2 k1 Kn-1 k…

树型结构 其关系r为层次关系,或称父子关系、上下级关系 图结构 每一个结点可以有多于一个的宜接下级,但是它只能有 唯一的直接上级 根〔root)结点没有父结点 图着限惭:R(,中点相对于前愿和后个数 Q ⊙oooo 物盒啦张促写 北大单张铭写 叔新有,命邮 图结构 数据的存储结构 左图逻辑结构B=(KR),其中 ■映射:逻辑→存储 [A, B. C, D,E, F] ■对于数据逻辑结构(K,r)其中∈R R={r},r={, , , , BF>,,,,, 关系元组(k1,k2)∈r(k1k2∈K映射为 存储单元的地址指向关系 四种存储结构:顺序、链接、索引、散列 可以筒写为 空间时间权衡 r=H(A, C)(A, E),(B, C), (B, F). ■尽量少的空间,尽量快的运算速度 (C, D),(C F (D,F)(E, FI 北真大脆张写 叔新有,量究 顺序存储—数组 链接( inked)的方法 的指向:结点间逻辑后继关系 ■两部分:数据字段、指针字段 ■链索:多个相关结点的依次链接就会形成 把一組结点存储在按地址相邻的顺序存储单元里 存储密度;p=nxE/n(P+E)=E/(P+E) 结点间的逻辑后能关系用存储单元的自然顺序关系来表达 紧凑存储结构 紧凑性可以用存储密度来度量 a…一a 存储密度(≤1)=数本身存储量/整个构占用存健量 单链 First Last 北真大学张铭编写 聊张帖写 权新有,究

8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 树型结构 „ 其关系r为层次关系，或称‘父子关系’、‘上下级关系’ „ 每一个结点可以有多于一个的‘直接下级’，但是它只能有 唯一的‘直接上级’。 „ 根（root）结点没有父结点 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 图结构 有 向 图 图：B={K, R}, R={r}, K中结点相对于r前驱和后继个数 都没有限制。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 图结构 无 向 图 左图逻辑结构B=(K, R) ，其中 K＝ ｛A,B,C,D,E,F} R = {r}，r = {,, ,, ,, ,, ,, ,, ,, ,} 可以简写为: r = {(A, C), (A,E), (B,C), (B,F), (C,D), (C,F),(D,F ), (E,F)} 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 数据的存储结构 „ 映射：逻辑 → 存储 „ 对于数据逻辑结构（ K , r ）,其中r∈R „ 从K到存储器M的单元的映射：K→M „ 每一个结点k∈K都对应于唯一的区域c∈M。 „ 关系元组（k1 , k2）∈r（k1, k2∈K映射为 存储单元的地址指向关系 „ 四种存储结构：顺序、链接、索引、散列 „ 空间时间权衡 „ 尽量少的空间，尽量快的运算速度 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 „ 把一组结点存储在按地址相邻的顺序存储单元里 „ 结点间的逻辑后继关系用存储单元的自然顺序关系来表达 „ 紧凑存储结构 „ 紧凑性可以用‘存储密度’来度量： „ 存储密度(≤ 1) =数据本身存储量/整个结构占用存储量 顺序存储——数组 01 2 3 4 5 6 7 S: 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 链接（linked）的方法 „ 指针的指向：结点间逻辑后继关系 „ 两部分: 数据字段、指针字段 „ 链索：多个相关结点的依次链接就会形成 „ 存储密度：ρ= n×E /n(P+E) = E /(P+E) a1 an First Last 单链 表

索引( indexing)的方法 索引函数Y:z→D 结点的整数索引值z∈z 索引法是顺序存储法的一种推广,它也 结点的存储地址d∈D 使用整数编码来访问数据结点位置 紫引衰 救库记 举位▲张倍墙写 北大单张铭写 叔新有,命邮 倒排文件 倒排文件与线性索引 ment Location Term Pointer to 19 Inverted elk 43 真大影张帖写 叔新有,量究 散列( hashing)的方法 散列( hashing)的方法 散列是索引方法的一种延伸和扩展 散列函数h(s)除了它取非负整数值外,关 更快的检索速度 键的问题 受数组元素地址计算启发 Loc( A[D= Loc(A[OD+i* sizeof(Element); 恰当地选择散列函数 ■散列函数是将字符串s映射到非负整数z的一类 ■如何建造散列表 函数h:s→z, 在构建散列表的中间解决碰撞的办法 对任意的s∈S,散列函数h(s)=z,z∈2 北真大学张铭编写 聊张帖写 权新有,究

9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 49 索引（indexing）的方法 „ 索引法是顺序存储法的一种推广，它也 使用整数编码来访问数据结点位置 01 2 3 4 5 6 7 数据节点的存储区域 索引表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 back 92 73 37 55 数据库记录 线形索引文件 „ 索引函数Y：ZÆD „ 结点的整数索引值 z∈Z „ 结点的存储地址 d∈D 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 51 倒排文件 Word Postings Document Location abacus 4 3 94 19 7 19 212 22 56 actor 3 2 66 19 213 29 45 aspen 1 5 43 atoll 3 11 3 11 70 34 40 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 52 倒排文件与线性索引 Term Pointer to list of postings ant bee cat dog elk fox gnu hog Inverted lists 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 53 散列（hashing）的方法 „ 散列是索引方法的一种延伸和扩展 „ 更快的检索速度 „ 受数组元素地址计算启发 „ Loc(A[i]) = Loc(A[0]) + i * sizeof(Element); „ 散列函数是将字符串s映射到非负整数z的一类 函数h: S Æ Z ， 对任意的 s∈ S，散列函数 h(s)=z，z∈ Z 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 54 散列（hashing）的方法 „ 散列函数h(s)除了它取非负整数值外，关 键的问题： „ 恰当地选择散列函数 „ 如何建造散列表 „ 在构建散列表的中间解决‘碰撞’的办法

散列( hashing)的方法 数据的运算 110 逻辑结构和存储结构都相同,但 运算不同,则数据结构不同 例如,栈与队列 ■对于一种数据结构,常见的运算 建立、清除数据结构 插入、删除、修改某个数据元素 H(k)=k%11 排序、检索 举位▲张倍墙写 北大单张铭写 叔新有,命邮 排序问题 抽象数据类型ADT ■ Google等搜索引擎返回结果排级 图书馆员书目编号、上架 抽象数据类型是定义了一组运算 各种排名 的数学模型 (霜与B)x套学排名 剥离存储与实现细节 保研成绩排名 在适当的抽象层次上考虑程序的 Windows资源管理器,文件查看 结构和算法 封装和信息隐蔽 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 栈的不同存储实现 ■逻辑、存储、运算三者不同,都 插入、删除、检索都只能被限制在 可以看作不同数据结构 同一端的线性表先进后出LFo ■忽略存储,强调逻辑、运算则为 顺序实现 ADT [3 max size-1 ■不特别指明,允许使用sTL ■链表实现 機顶 北真大学张铭编写 聊张帖写 权新有,究

10 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 55 散列（hashing）的方法 H(k) = k % 11 0 1 2 3 4 5 6 7 8 9 10 77 14 7 75 110 6295 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 56 数据的运算 „ 逻辑结构和存储结构都相同, 但 运算不同, 则数据结构不同 „ 例如, 栈与队列 „ 对于一种数据结构, 常见的运算 „ 建立、清除数据结构 „ 插入、删除、修改某个数据元素 „ 排序、检索 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 57 排序问题 „ Google等搜索引擎返回结果排级 „ 图书馆员书目编号、上架 „ 各种排名 „ 《泰晤士报》 大学排名 „ 《福布斯》 富豪榜 „ 保研成绩排名 „ …… „ Windows资源管理器，文件查看 „ …… 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 58 抽象数据类型ADT „ 抽象数据类型是定义了一组运算 的数学模型 „ 剥离存储与实现细节 „ 在适当的抽象层次上考虑程序的 结构和算法 „ 封装和信息隐蔽 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 59 „ 逻辑、存储、运算三者不同，都 可以看作不同数据结构 „ 忽略存储，强调逻辑、运算则为 ADT „ 不特别指明，允许使用STL 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 60 栈的不同存储实现 „ 插入、删除、检索都只能被限制在 同一端的线性表先进后出LIFO „ 顺序实现 „ 链表实现 栈顶 5 4 8 7 1 element [0] [1] [2] [3] [4] max_size - 1 N 1 2 3 4 栈顶