第1章数据结构与算法培训讲学.ppt

第一章数据结构与算法第一节算法第二节数据结构的基本概念第三节线性表及其顺序存储结构第四节栈和队列第五节线性链表第六节树与二叉树第七节查找技术第八节排序技术第一节算法一、算法的基本概念所谓算法是指解题方案的准确而完整的描述。1、算法的基本特征(1)可行性:算法中的每一步操作都应该能有效执行,一个不可执行的操作是无效的。例如,一个数被0除的操作就是无效的,应当避免这种操作。(2)确定性:算法中每一步的含义必须是确切的,不可出现任何二义性,如举起手;(3)有穷性:一个算法必须在执行有限个操作步骤后终止;(4)拥有足够的情报(有零个或多个输入、有一个或多个输出)例:全真(1)-5第一节算法一、算法的基本概念2、算法的基本要素(1)算法中对数据的运算和操作算术运算:加减乘除等逻辑运算:与、或、非运算关系运算:大于、小于、等于、不等于等运算数据传输:赋值、输入、输出等运算第一节算法一、算法的基本概念2、算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。一个算法可以用顺序、选择、循环三种基本控制结构组合而成。第一节算法一、算法的基本概念2、算法设计的基本方法(4)递归:将问题逐层分解,最后把复杂问题归结为一些最简单的问题,当解决了最后那些最简单的问题后,再沿着原来分解的逆过程逐步进行综合,这就是递归的方法。(5)减半递推技术:减半递推即将问题的规模减半,然后,重复相同的递推操作。例如,一元二次方程的求解。(6)回溯法:采用试探的方法,通过对问题的分析,找出解决问题的线索,然后沿着这个线索进行试探,如果试探成功,就得到问题的解,如果不成功,再逐步回退,换别的路线进行试探。这种方法,即称为回溯法。如人工智能中的机器人下棋。第一节算法二、算法复杂度1、算法的时间复杂度(例:全真(2)-5,-2)指执行算法所需要的计算工作量。用算法在执行过程中所需基本运算的次数来衡量算法的工作量。方法:平均性态,最坏情况复杂性2、算法的空间复杂度(例:全真(5)-1,专家(1)-1)指执行这个算法所需的内存空间。例:专家(2)-1第二节数据结构的基本概念一、什么是数据结构数据结构是指相互有关联的数据元素的集合。如:春、夏、秋、冬父亲、儿子、女儿(1)数据元素有共同的特征(2)各个元素之间存在着某种关系(联系)。用前后件关系来描述。如:夏是秋的前件,秋是夏的后件。父亲是儿子和女儿的前件,儿子和女儿都是父亲的后件第二节数据结构的基本概念一、什么是数据结构1、数据的逻辑结构数据结构是指带有结构的数据元素的集合。一个数据结构应包含以下两方面的信息:(1)表示数据元素的信息(2)表示各数据元素之间的前后件关系,前后件关系是逻辑关系,与它们在计算机中的存储位置无关。数据的逻辑结构反映数据元素之间的逻辑关系。第二节数据结构的基本概念一、什么是数据结构2、数据的存储结构数据的逻辑结构在计算机中的存放形式称为数据的存储结构,也称数据的物理结构。采用不同的存储结构,数据处理的效率不同。一般情况下,数据的逻辑结构和存储结构是不同的。例:全真(3)-6