数据结构课件第1章.ppt

数据结构 C语言版 课时安排 专业必修 4 5学分总学时 70小时上课 54小时试验 16小时考试 成绩计算 平时成绩 30 考勤 课堂表现 作业 上机实验报告 上机考察考试成绩 70 要求 上机不能做与该课程无关的内容 注意 无故缺勤或上机时间玩游戏等第1次平时成绩扣5分 第2次扣10分 第3次扣15分 第4次扣20分 第5次扣30分 第6次平时成绩为0 教材与参考书 教材 苏德富 数据结构 C语言 重庆大学出版社参考书 严蔚敏 数据结构 清华大学出版社李勤 数据结构 中国电力出版社CliffordA Shaffer 数据结构与算法分析 电子工业出版社 课程重要性简介 是计算机相关专业考研的重点内容 大公司笔试的主要内容 是计算机专业核心必修课 是其它后续计算机课程的重要基础 是非计算机专业的主要选修课 数据结构在学科中的地位 数据结构 是计算机科学中一门综合性的专业基础课 数据结构的研究不仅涉及计算机的硬件的研究范围 而且和计算机软件的研究有着更为密切的关系 无论是编译程序还是操作系统 都涉及数据元素在存储器中的分配问题 可以认为数据结构是介于数学 计算机硬件 计算机软件三者之间的一门核心课程 数据结构 所处的地位 课程主要内容简介 数据的逻辑结构 数据的存储结构 顺序与链式 及其操作 算法 插入 删除与遍历等 线性表 树和图 查找与排序 属常用算法总结 算法的时空效率分析法 本课程章节主要内容第一章 绪论第二章 线性表和数组第三章 栈和队列第四章 串第五章 树和二叉树第六章 图第七章 排序第八章 查找第九章 文件 第一章绪论 数据结构的引论 例1图书馆的书目检索系统自动化问题 线形数据结构 1 1的关系在书目自动检索系统中可以建立一张按登录顺序号排列的书目文件和三张分别按书名 作者名和分类号顺序排列的索引表 如下所示 什么是数据结构 书目卡片 特点 计算机按某个特定的要求进行查询 处理对象之间存在一种简单的线形关系 这类模型可以称为简单的线形数据结构 按书名排列 按作者排列 按索引号排列 例2计算机和人的对弈问题 树 形数据结构 1 N的关系 对奕的过程是在一定的规则下随机进行的 因此 计算机必须对对弈过程之中可能发生的情况以及相应的对策都考虑周全 这个关系不是线形的 从一个棋盘可以派生出几个格局 如下图 树根 是对奕开始之前的棋盘格局 而所有的 叶子 是可能出现的结局 对奕的过程就是从树根沿树叉到达某个叶子的过程 例3多叉路口交通灯的管理问题 图 形数据结构 M N的关系 可以把这类交通 道路的问题当作一种 图 的结构 一个顶点表示一条通道 而通道之间的矛盾的关系以两个顶点之间的连线表示 如下图所示 结论 综合上面三个例子 描述这类非数值计算性问题的数学模型不再是数学方程 而是诸如表 树和图之类的数据结构 数据结构 数据结构是一门非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 数据 Data 客观事物的符号表示 能输入到计算机中并被计算机中程序处理的符号的总称 数据元素 Dataelement 数据的基本单位 可由数据项组成 数据类型 DataType 是一个值的集合和定义在这个值集上的一组操作的总称 如 int数据类型 取值范围为 32768 32767 操作运算有加 减 乘 除 取模 乘方等 基本概念 数据对象 DataObject 性质相同的数据元素的集合 是数据的子集 数据结构 DataStructure 相互之间存在一种或多种特定关系的数据元素的集合 数据元素之间的相互关系称为结构 有下列四种基本结构 1 集合 2 线形结构 3 树形结构 4 图状结构 网状结构 数据结构DS的形式定义 数据结构是一个二元组 DS K R 其中 K是数据元素的有限集R是数据元素之间关系的有限集对于R中任意二元关系 x y K 称x为第一元素 或y的前驱 y为第二元素 或x的后继 数据元素之间的相互关系 数据元素之间的相互关系包括三个方面 数据的逻辑结构 存储结构 操作集合 数据元素之间的逻辑关系 称为数据的逻辑结构 数据的逻辑结构分两大类 线性结构 线性表 栈 队列 字符串 数组 广义表 非线性结构 树 二叉树 图 数据元素之间的关系在计算机中的表示 有顺序映象和非顺序映象两种方法 由此得到两种存储结构 顺序存储结构 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系 链式存储结构 借助指示元素存储地址的指针表示数据元素之间的逻辑关系 数据结构在计算机中的表示 称为数据的物理结构 存储结构 逻辑结构是面向用户的 是抽象的 存储结构是面向计算机的 面向实现的 数据操作描述 数据的基本操作 插入 在数据结构的指定位置添加新的数据元素 删除 去掉数据结构中某个指定的数据元素 更新 改变数据结构中某个数据元素的值 查找 在数据结构中寻找某个满足特定要求的数据元素 排序 重新安排数据元素的逻辑顺序关系 使其值按从小到大或从大到小的顺序排列 从操作的特性分 所有的操作可以归结为两类 加工型操作 操作改变了 操作之前的 结构的值 引用型操作 不改变值 只是查询或求得结构的值 算法 是对特定问题求解步骤的一种描述 是指令的有限序列 什么是算法 算法的五个特征 1 输入 可有0个或多个输入 2 输出 至少有1个或多个输出 3 确定性 算法中每一步骤必须有确切含义 无二义性 4 有限性 能够在有限步骤内结束 不能形成无限循环 5 有效性 算法可以在纸上作业方式跟踪其结果 算法设计的要求 1 正确性 当输入数据合法时 能够得到满足要求的结果 2 可读性 算法简单明了 便于别人对算法的理解和对程序的维护 3 低存储规模 存储规模是指算法在执行过程中所需的最大存储空间 也称为算法的空间复杂性 4 高效率 执行时间短的算法其效率就高 算法的执行时间也称为算法的时间复杂性 算法与程序的区别 计算机科学家N 沃思给出一个著名公式 数据结构 算法 程序1 程序是在特定计算机上执行的算法 是具体的 而算法与具体计算机无关 是抽象的 2 程序可以不满足有限性要求 而算法必须满足有限性 如 操作系统程序 除非关机 否则一直在等待循环中等待下一个工作进入系统 所以只要系统是在运作下 则操作系统程序就不会终止 算法效率需通过该算法编制的程序在计算机上运行所消耗的时间多少以及所需辅助空间的大小来度量 算法效率的度量 算法效率的衡量指标 时间复杂度和空间复杂度 时间复杂度 从算法中选取一个对于所研究的问题来说是基本操作的原操作 指固有数据类型的操作 以该基本操作重复执行的次数作为算法的时间量度 计作 T n O f n 它表示随着n的增大 算法执行时间的增长率和f n 的增长率相同 空间复杂度 一个上机执行的程序除了需要存储空间来积存本身所用指令 常数 变量和输入数据外 也需要一些对数据进行操作的工作单元和存储一些实现计算所需信息的辅助空间 该辅助空间的大小及反映了该算法的空间复杂性 计作 S n O f n 频度 某语句重复执行的次数 程序段一 x s 0 该程序中 x 是基本操作语句 其频度为1 其时间复杂度为O 1 为常量阶 例 求下面程序的时间复杂度 程序段二 for i 1 i n i x s x 该程序中 x 是基本操作语句 其频度为n 其时间复杂度为O n 为线性阶 程序段三 for j 1 j n j for k 1 k n k x s x 该程序中 x 是基本操作语句 其频度为n2 其时间复杂度为O n2 为平方阶 程序段四 for i 2 i n i for j 2 j i 1 j x a i j x 语句 x 的执行次数关于n的增长率为n2 它是语句频度表达式 n 1 n 2 2中增长最快的项 时间复杂度为O n2 i 2 执行0次 i 3 执行1次 i 4 执行2次 i n 执行n 2次 总共执行次数 1 2 3 n 2 n 2 n 2 1 2 n 2 n 1 2 n2 3n 2 2 常见的几种时间复杂度数量级 一般情况下 随着n的增大 T n 增长较慢的算法为最优的算法 应该选择对数阶或多项式阶的算法 避免使用指数阶的算法 衡量两个算法的好坏 应当是在n足够大的情形下 对算法的工作量进行比较 即对算法进行渐近性态分析 n较小时难辨优劣 算法的阶 设非负函数f n 和g n n N 如果存在正常数c和正整数n0 使得当n n0时 有f n cg n 则称f n 的阶小于或等于g n 的阶 记为f n O g n 读作f n 是g n 的大O 一般采用求极限的方法 来比较两个算法时间复杂性函数的阶 当n 时 limf n g n c 1 当c 0 f n 比g n 低阶 记为f n O g n 2 当c 0 f n 和g n 同阶 记为f n g n 3 当c f n 比g n 高阶 记为f n g n 算法的阶 算法的阶 例如 2n 5 O n2 因为当n 时 lim 2n 5 n2 2 n 5 n2 0 0 0