数据结构-第一章 第一次课.ppt

数据结构,主讲：何彩霞,考核方式期末期末：50%平时成绩：50%TELmail:449060750,第一章绪论,学习数据结构的意义及要数据结构的主要内容基本术语算法描述及分析,1.1学习数据结构的意义及要求,意义1.算法与数据结构是计算机科学的两大支柱计算机科学的早期定义为：研究算法的科学近期定义为：研究数据的科学2数据结构是程序设计的基础程序=算法+数据结构,1.1学习数据结构的意义及要求,3数据结构是计算机专业的一门综合性专业课程是计算机专业本科生必修的学位课程是计算机研究生入学考试必考科目,1.1学习的要求,1.掌握各类基本数据结构类型和相应的存储结构2.提高阅读和编写算法的能力3.能针对给定问题，选择相适应的数据结构，并能设计和分析算法,1.2的主要内容,2108006011班号83202670计算机学院办公室电话号码610054电子科技大学邮份证号码,例1：210800601183202670610054510102197806187482,结论1.杂乱的数据不能表达和交流信息,1.2的主要内容,例2:电话号码簿(a1，b1)(a2，b2)(an，bn)其中：ai为某人姓名，bi为该人的电话号码。要求：设计一个算法，给定一个姓名时，能查出此人的电话号码。,如果姓名和电话号码的排列次序无规律，则只能逐一比较姓名进行查找如果姓名按字典顺序组织，则查找就快捷多了,结论2.数据之间是有联系的这些联系常常影响算法的选择和效率。DS就是要研究数据之间的联系。,1.2的主要内容,例3：大学学生管理机构学校一系八系一年级二年级三年级四年级班班张三李四,结论数据之间是有结构的例中数据之间呈分层结构（树状结构）DS就是要研究数据之间的各类结构。,例4：交通网络图从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。,1.2的主要内容,例5：图书目录管理设每个书目含：书名，作者，登录号，分类号，出版年月，对图书目录常有如下操作：查找：某书在书库中是否存在？插入：购进新书时的登录；删除：报废或丢失的书，需从目录中去掉；,结论在某种数据结构上可定义一组运算DS就是要研究各类数据结构上的各种运算。,1.2的主要内容,综上所述：DS主要研究内容：计算机的操作对象数据；数据的各种逻辑结构和物理结构，以及它们之间的相应关系；并对每种结构定义相适应的各种运算；设计出相应的算法；分析算法的效率。,常见的数据结构有：数组、栈、队列、表、串、树、图和文件等。,1.基本术语,数据（Data)：所有能被计算机处理的符号的集合。数据元素（DataElement）：是数据这个集合中的一个个体。设给定数据集合为：D=d1，d2，dn则di属于D，并称di为数据元素。数据项（DataItem）：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。,1.基本术语,数据对象（DataObject）:具有相同特性的数据元素的集合。例如：数据集合D=0，1，A，B，Z则：数据对象正整数N0，1，数据对象字母CA，B，Z数据元素是数据的一个个体，数据对象是数据的一个子集。,数据结构(DataStructure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所示。集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。线性结构：结构中的数据元素之间存在一对一的关系。树型结构：结构中的数据元素之间存在一对多的关系。图状结构：结构中的数据元素之间存在多对多的关系。,1.基本术语,数据结构（DataStructure）：是带有结构的数据元素的集合。所谓结构就是数据元素之间的关系，可有一种或多种特定的关系。用集合的形式描述，数据结构是一个二元组：DS=(D，R)其中：D是数据元素的有限集，R是D上关系的有限集。简言之，数据元素和其相互关系称为数据结构,1.基本术语,例1：复数的表示Complex=（C，R）C=c1，c2|c1，c2是实数R=PP=|c1,c2C,1.基本术语,例2：课题小组的描述Group=（P，R）P=T,G1,Gn,S11,Snm|1n3,1m2R=R1,R2R1=|1in,1n3R2=|1in,1jm,1n3,1m2,1.基本术语,逻辑结构（LogicalStructure）：指数据元素之间的结构关系。物理结构（PhysicalStructure）：指数据结构在机内的表示。也称存储结构，通常有顺序存储结构和链式存储结构。一点说明：算法的设计取决于逻辑结构；算法的实现依赖于存储结构。,1.基本术语,数据类型（DataType）：一个值的集合和定义在这个值集上的操作的总称。基本操作的分类：引用型查找；加工型插入、删除、更新、排序。,1.算法描述和算法分析,一算法（Algorithm）算法概念：算法是对特定问题求解步骤的一种描述，是指令的有限序列。,算法五个基本特性：有穷性：算法经有限步后结束；确定性：每一步必须有明确的含义；可行性：每一步是可执行的。,输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。,1.算法描述和算法分析,算法与程序的区别算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。程序是用某种程序设计语言对算法的具体实现。,主要区别在：有穷性和描述方法程序可以是无穷的，例如OS，算法是有穷的；程序是用程序设计语言描述，在机器上可以执行；算法还可以用框图、自然语言等方式描述。,1.算法描述和算法分析,二算法描述语言类Pascal为了便于理解掌握算法的思想和实质，本课程采用类Pascal语言来描述各种算法。所有的算法均以过程或函数的形式表示；PROC过程名(参数表);算法说明语句组ENDP;过程名,1.算法描述和算法分析,FUNC函数名(参数表)：类型;函数说明语句组RETURN(f)ENDF;函数名可有若干值参或变参；参数必须说明类型，局部变量可省缺说明；过程或函数均允许嵌套或递归调用,1.算法描述和算法分析,布尔运算：AND、OR、NOT、CAND、CORCAND和COR称为DelayComputation，其含义ACANDB：ifAthenBelsefalseACORB：ifAthentrueelseB,1.算法描述和算法分析,例1:用过程实现求n!PROCfac1(n:integer;VARf:integer);ifn0thenERROR;f:=1;fori:=1TOnDOf:=f*iENDP;,1.算法描述和算法分析,例2:用函数实现求n!FUNCfac2(n:integer):integer;ifn0thenERROR;f:=1;fori:=1TOnDOf:=f*i;RETURN(f)ENDF;,1.算法描述和算法分析,例3:用递归函数实现求n!FUNCfac3(n:integer):integer;ifn0thenERROR;ifn=0thenRETURN(1);RETURN(n*fac3(n-1)ENDF;,1.算法描述和算法分析,例4:将x、y、z中的整数值由大到小排列PROCsort(VARx,y,z:integer);ifxythent:=x;x:=y;y:=t;ifyaj+1THENajaj+1;change:=true;i:=i+1UNTIL(i=n)OR(NOTchange)ENDP;,1.算法描述和算法分析,对上述算法,用下述序列执行1,3,5,7,99,7,5,3,13,