数据结构绪论解读.ppt

第一章 绪论 什么是数据结构 基本概念和术语 抽象数据类型的表示和 实现 算法和算法分析 绪论 数据结构在计算机科学中是一门综合性的专业基 础课.在计算机科学中，数据结构不仅是一般程序设 计的基础，而且是设计和编译程序、操作系统、数据 库系统及其它系统程序和大型应用程序的重要基础。 ??? 本课程详细介绍了线形表、栈和队列、串、数组 和广义表、树和二叉树及图等几种基本类型的数据结构， 以及在程序设计中经常遇到的两个算法--查找和排序算法。 本课程的内容 是研究数据的逻辑组织,物理存储方式,以及对于数据进行各种操作的方法(插入,删除,修改,查找等),设计各种算法,并且分析算法效率,研究各种数据结构的性质. 因此,数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科. 什么是数据结构 例1-1:设有一个职工通讯录,要求编写查找某一个职工的家庭地址的算法. 分析: . 计算机程序处理的对象---职工通讯录表(这些对象之间存在着最简单的线性关系) .计算机程序的操作是按照某个特定的要求进行查询(不是数值性计算) 例1-2 人机对弈问题 分析: .计算机操作的对象是对弈过程中可能出现的棋盘状态(棋局)---树型结构. .计算机操作的对弈过程是一个从树根(开局)经过树枝到树叶(结局)的过程---非数值性计算 例1-3学生选课系统.通常一个学生可选择多门课程,一门课程可以被多个学生选择,这样学生和课程之间形成了多对多关系. 分析: .计算机操作的对象----图型结构 .计算机的操作------非数值性计算 什么是数据结构 通过上面三个例子可见,描述这类非数值计算问题的数学模型不在是数学方程,而是诸如表,树,图之类的数据结构.因此要设计一个高效实用的程序,必须分析程序处理的数据对象的特性,合理的组织数据,了解数据之间的关系,这就是”数据结构”这门学科形成和发展的背景. 因此,数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科. 基本概念和术语(1) 数据： 是对客观事物的符号表示，在计算机科 学中 是指所有能输入到计算机中并被计算机程序 处理的符号的总称。 数据元素：是数据的基本单位。 数据项： 是数据的不可分割的最小单位。 数据对象：是性质相同的数据元素的集合，是数据的一 个子集。 数据结构：是相互之间存在一种或多种特定关系的数据 元素的集合。 四种基本数据结构： （1）集合：元素之间同属于一个集合； （2）线性结构 ： 一对一关系； （3）树形结构： 一对多关系； （4）图状结构： 多对多关系； 数据结构形式定义： Data Structure=(D,S) 其中：D是数据元素的有限集，S是D上关系 的有限集。 物理结构（存储结构）：数据的逻辑结构在计算机中的表示。即数据元素和数据元素之间的关系在计算机中的表示. 数据元素之间的关系在计算机中有两种不同的表示方法： 顺序映象和非顺序映象 并由此得到两种不同的存储结构： 顺序存储结构和链式存储结构。 数据类型（Data Type）：数据类型是一个值的集合和定 义在这个值集上的一组操作的总称。 多形数据类型（Polymorphic Data Type）： 是指其值的成分不确定的数据类型 抽象数据类型 抽象数据类型（Abstract Data Type)：是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型表示：ADT=（D，S，P） 抽象数据类型定义的格式： ADT抽象数据类型名{ 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 } ADT抽象数据类型名 三元组Triplet的抽象数据类型的定义 抽象数据类型三元组Triplet的定义举例： ADT Triplet