《数据结构》课件1第2章概述.pptx
《《数据结构》课件1第2章概述.pptx》由会员分享,可在线阅读,更多相关《《数据结构》课件1第2章概述.pptx(108页珍藏版)》请在文库网上搜索。
1、主要学习内容数据数据结构构相关概念相关概念12数据数据结构构课程学程学习的内容的内容3算法性能分析算法性能分析4算法及特点算法及特点数据结构相关概念v1、数据、数据v2、数据元素、数据元素v3、数据、数据项v4、数据、数据对象象v5、数据、数据结构构逻辑结构存储结构概念数据(Data)v所有能所有能输入入到到计算机中,并被算机中,并被计算机算机识别和和处理理的符号的的符号的总称称。v数数值型数据:整数、型数据:整数、实数数等;等;v非数非数值型数据:字符、文本、声音、型数据:字符、文本、声音、图像、像、视频等;等;v数据是数据是计算机程序加工的原料算机程序加工的原料,是信息的,是信息的编码表示
2、。表示。文字翻译程序处理的数据是各国语言文本字符串;视频编辑软件则处理的是视频、图片、音乐等多媒体数据。数据元素(Data Element)v数据集合中的数据集合中的一个个体一个个体。v是是数数据据的的基基本本单位位,在在计算算机机程程序序中中通通常常将将其其作作为一一个个逻辑整整体体进行行处理。理。v如如一一个个整整数数30,一一个个字字符符串串hello world,一一个个商商品品,一一节讲课视频等。等。v在在不不同同场合合下下,数数据据元元素素也也常常被被称称为元元素素、结点点、顶点点和和记录等。等。v当一个数据元素包含有多个部分信息当一个数据元素包含有多个部分信息时,通常被称,通常被
3、称为记录。v当当一一个个数数据据元元素素(记录)包包含含有有多多个个部部分分信信息息时,其其中中每每个个部部分的信息被分的信息被称称为一个一个数据数据项。v如如一一件件商商品品的的记录可可能能包包含含商商品品名名称称、编号号、类别、价价格格等等多多个数据个数据项。v数数据据项是是构构成成数数据据元元素素的的不不可可分分割割的的最最小小单位位,也也被被称称为字字段段、域域或或属性属性。数据项(Data Item)数据对象(Data Object)v数据数据对象是性象是性质相同的数据元素的集合,是数据的一个子集。相同的数据元素的集合,是数据的一个子集。v例例如如,整整数数的的数数据据对象象是是集集
4、合合0,1,2,,英英文文字字母母的的数数据据对象是集合象是集合a,A,b,B,。v在在具具体体应用用中中,一一个个数数据据对象象中中的的元元素素通通常常相相互互之之间存存在在某某种种关系关系。v相互之相互之间存在一种或多种特定关系的数据元素的集合;存在一种或多种特定关系的数据元素的集合;v带关关系系的的数数据据元元素素的的集集合合(Collection of relational data elements)。)。数据结构(Data Structure)结 构构 =实 体体 +关关 系系数据数据结构构 =数据元素数据元素+关关 系系ABv最最外外面面的的大大圆圈圈表表示示数数据据这个大集合;
5、个大集合;v标识为A和和B的的两两个个圆圈圈分分别表示表示2个数据个数据对象集合;象集合;v除除此此之之外外的的各各圆圈圈表表示示各各种不同大小的数据元素;种不同大小的数据元素;v数数据据对象象A、B中中分分别包包含含若干相同若干相同类型的数据型的数据元素元素;vB数数据据对象象中中的的数数据据元元素素之之间存存在在关关系系,即即形形成成了了一一种数据种数据结构。构。数据的层次v数据数据结构的概念由构的概念由C.A.R.Hoare和和N.Wirth在在1966年提出年提出。vAlgorithms+Data Structures=Programs-N.Wirth1976年年提出。提出。v精心精心
6、选择的的数据数据结构构可以可以带来更高的来更高的运行运行效率效率。v实现大大型型的的复复杂程程序序,必必须对程程序序所所处理理的的数数据据结构构进行行深深入入研究研究。数据结构(Data Structure)v数据数据结构构是是带关系的数据元素的集合。关系的数据元素的集合。v数据数据结构的构的2个个层面:面:逻辑结构存储结构数据结构(Data Structure)v逻辑结构构是是指指数数据据元元素素之之间的的内内在在关关系系(The intrinsic relations between data elements)。)。v根根据据数数据据元元素素之之间关关系系的的不不同同特特性性,数数据据结
7、构构被被抽抽象象为四四类逻辑结构构:线性结构线性结构(linear structure)树形结构树形结构(tree)图状结构图状结构(graph)集合结构集合结构(set)逻辑结构(Logical Structure)逻辑逻辑结构示意图结构示意图v线性性结构构(一一对一一)v树形形结构构(一一对多多)v图状状结构构(多多对多多)v集合集合(松散松散)逻辑结构(Logical Structure)v独立于独立于计算机,与是否算机,与是否存存储在在计算机算机中无关;中无关;v逻辑结构是构是从具体从具体问题中抽象出来的中抽象出来的数学模型;数学模型;vLogical_Structure=(D,R)其
8、中其中:D是数据元素的有限集合,是数据元素的有限集合,R是是D上关系的有限集合。上关系的有限集合。逻辑结构(Logical Structure)【例例1】设有数据有数据结构构G=(D,R),其中:,其中:D=A,B,C,D,ER=,画出画出逻辑结构示意构示意图。逻辑结构(Logical Structure)vPython语言内置言内置数据数据类型中:型中:线性结构列表列表类型(型(list)、元)、元组类型(型(tuple)和字符串()和字符串(str)等)等;集合结构集合(集合(set)和字典()和字典(dict)等)等。逻辑结构(Logical Structure)v存存储结构是指数据构是
9、指数据结构在构在计算机的算机的内存内存中的存中的存储表示表示方法(映方法(映像方法),存像方法),存储内容包括:内容包括:数据元素数据元素本身;本身;数据元素之数据元素之间的的关系关系;存储结构(Storage structure)v数据元素映象方法数据元素映象方法根据数据根据数据元素的性元素的性质选取取对应的的类型型进行存行存储,最,最终对应于若干于若干个字个字节的二的二进制位串。制位串。如如Python语言中,整数言中,整数对象存象存储了相了相应的的对象象头部和若干字部和若干字节的的该值的二的二进制制补码。存储结构(Storage structure)v元素之元素之间关系的关系的映象映象方
10、法方法1顺序存序存储结构构2链式存式存储结构构3索引存索引存储结构构4哈希存哈希存储结构构存储结构(Storage structure)如:表示如:表示 x,yx,y 的的方法:方法:x yxy(a)元素内置的)元素内置的顺序存序存储(b)元素外置的)元素外置的顺序存序存储v1.顺序存序存储结构构 Contiguous implementation元素间的物理位置反映其逻辑关系存储结构(Storage structure)xyv2.链式存式存储结构构Linked implementation逻辑上相上相邻的元素,其物理位置不一定的元素,其物理位置不一定相相邻;元素元素之之间的的逻辑关系由关系由
11、附加的附加的链域域(指(指针域)来域)来指示;指示;表示表示 x,yx,y 的方法:的方法:在存在存储x对象的同象的同时附加存附加存储一个地址,一个地址,该地址地址为y对象的内存象的内存映像的位置,称映像的位置,称为指向指向y的指的指针。存储结构(Storage structure)v2.链式存式存储结构构Linked implementation元元素素在在内内存存中中的的映映像像包包含含:元元素素值和和指指针域域,这两两个个部部分分的的整整体体,称称为结点点;每每个个结点点的的存存储空空间是是单独独分分配配的的,因因此此存存储这些些结点点的的内内存存空空间不一定是不一定是连续的;的;通通过
12、指指针域将每一域将每一个个结点点连接接起来起来,形成,形成链式存式存储结构。构。v链式存式存储结构存构存储线性表性表 存储结构(Storage structure)v3.索引存索引存储结构构主主数据表用数据表用顺序表序表存存储元素信息的同元素信息的同时,再建立附加的,再建立附加的索引表索引表。该方法主要用于方法主要用于快速快速查找找数据元素。数据元素。详见11章。章。存储结构(Storage structure)块间有序块内可以无序v4.哈希存哈希存储结构构也称也称哈希表,哈希表,散列散列表,表,通常通常是一个稀疏是一个稀疏顺序表,用于存序表,用于存储集合集合,元素的存元素的存储位置由关位置由
13、关键字字值决定。决定。该方法主要用于方法主要用于快速快速查找找数据元素数据元素。详见11章章。Python中的字典中的字典dict和集合和集合set底底层就是用哈希存就是用哈希存储结构构实现的。的。存储结构(Storage structure)v顺序存序存储结构构和和链式存式存储结构构是两种最基本、最常用的存是两种最基本、最常用的存储结构。在构。在实际应用用中常将两者中常将两者进行行组合运用。合运用。v同一种同一种逻辑结构构可可采用采用不同的存不同的存储方案方案,得到,得到不同的存不同的存储结构构。v表示某种表示某种逻辑结构构时选择何种存何种存储结构构,应视不同的不同的应用用场合合确定。通常确
14、定。通常从从存存储结构的空构的空间性能性能、常用基本操作的常用基本操作的时间性性能能以及以及算法的算法的简便性便性等角度等角度进行考行考虑。存储结构(Storage structure)v线性表与性表与Python的的list的关系的关系线性表是逻辑结构概念,list是线性表在Python中的一种内置存储实现方法,线性表可以有其它存储方式;Python的list中的数据元素可以不同构。问题讨论v高高级语言中的概念言中的概念。v用于区分不同用于区分不同性性质的数据并的数据并对它它们做不同操作。做不同操作。v某某种种特特定定语言言中中,确确定定了了对象象的的数数据据类型型,也也就就确确定定了了该对
15、象象的的取取值范范围、存、存储方法和可方法和可进行的操作行的操作。v例例如如Python语言言中中的的整整数数数数据据类型型用用于于存存储所所有有整整数数,采采用用变长结构构进行行存存储,可可进行行的的操操作作有有加加、减减、乘乘、除除、求求余余数数等。等。数据类型(Data Type)vPython语言言的的数数据据类型型包包括括内内置置的的数数据据类型型、模模块中中定定义的的数数据据类型型和和用用户自自定定义的的类型型。内内置置数数据据类型型包包括括数数值类型型、序序列列类型型、集集合合类型型等等,数数值类型型则包包括括整整数数、浮浮点点数数、复复数和布数和布尔类型。型。v按按照照对象象值
16、是是否否可可分分解解,数数据据类型型分分为原原子子类型型和和组合合类型型。例例如如:Python数数值对象象的的值不不可可再再分分解解,属属于于原原子子类型型;而而序列序列类型和集合型和集合类型的型的对象包括了多个成分,象包括了多个成分,属于属于组合合类型型。数据类型(Data Type)v抽抽象象数数据据类型型是是指指一一个个数数学学模模型型及及定定义在在该模模型型上上的的一一组操操作作,简称称ADT。这个个概概念念允允许我我们定定义现实世世界界中中的的任任何何对象象,但但它它去去除除了了数数据据类型型概概念念中中关关于于具具体体存存储方方法法的的描描述述,仅包包含含两两个个方方面面:一一是
17、是对该数数学学模模型型本本身身性性质的的描描述述,二二是是对该模型的基本操作的描述模型的基本操作的描述。vADT定定义的两个方面的两个方面对应于:于:数据结构的逻辑结构和对该数据结构的操作;因此可以用ADT定义来描述数据结构,但注意ADT定义与计算机内部表示和实现无关,因此此时描述的数据结构也不涉及具体的存储方案。抽象数据类型(Abstract Data Type)v在在C+和和Java语言言中中,可可以以用用抽抽象象类来来描描述述抽抽象象数数据据类型型,然然后再后再设计普通普通类来来实现抽象抽象类完成完成对它的表示和操作它的表示和操作。v在在Python语言言中中,可可以以通通过引引入入AB
18、C模模块利利用用抽抽象象基基类来来描描述述抽象数据抽象数据类型,型,ABC是是Abstract Base Class的的缩写写。抽象数据类型(Abstract Data Type)抽象数据类型“容器”的定义v利利用用ABC模模块定定义一一个个抽抽象象基基类AbsrtactContainer来来表表示示抽抽象象数据数据类型型“容器容器”。v一个容器一个容器类型的型的对象可以容象可以容纳多个元素,并且具有以下操作:多个元素,并且具有以下操作:返回容器中元素个数;判断容器是否为空;在容器中放入元素item;在容器中删除元素item;判断容器中是否包含元素item;清空容器中的所有元素;输出容器中的所
19、有元素。from abc import ABCMeta,abstractproperty,abstractmethodclass AbstractContainer(metaclass=ABCMeta):抽象容器类,metaclass=ABCMeta表示将AbstracContainer类作为ABCMeta的子类 继承于abc.ABCMeta的类可以使用abstractproperty,abstractmethod修饰器声明虚属性与虚方法 abstractmethod def size(self):返回容器中元素的个数 abstractmethod def empty(self):判断容器是否
20、为空 abstractmethod def insert(self,item):在容器中放入元素item abstractmethod def remove(self,item):在容器中删除元素item abstractmethod def contains(self,item):判断容器中是否包含元素item abstractmethod def clear(self):清空容器中的所有元素 abstractmethod def output(self):输出容器中的所有元素 抽象数据类型“容器”的定义v定定义一一个普通个普通类AContainervAContainer继承抽象基承抽象基类
21、AbstractContainervAContainer实现AbstractContainer的各个方法的各个方法抽象数据类型“容器”的实现class AContainer(AbstractContainer):def _init_(self,source=):self.data=source def size(self):return len(self.data)def empty(self):return len(self.data)=0 def insert(self,key):self.data.append(key)def contains(self,x):return x in s
22、elf.data def remove(self,key):return self.data.remove(key)def clear(self):self.data.clear()def output(self):print(self.data)a=AContainer(3,4)a.insert(5)a.insert(6)a.remove(4)a.output()a.clear()a.output()抽象数据类型“容器”的实现v数据数据结构、构、ADT与与Python类的关系的关系用ADT来描述数据结构的逻辑结构及其操作用Python的抽象类来定义ADT用Python的普通类来实现ADT,即
23、实现数据结构的逻辑结构、存储结构和基本操作当然,同一ADT可以有多种不同的实现方案。v数据数据结构通常包括构通常包括2个个层次:次:逻辑结构:元素之构:元素之间的关系,与的关系,与计算机无关算机无关存存储结构:数据构:数据结构的存构的存储,与,与计算机相关算机相关问题数据结构课程学习的内容v要要在在某某城城市市新新区区的的各各小小区区之之间铺设通通讯线路路,要要求求连通通每每个个小小区,并使得区,并使得总投投资最小。最小。请设计一个方案。一个方案。v假假设该新新区区共共有有n个个小小区区,要要连通通n个个小小区区,至至少少需需要要铺设多多少条少条线路?路?n-1如4个小区,必须要有3条线路才能
24、连通它们v到底到底选哪几条哪几条线路呢路呢?例:最小代价铺设通讯线路例:最小代价铺设通讯线路a、b、c、d四四个个小小区区,测算算出出每每两两个个小小区区之之间铺设通通讯线路路的的造造价,并用一个价,并用一个带权图来表示;来表示;图的的顶点点表表示示小小区区,顶点点之之间的的边及及权值表表示示对应小小区区间架架设通通讯线路路时所所需需的的代代价价,如如连通通a、b小区的代价是小区的代价是12万;万;这个个最最小小代代价价连通通的的问题对应于于图的最小生成的最小生成树的求解的求解问题;整整个个问题归结为图的的存存储表表示示和和最小生成最小生成树求解的求解的问题。算法实现/算法分析外部对象(小区)
25、实现功能(最小代价连通)逻辑结构(带权图)基本操作(求解最小生成树)存储结构(邻接矩阵或邻接表)数据抽象问题抽象数据表示算法抽象应用程序编程调试与计算机无关与计算机无关数据结构课程数据结构课程研究研究内容内容抽象数据抽象数据类型类型v在于在于解决两个主要解决两个主要问题:根据实际问题选择一种好的数据结构;设计一个好的算法,好的算法在很大程度上取决于描述实际问题的数据结构。vPrograms=Algorithm+Data Structures (程序(程序=算算 法法+数数 据据 结 构构 )数据结构:问题的数学模型,它反映数据元素之间关系。算 法:解决问题的策略、步骤程序设计的实质v1.确定求
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件 概述