国家级精品课程—《数据结构与算法》 第1章概论 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.jpk.pku.edu.cn/pkujpk/course/sigl 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:赵海燕 版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：赵海燕 ©版权所有，转载或翻印必究 第 1 章 概论
主要内容 问题求解 数据结构及抽象数据类型 算法的特性及分类 算法的效率度量 数据结构的选择和评价 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 问题求解 ◼ 数据结构及抽象数据类型 ◼ 算法的特性及分类 ◼ 算法的效率度量 ◼ 数据结构的选择和评价
问题求解 阶段和步骤 口获取需求(问题),以保证解决的问题正是需 要的(so/ ve the right problem); 口分析问题,将其分解为粒度更小的部分; 口针对问题(子问题)给出相应的解决方案,易 于理解和修改; 口估算解决方案的开销,以事先判断其可行性; 利用数学等工具的辅助得到正确且简洁的解决方案 口维护和演化 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 问题求解 ◼ 阶段和步骤 ❑ 获取需求（问题），以保证解决的问题正是需 要的（solve the right problem）； ❑ 分析问题，将其分解为粒度更小的部分； ❑ 针对问题（子问题）给出相应的解决方案，易 于理解和修改； ❑ 估算解决方案的开销，以事先判断其可行性； ◼ 利用数学等工具的辅助得到正确且简洁的解决方案 ❑ 维护和演化
问题求解 问题求解 设计方法 描述语言 数据结构 算法理论 (数据模型 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 问题求解 问题求解 数据结构 设计方法 描述语言 算法理论 数据模型
问题求解 通过 问题抽象 数据抽象 算法抽象 分析问题,应用数据结构和算法来设计 和实现高效的程序 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 问题求解 ◼ 通过 ◼ 问题抽象 ◼ 数据抽象 ◼ 算法抽象 分析问题，应用数据结构和算法来设计 和实现高效的程序
问题求解 实质 口描述问题域中实际对象的数据及其相互 关系 口映射到计算机的存储器上 口编写算法模拟对象领域中的求解过程 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 问题求解 ◼ 实质 ❑ 描述问题域中实际对象的数据及其相互 关系 ❑ 映射到计算机的存储器上 ❑ 编写算法模拟对象领域中的求解过程
问题求解 计算机科学就是“一种关于信息结构转换 的科学” Wegner) 计算机科学是“算法的学问”( Knuth) 其实数据结构与算法两者互为存在(数据 结构离不开施于其上的操作,同时算法也 必然离不开作为其处理对象和结果的数据)
问题求解 ◼ 计算机科学就是“一种关于信息结构转换 的科学” (Wegnor) ◼ 计算机科学是“算法的学问” (D.Knuth) ◼ 其实数据结构与算法两者互为存在 （数据 结构离不开施于其上的操作，同时算法也 必然离不开作为其处理对象和结果的数据）
问题求解 ■例子: 口从一组人中找出最高、最矮,及身高最适 中的人。 口有12个外表完全相同的球,只有一个不标 准,或轻或重,要求用天平以最少的次数 找出该球,并判定其轻重 口计算机专业课程安排。 ■问题抽象、数据抽象、算法抽象 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 问题求解 ◼ 例子： ❑ 从一组人中找出最高、最矮，及身高最适 中的人。 ❑ 有12个外表完全相同的球，只有一个不标 准，或轻或重，要求用天平以最少的次数 找出该球，并判定其轻重。 ❑ 计算机专业课程安排。 ◼ 问题抽象 、数据抽象、算法抽象
数据结构 数据的逻辑结构 口图树二叉树线性表 数据的存储结构 口顺序方法、链接方法逻 存 索引方法、散列方法 辑数据储 结构 数据的运算 口增、删、查、改 口排序、检索 运算 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 数据结构 ◼ 数据的逻辑结构 ❑ 图树二叉树线性表 ◼ 数据的存储结构 ❑ 顺序方法、链接方法 ❑ 索引方法、散列方法 ◼ 数据的运算 ❑ 增、删、查、改 ❑ 排序、检索 存 数据 储 结构 逻 辑 运 算
数据结构 一类按照一定逻辑关系组织起来的数据的 表示及其相关操作 口逻辑结构:表示数据元素之间的逻辑关系; 口存储结构:数据结构在计算机存储器中的表示, 也称存储表示; 运算(结构的行为特征):作用于数据结构上的 运算。 常见的基本数据结构:线性表,字符串,堆栈与 队列,树与二叉树,字典,图 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 数据结构 ◼ 一类按照一定逻辑关系组织起来的数据的 表示及其相关操作 ❑ 逻辑结构：表示数据元素之间的逻辑关系； ❑ 存储结构：数据结构在计算机存储器中的表示， 也称存储表示； ❑ 运算（结构的行为特征）：作用于数据结构上的 运算。 常见的基本数据结构：线性表，字符串，堆栈与 队列，树与二叉树，字典，图