二级vfp 算法与数据结构基础

管群主编第1章算法与数据结构基础1.1算法的基本概念1.2数据结构基础1.3线性表1.4栈和队列1.5树1.6排序1.7查找1.1算法的基本概念算法的定义：一个有穷的指令集，这些指令为解决某一特定问题规定了一个运算序列，即方法和步骤，在计算机学科中，算法就是计算机解决问题的过程或步骤。结构化程序算法的特性如下。（1）输入（2）输出（3）确定性（4）有穷性（5）有效性算法复杂度通常采用由德国数学家PaulBachmann在1892年提出的“大O表达式”表述，该符号以大写字母O带一对小括号括起的一个表达式构成。一般描述算法复杂度时括号里用N的简单函数表示，如O(N2)（读作：ON大平方）。算法的时间复杂度指算法的时间耗费，算法时间是由控制结构和原操作的决定的。算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。算法的空间复杂度描述算法的存储空间需求，运行完一个程序所需要的内存大小是问题规模n的某个函数g(n)，记作：S(n)=O(g(n))它表示随着问题规模n的增大，算法运行所需存储空间的增长率S(n)与g(n)的增长率相同。1.2数据结构基础数据：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据包括数值性数据和非数值性数据。数据元素（也称为元素、接点、顶点、记录）：数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成。数据项：数据项是具有独立含义的最小标识单位。数据对象：数据的子集，是具有相同性质的数据成员（数据元素）的集合。数据结构的定义：数据结构是指数据之间的相互关系，即数据的组织形式，由某一数据对象及该对象中所有数据成员之间的关系组成，记为：Data_Structure={D,R}，其中D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。它包括逻辑结构、存储结构和数据的运算3个方面的内容。数据的逻辑结构：用来描述数据元素之间的逻辑关系。数据的存储结构：用来描述数据元素及数据元素之间的关系在存储器中的存储形式。数据的运算：即对数据元素施加的操作。数据结构的图形表示：用图形来直观地表示数据及其之间的关系。学生（学号，姓名，性别，籍贯）课程（课程号，课程名，学分，课时）选课（学号，课程号，成绩）图1-1数据结构的图形表示数据的逻辑结构分为线性结构和非线性结构两类：线性结构：数据元素之间构成一种顺序的线性关系，如图1-2所示。线性结构包括线性表、堆栈、队列和串。数据1数据2数据3图1-2数据元素的线性关系线性结构的特征有：（1）集合中必存在惟一的一个“第一元素”；（2）集合中必存在惟一的一个“最后元素”；（3）除最后的元素之外，均有惟一的后继；（4）除第一元素之外，均有惟一的前驱。非线性结构是指不满足以上条件的存储结构。非线性结构包括树、二叉树、图（或网络）和广义表。1.3线性表1.3.1线性表的顺序存储结构线性表是最常用且最简单的一种数据结构。采用顺序存储结构的线性表也叫做顺序表，如n个元素的线性表可以记为：L=（a1，a2，…，an）。a1a2a3a4a5顺序表L：图1-3顺序表顺序表有插入和删除两种基本操作。a1…ai-1ai顺序表L：…an0i2i1n1n插入前a1…ai-1ai…an0i2i1插入后ein1图1-4顺序表的插入1.3.2线性表的链式存储结构链式存储是指用一组地址任意的存储单元存放线性表中的数据元素。链式存储采用结点来表示数据元素。一个结点由两个部分构成：数据域和指针域。（1）单链表及其基本操作a0a1a2a3firstlast^图1-5单链表xnewnodepxnewnodep插入前插入后图1-6单链表的插入ai-1paiai+1q删除前ai-1paiai+1q删除后图1-7单链表的删除（2）双向链表及其基本操作esp插入前插入后ai-1aiespai-1ai图1-8双向链表的插入1.4栈和队列1.4.1栈及其基本操作栈是规定只能在表的一端进行插入和删除的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。当表中没有元素时称为空栈。由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先被删除，所以又把栈称为后进先出（Last_In_First_Out，简称LIFO）表。栈有插入（即进栈）和删除（即出栈）两种基本操作。插入也叫入栈或进栈。1.4.2队列及其基本操作队列可以看作是插入在一端进行，删除在另一端进行的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为先进先出（First_In_First_Out,FIFO）表。队列的基本操作有插入（即入队）和删除（即出队）两种。a0a1a2an-1…出队入队frontrear图1-10顺序队列空队列67012345frontrear670123456701234567012345frontrearA进队AABCfrontrearBCrearfrontA出队BC进队图1-11循环队列的插入和删除1.5树1.5.1树的基本概念树是由n(n≥0)个结点组成的有限集合。如果n=0，称为空树；如果n＞0，则有一个特定的称之为根（root）的结点，根结点只有直接后继，没有直接前驱；除根以外的其他结点划分为m(m≥0)个互不相交的有限集合T0，T1，…，Tm−1，每个集合又是一棵树，并且称之为根的子树（subTree）。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。ABCDJIHGFEKLMrootlevel0level1level2level3depth=3(c)图1-13树1.5.2二叉树的基本概念一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LRRL(a)(b)(c)(d)(e)图1-145种二叉树014378265910111213140143782659(a)满二叉树(b)安全二叉树图1-15满二叉树和完全二叉树1.5.3二叉树的存储结构（1）顺序存储结构31236670621217058855312319466706212170549(b)完全二叉树的顺序存储(d)一般二叉树的顺序存储55880134789101125601263578121431231266940517706249558801234567891011(a)3123126605177062012345678910118855121413(c)图1-16二叉树的顺序表示（2）链式存储结构ABDCEFrootG(a)二叉树A^BC^DEF^G^^^^^root(b)二叉链表A^^BC^^DE^F^^G^^root(c)三叉链表图1-17二叉树的链式存储表示1.5.4二叉树的遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作V，遍历根的左子树记作L，遍历根的右子树记作R，则可能有以下6种遍历二叉树的方案：前序VLRVRL中序LVRRVL后序LRVRLVabcdef图1-18二叉树1．中序遍历中序遍历的算法过程如下。（1）若二叉树为空，则空操作，返回。（2）否则依次执行：中序遍历左自树（L）；访问根结点（V）；中序遍历右自树（R）。2．前序遍历前序遍历二叉树的算法过程如下。（1）若二叉树为空，则返回。（2）否则依次执行：访问根结点（V）；前序遍历左子树（L）；前序遍历右子树（R）。3．后序遍历后序遍历的算法过程如下。（1）若二叉树为空，返回。（2）否则依次执行：后序遍历左子树（L）；后序遍历右子树（R）；访问根结点（V）。1.6排序排序是将一组杂乱无章的数据按一定的规律顺次排列起来。通常数据对象有多个属性域，即由多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域称为关键字（key）。排序的时间开销是衡量算法好坏的最重要的标志。1.6.1选择排序选择排序的思想是：每一趟（例如，第i趟，i=0，1，…，n−2）在后面n−i个待排序对象中选出关键字最小（升序，若为降序，选出最大关键字）的对象，作为有序对象序列的第i个对象。待到第n−2趟作完，待排序对象只剩下1个，不用再选了，结束排序。1．直接选择排序直接选择排序是一种简单的排序方法，它的基本步骤是：（1）在一组对象v[i]～v[n−1]中选择具有最小关键字的对象；（2）若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调；（3）在这组对象中剔除这个具有最小关键字的对象。在剩下的对象v[i+1]～v[n−1]中重复执行第1步和第2步，直到剩余对象只有一个为止。2．树型选择排序树型选择排序的基本思想是：首先取得n个对象的关键字，进行两两比较，得到[n/2]个比较的优胜者（关键字小者），作为第一步比较的结果保留下来。然后对这[n/2]个对象再进行关键字的两两比较……如此重复，直到选出一个关键字最小的对象为止。可以使用满二叉树来描述该算法，因此称之为树型选择排序。82125*21212586384916863第一次输出825*胜者162125*21212516631649166325*胜者第二次输出16212125*21212563634963第三次输出2125*胜者252525*25256363496325*胜者第四次输出25树型选择排序总时间复杂度为O(nlog2n)。树型选择排序是一个稳定的排序方法。1.6.2插入排序插入排序的基本方法是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。1．直接插入排序直接插入排序的基本思想如下：当插入第i（i≥1）个对象时，前面的v[0]，v[1]，…，v[i−1]已经排好序。这时，用v[i]的关键字与v[i−1]，v[i−2]，…的关键字顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。直接插入排序的时间复杂度为O(n2)。这种排序方法是稳定的。2．希尔排序希尔排序又称缩小增量排序。该方法的基本思想如下：设待排序对象序列有n个对象，首先取一个整数gap＜n作为间隔，将全部对象分为gap个子序列，所有距离为gap的对象放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔gap，例如取gap=[gap/2]，重复上述的子序列划分和排序工作。知道最后取gap=1，将所有对象放在同一个序列中排序为止。希尔排序是不稳定的排序方法。1.6.3交换排序交换排序的基本思想是：两两比较待排序对象的关键字，如果发生逆序，则交换之。直到所有对象都排好序为止。1．冒泡排序若不符合排序顺序，就交换这两个记录，直到第n个记录为止。第一次循环结束时，得到最大的记录。在剩下的n−1个数据元素中重复上述步骤，得到次大的记录。重复若干次后，得到已排序好的一组记录。2．快速排序快速排序是对冒泡排序的改进，是目前内部排序中速度最快的一种。快速排序基本思想如下。首先取待排序对象序列中的某个对象（例如取第一个对象）作为基准，按照该对象的关键字大小，将整个对象序列划分为左右两个子序列：左侧子序列中所有对象的关键字都小于或等于基准对象的关键字；右侧子序列中所有对象的关键字都大于基准对象的关键字；基准对象则排在这两个子序列中间（这也是该对象最终应排放的位置）。1.7查找查找又称检索。查找算法的评价主要考虑算法的时间复杂性，既可以采用数量级的形式表示，也可以采用平均检索（查找）长度，即在查找成功情况下的平均比较次数来表示。1.7.1顺序查找顺序查找又称线性查找。它是一种最简单、最基本的查找方法。基本思想是：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较。若某个记录的关键字和给定值相等，则查找成功；否则，若直至第一个记录，其关键字和给定值都不相等，则表明表中没有所查记录，查找不成功。1.7.2二分查找二分查找又称折半查找。作为二分查找对象的表必须是顺