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