文档介绍：数据结构与算法第1章概论数据结构与算法第1章概论本章由赵海燕主写 ./mzhang/DS/ .cn/pkujpk/course/sjjg 张铭,王腾蛟,赵海燕高等教育出版社, 2008. 6 。“十一五”国家级规划教材本章由赵海燕主写 ./mzhang/DS/ .cn/pkujpk/course/sjjg 张铭,王腾蛟,赵海燕高等教育出版社, 2008. 6 。“十一五”国家级规划教材““十一五十一五””国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 2008. 6 2008. 6 数据结构 + 算法 = ? ?数据结构?有哪些基本的工具?如何用基本工具制造复杂工具?算法?如何使用这些工具解决具体的问题?““十一五十一五””国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 2008. 6 2008. 6 “算法+数据结构=程序”?表达了算法与数据结构的联系及其在程序中的地位?程序就是在数据的某些特定的结构和表示的基础上对于算法的描述?算法与数据结构是程序设计中相辅相成、不可分割的两个方面““十一五十一五””国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 2008. 6 2008. 6 数据结构 vs 计算机科学?核心基础课程?任何问题都离不开数据?数据是计算机化的信息(对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述) ?后续专业课程学习的必要知识与技能准备?编译技术要使用栈、散列表及语法树?操作系统中用队列、存储管理表及目录树?数据库系统运用线性表、多链表、及索引树? etc. ““十一五十一五””国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 2008. 6 2008. 6 课程目标?学会如何有效地组织信息,以便支持高效的数据处理?掌握常用的基本数据结构及其应用?学会合理地组织数据,有效地表示数据, 有效地处理数据?基本掌握算法的设计与分析技术?提高程序设计能力与程序的质量?提高使用计算机解决问题的能力““十一五十一五””国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 2008. 6 2008. 6 第1章概论?问题求解?数据结构及抽象数据类型?算法的特性及分类?算法的效率度量?数据结构的选择和评价““十一五十一五””国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 2008. 6 2008. 6 问题求解问题求解数据结构设计方法描述语言算法理论数据模型““十一五十一五””国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 2008. 6 2008. 6 问题求解?建立问题的模型?描述问题域中实际对象的数据及其相互关系映射到计算机的存储器上,编程序模拟对象领域中的求解过程““十一五十一五””国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 2008. 6 2008. 6 问题求解?求解问题?计算机科学就是“一种关于信息结构转换的科学” (Wegnor) ;(数据结构也称“信息结构”) ?计算机科学是“算法的学问”,算法是精确定义的一系列规则,指出怎样从给定的输入信息经过有限步骤产生所求的输出信息(D. Knuth) ?其实数据结构与算法两者互为存在(数据结构离不开施于其上的操作,同时算法也必然离不开作为其处理对象和结果的数据) ““十一五十一五””国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社, 2008. 6 2008. 6 问题求解?例子: ?已知一组人的身高,从中找出最高、最矮的,再找出身材最适中的(诸如 101 个人中, 找出高度第 51 位的那个); ? Tower of Hanio: 给出 3个柱子和 n个圆盘,起初所有盘子均放在最左边的柱子上, 按大盘在下的顺序堆放;如何把所有盘子移到最右的柱子上?要求任何盘子都不能放到比它小的圆盘上面