数据结构 课件 第一章绪论

《数据结构 课件 第一章绪论》由会员分享，可在线阅读，更多相关《数据结构 课件 第一章绪论（66页珍藏版）》请在金锄头文库上搜索。

1、2020/9/13,1,数据结构,第一章 绪论,院(系) : 计算机科学与技术学院 教研室: 计算机软件与理论(602) 教 师: 王红滨,2020/9/13,2,重点和难点 重点:了解有关数据结构的各个名词和术语的含义,以及语句频度和时间复杂度、空间复杂度的估算。 难点:无 知识点 数据、数据元素、数据结构、数据类型、算法及其设计原则、时间复杂度、空间复杂度,第一章 绪论,2020/9/13,3,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.5 C语言回顾,本章与后续各章的关系:本章是后续各章的准备,主要内容,2020/9/13

2、,4,1.1 数据结构,用计算机解决一个具体的问题,需要经过以下几个步骤: 从具体问题抽象出一个适当的数学模型; 设计一个解此数学模型的算法; 编出程序; 进行测试、调整直至得到最终解答。,寻求数学模型的实质: 分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。,2020/9/13,5,1.1 数据结构(续),很多问题求解最后都转化为求解数学方程或数学方程组。 在房屋设计或桥梁设计中的结构应力分析计算可化解为线性代数方程组求解的问题, 天天看到的天气预报,它的数学模型是一个环流模式方程。 预报人口增长情况的数学模型为微分方程。 当计算机进入非数值计算领域

3、,特别是用在管理上的时候,计算机的操作对象之间的关系就无法用数学方程加以描述了。,非数值计算问题的数学模型正是本课程要讨论的数据结构。,2020/9/13,6,1.1 数据结构(续),书目文件,例1 书目自动检索系统,线性的数据结构,2020/9/13,7,1.1 数据结构(续),特点: (1)每本图书的信息占据一行,所有图书的信息按登录号顺序依次排列构成一张表格; (2)表中每本图书的信息依据登录号的大小存在着一种前后关系,这就是我们所说的线性结构; (3)对它的操作通常是插入某本图书的信息,删除某本图书的信息,更新某本图书的信息,按条件检索某本图书的信息等等。,2020/9/13,8,例2

4、-1 人机对奕问题,树形的数据结构,2020/9/13,9,例2-2 学校问题,刘志刚,部门,学院,.,后勤集团,系,科,教研室,实验室,.,我,.,树形的数据结构,2020/9/13,10,1.1 数据结构(续),特点: (1)在表示或求解过程中,所处理的数据之间具有层次关系,这是我们所说的树形结构; (2)对它的操作有:建立树形结构,输出最低层结点内容等等。,2020/9/13,11,例3-1 多叉路口交通灯管理问题,图形的数据结构,2020/9/13,12,例3-2 交通网问题,在交通咨询系统中,我们可以采用一种图的结构来表示实际的交通网络。图中的顶点表示城市,边表示城市间的交通联系,对

5、边所赋予的权值可以表示两城市间的距离,或途中所需的时间,或交通费用等等。考虑到交通图的有向性(如航运,逆水和顺水时的船速就不一样),图中的边可以用弧线来表示,如下图所示。这个咨询系统可以回答旅客提出的各种问题。 例如,从某地到某地应如何走才最节省费用,也就是要求从某地到某地的最短路径。在这个问题中所使用的图也是一种数据结构。,2020/9/13,13,图 一个表示交通网的图,例3-2 交通网问题,2020/9/13,14,1.1 数据结构(续),特点 (1)道路之间的先后关系用图结构描述; (2)通过实施创建图结构,按要求得到正确结果。,2020/9/13,15,1.1 数据结构(续),结论:

6、 计算机的操作对象的关系更加复杂,操作形式不再是单纯的数值计算,而更多地是对这些具有一定关系的数据进行组织管理,我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理,就必须弄清楚这些操作对象的特点,在计算机中的表示方式以及各个操作的具体实现手段。这些就是数据结构这门课程研究的主要内容。,2020/9/13,16,1.1 数据结构(续),瑞士的计算机专家在1976年出版了一本书,书名为算法+数据结构 = 程序设计,它正说明了数据结构在程序设计中的作用。 程序设计的实质即为计算机处理问题编制一组指令,首先需要解决两个问题:即算法和数据结构。算法即处理问题的策略,而数据结构即为问题的

