(3.1)--数据结构第1章绪论.pdf

《(3.1)--数据结构第1章绪论.pdf》由会员分享，可在线阅读，更多相关《(3.1)--数据结构第1章绪论.pdf（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1章章绪绪论论计算机是一门研究用计算机进行计算机是一门研究用计算机进行信息表示信息表示和处理和处理的科学，这里面涉及到两个问题：的科学，这里面涉及到两个问题：信息的表示信息的表示信息的处理信息的处理信息的表示和组织又直接关系到处理信息的效率。信息的表示和组织又直接关系到处理信息的效率。因此，为了编写出一个“因此，为了编写出一个“好好”的程序，必须分析待处”的程序，必须分析待处理理对象的特征及各对象之间存在的关系对象的特征及各对象之间存在的关系，这就是数据，这就是数据结构这门课所要研究的问题。结构这门课所要研究的问题。提提 纲纲什么是数据结构什么是数据结构基本概念和术语基本概念和术语抽象数据

2、类型的表示和实现抽象数据类型的表示和实现算法和算法分析算法和算法分析什么是数据结构什么是数据结构计算机解决一个问题的计算机解决一个问题的步骤步骤：从具体问题中抽象出一个适当的从具体问题中抽象出一个适当的数学模型数学模型；设计解此数学模型的设计解此数学模型的算法算法；编制编制程序程序（程序设计语言描述数据结构和描程序设计语言描述数据结构和描述算法述算法）、测试测试，得到结果；得到结果；例例1：书：书数据；结构数据；结构（分类法分类法）：线性结构；：线性结构；算法算法查找查找例例2：格局格局数据；结构（格局之间的关系）：树数据；结构（格局之间的关系）：树结构；算法结构；算法搜索搜索演化演化例例3：

3、通道通道（两个路口两个路口）数据数据（顶点顶点）；结构；结构（不可同时通行不可同时通行）：图结构；算法：图结构；算法图着色图着色通道表示：通道表示：EC,AC,AD,DAEC,AC,AD,DA等等。ABCDEAB1AB通道通道颜色颜色DA2DA提提 纲纲什么是数据结构什么是数据结构基本概念和术语基本概念和术语抽象数据类型的表示和实现抽象数据类型的表示和实现算法和算法分析算法和算法分析基本概念和术语基本概念和术语 数据数据(Data)是对信息的一种是对信息的一种符号表示符号表示。在计算机科学中是指所有。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。能输入到计算机中并被计算

4、机程序处理的符号的总称。数据元素数据元素(Data Element)是数据的是数据的基本单位基本单位，在计算机程序中通常作为一个，在计算机程序中通常作为一个整整体体进行考虑和处理。进行考虑和处理。例：例：书；书；格局；格局；通道通道数据项（数据项（Data Item)一个数据元素可由若干个数据项组成，数据项是数据的不可一个数据元素可由若干个数据项组成，数据项是数据的不可分割的分割的最小单位最小单位。数据对象数据对象(Data Object)是性质相同的数据元素的是性质相同的数据元素的集合集合，是数据的一个子集。，是数据的一个子集。数据结构数据结构(Data Structure)是相互之间存在一

5、种或多种特定是相互之间存在一种或多种特定关系关系的的数据元素数据元素的集合。的集合。四种结构：四种结构：集合集合:结构中的数据元素除了同属于一种类型外，结构中的数据元素除了同属于一种类型外，别无其别无其它关系它关系。线性结构线性结构:结构中的数据元素之间存在结构中的数据元素之间存在一对一一对一的关系的关系。树型结构树型结构:结构中的数据元素之间存在结构中的数据元素之间存在一对多一对多的关系的关系。图状结构或网状结构图状结构或网状结构:结构中的数据元素之间存在结构中的数据元素之间存在多对多多对多的关系的关系。数据结构的形式定义数据结构的形式定义，数据结构是一个数据结构是一个二元组二元组：Data

