基本数据结构与算法 (2)优秀课件.ppt

《基本数据结构与算法 (2)优秀课件.ppt》由会员分享，可在线阅读，更多相关《基本数据结构与算法 (2)优秀课件.ppt（74页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、基本数据结构与算法第1页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法本章主要内容本章主要内容本章主要内容本章主要内容 算法算法算法算法 数据结构数据结构数据结构数据结构 数据结构研究的主要内容数据结构研究的主要内容数据结构研究的主要内容数据结构研究的主要内容 基本概念和术语基本概念和术语基本概念和术语基本概念和术语 数据结构类型数据结构类型数据结构类型数据结构类型 线性结构和非线性结构线性结构和非线性结构线性结构和非线性结构线性结构和非线性结构 顺序存储与链式存储顺序存储与链式存储顺序存储与链式存储顺序存储与链式存储 线性表线性表线性表线性表 栈和队列栈

2、和队列栈和队列栈和队列 线性链表线性链表线性链表线性链表 树与二叉树树与二叉树树与二叉树树与二叉树 查找和排序查找和排序查找和排序查找和排序 图图图图 第2页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法3.1 3.1 算法算法算法的基本概念算法的基本概念算法：解题方案的准确而完整的描述。算法：解题方案的准确而完整的描述。算法的基本特征：算法的基本特征：是一组严谨地定义运算顺序的规则，是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。下终止。算法不等于程序，程序不

3、可能优于算法。算法不等于程序，程序不可能优于算法。基本特性基本特性可行性：根据实际问题设计的算法，执行得到满意结果可行性：根据实际问题设计的算法，执行得到满意结果确定性：每一步骤必须有明确定义，不允许有多义性。确定性：每一步骤必须有明确定义，不允许有多义性。有穷性：算法必须能在有限的时间内做完。有穷性：算法必须能在有限的时间内做完。输入和输出：拥有足够的情报，方可执行。输入和输出：拥有足够的情报，方可执行。第3页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法3.1 3.1 算法算法算法的基本要素算法的基本要素1.1.对数据对象的运算和操作对数据对象的运算和

4、操作 算术运算：、算术运算：、等等 逻辑运算：逻辑运算：、=、=1k1，则则该该结结点点的的父父结结点点的的编编号号为为INT(k/2)INT(k/2)。若若2kn2kn，则结点，则结点k k的左子结点编号为的左子结点编号为2k2k；否则该结点无左子结点（显然也没有右子结点）。；否则该结点无左子结点（显然也没有右子结点）。若若2k+1n2k+1n，则结点，则结点k k的右子结点编号为的右子结点编号为2k+12k+1；否则该结点无右子结点。；否则该结点无右子结点。二叉树的基本性质二叉树的基本性质42 3 16 78910 11 12 13 14 15 53.3.6树与二叉树树与二叉树例如结点例如

5、结点6 6，其父结点为，其父结点为3 3，左子结，左子结点为点为1212，左子结点为，左子结点为1313第52页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法3.3.6树与二叉树树与二叉树 二叉树的存储结构二叉树的存储结构二叉树的存储结构二叉树的存储结构 顺序存储结构顺序存储结构 链式存储结构链式存储结构 顺序存储结构顺序存储结构顺序存储结构顺序存储结构 用一组用一组连续的存储单元存放连续的存储单元存放二叉树的数据元素。结点在数组中二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。的相对位置蕴含着结点之间的关系。用数组存储时，若父结点在数组中用

6、数组存储时，若父结点在数组中i i下标处，其左孩子在下标处，其左孩子在2*i2*i处，右孩子在处，右孩子在2*i+12*i+1处。处。顺序存储二叉树顺序存储二叉树必须按完全二叉树的形式存储必须按完全二叉树的形式存储，将造成存储的浪，将造成存储的浪费。费。第53页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法二叉树的顺序存储结构二叉树的顺序存储结构二叉树的顺序存储结构二叉树的顺序存储结构 T1611ABcFED12 4 8 9105637121314152h-1=24-1=150000FE00 0DC0BA 151413121110987654321003.

7、3.63.3.6树与二叉树树与二叉树第54页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法3.3.6树与二叉树树与二叉树 二叉树链式存储结构二叉树链式存储结构二叉树链式存储结构二叉树链式存储结构 在顺序存储结构中，对于非完全二叉树，需要将空缺的位在顺序存储结构中，对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。下降。在这种情况下，就应该考虑使用链式存储结构。常见的二常见的二叉树结点结构如下所示：叉树结点结构如下所示

