算法和数据结构

第三章算法与数据结构设计程序首先要了解需要研究要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤,模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来本章着重讨论解决问题的核心--算法以及算法的处理对象--数据的结构算法和数据结构全文共46页，当前为第1页。3．1算法解题过程的准确、完整的描述称作解该问题的算法程序就是用计算机语言表述的算法，流程图就是图形化了的算法程序＝算法＋数据结构3.1.1算法的两要素算法由操作与控制结构两要素组成1.操作(1)逻辑运算：“与”、“或”、“非”；(2)算术运算：加、减、乘、除；(3)数据比较：大于、小于、等于、不等于；(4)数据传送：输入、输出、赋值。算法和数据结构全文共46页，当前为第2页。2.控制结构算法的控制结构，决定了各操作的执行次序。用流程图可以形象地表示出算法的控制结构任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成算法和数据结构全文共46页，当前为第3页。3.1.2算法的特征1.算法是由一套计算规则组成的一个过程2.组成算法的规则是确定的、可执行的3.每种算法必须有确定的结果，产生一个或多个输出4.每个算法必须有0个（自动生成初始数）或多个输入5.解答必须在有限步内得到,不能出现“死循环”我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答算法和数据结构全文共46页，当前为第4页。3.1.3算法的表示算法设计一般是由粗到细的过程，一般可以使用下面几种类型的工具描述算法:1.自然语言自然语言描述算法通俗易懂，但它有着难以克服的缺陷：(1)易产生歧义性(2)语句繁琐冗长，很难清楚地表达算法的逻辑流程(3)当今的计算机尚不能处理用自然语言表示的算法2.专用工具常用的有流程图、PAD图和N-S图、伪代码等3.算法描述语言为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。在本书中为类VB语言继续算法和数据结构全文共46页，当前为第5页。流程图

是采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作常用流程图符号：返回算法和数据结构全文共46页，当前为第6页。1.枚举法（穷举法）基本思想是：先依据题目的部分条件确定答案的大致范围在此范围内对所有可能的情况逐一验证，直到全部情况验证完若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解3.1.4常用算法算法和数据结构全文共46页，当前为第7页。2.迭代法使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程使用迭代法构造算法的基本方法是：首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差并认为最后一次迭代得到的近似值为问题的解。算法和数据结构全文共46页，当前为第8页。3.递归法如果一个过程直接或间接地调用它自身，则称该过程是递归的例：求阶乘。Funcfac(nAsInteger)Ifn=1thenfac=1Elsefac=n*fac(n-1)Endif递归过程必须有一个递归终止条件，当n=0时定义为1，是阶乘递归定义的递归出口递归则是从函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值算法和数据结构全文共46页，当前为第9页。4.递推法所谓递推法，它的数学公式也是递归的。只是在实现计算时与递归相反。从给定边界出发逐步迭代到达指定计算参数。例：求阶乘f(n)＝n!＝n×(n-1)!＝n×f(n-1)要计算10!，可以从递推初始条件f(0)=1出发，应用递推公式f(n)=n×f(n-1)逐步求出f(1)、f(2)…、f(9)、最后求出f(10)的值递推操作是提高递归函数执行效率最有效的方法，科技计算中最常见算法和数据结构全文共46页，当前为第10页。5.分治法解一个夏杂的问题时，尽可能地把这个问题分解为较小部分，找出各个的解，然后再把各部分的解组合成整个问题的解，这就是所谓的分治法6.回溯法在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解算法和数据结构全文共46页，当前为第11页。回溯法的算法是：ProcBacktracking(succ:Boolean)确定起始状态值走第一步确定下一步还有几种可能选一可能走下一步，记住可能和本步特征做完新一步应做的事While目标未达到do

确定下一步有几种可能

While没有可能and还有上一步do

回退上一步查有无下一可能

Enddo

If上一步没有了Thenreturn(SUCC=FALSE)

EndIf选一可能走一步，记住可能和本步特征做完新一步应做的事Enddoreturn(SUCC=TRUE)EndBacktracking算法和数据结构全文共46页，当前为第12页。3.2数据结构

3.2.1数据结构概述。1．数据结构的研究内容数据的逻辑结构、数据的存储结构、数据的运算

数据的逻辑结构：Data-Structure＝(D,R)其中：D是数据元素的集合，R是D上关系的集合一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图程序中的数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等算法和数据结构全文共46页，当前为第13页。2．数据结构应用示例例3.4识别“体”字的过程按分支和层次组织的数据，称为：“树形结构”算法和数据结构全文共46页，当前为第14页。例3.5计算机换房系统中的“多角互换问题”数据结构叫它们为“循环链表”例3.6饭店服务系统中的客房预订问题这种结构称为“队列”，是一种元素间先后次序很强的数据结构算法和数据结构全文共46页，当前为第15页。例3.7管理信息系统中的查询问题 各种计算机管理信息系统中，通常相关的信息(记录)组成一个文件,文件是一类很重要的数据结构文件中的记录可按顺序方式组织顺序文件导出的链表为提高检索效率，可将所有选修“算法分析”课的同学记录串接到一起，这种串接称为“加链”算法和数据结构全文共46页，当前为第16页。3.2.2线性表线性表的逻辑结构是n个数据元素的有限序列: (a1,a2,a3,…an)

