搜索
东北大学信息学院计算机应用技术研究所杨雷yanglei@ise.neu.edu.cn数据结构课程简介•1946年世界上第一台数字式电子计算机•计算机应用普及也在以惊人的速度发展。计算机应用已经深入到人类社会的各个领域。早期的科学计算，现在更多地应用在信息处理方面。计算机处理的对象不再是纯粹的数值，而扩展到字符、声音、图象和表格等各种各样的信息。信息的处理不再单纯的计算，而是一些如信息存储、信息检索等非数值计算的处理。–信息的表示是计算机科学的基础。要解决某一复杂问题，设计一个高效适用的程序，需要解决怎样合理地组织数据、建立合适的数据结构、提高程序执行的时间效率和空间效率。“数据结构”就是在此背景下逐步形成、发展起来。课程简介•数据结构+算法=程序•数据结构：问题的数据模型–线性结构：线性表、栈、队列、串、…..–非线性结构：树、图•算法：求解问题的策略–查找：–排序与其它课程的关系•先修课：程序设计语言–C程序设计语言•后续课：算法基础–部分数据结构的内容移至算法基础•.操作系统、数据库、编译原理….•“数据结构涉及到各方面的知识，–如计算机硬件范围的存储装置和存取方法；–在计算机软件范围中的文件系统，数据的动态存储与管理，信息检索；数学范围的许多算法知识，–还有一些综合性的知识，如编码理论、算子关系、数据类型、数据表示、数据运算、数据存取等各方面的知识。•因此，数据结构是数学、计算机硬件、软件三者之间的一门核心课程。课程的发展历程•数据结构作为一门独立的课程在国外是从1968年才开始的。1968年，美国的D.E.Knuth教授开创了数据结构的最初体系，他的名著《计算机程序设计技巧》较为系统地阐述了数据的逻辑结构和存储结构及其操作。•从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。•目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。第一章绪论1.1数据结构讨论的范畴1.2基本概念1.3算法和算法的量度1.1数据结构讨论的范畴NiklausWirth：Algorithm+DataStructures=Programs算法:数据结构:处理问题的策略问题的数学模型它正说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组指令，首先需要解决两个问题：即算法和数据结构。结构静力分析计算数值计算的程序设计问题━线性代数方程组━环流模式方程(球面坐标系)全球天气预报•数值计算解决问题的一般步骤：•数学模型→设计算法→编出程序→测试→最终解答•数值计算的关键是：如何得出数学模型（方程）？•程序设计人员比较关注程序设计的技巧例一：学生信息检索系统算法：?模型：?需要检索的项目如何检索。用户界面各种表格非数值计算的程序设计问题数据元素之间的相互关系一般无法用数学方程加以描述例二：计算机对弈算法：?模型：?对弈的规则和策略棋盘及棋盘的格局例三：教学计划编排问题算法：?模型：?课表编排的规则课程以及课程间关系由以上述例子可见，求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。–为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。–与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。学习数据结构的目的•数据结构课程集中讨论软件开发过程中的设计阶段、同时涉及编码和分析阶段的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”。所有能被输入到计算机中，且能被计算机处理的符号的集合。计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。它是信息的载体，它能够被计算机识别、存储和加工处理。数据:1.2基本概念计算机科学中，所谓数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。数据元素是数据（集合）中的一个“个体”是数据结构中讨论的基本单位。例如，学生信息检索系统中学生信息表中的一个记录、对弈问题中状态树的一个状态、排课问题中的一个顶点等，都被称为一个数据元素。数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个学生的数据元素可以是称之为组合项数据对象:是性质相同的数据元素的集合，是数据的一个子集。数据元素是数据对象的一个实例。例如，整数数据对象是集合N={…-2,-1,0,1,2…..}字母字符数据对象是集合N={‘A’,’B’…,’Z’}数据结构：带结构的数据元素的集合假设用三个4位的十进制数表示一个含12位数的十进制数。3214,6587,9345─a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3之间存在着“次序”关系a1,a2、a2,a33214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:又例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:a1a2a3a4a5a6行的次序关系:列的次序关系:row={a1,a2,a2,a3,a4,a5,a5,a6}col={a1,a4,a2,a5,a3,a6}a1a3a5a2a4a6a1a2a3a4a5a6数据结构：带结构的数据元素的集合再例，在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系:{ai,ai+1|i=1,2,3,4,5}或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。数据结构：带结构的数据元素的集合可见，不同的“关系”构成不同的“结构”数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构数据的逻辑结构数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。•数据结构包括逻辑结构和物理结构。•数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关。•我们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构。•数据结构在计算机中的标识（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。数据的存储结构——逻辑结构在存储器中的映象存储结构两方面的内容（1）“数据元素”的映象？（2）“关系”的映象？基本的存储方法•四种基本的存储方法：（1）顺序存储方法（2）链接存储方法（3）索引存储方法（4）散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息xy链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx在不同的编程环境中，存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。数据类型数据类型是和数据结构密切相关的一个概念。它最早出现在高级程序设计语言中，用以刻划程序中操作对象的特性。在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。例如，C语言中提供的基本数据类型整型int浮点型float字符型char逻辑型bool（C++语言）双精度型double实型（C++语言）数据类型是一个值的集合和定义在此集合上的一组操作的总称。类型显式地或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许进行的操作。•在高级程序设计语言中，数据类型可分为两类：•原子类型–值是不可分解的。–如C语言中整型、字符型、浮点型、双精度型等基本类型，分别用保留字int、char、float、double标识。•结构类型–值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。–例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。•在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而数据类型则可被看成是由一种数据结构和定义在其上的一组操作所组成的。抽象数据类型(AbstractDataType简称ADT):•由用户定义，用以表示应用问题的数据模型•由基本的数据类型组成,并包括一组相关的服务（或称操作）•数据封装和信息隐蔽，使用与实现相分离抽象数据类型•抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。例如，ADT复数的定义：数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{e1,e2|e1是复数的实数部分|e2是复数的虚数部分}ADTComplex{基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex假设:z1和z2是上述定义的复数则Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的结果ADT有两个重要特征:数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。•抽象数据类型和数据类型实质上是一个概念。“抽象”的意义在于数据类型的数学抽象特性。•另一方面，抽象数据类型的范畴更广，它不再局限于各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。ADT与数据类型的关系抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉赋值参数只为操作提供输入值。引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。抽象数据类型的表示和实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。例如，对以上定义的复数。typedef