清华大学数据结构.ppt

1 第一章 数据结构 概论 数据结构电子教案 殷人昆 王宏 2 n n 什么是数据结构什么是数据结构 n n 抽象数据类型及面向对象概念抽象数据类型及面向对象概念 n n 算法定义算法定义 n n 算法简单性能分析与度量算法简单性能分析与度量 第一章 数据结构概论 3 示例示例 “学生学生” ”表格表格 4 “ “课程课程” ”表格表格 5 学生 (学号,姓名,性别,籍贯) 课程 (课程号,课程名,学分) 选课 (学号,课程号,成绩) “ “选课单选课单” ”包含如下信息包含如下信息 学号学号 课程编号课程编号 成绩成绩 时间时间 学生选课系统中实体构成的学生选课系统中实体构成的网状关系网状关系 6 UNIX文件系统的结构图(层次结构) / (root) binlibuseretc mathdsswyinwh jia stack.cppqueue.cpptree.cpp 7 数据（Data） n数据是信息的载体，是描述客观事物的数、 字符、以及所有能输入到计算机中并被计算 机程序识别和处理的符号的集合。 n数据的分类： u 数值型数据（整数、浮点数、双精度数 ） u 非数值型数据（字符、文字、语音、图 形、图像） 8 姓名 学号性别出生年月 年 月 籍贯 所在 院系 数据元素 (Data Element) n数据的基本单位是数据元素 。在计算机 程序中常作为一个整体进行考虑和处理。 n有时一个数据元素可以由若干数据项 (data item)组成。数据项是具有独立含义的最小 标识单位（初等项与组合项）。 n数据元素又称为元素、结点、记录。 9 数据元素之间通常不是孤立的，它 们往往存在这样或那样的关系，数据元 素之间的这种关系称为结构。 例：N 个顶点之间的连通关系 树形关系树形关系网状关系网状关系 1 5 6 1 5 2 4 36 2 4 3 10 什么是数据结构 u 由某一数据元素的集合以及该集合中所有 数据元素之间的关系组成。记为： Data_Structure = D, R 其中，D 是某一数据元素的集合，R 是该集 合中所有数据元素之间的关系的有限集合。 uu 数据结构描述的是按照一定逻辑关系组织数据结构描述的是按照一定逻辑关系组织 起来的待处理数据元素的表示及相关操作，涉起来的待处理数据元素的表示及相关操作，涉 及数据的逻辑结构、存储结构和数据的运算。及数据的逻辑结构、存储结构和数据的运算。 11 数据结构反映数据的组织形式 n包括三个方面： u数据元素间的逻辑关系，即数据的逻辑结 构； u数据元素及其关系在计算机存储内的表示 ，即数据的存储表示 (存储结构)； u数据的运算，即对数据元素施加的操作。 12 数据的逻辑结构分类 数据的基本逻辑结构 1. 线性结构 1 (除始结点与终结点外，每个结点有唯一的前驱和后继) 2. 非线性结构 * 层次结构 树结构 2 (除根外每个结点有唯一的前驱，但后继不加限制) * 群结构（元素同属于一个集合，但无顺序关系） 图结构与网络结构 3 (结点的前驱与后继数目均无限制) 13 线性结构 层次结构 树形结构 树多叉树 二叉树 bindevetclib user 14131211 234 56789103 15 8 7 10 11 9 987 456 62313 1 1 14 堆结构 一种特殊的树结构 “最大最大”堆堆 “最小最小”堆堆 12 3548 7 11 10 2 9 16 4 10 1211 5 1 2 36 98 7 15 图结构 网络结构 12 54 3 6 11 33 18 14 6 6 5 16 19 21 12 5 6 3 4 16 数据的存储结构 n数据的存储结构是各种逻辑结构在计算机中 的物理存储表示； n建立一种由逻辑结构到物理存储空间的映射 n数据的4种存储结构（依赖于计算机语言） u 顺序存储 u 链接存储 u 索引存储 u 散列存储 主要用于内存数据 的存储表示 主要用于外存 (文件 ) 的存储表示 17 数据的四种存储结构 n顺序存储 逻辑上相邻的元素存放在物理位置相邻的存储单元中 n链接存储 元素之间的逻辑关系由附加的指针指示 n索引存储 在存储元素信息的同时建立附加的索引表 n散列存储 根据结点的关键码通过一个散列函数计算得到存储地址 18 抽象数据类型及面向对象概念 n数据类型 数据类型是一组性质相同的值的集合, 以及定 义于这个值集合上的一组操作的总称。 n如在程序设计语言中，一个变量的数据类型不仅规定了 变量的取值范围，而且定义了该变量可用的操作。 n例：C语言中的基本数据类型 char int float double voidchar int float double void 字符型 整型 浮点型 双精度型 无值 19 n构造数据类型由基本数据类型或构造数据 类型组成，可由不同成分类型构成。 n基本数据类型可以看作是程序设计语言中 已实现的数据结构。 n数据类型本身就是数据结构，不过它是从 编程者的角度来使用的。 n数据类型是模板，必须定义属于某种数据 类型的变量，才能参加运算。 20 抽象数据类型 (ADTs: Abstract Data Types) n抽象：抽取反映问题本质的东西，忽略非本质的细节。 一旦一个抽象问题得到解决，则很多同类问题便可迎刃 而解。 n用户自定义数据类型即是对多种可能的结构和实现的一 种抽象。 nADT: 由用户自定义，用以表示应用问题的数据模型。 nADT由基本数据类型（或构造数据类型）组成, 并包括 一组相关的服务(或操作)。 n特点：将数据和操作封装在一起，用户程序只能通过ADT所定义的 操作来访问其中的数据，从而实现信息隐藏。 21 抽象数据类型的表示 n抽象数据类型可用三元组表示: （D, R, P） D 是数据元素的集合（简称数据对象） R 是 D上的关系集合， P 是对 D 的基本操作集合。 22 抽象数据类型举例 n例 复数是一种数据类型, 也是一种数据结构 Complex = (C, R) 其中：C 是含两个实数的集合c1, c2 。 R = rc rc是定义在集合 C上的一种关系 ， 有序偶表示c1是复数的实部， c2是复 数的虚部。 在Complex上再定义一些操作或运算，就构成 了它的抽象数据类型。 23 抽 象 数 据 类 型 查找 插入 删除 修改 符 号 表 24 抽象数据类型的描述 n其中数据对象、数据之间的关系用伪码描 述；基本操作定义格式为 ADT 抽象数据类型名 数据对象D：数据对象的定义 数据关系R：数据关系的定义 基本操作P：基本操作的定义 ADT 抽象数据类型名 基本操作名（参数表） 前置条件：先决条件描述 后置条件：操作结果描述 25 n基本操作有两种参数：赋值参数只为操作提 供输入值；引用参数以 False, True Boolean, +、-、 b n几点注意 一个函数增长率的上限与最小上限的区别 注意等式的单向性 53 n加法规则 针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m) n各种函数的增长趋势 c = i; j-) /n-i次比较 if (aj-1 aj) int tmp = aj-1; aj-1 = aj; aj = tmp; /一趟比较 61 渐进时间复杂度渐进时间复杂度 O(f (n)*g (n) = O(n2) BubbleSort 外层循环 n-1 趟 内层循环 n-i 次比较 62 n有时, 算法的时间复杂度不仅依赖于问题规 模 n，还与输入实例的初始排列有关。 n在数组 An 中查找给定值 k 的算法： int i = n-1; while (i = 0 return i; n算法的语句 i- 的频度不仅与 n 有关，还与 A 中各元素的取值以及 k 的取值有关。 63 n例：设有两个算法在同一机器上运行，其执 行时间分别为 100n2 和 2n，问：要使前者快 于后者，n 至少要取多大？ 解答： 问题是找出满足 100n2 2n = 8192 n = 14时，100n2 = 19600 2n = 16384 n = 15时，100n2 = 22500 2n = 32768 取 n = 15 满足要求。/渐进分析与某些常系数的影响 64 小结 n数据结构的概念与表示 n数据的基本逻辑结构与分类 n数据的四种基本存储结构 n抽象数据类型 n算法的定义与五种特性 n时间复杂度的渐进表示法 65 表示法 n大表示 当且仅当存在正常数c和n0, 使得T(n)c g(n) 对对所有 nn0都成立， 则称g(n) 给给出了T(n)的一个下界。记为 T(n) (g(n) 大表示法是对算法效率的一种乐观估计，对于 规模为n的任意输入，算法的运行时间都不会低于 (g(n)。 66 表示法 如果存在正常数 ab, n0, 和一个函数h(n) 使得对对所有 nn0 , 都有 ，