数 据 结 构信息与计算科学专业一、任课教师简介姓名：郭荣伟联系电话：13173006561二、课程要求1、本课程总评成绩的计算算法：总成绩=平时成绩*30%+期末成绩*70%；平时成绩（100分）=出勤（30）+作业（40） +随堂上机（30）；2、出勤的统计方法是随机抽查和全查，无故缺勤一次扣10分，累计三次无考试资格；请假必须提前通知任课老师，并具有班主任或者辅导员签字的假条，视具体情况扣分，原则上不会超过5分，补假无效。三、本课程简介数据结构是信息与计算专业的一门专业基础课，其目的是要学习和逐步掌握各种数据结构和算法，培养设计算法和开发程序的能力，达到能够根据实际问题的需要，选择适当的数据结构及设计出相应的算法，并通过上机实验，编写出程序。本课程的主要任务是进一步锻炼学生的动手能力，提高学生分析和解决实际问题的能力。 本课程的主要内容有各种线性表的介绍，如栈和队列，串；树的介绍和应用，图的介绍和应用，各种查找和排序算法以及相应的算法设计和分析。本课程达到的要求是掌握各种数据结构的逻辑机构和物理结构，以及相应的各种算法。达到对给定一个具体的问题，能设计出合适的数据结构，选择恰当的算法，并且编写出具体的实现程序，同时还能书写出规范的程序说明书。第第1 1章章 绪论绪论本章主题：数据结构的基本概念和术语本章主题：数据结构的基本概念和术语本章主题：数据结构的基本概念和术语本章主题：数据结构的基本概念和术语教学目的：了解数据结构的基本概念，理解常用术语教学目的：了解数据结构的基本概念，理解常用术语教学目的：了解数据结构的基本概念，理解常用术语教学目的：了解数据结构的基本概念，理解常用术语教学重点：熟悉数据结构常用术语，掌握基本概念，了解算教学重点：熟悉数据结构常用术语，掌握基本概念，了解算教学重点：熟悉数据结构常用术语，掌握基本概念，了解算教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分析与评价法时间复杂度和空间复杂度的分析与评价法时间复杂度和空间复杂度的分析与评价法时间复杂度和空间复杂度的分析与评价 教学难点：数据元素间的教学难点：数据元素间的教学难点：数据元素间的教学难点：数据元素间的 4 4 种结构关系。种结构关系。种结构关系。种结构关系。主要内容：主要内容：主要内容：主要内容： 1.1 1.1 什么是数据结构什么是数据结构什么是数据结构什么是数据结构 1.21.2 算法描述算法描述算法描述算法描述 1.3 1.3 算法分析与评价算法分析与评价算法分析与评价算法分析与评价 计算机是一门研究用计算机进行信息表示和计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：处理的科学。这里面涉及到两个问题： 1. 信息的表示信息的表示,2.信息的处理信息的处理 而信息的表示又直接关系到处理信息的程而信息的表示又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个因此，为了编写出一个“好好”的程序，必须的程序，必须分析待处理的对象的特征及各对象之间存在分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的的关系，这就是数据结构这门课所要研究的问题。问题。l 1.1什么是数据结构什么是数据结构l 众所周知，计算机的程序是对信息进行加工处理。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几结构的内容。那么，什么是数据结构呢？先看以下几个例子。个例子。l 例例1、电话号码查询系统、电话号码查询系统l 设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N个人的名字和其个人的名字和其相应的电话号码，假定按如下形式安排：相应的电话号码，假定按如下形式安排：l (a1，b1)(a2，b2)(an，bn)l其中其中ai，bi(i=1，2n) 分别表示某人的名字和对应的分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。这个人的标志。l 算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。l 数据的结构，直接影响算法的选择和效率。l 上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。 假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)， 1in 数据结构还要提供每种结构类型所定义的各种运算的算法。例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题 见课本 通过以上几例可以直接地认为：数据结构数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。l 1.2 基本概念和术语l数据数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。l数据元素数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。l 一个数据元素可由若干个数据项组成。数数据项据项是数据的不可分割的最小单位。l数据对象数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。l数据结构数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。l数据类型数据类型：在一种程序设计语言中，变量所具有的数据种类。l例、在C语言中l数据类型：基本类型和构造类型l基本类型：整型、浮点型、字符型l构造类型：数组、结构、联合、指针、枚举型、自定义l数据结构主要指逻辑结构和物理结构l 数据之间的相互关系称为逻辑结构。通常分为四类基本结构：l一、集合集合 结构中的数据元素除了同属于一种类型外，别无其它关系。l二、线性结构线性结构 结构中的数据元素之间存在一对一的关系。l三、树型结构树型结构 结构中的数据元素之间存在一对多的关系。l四、图状结构或网状结构图状结构或网状结构 结构中的数据元素之间存在多对多的关系。l 四四类数据基本结构的示意图：(a)(a)(a)(a)集合结构集合结构 (b)(b)(b)(b)线性结构线性结构线性结构线性结构 (c)(c)(c)(c)树型结构树型结构树型结构树型结构 (d)(d)(d)(d)图形结构图形结构图形结构图形结构l数据结构的形式定义为：数据结构是一个二元组：l Data-Structure=(D，S)l其中：D是数据元素的有限集，S是D上关系的有限集。例 复数的数据结构定义如下： Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2。数据结构在计算机中的表示称为数据的物理结物理结构构，又称为存储结构存储结构。l数据结构在计算机中有两种不同的表示方法：l 顺序表示和非顺序表示l由此得出两种不同的存储结构：顺序存储结顺序存储结构和链式存储结构构和链式存储结构l顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。l链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。注：任何一个算法的设计取决于选定的数据（逻注：任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构辑）结构，而算法的实现依赖于采用的存储结构 抽象数据类型抽象数据类型（Abstruct Data Type，简称ADT） ADT是指一个数学模型以及定义在该模型上的一组的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。l 抽象数据类型和数据类型实质上是一个概念。例如，各个计算机都有的“整数”类型是一个抽象数据类型，尽管他们在不同处理器上实现的方法不同，但由于其定义的数学特性相同，在用户看来都是相同的，因此“抽象”的意义在于数据类型的数学抽象性。l用三元组描述如下：l（，）l其中是数据对象，是上的关系集，是对的基本操作。l详细内容见课本8l算法和算法分析算法和算法分析l算法算法：是对特定问题求解步骤的一种描述l 算法是指令的有限序列，其中每一条指令表示一个或多个操作。l 算法具有以下五个特性：l（1）有穷性有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。l（2）确定性确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。l（3）可行性可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。l4）输入输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。l5）输出输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。l算法设计的要求算法设计的要求l评价一个好的算法有以下几个标准:l(1) 正确性正确性(Correctness ) 算法应满足具体问题的需求。l(2)可读性可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。 (3)健状性健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。l(4)效率与存储量需求效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。l1.4.3 算法效率的度量算法效率的度量l 对一个算法要作出全面的分析可分成两用人才个阶段进行，即事前分析事前分析和事后统计事后统计l事前分析事前分析 求出该算法的一个时间界限函数l事后统计事后统计 收集此算法的执行时间和实际占用空间的统计资料。l注：事后统计有两个缺陷，人们常常采用事前注：事后统计有两个缺陷，人们常常采用事前分析估算的方法。分析估算的方法。一般情况下，算法中基本操作重复执行的次数是问题规模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; l由于是一个三重循环，每个循环从1到n，则总次数为: nnn=n3l时间复杂度为T(n)=O(n3)l频度频度：是指该语句重复执行的次数l例 +x;s=0;l将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)l例、for(i=1;i=n;+i)l +x;s+=x;l 语句频度为：n其时间复杂度为：O(n)l 即时间复杂度为线性阶。l例、for(i=1;i=n;+i)lfor(j=1;j=n;+j)l +x;s+=x;l 语句频度为：n2l其时间复杂度为：O(n2)l 即时间复杂度为平方阶。l定理定理：若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;aij=x;l语句频度为：l 1+2+3+n-2=(1+n-2) (n-2)/2l =(n-1)(n-2)/2l =n2-3n+2l 时间复杂度为O(n2)l 即此算法的时间复杂度为平方阶.l 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。l l以下六种计算算法时间的多项式是最常用的。其关系为：l O(1)O(logn)O(n)O(nlogn)l O(n2)O(n3)l指数时间的关系为：l O(2n)O(n!)1 & change;-I)l l change=false;l for(j=0;jaj+1) l aj aj+1;l change=TUREl l l l最好情况：0次l最坏情况：1+2+3+n-1l =n(n-1)/2l平均时间复杂度为:O(n2)l注：除特别指明外，均指最坏情况下的注：除特别指明外，均指最坏情况下的时间复杂度时间复杂度 2 2空间复杂度空间复杂度（Space complexitySpace complexity） 一一个个算算法法的的空空间间复复杂杂度度是是指指算算法法运运行行从从开开始始到到结结束束所所需的存储量。需的存储量。 算算算算法法法法的的的的存存存存储储量量量量指指指指的的的的是是是是算算算算法法法法执执行行行行过过程程程程中中中中所所所所需需需需的的的的最最最最大大大大存存存存储储空空空空间间。 算法算法执执行期行期间间所需要的存所需要的存储储量量应该应该包括以下三部分：包括以下三部分： (1) (1) 输输入数据所占空入数据所占空间间； (2) (2) 程序本身所占空间；程序本身所占空间； (3) (3) 辅辅助助变变量所占空量所占空间间。 类类似似于于算算法法的的时时间间复复杂杂度度，通通常常以以算算法法的的空空间间复复杂杂度度作作为为算法所需存算法所需存储储空空间间的量度。定的量度。定义义：S(n)=O(g(n)S(n)=O(g(n)称称S(n)S(n)为为算法的空算法的空间间复复杂杂度。度。 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间，否则应同时考虑输入本身所需空间（和输入数据的表示形式有关）原地工作：原地工作：若额外空间相对于输入数据量来说是个常数，练习题练习题一、选择题一、选择题1. 算法的计算量的大小称为计算的（ ）。A效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（ ）A问题的规模 B. 待处理数据的初态 C. A和B D. 以上都不对3.计算机算法指的是（ ），它必须具备（ ） 这三个特性。(1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4从逻辑上可以把数据结构分为（ ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构 CB.CCB5在下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 6程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF AjAj+1 THEN Aj与Aj+1对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ）A. O（n） B. O(nlogn) C. O(n3) D. O(n2) CD二、判断题二、判断题1. 数据元素是数据的最小单位。( )，2. 记录是数据处理的最小单位。 ( ) ，3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( )， 4算法的优劣与算法描述语言无关，但与所用计算机有关。( )5健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )6算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( ) 7程序一定是算法。( )8数据的物理结构是指数据在计算机内的实际存储形式。( ) 9. 数据结构的抽象操作的定义与具体实现有关。( ) 10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( )答案: 正确的是:5, 8, 12.三、填空三、填空1数据的物理结构包括 的表示和 的表示。2. 对于给定的n个元素,可以构造出的逻辑结构有 ， ， ，_ _ 四种。3数据的逻辑结构是指 。4一个数据结构在计算机中 称为存储结构。5抽象数据类型的定义仅取决于它的一组_ _，而与_ _无关，即不论其内部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。6数据结构中评价算法的两个重要指标是 7. 数据结构是研究数据的_ _和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_（3）_，设计出相应的（4）_。集合线性结构树形结构图状结构或网状结构1数据元素 数据元素间关系 2集合 线性结构 树形结构 图状结构或网状结构。3数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。4表示（又称映像）。5（1）逻辑特性 （2）在计算机内部如何表示和实现 （3）数学特性。6算法的时间复杂度和空间复杂度。7（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法8已知如下程序段FOR i:= n DOWNTO 1 DO 语句1BEGIN x:=x+1； 语句2FOR j:=n DOWNTO i DO 语句3 y:=y+1; 语句4END；语句1执行的频度为 （1） ；语句2执行的频度为 （2） ；语句3执行的频度为 （3） ；语句4执行的频度为 （4） 。10在下面的程序段中，对的赋值语句的频度为_（表示为n的函数） FORi： TO nDOFORj：TO iDOFORk：1TOjDO：delta；8 （1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2。101+（1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 O(n3)11. 下面程序段的时间复杂度为_。(n1) sum=1； for (i=0;sumn;i+) sum+=1; 12. 在有n个选手参加的单循环赛中，总共将进行_场比赛。11. O(n) 12. n(n-1)/2