数据结构与算法1资料.ppt

人类使用计算机求解实际问题的基本步骤是：首先将实际问题抽象成数学模型，即分析问题，从中抽象出操作的对象，并且找出这些操作对象之间的关系和要进行的相应操作，然后用数学的语言加以描述；其次是设计能够完成这些操作的算法；然后是编写程序实现相应的算法；最后是运行程序对实际问题进行求解。图1-1是使用计算机求解实际问题的流程图。;1.1 数据结构基础;;;1.1 数据结构基础;1.1 数据结构基础;1.1 数据结构基础;1.1 数据结构基础;(二)非线性结构 （1）树状结构 树状结构指的是数据元素之间存在着“一对多”关系的数据结构。 例如，家族的血统关系、行政人事组织结构、计算机的文件系统等问题都可以归结为树状结构。图1-3是树状结构的示意图。 ;（2）网状结构 在网状结构中，数据元素间的关系是任意的，任意两个数据元素间均可相关联，即一个结点可以有一个或多个前驱结点，也可以有一个或多个后继结点。 例如，城市道路交通、施工计划、各种网络建设等问题都可以归为网状结构。图1-4是网状结构的示意图。;（3）集合结构图 集合结构是指数据元素之间除了“同属于一个集合”外，没有其它关系，即结点之间不存在前驱和后继的关系。 例如，整数集合、实数集合、学生集合等。图1-5是集合结构的示意图。;1.1 数据结构基础;1.1 数据结构基础;1.1 数据结构基础;1.1 数据结构基础;1.1 数据结构基础;;计算机技术的每一个进步都与算法研究的突破有关。如多媒体技术的发展与数据压缩算法的研究密切相关，电子政务、电子商务、网上银行的发展离不开数据加密算法的研究。在计算机性能不断提高的同时，人类使用计算机解决的问题也在不断地变化，应用范围和规模不断增大，应用问题本身也越来越复杂。算法与计算复杂性理论表明，当问题的复杂度较高时，单纯地提高计算机性能是不能解决问题的。因此，在计算机的速度不断提高的同时，仍然需要研究算法。 ;1.2 算法设计与算法分析基础 ; 1.算法 算法是对计算机上执行的计算过程的具体描述。一个有效的算法必须满足的五个重要特性： ① 有穷性：算法必须能在有限的时间内做完不能陷入无穷循环中。 ② 确定性：算法中的每一个步骤，必须经过明确的定义，不允许有二义性。 ③ 输入：算法有0个或多个输入值 ④ 输出：算法至少有1个或多个输出值 ⑤ 可行性：算法中要做的运算都是基本运算，能够被精确地进行。 ; 2.算法与算法程序 一个计算机程序是算法的一个具体描述，同一个算法可以用不同语言编写的程序来描述。实现算法的程序应该具备如下特性： ① 正确性：一个正确的算法程序能够实现算法问题求解的功能 ② 可读性：算法程序应该是易于理解的，可读性差的程序容易隐藏较多错误而难以发现。 ③ 健壮性：当输入的数据非法时，算法程序应当能进行相应处理，而不是出现无法预知的输出结果。 ;;;;;1.2 算法设计与算法分析基础 ;;1.3 算法设计基本方法与策略基础;1.3 算法设计基本方法与策略基础;1.3 算法设计基本方法与策略基础; 1. 递推法 递推法是利用问题本身所具有的一种递推关系求解问题的一种方法。它把问题求解分成若干步，找出相邻几步的关系，从而达到求解问题的目的。 具有如下性质的问题可以采用递推法：当得到问题规模为i-1的解后，由问题的递推性质，能构造出问题规模为i的解。 【例1-10】使用递推策略计算n!（假设n=10） 分析：计算n!的问题可以写成递推公式的形式：n! =(n-1)!*n。可以看到，n!是前一项的阶乘再乘以问题规模n。所以可以从1的阶乘出发，分别求出2!、3!、......、(n-1)!，最后求出n! ; 2.递归法 递归策略是利用函数直接或间接地调用自身来完成某个计算过程。 能采用递归描述的算法通常有这样的特征：为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模n=1时，能直接得解。 ; 递归算法具有代码简洁、可读性强的优点。递归算法的缺点是运行效率较低，递归调用会由于需要频繁保存运行状态而消耗额外的时间、占用额外的空间，递归次数过多容易造成栈溢出等。 在使用递归策略时，要注意两个条件： ① 确定递归公式：函数里直接或间接调用自身； ② 确定终止条件：必须有一个明确的递归结束条件，即递归出口。 递归法一般用于解决三类问题： ①