计算机基础（第2版）课件第4章 数据结构与算法基础

第4章数据结构与算法基础4数据结构与算法基础4.1算法和算法分析4.2数据结构的基本概念4.3数据结构的分类及表示4.4线性结构4.1

算法和算法分析

算法的概念算法的特征

算法的效率4.1.1算法的概念通俗地讲,算法是解决问题的方法；严格地说，算法是对特定问题求解步骤的一种描述,是指令的有限序列。对于一个问题，如果可以通过一个计算机程序,在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序,也不等于计算方法。当然，程序也可以作为算法的一种描述,但程序通常还需考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。通常,程序的编制不可能优于算法的设计。4.1.2算法的特征作为一个算法，一般应具有以下几个基本特征。(1)可行性(Eflectiveness)算法的可行性包括以下两个方面。①算法中的每一个步骤必须能够实现。如在算法中不允许出现分母为0的操作，在实数范围内不可能求一个负数的平方根等。②算法执行的结果要能够达到预期的目的。针对实际问题设计的算法,人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的、因此,算法在执行过程中往往要受到计算工具的限制,使执行结果产牛偏差。例如，A/B*C与A*C/B,如果B的数据类型是整型与B的数据类型是实型，可能会产生不同的结果。因此,算法与计算公式是有差别的。在设计一个算法时,必须要考虑它的可行性,否则是不会得到满意结果的。4.1.2算法的特征(2)确定性(Definiteness)算法的确定性,是指算法中的每一个步骤都必须是有明确定义的,不允许有模梭两可的解释,也不允许有多义性。这一性质也反映了算法与数学公式的明显差别。在解决实际问题时,可能会出现这样的情况:针对某种特殊问题，数学公式是正确的,但按此数学公式设计的计算过程可能会使计算机系统无所适从。这是因为根据数学公式设计的计算过程只考虑了正常使用的情况，而当出现异常情况时,此计算过程就不能适应了。(3)有穷性(Finiteness)算法的有穷性，是指算法必须在有限的时间内做完，即算法必须在执行有限步骤之后终止。数学中的无穷级数、在实际计算时只能取有限项,即计算无穷级数值的过程只能是有穷的。因此，一个数的无穷级数表示只是一个计算公式,而根据精度要求确定的计算过程才是有穷的算法。算法的有穷性还应包括合理的执行时间的含义。因为、如果一个算法需要执行千万年,显然失去了实用价值。4.1.2算法的特征(4)拥有足够的情报一个算法是否有效，还取决于为算法所提供的情报是否足够。通常,算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态,这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关,不同的输入将会有不同的结果输出。当输入不够或输入错误时,算法本身也就无法执行或导致执行有错。一般来说．当算法拥有足够的情报时，此算法才是有效的，面当提供的情报不够时,算法可能无效。综上所述，所谓算法。是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。4.1.3算法的效率(1)设计一个好的算法通常需要考虑以下几方面的要求。①正确性。要求算法能够正确地执行预先规定的功能,并达到所期望的性能要求。②可读性。为了便于理解、测试和修改算法,算法应该具有良好的可读性。③健壮性。当输入非法的数据时,算法应能恰当地做出反应或进行相应处理,而不是产生莫名其妙的输出结果。并且处理出错的方法不应是中断程序的执行,而是返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理。④高效性。要求算法的执行时间要尽可能短，算法的效率就越高。⑤低存储量。完成相同的功能,执行算法时所占用的附加存储空间要尽可能地少。4.1.3算法的效率(2)考虑算法的效率问题，即算法的时间效率(所需运算的时间)和空间效率(所占存储空间)两方面。一般情况下，鉴于运算空间(内存)较为充足，所以把算法的时间复杂度作为重点分析。①时间复杂度(TimeComplexity)一个算法所需的运算时间通常与所解决问题的规模大小有关。问题规模是一个和输入有关的量，用n表示问题规模的量。通常把算法运行所需的时间T表示为n的函数，记为T(n)。当n逐渐增大时T(n)的极限情况，一般简称为时间复杂度。随着数据输入规模的增大,fn)的增长率与T(n)的增长率相近，因此、T(n)同f(n)在数量级上是一致的。记作T(n)=O(f(n))。算法时问复杂度的数量级越大，表示该算法的效率越低，反之越高。例如,O(1)为常数数量级,即算法的时间复杂性与输人规模n无关。4.1.3算法的效率②空间复杂度(SpaceComplexity)一个算法的空间复杂度是指程序运行开始到结束所需要的存储空间。类似于算法的时间复杂度,算法所需存储空间的量度记作S(n)=O(f(n))。其中n为问题的规模,一个程序上机执行时,除了需要存储空间来存放本身所用的指令、常数、变量和输入数据以外,还需要一些对数据进行操作的工作单元和实现算法所必需的辅助空间。在进行时间复杂度分析时,如果所占空间量依赖于特定的输入,一般都是按最坏情况来分析。4.2

