第2章-数据结构与算法-第1节-概述概要

第2章-数据结构与算法-第1节-概述概要第一页，共49页。学习内容与要求学习和了解数据结构所研究的内容；掌握数据的逻辑结构和存储结构的定义和基本分类；学习和掌握与数据结构有关的名词术语（如数据、数据元素、数据对象、数据类型、抽象数据类型ADT等等）；学习和了解算法的概念、特点以及算法的评价标准。2第二页，共49页。DataStructures+Algorithms=Programs——NicklausWirth程序:数据结构:

算法:利用计算机语言编制的一组具有确定功能的指令集合。处理问题的策略。问题或对象的数学模型(如何描述数据的外部表现形式和内部存储结构)。3第三页，共49页。一、数据结构研究和讨论的范畴4第四页，共49页。“学生”数据1234567895第五页，共49页。“课程”数据6第六页，共49页。“选课”数据学号课程编号成绩时间981640240028206.6.10981640240169006.6.15981650240028506.6.10981650240167606.6.15981650240248906.6.139816598164024016024002024024学生课程7第七页，共49页。学生(学号,姓名,性别,籍贯)课程(课程号,课程名,学分)选课(学号,课程号,成绩)“选课”数据包含如下信息:

学号课程编号成绩时间

学生选课系统中“学生”和“课程”这两个实体构成了网状（图状）关系（即“选课”关系）。8第八页，共49页。UNIX文件系统的系统结构图/(root)binlibuseretcmathdsswlintaoxieStack.cppQueue.cppTree.cpp9第九页，共49页。数据结构的研究内容

综合上述例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。简单地说，作为一门学科，数据结构主要研究非数值计算的程序设计问题当中计算机的操作对象（数据）以及它们之间的关系（逻辑结构和物理结构）和操作（算法实现）。10第十页，共49页。若干名词术语数据（data）数据元素（dataelement）数据项（dataitem）数据对象（dataobject）数据结构（datastructure）数据类型（datatype）抽象数据类型（ADT）11第十一页，共49页。数据（data）数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中、被计算机程序识别和处理的符号的集合。数值性数据非数值性数据12第十二页，共49页。数据元素(dataelement)和

数据项（dataitem）数据元素是数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。数据元素又可称为元素、结点、记录。有时一个数据元素可以由若干数据项（dataitem）组成。数据项是具有独立含义的最小标识单位。13第十三页，共49页。数据对象(dataobject)具有相同性质的数据成员（数据元素）的集合，数据的子集。例：整数数据对象N={0,1,2,…}学生数据对象有穷集和无穷集14第十四页，共49页。什么是数据结构定义:

由某一数据对象及该对象中所有数据成员之间的关系组成。

与“数据对象”这一概念的区别？作为术语名词和作为学科名词的区别？15第十五页，共49页。数据元素间的逻辑关系，即数据的逻辑结构。数据元素及其关系在计算机存储内的表示，即数据的存储表示（物理结构、物理表示）。数据的运算，即对数据元素施加的操作。作为学科，数据结构研究数据的组织形式，包括以下内容：16第十六页，共49页。数据的逻辑结构数据的逻辑结构从数据的逻辑关系上描述数据，与数据的存储无关，与数据元素本身的具体形式、内容无关。数据的逻辑结构可以看作是从具体问题抽象出来的数据模型。17第十七页，共49页。数据的逻辑结构可归结为以下四类：线性结构：一对一关系树形结构：一对多关系图状结构：多对多关系集合结构：简单隶属关系18第十八页，共49页。数据逻辑结构的描述方式Data_Structure={D,R}

其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。一般表现形式如下：D={d1,d2,…,dn}R={r1,r2,…,rm}关键字：数据元素中可用于标识该数据元素的某个分量（数据项）。通常用关键字区别不同的数据元素。19第十九页，共49页。D＝{01,02,03,04,05,06,07,08,09,10}R1={<08,05>,<05,02>,<02,01>,<01,03>,<03,09>,<09,04>,<04,06>,<06,10>,<10,07>}R2={<01,02>,<01,05>,<01,08>,<02,03>,<02,04>,<05,06,>,<05,07>,<08,09>,<08,10>}R3={<01,04>,<04,01>,<01,05>,<05,01>,<01,08>,<08,01>,<04,07>,<07,04>,<05,06>,<06,05>,<06,04>,<04,06>,<05,08>,<08,05>,<06,09>,<09,06>,<09,02>,<02,09>,<08,10>,<10,08>,<04,03>,<03,04>}20第二十页，共49页。R1={<08,05>,<05,02>,<02,01>,<01,03>,<03,09>,<09,04>,<04,06>,<06,10>,<10,07>}用连线表示数据元素之间的联系21第二十一页，共49页。R2={<01,02>,<01,05>,<01,08>,<02,03>,<02,04>,<05,06>,<05,07>,<08,09>,<08,10>}22第二十二页，共49页。R3={<01,04>,<04,01>,<01,05>,<05,01>,<01,08>,<08,01>,<04,07>,<07,04>,<05,06>,<06,05>,<06,04>,<04,06>,<05,08>,<08,05>,<06,09>,<09,06>,<09,02>,<02,09>,<08,10>,<10,08>,<04,03>,<03,04>}23第二十三页，共49页。由上述数据结构的描述可得出结论：相同数据元素的集合（即同一数据对象），因其关系的不同而构成不同的数据逻辑结构。对一实际应用问题，合理选择数据逻辑结构才能够设计出有效的算法。例：根据下列选课情况安排考试日程，使得在不冲突的情况下用尽可能短的时间安排所有考试。学生姓名选修课1选修课2选修课3甲ABC乙DE丙DCF丁EFA戊BF24第二十四页，共49页。数据的存储结构数据的存储结构是数据在计算机内部的存储方式，依赖于计算机语言。存储结构分类

