资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.1,为什么学习数据结构,1.2,数据结构的有关概念和术语,1.3,算法和算法描述,1.4,算法的时空效率分析方法,1.5,小结与习题,第一章 绪论,主要介绍课程中常用术语、常用数据结构及用,C,语言实现算法描述的一般规则,算法的时间复杂度和空间复杂度分析与评价。,本章主要内容,通过本章学习,应掌握如下内容:,数据结构中的基本概念及常用术语。,线性结构、树型结构和图型结构等的逻辑特点。,算法的定义、特性。评价算法优劣的标准,:,时间复杂度、空间复杂度的定义及表示。,1.1,为什么要学习数据结构,数据结构是程序设计的中级课程,主要培养学生分析数据、组织数据的能力,告诉学生如何编写效率高、结构好的程序。,随着计算机应用领域的不断扩大,计算机处理的对象更多的是非数值计算问题,它们的数学模型无法用数学方程来进行描述,此时就必须建立相应的数据结构来进行描述,分析问题中所用到的数据是如何组织的,研究数据之间的关系如何,进而为解决这些问题设计出合适的数据结构。,【,例,1-1】,学生信息检索问题。学生信息包括学号、姓名、性别和成绩等,一行为,一个记录,,表示一个学生的信息(也称为一个,数据元素,),一列为一个,属性,。,学,号,姓,名,性,别,成,绩,20050601,张,三,男,518,20050602,李一宁,女,496,20050603,吴,磊,女,581.5,20050636,梁,磊,男,529,线性关系,:,对线性表的主要操作有查找、修改、插入和删除等。,【,例,1-2】,某大学专业设置问题。显然这种关系用“,树,”型结构来表示更形象。通常用来表示结点的分层组织,结点之间是,一对多的关系,。对树型结构主要操作有查找、修改、插入和删除等。,*大学,机械工程系,电子工程系,计算机信息系,机械制造,材料科学,电子应用,电气自动化,计算机应用与维护,计算机应用与维护,【,例,1-3】,通信网络问题。带圆圈的顶点表示城市,顶点和顶点之间的连线和数据表示城市之间的通信线路及其长度。,各顶点之间是多对多的关系,是,网,状结构,也称为,图型,结构,操作有:求从一个顶点到另一个顶点的最短路径等。,由以上三个例子可见,描述这类非数值计算问题的数学模型有,线性表、树、图,等。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。,B,C,D,F,E,A,60,45,40,42,30,40,80,65,32,26,1.2,数据结构的有关概念和术语,1.2.1,基本概念和术语,1,数据(,Data,),是描述客观事物的数值、字符以及所有能被输入到计算机并能被计算机识别、存储和处理的符号的集合。客观事物包括数值数据和非数值数据。数值数据:整数、实数或复数;非数值数据:字符、文字、图形、表格和声音等。,例如,一个个人书库管理程序所要处理的数据可能是一张如,表,1-1,所示的表格。,表,1-1,个人书库,2,数据元素(,Data Element,),是数据的基本单位。在不同的条件下,数据元素又可称为,元素、结点、顶点、记录,等。,在程序中通常把结点作为一个整体进行考虑和处理。例如,在,表,1-1,所示的个人书库中,为了便于处理,把其中的每一行(代表一本书)作为一个基本单位来考虑,故该数据由,10,个结点构成。,一般情况下,一个结点中含有若干个字段(也叫数据项)。例如,在,表,1-1,所示的表格数据中,每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。,数据项:,数据结构中讨论的最小单位。一个数据元素可由若干个数据项(,Data Item,)组成。,3,数据对象(,Data Object,),是具有,相同性质数据元素,的集合。,4,数据类型,(Data Type),在用高级语言编写的程序中,每个变量、常量或表达式都有一个它所属的确定的数据类型。,5,抽象数据类型,(,Abstract Data Type,,,简称,ADT,)是指一个数学模型及定义在该数学模型上的一组操作。抽象数据模型的定义取决于它的一组逻辑特性,与其在计算机内部如何表示和实现无关。,ADT,抽象数据类型名,数据对象:(数据对象的定义),数据关系:(数据关系的定义),基本操作:(基本操作的定义),【,例,1】,线性表的抽象数据类型可描述如下:,ADT Linear_list,数据元素,所有,a,i,属于同一数据对象,,i=1,,,2,,,,,n,(,n,1,),逻辑结构,所有数据元素,a,i,存在次序关系(,a,i,,,a,i+1,),,a,1,无前驱,,a,n,无后继。,操作,/*,设,L,为,Linear_list,类型的线性表*,/,InitList,(,L,);,/*,建立一个空的线性表,L*/,Length,(,L,);,/*,求线性表,L,的长度*,/,GetElement,(,L,,,i,);,/*,取线性表,L,中的第,i,个元素*,/,Locate,(,L,,,x,);,/*,确定元素,x,在线性表,L,中的位置*,/,Insert,(,L,,,i,,,x,);,/*,在线性表,L,中的第,i,个位置处插入数据元素,x*/,Delete,(,L,,,i,);,/*,删除表,L,中第,i,个位置的元素*,/,;,/*ADT Linear_list */,1.2.2,数据结构定义,数据结构,(,Data Structure,),是研究数据元素(,Data Element,),之间抽象化的相互关系(逻辑结构)和这种关系在计算机中的存储表示(物理结构),并对这种结构定义相适应的运算,设计出相应的算法。,数据结构主要指逻辑结构和物理结构。,(,1,)逻辑结构:,是数据元素之间的相互逻辑关系,它与数据的存储无关,是独立于计算机而存在。,通常分为,4,类基本结构:,集合,结构中的数据元素除了同属于一种类型外,别无其它关系。,线性结构,结构中的数据元素之间存在一对一的关系。,树型结构,结构中的数据元素之间存在一对多的关系。,图状结构或网状结构,结构中的数据元素之间存在多对多的关系,在,表,1-1,所示的表格中,,由,10,个结点,(,数据元素,),组成,每个数据元素又包括,6,个数据项,(,字段,),。,各结点之间在逻辑上有一种线性关系,它指出了,10,个结点在表中的排列顺序。,这张表的逻辑结构就是数据元素,(,或是结点,、记录,),之间的关系。对于表中的任一个结点,(,记录,),,都只有一个前驱结点,也只有一个后继结点,整个表只有一个开始结点和一个终端结点。,此表的逻辑结构是线性的。,四类数据基本结构的示意图:,(a),集合结构,(b),线性结构,(c),树型结构,(d),图形结构,由以上例子可见,描述这类非数值计算问题的数学模型和方法不再是数学方程,而是诸如线性表、树和图之类的数据结构。,数据结构是由两个集合构成的一个二元组:,Data_Structure(D,,,R),Data_Structure,是一种数据结构,它由同属一个数据对象的数据,元素,的有限集合,D,和,D,上二元,关系,的有限集合,R,组成。其中:,D=di|1in,n1,R=rj|1jm,m1,d,i,表示第,i,个数据元素,,r,j,表示第,j,个关系。,D,上二元关系,R,是序偶的集合。对于,R,中的任一序偶,(x,yD),,,x,称为序偶的第一元素,,y,称为序偶的第二元素,又称序偶的第一元素是第二元素的直接前驱;第二元素为第一个元素的直接后继。,【,例,】,树型结构中的圆圈代表数据元素,带箭头的连线表示元素之间的关系,试用二元组表示法表示其逻辑结构。,解:二元组为,(D,R),其中,,D=A,B,C,E,F,G,H,I,J;,R=,A,B,C,E,F,G,H,I,J,(,2,)物理结构(或存储结构),数据结构在计算机中的存储表示称为数据的存储结构。它包括数据元素的表示和关系的表示。,表,1-1,所示的表格数据在计算机中可以有多种存储表示:,数据既可以存放在一块连续的内存单元中,通过元素在存储器中的位置来表示它们之间的逻辑关系(顺序);,也可以随机分布在内存中的不同位置,通过指针元素表示数据元素之间的逻辑关系(链式)。这两种不同的表示方法对应有四种不同的存储结构(亦称方式):,顺序,存储结构、,链式,存储结构、,索引,存储结构和,散列,存储结构。,(3),数据的运算,数据运算定义在数据的逻辑结构上,即施加于数据的操作。,例如对一张表的记录进行查找、增加、删除、修改,这就是对数据的运算。,(4),数据结构三方面的关系,数据的逻辑结构、数据的存储结构及数据的运算三方面构成一个数据结构的整体。,存储结构是对数据项的存储,。,同一逻辑结构可用不同存储结构就对应不同的存储标识。,例如,线性表若采用顺序存储方式,称为,顺序表,;若采用链式存储方式,称为,链表,;若采用散列存储方式,可称为,散列表,。,数据结构作为一门学科主要研究数据的各种,逻辑结构,和,存储结构,,以及对数据的,各种操作,。同时还要考虑执行算法时的,时间和空间效率,。,1.3,算法和算法描述,有穷性,。一个算法必须在有穷步之后结束,即必须在有限时间内完成。,确定性,。算法的每一步必须有确切的定义,无二义性。,可行性,。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。,输入,。一个算法具有零个或多个输入,这些输入取自特定的数据对象集合。,输出,。一个算法具有一个或多个输出,这些输出同输入之间存在某种特定的关系。,1.3.1,算法与算法特性,算法,(,Algorithm,),是对特定问题求解步骤的一种描述,是指令的有限序列。一个算法应该具有下列特性:,一个好的算法通常要达到以下的要求:,正确,。执行结果应当满足预先规定的功能和性能要求。,可读,。应当思路清晰、层次分明、简单明了、易读易懂。,健壮,。当输入不合法数据时,应能作适当处理,不至引起严重后果。,高效,。有效使用存储空间和有较高的时间效率。,1.4,算法时空效率分析方法,评价算法的性能用时间复杂度与空间复杂度来度量。,1,、算法的时间复杂度,算法的时间复杂度(,Time complexity,),是指算法转换为程序后,(,这里仍称为算法,),在计算机上从开始运行到结束所需要的时间。运行所需要的时间取决于下列因素:,硬件的速度。,与硬件的配置高低有关。,书写程序的语言。,语言的级别越高,其执行效率就越低。,编译程序所生成目标代码的质量,。,依据,算法所选用的策略,。,问题的规模,。一般情况下,处理的数据量越大,执行的时间相对也越长。,通常的做法是:不考虑不确定的情况,而以算法中简单操作重复执行的次数作为算法的时间度量。为此,一个特定算法的运行时间长短就只依赖于,问题的规模,n,,,或者说它是问题规模,n,的函数,f(n),。,【,例,1-7】,求累加求和,int,sum(int,b,,,int,n,),int,sum=0;/*,第,1,条定义并赋初值语句执行,1,次*,/,for,(,int,i=0,;,in,;,i+,),/*3n+2,次*,/,sum+=bi;/*n,次 *,/,return sum;,/*,返回语句执行,1,次 *,/,要精确地计算,f(n),是困难的,引入渐进时间复杂度在数量上估计一个算法的执行时间。算法时间的度量记作,T(n)=(f(n),它表示随问题的规模,n,的增大,算法执行时间的增长率和,f(n),相同。使用大,记号,,(f(n),称为算法的渐进时间复杂度(,Asymptotic Time Complexity,),,简称时间复杂度。,例如,一个程序的实际执行时间为,T(n),2.7,n,3,+3.8n,2,+5.3,。则,T(n),(n,3,),。,【,例,1-8】,求下面程序段的时间复杂度。,s=0;,for(j=1;j=n;j+),for(x=1,k=1;k=n;k+),x=x*k;,s+=x;,解:该算法中“,s=0;”,的频度为,1,,后面由两个“,for”,语句构成了一个二重循环结构,其内循环体执行的频度为,n,2,,,用最高数量级,n,2,的表示,则该程序段的时间复杂度为,O(n,2,),。,通常将称,(1),为,常数阶,,,(n),为,线性阶,,,O(n,2,),为,平方阶,。算法还可能呈现的复杂度有:对数阶,(log,2,n),,,指数阶,(2,n,),等,不同数量级时间复杂度的关系有:,(1),(log,2,n),(n),(nlog,2,n),(n,2,),(n,3,),(2,n,),0 1 2 4 8 16 32 64 128 256 n,T(n),1024,512,256,128,64,32,16,8,4,2,1,0 1 2 4 8 16 32 64 128 256 512 1024 n,n,log,2,n,2,n,n,2,n,3,nlog,2,n,图,1-7,常见函数的增长率,2,、算法的空间复杂度,一个程序的空间复杂度(,Space complexity,),是指程序运行从开始到结束所需的最大存储空间。,包括以下三部分:,(,1,)输入数据所占空间;,(,2,)程序本身所占空间;,(,3,),辅助变量所占空间,。,只需要分析辅助变量所占空间即可。通常以算法的空间复杂度作为算法所占用存储空间的量度。定义:,S(n)=O(g(n),小 结,术语:,数据(,Data,),、,数据元素(,Data Element,)、,数据项、,数据对象、数据类型等,线性结构、树型结构和图型结构等的逻辑特点。算法的定义、特性及用类,C,语言描述算法的规则。评价算法优劣的标准,:,时间复杂度、空间复杂度的定义及表示。,本书选用,C,语言作为描述算法的工具。现简单说明,C,语言,的语法结构如下:,1,预定义常量和类型:,#define TRUE 1,;,#define FALSE -1,;,#define ERROR NULL,;,2,函数的形式,数据类型,函数名 (,形式参数,),形式参数说明;,内部数据说明;,执行语句组;,/*,函数名*,/,函数的定义主要由函数名和函数体组成,函数体用花括号“,”,和“,”,括起来。函数中用方括号括起来的部分为可选项,函数名之间的圆括号不可省略。函数的结果可由指针或别的方式传递到函数之外。执行语句可由各种类型的语句所组成,两个语句之间用“;”号分隔。可将函数中的表达式的值通过,return,语句返回给调用它的函数。最后的花括号“,”,之后的,/*,函数名*,/,为注释部分,,可舍。,3,赋值语句,简单赋值:,变量名,=,表达式,,它表示将表达式的值赋给左边的变量;,变量,+,,它表示变量加,1,后赋值给变量;,变量,-,,它表示变量减,1,后赋值给变量;,4,条件选择语句,if,(,表达式,)语句;,if,(,表达式,)语句,1,;,else,语句,2,;情况语句,switch,(,表达式,),case,判断值,1,;语句组,1,;,break,;,case,判断值,2,;语句组,2,;,break,;,case,判断值,n,;,语句,组,n,;,break,;,default,:,语句组;,break,;,注意:,switch case,语句是先计算表达式的值,然后用其值与判断值相比较,若它们相一致时,就执行相应的,case,下的语句组;若不一致,则执行,default,下的语句组;其中的方括号代表可选项。,5,循环语句,for,语句,for,(,表达式,1,;,表达式,2,;,表达式,3,),循环体语句;,首先计算表达式,1,的值,然后求表达式,2,的值,若结果非零则执行循环体语句,最后对表达式,3,运算,如此循环,直到表达式,2,的值为零时止。,while,语句,while,(,条件表达式,),循环体语句;,while,循环首先计算条件表达式的值,若条件表达式的值非零,则执行循环体语句,然后再次计算条件表达式,重复执行,直到条件表达式的值为假时退出循环,执行该循环之后的语句。,do-while,语句,do,循环体语句,while,(,条件表达式,),该循环语句首先执行循环体语句。然后再计算条件表达式的值,若条件表达式成立,则再次执行循环体,再计算条件表达式的值,直到条件表达式的值为零,即条件不成立时结束循环,。,6,输入、输出语句,输入语句:用函数,scanf,实现,特别当数据为字符时,,用,getchar,函数实现。,输出语句:用,printf,函数实现,当要输出字符数据时,用,putchar,函数实现。,7,其他一些语句,(,1,),return,表达式或,return,:,用于函数结束。,(,2,),break,语句:可用在循环语句或,case,语句中结束循环过程或跳出情况语句。,(,3,),exit,语句:表示出现异常情况时,控制退出语句。,8,注释形式,可用,/*,字符串*,/,或者 单行注释 或,/,文字序列。,9,一些基本的函数,如:,max,函数,用于求一个或几个表达式中的最大值;,min,函数,用于求一个或几个表达式中的最小值;,abs,函数,用于求表达式的绝对值;,实训,上机编程求出,1000,内的所有素数。,
展开阅读全文