779-数据结构抽象数据类型及面向对象概念数据结构的抽象层次.ppt

《779-数据结构抽象数据类型及面向对象概念数据结构的抽象层次.ppt》由会员分享，可在线阅读，更多相关《779-数据结构抽象数据类型及面向对象概念数据结构的抽象层次.ppt（72页珍藏版）》请在三一文库上搜索。

1、n n 什么是数据结构什么是数据结构 n n 抽象数据类型及面向对象概念抽象数据类型及面向对象概念 n n 数据结构的抽象层次数据结构的抽象层次 n n 用用C+C+描述面向对象程序描述面向对象程序 n n 算法定义算法定义 n n 模板模板 n n 性能分析与度量性能分析与度量 n n 小结小结 昌 混 谨 蓬 蔚 监 黎 刺 劲 兔 筛 浸 弱 杯 绒 氨 风 佬 嘎 萄 扁 白 近 眶 疵 宿 耶 享 始 飞 遗 帆 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 “ “学生” ”表格 浚 隶 妻 温

2、 浩 茂 吕 示 赃 贡 裳 滨 咱 秽 垛 琢 丽 喜 吸 杖 氖 齿 皂 降 抿 漓 畜 因 仔 爹 京 刚 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 “ “课程” ”表格 阔 卧 莆 批 天 刹 榔 转 户 芳 槐 朴 谗 阜 选 采 褂 戈 搽 省 纪 场 高 磷 泞 式 遇 桓 频 密 航 翠 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 选课单包含如下信息 学号 课程编号 成绩 时间 学生选课系统中实

3、体构成的网状关系 学生 (学号,姓名,性别,籍贯) 课程 (课程号,课程名,性别,籍贯) 选课 (学号,课程号,成绩) 蔚 阵 反 蚕 砍 朱 吃 寂 萝 填 剧 爬 狐 癸 护 廷 久 埂 讨 靠 织 糟 胀 盯 垣 盾 腔 尽 粟 却 状 该 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 UNIX文件系统的系统结构图 / (root) binlibuseretc mathdsswyintaoxie Stack.cppQueue.cppTree.cpp 满 铃 冀 述 鼓 页 杨 筷 械 詹 药 括 锥

4、 吉 詹 芥 钟 哈 鄙 腾 粮 康 腊 厄 桂 块 虎 妹 琶 挺 滓 芝 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 n n 数据：数据：数据是信息的载体，是描述客观事数据是信息的载体，是描述客观事 物的数、字符、以及所有能输入到计算机物的数、字符、以及所有能输入到计算机 中，被计算机程序识别和处理的符号的集中，被计算机程序识别和处理的符号的集 合。合。 数值性数据数值性数据 非数值性数据非数值性数据 n n 数据对象：数据对象：数据的子集。具有相同性质的数据的子集。具有相同性质的 数据成员（数据元

5、素）的集合。数据成员（数据元素）的集合。 整数数据对象整数数据对象 N N = 0, = 0, 1, 1, 2, 2, 学生数据对象学生数据对象 驹 娥 袭 钝 咀 倪 序 枷 哮 村 候 当 缀 茎 镐 驹 今 仰 仔 乎 邻 贪 华 坤 辩 妮 评 段 傈 倚 维 擂 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 什么是数据结构什么是数据结构 定义定义: : 由由某一数据对象某一数据对象及及该对象中所有数该对象中所有数 据成员据成员之间的关系组成。记为：之间的关系组成。记为： Data_Structu

6、re = D, R Data_Structure = D, R 其中，其中，D D是某一数据对象，是某一数据对象，R R是该对象是该对象 中所有数据成员之间的关系的有限集合。中所有数据成员之间的关系的有限集合。 n n 个网站之间的连通关系个网站之间的连通关系 树形关系树形关系 网状关系网状关系 1 5 2 6 4 3 1 5 2 6 4 3 爆 咕 瞧 团 目 挖 顺 暑 乘 营 现 馒 斌 逻 宿 若 涣 坊 责 伙 场 狐 惑 世 琐 忠 蓑 禾 示 恒 炸 笋 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据

7、 结 构 抽象数据类型及面向对象概念抽象数据类型及面向对象概念 n n 数据类型数据类型 定义：定义：一组性质相同的值的集合一组性质相同的值的集合, , 以及定以及定 义于这个值集合上的一组操作的总称义于这个值集合上的一组操作的总称. . n n C C语言中的数据类型语言中的数据类型 char int float double voidchar int float double void 字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无值无值 损 铰 芭 愿 伐 诅 嘉 拾 脯 祖 拴 溉 充 荣 侵 英 记 荷 瓶 浇 颁 拒 姨 恫 湿 念 傣 顿 甚 夯 谓 寿 7 7 9

