数据结构与算法_北京大学2008_张铭(全部课件pdf方便打印)

《数据结构与算法_北京大学2008_张铭(全部课件pdf方便打印)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构+算法=？“算法＋数据结构＝程序”数据结构与算法数据结构表达了算法与数据结构的联系及其在第1章概论有哪些基本的工具程序中的地位第1章概论如何用基本工具制造复杂工具程序就是在数据的某些特定的结构和表示的基本章由赵海燕主写础上对于算法的描述算法算法与数据结构是程序设计中相辅相成、不可http://http://db.pku.edu.cn/mzhang/DS/db.pku.edu.cn/mzhang/DS/如何使用这些工具解决具体的问题分割的两个方面http://http://www.jpk.pku.edu.cn/pkujpk/c

2、ourse/sjjgwww.jpk.pku.edu.cn/pkujpk/course/sjjg张铭，王腾蛟，赵海燕高等教育出版社，高等教育出版社，2008.6。“十一五”国家级规划教材2008.6。“十一五”国家级规划教材123数据结构vs计算机科学课程目标第1章概论学会如何有效地组织信息，以便支持核心基础课程任何问题都离不开数据高效的数据处理问题求解数据是计算机化的信息（对现实世界的事物采用计算掌握常用的基本数据结构及其应用数据结构及抽象数据类型机能够识别、存储和处理的形式所进行的描述）学会合理地组织数据，有效地表示数据，有效地处

3、后续专业课程学习的必要知识与技能准备算法的特性及分类理数据•编译技术要使用栈、散列表及语法树•操作系统中用队列、存储管理表及目录树基本掌握算法的设计与分析技术算法的效率度量•数据库系统运用线性表、多链表、及索引树提高程序设计能力与程序的质量数据结构的选择和评价•etc.提高使用计算机解决问题的能力4561.1问题求解问题求解问题求解问题求解建立问题的模型求解问题描述问题域中实际对象的数据及其相互关系映射到计算机科学就是“一种关于信息结构转换的科学”计算机的存储器上，编程序模拟对象领域中的求解(Wegnor)；（数据结构也称“信

4、息结构”）过程计算机科学是“算法的学问”，算法是精确定义的一系列设计方法描述语言规则，指出怎样从给定的输入信息经过有限步骤产生所数据结构求的输出信息(D.Knuth)其实数据结构与算法两者互为存在（数据结构离不开施于其上的操作，同时算法也必然离不开作为其处理对象和结果的数据）算法理论数据模型7891问题求解1.2数据结构数据的逻辑结构例子：涉及如下三个方面二元组B=(K,R)数据的逻辑结构：表示数据元素之间的逻辑关系；–K：结点（初等或组合类型）的有限集合已知一组人的身高，从中找出最高、最矮的，–R:K上的有穷关系的集合（一组二元关系

5、）数据的存储结构：数据结构在计算机存储器中的表示，也称再找出身材最适中的（诸如101个人中，找出存储表示；高度第51位的那个）；数据的运算（结构的行为特征）：作用于数据结构上的运算TowerofHanio:给出3个柱子和n个圆盘，起。例如：检索，插入，删除等K是由有限个结点组成的集合，每一个结点都代表一个初所有盘子均放在最左边的柱子上，按大盘在简言之，一类按照一定逻辑关系组织起来的数据的表示数据或一组有明确结构的数据下的顺序堆放；如何把所有盘子移到最右的柱及其相关操作。关系集R是定义在集合K上的一组关系，其中每个关系子上？要求任何盘子都不

6、能放到比它小的圆盘(relation)r（r∈R）都是K×K上的二元关系，用它描上面常见的基本数据结构：线性表，字符串，堆栈与队列，述结点数据之间的逻辑关系树与二叉树，字典，图–例如,r={

7、ki∈K,1

8、中的字符集K字节来存储整数汉字符号需要使用2个字节（每个字节的最高位bit为1）的编家族的各类亲属关系就是一组关系R，其中如母系血缘关系r、远亲关系r*、和非血缘的亲情关系r’等等，每一个关系要给出具体实数类型(real)：计算机的浮点数据类型所能表码，单个字节对于汉字是没有独立含义的人员的关系元组示的数值范围和精度是有限的。机器一般使用在C++中把双字节表示中文符号的字节类型称为w_char类型例如：母子关系（戴爱莲，张远）4个字节到8个字节来存储浮点数（widecharacter）。兄弟关系（张远，张立）目前国际上已经采用了统一的扩

9、展字符集合标准UNICODE妯娌关系（戴爱莲，李美英）布尔类型(boolean)：取值为真(true)和假，这一标准允许