915-数据结构的基本概念.ppt
《915-数据结构的基本概念.ppt》由会员分享,可在线阅读,更多相关《915-数据结构的基本概念.ppt(59页珍藏版)》请在三一文库上搜索。
1、第1章 绪论,吴文国,主要内容,1.1 数据结构的基本概念 1.2 数据结构的内容 1.3 算法设计 1.4 算法描述工具 1.5 算法的性能评价 1.6 数据结构与C语言表示,1.1 数据结构的基本概念,本节介绍以下几个基本概念和术语 1. 数据 2. 数据元素和数据项 3. 数据结构 4. 数据类型 5. 抽象数据类型,1. 数据,数据是信息的载体,它是能够被计算机识别、存储和加工处理。,信息,计算机,数据,数据的主要特征,计算机能够识别、能够处理、能够存储的信息。 计算机化的信息。 数据的含义随着计算机的发展而变化。,数据处理的实例,例1:要判断某一点是否在三角形之内 例2:判断下面这个
2、人是否是某个电影明星 例3: 判断二条直线是否相交 如何要计算机处理这些问题?如何把这些问题表示成计算机能处理的数据呢?,数据例子,表示物体的位置,我们用两个整数表示。 表示物体飞行路径(假设是直线的)则用两个点来描述。 假如描述物体运动过程,则要坐标,时间来描述。 如何表示声音?,结论,数据是表示客观事物的数值、文字能够被计算机识别的各种符号集合。,说明,数据随计算机的发展而变化。 最早的计算机:只能处理二进制的数据,需要打孔(punch)。 后来可以是十进 制数据,再后来可以是英文字符,声音,图像。,2. 数据元素,数据元素(Data Element) 数据元素是数据基本单位,在处理过程一
3、般表示其整体性和完整性。数据元素又称为元素,顶点或结点。又称记录(Record)。,数据项,数据项:是具有独立含义的最小标识。又称为数据域。,数据项与数据元素的关系,数据元素是由数据项组成的。,举例,数据元素:一行就是一个数据元素,张三,男,78等是一个数据项。,数据对象,数据对象是性质相同的数据元素的集合,是数据的一个子集。如整数数据对象。 某个班级的45位同学的数据(姓名,性别,地址,联系电话,家长姓名,照片)。,3. 数据结构(Data Structure),数据结构是指数据相互之间存在一种或多种特定关系的数据元素集合。,4. 数据类型,所谓数据类型是一个值的集合以及定义在这些值上的操作
4、的总称。一般高级语言有基本的数据类型,也有根据用户需要创建的类型,即结构体。 数据结构课程 里经常用到结构体。,数据类型,原子类型:不可分割,如整型(int ,char,float ,double) 结构类型:其可以分割的,如数组,结构体等(struct ,union)。 通常数据类型可以看成是程序设计语言中已实现的数据结构。,5. 抽象数据类型ADT,ADT包括定义和实现两个方面。定义独立于实现。定义仅给出一个ADT的逻辑特性,不必考虑如何在计算机中实现。 只从问题本身抽象出来。,ADT定义的格式,ADT 数据对象: 结构关系: 基本操作: ADT ,ADT说明,数据对象定义是用已定义的数据
5、类型定义新的数据对象。 数据对象和结构关系采用数学符号和自然语言描述。 基本操作定义包括操作名,参数表、初始条件和操作结果四部分内容的定义和描述。其格式是 操作名(参数表) 操作前提:操作前提描述 操作结果:操作结果描述,例1-2 给出简化线性表的ADT类型定义,ADT Linear_List 数据对象:所有属于同一类型的数据对象,i=1,2n,n=0 结构关系:所有数据元素ai,存在次序关系。a1无前趋,an无后继 基本操作: InitList(L):初始化空表,续,ListLength(L):求线性表的长度 GetData(L,i):取线性表的第i个元素 InsList(L,i,b): 在
6、L线性表中i位置插入元素b. DelList(L,i):删除L的第i个元素。 通过以上描述可以知道,由于它是ADT(抽象),不限于某个特定类开,也不限于某特定的存储类型。,用C语言实现ADT,在用C语言实现ADT时,要考虑数据的存储类型。 譬如前面的例子里, a可以是一个整数,或一个浮点数,或一个学生信息的数据元素。 数据存储可以是数组,也可以是链表等,只要能反映它的逻辑结构关系就行。,1.2 数据结构的内容,数据结构这个术语包含三方面的内容: 1. 逻辑结构 2. 存储结构 3. 算法设计,1. 逻辑结构, 数据元素之间的逻辑关系,也称数据的逻辑结构(Logical Structure);
7、数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。,四种逻辑结构,集合结构 线性结构 树形结构 图状结构 线性结构:线性表、栈,队、串,数组,广义表 非线性结构:树和图,2. 存储结构,数据元素及其关系在计算机存储器内的表示,称为数据的存储结构(Storage Structure); 数据的存储结构是逻辑结构用计算机语言的实现(亦称为映象),它依赖于计算机语言。一般只在高级语言的层次上讨论存储结构。,3. 数据的运算,数据的运算,即对数据施加的操作。 数据的运算定义在数据的逻辑结构上,每种逻辑结构都有一个运算的集合。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 915 数据结构 基本概念
链接地址:https://www.31doc.com/p-3025385.html