北大数据结构课件,内部资料,精品

北大数据结构课件,内部资料,精品

数据结构任课教员：张铭、赵海燕、冯梅萍、王腾蛟http://www.77cn.com.cn/mzhang/DS/北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究

北大数据结构课件,内部资料,精品

教学目的掌握常用的基本数据结构的ADT 及其应用 学会合理地组织数据, 有效地表 示数据, 有效地处理数据 基本掌握算法的设计分析技术 提高程序设计的质量北京大学信息学院 ©版权所有，转载或翻印必究 Page 2

北大数据结构课件,内部资料,精品

教学要求平时(考勤+作业)20％ 上机(+报告)30％ 期中20％ 期末30％北京大学信息学院 ©版权所有，转载或翻印必究 Page 3

北大数据结构课件,内部资料,精品

诚信端正学习态度、调动学习兴趣提倡讨论，但严禁抄袭可以讨论思路，请同学看算法的逻辑问题和效率问题。 但要亲自动手实现。发现抄袭，则抄袭者和被抄袭者本次作业或上机题 计双倍倒扣分，即得 - 20分。以后的作业题会得到 重点检查。严重的期评将给予不及格处理数据结构教学计划和要求北京大学信息学院©版权所有，转载或翻印必究Page 4

北大数据结构课件,内部资料,精品

按时提交作业，严禁抄袭所有书面作业和上机作业都必须在指定的期限 内完成并提交 一般周三交书面作业。除非不可抗拒的客观原 因，请严格按提交时间完成书面作业和上机作 业。例如，一个满分为10分的作业题，记分标 准为：（1）准时提交，满分可达10分（个别加分）； （2）延迟3天之内提交，满分可达7分； （3）延迟7天之内提交，满分可达3分； （4）7天之后提交或不交，得分 - 5分。 （5）抄袭得 – 20分。北京大学信息学院 ©版权所有，转载或翻印必究 Page 5

北大数据结构课件,内部资料,精品

书面作业提交要求1) 写学号、名字 2) 每次作业，都在作业本或电子稿的word文 档中写上“我保证没有抄袭他人作业”的诚实保 证。否则，计零分或根据抄袭情况倒扣分。 3) 写算法分析、注释 4) 算法中直接使用的函数、过程先写ADT， 并说明函数功能、入口参数、出口参数 5) 注意算法格式(层次嵌套、不同功能块之间 留空)北京大学信息学院 ©版权所有，转载或翻印必究 Page 6

北大数据结构课件,内部资料,精品

上机题提交要求上机作业提交时打一个zip包，学号+姓名+作业次数，如”00308096张宁1.zip”包中含有： 1. readme.txt文件，把你的程序运行环境、 编译运行步骤、程序功能等等简单说明一下。 2. 附加了诚实代码保证和足够注释的源程序 以及相关的项目和资源文件。例如，VC++中 的.dsw, .dsp文件，rc目录中的图像资源文 件；Jbuilder中的.jpr或.jpx文件，特殊的 Java包等等。 3. 上机实习总结报告北京大学信息学院 ©版权所有，转载或翻印必究 Page 7

北大数据结构课件,内部资料,精品

上机题编程风格要求1．诚实代码保证 2. 内部文档要求 3. 过程代码要求 4. 面向对象的代码要求北京大学信息学院©版权所有，转载或翻印必究Page 8

北大数据结构课件,内部资料,精品

教材许卓群、杨冬青、唐世渭、张铭，《数据结构 与算法》，高等教育出版社， 2004年 7月。 参考书目张铭、刘晓丹译, 《数据结构与算法分析》(C++第 二版)，电子工业出版社，2002年。（用1998年的 第一版也可以，也可以直接用英文原版） 张铭、刘晓丹译, 《数据结构与算法分析——Java 版》，电子工业出版社，2001年。 许卓群，《数据结构》，高等教育出版社，1988。 严蔚敏，《数据结构题集》，清华大学出版社北京大学信息学院 ©版权所有，转载或翻印必究 Page 9

北大数据结构课件,内部资料,精品

教学参考书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 10

北大数据结构课件,内部资料,精品

教学参考书(续)殷人昆，《数据结构——用面向对象方法与 C++描述》，清华大学出版社，1999。 张乃孝，裘宗燕，《数据结构——C++与面向 对象的途径》，高等教育出版社，2001。 张乃孝，《数据结构基础》，北京大学出版 社。 严蔚敏，《数据结构》 第二版(Pascal和语言 版都可以)，清华大学出版社。北京大学信息学院©版权所有，转载或翻印必究Page 11

北大数据结构课件,内部资料,精品

第一章 概论1.1 为什么要学习数据结构 1.2 什么是数据结构 1.3 抽象数据类型 1.4 算法的特性及分类 1.5 算法的效率度量 1.6 数据结构的选择和评价北京大学信息学院 ©版权所有，转载或翻印必究 Page 12

北大数据结构课件,内部资料,精品

1.1 为什么要学习数据结构计算机软件与理论学科的专业基础课程 后续专业课程学习的必要知识与技能准备编译技术要使用栈、散列表及语法树 操作系统中用队列、存储管理表及目录树 数据库系统运用线性表、多链表、及索引树 etc.增强读者求解复杂问题的能力北京大学信息学院 ©版权所有，转载或翻印必究 Page 13

北大数据结构课件,内部资料,精品

1.2 什么是数据结构 (data structure)数据的逻辑结构 数据的存储结构 数据的运算北京大学信息学院 ©版权所有，转载或翻印必究 Page 14

北大数据结构课件,内部资料,精品

1.2.1 数据的逻辑结构反映了我们对数据含义的解释 数据的逻辑结构可以用一组数据（表示为结点集合 K），以及这些数据之间的一组二元关系（关系集合 R）来表示：( K ，R )K是由有限个结点组成的集合，每一个结点都代表一个数据 或一组有明确结构的数据 而关系集R是定义在集合K上的一组关系，其中每个关系 (relation) r（r∈R）都是K×K上的二元关系，用它描述结 点数据之间的逻辑关系北京大学信息学院 ©版权所有，转载或翻印必究 Page 15

北大数据结构课件,内部资料,精品

数据的逻辑结构（示例）家族人员把每个成员个体的属性描述作为数据结点，而全部人员组成 结点集K 家族的各类亲属关系就是一组关系R, 其中如母系血缘关系 r、远亲关系r*、和非血缘的亲情关系r’等等，每一个关系要 给出具体人员的关系元组 例如：母子关系（王爱莲，张选） 兄弟关系（张选，张立） 妯娌关系 （王爱莲，李美英）北京大学信息学院 ©版权所有，转载或翻印必究 Page 16