数据结构-1合编.ppt

  1. 1、本文档共68页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
主讲教师:顾韵华 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抽象数据类型名{ 数据对象:数据对象的定义

文档评论(0)

1112111 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档