数据结构教案(苏1).ppt

1、 数 据 结 数 据 结 构构 主讲：苏仕华 第一章 绪 论第一章 绪 论1.1 引言1.2 基本概念和术语1.3 抽象数据类型1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示和信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据

2、结构这门课所要研究的问题。在计算机发展的初期，人们使用计算机的主要目的是处理数值计算问题。使用计算机解决一个具体问题时，一般需要经过下列几个步骤：由于当时所涉及的运算对象是简单的整型、实型或布尔等类型的数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，处理非数值计算性问题占了 90%以上的计算机运行时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。1.

3、1 引言 著名的瑞士计算机科学家沃思(N.Wirth)教授曾提出，算法+数据结构=程序。这里的数据结构指的是数据的逻辑结构和存储结构，而算法则是对数据运算的描述。由此可见，程序设计的实质是对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。因此，要设计出一个“好”的程序，就必须有好的算法，而好的算法必须建立在研究数据的特性及数据之间存在的关系的基础上。这些正是数据结构结构这门课程所要研究的内容。到底什么是数据结构呢？先通过一个例子来说明有关数据结构的概念。例【1.1】电话号码查询系统 设有一个电话号码薄，它记录了 N 个人的名字和其相应的电话号

4、码，假定按如下形式安排：(a1，b1)(a2，b2)(an，bn)其中 ai，bi(i=1，2n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成 n元向量的形式，它的每个元素是一个数对 (ai，bi)，1in 数据结

5、构还要提供每种结构类型所定义的各种运算的算法。【例 1.2】图书馆信息检索系统。当我们根据书名查找某本书有关情况的时候；或者根据作者或某个出版社查找有关书籍的时候，或根据书刊号查找作者和出版社等有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机的自动检索。若使用计算机处理上述图书检索问题，首先要建立一张图书基本信息表，列在每一行上的是一本书的信息，一般包括：登录号、书名、作者、分类号、出版社和出版时间等项，登录号是唯一的。如表 1.1 所示。表 1.1 图书目录卡片表 73.5612381998.11 清华大学陈大鹏 软件工程0126743573.323

6、2652001.05人民邮电孙华英 数据库原理0059205673.7521961999.12机械工业许海平 操作系统0150942973.9611622000.08高等教育刘晓阳 数据结构01771778分类号出版时间出版社 作 者 书 名登录号 表中的数据元素(一行)可按登录号、书名、作者名等建立相应的索引表。这些表构成的文件就是图书目录检索的数学模型。计算机的主要操作是按某个特定要求（如书名、作者）对书目文档进行查询检索。诸如此类的问题还有各种查号系统、仓库管理系统、帐务处理等。这类问题中的处理对象之间都是一种最简单的线性关系，它们所对应的数学模型称为线性的数据结构。【例 1.3】图的

7、m 着色问题。图的着色问题是由地图的着色问题引申而来的：用 m 种颜色为地图着色，使地图的每个区域着一种颜色，且相邻区域的颜色不同。如果把一个区域收缩为一个顶点，将相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图和一个区域邻接关系图，如图 1.1(a)、(b)所示。0 0101020203030404050506060707080809090第一季度第一季度 第二季度第二季度 第三季度第三季度 第四季度第四季度东部东部西部西部北部北部 (a)抽象的平面图(b)区域 邻接关系图 图 1.1 图的着色问题示意图 19 世纪 50 年代，英国学者提出了任何地图都可以用 4 种颜色来着色

8、的 4 着色猜想问题。过了 100 多年，这个问题才由美国学者在计算机上予以证明，这就是著名的 4 色定理。如在图 1.1 中，颜色用数字表示，字母表示区域，则图中表示了不同区域的不同着色情况。再例如，家族的血统关系、博奕树问题（人一机下棋）、计算机的文件系统等都是一种树形结构；而城市之间的交通网络、工程管理中的活动安排以及多叉路口交通灯管理等问题是图形结构的。它们都是一种非线性的数据结构。通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。1.2 基本概念和术语数据(D

9、ata):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。例如，一个代数方程的求解程序中所使用的数据是整数和实数，而对一个文本编辑程序中使用的数据是字符串。随着计算机的发展以及计算机应用领域的扩大，数据的含义也随之拓展了。例如，当今计算机可以处理的图形、图像、声音等，它们也都属于数据的范畴。数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。如前例中的目录卡片表中的一张卡片（表格中的一行）、树中的一个节点、图的一个顶点等都是数据元素

10、，有时一个数据元素可由若干个数据项（也称为字段、域、属性）组成，数据项是具有独立含义的最小标识单位。如图书卡片信息中的登录号、书名、作者等。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。例如，大写字母数据对象就是集合 A,B,Z。数据结构(Data Structure)：是相互之间存在一种或多种特定关系(结构)的数据元素的集合。虽然至今没有一个关于数据结构的标准定义，但它一般包括以下三个方面的内容：(1)数据元素之间的逻辑(或抽象)关系，也称为数据的逻辑结构逻辑结构。(2)数据元素及其关系在计算机内的存储方式，称为数据的存储结构存储结构(物理结构物理结构)。

11、(3)数据的运算运算，即对数据元素施加的操作(行为)。数据结构：带结构结构的数据元素的集合 一特性相同的据元素的集个数合，如果在据元素之存在一或数间种多特定的系，一据种关则称为个数结。构指的是据元素之存在的系数间关 又分和存这种结构为逻辑结构储结构 数据的逻辑结构数据的逻辑结构是从逻辑关系上描述数据的，它与数据元素的存储结构无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。如上一节中表 1.1 所表示的图书目录卡片，表中数据元素之间的逻辑关系就是一种相邻关系：对表中任一个结点，与它相邻且在它前面的结点称为直直接前趋，接前趋，这种直接前驱最多只有一个；与表中任一

12、结点相邻且在其后面的结点称为直接后继，直接后继，也最多只有一个。表中只有第一个结点没有直接前趋，称之为开开始结点始结点；也只有最后一个结点没有直接后继，称之为终端结点终端结点。例如，表中的“操作系统”所在结点的直接前趋结点和直接后继结点分别是“数据结构”和“数据库原理”所在的结点，这种结点之间的关系就构成了图书目录卡片表的逻辑结构。数据的逻辑结构又可分为两大类：(1)线性结构 线性结构的特征是：数据元素(结点)之间存在着一对一的关系，且结构中有仅有一个开始结点和一个终端结点，其余结点都是有仅有一个直接前趋和一个直接后继。因此，上述图书目录卡片表就是一个典型的线性结构。(2)非线性结构 非线性结

13、构的特征是：数据元素之间存在着一对多或多对多的关系，即一个结点可能有多个直接前趋和多个直接后继。该结构包括树形结构、图形结构和网状结构等。数据结构的逻辑结构常又细分为以下四类基本结构：一、线性结构 结构中的数据元素之间存在一对一的关系。二、树型结构 结构中的数据元素之间存在一对多的关系。三、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。四、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。后三种都属于非线性结构 从关系或结构分，数据结构可归结以下为四类:数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D 是数据元素的有限集，S是 D

14、 上关系的有限集。例 复数的数据结构定义如下：Complex=(C，R)其中：C 是含两个实数的集合 C1，C2，分别表示复数的实部和虚部。R=P，P 是定义在集合上的一种关系 C1，C2 。例如，用当三个 4 位的十进制数表示一含个 12 位数的十进制数时，3214,6587,9345 a1(3214),a2(6587),a3(9345)在据元素 则数a1、a2 和 a3 之存在间着“次序”关系 a1,a2 、a2,a3 3214，6587，9345 6587，3214，9345a1 a2 a3a2 a1 a3 又例，在 2 行 3 列的二维数组中六元素个a1,a2,a3,a4,a5,a6之

15、存在系间两个关:行的次序关系行的次序关系:row=,col=,a1 a2 a3 a4 a5 a6列的次序关系列的次序关系:若在 6 据元素个数a1,a2,a3,a4,a5,a6 之存在如下的间次序关系次序关系:|i=1,2,3,4,5 数据结构是相互之间存在着某种逻辑关系的数据元素的集合。可，不同的“见关系”成不同的“构结构”成则构一维数组的定。义 数据的存储结构数据的存储结构是数据在计算机中的存储表示（映象），亦称为数据的物理结构。它包括数据元素和关系的表示，是依赖于计算机语言的。数据的存储结构可以用以下四种基本的存储方法实现：(1)顺序存储方法 该方法是把逻辑上相邻的结点存储在物理位置上也

16、相邻的连续存储单元里，由此得到的存储结构称为顺序存储结构顺序存储结构。它通常是借助于程序设计语言的数组来描述的。该方法主要应用于线性的数据结构，但非线性的数据结构也可通过某种线性化的方法来实现顺序存储。(2)链接存储方法 该方法是用一组不一定连续的存储单元存储逻辑上相邻的元素，元素间的逻辑关系是由附加的指针域表示的。由此得到的存储结构称为链式存储结构链式存储结构。它通常是借助于程序设计语言中的指针来描述的(3)索引存储方法 该方法通常是在存储元素信息的同时，还建立附加的索引表。表中的索引项一般形式是：(关键字，地址)，关键字是能唯一标识一个元素的一个数据项或多个数据项的组合。(4)散列存储方法

17、 该方法的基本思想是根据元素的关键字直接计算出该元素的存储地址。无论怎样定义数据结构，都应该将数据的逻辑结构、数据的存储结构及数据的运算这三方面看成一个整体。因此，存储结构是数据结构不可缺少的一个方面。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，要视具体的应用系统要求而定，而主要考虑的还是运算方便及算法的时间和空间上的要求。数据的运算数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合，最常用的运算有：检索、插入、删除、更新、排序等。数据运算是数据结构不可分割的一个方面，在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及

18、其运算性质的不同，可能导致完全不同的数据结构。例如，若对线性表的插入、删除运算限制在表的一端进行，则该线性表称为栈；若对线性表的插入运算限制在表的一端，而删除运算限制在表的另一端，则该线性表称为队列。数据类型：(data type)是和数据结构密切相关的一个概念。所谓数据类型是一个值的集合和定义在这个值集上的一组操作的总称。在使用高级程序设计语言编写的程序中，每个变量、常量或表达式都有一个它所属的数据类型。类型规定了在程序执行期间变量或表达式可能的取值范围以及在这些值上所允许的操作运算。例如：在 FORTRAN 语言中，变量的数据类型有整型、实型、和复数型；在 C 语言中有：数据类型：基本类型

19、和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义类型 C 语言中的整数类型，就给出了一个整型量的取值范围(依赖于不同的机器或编译系统)，定义了对整型量可施加的加、减、乘、除和取模等算术运算。在高级程序设计语言中，按“值”的不同特性，可将数据类型分为两类：一类是其值不可分解的称为原子类型原子类型(或非结构类型)。例如 C 语言中的基本类型(整型、实型、字符型和枚举类型)以及指针类型和空类型等简单类型；另一类则是结构类型，结构类型，其值可由若干个分量(或成分)按某种结构组成，它的分量可以是非结构型的，也可以是结构型的。例如，C 语言中数组、结构等类型。通常数

20、据类型可以看作是程序设计语言中已实现的数据结构。1.3 抽象数据类型 抽象数据类型抽象数据类型(Abstract Data Type,简简称称 ADT)是 20 世纪 70 年代提出的一种新概念，它是抽象数据的组织和与之相关的操作。一个 ADT 可以看作是定义了相关操作运算的一个数学模型。例如，集合与集合的并、交、差运算就可以定义为一个抽象数据类型。抽象数据类型可以看作是描述问题的模型，它独立与具体实现。它的特点是将数据定义和数据操作封装在一起，使得用户程序只能通过在 ADT 中定义的某种操作来访问其中的数据，从而实现了信息的隐藏性。这种抽象数据类型类似于 C+中的类定义。ADT 的一般定义形

21、式是：的一般定义形式是：ADT 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT 其中数据对象和数据关系的定义用伪码描述其中数据对象和数据关系的定义用伪码描述。基本操作的定义是：基本操作的定义是：()初始条件：初始条件：操作结果：操作结果：初始条件：描述操作执行之前数据结构和参数应满足的初始条件：描述操作执行之前数据结构和参数应满足的条件条件;若不满足，则操作失败，返回相应的出错信息。若不满足，则操作失败，返回相应的出错信息。操作结果：描述操作正常完成之后，数据结构的变化状操作结果：描述操作正常完成之后，数据结构的变化状况和 应返回的结果。况和 应返回的结果。作为一个例子，看

22、一个“圆”数据类型的描述。我们知道，要表示一个圆一般应包括圆心的位置和半径的大小。如果只关心圆的面积，那么这个抽象数据类型中就只需要有表示半径的数据。假设要设计一个圆(Circle)抽象数据类型，它包括计算面积(area)、周长（circumference）的操作，Circle 的抽象数据类型描述如下：ADT Circle /圆的抽象数据类型描述 Data 非负实数表示圆的半径 Operations Constructor 输入的初值：非负实数 处理：给半径赋初值 Area 输入：无 处理：计算圆面积 输出：圆的面积 Circumference 输入：无 处理：计算圆周长 输出：圆周长 ADT

23、 Circle C+类和对象#include iostream.hclass Circleprivate:double x,y,r;public:void print()cout 圆心圆心:(x,y)endl;cout 半径半径:rendl;void set(double x1,double y1,double r1)x=x1;y=y1;r=r1;void main()Circle p;p.set(0,0,2);p.print();引例:圆类定义类定义数据成员成员函数定义类对象对对象调用成员函数Ci rcl e 类将圆的属性（圆心坐标和半径）和操作（pri nt、set）封装在一起 由于我们是

24、以 C 语言为基础来描述算法的，而 C 语言中没有提供“类”这一数据类型，所以无法实现抽象数据类型，因此，我们将不采用 ADT的形式来描述数据结构。但读者只需要记住，ADT 实际上等价于我们定义的数据的逻辑结构以及在逻辑结构上定义的抽象操作。1.4 算法和算法分析算法：是对特定问题求解步骤的一种描述,算法是操作指令的有限序列，其中每一条指令表示一个或多个操作。例如，我们要用计算机求解一个已知 3 个坐标点 a(x1,y1)、b(x2,y2)、c(x3,y3)所构成的三角形的面积。首先要根据实际问题，找出求解三角形面积的相关计算公式(抽象出数学模型)，然后再逐步求解计算。比如要计算面积，就必须先

25、求边长，求边长的公式为：求三角形面积的公式为：在有了上述公式(模型)之后，就要给出求解问题的过程（又叫解题的方法或步骤），这就是所谓的算法。该问题的算法描述如下：（1）输入三角形的 3 个坐标点 a、b 和 c；（2）计算三条边长及边长和的一半；（3）计算三角形的面积 area;（4）输出三角形的边长和面积。然后再根据算法的描述，编写相应的程序代码上机调试运行直至得出正确结果。#include /包含输入/输出流#include /包含数学函数的头文件double edge(double x1,double x2,double y1,double y2)/求三角形的边长 double len;

26、len=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)；/求边长 return len;void main()double x1,x2,x3,y1,y2,y3,s,area,ab,ac,bc；/说明变量 scanf(%lf%lf%lf”,&x1,&x2,&x3);scanf(%lf%lf%lf”,&y1,&y2,&y3);/输入坐标值 ab=edge(x1,x2,y1,y2)；/求边长 ac=edge(x1,x3,y1,y3)；bc=edge(x2,x3,y2,y3)；s=(ab+ac+bc)/2；/求边长和的一半 area=sqrt(s*(s-ab)*(s-ac)*(

27、s-bc)；/计算面积 printf(area=%lfn”,area)；/输出三角形面积#includeclass Point public:void SetPoint(float a,float b)x=a;y=b;/设置 X、Y 值 void Print()cout”(”x”,”y”)”endl;void Move(float a,float b)x=x+a;y=y+b;/移动坐标点 private:float x,y;void main()Point A，B，C;A.SetPoint(3.0,4.0);B.SetPoint(6.0,8.0);C.SetPoint(9.0,4.0);A.P

28、rint();/输出 A 点坐标的 X、Y 值 B.Print();C.Print();B.Move(2,-3);C.Move(-3,5);/移动 C 点坐标的 X-3,Y+5 B.Print();C.Print();/输出 C 点坐标的 X、Y 值 从上述的实例可以看出，算法是对问题求解步骤的一种描述。通俗地说：一个算法就是一种解题的方法。算法必须满足以下五个准则：（1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性 一个算法是可行的。即算法描述的操作都是可以通

29、过已经实现的基本运算执行有限次来实现的。（4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。（5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。因此，一个程序如果对任何输入都不会陷入无限循环，则它就是一个算法。算法的含义与程序十分相似，但二者是有区别的，程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。例如上述求解三角形面积的算法就是中文语言描述的。目前最常用的描述算法的语言有两种，一种是用类 PASCAL，另一种是类 C，类似于 C 语言，而又不完全同 C 语言。类 C 语言借助于 C 语言的语法

30、结构，辅之以自然语言的叙述，使得用它编写的算法既具有良好的结构，又不拘泥于具体程序语言的某些细节。因此，类 C 语言使得算法易读易写。1.4.2 算法设计要求评价一个好的算法有以下几个标准:(1)正确性(Correctness)算法应满足具体问题的需求。(2)可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。(3)健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.4.3 算

31、法分析（效率的度量）求解一个问题可能有多种不同的算法，而算法的好坏直接影响程序的执行效率，且不同的算法之间的运行效率相差巨大。那么，又如何来评价算法的优劣而从中选择好的算法呢？显然，算法的“正确性”是首先要考虑的。所谓一个算法的正确性，是指对于一切合法的输入数据，该算法经过有限时间的执行都能得到正确的结果，此外，应主要考虑如下几点：（1）执行算法所耗费的时间，即时间复杂性；（2）执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；（3）算法应易于理解、易于编程，易于调试等，即可读性和可操作性。在以上几点当中，最主要的还是时间复杂性。一个算法所耗费的时间，应是该算法中每条语句的执行时间之和。

32、每条语句的执行次数又称为频度，频度，所以每条语句的执行时间就是该语句的执行次数（频度频度）与该语句执行一次所需时间的乘积。由于计算机之间的性能千差万别，不能以一个统一的标准来度量，因此，通常就将每条语句的执行时间忽略，而以语句的执行频度作为衡量一个算法好坏的主要参数。一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数。例，计算 nn 两矩阵乘积的算法如下：（1）for(i=1，i=n;+i)（2）for(j=1;j=n;+j)（3）cij=0;（4）for(k=1;k=n;+k)（5）cij+=aik*bkj;其中，语句(1)的循环控制变量 i要增加到 n+1，测试 i=n+1

33、 成立时,循环才会终止，因此它的频度为 n+1，但它的循环体却只能执行 n 次；语句(2)作为(1)的循环内语句应执行 n 次，但语句(2)本身要执行 n+1 次，所以语句(2)的频度为n(n+1)，同理可得语句(3)、语句(4)和语句(5)的频度分别为 n2、n2(n+1)、n3。因此，该算法中所有语句的频度之和（即运行算法耗费的时间）为：T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3 =2n3+3n2+2n+1耗费时间 T(n)是矩阵阶数 n 的函数。矩阵乘积算法的时间复杂度 T(n)，当 n 足够大时，T(n)与 n n3 3之比是一个不等零的常数，则称 T(n)和 n n3 3是同阶的，或者说 T(n)和 n n3 3的数量级相同，可记为 T(n)=O(n3)。这时,我们称 T(n)=O(n3)是矩阵乘积算法的渐进近时间复杂度。语句频度：是指该语句重复执行的次数定义