顺序存储结构链式存储结构索引结构散列结构25第二十五页，共49页。顺序存储（矢量存储）结构Contiguousimplementation（vector

implementation）

所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存中其存储地址仍然相邻。

链式存储结构Linkedimplementation

所有元素可以存放在不连续的存储单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后其存储地址不一定是相邻的。26第二十六页，共49页。顺序和链式存储结构示意图27第二十七页，共49页。数据类型数据类型

定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称。

C语言中的数据类型charintfloatdoublevoid

字符型整型浮点型双精度型无值

基本数据类型（原子类型）：可以看作是计算机中程序设计语言已实现的数据结构。构造型数据类型：由相同或不同成分的类型构成，如数组、结构体、类等。28第二十八页，共49页。抽象数据类型

(ADTs:AbstractDataTypes)由用户定义，用以表示实际应用问题的数据模型。由基本的数据类型组成,并包括一组相关的服务（或称操作）。29第二十九页，共49页。抽象数据类型的描述方法抽象数据类型从形式上可用（D，R，O）三元组表示。其中：D是数据对象，R是D上的关系集，O是对D的基本操作集。一般采用如下格式描述ADT

抽象数据类型名

{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉}

ADT

抽象数据类型名30第三十页，共49页。ADT基本操作的定义格式基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉

参数：赋值参数只为操作提供输入值;引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空,则省略之。操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果。31第三十一页，共49页。例如，抽象数据类型“复数”的定义：数据对象：D＝{<e1,e2>｜e1,e2∈RealSet}数据关系：R1＝{<e1,e2>|e1是复数的实数部分，

e2是复数的虚数部分}ADTComplex{32第三十二页，共49页。基本操作：

AssignComplex(&Z,v1,v2)操作结果：构造一个复数Z，其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。33第三十三页，共49页。

GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex34第三十四页，共49页。抽象数据类型的实现

抽象数据类型描述的是抽象的数据模型及其操作，需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。引入抽象数据类型的意义

通常研究一个数据结构的实现问题可以从研究其抽象数据类型着手，例如通过对抽象数据类型的加工来用C++类实现该数据结构：类的数据成员对应于ADT所描述的数据结构，类的方法对应于ADT所描述的操作。35第三十五页，共49页。二、算法36第三十六页，共49页。关于算法

算法是为了解决某类问题而设计的一个有限长的操作序列。算法特性有穷性、确定性、可行性、有输入、有输出37第三十七页，共49页。有穷性：对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行；并且在任何条件下，算法都只有一条执行路径。可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。38第三十八页，共49页。有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上输入已被嵌入算法之中。有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。39第三十九页，共49页。用自然语言描述算法：用我们日常生活中的自然语言也可以描述算法。算法描述方法用流程图描述算法：一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。用其它方式描述算法：我们还可以用数学语言或约定的符号语言（如伪代码）来描述算法。用C++描述算法：在本课程中，我们将采用C++来描述算法，所有算法的描述都用C++中的函数形式。40第四十页，共49页。算法和程序的关系

算法≠程序！

算法着重体现思路和方法，程序着重体现计算机的实现。程序不一定满足有穷性（例如死循环情形）；另外，程序中的指令必须是机器可执行的，算法中的指令无此限制。算法用计算机语言来书写时才是程序。41第四十一页，共49页。算法设计原则正确性可读性健壮性高效率低需求算法评价标准

时间特性：时间复杂度T(n)

空间特性：空间复杂度S(n)算法设计原则与评价标准42第四十二页，共49页。一个特定算法的运行时间由其“运行工作量”决定。其运行工作量的大小，通常只依赖于问题的规模（通常由问题涉及的数据量决定，用整数量n表示），或者说，它是问题规模的函数。算法的运行时间

假如，随着问题规模n

的增长，算法执行时间的增长率和函数f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的时间复杂度。43第四十三页，共49页。程序执行时间的计算事后统计法事前分析估算法算法策略问题规模程序设计语言机器代码运行效率机器执行指令的速度44第四十四页，共49页。如何估算算法的时间复杂度？算法=控制结构+基本操作(基本数据类型的操作)算法的执行时间=∑基本操作的执行次数×基本操作的执行时间算法的执行时间

与

基本操作执行次数之和

成正比。从算法中选取一种对于所研究的问题来说是基本操作的操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。45第四十五页，共49页。例一两个矩阵相乘voidmult(inta[],intb[],int&c[]){

//以二维数组存储矩阵元素，c为a和b的乘积for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作时间复杂度:

O(n