7、数学模型。 简单地说,数据结构是一门讨论描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现的学科。,地位:,2020/9/13,17,1.1 数据结构(续),数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 主要研究和讨论以下三个方面的问题: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构。 (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。 (3)对各种数据结构进行的运算。,2020/9/13,18,1.2 基本概念和术语,数据 是描述客观事物的符号表示,指所有能输入到

8、计算机中并被计算机程序处理的符号的总称。 是计算机加工的“原料”。 包括:图像、声音、数值、字符串等。 数据元素 是数据的基本单位。 在计算机程序中通常作为一个整体进行考虑和处理。 例如:5,N,记录,格局,顶点。 数据项: 一个数据元素可由多个数据项组成。 数据项是数据的不可分割的最小单位。 例如:字段,2020/9/13,19,1.2 基本概念和术语(续),信息:客观事物在人的头脑中的反映,人们进行各种活动所需要的知识。 数据和信息:(1)并非任何数据都能表示信息,信息是消化的数据,信息依赖数据存在。(2)信息是更基本的,直接反映现实的概念,数据是信息的具体表现。信息=数据+处理,关键字

9、能识别一个或多个数据元素的数据项。 若能起唯一识别作用,则称之为 “主” 关键字,否则称之为 “次” 关键字。 例如:学号,2020/9/13,20,1.2 基本概念和术语(续),数据对象 是性质相同的数据元素的集合。 是数据的一个子集。 例如:整数数据对象是集合N=0,1,2, 字母字符数据对象是集合C=“A”,“B”,“Z”,2020/9/13,21,1.2 基本概念和术语(续),数据结构(data structure):指互相之间存在着一种或多种特定关系的数据元素的集合。在任何问题中,数据元素之间都不会是孤立的, 在它们之间都存在着这样或那样的关系,这种数据元素之间的关系称为结构。根据数

10、据元素间关系的不同特性,通常有下列四类基本的结构: (1)集合结构:在集合结构中,数据元素间的关系是“属于同一个集合”,集合是元素关系极为松散的一种结构。 (2)线性结构:该结构的数据元素之间存在着一对一的关系。如线性表、栈、队列 (3)树形结构:该结构的数据元素之间存在着一对多的关系。 (4)图状(网状)结构:该结构的数据元素之间存在着多对多的关系,图状结构也称网状结构。,2020/9/13,22,1.2 基本概念和术语(续),图 四类基本结构的关系图 (a) 集合; (b) 线性; (c) 树形; (d) 图状,(a) (b) (c) (d),下图表示上述四类基本结构的关系图。,2020/

11、9/13,23,1.2 基本概念和术语(续),数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系,又称此为逻辑结构。,数据的逻辑结构,数据的物理结构,数据的运算:检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面:,(以后称”存储结构”),(以后称”数据结构”),串,（操作）,2020/9/13,24,1.2 基本概念和术语(续),数据的物理结构 顺序存储结构借助元素在存储器中的相对位置来表示数据元 素间的逻辑关系。 链式存储结构借助指示元素存储地址的指针表示数据元素间 的逻辑关系,存储结构是逻辑结构在存储器

12、中的映象,它包含数据元素的映象和关系的映象。,2020/9/13,25,1.2 基本概念和术语(续),元素n,.,元素i,.,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+(n-1)*m,存储地址,存储内容,Loc(元素i)=Lo+(i-1)*m,顺序存储,长度m,2020/9/13,26,1.2 基本概念和术语(续),1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,2020/9/13,27,1.2 基本概念和术语(续),关系有两种表示方法:其一为顺序映象。以 y 相对于 x 的存储位置 表示 y 是x的后继,例如,令 y 的存储位置和

13、x 的存储位置之间相差一个预设常量C,C本身是个隐含值,由此得到的数据存储结构为顺序存储结构。其二为链式映象。以和x绑定在一起的附加信息(指针)表示后继关系,这个指针即为 y 的存储地址,由此得到的数据存储结构为链式存储结构。可见,在顺序存储结构中只包含数据元素本身的信息,而链式存储结构中以由数据元素 x 的存储映象和附加指针合成的结点表示数据元素。,2020/9/13,28,逻辑结构与物理结构的比较,数据的逻辑结构是面向问题的 数据的物理结构是面向计算机的,2020/9/13,29,1.2 基本概念和术语(续),对每一个数据结构而言,必定存在与它密切相关的一组操作。 不同的数据结构其操作集不

14、同,但下列操作必不可缺:1) 结构的生成;2) 结构的销毁;3) 在结构中查找满足规定条件的数据元素;4) 在结构中插入新的数据元素;5) 删除结构中已经存在的数据元素;6) 遍历。,2020/9/13,30,1.2 基本概念和术语(续),程序中对变量或常量说明其所属类型的作用是,对它们加上两个约束条件:一是可取值的范围,二是可进行的操作。 在高级编程语言中实现的整数都具有下列“数学特性”:它是这样一个序列:,-2,-1,0,1,2,此外,它可以进行“+”、“-”、“*”、“/”及“取模”等运算。“抽象”意为提取“数学特性”。 抽象数据类型必须给它的外部用户提供完整的“接口”,例如,明确长整数

15、是取值多少的整数以及可以对它进行的操作等。同时,对外部用户来说,不需要了解它是如何实现的,内部实现的改变不影响外部的使用,更重要的是应该做到,不能让外部用户侵入内部。对外部用户来说,抽象数据类型应该完全是一个黑盒子。,2020/9/13,31,抽象数据类型,抽象数据类型(Abstract Data Type 简称 ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如,矩阵的抽象数据类型定义为,矩阵是一个由 m X n 个数排成 m 行 n 列的表,它可以进行初等变换、相加、相乘、求逆、等运算。抽象数据类型有两个重要特性:数据操作 用ADT描述程序处理的实体时,强调的是其本质的特征、其

16、所能完成的功能以及它和外部用户的接口(即外界使用它的方法)数据封装 将实体的外部特性和其内部实现细节分离,并且对外部用户隐藏其内部实现细节。,2020/9/13,32,抽象数据类型(续),在以后各章中均以如下相同形式描述抽象数据类型。 其形式定义为:ADT 抽象数据类型名 数据对象: 数据对象的定义 数据关系: 数据关系的定义 基本操作: 基本操作的定义 ADT 抽象数据类型名其中,数据对象和数据关系的定义用伪码描述,基本操作的定义格式为基本操作名(参数表)初始条件:初始条件描述操作结果:操作结果描述,2020/9/13,33,1.2 基本概念和术语(续),数据类型(data type):一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称。(高级语言中指数据的取值范围及其上可进行的操作的总称,即允许的变量种类。如:整型。),数据类型,原子类型:其值是不可分解的。