n为线性表的长度(n≥0)，n=0的表称为空表数据元素呈线性关系.必存在唯一的称为“第一个”的数据元素;必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素；除最后一个元素外，每个元素都有且只有一个后继元素。所有数据元素ai在同一个线性表中必须是相同的数据类型算法和数据结构全文共46页，当前为第17页。线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表线性表的基本运算主要有：(1)在两个确定的元素之间插入一个新的元素；(2)删除线性表中某个元素；(3)按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新算法和数据结构全文共46页，当前为第18页。1.顺序表和一维数组将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表，其下标可看成元素的相对地址运算：(1)插入，在线性表(a1,a2…，ai，ai+1…，an)的第i个位置插入元素x，算法如下：PROCINSERT(VARA,VARn,i,x)If(i<1)Or(i>n+1)ThenERROR(“位置不存在！”)

ElseForj=nDownToiA(j+1)=A(j)

NextjEndifA(i)=x

n=n+1End算法和数据结构全文共46页，当前为第19页。(2)删除：在表长为n的线性表(a1,a2,…ai-1,ai,ai+1…an)中删除第i个数据元素，通常还需将第i+1个至第n个元素向前推动一个位置，即(a1,a2,…，ai-1,ai+1，…，an)，其算法描述如下:PROCDELETE(VARA,VARn,I)If(i<1)Or(i>n)Then

ERROR('位置不存在！') ELSEFORj=iTOn-1A(j)=A(j+1)Nextjn=n-1EndifEnd在顺序表中插入或删除元素时，每进行一次插入或删除，都要移动近乎一半的元素。对于长度可变的线性表，必须按可能达到的最大长度分配空间顺序表的不足：算法和数据结构全文共46页，当前为第20页。2．链表(1）单链表(线性链表):链式存储的线性表结点除信息域外还含有一个指针域，用来指出其后继结点的位置最后一个结点没有后继结点，指针它的指针域为空(记为NIL或∧)。另外还需要设置一个指针head，指向单链表的第一个结点算法和数据结构全文共46页，当前为第21页。链表的一个重要特点是插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可插入删除算法和数据结构全文共46页，当前为第22页。(2）循环链表：循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“NIL”，而是指向头一个结点，成为一个由链指针链结的环(3）双向链表：设有一个指向后继结点的指针和一个指向前驱结点的指针算法和数据结构全文共46页，当前为第23页。3．栈栈(STACK)也是一种特殊的线性表，是一种“后进先出”的结构，它的运算规则受到一些约束和限定，故又称限定性数据结构(1）栈的结构特点栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)栈的物理存储可以用顺序存储结构，也可以用链式存储结构(2）栈的运算设置一个空栈判定栈是否为空进栈、退栈读取栈顶元素等算法和数据结构全文共46页，当前为第24页。4．队列(1）队列的结构特点队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)队列的操作是按先进先出的原则进行的队列的物理存储可以用顺序存储结构，也可以用链式存储结构。算法和数据结构全文共46页，当前为第25页。(2）队列的运算：设置一个空队列；判定队列是否是空队列；入队列；出队列；读取队头元素等如果队列的容量无法预先估计时，可以采用链表存储结构循环队列的插入、删除算法和数据结构全文共46页，当前为第26页。3.2.3串串(String)可以看作一维字符数组，但其长度不恒定，可以作删除、插入操作许多高级语言把串作为一种单独的类型，其元素不可作四则运算进行连接、删除、插入操作，用子串有时很方便子串(Substring)是串的一部分，具有串的一切特征算法和数据结构全文共46页，当前为第27页。3.2.4树和二叉树

1.树和二叉树的定义和术语树的逻辑结构树的形式化定义：树(Tree)是由一个或多个结点组成的有限集合T，其中有一个特定的称为根的结点；其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm，每一个集合本身又是一棵树，且称为根的子树用表来表示树：(A(B(E,F),C(G),D(H,I,J)))结点子树个数为结点的度,结点度的最大值为该树的度结点B的度为2，树的度为3算法和数据结构全文共46页，当前为第28页。0棵或多棵不相交的树的集合称为树林二叉树是另一种重要的树形结构，其结构定义为：二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为根的左子树和右子树的、互不相交的二叉树组成二叉树的逻辑结构：二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树算法和数据结构全文共46页，当前为第29页。2.树的存储结构树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理算法和数据结构全文共46页，当前为第30页。3.二叉树的存储结构可使用具有2个指针域的链表，LC为左指针域，指向结点的左子树，RC为右指针域，指向结点的右子树。亦可用数组的下标来模拟指针，即开辟三个一维数组DATA，LC和RC分别存放结点的元素及其左、右指针算法和数据结构全文共46页，当前为第31页。4.树的二叉树表示每一棵都能唯一地转换到它所对应的二叉树转换方法：凡是兄弟就用线连接起来，对每个非终端结点，除其最左孩子外，删去该结点与其他孩子结点的连线，再以根结点为轴心，顺时针旋转450算法和数据结构全文共46页，当前为第32页。5.树和二叉树的遍历(周游)树的遍历根据树的递归定义，有两种遍历树的方法：(1)先根(次序)遍历：若树中只有一个根结点，则访问树的根结点；否则，首先访问树的根结点，然后依次先根遍历每棵子树。(2)后根(次序)遍历：若树中只有一个根结点，则访问树的根结点；否则，首先依次后根遍历每一棵子树，然后访问树的根结点。算法和数据结构全文共46页，当前为第33页。二叉树的遍历(3)后序遍历二叉树的算法为：若二叉树不空，则：

a)后序遍历左子树；

b)后序遍历右子树；

c)访问根结点。前图用后序遍历为：FEGJIHDCBA(1)前序遍历二叉树算法为：若二叉树不空，则：

a)访问根结点；

b)前序遍历左子树；