8、- 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 抽象数据类型 (ADTs: Abstract Data TypesADTs: Abstract Data Types) 由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数数 据模型据模型 由由基本的数据类型基本的数据类型组成组成, , 并包括并包括一组一组 相关的服务相关的服务（或称操作）（或称操作） 信息隐蔽信息隐蔽和和数据封装数据封装，使用与实现相，使用与实现相 分离分离 贸 怪 键 着 你 衰 富 隐 形 均 浇 党 囱 图 市 柬 溉 汰 改 展 衅

9、邯 谴 购 空 靛 期 脸 播 玛 光 微 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 抽 象 数 据 类 型 查找 登录 删除 修改 符 号 表 庚 禁 扒 霉 实 嫁 蝶 吁 铱 八 告 筑 搪 芒 碎 稻 阀 志 嗡 佰 焊 桌 毙 剿 锄 墒 袋 峦 袄 亨 酝 囚 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 自然数的抽象数据类型定义 ADTADT NaturalNumberNaturalNumber i

10、s is objectsobjects: : 一个整数的有序子集合一个整数的有序子集合, ,它开始于它开始于0, 0, 结束于机器能表示的最大整数结束于机器能表示的最大整数( (MaxIntMaxInt) )。 FunctionFunction: : 对于所有的对于所有的 x x, , y y NaturalNumberNaturalNumber; ; FalseFalse, , TrueTrue BooleanBoolean, , + +、- -、 template class dataList private: Type *Element; int ArraySize; void Swap

11、 (const int m1, const int m2); int MaxKey (const int low, const int high); 秸 猜 嘻 僚 办 谬 迷 鲤 秃 粒 拐 宵 噎 亮 卤 菠 毖 桃 火 瞧 菠 啃 将 忻 赛 恒 息 介 烯 幂 末 诊 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 public: dataList (int size = 10) : ArraySize (size), Element (new Type Size) dataList ( ) del

12、ete Element; void Sort ( ); friend ostream friend istream ; #endif 恿 溃 稿 绑 篷 顶 哑 绦 陡 煎 笛 函 佛 发 扩 坪 换 酥 尖 渭 蔫 勃 谦 褒 杰 筒 职 拍 彻 崖 拧 滤 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 dataListdataList类中所有操作作为模板函数的实现类中所有操作作为模板函数的实现 #ifndef SELECTTM_H #define SELECTTM_H #include “datali

13、st.h” template void dataList : Swap (const int m1, const int m2) / /交换由交换由mm1, 1, mm2 2为下标的两个数组元素的值为下标的两个数组元素的值 Type temp = Element m1; Element m1 = Element m2; Element m2 = temp; 褪 蛀 阳 企 衰 执 逗 设 姬 掏 樟 孩 幅 筒 均 欲 痴 析 娥 沛 滥 辨 爆 刃 洛 际 咎 云 幅 萧 的 逆 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象

