1-数据结构的基本概念和术语.ppt

课程类别：专业选修 学时、学分数：48学时3学分 考核方式与要求：考查 重要性 章节介绍 绪论 4 线性表 6 栈和队列 6 串 1 数组和广义表 1 树和二叉树 9 图 9 查找 6 内部排序 6 主要内容 几点要求 上课请关机 不迟到，不旷课 准备笔记本 机房禁止玩游戏，上网，吃东西 6、抽象数据类型(Abstract Data Type 简称ADT) 指一个数学模型以及定义在该模型上的一组操作。 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作） 抽象数据类型的描述方法(P8) 抽象数据类型可用（D，S，P）三元组表示。 其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。 格式：ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 赋值参数 只为操作提供输入值。 引用参数 以打头，除可提供输入值外，还将返回操作结果。 初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。 例9、抽象数据类型复数的定义 ADT Complex {　数据对象：D = {e1,e2 | e1,e2 RealSet }　数据关系：R1 = {e1,e2 | e1是复数的实部，e2是复数的虚部 }　基本操作：　　InitComplex( Z, v1, v2 )　　　操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。　　DestroyComplex( Z)　　　初始条件：复数已存在。　　　操作结果：复数Z被销毁。　　GetReal( Z, realPart )　　　初始条件：复数已存在。　　　操作结果：用 realPart 返回复数Z的实部值。　　GetImag( Z, ImagPart )　　　初始条件：复数已存在。　　　操作结果：用 ImagPart 返回复数Z的虚部值。 　　Add( z1,z2, sum )　　　初始条件：z1，z2 是复数。　　　操作结果：用sum返回两个复数z1，z2的和值。} ADT Complex 假设:z1和z2是上述定义的复数 则 Add(z1, z2, z3) 操作的结果 即为用户要求的结果 z3 = z1 + z2 课堂总结 主要内容：什么是数据结构、数据结构的基本概念。 重点难点：数据结构的基本概念。 作业 复习，理解相关概念 预习， 算法及其分析 计算机解题是指计算机对某类信息进行某一种的处理，步骤如下 数据结构是一门和程序设计密切相关的课程，美国的计算机专家pascal语言的创始人Niklaus Wirth教授在1976年出版了一本书： 《算法+数据结构=程序》说明了算法和数据结构是进行程序设计的两大要素，也就是进行程序设计首先要解决这两个问题。 计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，将此称为非数值性处理。 计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，将此称为非数值性处理。 在由多个数据项构成的数据元素中必定存在关键字。 关键字　　指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 “主” 关键字，否则称之为 “次” 关键字。 在由多个数据项构成的数据元素中必定存在关键字。 关键字　　指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 “主” 关键字，否则称之为 “次” 关键字。 存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。 有两种表示方法： 以x,y的有序对为例,即x和y在逻辑上有先后关系 一为“顺序映象”。以 “y 相对于 x 的存储位置” 表示 “y 是x的后继”，(即x和y在存储位置上是有先后关系的)由此得到的数据存储结构为“顺序存储结构”。 二为“链式映象”。以和x绑定在一起的附加信息(指针)表示后继关系， (即x和y在存储位置上是没有先后关系的)这个指针即为 y 的存储地址，由此得到的数据存储结构为链式存储结构。 信息工程系 * * 课程介绍 数学 软件 硬件 数据结构 数据结构 逻