数据结构与算法第1节概述.ppt

第2章数据结构与算法,一、数据结构讨论与研究的范畴二、算法,第1节概述,第2页,学习内容与要求,学习和了解数据结构所研究的内容；掌握数据的逻辑结构和存储结构的定义和基本分类；学习和掌握与数据结构有关的名词术语（如数据、数据元素、数据对象、数据类型、抽象数据类型ADT等等）；学习和了解算法的概念、特点以及算法的评价标准。,第3页,DataStructures+Algorithms=ProgramsNicklausWirth,程序:数据结构:算法:,利用计算机语言编制的一组具有确定功能的指令集合。,处理问题的策略。,问题或对象的数学模型(如何描述数据的外部表现形式和内部存储结构)。,第4页,一、数据结构研究和讨论的范畴,第5页,“学生”数据,123456789,第6页,“课程”数据,第7页,“选课”数据,学生,课程,第8页,学生(学号,姓名,性别,籍贯),课程(课程号,课程名,学分),选课(学号,课程号,成绩),“选课”数据包含如下信息:学号课程编号成绩时间学生选课系统中“学生”和“课程”这两个实体构成了网状（图状）关系（即“选课”关系）。,第9页,UNIX文件系统的系统结构图,/(root),bin,lib,user,etc,math,ds,sw,lin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,第10页,数据结构的研究内容综合上述例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。简单地说，作为一门学科，数据结构主要研究非数值计算的程序设计问题当中计算机的操作对象（数据）以及它们之间的关系（逻辑结构和物理结构）和操作（算法实现）。,第11页,若干名词术语,数据（data）数据元素（dataelement）数据项（dataitem）数据对象（dataobject）数据结构（datastructure）数据类型（datatype）抽象数据类型（ADT）,第12页,数据（data）,数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中、被计算机程序识别和处理的符号的集合。数值性数据非数值性数据,第13页,数据元素(dataelement)和数据项（dataitem）,数据元素是数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。数据元素又可称为元素、结点、记录。有时一个数据元素可以由若干数据项（dataitem）组成。数据项是具有独立含义的最小标识单位。,第14页,数据对象(dataobject),具有相同性质的数据成员（数据元素）的集合，数据的子集。例：整数数据对象N=0,1,2,学生数据对象有穷集和无穷集,第15页,什么是数据结构,定义:由某一数据对象及该对象中所有数据成员之间的关系组成。与“数据对象”这一概念的区别？作为术语名词和作为学科名词的区别？,第16页,数据元素间的逻辑关系，即数据的逻辑结构。数据元素及其关系在计算机存储内的表示，即数据的存储表示（物理结构、物理表示）。数据的运算，即对数据元素施加的操作。,作为学科，数据结构研究数据的组织形式，包括以下内容：,第17页,数据的逻辑结构,数据的逻辑结构从数据的逻辑关系上描述数据，与数据的存储无关，与数据元素本身的具体形式、内容无关。数据的逻辑结构可以看作是从具体问题抽象出来的数据模型。,第18页,数据的逻辑结构可归结为以下四类：,线性结构：一对一关系,树形结构：一对多关系,图状结构：多对多关系,集合结构：简单隶属关系,第19页,数据逻辑结构的描述方式,Data_Structure=D,R其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。一般表现形式如下：,D=d1,d2,dnR=r1,r2,rm,关键字：数据元素中可用于标识该数据元素的某个分量（数据项）。通常用关键字区别不同的数据元素。,第20页,D01,02,03,04,05,06,07,08,09,10R1=,R2=,R3=,第21页,R1=,用连线表示数据元素之间的联系,第22页,R2=,第23页,R3=,第24页,由上述数据结构的描述可得出结论：相同数据元素的集合（即同一数据对象），因其关系的不同而构成不同的数据逻辑结构。对一实际应用问题，合理选择数据逻辑结构才能够设计出有效的算法。,例：根据下列选课情况安排考试日程，使得在不冲突的情况下用尽可能短的时间安排所有考试。,第25页,数据的存储结构,数据的存储结构是数据在计算机内部的存储方式，依赖于计算机语言。存储结构分类顺序存储结构链式存储结构索引结构散列结构,第26页,顺序存储（矢量存储）结构Contiguousimplementation（vectorimplementation）所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存中其存储地址仍然相邻。,链式存储结构Linkedimplementation所有元素可以存放在不连续的存储单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后其存储地址不一定是相邻的。,第27页,顺序和链式存储结构示意图,第28页,数据类型,数据类型定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称。C语言中的数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值,基本数据类型（原子类型）：可以看作是计算机中程序设计语言已实现的数据结构。构造型数据类型：由相同或不同成分的类型构成，如数组、结构体、类等。,第29页,抽象数据类型(ADTs:AbstractDataTypes),由用户定义，用以表示实际应用问题的数据模型。由基本的数据类型组成,并包括一组相关的服务（或称操作）。,第30页,抽象数据类型的描述方法,抽象数据类型从形式上可用（D，R，O）三元组表示。其中：D是数据对象，R是D上的关系集，O是对D的基本操作集。,一般采用如下格式描述ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT抽象数据类型名,第31页,ADT基本操作的定义格式,基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述,参数：赋值参数只为操作提供输入值;引用参数以in-1;+i)if(j!=i)ajai,j=i;/选择第i个最小元素for(k=i+1;kn;+k)if(akaj)j=k;,第48页,例三冒泡排序,voidbubble_sort(int-i)/冒泡排序,基本操作:赋值操作,时间复杂度:O(n2),change=FALSE;/change为元素进行交换标志for(j=0;jaj+1)ajaj+1;ch