8、：LchilditemRchildparentAB第55页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法3.3.63.3.6树与二叉树树与二叉树树与二叉树树与二叉树G H D E F B C A G H D E F B C A BT 二叉树的链接存储结构二叉树的链接存储结构二叉树的链接存储结构二叉树的链接存储结构 第56页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法二叉树的遍历二叉树的遍历 遍遍历历是是指指按按某某条条搜搜索索路路线线寻寻访访树树中中每每个个结结点点，且且每每个个结结点点只只被访问一次。被访问一次。按

9、先左后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历：先序遍历先序遍历(D L R):(D L R):访问访问根结点根结点，按先序遍历，按先序遍历左子树左子树，按先序遍历，按先序遍历右子树右子树。中序遍历中序遍历(L D R):(L D R):按中序遍历按中序遍历左子树左子树，访问，访问根结点根结点，按中序遍历，按中序遍历右子树右子树。后序遍历后序遍历(L R D):(L R D):按后序遍历按后序遍历左子树左子树，按后序遍历，按后序遍历右子树右子树，访问，访问根结点根结点。二叉树为空时，执行空操作，即空二

10、叉树已遍历完。二叉树为空时，执行空操作，即空二叉树已遍历完。3.3.63.3.6树与二叉树树与二叉树第57页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法遍历算法遍历算法遍历算法遍历算法先序遍历：先序遍历：D L R D L R 中序遍历：中序遍历：L D R L D R 后序遍历：后序遍历：L R DL R DADBCT1T2T3DLRADLRDLRBDCDLR以先序遍历以先序遍历DLRDLR为例为例演示遍历过程演示遍历过程 ABDCBDACDBCA3.3.63.3.6树与二叉树树与二叉树第58页，本讲稿共74页二级二级ACCESSACCESS基本数据结

11、构与算法基本数据结构与算法查找：查找：在一个给定的数据结构中，在一个给定的数据结构中，根据给定的条件找到满足根据给定的条件找到满足条件的结点。条件的结点。不同的数据结构采用不同的查找方法。查找的不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。效率直接影响数据处理的效率。平均查找长度：平均查找长度：查找过程中比较的次数查找过程中比较的次数 查找的结果查找的结果 查找成功：查找成功：找到满足条件的结点找到满足条件的结点 查找失败：查找失败：找不到满足条件的结点。找不到满足条件的结点。3.3.7查找和排序查找和排序第59页，本讲稿共74页二级二级ACCESSACCESS基本数据结

12、构与算法基本数据结构与算法顺序查找（线性查找）顺序查找（线性查找）对给定的一对给定的一关键字关键字K K，从线性表的一端开始，逐个进行，从线性表的一端开始，逐个进行记录的关键字和记录的关键字和K K的比较，直到找到关键字等于的比较，直到找到关键字等于K K的记录的记录或到达表的另一端。或到达表的另一端。可以采用从前向后查，也可采用从后向前查的方法。可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较，效在平均情况下，大约要与表中一半以上元素进行比较，效率较低。率较低。平均查找长度平均查找长度=(n+1)/2=(n+1)/2。时间复杂度时间复杂度O(n)O

13、(n)在下面两种情况下只能采取顺序查找：在下面两种情况下只能采取顺序查找：线性表为无序表（元素排列是无序的）；线性表为无序表（元素排列是无序的）；即使是有序线性表，但采用的是链式存储结构。即使是有序线性表，但采用的是链式存储结构。3.3.7查找和排序查找和排序第60页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法折半查找（二分法查找）折半查找（二分法查找）折半查找（二分法查找）折半查找（二分法查找）思想：思想：先确定待查找记录所在的范围，然后逐步缩小范围，直先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。到找到或确认找不到该记

14、录为止。前提：前提：必须在必须在具有顺序存储结构的具有顺序存储结构的有序表中进行有序表中进行。分三种情况：分三种情况：若中间项的值等于若中间项的值等于x,x,则说明已查到。则说明已查到。若若x x小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在线性表的前半部分查找；若若x x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。特点：特点：比顺序查找方法效率高。比顺序查找方法效率高。最坏的情况下，需要比较最坏的情况下，需要比较 loglog2 2n n次。次。3.3.73.3.7查找和排序查找和排序第61页，本讲稿共74页折半查找（二分法查找）算法折

