计算机软技术基础——数据结构概述PPT课件.ppt

计算机软件技术基础 教师 曾晓东电话 mail zengxiaodong 1 第一部分基本数据结构 第2章数据结构概述1学时第3章线性结构11学时3 1线性表7学时3 2栈和队列3学时3 3数组1学时第4章树6学时第6章查找和排序9学时 2 2020 3 21 可编辑 第2章数据结构概述 一 什么是数据结构二 有关数据结构的基本概念和术语三 算法四 算法描述语言和算法分析 3 2020 3 21 可编辑 第2章数据结构概述 一 什么是数据结构程序 算法 数据结构例 表达式解释6 5 4 字符串匹配串 ABCAC 出现在另一个串 ABCABCACAC 的第几个位置上排序一个序列 如何最快地对其进行排序压缩编码AAAABBBCDDE 图的最短路径地理研究中的交通网络 4 2020 3 21 可编辑 第2章数据结构概述 一 什么是数据结构1 数值型与非数值型数据 1 学生表格 5 2020 3 21 可编辑 一 什么是数据结构 2 选课表 3 UNIX的文件系统 6 2020 3 21 可编辑 一 什么是数据结构 2 数据结构简单来说 就是相互之间存在一种或多种特定关系的数据元素的集合 如线性关系 层次关系 网状关系等 7 2020 3 21 可编辑 第2章数据结构概述 二 有关数据结构的基本概念和术语1 数据 data 计算机程序所处理的一切数值性的和非数值性的信息 2 数据元素 dataelement 是数据集合中的一个个体 是数据的基本单位 如数据集合N 1 2 3 4 5 中整数1至5均为数据元素 数据元素不一定是单个的数字或字符 也可能是若干个数据项的组合 如学生信息 学生 学号 姓名 性别 成绩 数据项 dataitem 是数据不可再分的最小单位 数据元素有时也称结点 节点或记录 8 2020 3 21 可编辑 二 有关数据结构的基本概念和术语 3 数据对象 dataobject 是具有相同性质的数据元素的集合 如大写字母字符的数据对象是集合 C A B Z 4 数据结构 datastructure 研究数据元素之间抽象化的相互关系和这种相互关系在计算机系统中的存储方式 并对每种数据结构定义相关的运算算法 确保经过运算后仍然是原来的数据结构类型 5 数据的逻辑结构 logicalstructure 表示数据元素之间抽象化的相互关系 又可简称为数据结构 它研究数据元素及其关系的数学特性 集合 线性 树型 网状6 数据的物理结构 physicalstructure 表示数据的逻辑结构在计算机系统中的存储方式 又可简称为存储结构 它是逻辑结构在计算机中的映象 也就是具体实现 顺序存储 链式存储 索引存储 散列存储 9 2020 3 21 可编辑 第2章数据结构概述 三 算法1 算法 为解决某个计算任务而安排的有限操作过程的描述 2 算法的特性有穷性确定性数据输出数据输入能行性 10 2020 3 21 可编辑 三 算法 3 好的算法的特性正确性可读性健壮性高效率和低存储空间要求简洁性 11 2020 3 21 可编辑 第2章数据结构概述 四 算法描述语言和算法分析1 算法描述语言本门课程基本采用ANSIC描述算法 注释部分用 或 表示 有些地方为方便起见 可能省略变量定义等有关内容 请大家复习C语言的相关内容 特别是指针和结构两部分的内容 12 2020 3 21 可编辑 四 算法描述语言和算法分析 2 算法的复杂性分析一个可执行的算法不一定是一个好算法 算法的分析是一个复杂的问题 通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法优劣的标准 这两个标准分别称为时间复杂度和空间复杂度 一般时间复杂度考虑的较多 度量一个程序的执行时间通常有两种方法 事后统计和事前分析估算这里我们介绍第二种方法 13 2020 3 21 可编辑 四 算法描述语言和算法分析 2 1时间复杂度频度 指一条语句重复执行的次数 记作 F n 时间复杂度 T n O F n 下面举例说明如何求时间复杂度 14 2020 3 21 可编辑 四 算法描述语言和算法分析 1 for i 0 i n i 2 for j 0 j n j 3 b i j 0 4 for k 0 k n k 5 b i j b i j a i k a k j 6 我们以执行次数最多的语句 第5句 进行计算 语句频度为 F n n3时间复杂度 T n O F n O n3 15 2020 3 21 可编辑 四 算法描述语言和算法分析 思考下列程序段的时间复杂度1 x x 1 2 for j 0 j n j x x 1 3 for j 0 j n j for k 0 k n k x x 1 4 for j 2 j n j for k 2 k j 1 k x x 1 T n O 1 T n O n T n O n2 T n O n2 计算方法 对于外层循环中的j 从2到n循环 计算出j每取一个值时 内层循环执行的次数0 1 2 n 2 然后累加起来 得到一个n的多项式 n 1 n 2 2 取出次数最高的项即可 16 2020 3 21 可编辑 四 算法描述语言和算法分析 常见的时间复杂度1 O 1 常量型2 O n O n2 O nk 多项式型3 O log2n O 2log2n 对数型4 O 2n O en 指数型 17 2020 3 21 可编辑 四 算法描述语言和算法分析 2 空间复杂度空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间 因为这些单元与算法无关 记作 S n 时间与空间是一对矛盾 要节约空间往往就要消耗较多时间 反之亦然 而目前由于计算机硬件的发展 一