6、_Structure=(D,S)其中：其中：D是是数据元素数据元素的有限集，的有限集，S是是D上上关系关系的有限集。的有限集。数据的逻辑结构数据的逻辑结构数据之间的相互关系称为逻辑结构数据之间的相互关系称为逻辑结构数据的物理结构数据的物理结构（存储结构存储结构）数据结构在计算机中的表示数据结构在计算机中的表示（数据元素数据元素，关系关系）数据结构的表示数据结构的表示数据元素之间的关系在计算机中有数据元素之间的关系在计算机中有两种两种不同的表示方法不同的表示方法顺序映象和非顺序映象顺序映象和非顺序映象顺序映象的特点顺序映象的特点借助元素在存储器中的借助元素在存储器中的相对位置相对位置来表示数据元

7、素之间的逻辑来表示数据元素之间的逻辑关系关系。非顺序映象的特点非顺序映象的特点借助指示元素存储地址的借助指示元素存储地址的指针指针表示数据元素之间的逻辑关系。表示数据元素之间的逻辑关系。线性表线性表逻辑结构逻辑结构（存储结构）（存储结构）物理结构物理结构 数据类型数据类型（Data Type）是一个值的是一个值的集合集合和定义在这个值集上的一组和定义在这个值集上的一组操作操作的总的总称称。抽象数据类型抽象数据类型(Abstract Data Type)是指一个数学模型以及定义在该模型上的一组操作是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型可以用以下的抽象数据类型可以用以下的三元组

8、三元组表示：表示：ADT=（D，S，P）其中，其中，D是数据对象，是数据对象，S是是D上关系集，上关系集，P是基本操作集。是基本操作集。本书的定义格式：本书的定义格式：ADTADT 抽象数据类型名抽象数据类型名 数据对象数据对象：数据对象的定义：数据对象的定义数据关系数据关系：数据关系的定义：数据关系的定义基本操作基本操作：基本操作的定义：基本操作的定义ADTADT抽象数据类型名抽象数据类型名提提 纲纲什么是数据结构什么是数据结构基本概念和术语基本概念和术语抽象数据类型的表示和实现抽象数据类型的表示和实现算法和算法分析算法和算法分析#define TRUE1#define FALSE 0#de

9、fine OK1#define ERROR 0#define INFEASIBLE-1（不可行的不可行的）#define OVERFLOW 2typedef intStatus;数据元素类型约定为：数据元素类型约定为：ElemType抽象数据类型的表示和实现抽象数据类型的表示和实现提提 纲纲什么是数据结构什么是数据结构基本概念和术语基本概念和术语抽象数据类型的表示和实现抽象数据类型的表示和实现算法和算法分析算法和算法分析算法和算法分析算法和算法分析 算法算法（Algorithm）是对特定问题是对特定问题求解步骤求解步骤的一种描述的一种描述，它是指令的它是指令的有限序列有限序列。特性特性有穷性有

10、穷性：一个算法必须总是在执行有穷步之后结束：一个算法必须总是在执行有穷步之后结束，且每一步都在且每一步都在有穷时间内完成有穷时间内完成.确定性确定性：算法中每一条指令必须有确切的含义：算法中每一条指令必须有确切的含义，不存在二义性不存在二义性，且且算法只有一个入口和一个出口算法只有一个入口和一个出口。可行性可行性：一个算法是可行的：一个算法是可行的。即算法描述的操作都是可以通过已经即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的实现的基本运算执行有限次来实现的。输入输入：一个算法有零个或多个输入：一个算法有零个或多个输入，这些输入取自于某个特定的对这些输入取自于某个特定的对象集

11、合象集合。输出输出：一个算法有一个或多个输出：一个算法有一个或多个输出，这些输出是同输入有着某些特这些输出是同输入有着某些特定关系的量定关系的量。算法设计的要求算法设计的要求(1)正确性正确性(Correctness)：算法应满足具体问题的需求：算法应满足具体问题的需求。(2)可读性可读性(Readability)：算法应该好读：算法应该好读。以有利于阅读者对以有利于阅读者对程序的理解程序的理解。(3)健壮性健壮性(Robustness)：算法应具有容错处理：算法应具有容错处理。当输入非法当输入非法数据时数据时，算法应对其作出反应算法应对其作出反应，而不是产生莫名其妙的而不是产生莫名其妙的输出

