1_数据结构与算法_北京大学2008_张铭_数据结构和算法简介

《1_数据结构与算法_北京大学2008_张铭_数据结构和算法简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法第1章概论本章由赵海燕主写http://db.pku.edu.cn/mzhang/DS/http://www.jpk.pku.edu.cn/pkujpk/course/sjjg张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材数据结构+算法=？数据结构有哪些基本的工具如何用基本工具制造复杂工具算法如何使用这些工具解决具体的问题“算法＋数据结构＝程序”表达了算法与数据结构的联系及其在程序中的地位程序就是在数据的某些特定的结构和表示的基础上对于算法的描述算法与数据结构是程序设计中相辅相成、不可分割的两个方面数据结构vs计算

2、机科学核心基础课程任何问题都离不开数据数据是计算机化的信息（对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述）后续专业课程学习的必要知识与技能准备编译技术要使用栈、散列表及语法树操作系统中用队列、存储管理表及目录树数据库系统运用线性表、多链表、及索引树etc.课程目标学会如何有效地组织信息，以便支持高效的数据处理掌握常用的基本数据结构及其应用学会合理地组织数据，有效地表示数据，有效地处理数据基本掌握算法的设计与分析技术提高程序设计能力与程序的质量提高使用计算机解决问题的能力第1章概论问题求解数据结构及抽象数据类型算法的特性及分类算法的效率度

3、量数据结构的选择和评价1.1问题求解问题求解数据结构设计方法描述语言算法理论数据模型问题求解建立问题的模型描述问题域中实际对象的数据及其相互关系映射到计算机的存储器上，编程序模拟对象领域中的求解过程问题求解求解问题计算机科学就是“一种关于信息结构转换的科学”(Wegnor)；（数据结构也称“信息结构”）计算机科学是“算法的学问”，算法是精确定义的一系列规则，指出怎样从给定的输入信息经过有限步骤产生所求的输出信息(D.Knuth)其实数据结构与算法两者互为存在（数据结构离不开施于其上的操作，同时算法也必然离不开作为其处理对象和结果的数据）问题求解例子：已知一

4、组人的身高，从中找出最高、最矮的，再找出身材最适中的（诸如101个人中，找出高度第51位的那个）；TowerofHanio:给出3个柱子和n个圆盘，起初所有盘子均放在最左边的柱子上，按大盘在下的顺序堆放；如何把所有盘子移到最右的柱子上？要求任何盘子都不能放到比它小的圆盘上面1.2数据结构涉及如下三个方面数据的逻辑结构　：表示数据元素之间的逻辑关系；数据的存储结构　：数据结构在计算机存储器中的表示，也称存储表示；数据的运算（结构的行为特征）：作用于数据结构上的运算。例如：检索，插入，删除等简言之，一类按照一定逻辑关系组织起来的数据的表示及其相关操作。常见的基

5、本数据结构：线性表，字符串，堆栈与队列，树与二叉树，字典，图数据的逻辑结构二元组B=(K,R)–K：结点（初等或组合类型）的有限集合–R:K上的有穷关系的集合（一组二元关系）K是由有限个结点组成的集合，每一个结点都代表一个数据或一组有明确结构的数据关系集R是定义在集合K上的一组关系，其中每个关系(relation)r（r∈R）都是K×K上的二元关系，用它描述结点数据之间的逻辑关系–例如,r={

6、ki∈K,1

7、中如母系血缘关系r、远亲关系r*、和非血缘的亲情关系r’等等，每一个关系要给出具体人员的关系元组例如：母子关系（戴爱莲，张远）兄弟关系（张远，张立）妯娌关系（戴爱莲，李美英）结点类型：基本数据类型整数类型(integer)：该类型规定了所能表示的整数范围，在计算机中一般使用1个字节到4个字节来存储整数实数类型(real)：计算机的浮点数据类型所能表示的数值范围和精度是有限的。机器一般使用4个字节到8个字节来存储浮点数布尔类型(boolean)：取值为真(true)和假(false)，在C++语言中一般使用整数0表示false，用非0表示true结点类型：基

8、本数据类型字符类型(char)：用单个字节（8bit，最高位bit为0）表示ASCII字符集中的字符汉字符号需要使用2个字节（每个字节的最高位bit为1）的编码，单个字节对于汉字是没有独立含义的在C++中把双字节表示中文符号的字节类型称为w_char类型（widecharacter）。目前国际上已经采用了统一的扩展字符集合标准UNICODE，这一标准允许英、日、韩、阿拉伯语等文字的混合文字处理结点类型：基本数据类型指针类型(pointer)：用于表示机器内存地址，指针表示指向某一内存单元的地址由于机器的指令系统一般采用32bit或64bit的地址长度，所以

9、指针类型也相应地用4个字节或8个字节来表示一个指针指针值的存储和指