数据结构-第1章绪论剖析.ppt

教学目的与要求教学目的与要求教学目的与要求教学目的与要求了解数据结构研究的对象、数据结构的发展及地位，掌握实际问题抽象成数学模型的概念掌握基本概念及基本术语掌握算法描述的语言及算法分析的方法。重点与难点重点与难点重点与难点重点与难点重点：概念、算法分析的方法。难点：算法分析的方法。教学内容教学内容教学内容教学内容1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4算法和算法分析 第一章 绪 论 第一章 绪 论计算机应用主要涉及到两个问题：（1）信息的表示（2）信息的处理 信息的表示直接关系到处理信息的程序的效率信息的表示直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所对象之间存在的关系，这就是数据结构这门课所要研究的问题。要研究的问题。计算机的程序是对信息进行加工处理。信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。例例1、电话号码查询系统、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)，(a2，b2)，(an，bn)其中ai，bi(i=1，2n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。1.1什么是数据结构算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1in 数据结构还要提供每种结构类型所定义的各种运算的算法。1.1什么是数据结构例2、图书馆的书目检索系统自动化问题例3、人机博弈问问题例4、多叉路口交通灯的管理问题 通过以上几例可以直接地认为：数据结构就数据结构就是研究数据的是研究数据的逻辑结构和物理结构逻辑结构和物理结构以及以及它们它们之间相互关系之间相互关系，并对这种结构定义相应的，并对这种结构定义相应的运运算算，而且确保经过这些运算后所得到的新结，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。构仍然是原来的结构类型。1.1什么是数据结构数据结构的发展1.“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。2.1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧计算机程序设计技巧计算机程序设计技巧计算机程序设计技巧第一卷基本算法基本算法基本算法基本算法是第一本较系统地阐述数据的逻数据的逻数据的逻数据的逻辑结构和存储结构及其操作的著作辑结构和存储结构及其操作的著作辑结构和存储结构及其操作的著作辑结构和存储结构及其操作的著作。3.20世纪70年代中期到80年代，各种版本的数据结构著作相继出现。4.目前在我国，数据结构已经是计算机专业的核心课程之一。介于：计算机硬件，计算机软件、数学三者之间介于：计算机硬件，计算机软件、数学三者之间介于：计算机硬件，计算机软件、数学三者之间介于：计算机硬件，计算机软件、数学三者之间数据数据数据数据(Data):(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素数据元素数据元素数据元素(Data Element):(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象数据对象数据对象数据对象(Data Object)(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。数据结构数据结构数据结构数据结构(Data Structure)(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。1.2 基本概念和术语 数据结构主要指逻辑结构和物理结构逻辑结构和物理结构逻辑结构和物理结构逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、一、一、一、集合集合集合集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、二、二、二、线性结构线性结构线性结构线性结构 结构中的数据元素之间存在一对一的关系。三、三、三、三、树型结构树型结构树型结构树型结构 结构中的数据元素之间存在一对多的关系。四、四、四、四、图状结构或网状结构图状结构或网状结构图状结构或网状结构图状结构或网状结构 结构中的数据元素之间存在多对多的关系。1.2 基本概念和术语数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例例1.4 复数的数据结构定义如下复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P定义在集合上的一种关系C1，C2。C1实部，C2虚部。例例例例1.5 1.5 课题小组的数据结构定义课题小组的数据结构定义课题小组的数据结构定义课题小组的数据结构定义（思考）（思考）（思考）（思考）1.2 基本概念和术语数据结构在计算机中的表示称为数据的物理结构物理结构物理结构物理结构，又称为存储结构存储结构存储结构存储结构。Bit Bit：信息表示的最小单位元素或结点：元素或结点：元素或结点：元素或结点：表示数据元素的位串数据域：数据域：数据域：数据域：数据项对应的位串1.2 基本概念和术语域域域结点：数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存地址的指针（），用此指针来表示数据素之间的逻辑关系。顺序存储和链式存储参见顺序存储和链式存储参见顺序存储和链式存储参见顺序存储和链式存储参见P6 P6 图图图图1.61.61.2 基本概念和术语 可借用高级语言的数据类型来描述存贮结构。数据类型：一组值的集合及定义的相应操作的总称。（1）原子类型 （2）结构类型 注：数据结构不同于数据类型，也不同于数数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系而且要描述数据对象各元素之间的相互关系。1.2 基本概念和术语数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C语言中数据类型：基本类型和构造类型；基本类型：整型、浮点型、字符型；构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是-3，-2，-1，0，1，2，3，英文字符类型的数据对象是A，B，C，D，E，F，1.2 基本概念和术语抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。抽象数据类型软件模块通常包括：定义，表示和实现定义，表示和实现定义，表示和实现定义，表示和实现。根据其值的特性分为：原子类型：原子类型：原子类型的变量的值不可分解。固定聚合类型固定聚合类型：确定数目成分的某种结构。可变聚合类型可变聚合类型：值的成分的数据不确定。例：有序整数序列。抽象数据类型可用三元组描述如下：（，）参见参见参见参见 P9 P9 例例例例1-61-61.2 基本概念和术语抽象数据类型通常是指由用户定义，用以表示应用问题的数据类型，抽象数据类型由基本的数据类型组成，并包括一组相关的服务（或称操作）。抽象数据类型有些类似于pascal语言中的记录(record)类型和c语言中的构造(struct)类型，但它增加了相关的服务。1.3 抽象数据类型的表示和实现在计算机中使用二进制定点数和浮点数实现数据的存储和运算，而在汇编中给出数据的自然表示，到了高级语言，给出了更高一级的数据抽象，出现了整形、实型、字符型、双精度行。待到抽象数据类型出现时，可以进一步定义出更高级的数据抽象。如各种表、队列、图、甚至窗口、管理器等。抽象数据类型的特征是使用和实现分离，实行封装和信息隐蔽。1.2 基本概念和术语算法算法：是对特定问题求解步骤的一种描述 算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。1.4 算法和算法分析4）输入）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。5）输出）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1.4.2 算法设计的要求算法设计的要求评价一个好的算法有以下几个标准:(1)正确性正确性(Correctness)算法应满足具体问题的需求。(2)可读性可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。(3)健状性健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。1.4 算法和算法分析(4)效率与存储量需求效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.4.3 算法效率的度量算法效率的度量 对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和事后测试事先分析和事后测试事先分析事先分析 求出该算法的一个时间界限函数事后测试事后测试 收集此算法的执行时间和实际占用空间的统计资料。定义：如果存在两个正常数c和n0，对于所有的nn0，有f(n)cg(n)则记作 f(n)=O(g(n)1.4 算法和算法分析一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)称作算法的渐近时间复杂度。例例例例 ：for(I=1；I=n;+I)for(j=1;j=n;+j)cIj=0;for(k=1;k=n;+k)cIj+=aIk*bkj;1.4 算法和算法分析由于是一个三重循环，每个循环从1到n，则总次数为:nnn=n3时间复杂度为T(n)=O(n3)频度：是指该语句重复执行的次数频度：是指该语句重复执行的次数频度：是指该语句重复执行的次数频度：是指该语句重复执行的次数例例：+x;s=0;若将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。例：例：for(I=1;I=n;+I)+x;s+=x;语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。1.4 算法和算法分析例：例：for(I=1;I=n;+I)for(j=1;j=n;+j)+x;s+=x;语句频度为：2n2其时间复杂度为：O(n2)即时间复杂度为平方阶。定理：定理：定理：定理：若A(n)=a m n m+a m-1 n m-1+a1n+a0是一个m次多项式，则A(n)=O(n m)证略。例例例例 for(i=2;i=n;+I)for(j=2;j=i-1;+j)+x;ai，j=x;1.4 算法和算法分析语句频度为：1+2+3+n-2=(1+n-2)(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 时间复杂度为O(n2)即此算法的时间复杂度为平方阶.一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。1.4 算法和算法分析以下六种计算算法时间的多项式是最常用的。其关系为：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)aj aj+1;change=TURE 最好情况：0次 1.4 算法和算法分析最坏情况：1+2+3+n-1 =n(n-1)/2 平均时间复杂度为:O(n2)1.4.4 算法的存储空间需求算法的存储空间需求空间复杂度空间复杂度空间复杂度空间复杂度:算法所需存储空间的度量算法所需存储空间的度量，记作:S(n)=O(f(n)其中n为问题的规模(或大小）)程序所用的存储空间包括两个部分：固定部分 可变部分 1.4 算法和算法分析1、固定部分：这部分空间的大小与输入输出的个数多少、数值大小无关。主要包括存放程序指令代码的空间，常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员等）变量所占的空间等。这部分属于静态空间，只要作简单的统计就可估算。2、可变部分：这部分空间主要包括其尺寸与实例特征有关的成分变量所占空间、引用变量所占空间、以及递归栈所用的空间，还有算法运行时动态命令使用的空间。1.4 算法和算法分析