《算法与数据结构》PPT课件.ppt

1、第三章 算法与数据结构,设计程序首先要了解需要研究要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤,模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来 本章着重讨论解决问题的核心 - 算法以及算法的处理对象 - 数据的结构,31算法,解题过程的准确、完整的描述称作解该问题的算法 程序就是用计算机语言表述的算法，流程图就是图形化了的算法 程序算法数据结构 3.1.1 算法的两要素 算法由操作与控制结构两要素组成 1.操作,(1) 逻辑运算： “与”、“或”、“非”； (2) 算术运算： 加、减、乘、除； (3) 数据比较： 大于、小于、等于、不等于； (4) 数据传送： 输入、

2、输出、赋值。,2. 控制结构,算法的控制结构，决定了各操作的执行次序。用流程图 可以形象地表示出算法的控制结构 任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成,3.1.2 算法的特征,1. 算法是由一套计算规则组成的一个过程 2. 组成算法的规则是确定的、可执行的 3. 每种算法必须有确定的结果，产生一个或多个输出 4. 每个算法必须有0个（自动生成初始数）或多个输入 5. 解答必须在有限步内得到,不能出现“死循环” 我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答,3.1.3 算法的表示,算

3、法设计一般是由粗到细的过程，一般可以使用下面几种类型的工具描述算法: 1.自然语言 自然语言描述算法通俗易懂，但它有着难以克服的缺陷： (1) 易产生歧义性 (2) 语句繁琐冗长，很难清楚地表达算法的逻辑流程 (3) 当今的计算机尚不能处理用自然语言表示的算法 2.专用工具 常用的有流程图、PAD图和N-S图、伪代码等 3.算法描述语言 为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。在本书中为类VB语言 继续,流程图 是采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作,常用流程图符号：,返回,1.枚举法（穷举法） 基本思想是： 先依据题目的部分条件确定

4、答案的大致范围 在此范围内对所有可能的情况逐一验证，直到全部情况验证完 若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解,3.1.4 常用算法,2.迭代法,使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程 使用迭代法构造算法的基本方法是： 首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差 然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差 并认为最后一次迭代得到的近似值为问题的解。,3.递归法,如果一个过程直接或间接地调用它自身，则称该过程是递归的 例：求阶乘。 F

5、unc fac(n As Integer) If n=1 then fac=1 Else fac=n*fac(n-1) Endif,递归过程必须有一个递归终止条件， 当n=0时定义为1，是阶乘递归定义的递归出口,递归则是从函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值,4.递推法,所谓递推法，它的数学公式也是递归的。只是在实现计算时与递归相反。从给定边界出发逐步迭代到达指定计算参数。 例：求阶乘 f(n)n! n(n-1)! nf(n-1) 要计算10!，可以从递推初始条件f(0)=1出发，应用递推公式f(n)=nf(n-1)逐步求出f(1)、f

6、(2)、f(9)、最后求出f(10)的值 递推操作是提高递归函数执行效率最有效的方法，科技计算中最常见,5.分治法,解一个夏杂的问题时，尽可能地把这个问题分解为较小部分，找出各个的解，然后再把各部分的解组合成整个问题的解，这就是所谓的分治法 6.回溯法 在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解,回溯法的算法是：,Proc Backtracking(succ : Boolean) 确定起始状态值走第一步 确定下一步还有几种可能 选一可能走下一步，记住可能和本步特征 做完新一步应做的事 While 目标未达到 do 确定下一步有几种可能 While

7、 没有可能and 还有上一步 do 回退上一步 查有无下一可能 Enddo If 上一步没有了Then return (SUCC=FALSE) EndIf 选一可能走一步，记住可能和本步特征 做完新一步应做的事 Enddo return (SUCC=TRUE) End Backtracking,3.2 数据结构 3.2.1 数据结构概述 。,1数据结构的研究内容 数据的逻辑结构、数据的存储结构、数据的运算 数据的逻辑结构：Data-Structure (D,R) 其中：D是数据元素的集合，R是D上关系的集合 一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表、栈、队列