c)前序遍历右子树。前图用前序遍历为ABEFCGDHIJ(2)中序遍历二叉树的算法为：

若二叉树不空，则作：

a)中序遍历左子树；

b)访问根结点；

c)中序遍历右子树。前图用中序遍历为：EFBGCHIJDA算法和数据结构全文共46页，当前为第34页。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的结点称为终端结点。算法和数据结构全文共46页，当前为第35页。2.图的存储

(1)图的相邻矩阵表示法若G是一个具有n个结点的图，则G的相邻矩阵是:(2)图的邻接表表示法用邻接表法表示有向图，根据需要可以保存每个结点的出边表，也可以保存每个结点的入边表算法和数据结构全文共46页，当前为第36页。3.图的遍历

(1)深度优先遍历基本思想是：从图中某个V出发，访问此结点，再依次访问所有与V有路径的结点。完成后再另选图中一个未被访问的结点作始点，重复上述过程，直至图中所有结点都被访问到为止。(2)广度优先遍历基本思想是：从某个结点V出发，访问此结点，再依次访问V邻接的未访问结点。再从这些结点出发进行广度优先遍历，直至图中所有被访问过的结点的相邻结点都被访问到。完成后另选图中一个未曾访问的结点作始点，重复上述过程，直至图中所有结点都被访问到为止算法和数据结构全文共46页，当前为第37页。3.3查找3.3.1基本概念关键字是数据元素中可以唯一标识一个数据元素的数据项，比如学号、身份证号等，查找是根据给定的关键值，在一组数据中确定一个其关键字等于给定值的数据元素的过程确切定义：给定一个值K，在含有n个记录的文件中进行搜索，寻找一个其关键字等于给定的K值的记录，如找到，则输出记录或记录在文件中的相对位置称查找成功；否则输出查找不成功的信息称查找失败。算法和数据结构全文共46页，当前为第38页。

3.3.2查找算法

1.顺序查找顺序查找的方法是：用待查关键字值与线性表中各结点的关键字值逐个比较，直到找出相等的关键字值;或找遍所有结点都找不到,即查找失败顺序查找的优点是对线性表结点的逻辑次序无要求,对线性表的存储结构无要求,缺点是平均检索长度长,为n/22.二分法查找要求线性表结点按关键字码值排好，且以顺序方式存储用要查找的码值X与中间位置结点的关键码值W相比较：(1)X=W，此时已经查找成功，查找结束。(2)X>W,表明X在表的后半部分,取后半部分进行查找(3)X<W,表明X在表的前半部分，取前半部分进行查找二分法查找的优点是平均检索长度小，为log2n算法和数据结构全文共46页，当前为第39页。3.分块查找要求文件中记录关键字“分块有序”,即前一块中最大关键字小于后一块中最小关键字,而块内的关键字不一定有序分块查找的基本思想：先抽取各块中的最大关键字构成一个索引表，由于文件中的记录按关键字分块有序，则索引表呈递增有序状态。查找分两步进行:第一步先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块，第二步在已限定的那一块中进行顺序查找用分块查找的文件不一定分成大小相等的若干块，块大小及其分法可根据文件的特征来定。分块查找不仅适用于顺序方式存储的顺序表，也适用于线性链表方式存储的文件算法和数据结构全文共46页，当前为第40页。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)｝，这种运算就称为排序内排序指当文件的数据量不太大时，全部信息放在内存中处理的排序方法。当文件的数据量较大时，排序过程中需要在内、外存之间不断地进行数据交换才能达到排序的目的，这种排序称为外排序算法和数据结构全文共46页，当前为第41页。3.4.2插入排序基本思想是：每步将一个待排序的记录，按关键码值的大小插入到前面已排序的适当位置上，直到全部插完止1.直接插入排序：在排