03-算法与数据结构.ppt

《03-算法与数据结构.ppt》由会员分享，可在线阅读，更多相关《03-算法与数据结构.ppt（48页珍藏版）》请在三一文库上搜索。

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个顶点的

19、无向图边的最大数目是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)图的邻接表表示法 用邻接表法表示有向图，根据需要可以保存每个结点的出边表，也可以保存每个结点的入边表,3.图的遍历 (1)深度优先遍历,基本思想是：从图

20、中某个V出发，访问此结点，再依次访问所有与V有路径的结点。完成后再另选图中一个未被访问的结点作始点，重复上述过程，直至图中所有结点都被访问到为止。 (2)广度优先遍历 基本思想是：从某个结点V出发，访问此结点，再依次访问V邻接的未访问结点。再从这些结点出发进行广度优先遍历，直至图中所有被访问过的结点的相邻结点都被访问到。完成后另选图中一个未曾访问的结点作始点，重复上述过程，直至图中所有结点都被访问到为止,3.3 查找,3.3.1 基本概念 关键字 是数据元素中可以唯一标识一个数据元素的数据项，比如学号、身份证号等， 查找 是根据给定的关键值，在一组数据中确定一个其关键字等于给定值的数据元素的过

21、程 确切定义：给定一个值K，在含有n个记录的文件中进行搜索，寻找一个其关键字等于给定的K值的记录，如找到，则输出记录或记录在文件中的相对位置称查找成功；否则输出查找不成功的信息称查找失败。,3.3.2 查找算法 1.顺序查找,顺序查找的方法是：用待查关键字值与线性表中各结点的关键字值逐个比较，直到找出相等的关键字值;或找遍所有结点都找不到,即查找失败 顺序查找的优点是对线性表结点的逻辑次序无要求,对线性表的存储结构无要求,缺点是平均检索长度长,为n/2 2.二分法查找 要求线性表结点按关键字码值排好，且以顺序方式存储 用要查找的码值X与中间位置结点的关键码值W相比较： (1)X=W，此时已经查

22、找成功，查找结束。 (2)XW,表明X在表的后半部分,取后半部分进行查找 (3)XW,表明X在表的前半部分，取前半部分进行查找 二分法查找的优点是平均检索长度小，为log2n,3.分块查找,要求文件中记录关键字“分块有序”,即前一块中最大关键字小于后一块中最小关键字,而块内的关键字不一定有序 分块查找的基本思想 ：先抽取各块中的最大关键字构成一个索引表，由于文件中的记录按关键字分块有序，则索引表呈递增有序状态。查找分两步进行:第一步先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块，第二步在已限定的那一块中进行顺序查找 用分块查找的文件不一定分成大小相等的若干块，块大小及其分法可根据文件

23、的特征来定。分块查找不仅适用于顺序方式存储的顺序表，也适用于线性链表方式存储的文件,3.4 排序 3.4.1 基本概念,设含有n个记录的文件R1，R2，Rn,其相应的关键字为K1，K2，Kn,需确定一种排列P(1),P(2)P(n)使其相应的关键字满足递增(或递减)关系： KP(1)KP(2)KP(n) 或KP(1)KP(2)KP(n) 使上述文件成为一个按其关键字线性有序的文件RP(1)，RP(2) ，RP(n)，这种运算就称为排序 内排序 指当文件的数据量不太大时，全部信息放在内存中处理的排序方法。当文件的数据量较大时，排序过程中需要在内、外存之间不断地进行数据交换才能达到排序的目的，这种

24、排序称为外排序,3.4.2 插入排序,基本思想是：每步将一个待排序的记录，按关键码值的大小插入到前面已排序的适当位置上，直到全部插完止 1. 直接插入排序：在排好的序列中用顺序法查找插入位置，找到后将其后记录后移一个位置，插入新记录。排序n个记录的文件，关键码比较次数为n2量级，记录移动个数也为n2量级 2. 二分法插入排序：在已排好序的序列中使用二分法查找插入位置，找到后移动其后记录插入新记录。关键字比较次数降为nlog2n量级，记录移动个数仍为n2量级,3.4.3 选择排序,基本思想是：每次从待排序的记录中选出关键字最小(或最大)的记录，顺序放在已排序的记录序列的最后，直到全部排完为止 3

25、.4.4 交换排序 基本思想是：两两比较待排序记录的关键码，并交换不满足顺序要求的偶对，直至全部满足为止 1.起泡排序：将待排序的记录按从后向前的顺序顺次两两比较，若为逆序则进行交换。将序列照此 方法从头到尾处理一遍称作一趟起泡，一趟起泡的效果是将关键码值最小的记录交换到了最前位置，即该记录的顺序起始位置。若某一趟起泡过程中没有任何交换发生，则排序过程结束 对n个记录的文件进行排序。所需执行时间是n2量级,2.快速排序,快速排序的基本方法是：在待排序列中任取一个记录，以它为基准用交换的方法将所有记录分成两部分，关键码值比它小的在一部分，关键码值比它大的在另一部分。再分别对这两部分实施上述过程，

26、一直重复到排序完成。快速排序法的平均执行时间为log2n量级。,3.5 文件简介 3.5.1 基本概念,文件是命名的性质相同的记录的集合,3.5.2 文件的结构,1.顺序文件：文件记录按关键码递增(或递减)的次序定义，且在外存上按同样的次序排列，则文件叫做顺序文件 2.索引文件:索引表的每项由一个关键码和一个指针构成的二元组(k,p)。每个索引项对应文件的一个逻辑记录,k是对应记录的关键码，p是该记录的外存地址 3.倒排文件:按属性字段来建立索引。这种索引叫做倒排索引或副索引。带有倒排索引的文件叫做倒排索引文件，简称倒排文件 除上述三种文件外，还有直接文件、相对文件、字节流文件等,3.5.3 文件的操作,1.检索：在文件中查找满足一定条件的记录，最常见的是查找关键码为一指定值的记录，更一般地，可以根据一组字段的值进行检索， 2.插入：在文件中增加一个新记录。 3.删除：删去文件中的一个记录。这种操作常常需要通过检索先找到被删记录的位置，而后再删除 4.修改：把记录中某些字段的值改为新值。 5.排序：按照一组指定字段的值把文件的全部记录在外存上重新进行排列，使记录的外存地址随这组字段值从小到大(或从大到小) 排列,叫做外排序,