数据结构的基本概念1.什么是数据数据Data:客观事物的符号表示。在计算机学科中，数据的概念被大大的扩充了,不仅包含数学中的整数实数，任何能用计算机识别的符号都可作为数据。例如,课程名、地名、书名都是数据。2.什么是程序程序描述了数据加工处理的过程,即程序的任务是对数据进行加工处理。3.什么是程序设计程序设计是将问题的求解过程用某种计算机语言表达出来。为编写程序,首先要分析实际问题所涉及的对象，要解决数据如何表达、如何存储、如何处理的问题。数据结构就是研究关于数据表达,数据存储及数据处理的方法。有些计算机专家认为程序设计=数据结构＋算法。4.2

数据结构的基本概念4.数据结构的有关概念数据Data:客观对象的符号表示。在计算机科学中,数据的含义非常广泛,我们把一切能够输人计算机中并被计算机程序处理的信息,包括文字、表格,图像等,都称为数据。例如,课程名、地名、书名都是数据。再如,一个个人书库管理程序所要处理的数据可能是一张。数据元素DataElement:数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。如在表4-1所示的个人书库中，为了便于处理，把其中的每一行(代表一本书)作为一个基本单位来考虑,故该数据由10个数据元素构成。一般情况下，一个数据元素中含有若干个数据项数据结构DataStructure:相互之间存在一种或多种特定关系的数据元素的集合，即带结构的数据元素的集合。4.2

数据结构的基本概念数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题。(1)数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。数据元素之间的逻辑关系如下。a.元素之问没有关系——集合b.元素之间具有线性关系——线性数据结构(线性表结构)c元素之间具有层次关系——层次数据结构(树结构)d.元素之间具有网状关系——网状数据结构(图结构)(2)在对数据进行处理时,各数据元素在计算机中的存储关系，即数据的存储结构。数据在计算机中的存储只有两种形式。a.顺序:数据元素逐个连续存放(通过物理相邻来确定关系)b.非顺序:数据元素任意存放(通过存储地址确定关系)(3)对各种数据结构进行的运算。4.3

数据结构的分类及表示1.常用的数据结构:现实世界中,客观事物对象之间的关系虽然形形色色,但从抽象的观点看,主要有集合、线性结构、树形结构、图状结构或网状结构。2.数据结构的表示:图示表示、二元组表示。图示表示是由顶点和边构成的图,其中顶点表示数据,边表示数据之间的结构关系。二元组表示是用一个二元组(D，S)表示数据结构，其中D是数据元素集合,S是D上关系的集合。4.4线性结构

线性表栈和队列

树与二叉树

图

查找

排序4.4.1

线性表(1)线性表的概念及特征线性表(LinearList)：由n个数据元素（结点）组成的有限序列。数据元素之间具有线性关系。其中数据元素的个数n定义为表的长度。当n=0时称为空表。常常将非空的线性表(n>0)记作L=(a1,a2,a3，…,an),其中ai是数据元素。线性结构的特征：除第一个外、每个数据元素均有且只有一个前驱元素；除最后一个外,每个数据元素均有且只有一个后继元索。线性表的特征：数据元素之间的关系是它们在数据集合中的相对位置。线性表是一种典型的线性结构。表中的每个数据元素都有一个确定的位置,ai是第i个数据元素,称i为数据元素ai在线性表中的位序。4.4.1

