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

数据结构与算法第1章概论本章由赵海燕主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6数据结构+算法=？数据结构有哪些基本的工具如何用基本工具制造复杂工具算法如何使用这些工具解决具体的问题“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6“算法＋数据结构＝程序”表达了算法与数据结构的联系及其在程序中的地位程序就是在数据的某些特定的结构和表示的基础上对于算法的描述算法与数据结构是程序设计中相辅相成、不可分割的两个方面“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6数据结构vs计算机科学核心基础课程任何问题都离不开数据数据是计算机化的信息（对现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述）后续专业课程学习的必要知识与技能准备•编译技术要使用栈、散列表及语法树•操作系统中用队列、存储管理表及目录树•数据库系统运用线性表、多链表、及索引树•etc.“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6课程目标学会如何有效地组织信息，以便支持高效的数据处理掌握常用的基本数据结构及其应用学会合理地组织数据，有效地表示数据，有效地处理数据基本掌握算法的设计与分析技术提高程序设计能力与程序的质量提高使用计算机解决问题的能力“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6第1章概论问题求解数据结构及抽象数据类型算法的特性及分类算法的效率度量数据结构的选择和评价“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.61.1问题求解问题求解数据结构设计方法描述语言算法理论数据模型“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6问题求解建立问题的模型描述问题域中实际对象的数据及其相互关系映射到计算机的存储器上，编程序模拟对象领域中的求解过程“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6问题求解求解问题计算机科学就是“一种关于信息结构转换的科学”(Wegnor)；（数据结构也称“信息结构”）计算机科学是“算法的学问”，算法是精确定义的一系列规则，指出怎样从给定的输入信息经过有限步骤产生所求的输出信息(D.Knuth)其实数据结构与算法两者互为存在（数据结构离不开施于其上的操作，同时算法也必然离不开作为其处理对象和结果的数据）“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6问题求解例子：已知一组人的身高，从中找出最高、最矮的，再找出身材最适中的（诸如101个人中，找出高度第51位的那个）；TowerofHanio:给出3个柱子和n个圆盘，起初所有盘子均放在最左边的柱子上，按大盘在下的顺序堆放；如何把所有盘子移到最右的柱子上？要求任何盘子都不能放到比它小的圆盘上面“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.61.2数据结构涉及如下三个方面数据的逻辑结构：表示数据元素之间的逻辑关系；数据的存储结构：数据结构在计算机存储器中的表示，也称存储表示；数据的运算（结构的行为特征）：作用于数据结构上的运算。例如：检索，插入，删除等简言之，一类按照一定逻辑关系组织起来的数据的表示及其相关操作。常见的基本数据结构：线性表，字符串，堆栈与队列，树与二叉树，字典，图“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6数据的逻辑结构二元组B=(K,R)–K：结点（初等或组合类型）的有限集合–R:K上的有穷关系的集合（一组二元关系）K是由有限个结点组成的集合，每一个结点都代表一个数据或一组有明确结构的数据关系集R是定义在集合K上的一组关系，其中每个关系(relation)r（r∈R）都是K×K上的二元关系，用它描述结点数据之间的逻辑关系–例如,r={ki-1,ki|ki∈K,1in}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6数据的逻辑结构：示例家族人员把每个成员个体的属性描述作为数据结点，而全部人员组成结点集K家族的各类亲属关系就是一组关系R，其中如母系血缘关系r、远亲关系r*、和非血缘的亲情关系r’等等，每一个关系要给出具体人员的关系元组例如：母子关系（戴爱莲，张远）兄弟关系（张远，张立）妯娌关系（戴爱莲，李美英）“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6结点类型：基本数据类型整数类型(integer)：该类型规定了所能表示的整数范围，在计算机中一般使用1个字节到4个字节来存储整数实数类型(real)：计算机的浮点数据类型所能表示的数值范围和精度是有限的。机器一般使用4个字节到8个字节来存储浮点数布尔类型(boolean)：取值为真(true)和假(false)，在C++语言中一般使用整数0表示false，用非0表示true“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6结点类型：基本数据类型字符类型(char)：用单个字节（8bit，最高位bit为0）表示ASCII字符集中的字符汉字符号需要使用2个字节（每个字节的最高位bit为1）的编码，单个字节对于汉字是没有独立含义的在C++中把双字节表示中文符号的字节类型称为w_char类型（widecharacter）。目前国际上已经采用了统一的扩展字符集合标准UNICODE，这一标准允许英、日、韩、阿拉伯语等文字的混合文字处理“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6结点类型：基本数据类型指针类型(pointer)：用于表示机器内存地址，指针表示指向某一内存单元的地址由于机器的指令系统一般采用32bit或64bit的地址长度，所以指针类型也相应地用4个字节或8个字节来表示一个指针指针值的存储和指针值的运算方式，在形式上与正整数相似但指针的运算一般仅限于两个指针地址的比较，加减，或对一个指针增减一个整数量等“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6结点类型：复合数据类型复合类型是由基本数据类型组合而成的数据结构类型例如：在程序语言中常用的数组类型，结构（记录）类型等皆属复合数据类型复合数据类型本身，又可以参与定义结构更为复杂的结点类型结点的类型不限于基本数据类型，可以根据应用的需要来灵活定义“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6结构的分类讨论逻辑结构（K,R）的分类，一般把讨论重点放在关系集R上。用R的性质来刻划数据结构的特点，并对数据结构进行分类：线性结构（linearstructure）树型结构（treestructure）图结构（graphstructure）“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性结构关系r是一种线性关系，或称为“前后关系”，有时也称为“大小关系”。关系r是有向的，且满足全序性和单索性等约束条件全序性是指，线性结构的全部结点两两皆可以比较前后（关系r）单索性是指，每一个结点x都存在唯一的一个直接后继结点y。如果其他结点z在y之前，则这个z也一定在x之前，不会在x，y之间在程序设计中应用最多“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6树型结构树型结构简称树结构，或称为层次结构。其关系r称为层次关系，或称“父子关系”、“上下级关系”等每一个结点可以有多于一个的“直接下级”，但是它只能有唯一的“直接上级”。树型结构的最高层次的结点称为根（root）结点。只有它没有父结点树型结构存在着很多变种，如二叉树结构，堆结构等，它们都有着各自独特的有效应用“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6图结构图结构有时称为结点互联的网络结构，因特网的网页链接关系就是一个非常复杂的图结构对于图结构的关系r没有加任何约束。这样也就无法象线性结构及树结构那样，利用关系r的约束来设计图结构的存储结构在日常应用中图结构往往只是层次结构的一种扩展――允许结点具有多个“直接上级结点”，关系r表现为树型结构约束的放松从数学上看，树型结构和图结构的基本区别就是“每个结点是否仅仅从属一个直接上级”。而线性结构和树型结构的基本区别是“每个结点是否仅仅有一个直接后继”“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6结点和结构对于数据结构（K,R），结点数据类型不限于基本数据类型，可以根据应用需要来灵活设计结点的数据类型可以认为数据结构的设计是一层一层地进行的先明确数据结点，及其主要关系r在分析关系r的同时，也要分析其数据结点的数据类型如果数据结点的逻辑结构比较复杂，那么把它作为下一个层次，再分析下一层次的逻辑结构这是一种自顶向下的分析设计方法“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6数据的存储结构计算机的主存储器的特性其存储空间提供了一种具有非负整数地址编码的，相邻单元的集合，其基本的存储单元是字节计算机的指令具有按地址随机访问存储空间内任意单元的能力，访问不同地址所需的访问时间基本相同“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6数据的存储结构用数学上的映射来表示，数据的存储结构是建立一种映射，对于数据逻辑结构（K，r），其中r∈R对它的结点集合K建立一个从K到存储器M的单元的映射：K→M，对于每一个结点j∈K都对应一个唯一的连续存储区域c∈M每一个关系元组（j1，j2）∈r（其中j1，j2∈K是结点），亦即j1，j2的逻辑后继关系应映射为存储单元的地址顺序关系（或指针的地址指向关系）四种基本存储映射方法：顺序、链接、索引、散列“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序方法用一块无空隙的存储区域存储数据称为顺序存储顺序存储把一组结点存储在按地址相邻的顺序存储单元里，结点间的逻辑后继关系用存储单元的自然顺序关系来表达顺序存储法为使用整数编码来访问数据结点提供了便利02136547S“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序方法顺序存储结构称为紧凑存储结构，其紧凑性是指它的存储空间除了存储有用数据外，没有用于存储其他附加的信息紧凑性可以用“存储密度”来度量：它是一个存储结构所存储的“有用数据”和该结构（包括附加信息）整个存储空间大小之比有时为了“用空间换取时间”，在存储结构中存储一些附加信息还是很必要的譬如，用于提高算法的执行速度，或者让算法实现更为简便等“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6链接方法利用指针，在结点的存储结构中附加指针字段称为链接法。两个结点的逻辑后继关系可以用指针的指向来表达任意的逻辑关系r，也可以使用这种指针地址来表达。一般的做法是将数据结点分为两部分:一部分存放结点本身的数据，称为数据字段另一部分存放指针，称指针字段，链接到某个后继结点，指向它的存储单元的开始地址。多个相关结点的依次链接