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

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