基本数据结构与算法PPT课件[通用]

1、第三章基本数据结构与算法二级ACCESS基本数据结构与算法本章主要内容算法 数据结构 数据结构研究的主要内容 基本概念和术语 数据结构类型 线性结构和非线性结构 顺序存储与链式存储 线性表 栈和队列 线性链表 树与二叉树 查找和排序 图 二级ACCESS基本数据结构与算法3.1 算法算法的基本概念 算法：解题方案的准确而完整的描述。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。 基本特性 可行性：根据实际问题设计的算法，执行得到满意结果 确定性：每一步骤必须有明确定义，不允许有多义性。 有穷性：

2、算法必须能在有限的时间内做完。 输入和输出：拥有足够的情报，方可执行。二级ACCESS基本数据结构与算法3.1 算法算法的基本要素 1.对数据对象的运算和操作 算术运算：、等 逻辑运算：、=、1，则该结点的父结点的编号为INT(k/2)。 若2kn，则结点k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。 若2k+1n，则结点k的右子结点编号为2k+1；否则该结点无右子结点。二叉树的基本性质42 3 16 78910 11 12 13 14 15 53.3.6 树与二叉树例如结点6，其父结点为3，左子结点为12，左子结点为13二级ACCESS基本数据结构与算法3.3.6 树与

3、二叉树二叉树的存储结构 顺序存储结构 链式存储结构 顺序存储结构 用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。 用数组存储时，若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。 顺序存储二叉树必须按完全二叉树的形式存储，将造成存储的浪费。二级ACCESS基本数据结构与算法二叉树的顺序存储结构 T1611 A B c F E D 1 2 4 8 910 5 6 3 7121314152h-1=24-1 = 150000FE00 0DC0BA 151413121110987654321003.3.6 树与二叉树二级ACCESS基本数据结构

4、与算法3.3.6 树与二叉树二叉树链式存储结构 在顺序存储结构中，对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：LchilditemRchildparentAB二级ACCESS基本数据结构与算法3.3.6 树与二叉树G H D E F B C A G H D E F B C A BT 二叉树的链接存储结构 二级ACCESS基本数据结构与算法二叉树的遍历 遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。 按先左后右的原则，一般使用三种遍历： 先序遍历(D L R

5、): 访问根结点，按先序遍历左子树，按先序遍历右子树。 中序遍历(L D R): 按中序遍历左子树，访问根结点，按中序遍历右子树。 后序遍历(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。3.3.6 树与二叉树二级ACCESS基本数据结构与算法遍历算法先序遍历：D L R 中序遍历：L D R 后序遍历：L R DADBCT1 T2 T3 D L RAD L RD L RBDCD L R以先序遍历D L R为例演示遍历过程 ABDCBDAC DBCA3.3.6 树与二叉树二级ACCESS基本数据结构与算法查找：在一个给定的数据结

6、构中，根据给定的条件找到满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。 平均查找长度：查找过程中比较的次数 查找的结果 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。3.3.7 查找和排序二级ACCESS基本数据结构与算法顺序查找（线性查找） 对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。 可以采用从前向后查，也可采用从后向前查的方法。 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度=(n+1)/2。 时间复杂度O(n) 在下面两种情况下只能采取顺

7、序查找： 线性表为无序表（元素排列是无序的）； 即使是有序线性表，但采用的是链式存储结构。3.3.7 查找和排序二级ACCESS基本数据结构与算法折半查找（二分法查找）思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 分三种情况： 若中间项的值等于x,则说明已查到。 若x小于中间项的值，则在线性表的前半部分查找； 若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。3.3.7 查找和排序折半查找（二分法查找）算法 假设查找表存放在数组a的a1an中，且

8、升序，查找关键字值为k。折半查找的主要步骤为： （1）置初始查找范围：low=1，high=n; （2）求查找范围中间项：mid=(low+high)/2 （3）将指定的关键字值k与中间项amid.key比较。 若相等，查找成功，找到的数据元素为此时mid 指向的位置； 若小于，查找范围的低端数据元素指针low不变，高端数据元素指针high更新为mid-1; 若大于，查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1; （4）重复步骤（2）、（3）直到查找成功或查找范围空（lowhigh），即查找失败为止。 （5）如果查找成功，返回找到元素的存放位置，即当前的中间项

9、位置指针mid；否则返回查找失败标志。 查找23和79的过程如下图：9元素mid=(low+high)/2不进位取整( 08, 14, 23, 37, 46, 55, 68, 79, 91 )( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhigh=mid-1mid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )low=mid+1highmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid

10、( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid二级ACCESS基本数据结构与算法 排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。 排序过程的组成步骤 1、首先比较两个关键字的大小； 2、然后将记录从一个位置移动到另一个位置。 3.3.7 查找和排序堆排序起泡排序排序方法插入排序选择排序交换排序归并排序直接、折半插入排序希尔排序简单选择排序快速排序二级ACCESS基本数据结构与算法该算法适合于n 较小的情况，时间复杂度

11、为O(n2).待排元素序列：53 27 36 15 69 42 第一次排序： 27 53 36 15 69 42 第二次排序： 27 36 53 15 69 42 第三次排序： 15 27 36 53 69 42 第四次排序： 15 27 36 53 69 42 第五次排序： 15 27 36 42 53 69 直接插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1次3.3.7 直接插入排序 从数组的第2号元素开始，顺序取出后续元素，并将该元素插入到其左端已排好序数组的适当位置。需比较n(n-1)/2次二级ACCESS基本数据结构与算法例：有6个记录，前5 个已排序的基础上，对第6

12、个记录排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 (high36 ) ( 4253 ) 3.3.7 折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置 。待排序元素越多，改进效果越明显。 思想：首先从1n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。 时间复杂度为O(n2)，最坏情况下需要比较 n(n-1

13、)/2次 适用于待排序元素较少的情况。3.3.7 简单选择排序初态8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 ijkijkijkijk1 3 9 8 6 互换ijk1 3 9 8 6 ikj1 3 9 8 6 ikj第一趟第二趟1 3 9 8 6 ikj第三趟二级ACCESS基本数据结构与算法 交换排序的特点在于交换，有冒泡和快速排序两种。 冒泡排序（起泡排序） 思想：小的浮起，大的沉底。从左端开始比较。 第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，关键字最大的记录交换到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字

14、次大的记录交换到第n-1个位置上； 依次类推，则完成排序。 正序：时间复杂度为O(n) 逆序：时间复杂度为O(n2) 排序n个记录的文件最多需要n-1趟冒泡排序。3.3.7 交换排序二级ACCESS基本数据结构与算法第 六 趟 排 序 后 第 五 趟 排 序 后 第 四 趟 排 序 后 第 三 趟 排 序 后 第 二 趟 排 序 后 第 一 趟 排 序 后初 始 关 键 字 4936416511 7836 653641 56364165 4136415611783636414911564925252511494956111111252525253.3.7 交换排序示例二级ACCESS基本数据结构与算法各种排序法比较二级ACCESS基本数据结构与算法3.3.8 图图的基本概念 图：节点(图中称顶点)间的连接是任意的。 图的分类：有向图、无向图V1 V3 V2 V4 在有向图中，表示从V1到V3的一条弧。 V1为弧尾或初始点，V3为弧头或终端点。V1