您好,欢迎访问三七文档
项目1数据结构基础知识问题的引入1、书目自动检索系统的数学模型登录号:书名:作者名:分类号:出版单位:出版时间:价格:书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02……………………书目文件按书名按作者名按分类号高等数学001,003……理论力学002,……..线性代数004,………………..樊映川001,…华罗庚002,….栾汝书004,….…….…….L002,…S001,003,…………索引表线性表……..……..…...…...…...…...2、人机对奕问题的数学模型ABACADBABCBDDADBDCEAEBECEDCEDAB3、十字路口的交通灯管理问题的数学模型主要考虑的是设计出合适的数据结构及相应的算法。即:首先要考虑对相关的各种信息如何表示、组织和存储?因此,简单说来,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。问题的分析1、为什么要学习数据结构?1、电子计算机的主要用途:早期:主要用于数值计算。后来:处理逐渐扩大到非数值计算领域(能处理多种复杂的具有一定结构关系的数据)。问题的提出用计算机解决问题的过程建立模型构造求解算法选择存储结构编写程序测试描述问题的共性描述问题的求解方法将问题涉及的数据存储到计算机中分析问题的过程数据结构的作用进行更为复杂的算法设计选择合理的存储结构提高编程技术2、数据结构课程的形成和发展形成阶段60年代初期,“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年,美唐•欧•克努特教授开创了数据结构的最初体系,《计算机程序设计技巧》第一卷《基本算法》,“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段:数据结构的概念不断扩充,包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期,80年代初,我国高校陆续开设该课程。3、《数据结构课程》所处的地位:介于数学、计算机硬件和计算机软件三者之间的一门核心课程。知识目标⑴数据、数据元素、数据项;⑵逻辑结构和存储结构在概念上的联系与区别;⑶数据结构及其三个组成部分;⑷抽象数据类型和数据抽象;⑸评价算法优劣的标准及方法。教学目标技能目标掌握本课程所涉及到的基本名词、术语和概念,特别是数据的逻辑结构和存储结构之间的关系及性质。了解抽象数据类型的定义、表示和实现方法。理解算法设计的五个要素和基本要求;掌握算法效率的度量方法,着重学习算法的时间复杂度分析。教学目标素质目标理解什么是数据结构,数据结构在程序设计中的重要性。了解程序开发的过程,明确数据设计的目的和意义。1.1基本概念1、数据(data)数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合,是计算机程序加工的”原料”。分类:数值性数据非数值性数据教学知识点2、数据元素(dataelement)数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成。数据项是数据不可分割的最小标识单位。数据元素又称为元素、结点、记录。学号姓名成绩001LiLy89002Yang98003Zhao783、数据对象(dataobject)数据对象是具有相同性质的数据元素的集合。整数数据对象N={0,1,2,…}字母字符数据对象C={‘A’,’B’,…,’Z’}学生成绩数据对象Cj={(‘101’,‘jane’,80),(‘102’,‘jack’,90),(‘103’,‘jerry’,75)}学号姓名成绩001LiLy89002Yang98003Zhao784、数据结构(datastructure)数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中,数据元素都不是孤立存在的,而是在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构(Structure)。数据结构是一堆数据元素和这些数据元素之间的关系的总和。按数据元素之间关系的不同特性,通常有4类基本结构(1)集合结构中的数据元素除了“同属于一个集合”外,别无其它关系。(2)线性结构结构中的数据元素之间存在一对一的关系。(3)树型结构结构中的数据元素之间存在一对多的关系。(4)图状结构或网状结构结构中的数据元素之间存在多对多的关系。线性结构数据元素之间存在着一个对一个的关系bindevetclibuseretcuser集合数据元素之间无特殊关系devlibbindevetcuser树形结构数据元素之间存在着一个对多个的关系树二叉树二叉搜索树14131211234567891031587101199·874566231311图形(网状)结构数据元素之间存在着多对多的关系。1524365、数据结构的形式定义用一个二元组表示,记为:Data_Structure=(D,S)其中,D是数据元素的有限集(即一个数据对象),S是该对象中所有数据成员之间的关系的有限集合。在计算机科学中,对复数的定义:复数是一种数据结构Complex=(C,R)其中:C是包含两个实数的集合{C1,C2},R={P},P是定义在C上的一种关系{C1,C2}。例1、用数据结构如何描述2行3列矩阵:它是一个含6个数据元素{a1,a2,a3,a4,a5,a6}的集合,且集合上存在“行关系”和“列关系”两个次序关系,其中行关系为{a1,a2,a2,a3,a4,a5,a5,a6}列关系为{a1,a4,a2,a5,a3,a6}。x,y意为x和y之间存在x领先于y的次序关系。654321aaaaaa思考:如何描述一个一行六列的矩阵?例2、假设我们需要编制一个事务管理的程序,管理学校科学研究课题小组的各项事务,则首先要为程序的操作对象——课题小组设计一个数据结构。假设每个小组由一位教师、一至三名研究生及一至六名本科生组成,小组成员之间的关系是:教师指导研究生,而由每位研究生指导一至两名本科生。则可以如下定义数据结构:Group=(P,R)其中:P={T,G1,…,Gn,S11…Snm}1=n=3,1=m=2,R={R1,R2}R1={T,Gi|1=i=n,1=n=3}R2={Gi,Sij|1=i=n,1=j=m,1=n=3,1=m=2}6、数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据,可以看作是从具体问题抽象出来的数据模型,与数据的存储无关,也与数据元素本身的形式、内容、相对位置无关;数据的逻辑结构分类:线性结构线性表、栈、队列、串非线性结构树、图(或网络)7、数据的存储结构数据结构在计算机中的表示(或称映象)称为数据的存储结构,又称为物理结构。它包括数据元素的表示和关系的表示。(1)数据元素的表示:位、字长、元素、结点、数据域(2)关系的表示两种基本的存储方法:①顺序映像(顺序存储结构)②非顺序映像(链式存储结构)顺序存储结构:借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。所有元素存放在一片连续的存贮单元中,逻辑上相邻的元素存放到计算机内仍然相邻。链式存储结构:在每一个数据元素中增加一个存放地址的指针,借助该指针来表示数据元素之间的逻辑关系。所有元素存放在可以不连续的存贮单元中,但元素之间的关系可以通过地址(指针)确定,逻辑上相邻的元素存放到计算机内存后不一定是相邻的。存储结构的描述存储结构的描述方法随编程环境的不同而不同,通常可用高级编程语言中提供的数据类型描述之。例如,用一维数组类型描述顺序存储结构,用指针描述链式存储结构。例如,定义日期为:typedefstruct{inty;//年号Yearintm;//月号Monthintd;//日号Day}DateType;//日期类型同样,此时对数据元素也要借用高级编程语言中的数据类型描述之。8、数据类型(datatype)数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分两类:原子类型和结构类型。例如:在C语言中原子类型:整型、实型、字符型等结构类型:数组、结构体、联合等9、抽象抽象数据类型(AbstractDataType简称ADT)由用户定义,用以表示应用问题的数据模型指一个数学模型以及定义在此数学模型上的一组操作。例如:计算机拥有的整数类型。它与数据类型实质上是一个概念,但其特征是使用与实现分离,实行封装和信息隐蔽(独立于计算机)。抽象数据类型的描述方法抽象数据类型可用(D,S,P)三元组表示,其中,D是数据对象,S是D上的关系集,P是对D的基本操作集。ADT抽象数据类型名{数据对象:〈数据对象的定义〉数据关系:〈数据关系的定义〉基本操作:〈基本操作的定义〉}ADT抽象数据类型名数据对象和数据关系的定义用伪码(不真正执行的符号)描述。基本操作的定义格式为:基本操作名(参数表)初始条件:〈初始条件描述〉操作结果:〈操作结果描述〉基本操作有两种参数:赋值参数只为操作提供输入值;引用参数以&打头,除了可以提供输入值外,还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息。若初始条件为空,则省略之。“操作结果”说明了操作正常完成之后,数据结构的变化状况和应返回的结果。举例——抽象数据类型复数的定义:ADTComplex{数据对象:D={e1,e2|e1,e2∈RealSet}数据关系:R1={e1,e2|e1是复数的实数部分,e2是复数的虚数部分}基本操作:InitComplex(&Z,v1,v2)操作结果:构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果:复数Z被销毁。GetReal(Z,&realPart)初始条件:复数已存在。操作结果:用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件:复数已存在。操作结果:用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件:z1,z2是复数。操作结果:用sum返回两个复数z1,z2的和值。}ADTComplex假设:z1和z2是上述定义的复数,则Add(z1,z2,z3)操作的结果将得到z3=z1+z21.2抽象数据类型的表示与实现抽象数据类型可通过固有数据类型来表示和实现,即利用处理器中已存在的数据类型来说明新的结构,用已经实现的操作来组合新的操作。一、类C语言简要说明(1)预定义常量和类型://函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE—1#defineOVERFLOW—2//Status是函数的类型,其值是函数结果状态代码typedefintStatus;(2)数据结构的表示(存储结构)用类型定义(typedef)描述。数据元素类型约定为ElemType,由用户在使用该数据类型时自行定义。(3)基本操作的算法都用以下形式的函数描述:函数类型函数名(函数参数表){//算法说明语句序列}//函数名除了函数的参数需要说明类型外,算法中使用的辅助变量可以不作变量说明,必要时对其作用给予注释。一般而言,a、b、c、d、e等用作数据元素名,i、k、1、m、n等用作整型变量名,p、q、r等用作指针变量名。当函数返回值为函数结果状态代码时,函数定义为Status类型。为了便于算法描述,除了值调用方式外,增添了C++语言的引用调用的参数传递方式。在形参表中,以&打头的参数即为引用参数。(4)赋值语句有简单赋值变量名=表达式;串联赋值变量名1=变量名2=…=变量名k=表达式;成组赋值(变量名1,…,变量名k)=(表达式1,…,表达式k);结构名=结构名;结构名=(值1,…,值k);变量名[]=表达式;变量名[起始下标
本文标题:项目1基础知识
链接地址:https://www.777doc.com/doc-1982748 .html