《大学计算机基础与思维》第5章 算法与数据结构.pptVIP

5.3.6数据结构与算法的关系 * 太原理工大学.计算机科学与技术学院.计算机基础教学部 1.数据结构与算法的联系 程序=算法+数据结构。数据结构是算法实现的基础，算法总是要依赖于某种数据结构才能实现的。往往是在研究一种算法的时候就已经构建了适合于这种算法的数据结构。 算法的操作对象是数据结构，数据结构是算法设计的基础。 算法设计必须考虑到数据结构，数据结构的设计和选择需要为算法服务，知道某种数据结构的典型操作才能设计出好的算法。 2.数据结构与算法的区别： 数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。 本章小结 * 太原理工大学.计算机科学与技术学院.计算机基础教学部 一、算法 定义：是为解决问题而采用的方法或步骤， 特性：有穷性、确定性、可行性、输入可有可无、输出必须有。 表示方法：自然语言、流程图、N-S图、伪代码等。 3种结构：顺序结构：顺序结构按照顺序从上向下依次执行算法步骤 分支（选择）结构：选择结构根据给定的条件判断选择执行相应的步骤； 循环结构：循环结构在给定条件成立时，反复执行某些算法步骤。 算法质量的优劣：主要看算法的时间复杂度和算法的空间复杂度。 * 太原理工大学.计算机科学与技术学院.计算机基础教学部 二、常用的基本算法： 交换两个变量的值、累加、累乘、求最值、排序、查找等。 三、经典的算法策略思想：枚举策略、递推策略、递归策略、分治策略等。 四、数据结构 定义、内容、常见的数据结构有：数组、线性表、链表、队列、栈、树、图 五、数据结构与算法的关系： 数据结构是算法实现的基础，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。此外，数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。可以说算法是编程思想，数据结构则是这些思想的逻辑基础。 【例5-7】我国古代数学家张丘建在《张丘建算经》一书中提出了“百钱买百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？ * 太原理工大学.计算机科学与技术学院.计算机基础教学部 【分析】在本题中可以设鸡翁为x只，鸡母为y只，鸡雏为z只。由题意给出一共要用100钱买一百只鸡，可将问题简化为三元一次方程组： 　 　x+y+z=100 （1） 5x+3y+z/3=100 （2） 这里x,y,z为正整数，由于鸡和钱的总数都是100，可以确定x，y，z的取值范围：0≤x≤20、0≤y≤33、0≤z≤100。 下面用枚举的方法设计本题算法。 * 太原理工大学.计算机科学与技术学院.计算机基础教学部 算法设计一：根据问题中的约束条件，排除一些明显的不可能的情况，将可能的情况一一列举出来，即遍历x，y，z的所有可能组合，最后得到问题的解。流程图如图所示。 * 太原理工大学.计算机科学与技术学院.计算机基础教学部 算法设计二：在假设了鸡翁和鸡母的只数为x和y之后，鸡雏的数量就可确定为100﹣x﹣y，那么此时只对x，y进行枚举即可，而约束条件就只有一个5x＋3y＋z/3＝100，流程图如图5.13所示。 2.递推策略 * 太原理工大学.计算机科学与技术学院.计算机基础教学部 递推策略在数学上又称为迭代法或辗转法，其基本思想是从给定的初始条件出发，通过算法（递推公式）推出可求的新值，再由所得新值代替旧值，然后按着同样的算法（递推公式）又可求得另一个新值，依此类推，经过有限次推导，即可求得最终结果。递推的过程就是找出旧值和新值（即相邻两项或几项）之间的关系，即递推公式。然后通过给定的初始条件，再按照这一规律来计算序列中其余各项。递推策略更多地用于计算，如利用辗转相除法求两个正整数的最大公约数，就体现了这一算法思想。 * 太原理工大学.计算机科学与技术学院.计算机基础教学部 【例5-8】猴子吃桃问题。一只猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个，第二早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半再多一个。到第10天早上想再吃时，见只剩下一个桃子了。求猴子第一天共摘了多少个桃子？ 【分析】这是一个递推问题，因为猴子每次吃掉前一天的一半又多一个，则若设xn为第n天的桃子数，它就是第n-1天的桃子数的一半减1个，即 那么第n-1天的桃子数的递推公式为： 3. 递归策略 * 太原理工大学.计算机科学与技术学院.计算机基础教学部 递归策略是利用大问题与其子问题的递推关系来解决问题。它通常把一个大