数据结构-1合编.ppt

主讲教师：顾韵华 2007.3~2007.7 yhgu@nuist.edu.cn 迷宫问题。在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树” 多叉路口交通灯问题 算法的描述 流程图 自然语言 伪代码 高级语言 数据(逻辑)结构的二种常用表示方法（图示、二元组） ? 图示表示 图示表示是由顶点和边构成的图，其中顶点表示数据 ，边表示数据之间的结构关系； 001 003 002 004 006 005 008 007 例如：学生基本情况表的图示表示 J I A C B D H G F E 再如：家族树的图示表示 例如：学生基本情况表的二元组表示（D，S） ? 二元组表示 二元组表示是用一个二元组（D，S）表示数据结构， 其中 D 是数据元素集合，S 是 D 上关系的集合。 D = { 001，002，003，004，005，006，007，008} S = { R } R= {001,002,002,003,003,004,004,005,005,006, 006,007,007,008 } 再如：家族树的二元组表示（D，S） D = { A，B，C，D，E，F，G，H，I，J} S = { R } R = {〈A,B,A,C,A,D,B,E,B,F,C,G,D,H,D,I,D,J } J I A C B D H G F E 001 003 002 004 006 005 008 007 (2) 数据的存储(物理)结构 --逻辑结构在存储器中的映象 数据元素的映象方法：用二进制位(bit)的位串表示数据元素 。 例如： (321)10 ? (101000001)2 A ? (001000001)2 关系的映象方法：主要有以下 4种 顺序结构 链接结构 索引结构 散列结构 ? 链接结构： 使用指针表示元素间的关系。 ? 顺序结构： 以计算机存储器中存储单元之间的相邻关系表示元素间的相邻关系。 x y z 特点：使用连续存储空间，整个存储结构中只含数据元素本身的信息。 x y z 顺序结构与链接结构的比较： 从空间利用率和运算两方面进行比较。 ? 索引结构： 使用索引表和基本表实现数据结构。 ? 散列结构： 根据结点的值确定结点存储地址。 说明： 4种存储方法可结合使用。 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队列 树形结构 图形结构 数据结构的三个方面： 散列存储 索引存储 串及数组 1.3 抽象数据类型(ADT) 数据类型与抽象数据类型的区别？ 抽象数据类型如何定义？ 抽象数据类型如何表示和实现？ 提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。 数据类型：在一种程序设计语言中，变量所具有的 数据种类。用于刻画操作对象的特征。 例、在C语言中： 数据类型：基本类型和构造类型 基本类型：整型、实型、字符型、指针、枚举型 构造类型：数组、结构、共用体 数据类型与抽象数据类型的区别？ 数据类型：是一个值的集合和定义在该值上的一组 操作的总称。 抽象数据类型（ADT）：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。 ADT特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 抽象数据类型如何定义？ 抽象数据类型可以用以下的三元组来表示： ADT = （D，S，P） 数据对象 D上的关系集 D上的操作集 ADT抽象数据类型名{ 数据对象：数据对象的定义