计算机二级数据结构与算法ppt课件.ppt

1 计算机教研室 全国计算机等级考试二级公共基础知识 2 1 基本数据结构与算法 3 1 1算法 1 1 1算法 algorithm 基本概念对特定问题求解步骤的一种描述 它是指令的有限序列 其中每一条指令表示一个或多个操作 它是一组严谨地定义运算顺序的规则 并且每一个规则都是有效的 且是明确的 此顺序将在有限的次数下终止 4 算法的基本特征 可行性确定性有穷性拥有足够的情报输入和输出 5 算法的基本要素1 对数据对象的运算和操作算术运算 加 减 乘 除等运算逻辑运算 与 或 非 等运算关系运算 大于 等于 等运算数据传输 赋值 输入 输出等运算 6 算法的基本要素2 算法的控制结构算法中各操作之间的执行顺序描述算法的工具通常有传统流程图 N S结构化流程图 算法描述语言等一个算法一般可以用顺序 选择 循环三种基本机构组合而成 7 算法设计基本方法列举法归纳法递推递归 以简洁的形式设计和描述算法 减半递推技术回溯法 8 1 1 2算法复杂度 时间复杂度是指执行算法所需要的计算工作量 一般用算法在执行过程中所需要的基本运算的执行次数来度量算法的工作量 算法中基本运算执行次数和问题的规模有关 算法的工作量 f n 有时在固定规模下 基本运算执行次数还和具体输入有关 9 平均性态最坏情况复杂性 X出现的概率 算法在输入x时所执行的基本运算次数 规模为n时 算法执行时所有可输入的集合 10 算法的空间复杂度一般是指执行这个算法所需要的内存空间一个算法所占用的存储空间包括算法程序所占的空间 输入的初始数据所占的存储空间以及某种数据结构所需要的附加存储空间一个上机执行的程序除了需要存储空间来寄存本身所用指令 常数 变量和输入数据外 也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间 11 1 2数据结构 数据结构的定义数据的逻辑结构和存储结构数据结构的图形表示线性结构与非线性结构 12 1 2 1数据结构研究的主要内容 当今计算机应用的特点 所处理的数据量大且具有一定的关系 对其操作不再是单纯的数值计算 而更多地是需要对其进行组织 管理和检索 13 应用举例 学籍档案管理 假设用计算机管理学生档案 研究对象为 学生 常用操作查找 删除 修改 插入等一个学籍档案管理系统应包含如下表1 1所示的学生信息 14 15 特点 每个学生的信息占据一行 所有学生的信息按学号顺序依次排列构成一张表格 表中每个学生的信息依据学号的顺序存在着一种前后关系 这就是我们所说的线性结构 对它的操作通常是插入某个学生的信息 删除某个学生的信息 更新某个学生的信息 按条件检索某个学生的信息等等 16 数据结构是一门研究数据组织 存储和运算的一般方法的学科 1 2 2基本概念和术语 数据结构主要研究和讨论以下三个方面的问题 1 数据集合中各数据元素之间所固有的逻辑关系 即数据的逻辑结构 2 在对数据进行处理时 各数据元素在计算机中的存储关系 即数据的存储结构 3 对各种数据结构进行的运算 位置 P6 重要 17 能输入到计算机中并能被计算机程序处理的符号的集合 整数 1 2 实数 1 1 1 2 字符串 Beijing 图形 声音 1 2 2基本概念和术语 数据结构是一门研究数据组织 存储和运算的一般方法的学科 18 1 2 2基本概念和术语 计算机管理图书问题在图书馆里有各种卡片 有按书名编排的 有按作者编排的 有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短 又要考虑节省空间 数据结构是一门研究数据组织 存储和运算的一般方法的学科 19 最简单的办法之一是建立一张表 每一本书的信息在表中占一行 如 1 2 2基本概念和术语 数据结构是一门研究数据组织 存储和运算的一般方法的学科 20 将各种逻辑结构的数据存放在计算机存储空间中 目的不同 最佳的存储方方法就不同 数据元素在计算机中的表示 数据结构是一门研究数据组织 存储和运算的一般方法的学科 1 2 2基本概念和术语 21 对数据结构中的节点进行操作处理 插入 删除 修改 查找 排序 1 2 2基本概念和术语 数据结构是一门研究数据组织 存储和运算的一般方法的学科 22 数据元素 DataElement 现实世界中客观存在得一切个体或个体相关的操作都可以抽象为数据元素 如 四季的名称 春 夏 秋 冬由季节抽象而来 可以作为季节的数据元素 同理 父亲 儿子 女儿可以作为家庭成员的数据元素 简单的说 数据结构是指相互有关联的数据元素的集合 23 数据元素 DataElement 甚至客观存在的事件 如演出 借书 比赛等也可以抽象为数据元素 在具有相同特征的数据元素集合中 各个数据元素之间存在某种关系 这种关系反映了该集合中的数据元素所固有的一种结构 在数据处理领域中 通常把数据元素之间的这种固有的关系简单地用前后件关系来描述 24 数据的逻辑结构 表示数据元素的信息表示数据元素之间的前后件关系 数据逻辑结构通常用二元组表示数据逻辑结构也可用图形表示 25 数据逻辑结构可表示为 B D R B表示数据结构D表示数据元素的集合R表示数据元素间前后件关系 为反映前后件关系 通常用二元组 a b 来表示 它表示a是b的前件 26 B D R D 父亲 儿子 女儿 R 父亲 儿子 父亲 女儿 B D R D 春 夏 秋 冬 R 春 夏 夏 秋 秋 冬 27 数据结构的图形表示 28 数据的存储结构 数据的逻辑结构在计算机存储空间的表示 各数据元素在计算机存储空间中的位置与逻辑关系不一定相同 常用的存储结构有 顺序 链接 索引等 29 数据的存储结构 字节 30 二级公共基础05年4月试题 1 数据的存储结构是指A 存储在外存中的数据B 数据所占的存储空间量C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示 31 线性结构与非线性结构 有且只有一个根结点 没有前件的结点 每一个结点最多只有一个前件 也最多只有一个后件 32 线性结构 A B C X Y Z 学生成绩表 线性表 结点间是以线性关系联结 33 非线性结构 如果数据结构不满足线性结构的条件 则称之为非线性结构 此外 在线线结构中插入或删除一个结点 还应是线线结构 否则此结构非线线 34 树形结构 全校学生档案管理的组织方式 计算机程序管理系统也是典型的树形结构 35 树形结构 结点间具有分层次的连接关系 36 1 3线性表 1 3 1线性表的定义线性表是n个元素的有限序列 它们之间的关系可以排成一个线性序列 a1 a2 ai an其中n称作表的长度 当n 0时 称作空表 37 线性表的特点 1 线性表中所有元素的性质相同 2 除第一个和最后一个数据元素之外 其它数据元素有且仅有一个前件和一个后件 第一个数据元素无前件 最后一个数据元素无后件 3 数据元素在表中的位置只取决于它自身的序号 在线性表上常用的运算有 初始化 求长度 取元素 修改 前插 删除 检索 排序 38 1 3 2线性表的顺序存储结构 线性表顺序存储结构的特点 1 线性表所有元素所占的存储空间是连续的 2 线性表各数据元素在存储空间中是按逻辑顺序依次存放的 在计算机中存放线性表 采用顺序存储是一种简单方便的方法 39 元素an 元素ai 元素a2 元素a1 b ADR a1 k 存储地址 内存状态 顺序存储结构示意图 顺序表 首地址ADR a1 每个元素所占用的存储单元个数 ADR a1 i 1 k ADR a1 n 1 k ADR ai ADR a1 i 1 k 40 n 1 线性表的插入和删除运算示意图 ai 1 a2 a1 an ai 1 ai x x 删除运算 插入运算 41 若长度为n的线性表表示为 a1 a2 ai an 运算后表示为 a 1 a 2 a i a n 则满足以下关系 插入新元素b后 删除第i个元素后 42 1 4栈和队列 1 4 1栈和队列的定义栈和队列是两种特殊的线性表 它们是运算时要受到某些限制的线性表 故也称为限定性的数据结构 43 1 4 1 1栈的定义栈 限定只能在表的一端进行插入和删除的特殊的线性表 此种结构称为先进后出 FILO 或后进先出 LIFO 设栈s a1 a2 ai an 其中a1是栈底元素 an是栈顶元素 栈顶 top 允许插入和删除的一端 栈底 bottom 不允许插入和删除的一端 约定用指针top始终指向栈顶的位置 用指针bottom指向栈底 n 1 44 1 4 2栈的顺序存储结构及其基本运算 用顺序存储结构表示的栈 顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素 一般用一维数组表示 设置一个简单变量top指示栈顶位置 称为栈顶指针 它始终指向待插入元素的位置 基本运算 压 进 栈 PUSH出栈 POP读栈顶元素 45 进栈示例 栈满 栈顶指针指向存储空间的最后一个位置 46 退栈示例 47 1 4 1 2队列 Queue 的定义定义 一种特殊的线性结构 限定只能在表的一端进行插入 在表的另一端进行删除的线性表 a1 a2 a3 a4 an 1 an 队列示意图 队头 队尾 队列只允许在队尾插入 在对头删除 队头指针 front 指向排头元素的前一个位置队尾指针 rear 指向队尾元素此种结构称为先进先出 FIFO 或后进后出 LILO 48 队列的主要运算 1 插入一个新的队尾元素 称为进队 2 删除队头元素 称为出队 3 读取队头元素 当有新元素入队时 尾指针加1 当有元素出队时 头指针加1 故在非空队列中 头指针始终指向队头元素前一个位置 而尾指针始终指向队尾元素的位置 49 队列的进队和出队 进队时队尾指针先进一rear rear 1 再将新元素按rear指示位置加入 出队时队头指针先进一front front 1 再将下标为front的元素取出 队满时再进队将溢出出错 队空时再出队将队空处理 队满 队尾指针指向存储空间的最后一个位置 50 定义 存储队列的线型空间被模拟为首尾相接的环形空间处理 循环队列 长度为m 的的性质 循环队列的初始状态 front rear m队头 队尾指针加1时若结果等于m 1置为1 循环队列 CircularQueue 51 52 Q 1 6 A E C D B F 53 队空时 front rear 队满时 front rear由于队满和对空的条件一样 无法判断循环队列的状态 所以增加了一个标志s s的定义如下 P19 20详细说明 54 1 5链表 线性链表 线性链表节点 55 1 5 1线性表的链式存储结构 将线性表的元素放到一个具有头指针的链表中 链表中每个结点包含数据域和指针域 数据域存放数据 指针域存放后继结点的地址 最后一个结点的指针域为空 逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻 56 上图的线性表为ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 57 线性链表表示法 0 58 双向链表在每个结点中设置两个指针 一个指向后继 一个指向前驱 可直接确定一个结点的前驱和后继结点 可提高效率 59 链式存储结构的特点 插入 删除灵活方便 不需要移动结点 只要改变结点中指针域的值即可 适合于线性表是动态变化的 不进行频繁查找操作 但经常进行插入删除时使用 链表的查找只能从头指针开始顺序查找 60 H H 线性链表的插入运算 S 在H所指向的结点之后插入新的结点 1 5 2线性链表的运算 61 H 线性链表的删除运算 S 在H所指向的结点之后删除新的结点 1 5 2线性链表的运算 H S 62 栈的链接表示 链式栈 链式栈无栈满问题 空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头 0 63 队列的链接表示 链式队列 队头在链头 队尾在链尾 链式队列在进队时无队满问题 但有队空问题 队空条件为front NULL 0 64 1 5 3循环链表 首尾相接的链表 将最后一个结点的空指针改为指向头结点 从任一结点出发均可找到其它结点 L 带头结点的线性链表 L 循环线性链表 65 元素n 元素i 元素2 元素1 存储内容 缺点 1 作插入或删除操作时 需移动大量元素 2 长度变化较大时 需按最大空间分配 3 表的容量难以扩充 优点 1 结构简单 节省存储空间 2 可随机定位其中的元素 线性表顺序存储 66 1536 元素2 1400 元素1 1346 元素3