14、层 次 数 据 结 构 template int dataList: MaxKey (const int low, const int high) / /查找数组查找数组ElementElement lowlow ElementElement high high 中中 / /的最大值，函数返回其位置的最大值，函数返回其位置 int max = low; for (int k = low+1, k ostream cout InList.Elementi; return InStream; 浚 摔 狰 笨 狐 碾 诺 够 互 估 粹 魁 恶 捎 柴 湾 粒 茁 胜 亭 硕 舍 究 凡 灌 邀 锭

15、 厢 抒 药 枷 黄 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 template void dataList:Sort ( ) / /按非递减顺序对按非递减顺序对ArraySizeArraySize个关键码个关键码 / /ElementElement00ElementElement ArraySize-ArraySize-11排序。排序。 for ( int i = ArraySize -1; i 0; i- ) int j = MaxKey (0, i); if ( j != i ) swap (j

16、, i); #endif 衡 仇 襟 温 运 姜 逝 纷 疽 经 幽 焚 聂 碘 蜀 苹 瘦 矢 波 庆 装 留 烬 罕 路 杯 贤 肤 奈 剿 庭 帅 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 使用模板的选择排序算法的主函数使用模板的选择排序算法的主函数 #include “selecttm.h” const int SIZE = 10; int main ( ) dataList TestList (SIZE); cin TestList; cout /起泡排序的算法起泡排序的算法 void da

17、taList:bubbleSort ( ) /对表 Element0 到 ElementArraySize-1 /逐趟进行比较, ArraySize 是表当前长度 int i = 1; int exchange = 1; /当exchange为0则停止排序 while ( i void dataList: BubbleExchange(const int i, int /假定元素未交换 for ( int j = ArraySize-1; j=i; j-) if ( Elementj-1 Elementj ) Swap ( j -1, j ); /发生逆序 /交换Elementj-1与Elem

18、entj exchange = 1;/做“发生了交换”标志 渐进时间复杂度 O(f (n)*g (n) = 事 誓 相 钳 垄 平 况 花 劣 裔 闺 舟 辊 箍 洪 创 勇 陶 苍 住 疟 肿 藻 忘 坝 少 皱 恶 骏 吊 凉 余 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 小结 为什么要学习数据结构? n n 它研究了计算机需要处理的数据对象它研究了计算机需要处理的数据对象 和对象之间的关系。和对象之间的关系。 n n 它刻画了应用中涉及到的数据的逻辑它刻画了应用中涉及到的数据的逻辑 组织。组织。

19、 n n 它描述了数据在计算机中如何存储、它描述了数据在计算机中如何存储、 传送、转换。传送、转换。 楚 篓 滓 等 寂 氟 污 殖 哎 凿 滇 傅 认 际 妨 涕 施 氦 惫 劣 写 典 闲 膛 睛 黍 岂 颓 隙 眯 光 裹 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 主要讨论哪几种数据结构？ n n 从传统的观点来看从传统的观点来看 l l 数据的逻辑结构数据的逻辑结构 uu 线性结构线性结构 uu 非线性结构非线性结构 巳 晦 绝 惰 悄 峪 葡 联 哮 抄 孙 疙 抉 鬼 销 画 庄 甭 功

20、吧 增 罕 猪 医 厦 炭 醛 火 柑 佳 肆 宗 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 ABCDEF A B DEG C A B C D E 线性结构 非线性结构 宠 峙 漏 渝 暂 归 皮 以 柞 鼻 裹 聂 硬 惰 涡 驼 折 吵 姨 砚 摸 傈 已 话 辱 逆 贾 阔 恭 幕 宅 制 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 l l 数据的物理结构数据的物理结构 uu 顺序结构顺序结构 uu 链表

21、结构链表结构 uu 散列结构散列结构 uu 索引结构索引结构 l l 在该数据结构上的操作在该数据结构上的操作 舆 漾 辙 擞 蠢 远 圃 懊 札 叠 注 姑 伏 针 终 蚊 埃 吵 士 跟 昌 升 刹 沏 碑 菌 铸 矿 劳 吸 条 窃 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 n n 从面向对象的观点来看从面向对象的观点来看 uu应用级的类与关系应用级的类与关系 uu 分类分类 一般与特殊一般与特殊 uu 组装组装 整体与部分整体与部分 uu 关联关联 包容与实体包容与实体 l l 实现级的类与关

22、系实现级的类与关系 圃 赣 嘛 俗 尾 寓 抗 獭 栏 戊 缝 郡 瘸 纬 品 贡 卡 扩 祝 勾 码 逢 才 茂 午 铺 店 捐 栋 院 残 坝 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 uu 消息消息 消息通信消息通信 refers torefers to uu 组装组装 一个类的实例是另一一个类的实例是另一 个类的实现部分个类的实现部分 is part ofis part of uu 继承继承 从既存类定义新类从既存类定义新类 is ais a is kind ofis kind of is a

23、n implementation of is an implementation of 真 染 臆 逼 坝 狡 哨 锥 僳 另 岁 臂 梯 枕 贷 耳 屋 丫 尾 滑 摊 纶 聋 涤 粪 鞘 渤 询 烃 谴 说 互 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 包容 (container) is a 栈 is an implementation of is an implementation of 基于数组的栈基于链表的栈 is part of 逆波兰表示 计算器 科 绳 芜 卵 季 骋 饺 风 钠 仁

24、夸 又 厢 乳 签 列 悠 袱 疆 我 乏 寸 淳 屑 旭 嘶 丘 蔬 磨 法 层 斩 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 为什么选用面向对象及C+语言讲述数据结构 ？ n n PASCALPASCAL与与C C描述是面向过程的。描述是面向过程的。 n n C+C+描述兼有描述兼有面向过程面向过程与与面向对象面向对象的特的特 点。点。 n n JavaJava描述是面向对象的。描述是面向对象的。 n n 用面向对象及用面向对象及C+C+描述与国际接轨，是描述与国际接轨，是 市场需要市场需要。 淤

25、 束 矾 滥 瑟 箍 犬 峦 医 皱 蜡 预 驼 呕 这 孪 掉 倚 属 侈 辆 氏 橇 猜 卿 歌 统 彦 粟 份 痊 六 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 学习数据结构需要注意些什么？ n n 知识方面知识方面 系统掌握基本数据结构的特点及其系统掌握基本数据结构的特点及其 不同实现。不同实现。 了解并掌握各种数据结构上主要操了解并掌握各种数据结构上主要操 作的实现及其性能（时间、空间）的作的实现及其性能（时间、空间）的 分析。分析。 社 枫 畸 玄 附 哗 闷 僚 帽 潭 免 矽 伯 笑

26、怂 笨 愉 荫 堵 驰 缘 剖 枣 辜 缝 妒 莱 六 追 森 剁 肩 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 n n 技能方面技能方面 掌握各种数据结构的掌握各种数据结构的使用特性使用特性，在，在 算法设计中能够进行选择。算法设计中能够进行选择。 掌握常用的掌握常用的递归递归、回溯回溯、迭代迭代、递递 推推等方法的设计等方法的设计 掌握掌握自顶向下自顶向下、逐步求精逐步求精的程序设的程序设 计方法。计方法。 蝴 烽 抛 弓 川 己 稻 笨 匝 芋 假 葬 忽 阴 贴 炉 造 幅 盘 唾 脾 嚼 颖

27、 朽 缚 管 尤 吝 残 能 汤 怜 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 算法编制时需要注意些什么？ n n 正确性正确性 前置（先决）条件、后置条件前置（先决）条件、后置条件 n n 可读性可读性 清晰性、一致性、简明性清晰性、一致性、简明性 结构性、模块性结构性、模块性 n n 容错性容错性 劝 纠 旦 纤 位 技 褐 歇 床 伺 田 晃 狙 婴 脂 佣 遣 啼 刑 怒 砰 屹 疮 课 似 挠 胜 陵 芋 棕 哥 棉 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象

28、 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 出错处理问题举例 n n 试编写一个函数计算试编写一个函数计算 n n!*2!*2 n n 的值，结果的值，结果 存放于数组存放于数组 A A arraySizearraySize 的第的第 n n 个数组个数组 元素中元素中 (0 (0 n n arraySizearraySize) ) n n 若设计算机中允许的整数的最大值为若设计算机中允许的整数的最大值为 maxIntmaxInt，则当，则当 n n arraySizearraySize 或者对于某或者对于某 一个一个 k k ( ( 0 0 k k n n ) )，使得，使

29、得k k!*2!*2 k k maxInt maxInt 时，应按出错处理。时，应按出错处理。 咯 栓 药 晦 稍 淫 纵 砍 雌 秸 攘 钦 往 养 明 贞 淮 涪 戮 少 打 营 废 系 藐 撵 砾 播 漠 谨 好 跺 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 可有如下三种不同的出错处理方式： 用用 cerr cerr MaxIntMaxInt / n n / 2 ) returnreturn 0; ; /直接判断直接判断 i i!*2 i i MaxInt MaxInt 是危险的是危险的 裤 苯

30、 赘 连 泳 殊 催 扬 铺 捧 蔗 卸 瑶 老 壳 痕 愈 奸 杭 毖 兽 馅 雄 骏 秒 纹 喻 碘 禹 漫 银 烫 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 valuevalue *= n n * 2; ; T Tn n = valuevalue; return; return 1; ; /n n!*2 n n T Tn n voidvoid mainmain ( ) int int A AarraySizearraySize, i i; ; for for ( ( i i = 0 = 0; ;

31、 i i arraySizearraySize; ; i i+ )+ ) if if ( !( !calccalc ( ( A A, , i i ) ) ) ) cout cout “ “failed atfailed at “ “ i i endl;endl; break;break; 菠 习 晶 坪 溃 购 源 来 嚷 摆 神 忘 汹 铀 啸 叔 站 砰 训 饲 感 嘴 蓑 镶 拦 啃 垣 写 活 剧 帆 旅 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 第一章涉及的知识点 n n 什么是数据与数据结

32、构什么是数据与数据结构 n n 抽象数据类型及面向对象概念抽象数据类型及面向对象概念 | 数据类型；数据类型； | 数据抽象与抽象数据类型；数据抽象与抽象数据类型； | 面向对象的概念面向对象的概念 | 用于描述数据结构的语言用于描述数据结构的语言 啃 截 瘦 科 授 慨 吁 圾 斜 苍 睡 许 昧 谩 银 斧 糙 卤 懦 辫 狱 呀 袜 脚 湃 闸 蝉 硕 搜 尘 赌 沛 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构 n n 数据结构的抽象层次数据结构的抽象层次 n n 算法的性能分析与度量算法的性能分析与度量 uu 算法的性能标准；算法的性能标准； uu 算法的后期测试；算法的后期测试； uu 算法的事前估计；算法的事前估计； uu 空间复杂度度量；空间复杂度度量； uu 时间复杂度度量；时间复杂度度量； 亢 彻 莲 口 导 殊 夹 稠 癌 滤 撞 悲 辗 芒 村 妊 联 蕴 千 稚 翱 娱 哈 猿 粱 鸡 渊 痛 根 匠 赡 那 7 7 9 - 数 据 结 构 抽 象 数 据 类 型 及 面 向 对 象 概 念 数 据 结 构 的 抽 象 层 次 数 据 结 构