软件理论基础(算法与数据结构).ppt

基本数据结构与算法 算法的基本概念 算法是解题方案的准确而完整的描述 它是指令的有限序列 其中每一条指令表示一个或多个操作 它是一组严谨地定义运算顺序的规则 并且每一个规则都是有效的 且是明确的 此顺序将在有限的次数下终止 算法不同于程序 程序是算法的一种表示形式 它受到计算机系统等很多细节问题限制 一般地 程序的编制不可能优于算法 算法具有有穷性 确定性 可行性 输入和输出 拥有足够的情报 等 个重要特性 算法的基本要素 1 对数据对象的运算和操作算术运算逻辑运算关系运算数据传输2 算法的控制结构一个算法一般可以用顺序 选择 循环三种基本结构组合而成 3 算法设计基本方法列举法 归纳法 递推 递归 减半递推技术 回溯法 算法复杂度 时间复杂度指执行算法所需要的基本计算工作量 为了客观的反映算法的效率 可以用算法执行过程中所需基本运算的重复次数来度量算法的工作量 时间复杂度 f n n是问题的规模平均时间复杂度A n p x t x 最坏情况复杂度W n max t x 算法的空间复杂度一般是指执行这个算法所需要的内存空间 数据结构的基本概念 数据结构 相互之间存在特定关系的数据集合数据的逻辑结构 数据元素的信息 各数据元素之间的前后件关系数据的存储 物理 结构 数据的逻辑结构在计算机存储空间中的存放形式 线性 树 图 数据结构的图形表示 图形表示数据元素由结点表示 用从前件指向后件的有向线段表示 没有前件的结点称为根结点 没有后件的结点称为叶子结点 线性结构与非线性结构 一般将数据结构分为两种类型 1 线性结构如果一个非空的数据结构满足下列二个条件 1 有且只有一个根结点2 每个结点最多有一个前件和一个后件包括线性表 队列 堆栈 2 非线性结构如果一个数据结构不是线性的 则称非线性的包括树和图 线性表及其特点 线性表是一种线性结构 元素在线性表中的位置仅取决于自己的序号 线性表中结点的个数n称为表的长度 当n 0时 称作空表 线性表的特点 1 线性表中所有元素的性质相同 2 除第一个和最后一个数据元素之外 其它数据元素有且仅有一个前驱和一个后继 3 有且只有一个根结点和一个终端结点 第一个数据结点无前驱 最后一个数据结点无后继 线性表的顺序存储结构 1 线性表中数据元素类型一致 只有数据域 存储空间利用率高 2 所有元素所占的存储空间是连续的3 各数据元素在存储空间中是按逻辑顺序依次存放的 元素an 元素ai 元素a2 元素a1 b b m b i 1 m b maxlen 1 m 存储地址 内存状态 m为每个元素占用的存储单元数 起始地址 插入与删除运算 12 20 18 25 96 42 72 35 55 12 20 18 25 96 42 72 35 55 插入运算 删除运算 12 20 25 96 42 72 35 55 原始数据 插入结果 删除结果 栈和队列 栈和队列是两种特殊的线性表栈 限定只能在表的一端进行插入和删除的特殊的线性表 此种结构称为后进先出栈顶 top 允许插入和删除的一端 约定top始终指向新数据元素将存放的位置 栈底 bottom 不允许插入和删除的一端 a1 a2 an 进栈 出栈 栈顶 栈底 栈的基本运算 基本运算 压 进 栈 PUSH 插入top top 1出栈 POP 删除top top 1设置一个简单变量top指示栈顶位置 称为栈顶指针 它始终指向待插入元素的位置 A C B top PUSHX A C B X top A C B top POPX 队列 队列 限定只能在表的一端进行插入 在表的另一端进行删除的线性表 此种结构称为先进先出 FIFO 队尾rear只允许插入 队头front只允许删除 a1 a2 a3 a4 an 1 an 队列示意图 队头front 队尾rear 队列基本运算 A B C rear front 入队运算rear rear 1 A B C rear front D B C rear front D 出队运算front front 1 循环队列 线性链表 将线性表的元素放到一个具有头指针的链表中 链表中每个结点包含数据域和指针域数据域存放数据 指针域存放后继结点的地址 最后一个结点的指针域为空 逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻 双向链表与循环链表 线性双链表 每个结点设置两个指针 左指针指向其前件 右指针指向其后件循环链表 最后一个结点的指针域不为空 而是指向表头结点 单链表的插入运算 生成新结点新结点的指针S指向后一个结点S next P next前一个结点的指针P指向新结点P next S P P S 单链表的删除运算 要删除P的后继结点 则让P的指针指向P的后继的后继P next P next next然后释放被删除结点单链表的查找从表头开始顺次向后查找 直到找到需要的元素 P 树的基本概念 树是一种简单的非线性结构 在这种结构中 所有数据元素之间的关系具有明显的层次特性 父结点根结点子结点叶子结点结点的度树的度树的深度子树 计算机中 用树结构表示表达式a b c d e f g 二叉树及其基本性质 二叉树是具有以下两个特点的树 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 且分别称为该结点的左子树和右子树在二叉树中每一个结点的度的最大为2二叉树的基本性质性质1在二叉树的第k层上 最多有2 k 1 个结点性质2深度为m的二叉树最多有2m 1个结点 性质3在任意一棵二叉树中 度为0的结点 叶子结点 总比度为2的结点多一个 n0 n1 n2 1 n1 2 n2例 一棵二叉树有3个叶子结点 有8个度为1的结点 则该二叉树中总的结点数是多少 13 性质4具有n个结点的二叉树 其深度至少为 log2n 1 4 2 3 1 6 5 满二叉树与完全二叉树 满二叉树 除叶子结点外 所有结点都有两个子结点 在二叉树的第k层上 有2 k 1 个结点深度为m的二叉树有2 m 1个结点例在深度为5的满二叉树中 叶子结点的个数是多少 结点数是多少 16 31 完全二叉树 除最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若于结点特点 如果从根结点出发 对二叉树的结点自上而下 自左而右进行编号 则其编号是与满二叉树的编号相一致的 满二叉树一定是完全二叉树 完全二叉树不一定是满二叉树 满二叉树 完全二叉树 非完全二叉树 性质5具有n个结点的完全二叉树 其深度为 log2n 1性质6为结点数n的完全二叉树编号 则对于编号为k的结点有以下结论 1 若k 1 则该结点为根结点 2 若k 1 则该结点的父结点编号为INT k 2 3 编号为k的结点的左子结点编号为2k 若2k n 其右子结点编号为2k 1 若2k 1 n 例一个完全二叉树共有739个结点 则该树有多少个叶子结点 370 提示 叶子结点出现在层次最大的两层 可推导出公式 叶子结点数 INT 结点总数 1 2 顺序存储完全二叉树 则很容易确定每一个结点的父结点 左子结点 右子结点的存储位置 二叉树的存储结构 二叉树通常采用链式存储结构 称为二叉链表 对于满二叉树和完全二叉树可以采用顺序存储 BT 二叉链表的存储状态 二叉链表的逻辑状态 LchildValueRchild 二叉树结点结构 二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点 原则 先遍历左子树 后遍历右子树三种不同的方法 根据访问根结点的次序 二叉树的遍历可以分为前序遍历 中序遍历 后序遍历 前序遍历 访问根结点 前序遍历左子树 前序遍历右子树中序遍历 中序遍历左子树 访问根结点 中序遍历右子树后序遍历 后序遍历左子树 后序遍历右子树 访问根结点树的遍历是一个递归过程 例如下的二叉树 它的前序遍历是什么 中序遍历是什么 后序遍历是什么 前序遍历FCADBEGHP中序遍历ACBDFEHGP后序遍历ABDCHPGEF F C E A D B H P G 练习 一棵二叉树的中序遍历为DBEAFC 前序遍历是ABDECF 则后序遍历是什么 查找技术 所谓查找是指在一个给定的数据结构中查找某个指定的元素顺序查找就是从线性表的第一个元素开始 依次将线性表中的元素与所查元素进行比较顺序查找的最好情况 线性中的第一个元素就是被查找元素 只需1次比较顺序查找的最坏情况 线性中的最后一个元素就是被查找元素 需比较N次顺序查找的平均情况 N 2次在下面两种情况下只能采取顺序查找 a 线性表为无序表 元素排列是无序的 b 即使是有序线性表 但采用的是链式存储结构 折半查找 二分法查找 思想 先确定待查找记录所在的范围 然后逐步缩小范围 直到找到或确认找不到该记录为止 前提 必须在具有顺序存储结构的有序表中进行 分三种情况 1 若中间项的值等于x 则说明已查到 2 若x小于中间项的值 则在线性表的前半部分查找 3 若x大于中间项的值 则在线性表的后半部分查找 特点 比顺序查找方法效率高 最坏的情况下 需要比较log2n次 利用折半查找查找23的过程如下图 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 mid low high 2不进位取整 123456789 排序技术 排序的功能 将一个数据元素 或记录 的任意序列 重新排成一个按关键字有序的序列我们只讨论顺序存储的线性表的排序方法 排序方法 插入排序 选择排序 交换排序 直接插入排序O n2 希尔排序 简单选择排序O n2 堆排序 起泡排序O n2 快速排序 交换排序 冒泡排序 起泡排序 思想 小的浮起 大的沉底 排序n个记录的文件最多需要n 1趟冒泡排序 快速排序 思想 通过一趟排序将待排序列分成两部分 使其中一部分记录的关键字均比另一部分小 再分别对这两部分排序 以达到整个序列有序 快速排序过程示意图 key low high 一次交换185266723 low high 二次交换182366752 三次交换 186 23 6752 完成一趟排序后分别进行快速排序 插入排序 简单插入排序所谓插入排序 是指将无序序列中的各元素依次插入到已经有序的线性表中 待排元素序列 53 2736156942第一次排序 2753 36156942第二次排序 273653 156942第三次排序 15273653 6942第四次排序 1527365369 42第五次排序 152736425369 希尔排序 基本思想如下 将整个序列分割成基于小的子序列 分别进行插入排序将相隔某个增量h的元素构成一个子序列 在排序过程中 逐次减小这个增量 最后当h减到1时 进行一次插入排序 排序就完成 最坏