线性表(2)线性表的基本操作及存储结构线性表的数据元素存储方式分顺序存储和链式存储。顺序存储是指在计算机中用一-组地址连续的存储单元依次存储线性表的各个数据元素。假设存储每个元素占用L个存储单元,并且以所占的第一个单元的地址作为该元素的存储地址。线性表的顺序存储的优点:逻辑顺序与物理顺序一致，随机存取等;但是也存在一些缺点,比如插入，删除操作要移动元素;存储空间是预分配的，不灵活，空间浪费；表的存储空间难扩充等。这样就需要一种灵活的存储方式——链式存储结构。用任意存储空向单元来存放线性表的各个元素，为了能体现元素之间的逻辑关系(线性),在存放每个元素的同时，也存放相关元素的信息(相关元素的存储地址)，即用指针来表示元素之间的逻辑关系。存放一个数据元素占用的空间为结点。线性表的基本操作包括线性表的初始化、插入、删除、定位元素x在线性表中的位置,求某个元素的前驱及后继、求线性表的长度、销毁线性表等。4.4.2栈和队列(1)栈的定义及特征操作栈(stack)的定义：一种特殊的线性表(数据元素之间的关系是线性关系),其插入,删除只能在表的一-端进行,另一端固定不动。如(a1,a2,a3,…,an)是一个栈。表尾称为栈顶,表头称为栈底，即a1为栈底元素，an为栈顶元素；在表尾插入元素的操作称进栈操作,在表头删除元素的操作称为出栈操作；元素按a1,a2,a3,…,an的次序进栈,第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶，第一个出栈的元素为栈顶元素,如图4-5所示。①栈的特征及操作由于限制了插入删除只能在一端进行,那么元素的操作顺序有“先进后出"或“后进先出”的特点(LastInFirstout-LIFOFirstInlastout——FILO)。柱的基本操作包括初始化战、入栈、出栈、取栈顶元素、清空栈等操作。②栈的存储方式战的顺序存储方式同一般线性表的顺序存储结构完全相同，是利用一组连续的内存单元依次存放自找底到栈顶的数据元素，栈顶元素的位置由一个称为栈顶指针的变量指示。其中若base=NULL,则栈结构不存在;若top初始值=base，则栈为空栈;若出栈,则top=top-1:若入栈，则top=top+1，栈顶指针始终指向栈顶元素的下一个位置。栈的顺序存储方式特点:简单、方便,但易产生圈出。上溢(Overflow)栈已经满,又要压入元素;下溢(Underflow)栈已经空,还要弹出元素。上溢是一种错误，使问题的处理无法进行下去；而下溢一般认为是一种结束条件,即问题处理结束。4.4.2栈和队列(2)队列的定义及特征操作队列(Queue)的定义:是一种特殊的线性表,数据元素之间的关系是线性关系。其插入、删除分别在表的两端进行,一羹只能插入,另一端只能删除。队首(front):进行删除的一端;队尾(rear):进行插入的一端;入队:在队尾插入一个元素;出队:在队首删除一个元素。①队列的特征队列的特点:由于限制了插入、删除分别在两端进行,那么元素的操作顺序有“先进先出”或“后进后出”的特点(FirstlnFirstOut—FIFOLastInLastOut—LILO)。队列类似于日常的排队,新来的人站在队尾、队头的人进行事务处理后离队。队列通常设置两个变量分别指示队头元素位置和队尾元素的位置,这两个变量分别称为队头指针、队尾指针。如打印机队列管理。在一台打印机共享使用时,任何时刻它只能处理-一个用户的打印请求。打印任务的组织就用一个队列来组织(先请求的,先处理)。当用户发出打印请求时,把打印任务入队;当打印机空闲时,从打印队列中出队一-个任务;当打印机阻塞时,系统管理员可以清空队列。②队列的存储方式同一般线性表的顺序存储结构完全相同。但是由于在两端操作,设两个指示器(rear和front)，分别指示队列的尾和首。其中若rear=front=0，则队列为空队列;若front=rear，则队列空;若入队，则rear=rear+1;若出队，则front=front+1,栈顶指针始终指向栈顶元素的下一个位置。特别约定:头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一位置！4.4.3树与二叉树(1)树、二叉树的基本概念树(Tree)是由n个结点的有限集合。如果n=0，称为空树；如果n>0,则有且仅有一个特定的称为根(Root)的结点,它只有直接后维，但没有直接前驱;当n>1,除根以外的其他结点划分为m(m>0)个互不相交的有限集T1,T2，….Tm,其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。二叉树的定义:二叉树或为空树;或是由一个根结点加上两裸分别称为左子树和右子树的、互不相交的二叉树组成。二又树中每个结点至多只有两棵子树(二叉树中不存在度大于2的结点)。两种特殊形态的二叉树:满二叉树(FullBinaryTree)——一棵深度为k且有2k-1个结点的二叉树称为满二叉树；完全二叉树(CompleteBinaryTree)——若设二叉树的高度为h,则共有h层。除第h层外,其他各层(0—h-l)的结点数都达到最大个数,第h层从右向左连续缺若干结点,这就是完全二叉树。4.4.3树与二叉树

