数据结构与算法绪论概念.ppt

数据结构与算法,教材与参考书,教材：数据结构（C语言版）严蔚敏 吴伟民编著，清华大学出版社，2006参考书：（1）数据结构(C语言篇)习题与解析 李春葆编著，清华大学出版社，2001(2)数据结构课程实验 徐孝凯编著，清华大学出版社，2005（3）数据结构与算法 齐德昱编著，清华大学出版社，2003.10,课程的内容 数据结构经典的算法考核作业+实验+考试,数据结构与算法,1.1 什么是数据结构 数据结构问题起源于程序设计的发展。程序设计现在已经历了三个阶段：无结构阶段 1940s1960s，科学计算。结构化程序设计阶段 1960s末1980s 提出程序结构模块化，模块内以顺序、分支、循环为主。应用于非数值领域。,第一章 绪论,1.1 什么是数据结构,注意到数据表示与操作的结构化，程序中常用的一些数据表示，如表、栈、队、树、图等被单独列出研究。面向对象阶段(Object Oriented DS)兴起于1980s初，1990s流行。对象描述实体的属性与操作，是二者的封装体。面向对象技术实质上是数据结构概念的自然扩展与继续，对象包含数据结构中的主要因素数据成分与操作。数据结构的发展面向各专门领域中特殊问题的数据结构得到研究和发展。从抽象数据类型的观点来讨论数据结构。,例 计算机管理家谱,家谱管理主要实现家庭成员登记、查询及变更处理等。假定只考虑家庭中的父子关系。实体对象是人（家庭成员），关系是父子关系。每个实体用一个记录（元素）表示，包含姓名、出生日期、性别、死亡日期等。为了表示父子关系，在实体记录中可增加若干字段，每个字段用于指示一个儿子/女儿。一个家族就构成了一个层次结构。在数据结构中，该层次结构称为树。图1.1位于某结点下方的与其相连的各个结点，表示该结点的子女。,例家谱结构图,1.2 基本概念和术语,数据：所有能输入到计算机中并被计算机程序处理的符号的总称（包括数字、字符、声音、图像等信息）。数据类型：数据类型定义为：一个值的集合和定义在这个值集上的一组操作的总称。数据元素：能独立、完整地描述问题世界中的实体的最小数据单位称为数据元素（也称记录）。构成数据元素的不可分割的数据单位，称为数据项（也称字段）。数据对象：性质相同的数据元素的集合，是数据的一个子集(如整数数据对象)。,数据结构,结构：把数据元素之间的关系。数据结构：同一数据元素类中各数据元素之间存在的关系。数据结构三个组成部分：数据的逻辑结构 数据的物理结构 数据的运算（操作）逻辑结构：对数据之间关系的描述。物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式。物理结构是逻辑数据的存储映象,数据结构的形式化定义,（不考虑定义在数据结构上的操作）数据结构是一个二元组（D,S），其中D(data)是数据元素的有限集，S(struct)是D上的关系的有限集。数据元素之间的关系采用集合论中关系的形式化描述方法来定义。型为的二元关系中，我们称d1为关系的前件，d2为后件。称d2为d1的后继(subsequence)，而d1为d2的前驱(previous)。,数据结构的图示,用小圆圈代表数据元素。用小圆圈之间的连线代表小圆圈对应的数据元素之间的关系，如果强调关系的方向性，可用带箭头的线段表示关系。如：若d1和d2表示两个数据元素，它们具有关系d1,d2，则表示为：,d1,d2,数据结构的分类,由数据元素间关系的不同特性，有下列四类基本的结构：集合结构。数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。(set)线性结构。该结构的数据元素之间存在着一对一的关系。(linear)树型结构。该结构的数据元素之间存在着一对多的关系。(tree)图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。(graph),集合,如果数据结构中，数据元素之间不考虑关系问题（无前驱/后继之分），则称这种结构为集合。在集合中，各元素是“平等”的，它们的共同关系是：都属于同一个集合，无其他关系。,集合结构,线性结构,如果数据结构中，数据元素之间只存在前后顺序关系（每个元素都有唯一前趋和后继，第一个元素可以没有前驱，最后一个可以没有后继），则称这种结构为线性结构。线性结构是一种最常见的数据结构。线性表、栈、队列、串等均为线性结构。下图表示的数据结构可表示为：DS=(D,S)D=d1,d2,dn S=r r=,线性结构,树形结构,如果除一个特殊元素没有前驱外，其他每个元素都有唯一的前驱（后继个数不限），则称该结构为树型结构（简称树）。其中，将无前驱的元素称为树根。用图表示树时，通常习惯将树根画在最上面。某元素的各后继画在该元素的下面，且连线不带箭头，隐含着从上到下。这样，树型结构就象用一棵倒立的树。图 11就是一个树的例子，它代表的结构的形式描述为：DS=(D,S)D=W1,W11,W12,W13,W111,W121,W122,W131,W132,W133,W1111,W1112,W1221S=rr=,图状结构,在图状结构中，任一数据元素，均可有多个前趋和多个后继。该种结构也称网状结构。图状结构表达能力最强，它可表达任意复杂的数据结构。例如，交通图就是一种图状结构，结点代表城市，连线（关系）代表城市间的道路。树形结构与图状结构均称为非线性结构。,数据结构的存储存储结构,存储器表示问题 数据结构的存储问题，一般指内存。大多数高级语言支持的访问存储器的方式是相当高级的，隐蔽了存储器的许多特性，不利于表示数据的存储结构。许多高级语言都提供按数组访问存储器的方式。数组很接近存储器，所以我们决定用高级语言中的数组模拟计算机存储器。C/C+中的指针的概念相当接近内存的地址。,存储结构,数据结构的存储映象：数据结构在计算机中的存储方式。两方面：内容存储：数据结构中的各数据元素的内容（数据），都分别存储在一个独立的可访问的存储区中;关系存储：数据元素的存放方式方法，必须能显示地或隐式地体现数据元素间的逻辑关系。,基本存储方法,（1）顺序存储这是一种主要面向线性关系的存储方法。对线性数据结构，可将其数据元素，按相应的线性关系下的前后次序，存储在物理存储器中，使得数据元素在此线性关系下的逻辑次序与它们在存储器中的存放次序一致。这种存储方式称为顺序方法（也称连续方法）。数据元素之间的线性关系由它们的存储次序体现，而不需要专门存储。,例 数据结构DS=(D,S)的顺序存储,其中，D=d1,d2,d3,d4，S=r，r=，D中每个元素需占用两个存储单元，则该结构的顺序存储结构如下图所示（称存储结构图）.,二、链式存储,每个数据元素的存储区分两大部分，第一部分为数据区，存储元素的内容，第二部分为指针区。（存放该数据元素与其它数据元素之间的关系信息，这种关系信息一般为地址）例 对上例中的数据结构，它的一种链式存储结构如表 11所示。在该表中，假定每个元素占2个存储单元，第一个存储元素内容，第二个存储关系。这里，关系用后继地址描述，元素x的“关系指示”中存放x的后继的地址。,线性结构链式存储(图示),数据元素的存储区之间，可以是连续的，也可不连续。,三、索引存储,索引存储是面向检索操作。它主要是在数据结构的数据区外，增加一个或若干个索引区。用结点的索引号来确定结点存储地址。优点：检索速度快。缺点：增加额外的索引表，占用较多的存储空间。,四、散列存储,散列存储（也称杂凑法）是一种按元素内容存储元素的方法。其基本思想是：设置一个函数，称为散列函数：元素内容地址；规定元素内容到存储地址的映射；存储时，通过散列函数求出元素的应存储的地址，按此地址存储；读取时，通过散列函数求出元素的存储地址，按此地址读取。,数据结构的存储存储结构,一、线性结构的存储方式顺序链式索引散列二、树形结构的存储方式链式三、图形结构的存储方式链式，如邻接表、邻接矩阵。,数据结构访问接口,数据的操作：指对数据的读、修改、加工、处理等操作。数据结构中的一个重要的问题是：对每种数据结构，如何设置一些操作，使得各种应用都能通过这些操作就能实现对数据结构的各种操作，我们把这类操作称为数据结构的基本操作或运算。某一数据结构的基本操作的接口的全体，称为该数据结构的访问接口。,基本操作关键点,抽象性：不涉及具体应用，只是“结构”的操作；基本性：“粒度”很小，作为构造更复杂操作的基础；完备性：只要通过基本操作就能实现各种应用要求；支撑性：具有灵活方便的特点，可以供其他应用进一步实现各种操作。,基本操作的种类,按功能归纳为下列几种基本类型：属性读取(Get)：属性设置(Set)：查找插入删除关系访问遍历,1.3 抽象数据类型的表示与实现,抽象数据类型(Abstract Data Type 简称ADT):指一个数学模型以及定义在该模型上的一组操作。定义仅取决于它的一组逻辑特性，与存储结构无关。抽象数据类型和数据类型实质上是一个概念。如：各个计算机都拥有的“整数”类型是一个抽象数据类型。抽象数据类型的范畴更广。不局限于固有数据类型，还包括用户在设计软件系统时自己定义的数据类型。,抽象数据类型的表示与实现,抽象数据类型可用三元组表示(D，S，P)其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。采用如下格式定义：ADT 抽象数据类型名 数据对象:数据关系:基本操作:ADT抽象数据类型名其中，数据对象定义-伪代码 数据关系定义-伪代码,抽象数据类型的表示与实现,基本操作定义格式:基本操作名(参数表)初始条件:操作结果:基本操作有两种参数:赋值参数-为操作提供输入值 引用参数-可提供输入值及返回结果,以&打头.,抽象数据类型的表示与实现,例1-6 抽象数据类型三元组的定义:ADT Triplet 数据对象:D=e1,e2,e3|e1,e2,e3ElemSet 数据关系:R1=,基本操作:InitTriplet(&T,v1,v2,v3)操作结果:构造三元组T,参数v1,v2,v3-e1,e2,e3。DestroyTriplet(&T)操作结果:三元组T被销毁。Get(T,i,&e)初始条件:三元组T已存在,1=i=3。操作结果:用e返回T的第i元的值。Put(T,i,&e)初始条件:三元组T已存在,1=i=3。操作结果:改变T的第i元的值为e。,抽象数据类型的表示与实现,IsAscending(T)初始条件:三元组T已存在.操作结果:如果T的三个元素按升序排列,则返回1,否则返回0.IsDescending(T)初始条件:三元组T已存在.操作结果:如果T的三个元素按降序排列,则返回1,否则返回0.Max(T,&e)初始条件:三元组T已存在.操作结果:用e返回T的三个元素中的最大值.Min(T,&e)初始条件:三元组T已存在.操作结果:用e返回T的三个元素中的最小值.ADT Triplet,抽象数据类型的表示与实现,抽象数据类型可通过固有数据类型来表示和实现,即利用处理器中已存在的数据类型来说明新的结构,用已经实现的操作来组合新的操作.教材采用:类C语言(介于伪码和C语言之间)作为描述工具.精选C语言的一个核心子集,并作扩充.简要介绍类C语言:(1)预定义常量和类型:/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0,抽象数据类型的表示与实现,#define INFEASIBLE-1#define OVERFLOW-2/Status-函数类型,函数结果状态代码typedef int Status;#define MAXINT 65536(2)存储结构用类型定义(typedef)描述,数据元素类型约定为 ElemType,用户自行定义.(3)基本操作的算法由以下形式的函数描述:函数类型 函数名(函数参数表)语句序列,抽象数据类型的表示与实现,(4)赋值语句简单赋值 变量名=表达式;串联赋值 变量名1=变量名2=变量名k=表达式;成组赋值 课本P10交换赋值 变量名1变量名2;条件赋值 变量名=条件表达式?表达式T:表达式F;,抽象数据类型的表示与实现,(5)选择语句条件语句1 if(表达式)语句;条件语句1 if(表达式)语句;else 语句;开关语句1 switch(表达式)case 值1:语句序列1;break;case 值n:语句序列n;break;defalut:语句序列n+1;,抽象数据类型的表示与实现,(6)循环语句for 语句 for(赋初值序列;条件;修改表达式序列)语句;如:for(sum=0,i=1;i=100;i=i+1)sum=sum+1;while 语句 while(条件)语句;do-while语句 do 语句序列;while(条件);(7)结束语句函数结束语句 return 表达式;return;case结束语句 break;异常结束语句 exit(异常代码);,抽象数据类型的表示与实现,(8)输入和输出语句输入语句 scanf(格式串,变量1,变量n);输出语句 printf(格式串,表达式1,表达式n);(9)基本函数求最大值 max(表达式1,表达式n)求最小值 min(表达式1,表达式n)求绝对值 abs(表达式)求不足整数值 floor(表达式)求进位整数值 ceil(表达式)如:floor(2.8)=2 floor(-2.8)=-3 ceil(2.8)=3 ceil(-2.8)=-2判断文件结束 eof(文件变量)或eof判断行结束 eoln(文件变量)或eoln,抽象数据类型的表示与实现,(10)逻辑运算约定与运算&:对于A&B,当A的值为0时,不再对B求值.或运算|:对于A|B,当A的值为1时,不再对B求值.,抽象数据类型的表示与实现,例 1-7 抽象数据类型Triplet的表示和实现/采用动态分配的顺序存储结构/由InitTriplet分配3个元素存储空间typedef ElemType*Triplet;/基本操作函数原型说明Status InitTriplet(Triplet/初始条件:三元组T已存在,1=i=3/结果:用e返回T的第i元的值,抽象数据类型的表示与实现,Status Put(Triplet/初始条件:三元组T已存在/结果:用e返回T的三个元素中的最大值,抽象数据类型的表示与实现,Status Min(Triplet T,ElemType,抽象数据类型的表示与实现,Status DestroyTriplet(Triplet,抽象数据类型的表示与实现,Status Put(Triplet,抽象数据类型的表示与实现,Status Max(Triplet T,ElemType,