15、半查找（二分法查找）算法 假设查找表存放在假设查找表存放在数组数组a a的的a1a1anan中，且升序中，且升序，查找关键字，查找关键字值为值为k k。折半查找的。折半查找的主要步骤主要步骤为：为：（1 1）置初始查找范围：）置初始查找范围：low=1low=1，high=n;high=n;（2 2）求查找范围中间项：）求查找范围中间项：mid=(low+high)/2 mid=(low+high)/2（3 3）将指定的关键字值）将指定的关键字值k k与中间项与中间项amid.keyamid.key比较。比较。若相等，若相等，查找成功，找到的数据元素为此时查找成功，找到的数据元素为此时mid

16、mid 指向的位置；指向的位置；若小于，若小于，查找范围的低端数据元素指针查找范围的低端数据元素指针lowlow不变，高端数据元素指针不变，高端数据元素指针highhigh更新为更新为mid-1;mid-1;若大于，若大于，查找范围的高端数据元素指针查找范围的高端数据元素指针highhigh不变，低端数据元素指针不变，低端数据元素指针lowlow更新更新为为mid+1;mid+1;（4 4）重复步骤（）重复步骤（2 2）、（）、（3 3）直到查找成功或查找范围空（）直到查找成功或查找范围空（lowhighlowhigh），即查找失败为止。），即查找失败为止。（5 5）如果查找成功，返回找到元素

