第6章 算法与数据结构

第6章算法与数据结构目录Contents算法概述常用的查找和排序算法数据结构概述数据结构的分类6.16.26.36.4计算机之所以能够处理各种问题全靠程序的运行,而算法是程序的“灵魂”。算法是解决问题的方法和策略,数据结构则是计算机存储、组织数据的方式。算法概述6.1算法概述6.16.1.1算法的概念与特征算法实质上就是运算序列,是为求解一个问题而设计的需要遵循的、被清楚指定的简单指令的集合。这个运算序列中的所有运算定义在一类指定的数据模型上,并以解决一类特定问题为目标。算法具有以下5个特征:(1)确定性。算法的每个步骤都明确地说明这一步应该执行的语句,不存在二义性。(2)可行性。算法的设计对于任意输入的合法数据都会进行下一步操作。(3)有穷性。在算法的执行过程中,执行步骤是有限的,并且算法的执行时间也是有限的。算法概述6.16.1.1算法的概念与特征(4)输入。在输入设计中,算法具有零个或多个输入,以确保程序的正常运行。零个输入指的是算法本身给出初始条件,以实现程序的正常运行,或者说一个程序如果自身可以产生初始条件,就没有必要设计输入环节。(5)输出。算法至少要设计一个输出环节。如果没有了输出环节,那么设计的程序也就没有了实际意义。当然输出的形式比较多样,如打印、返回一个值或多个值,给某个程序一个初始条件,显示某些提示等。算法概述6.16.1.2算法的描述自然语言就是人们日常使用的语言，可以使用中文，也可以使用英文，用自然语言描述的算法通俗易懂，但是文字冗长，准确性不好，容易产生歧义。例如，下面是一个求100以内质数的算法。第一步：输入整数变量n和变量m,n表示输入的大于1的自然数，m表示从2到小于n本身的整数。第二步：定义一个嵌套循环结构，外层从2到100对n进行遍历，内层从2到n对m进行遍历，若m/2==0,则不输出，否则输出m。第三步：结束。1.自然语言描述算法概述6.12.伪代码描述伪代码不是一种现实存在的编程语言,使用伪代码的目的是使被描述的算法可以容易地以任何一种编程语言来实现,它可能会综合使用多种编程语言中的语法、保留字,甚至还会用到自然语言。因此,伪代码必须结构清晰、代码简单、可读性好,并且类似自然语言。例如,按照从小到大的顺序输出两个数,用伪代码描述如下:算法概述6.13.流程图描述流程图常用以下一组符号来表示,如表6-1-1所示。算法概述6.13.流程图描述例如,求两个数从小到大输出的流程图如图6-1-1所示。算法概述6.14.N-S结构图N-S结构图是美国的两位学者艾克·纳西和本·施耐德曼提出的。他们认为,既然任何算法都是由顺序结构、选择结构和循环结构三种基本程序结构组成的,那么各基本结构之间的流程线就是多余的,因此,N-S图用一个大矩形框来表示算法,它是算法的一种结构化描述方法,是一种适合于结构化程序设计的流程图,求两个数按照大小顺序输出的N-S结构图如图6-1-2所示。算法概述6.16.1.3算法效率的评价算法效率的评价用时间复杂度(所需运算时间)和空间复杂度(所占存储空间)表示,重点是时间复杂度。一个算法所需的运算时间通常与所解决问题的规模大小有关。用n表示问题规模的量,把算法运行所需的时间T表示为n的函数,记为T(n)。不同的T(n)算法,当n增长时,运算时间增长的快慢不相同。一个算法所需的执行时间就是该算法中所有语句执行次数之和。算法概述6.11.事后统计法事后统计法可通过计算机内部计时功能来统计,但存在以下缺点:(1)必须先运行按照算法编写的程序。(2)运行时间的统计依赖于计算机硬件和软件的环境,难以判断算法本身的优劣。算法概述6.12.事先估算法将一个算法转换成程序并在计算机上运行,其所需要的时间取决于下列几个因素:(1)使用何种程序设计语言。(2)采取怎样的算法策略。(3)算法涉及问题的规模。(4)编译程序产生的目标代码的质量。(5)机器执行指令的质量。显然,在各种因素不确定的情况下,使用执行算法的绝对时间来衡量算法的效率是不合适的。在上述各种与计算机相关的软、硬件因素确定以后,一个特定算法的运行工作量的大小就只依赖于问题的规模。常用的查找和排序算法6.2常用的查找和排序算法6.26.2.1查找算法1.顺序查找3.哈希查找2.二分查找常用的查找和排序算法6.26.2.1查找算法6.2.1查找算法1.顺序查找顺序查找过程:从表中的第一个记录或最后一个记录开始,逐个将记录的关键字与给定值进行比较,若某个记录的关键字与给定值相等,则查找成功,找到所查的记录;若其关键字和给定值比较都不相等,则说明表中没有所查的记录,查找失败。常用的查找和排序算法6.26.2.1查找算法2.二分查找二分查找也称折半查找,是一种效率较高的查找算法。但是,二分查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。二分查找的原理是首先将表中间位置记录的关键字与中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果以上过程,直到找到满足条件的记录,此时查找成功,或直到子表不存在为止,此时查找不成功。常用的查找和排序算法6.23.哈希查找6.2.1查找算法哈希表又称散列表,是一种存储结构,通常用来存储多个元素。和其他存储结构相比,哈希表查找目标元素的效率非常高,每个存储到哈希表中的元素配有唯一的标识,又称索引,用户想查找某个元素,凭借该索引就可以直接找到,无须遍历整个哈希表。在数组中查找一个元素,除非提前知晓它存储位置处的下标,否则只能遍历整个数组。哈希表的解决方案:各个元素并不从数组的起始位置依次存储,它们的存储位置由专门设计的函数计算得出,通常将这样的函数称为哈希函数。哈希函数类似于数学中的一次函数,我们给它传递一个元素,它反馈给我们一个结果值,这个值就是该元素对应的索引,也就是存储在哈希表中的位置。常用的查找和排序算法6.23.哈希查找6.2.1查找算法例如,要将(20,30,50,70,80)这五个数存储到哈希表中,设计哈希函数为y=x/10,最终各个元素的存储位置如图6-2-1所示。常用的查找和排序算法6.23.哈希查找6.2.1查找算法在构建了哈希表的基础上,假如要查找元素70,只需将它代入y=x/10这个哈希函数中,计算出它对应的索引值为7,就可以直接在哈希表中找到它。构建哈希表时,哈希函数的设计至关重要。假设将{5,20,30,50,55}存储到哈希表中,哈希函数是y=x%10,各个元素在数组中的存储位置如图6-2-2所示。常用的查找和排序算法6.23.哈希查找6.2.1查找算法可以看到,5和55以及20、30和50对应的索引值是相同的,它们的存储位置发生了冲突,习惯将这种冲突称为哈希冲突或者哈希碰撞。设计一个好的哈希函数,可以降低哈希冲突的出现次数。常用的查找和排序算法6.26.2.2排序算法6.2.1查找算法1.快速排序算法快速排序算法的原理是从数列中选择一个值作为基准值,小于这个基准值的数放在基准值的前面,大于基准值的数放在基准值的后面,然后按照递归的方式对基准值前的数列和基准值后的数列分别再进行操作。例如,对数列19,15,18,7,10,22,16初始序列进行排序。第一轮排序,选择18作为基准值。常用的查找和排序算法6.21.快速排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第二轮排序:将10作为基准值。第三轮排序:将16作为基准值。经过三轮排序,初始序列就按照从小到大的顺序排好了。常用的查找和排序算法6.22.插入排序算法6.2.1查找算法插入排序的原理是每次取出一个待排序的元素,将其和左边所有的元素进行比较,如果所取值比左边元素小就与其交换,重复此操作,直到全部待排序元素插入完毕。例如,对数列19,15,18,7,10,22,16初始序列进行插入排序。第一轮排序:15插入到19前面。常用的查找和排序算法6.22.插入排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第二轮排序:18插入19前面。第三轮排序:7插入15前面。常用的查找和排序算法6.22.插入排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第四轮排序:10插入15前面。第五轮排序:无交换。常用的查找和排序算法6.22.插入排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第六轮排序:16插入18前面。经过六轮排序,初始序列就按照从小到大的顺序排好了。常用的查找和排序算法6.23.选择排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。选择排序算法的原理是取第一个数作为目前最小的数和后面的数逐一比较,如果比它小,就将这个数作为最小的数继续比较,一轮后将得到的最小的数放在第一个位置,然后取第二个数,重复之前的比较,直到待排序的数都转移到排序区。例如,对数列19,15,18,7,10,22,16初始序列进行选择排序。常用的查找和排序算法6.23.选择排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第一轮排序:取19与后面的数逐一比较,得到第一小的数为7。第二轮排序:取19与后面的数逐一比较,得到第二小的数为10。常用的查找和排序算法6.23.选择排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第三轮排序:取19与后面的数逐一比较,得到第三小的数为15。第四轮排序:取19与后面的数逐一比较,得到第四小的数为16。常用的查找和排序算法6.23.选择排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第五轮排序:取19与后面的数逐一比较,得到第五小的数为18。经过五轮排序,初始序列就按照从小到大的顺序排好了。常用的查找和排序算法6.24.冒泡排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。冒泡排序的原理是依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一轮:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此重复,直至比较最后两个数,将小数放前,大数放后。例如,对数列19,15,18,7,10,22,16初始序列进行冒泡排序。第一轮排序:交换19和15的位置。常用的查找和排序算法6.24.冒泡排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第二轮排序:交换19和18的位置。第三轮排序:交换19和7的位置。常用的查找和排序算法6.24.冒泡排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第四轮排序:交换19和10的位置。第五轮排序:交换22和16的位置。常用的查找和排序算法6.24.冒泡排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第六轮排序:交换18和7的位置。第七轮排序:交换18和10的位置。常用的查找和排序算法6.24.冒泡排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第八轮排序:交换19和16的位置。第九轮排序:交换15和7的位置。常用的查找和排序算法6.24.冒泡排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第十轮排序:交换15和10的位置。第十一轮排序:交换19和16的位置。经过十一轮排序,初始序列就按照从小到大的顺序排好了。常用的查找和排序算法6.25.归并排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,再使子序列段间有序。例如,对数列19,15,18,7,10,22,16初始序列进行归并排序。第一轮排序:两两一组进行归并。常用的查找和排序算法6.25.归并排序算法6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。第二轮排序:四个一组进行归并。第三轮排序:得到最终排序结果。博学多识算法远不止日常我们所熟知的查找算法和排序算法等,当前,算法技术广泛渗入互联网应用中,在给用户带来一定程度便利的同时,也可能侵害用户的权益。例如,通过大数据“杀熟”实施不合理的差别待遇,利用算法诱导用户过度消费,刷销量、控制评论影响网络舆论,等等。中国电子技术标准化研究院党委书记建议,应加强算法安全技术能力建设,建设算法推荐服务备案、算法安全评估、算法安全风险检测等平台,提升算法推荐技术监管能力。数据结构概述6.3数据结构概述6.36.3.1数据结构的基本概念6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行效率或存储效率。数据结构往往同高效的检索算法和索引技术有关。数据结构具体指同一类数据元素中各元素之间的相互关系,包括数据的逻辑结构、数据的存储结构和数据的运算结构。数据结构概述6.36.3.2线性结构与非线性结构6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为两类:线性结构和非线性结构。(1)线性结构。线性结构是一个非空的数据集合,有且只有一个根节点,每一个节点最多只有一个前驱,也最多只有一个后继。常见的线性结构有线性表、栈(stack)、队列(queue)和线性链表等。(2)非线性结构。不满足线性结构的数据结构即为非线性结构。常见的非线性结构有树、二叉树和图等。数据结构的分类6.4数据结构的分类6.46.4.1线性表6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。1.线性表的定义线性表是线性结构的一种表现形式。它的特点是数据的元素在非空有限集{Ф}中存在唯一被称为“第一个”的数据元素,并存在唯一被称为“最后一个”的数据元素。除第一个元素之外,集合中的每个数据元素均只有唯一的前驱;除最后一个元素之外,集合中的每个数据元素均只有唯一的后继。数据结构的分类6.42.线性表的特征6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。(1)集合中必存在唯一的“第一元素”。(2)集合中必存在唯一的“最后元素”。(3)除最后一个元素之外,均有唯一的后继。(4)除第一个元素外,均有唯一的前驱。数据结构的分类6.43.线性表的插入运算6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。在顺序表A中下标为k的节点后插入值为i的节点,length为顺序表当前的长度。在保证表未满且插入位置合法的情况下,将顺序表A中下标大于或等于k+1的元素都向后移动一个位置。算法描述如下:(1)如果k<0或者k>length或者length=Maxsize,则插入位置不合法。(2)若插入位置合法,则从后向前将下标大于等于k+1的元素都向后移动一个位置。(3)将待插入元素i存储在k+1的位置上,length=length+1。数据结构的分类6.44.线性表的删除运算6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。顺序表非空且删除位置合法的前提下,删除顺序表中的元素只需要从前向后将顺序表中下标大于或等于k的节点均向前移动一个位置。算法描述如下:(1)如果删除位置不合法,则输出提示“删除不合法”。(2)若删除位置合法,则从前向后将下标大于或等于k的元素都向前移动一个位置。(3)length=length-1。数据结构的分类6.46.4.2栈和队列6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。1.栈及其基本运算栈也叫堆栈,它是一种特殊的线性表,即允许在表的同一端进行插入和删除操作,且这些操作都按后进先出的原则进行。栈可以表示如下:S=(a1,a2,a3,a4,a5,a6)将进行插入和删除的一端称为栈顶,不允许插入和删除的一端称为栈底,则在栈S中,a1为栈底元素,a6为栈顶元素,栈的示意图如图6-4-1所示。数据结构的分类6.41.栈及其基本运算6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。栈的基本运算有以下几种:(1)入栈(push):压入一个元素。(2)出栈(pop):弹出一个元素(删除）。(3)栈顶元素操作(peek):存取栈顶元素的值。(4)清空(clear):清空栈。(5)判断栈是否为空。数据结构的分类6.42.队列及其基本运算6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。队列是一种允许在一端进行插入,而在另一端进行删除的线性表。允许进行删除运算的一端称为队头,允许进行插入运算的一端称为队尾。例如,有一个队列Q=(q1,q2,q3,q4,q5,q6),则q1为队头元素,q6为队尾元素。队列操作按照“先进先出”或“后进后出”的原则进行。队列的示意图如图6-4-2所示。数据结构的分类6.42.队列及其基本运算6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。列的基本运算如下:(1)入队:向队尾添加元素。(2)出队:删除队首元素。(3)存取:获取队首的元素值。(4)判断队列是否为满。(5)判断队列是否为空。在实际应用中,队列一般采用循环队列的形式,也就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环形结构。在循环队列中,当队头=队尾时,不能判断队列是空还是满,在实际应用中还需要增加一个标志来区分队列是空还是满。数据结构的分类6.46.4.3线性链表6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。在顺序表结构中,插入或删除一个元素需要移动相当数量的元素,各个元素的地址也会产生变化,消耗了很多资源。为了解决这一问题,必须给出一种新的存储方式。用链接存储方式存储的线性表称为链表。在链表存储方式中,每个节点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中指针用于指向该节点前一个或后一个节点。链表主要有三种实现方式:单链表、双向链表和循环链表。数据结构的分类6.41.单链表6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。单链表是一个仅有一个数据域和一个指针域的链表结构,指向第一个节点的指针是一个特殊的指针,称为这个链表的头指针(head)。单链表节点示意图如图6-4-3所示。在图6-4-3中,数据域存放节点的数据值,指针域存放节点的直接后继地址。链表通过节点的指针域将线性表的n个节点按照逻辑顺序链接在一起。图6-4-4为单链表存储示意图。数据结构的分类6.42.双向链表6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。在某些应用中,对线性链表中的每个节点设置两个指针,一个称为左指针,用于指向其前驱节点;另一个称为右指针,用以指向其后继节点。这样的链表称为双向链表。图6-4-5为一个线性表(1,2,3)在计算机内部使用双向链表存储的示意图。第一个节点的左指针和最后一个节点的右指针为空,使用“Λ”来表示。数据结构的分类6.43.循环链表6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。在单链表的第一个节点前增加一个表头节点,队头指针指向表头节点,最后一个节点的指针域的值由空改为指向表头节点,这样的链表称为循环链表。在循环链表中,所有节点的指针构成了一个环状链。图6-4-6所示为循环链表存储示意图。数据结构的分类6.46.4.4树与二叉树6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。1.树树结构是一种非线性存储结构,存储的是具有“一对多”关系的数据元素的集合。图6-4-7所示为使用树结构存储的集合{A,B,C,D,E,F,G,H,I}。节点A和节点B、C有关系;节点C和E、F有关系,这就是“一对多”的关系。树是由n个有限节点组成的一个具有层次关系的集合。当n=0时,称为空树。把它称为树,是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。数据结构的分类6.46.4.4树与二叉树6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。1.树在任何非空树中:(1)有且只有一个特定的称为根的节点。(2)当n>1时,其余节点可分为m个互不相交的有限集,其中每一个集合又是一棵树,称为根的子树。树是由根节点和若干棵子树构成的,由一个集合及在该集合上定义的一种关系组成。集合中的元素称为树的节点,所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位,这个节点称为树的根节点,或者称为树根。数据结构的分类6.42.二叉树6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。(1)二叉树的特点。二叉树是一种非线性结构,其示意图如图6-4-8所示。二叉树具有以下两个特点:①非空二叉树只有一个根节点。②每一个节点最多只有两棵子树,分别称为该节点的左子树和右子树。数据结构的分类6.42.二叉树6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。(2)二叉树的存储结构。二叉树的存储方式分为两种,顺序存储和链表存储。①顺序存储。数组方式存储,表现上是一个一维数组,逻辑上是一棵二叉树。②链表存储。二叉树节点由一个数据元素和分别指向其左、右子树的两个分支构成,表示二叉树的链表中的节点至少包含3个域:数据域和左、右指针域。采用链表的方式进行存储,可以清楚地表明二叉树节点间的逻辑关系。链表存储从表现到逻辑都是一棵二叉树。数据结构的分类6.42.二叉树6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。(3)二叉树的遍历。二叉树的遍历包括三种方式,前序遍历、中序遍历和后序遍历。①前序遍历。先访问根节点,然后遍历左子树,最后遍历右子树。在遍历左右子树时,仍然先访问根节点,然后遍历左子树,最后遍历右子树。对图6-4-8中的二叉树进行遍历的结果是F,B,A,D,C,E,G,I,H。②中序遍历。先遍历左子树,然后访问根节点,最后遍历右子树。在遍历左右子树时,仍然遍历左子树,然后访问根节点,最后遍历右子树。对图6-4-8中的二叉树进行遍历的结果是A,B,C,D,E,F,G,H,I。数据结构的分类6.42.二叉树6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。③后序遍历。先遍历左子树,然后遍历右子树,最后访问根节点。在遍历左右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根节点。对6-4-8中的二叉树进行遍历的结果是A,C,E,D,B,H,I,G,F。数据结构的分类6.46.4.5图6.2.1查找算法经过三轮排序,初始序列就按照从小到大的顺序排好了。1.图的基本概念图是由顶点的有穷非空集合和顶点之间边的集合组成的,通常表示为G(V,E)。其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。图至少有一个顶点,图的顶点集V一定非空,但边集E可以为空,此时图中只有顶点而没有边。图有两种基本结构,即有向图和无向图。数据结构的分类