8、、串、数组和文件；非线性数据结构有树和图 程序中的数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等,2数据结构应用示例 例3.4识别“体”字的过程,按分支和层次组织的数据，称为：“树形结构”,例3.5计算机换房系统中的“多角互换问题”,数据结构叫它们为“循环链表”,例3.6 饭店服务系统中的客房预订问题,这种结构称为“队列”，是一种元素间先后次序很强的数据结构,例3.7 管理信息系统中的查询问题 各种计算机管理信息系统中，通常相关的信息(记录)组成一个文件,文件是一类很重要的数据结构,文件中的记录可

9、按顺序方式组织,顺序文件,导出的链表,为提高检索效率，可将所有选修“算法分析”课的同学记录串接到一起，这种串接称为“加链”,3.2.2 线性表,线性表的逻辑结构是n个数据元素的有限序列: (a1, a2 ,a3,an) n为线性表的长度(n0)，n=0的表称为空表 数据元素呈线性关系.必存在唯一的称为“第一个”的数据元素;必存在唯一的称为“最后一个”的数据元素； 除第一个元素外，每个元素都有且只有一个前驱元素； 除最后一个元素外，每个元素都有且只有一个后继元素。 所有数据元素ai在同一个线性表中必须是相同的数据类型,线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用

10、链式存储结构存储的线性表称为链表 线性表的基本运算主要有： (1)在两个确定的元素之间插入一个新的元素； (2)删除线性表中某个元素； (3)按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新,1.顺序表和一维数组 将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表，其下标可看成元素的相对地址 运算： (1) 插入，在线性表(a1, a2，ai，ai+1，an)的第i个位置插入元素x，算法如下：,PROC INSERT (VAR A,VAR n,i,x) If(in+1) Then ERROR(“位置不存在！”) Else F

11、or j=n Down To i A(j+1)=A(j) Next j Endif A(i)=x n=n+1 End,(2)删除：在表长为n的线性表(a1,a2,ai-1,ai,ai+1an)中删除第i个数据元素，通常还需将第i+1个至第n个元素向前推动一个位置，即(a1, a2 ,，ai-1,ai+1，an)，其算法描述如下:,PROC DELETE (VAR A,VAR n,I) If (in) Then ERROR (位置不存在！) ELSE FOR j=i TO n-1 A(j)=A(j+1) Next j n=n-1 Endif End,在顺序表中插入或删除元素时，每进行一次插入或删