12、结果输出结果。(4)效率与存储量需求效率与存储量需求：效率指的是算法执行的时间；存储：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间量需求指算法执行过程中所需要的最大存储空间。一般一般，这两者与问题的规模有关这两者与问题的规模有关算法效率的度量算法效率的度量对一个算法要作出全面的分析可分成两个阶段进行，对一个算法要作出全面的分析可分成两个阶段进行，即事先分析和事后测试即事先分析和事后测试.事先分析事先分析：求出该算法的一个时间界限函数：求出该算法的一个时间界限函数.事后测试事后测试：收集此算法的执行时间和实际占用空间的统计：收集此算法的执行时间和实际占用空间的统计资料

13、资料。以以基本操作重复执行的次数基本操作重复执行的次数作为算法的作为算法的时间效率度量时间效率度量。基本操作重复执行的次数一般是基本操作重复执行的次数一般是问题规模问题规模n 的某个函数的某个函数f(n)：执行时间执行时间：T(n)=O(f(n)T(n)称为算法的渐近时间复杂度称为算法的渐近时间复杂度，简称简称时间复杂度时间复杂度。例：例：f(n)=n3+n2+cT(n)=O(n3)例例1：矩阵乘矩阵乘，基本操作是乘法基本操作是乘法。for(i=1，i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij=cij+aik*bkj;由于是一个三重循环由于是一个

14、三重循环，每个循环从每个循环从1到到n，则总次数为则总次数为:nnn=n3时间复杂度为时间复杂度为T(n)=O(n3)基本操作总是被基本操作总是被包含在语句中！包含在语句中！语句的频度语句的频度是指该语句重复执行的是指该语句重复执行的次数次数例例2+x;s=0;将将x自增看成是基本操作自增看成是基本操作，则语句频度为则语句频度为，即时间复即时间复杂度为杂度为(1)如果将如果将s=0也看成是基本操作也看成是基本操作，则语句频度为则语句频度为，其时其时间复杂度仍为间复杂度仍为(1)，即即常量阶常量阶。例例3for(i=1;i=n;+i)+x;s+=x;语句频度为：语句频度为：2n其时间复杂度为：其

15、时间复杂度为：O(n)即时间复杂度为即时间复杂度为线性阶线性阶。例例4.for(i=1;i=n;+I)for(j=1;j=n;+j)+x;s+=x;语句频度为：语句频度为：2n2其时间复杂度为：其时间复杂度为：O(n2)即时间复杂度为即时间复杂度为平方阶平方阶。例例5 for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;aij=x;语句频度为：语句频度为：1+2+3+n-2=(1+n-2)(n-2)/2=(n-1)(n-2)/2=n2-3n+2时间复杂度为时间复杂度为O(n2)即此算法的时间复杂度为即此算法的时间复杂度为平方阶平方阶。以下六种计算算法时间的以下六种计算算法时间

16、的多项式多项式是最常用的是最常用的，其关系为：其关系为：O(1)常量阶常量阶 O(logn)对数阶对数阶O(n)线性阶线性阶O(nlogn)O(n2)平方阶平方阶O(n3)指数时间的关系为：指数时间的关系为：O(2n)O(n!)=1&change;-i)change=false;for(j=0;jaj+1)ajaj+1;change=true;最好：最好：0次次最坏：最坏：n*(n-1)/2最坏情况下的时间复杂度：最坏情况下的时间复杂度：O（n2）(以估算算法执行时间的以估算算法执行时间的一个上界一个上界)算法的存储空间需求算法的存储空间需求空间复杂度空间复杂度:算法所需存储空间的度量，记作算法所需存储空间的度量，记作:S(n)=O(f(n)其中其中n为问题的规模为问题的规模(或大小或大小)