《数据结构》(C语言版)-第一章-绪论.ppt

  1. 1、本文档共63页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第一章 绪论 §1.1 什么是数据结构 例2 书目自动检索系统 例3 人机对奕问题 例4 教学计划编排问题 数据的逻辑结构:只抽象反映数据元素的逻辑关系。 有两种衡量算法效率的方法: 1.事后统计法:利用计算机内记时功能,用一组或多组相同的统计数据区分。 2.事前分析估计法:求出算法的一个时间界限函数。 三、抽象数据类型 (Abstract Data Type 简称ADT) ADT定义: 指一个数学模型以及定义在该模型上的一组操作。 “抽象”的意义在于数据类型的数学抽象特性。 例如: 矩阵 +(求转置、加、乘、求逆、求特征值) 构成一个矩阵的抽象数据类型。 ADT的描述方法: 抽象数据类型可用三元组 (D,S,P) 表示。 其中:D 是数据对象; S 是 D 上的关系集; P 是对 D 的基本操作集。 ADT 抽象数据类型名 { 数据对象:〈数据对象的定义〉 数据关系:〈数据关系的定义〉 基本操作:〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名(参数表) 初始条件:〈初始条件描述〉 操作结果:〈操作结果描述〉 赋值参数:只为操作提供输入值。 引用参数:以打头,除可提供输入值外, 还将返回操作结果。 初始条件:描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息。 操作结果:说明了操作正常完成之后,数据结构的变化状况和应返回的结果。若初始条件为空,则省略之。 例如,抽象数据类型复数的定义: 数据对象: D={e1,e2|e1,e2∈RealSet } 数据关系: R1={e1,e2 | e1是复数的实数部分 | e2 是复数的虚数部分 } ADT Complex { 基本操作: AssignComplex( 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 即为用户所求的结果 ADT 有两个重要特征: 数据抽象: 用ADT描述程序处理的实体时,强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。 数据封装: 将实体的外部特性和其内部实现细节分离,并且对外部用户隐藏其内部实现细节。 ADT的表示和实现: 抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 例如,对以上定义的复数。 typedef struct { float realpart; float imagpart; }complex; // -----存储结构的定义 // -----基本操作的函数原型说明 void Assign( complex Z, float realval, float imagval ); // 构造复数 Z,其实部和虚部分别被赋以 //参数 realval 和 imagval 的值 float GetReal( complex Z ); // 返回复数 Z 的实部值 float Getimag( complex Z ); // 返回复数 Z 的虚部值 void add( complex z1, complex z2, complex sum ); // 以 sum 返回两个复数 z1, z2 的和 // -----基本操作的实现 void add( complex z1, compl

文档评论(0)

好文精选 + 关注
实名认证
内容提供者

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

1亿VIP精品文档

相关文档