4.4.3树与二叉树二叉树由根(Root)、左子树(Leftchild)、右子树（Rightchild)三部分组成。二叉树的遍历可以分解为访问根、遍历左子树和遍历右子树。约定先左后右，有种遍历方法，即DLR,LDR,LRD，分别称为先序遍历、中序遍历、后序遍历。先序遍历(DLR)的方法:若二叉树非空,访问根结点；先序遍历左子树；先序遍历右子树。中序遍历(LDR)的方法:若二叉树非空,中序遍历左子树；访问根结点；中序遍历右子树。后序遍历(LRD)的方法:若二叉树非空，后序遍历左子树;后序历右子树，访问根结点。4.4.4图(1)图的概念和存储图是由顶点集合（vertex）及顶点问的关系集合组成的一种数据结构：Graph=（V，E），其中V

=

{x

|

x

属于某个数据对象}是顶点的有穷非空集合；E1=

{（x,y）|x,y属于V}E2

={<x,y>1|x,y属于V&&

Path（x,y）}。其中，E1是顶点之间关系的有穷集合，也叫作边（edge）集合，此时的图称为无向图。E2

表示从x到y的一条弧，且称x为弧尾，y为弧头，这样的图称为有向图。

图是多对多的结构，比线性结构、树结构复杂，所以其存储结构也要复杂些。与线性结构、树结构一样，图的存储结构至少要保存两类信息：1）顶点的信息；2）顶点间的关系。顶点的编号:为了使图的存储结构与图一一对应,在讨论图的存储结构时,首先要给图的所有顶点编号。图的存储方式主要包括数组表示法和邻接表表示法。数组表示法也叫作邻接矩阵、在图的邻接矩阵表示中,有一个记录各个顶点信息的顶点表,还有一个表示各个顶点之问关系的邻接矩阵。4.4.4图(2)图的遍历及最小生成树从图中某顶点出发访遍图中所有的顶点,且使每个顶点仅被访问一次,这一过程就叫作图的遍历(TraversingGraph)。图中可能存在回路。且图的任一顶点都可能与其他顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问,可设置一个标志顶点是否被访问过的辅助数组visited[1。辅助数组visited[1的初始状态为0，在图的遍历过程中,一旦某一个顶点i被访问,就立即让visited[i]为1，防止它被多次访问,两种图的遍历方法:深度优先搜索DFS(DepthFirstSearch)，广度优先搜索BFS(BreadthFirstSearch)。最小生成树:在n个城市之间建立通信网络,则连通n个城市只需要n-1条线路，这是一个生成树概念的应用问题。如何构造一个造价最低的通信网络呢?在n个城市之间,最多可能设置的直接线路是n(n-1)/2条，每一条线路都有一个造价预算,如何在这些可能的线路中选择n-1条以使总的耗费最少而又实现通信网络呢?4.4.4图可以用连通网表示n个城市及n个城市之问可能设置的通信线路,其中顶点表示城市,边表示两城市之间的通信线路,边上的权值表示线路造价预算。n个顶点的连通网可以有多个生成树,每一棵生成树都可以是一个通信网络。一棵生成树的代价定义为生成树上各边权值之和。要选择一棵总耗费最少的生成树是我们要解决的问题使用不同的遍历图的方法，可以得到不同的生成树;从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。构造最小生成树的准则:1必须使用且仅使用该网络中的n-1条边来联结网络中的n个顶点;2不能使用产生回路的边;3各边上的权值的总和达到最小。4.4.5查找查找是数据处理领域中的一个重要内容,查找的效率将直接影响到数据处理的效率,查找是指在一个给定的数据结构中查找某个指定的元素。通常,根据不同的数据结构,应采用不同的查找方法。(1)顺序查找顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素,其基本方法是从线性表的第一个元素开始,依次将线性表中的元索与被查元素进行比较,若相等则表示找到(查找成功):若线性表中所有的元素都与被查元素进行了比较但都不相等,则表示线性表中没有要找的元素(查找失败)。在进行顺序查找过程中,如果线性表中的第一个元素就是被查找元素,则只需做一次比较就查找成功,查找效率最高；但如果被查的元素是线性表中的最后一个元素,或者被查元素根本不在线性表中,则为了查找这个元素需要与线性表中所有的元素进行比较,这是顺序查找的最坏情况。在平均情况下,利用顺序查找法在线性表中查找一个元素,大约要与线性表中一半的无素进行比较。由此可以看出,对于大的线性表来说,顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找。如果线性表为无序表(表中元素的排列是无序的),则不管是顺序存储结构还是链式存储结构,都只能用顺序查找。即使是有序线性表,如n采用链式存储结构,也只能用顺序查找。4.4.5查找(2)二分法查找二分法查找(又称对分查找)只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(从小到大，但允许相邻元素值相等)。设有序线性表的长度为n,被元素为x，则对分查找的方法如下。将x与线性表的中间项进行比较,若中间项的值等于x,则说明查到,查找结束;若x小于中间项的值,则在线性表的前半部分(中间项以前的部分)以相同的方法进行查找;若x大于中间项的值,则在线性表的后半部分(中间项以后的部分)以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。显然,当有序线性表为顺序存储时才能采用二分查找，并且,二分查找的效率要比顺序查找高得多。可以证明,对于长度为n的有序线性表,在最坏情况下,二分查找只需要比较logn次,而顺序查找需要比较n次。4.4.6排序排序也是数据处理的重要内容。所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多,根据待排序序列的规模以及对数据处理的要求,可以采用不同的排序方法。本节主要介绍一些常用的排序方法。排序可以在各种不同的存储结构上实现。在本节所介绍的排序方法中，其排序的对象一般认为是顺序存储的线性表,在程序设计语言中就是一维数组。(1)交换类排序所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属丁交换类的排序方法。4.4.6排序①冒泡排序法:冒泡排序法是一种最简单的交换类排序方法,它是通过相邻数据元素的交换逐步将线性表变冒泡排序法的基本过程如下:首先,从表头开始往后扫描线性表,在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中、前面的元素大于后面的元素,则将它们互换,称为消去了一个递序。显然，在扫描过程中，不断地将两相邻元索中的大者往后移动，最后就将线性表中的最大者换到了表的最后,这也是线性表中最大元素应有的位置。然后,从后到前扫描剩下的线性表，同样,在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中、后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然,在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面,这也是线性表中最小元素应有的位置。对剩下的线性表重复上述过程、直到剩下的线性表变空为止,此时的线性表已经变为有序。在上述排序过程中，对线性表的每一次来回扫描后,都将其中的最大者沉到了表的底部、最小者像气泡一样冒到表的前头。冒泡排序由此而得名,且冒泡排序又称下沉排序。假设线性表的长度为n，则在最坏情况下,冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。但这个工作量不是必需的、一般情况下要小于这个工作量。4.4.6排序②快速排序法:在前面所讨论的冒泡排序法中,由于在扫描过程中只对相邻两个元素进行比较,因此,在互换两个相邻元素时只能消除一-个逆序。如果通过两个(不是相邻的)元素的交换,能够消除线性表中的多个逆序，就会大大加快排序的速度。显然，为了通过一次交换能消除多个逆序、就不能像冒泡排序法那样对相邻两个元素进行比较，因为这只能使相邻两个元素进行交换,从而只能消除一个逆序。下面介绍的快速排序法可以实现通过一次交换而消除多个逆序。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快,因此,称为快速排序法。快速排序法的基本思想如下。从线性表中选取一个元素,设为T,将线性表后面小于T的元素移到前面,而前面大于T的元素移到后面，结果就将线性表分成了两部分(称为两个子表)，T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割,就以T为分界线,将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T,而后面子表中的所有元素均不小于T。如果对分