17、的存放位置，即当前的中间项位置指针）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针midmid；否则；否则返回查找失败标志返回查找失败标志。第62页，本讲稿共74页查找查找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(0

18、8,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid第63页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法 排序的功能：排序的功能：将一个数据元素（或记录）的将一个数据元素（或记录）的任意序列任意序列，重新排成一个按关键字重新排成一个按关键字有序有序的序列。的序列。排序过程的组成步骤排序过程的组成步骤 1 1、首先、首先比较比较两个关键字的大小；两个关键字的大小；2 2、然后将记录从一个

19、位置、然后将记录从一个位置移动移动到另一个位置。到另一个位置。3.3.73.3.7查找和排序查找和排序堆排序堆排序堆排序堆排序起泡排序起泡排序起泡排序起泡排序排序方法排序方法排序方法排序方法插入排序插入排序插入排序插入排序选择排序选择排序选择排序选择排序交换排序交换排序交换排序交换排序归并排序归并排序归并排序归并排序直接、折半插入排序直接、折半插入排序直接、折半插入排序直接、折半插入排序希尔排序希尔排序希尔排序希尔排序简单选择排序简单选择排序简单选择排序简单选择排序快速排序快速排序快速排序快速排序第64页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法该该算

20、算法法适适合合于于n较较小小的的情情况况，时时间间复复杂杂度度为为O(n2).待排元素序列：待排元素序列：532736156942第一次排序：第一次排序：275336156942第二次排序：第二次排序：273653156942第三次排序：第三次排序：152736536942第四次排序：第四次排序：152736536942第五次排序：第五次排序：152736425369直接插入排序示例直接插入排序示例对于有对于有n个数据个数据元素的待排序元素的待排序列，插入操作列，插入操作要进行要进行n-1次次3.3.7直接插入排序直接插入排序 从数组的第从数组的第2号元素开始，顺序取出后续元素，并将该元素插入

21、到号元素开始，顺序取出后续元素，并将该元素插入到其左端已排好序数组的适当位置。需比较其左端已排好序数组的适当位置。需比较n(n-1)/2次次第65页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法例：有例：有6个记录，前个记录，前5个已排序的基础上，对第个已排序的基础上，对第6个记录排序。个记录排序。152736536942 low mid high152736536942 low high mid152736536942 high low152736425369(high36)(4253)3.3.73.3.7折半插入排序折半插入排序折半插入排序折半插入排序

22、 折折半半插插入入排排序序在在寻寻找找插插入入位位置置时时，不不是是逐逐个个比比较较而而是是利利用用折折半半查查找找的的原原理理寻寻找找插插入入位位置置 。待待排排序序元元素素越越多多，改改进进效果越明显。效果越明显。第66页，本讲稿共74页 思想：首先从思想：首先从1 1n n个元素个元素中选出关键字中选出关键字最小最小的记录交换的记录交换到到第一个第一个位置上。然后再从第位置上。然后再从第2 2 个到第个到第n n个元素中选出次小的个元素中选出次小的记录交换到记录交换到第二个第二个位置上，依位置上，依次类推。次类推。时间复杂度为时间复杂度为O(nO(n2 2)，最，最坏情况下需要比较坏情况

23、下需要比较 n(n-n(n-1)/21)/2次次 适用于适用于待排序元素较少待排序元素较少的情况。的情况。3.3.73.3.7简单选择排序简单选择排序简单选择排序简单选择排序初态初态83916839168391683916ijkijkijkijk13986互换互换ijk13986ikj13986ikj第第一一趟趟第第二二趟趟13986i kj第第三三趟趟第67页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法 交换排序的特点在于交换排序的特点在于交换交换，有，有冒泡和快速排序冒泡和快速排序两种。两种。冒泡排序（起泡排序）冒泡排序（起泡排序）冒泡排序（起泡排序

24、）冒泡排序（起泡排序）思想：思想：小的浮起，大的沉底。小的浮起，大的沉底。从左端开始比较。从左端开始比较。第第一一趟趟：第第1 1个个与与第第2 2个个比比较较，大大则则交交换换；第第2 2个个与与第第3 3个个比比较较，大大则则交换，交换，关键字最大的记录交换到最后一个位置上；关键字最大的记录交换到最后一个位置上；第第二二趟趟：对对前前n-1n-1个个记记录录进进行行同同样样的的操操作作，关关键键字字次次大大的的记记录录交交换到第换到第n-1n-1个个位置上；位置上；依次类推，则完成排序。依次类推，则完成排序。正序：时间复杂度为正序：时间复杂度为O(n)O(n)逆序：时间复杂度为逆序：时间复

25、杂度为O(nO(n2 2)排序排序n n个记录的文件最多需要个记录的文件最多需要n-1n-1趟冒泡排序。趟冒泡排序。3.3.7交换排序交换排序第68页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法第第第第 六六六六 趟趟趟趟 排排排排 序序序序 后后后后 第第第第 五五五五 趟趟趟趟 排排排排 序序序序 后后后后 第第第第 四四四四 趟趟趟趟 排排排排 序序序序 后后后后 第第第第 三三三三 趟趟趟趟 排排排排 序序序序 后后后后 第第第第 二二二二 趟趟趟趟 排排排排 序序序序 后后后后 第第第第 一一一一 趟趟趟趟 排排排排 序序序序 后后后后初初初初

26、 始始始始 关关关关 键键键键 字字字字49364165117836653641563641654136415611783636414911564925252511494956111111252525253.3.7交换排序交换排序交换排序交换排序示例示例第69页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法各种排序法比较各种排序法比较各种排序法比较各种排序法比较第70页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法3.3.8图图图的基本概念图的基本概念图：图：节点节点(图中称图中称顶点顶点)间的连接是任意的。间的连接是

27、任意的。图的分类：图的分类：有向图、无向图有向图、无向图V1 V3 V2 V4 在有向图中，在有向图中，V 表示从表示从V V1 1到到V V3 3的一条弧。的一条弧。V V1 1为弧尾或为弧尾或初始点初始点，V V3 3为弧头或为弧头或终端点终端点。V1 V3 V2 V4 在无向图中，在无向图中，(V(V1 1，V V3 3)表示表示V V1 1和和V V3 3之间的一条之间的一条边边。第71页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法V1 V3 V2 V4 顶点集合顶点集合V=V1，V2，V3，V4边的集合E=(V1,V3),(V1,V2),(V1

28、,V4),(V2,V4)顶点顶点(V1,V3)与与(V3,V1)表示同一条表示同一条边边顶点集合顶点集合V=V1，V2，V3，V4弧的集合弧的集合G=,V1 V3 V2 V4 3.3.8图图图图图的表示图的表示:G=(V,E)第72页，本讲稿共74页二级二级ACCESSACCESS基本数据结构与算法基本数据结构与算法3.3.83.3.8图图图图 图的基本概念图的基本概念图的基本概念图的基本概念 权：权：与图的边或弧相关的数。与图的边或弧相关的数。网：网：带权的图。带权的图。顶点的度：顶点的度：依附于该顶点的边数或弧数。依附于该顶点的边数或弧数。出度出度:(:(仅对有向图）仅对有向图）以该顶点为尾的弧数。以该顶点为尾的弧数。入度入度:(:(仅对有向图）仅对有向图）以该顶点为头的弧数。以该顶点为头的弧数。路径：路径：顶点顶点A A与顶点与顶点C C之间存在一条路径。路径上边或弧的之间存在一条路径。路径上边或弧的数目称为该路径的路径长度。数目称为该路径的路径长度。连通图：连通图：在无向图在无向图G G中，任意两顶点中，任意两顶点vivi、vjvj都是连通的，则称都是连通的，则称G G是连通图。是连通图。n n个顶点的连通图中边的条数至少为个顶点的连通图中边的条数至少为n-1n-1条条B A C D 63215第73页，本讲稿共74页第74页，本讲稿共74页