计算机导论课件：算法与数据结构

4.1算法4.2数据结构算法与数据结构4.1算法4.1.1算法描述一个问题可以有多种求解方法，一个求解方法可以有多种描述形式。如果在人与人之间交流，可以采用自然语言、示例、图、表、公式等描述形式；如果在人与计算机之间交流，则只能采用程序设计语言，因此程序也称为程序设计语言描述的算法。下面，通过一个例子介绍不同的算法描述形式。例4-1求解两个正整数的最大公约数。针对这个问题，给出两种求解方法：穷举法和辗转相除法，每种方法给出三种描述形式：自然语言形式、流程图形式和程序设计语言(C语言)形式。1．穷举法(1)穷举法的自然语言形式如下：①令S为两个正整数M、N中的较小者；②令R1为M除以S的余数，R2为N除以S的余数；③若R1与R2同时等于0，则S就是两个正整数的最大公约数，否则令S为S减1，返回②继续。穷举法的流程图形式如图4-1所示。(2)穷举法的程序设计语言形式如下：intgreatest_common_divisor(intm,intn){ints,r1,r2;if(m>n)s=n;elses=m;r1=m%s;r2=n%s;while(r1!=0||r2!=0){s=s-1;r1=m%s;r2=n%s;}return(s);}2．辗转相除法(1)辗转相除法的自然语言形式如下：①令M为两个正整数中的较大者，N为较小者；②令R为M除以N的余数；③若R等于0，则N就是两个正整数的最大公约数；否则令M为N，N为R，返回②继续。(2)辗转相除法的程序设计语言形式如下：intgreatest_common_divisor(intm,intn){intr;if(m<n){r=m;m=n;n=r;}r=m%n;while(r!=0)

{m=n;n=r;r=m%n;}return(n);}辗转相除法的流程图形式如图4-2所示。4.1.2算法分析前面提到，一个问题可以有多个求解算法，究竟哪个算法好呢？这就是算法分析的任务。算法分析，也称为算法复杂性分析，是对运行算法所消耗的资源进行分析。算法消耗的资源越多，算法复杂性就越高。资源可以分为时间资源(运行时间)和空间资源(内存空间)，因此，算法复杂性分析也分为时间复杂性分析和空间复杂性分析。例4-2直观分析例4-1给出的两个算法——穷举法和辗转相除法。穷举法和辗转相除法的算法分析如表4-1所示。如果选择变量数目作为空间度量，则穷举法需要5个变量M、N、S、R1、R2，辗转相除法需要3个变量M、N、R，辗转相除法优于穷举法。如果选择循环语句执行次数作为时间度量，则当M = 30，N = 15时，穷举法和辗转相除法都是0次循环，而当M = 30，N = 16时，穷举法是14次循环，辗转相除法是2次循环。可以看到，不同的M和N，同一算法的循环次数也不同，因此，时间复杂性有最好情况、最坏情况、平均情况三种。从平均情况来看，辗转相除法优于穷举法。事实上，当进行算法复杂性分析时，不可能也没必要如例4-2一样，针对特定输入分析算法的变量数目和基本语句执行次数，而是分析随着问题规模的增长，复杂性增长的量级。例如，算法的时间复杂性与算法本身、问题规模n相关，当算法确定时，算法的时间复杂性就是n的函数T(n)，并且通常采用渐进上界O(f(n))表达其时间复杂性增长的量级。如果算法的时间复杂性过高，则该算法可能是理论可计算，而实际不可计算。例如，时间复杂性为O(2n)的算法，随着问题规模n的增加，运行时间呈指数增加，算法就是理论可计算而实际不可计算。4.1.3算法设计1.分治与递归计算机求解问题所需时间一般都与问题规模相关，问题规模越小，所需时间越少，也较容易处理。分治是将一个难以直接解决的规模较大的原问题分解成一系列规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。分治是算法设计的基本策略，包括三个步骤：(1)分解：将原问题分解成一系列子问题。(2)求解：求解各个子问题。(3)合并：合并子问题的解得到原问题的解。在算法设计中，递归与分治就像孪生兄弟，密切相关。递归是指函数(或过程)直接调用自己或通过一系列调用语句间接调用自己。通常，递归用于解决结构自相似问题，即构成原问题的子问题与原问题在结构上相似，可以采用类似方法求解。递归是描述问题和解决问题的基本方法，包括两个要素：(1)边界条件：确定递归何时终止，也称为递归出口。(2)递归模式：确定原问题如何分解为子问题，也称为递归体。例4-3求解n!。方法一：n!可以展开为n! = n*(n-1) * (n-2)*…*3*2*1，可以采用循环求解，流程图如图4-3所示，程序如下：intfactorial(intn){intp,m;p=1;m=1;while(m<=n){p=p*m;m=m+1;}return(p);}方法二：n! 也可以写成递归形式，即递归体：n! = n*(n-1)!，递归出口：1!=1，可以采用递归求解，求解过程如图4-4所示，程序如下：intfactorial(intn){intp;if(n==1)p=1;elsep=n*factorial(n-1);return(p);}2.动态规划当采用分治与递归设计算法时，原问题的一系列子问题最好相互独立，否则会因为重复求解公共子问题而导致效率低下。如果子问题相互重叠，通常可以采用动态规划。动态规划对每个子问题只求解一次并将解保存在表格中，当需要再次求解该子问题时，通过查表获得其解，从而避免重复求解公共子问题。例4-4计算2阶Fibonacci序列的第n项，公式如下：方法一：上述公式本身就是递归描述，即递归体：fn = fn-1 + fn-2，递归出口：f0 = 0，f1 = 1。递归求解过程中的子问题如图4-5所示，程序如下：intfibonacci(intn){intp;if(n==0)p=0;if(n==1)p=1;if(n>=2)p=fibonacci(n-1)+fibonacci(n-2);return(p);}从图4-5可以看到，在f5的递归计算中，有许多子问题被重复计算，如f3被重复计算了2次，f2被重复计算了3次。随着n的增加，这个现象更加突显，严重影响计算效率。方法二：采用动态规划，即颠倒计算方向，将自顶而下计算变为自底而上计算，对每个子问题仅计算一次并将解保存在表格中，当需要再次计算该子问题时，通过查表获得其解，从而避免重复求解公共子问题，程序如下：intfibonacci(intn){intp,f[100],i;if(n==0)p=0;if(n==1)p=1;if(n>=2){f[0]=0;f[1]=1;for(i=2;i<=n;i++)f[i]=f[i-1]+f[i-2];p=f[n];}return(p);}动态规划求解过程中的表格如表4-2所示。4.2数据结构4.2.1基本概念数据结构是相互之间存在一种或多种特定关系的数据元素的集合。所谓数据元素是在程序中作为一个整体进行考虑和处理的数据的基本单位，可由若干个数据项组成。例4-5如图4-6所示，在职工管理中，一个职工的信息就是一个数据元素，可由职工号、姓名、性别、出生年月等数据项组成。数据结构的研究内容包括：(1)数据的逻辑结构：研究数据元素之间的逻辑关系。(2)数据的存储结构：研究数据元素及其关系在计算机中的表示与存储。(3)基本操作的算法：研究当某种逻辑结构采用某种存储结构实现时，基本操作的算法及复杂性。数据结构的研究内容如图4-7所示。逻辑结构可以分为线性结构、树结构、图结构，存储结构可以分为顺序存储结构和链式存储结构。例4-6在职工管理中，n个职工的信息是n个数据元素，它们的逻辑结构可以看做线性结构中的线性表，即数据元素之间的逻辑关系是线性关系，而且可以在任一位置删除或者插入一个数据元素，如图4-8所示。线性表的顺序存储结构可以采用C语言中的数组实现，一个数组元素存储一个数据元素，数据元素之间的逻辑相邻采用数组元素之间的物理相邻表示，顺序存储结构如图4-9所示。线性表的链式存储结构可以采用C语言中的指针实现，如图4-10所示，一个结点存储一个数据元素，数据元素之间的逻辑相邻采用结点之间的指针表示。4.2.2线性结构线性结构是指数据元素之间的逻辑关系是线性关系(一对一关系)。第一个数据元素没有前驱，只有唯一后继，最后一个数据元素没有后继，只有唯一前驱，其它数据元素有唯一前驱和唯一后继。如图4-12所示，圆圈表示数据元素，线表示数据元素之间的关系。根据线性结构中数据元素的操作限制，线性结构分为以下几个：(1)线性表：允许在任一位置进行插入和删除操作。(2)堆栈：只允许在一端进行插入和删除操作。这一端称为栈顶，另一端称为栈底，如图4-13所示。堆栈的特点是先进栈的数据元素后出栈，称为先进后出(FirstInLastOut，FILO)。(3)队列：只允许在一端进行插入操作，在另一端进行删除操作。插入一端称为队尾，删除一端称为队头，如图4-14所示。队列的特点是先进队的数据元素先出队，称为先进先出(FirstInFirstOut，FIFO)。4.2.3树结构树结构是一种非常重要的数据结构。树的递归定义为：没有结点(数据元素)的树称为空树。在非空树中，有且仅有一个结点称为根结点，其余结点可分为若干互不相交的集合，每个集合又是一棵树，称为根结点的子树。结点的子树数目称为结点的度。除根结点外，度为0的结点称为叶子结点，度不为0的结点称为内部结点。结点的子树根结点称为该结点的子结点，相应地，该结点称为子树根结点的父结点。根结点没有父结点，可以有若干子结点；叶结点没有子结点，只有唯一父结点；内部结点只有唯一父结点，可以有若干子结点。因此，树结构是指数据元素(结点)之间的逻辑关系是一对多关系(分支)，一个父结点可以有若干子结点，一个子结点只有唯一父结点，如图4-15所示。二叉树是一种应用广泛的特殊的树结构，它的递归定义是：没有结点(数据元素)的二叉树称为空树。在非空二叉树中，有且仅有一个结点称为根结点，其余结点可分为两个互不相交的集合，每个集合又是一棵二叉树，分别称为根结点的左子树和右子树。二叉树的特点是任意结点至多有二个子结点，子结点有左右之分，如图4-16所示。二叉排序树又是一种用于查找的特殊的二叉树，它的特点是：对于任意结点，若它的左子树不空，则左子树上所有结点的值均小于它的值；若它的右子树不空，则右子树上所有结点的值均大于它的值，如图4-17所示。4.2.4图结构图结构是比树结构更复杂的一种数据结构。如图4-18所示，在图结构中，数据元素(顶点)之间的逻辑关系是多对多关系(边)。根据边是否有方向，可将图分为有向图(如图4-18(a)所示)和无向图(如图4-18(b)所示)。在无向图