数据结构教案(苏1).ppt
《数据结构教案(苏1).ppt》由会员分享，可在线阅读，更多相关《数据结构教案(苏1).ppt（192页珍藏版）》请在冰点文库上搜索。
数据结数据结构构主讲：
苏仕华第一章绪论第一章绪论1.1引言1.2基本概念和术语1.3抽象数据类型1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求计算机是一门研究用计算机进行信息表示和处理的科学。
这里面涉及到两个问题：
信息的表示和信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率。
随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。
因此，为了编写一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。
在计算机发展的初期，人们使用计算机的主要目的是处理数值计算问题。
使用计算机解决一个具体问题时，一般需要经过下列几个步骤：
由于当时所涉及的运算对象是简单的整型、实型或布尔等类型的数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。
随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。
据统计，处理非数值计算性问题占了90%以上的计算机运行时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。
因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。
1.1引言著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出，算法+数据结构=程序。
这里的数据结构指的是数据的逻辑结构和存储结构，而算法则是对数据运算的描述。
由此可见，程序设计的实质是对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。
因此，要设计出一个“好”的程序，就必须有好的算法，而好的算法必须建立在研究数据的特性及数据之间存在的关系的基础上。
这些正是数据结构结构这门课程所要研究的内容。
到底什么是数据结构呢？
先通过一个例子来说明有关数据结构的概念。
例【1.1】电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：
（a1，b1）（a2，b2）（an，bn）其中ai，bi（i=1，2n）分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。
算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。
数据的结构，直接影响算法的选择和效率。
上述的问题是一种数据结构问题。
可将名字和对应的电话号码设计成：
二维数组、表结构、向量。
假定名字和其电话号码逻辑上已安排成n元向量的形式，它的每个元素是一个数对（ai，bi），1in数据结构还要提供每种结构类型所定义的各种运算的算法。
【例1.2】图书馆信息检索系统。
当我们根据书名查找某本书有关情况的时候；或者根据作者或某个出版社查找有关书籍的时候，或根据书刊号查找作者和出版社等有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机的自动检索。
若使用计算机处理上述图书检索问题，首先要建立一张图书基本信息表，列在每一行上的是一本书的信息，一般包括：
登录号、书名、作者、分类号、出版社和出版时间等项，登录号是唯一的。
如表1.1所示。
表1.1图书目录卡片表73.5612381998.11清华大学陈大鹏软件工程0126743573.3232652001.05人民邮电孙华英数据库原理0059205673.7521961999.12机械工业许海平操作系统0150942973.9611622000.08高等教育刘晓阳数据结构01771778分类号出版时间出版社作者书名登录号表中的数据元素（一行）可按登录号、书名、作者名等建立相应的索引表。
这些表构成的文件就是图书目录检索的数学模型。
计算机的主要操作是按某个特定要求（如书名、作者）对书目文档进行查询检索。
诸如此类的问题还有各种查号系统、仓库管理系统、帐务处理等。
这类问题中的处理对象之间都是一种最简单的线性关系，它们所对应的数学模型称为线性的数据结构。
【例1.3】图的m着色问题。
图的着色问题是由地图的着色问题引申而来的：
用m种颜色为地图着色，使地图的每个区域着一种颜色，且相邻区域的颜色不同。
如果把一个区域收缩为一个顶点，将相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图和一个区域邻接关系图，如图1.1（a）、（b）所示。
00101020203030404050506060707080809090第一季度第一季度第二季度第二季度第三季度第三季度第四季度第四季度东部东部西部西部北部北部（a）抽象的平面图（b）区域邻接关系图图1.1图的着色问题示意图19世纪50年代，英国学者提出了任何地图都可以用4种颜色来着色的4着色猜想问题。
过了100多年，这个问题才由美国学者在计算机上予以证明，这就是著名的4色定理。
如在图1.1中，颜色用数字表示，字母表示区域，则图中表示了不同区域的不同着色情况。
再例如，家族的血统关系、博奕树问题（人一机下棋）、计算机的文件系统等都是一种树形结构；而城市之间的交通网络、工程管理中的活动安排以及多叉路口交通灯管理等问题是图形结构的。
它们都是一种非线性的数据结构。
通过以上几例可以直接地认为：
数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
1.2基本概念和术语数据（Data）:
是对信息的一种符号表示。
在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
例如，一个代数方程的求解程序中所使用的数据是整数和实数，而对一个文本编辑程序中使用的数据是字符串。
随着计算机的发展以及计算机应用领域的扩大，数据的含义也随之拓展了。
例如，当今计算机可以处理的图形、图像、声音等，它们也都属于数据的范畴。
数据元素（DataElement）:
是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
一个数据元素可由若干个数据项组成。
数据项是数据的不可分割的最小单位。
如前例中的目录卡片表中的一张卡片（表格中的一行）、树中的一个节点、图的一个顶点等都是数据元素，有时一个数据元素可由若干个数据项（也称为字段、域、属性）组成，数据项是具有独立含义的最小标识单位。
如图书卡片信息中的登录号、书名、作者等。
数据对象（DataObject）：
是性质相同的数据元素的集合。
是数据的一个子集。
例如，大写字母数据对象就是集合A,B,Z。
数据结构（DataStructure）：
是相互之间存在一种或多种特定关系（结构）的数据元素的集合。
虽然至今没有一个关于数据结构的标准定义，但它一般包括以下三个方面的内容：
（1）数据元素之间的逻辑（或抽象）关系，也称为数据的逻辑结构逻辑结构。
（2）数据元素及其关系在计算机内的存储方式，称为数据的存储结构存储结构（物理结构物理结构）。
（3）数据的运算运算，即对数据元素施加的操作（行为）。
数据结构：
带结构结构的数据元素的集合一特性相同的据元素的集个数合，如果在据元素之存在一或数间种多特定的系，一据种关则称为个数结。
构指的是据元素之存在的系数间关又分和存这种结构为逻辑结构储结构数据的逻辑结构数据的逻辑结构是从逻辑关系上描述数据的，它与数据元素的存储结构无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
如上一节中表1.1所表示的图书目录卡片，表中数据元素之间的逻辑关系就是一种相邻关系：
对表中任一个结点，与它相邻且在它前面的结点称为直直接前趋，接前趋，这种直接前驱最多只有一个；与表中任一结点相邻且在其后面的结点称为直接后继，直接后继，也最多只有一个。
表中只有第一个结点没有直接前趋，称之为开开始结点始结点；也只有最后一个结点没有直接后继，称之为终端结点终端结点。
例如，表中的“操作系统”所在结点的直接前趋结点和直接后继结点分别是“数据结构”和“数据库原理”所在的结点，这种结点之间的关系就构成了图书目录卡片表的逻辑结构。
数据的逻辑结构又可分为两大类：
（1）线性结构线性结构的特征是：
数据元素（结点）之间存在着一对一的关系，且结构中有仅有一个开始结点和一个终端结点，其余结点都是有仅有一个直接前趋和一个直接后继。
因此，上述图书目录卡片表就是一个典型的线性结构。
（2）非线性结构非线性结构的特征是：
数据元素之间存在着一对多或多对多的关系，即一个结点可能有多个直接前趋和多个直接后继。
该结构包括树形结构、图形结构和网状结构等。
数据结构的逻辑结构常又细分为以下四类基本结构：
一、线性结构结构中的数据元素之间存在一对一的关系。
二、树型结构结构中的数据元素之间存在一对多的关系。
三、图状结构或网状结构结构中的数据元素之间存在多对多的关系。
四、集合结构中的数据元素除了同属于一种类型外，别无其它关系。
后三种都属于非线性结构从关系或结构分，数据结构可归结以下为四类:
数据结构的形式定义为：
数据结构是一个二元组：
Data-Structure=（D，S）其中：
D是数据元素的有限集，S是D上关系的有限集。
例复数的数据结构定义如下：
Complex=（C，R）其中：
C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。
R=P，P是定义在集合上的一种关系C1，C2。
例如，用当三个4位的十进制数表示一含个12位数的十进制数时，3214,6587,9345a1（3214）,a2（6587）,a3（9345）在据元素则数a1、a2和a3之存在间着“次序”关系a1,a2、a2,a33214，6587，93456587，3214，9345a1a2a3a2a1a3又例，在2行3列的二维数组中六元素个a1,a2,a3,a4,a5,a6之存在系间两个关:
行的次序关系行的次序关系:
row=,col=,a1a2a3a4a5a6列的次序关系列的次序关系:
若在6据元素个数a1,a2,a3,a4,a5,a6之存在如下的间次序关系次序关系:
|i=1,2,3,4,5数据结构是相互之间存在着某种逻辑关系的数据元素的集合。
可，不同的“见关系”成不同的“构结构”成则构一维数组的定。
义数据的存储结构数据的存储结构是数据在计算机中的存储表示（映象），亦称为数据的物理结构。
它包括数据元素和关系的表示，是依赖于计算机语言的。
数据的存储结构可以用以下四种基本的存储方法实现：
（1）顺序存储方法该方法是把逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里，由此得到的存储结构称为顺序存储结构顺序存储结构。
它通常是借助于程序设计语言的数组来描述的。
该方法主要应用于线性的数据结构，但非线性的数据结构也可通过某种线性化的方法来实现顺序存储。
（2）链接存储方法该方法是用一组不一定连续的存储单元存储逻辑上相邻的元素，元素间的逻辑关系是由附加的指针域表示的。
由此得到的存储结构称为链式存储结构链式存储结构。
它通常是借助于程序设计语言中的指针来描述的（3）索引存储方法该方法通常是在存储元素信息的同时，还建立附加的索引表。
表中的索引项一般形式是：
（关键字，地址），关键字是能唯一标识一个元素的一个数据项或多个数据项的组合。
（4）散列存储方法该方法的基本思想是根据元素的关键字直接计算出该元素的存储地址。
无论怎样定义数据结构，都应该将数据的逻辑结构、数据的存储结构及数据的运算这三方面看成一个整体。
因此，存储结构是数据结构不可缺少的一个方面。
同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。
选择何种存储结构来表示相应的逻辑结构，要视具体的应用系统要求而定，而主要考虑的还是运算方便及算法的时间和空间上的要求。
数据的运算数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合，最常用的运算有：
检索、插入、删除、更新、排序等。
数据运算是数据结构不可分割的一个方面，在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算性质的不同，可能导致完全不同的数据结构。
例如，若对线性表的插入、删除运算限制在表的一端进行，则该线性表称为栈；若对线性表的插入运算限制在表的一端，而删除运算限制在表的另一端，则该线性表称为队列。
数据类型：
（datatype）是和数据结构密切相关的一个概念。
所谓数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
在使用高级程序设计语言编写的程序中，每个变量、常量或表达式都有一个它所属的数据类型。
类型规定了在程序执行期间变量或表达式可能的取值范围以及在这些值上所允许的操作运算。
例如：
在FORTRAN语言中，变量的数据类型有整型、实型、和复数型；在C语言中有：
数据类型：
基本类型和构造类型基本类型：
整型、浮点型、字符型构造类型：
数组、结构、联合、指针、枚举型、自定义类型C语言中的整数类型，就给出了一个整型量的取值范围（依赖于不同的机器或编译系统），定义了对整型量可施加的加、减、乘、除和取模等算术运算。
在高级程序设计语言中，按“值”的不同特性，可将数据类型分为两类：
一类是其值不可分解的称为原子类型原子类型（或非结构类型）。
例如C语言中的基本类型（整型、实型、字符型和枚举类型）以及指针类型和空类型等简单类型；另一类则是结构类型，结构类型，其值可由若干个分量（或成分）按某种结构组成，它的分量可以是非结构型的，也可以是结构型的。
例如，C语言中数组、结构等类型。
通常数据类型可以看作是程序设计语言中已实现的数据结构。
1.3抽象数据类型抽象数据类型抽象数据类型（AbstractDataType,简简称称ADT）是20世纪70年代提出的一种新概念，它是抽象数据的组织和与之相关的操作。
一个ADT可以看作是定义了相关操作运算的一个数学模型。
例如，集合与集合的并、交、差运算就可以定义为一个抽象数据类型。
抽象数据类型可以看作是描述问题的模型，它独立与具体实现。
它的特点是将数据定义和数据操作封装在一起，使得用户程序只能通过在ADT中定义的某种操作来访问其中的数据，从而实现了信息的隐藏性。
这种抽象数据类型类似于C+中的类定义。
ADT的一般定义形式是：
的一般定义形式是：
ADT数据对象：
数据对象：
数据关系：
数据关系：
基本操作：
基本操作：
ADT其中数据对象和数据关系的定义用伪码描述其中数据对象和数据关系的定义用伪码描述。
基本操作的定义是：
基本操作的定义是：
（）初始条件：
初始条件：
操作结果：
操作结果：
初始条件：
描述操作执行之前数据结构和参数应满足的初始条件：
描述操作执行之前数据结构和参数应满足的条件条件;若不满足，则操作失败，返回相应的出错信息。
若不满足，则操作失败，返回相应的出错信息。
操作结果：
描述操作正常完成之后，数据结构的变化状操作结果：
描述操作正常完成之后，数据结构的变化状况和应返回的结果。
况和应返回的结果。
作为一个例子，看一个“圆”数据类型的描述。
我们知道，要表示一个圆一般应包括圆心的位置和半径的大小。
如果只关心圆的面积，那么这个抽象数据类型中就只需要有表示半径的数据。
假设要设计一个圆（Circle）抽象数据类型，它包括计算面积（area）、周长（circumference）的操作，Circle的抽象数据类型描述如下：
ADTCircle/圆的抽象数据类型描述Data非负实数表示圆的半径OperationsConstructor输入的初值：
非负实数处理：
给半径赋初值Area输入：
无处理：
计算圆面积输出：
圆的面积Circumference输入：
无处理：
计算圆周长输出：
圆周长ADTCircleC+类和对象#includeiostream.hclassCircleprivate:
doublex,y,r;public:
voidprint（）cout圆心圆心:
（x,y）endl;cout半径半径:
rendl;voidset（doublex1,doubley1,doubler1）x=x1;y=y1;r=r1;voidmain（）Circlep;p.set（0,0,2）;p.print（）;引例:
圆类定义类定义数据成员成员函数定义类对象对对象调用成员函数Circle类将圆的属性（圆心坐标和半径）和操作（print、set）封装在一起由于我们是以C语言为基础来描述算法的，而C语言中没有提供“类”这一数据类型，所以无法实现抽象数据类型，因此，我们将不采用ADT的形式来描述数据结构。
但读者只需要记住，ADT实际上等价于我们定义的数据的逻辑结构以及在逻辑结构上定义的抽象操作。
1.4算法和算法分析算法：
是对特定问题求解步骤的一种描述,算法是操作指令的有限序列，其中每一条指令表示一个或多个操作。
例如，我们要用计算机求解一个已知3个坐标点a（x1,y1）、b（x2,y2）、c（x3,y3）所构成的三角形的面积。
首先要根据实际问题，找出求解三角形面积的相关计算公式（抽象出数学模型），然后再逐步求解计算。
比如要计算面积，就必须先求边长，求边长的公式为：
求三角形面积的公式为：
在有了上述公式（模型）之后，就要给出求解问题的过程（又叫解题的方法或步骤），这就是所谓的算法。
该问题的算法描述如下：
（1）输入三角形的3个坐标点a、b和c；
（2）计算三条边长及边长和的一半；（3）计算三角形的面积area;（4）输出三角形的边长和面积。
然后再根据算法的描述，编写相应的程序代码上机调试运行直至得出正确结果。
#include/包含输入/输出流#include/包含数学函数的头文件doubleedge（doublex1,doublex2,doubley1,doubley2）/求三角形的边长doublelen;len=sqrt（x1-x2）*（x1-x2）+（y1-y2）*（y1-y2）；/求边长returnlen;voidmain（）doublex1,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）*（s-bc）；/计算面积printf（area=%lfn”,area）；/输出三角形面积#includeclassPointpublic:
voidSetPoint（floata,floatb）x=a;y=b;/设置X、Y值voidPrint（）cout”（”x”,”y”）”endl;voidMove（floata,floatb）x=x+a;y=y+b;/移动坐标点private:
floatx,y;voidmain（）PointA，B，C;A.SetPoint（3.0,4.0）;B.SetPoint（6.0,8.0）;C.SetPoint（9.0,4.0）;A.Print（）;/输出A点坐标的X、Y值B.Print（）;C.Print（）;B.Move（2,-3）;C.Move（-3,5）;/移动C点坐标的X-3,Y+5B.Print（）;C.Print（）;/输出C点坐标的X、Y值从上述的实例可以看出，算法是对问题求解步骤的一种描述。
通俗地说：
一个算法就是一种解题的方法。
算法必须满足以下五个准则：
（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
（2）确定性算法中每一条指令必须有确切的含义。
不存在二义性。
且算法只有一个入口和一个出口。
（3）可行性一个算法是可行的。
即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
（4）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
（5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
因此，一个程序如果对任何输入都不会陷入无限循环，则它就是一个算法。
算法的含义与程序十分相似，但二者是有区别的，程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。
例如上述求解三角形面积的算法就是中文语言描述的。
目前最常用的描述算法的语言有两种，一种是用类PASCAL，另一种是类C，类似于C语言，而又不完全同C语言。
类C语言借助于C语言的语法结构，辅之以自然语言的叙述，使得用它编写的算法既具有良好的结构，又不拘泥于具体程序语言的某些细节。
因此，类C语言使得算法易读易写。
1.4.2算法设计要求评价一个好的算法有以下几个标准:
（1）正确性（Correctness）算法应满足具体问题的需求。
（2）可读性（Readability）算法应该好读。
以有利于阅读者对程序的理解。
（3）健状性（Robustness）算法应具有容错处理。
当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。
（4）效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般，这两者与问题的规模有关。
1.4.3算法分析（效率的度量）求解一个问题可能有多种不同的算法，而算法的好坏直接影响程序的执行效率，且不同的算法之间的运行效率相差巨大。
那么，又如何来评价算法的优劣而从中选择好的算法呢？
显然，算法的“正确性”是首先要考虑的。
所谓一个算法的正确性，是指对于一切合法的输入数据，该算法经过有限时间的执行都能得到正确的结果，此外，应主要考虑如下几点：
（1）执行算法所耗费的时间，即时间复杂性；
（2）执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；（3）算法应易于理解、易于编程，易于调试等，即可读性和可操作性。
在以上几点当中，最主要的还是时间复杂性。
一个算法所耗费的时间，应是该算法中每条语句的执行时间之和。
每条语句的执行次数又称为频度，频度，所以每条语句的执行时间就是该语句的执行次数（频度频度）与该语句执行一次所需时间的乘积。
由于计算机之间的性能千差万别，不能以一个统一的标准来度量，因此，通常就将每条语句的执行时间忽略，而以语句的执行频度作为衡量一个算法好坏的主要参数。
一般情况下，算法中基本操作重复执行的次数是问题规模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成立时,循环才会终止，因此它的频度为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）与nn33之比是一个不等零的常数，则称T（n）和nn33是同阶的，或者说T（n）和nn33的数量级相同，可记为T（n）=O（n3）。
这时,我们称T（n）=O（n3）是矩阵乘积算法的渐进近时间复杂度。
语句频度：
是指该语句重复执行的次数定义
升级会员 