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