12、除，都要移动近乎一半的元素。 对于长度可变的线性表，必须按可能达到的最大长度分配空间,顺序表的不足：,2链表,(1）单链表(线性链表):链式存储的线性表 结点除信息域外还含有一个指针域，用来指出其后继结点的位置 最后一个结点没有后继结点，指针它的指针域为空(记为NIL 或)。另外还需要设置一个指针head，指向单链表的第一个结点,链表的一个重要特点是插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可,插 入,删 除,(2）循环链表：循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“NIL”，而是指向头一个结点，成为一个由链指针链结的环,(3）双向链表：设有一个指向后继

13、结点的指针和一个指向前驱结点的指针,3栈,栈(STACK)也是一种特殊的线性表，是一种“后进先出”的结构，它的运算规则受到一些约束和限定，故又称限定性数据结构 (1）栈的结构特点 栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom) 栈的物理存储可以用顺序存储结构，也可以用链式存储结构,(2）栈的运算 设置一个空栈 判定栈是否为空 进栈、退栈 读取栈顶元素等,4队列,(1）队列的结构特点 队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表 表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Fro

14、nt) 队列的操作是按先进先出的原则进行的 队列的物理存储可以用顺序存储结构，也可以用链式存储结构。,(2）队列的运算：设置一个空队列；判定队列是否是空队列；入队列；出队列；读取队头元素等,如果队列的容量无法预先估计时，可以采用链表存储结构,循环队列的插入、删除,3.2.3 串,串(String)可以看作一维字符数组，但其长度不恒定，可以作删除、插入操作 许多高级语言把串作为一种单独的类型，其元素不可作四则运算 进行连接、删除、插入操作，用子串有时很方便 子串(Substring)是串的一部分，具有串的一切特征,3.2.4 树和二叉树1.树和二叉树的定义和术语,树的逻辑结构 树的形式化定义：

15、树(Tree)是由 一个或多个结点 组成的有限集合T，其中有一个特定的称为根的结点；其余结点可分为m(m0)个互不相交的有限集T1,T2,T3 ,Tm，每一个集合本身又是一棵树，且称为根的子树 用表来表示树：(A(B(E,F),C(G),D(H,I,J) 结点子树个数为结点的度,结点度的最大值为该树的度 结点B的度为2，树的度为3,0棵或多棵不相交的树的集合称为树林 二叉树是另一种重要的树形结构，其结构定义为：二叉树(Binary Tree)是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为根的左子树和右子树的、互不相交的二叉树组成 二叉树的逻辑结构： 二叉树的结点

16、的子树要区分 左子树和右子树，即使 在结点只有一棵子 树的情况下也要明确指出该 子树是左子树还是右子树,2.树的存储结构,树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定 但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理,3.二叉树的存储结构,可使用具有2个指针域的链表，LC为左指针域，指向结点的左子树，RC为右指针域，指向结点的右子树。亦可用数组的下标来模拟指针，即开辟三个一维数组DATA，LC和RC分别存放结点的元素及其左、右指针,4.树的二叉树表示,每一棵都能唯一地转换到它所对应的二叉树 转换方法：凡是兄弟就用线连接起来，对每个非终

17、端结点，除其最左孩子外，删去该结点与其他孩子结点的连线，再以根结点为轴心，顺时针旋转450,5.树和二叉树的遍历(周游),树的遍历 根据树的递归定义，有两种遍历树的方法： (1)先根(次序)遍历：若树中只有一个根结点，则访问树的根结点； 否则，首先访问树的根结点，然后依次先根遍历每棵子树。 (2)后根(次序)遍历：若树中只有一个根结点，则访问树的根结点； 否则，首先依次后根遍历每一棵子树，然后访问树的根结点。,二叉树的遍历,(3)后序遍历二叉树的算法为： 若二叉树不空，则： a) 后序遍历左子树； b) 后序遍历右子树； c) 访问根结点。 前图用后序遍历为：FEGJIHDCBA,(1)前序遍

18、历二叉树算法为： 若二叉树不空，则： a) 访问根结点； b) 前序遍历左子树； c) 前序遍历右子树。 前图用前序遍历为ABEFCGDHIJ,(2)中序遍历二叉树的算法为： 若二叉树不空，则作： a) 中序遍历左子树； b) 访问根结点； c) 中序遍历右子树。 前图用中序遍历为：EFBGCHIJDA,3.2.5 图1.图的概念和术语,常用G=(V,E)代表一个图，V是结点的有穷集合(非空)，E是边的有穷集合(E可为空集)。若一条边的结点对无序，则称无向图。(V1,V2)和(V2,V1)相同 有向图由顶点的非空有限集和边的有限 集组成。(V1,V2)和(V2,V1)表示不同边 n个顶点的无向图边的最大数目是n(n-1)/2。 n个顶点的有向图边的最大数目为n2（双环且自环）。 若(V1, V2)E，则称V1和V2是相邻结点。边(V1, V2)是V1和V2相关联的边。一个结点的度是与该结点相关联的边的数目。对于有向图，则把以结点Vi为终点的边的数目称结点Vi的入度； 把以Vi为始点的边的数目称为Vi的出度。出度为0的结点称为终端结点。,2.图的存储(1)图的相邻矩阵表示法,若G是一个具有n个结点的图，则G的相邻矩阵是: (2)图的邻接表表示法 用邻接表法表示有向图，根据需要可以保存每个结点的出边表，也可以保存每个结点的入