国家计算机二级公共基础知识(B4).doc

公共基础知识第一章 数据结构与算法1.1 算法1. 算法：所谓算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。当然，程序也可以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。 算法实际上是一种抽象的解题方法，它具有动态性。作为一个算法一般应具有以下几个基本特征。 (1) 可行性 算法的可行性主要包括两个方面。一是算法中的每一个步骤必须是能实现的。一是算法执行的结果要能达到预期的目的。 (2) 确定性 算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。 (3) 有穷性 算法的有穷性，是指算法必须能在有限的时问内做完即算法必须能在执行有限个步骤之后终止。 算法的有穷性还应包括合理的执行时间的含义。因为，如果一个算法需要执行千万年，也失去了实用价值。 (4) 拥有足够的情报一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法并不有效。综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的且是明确的，此顺序将在有限的次数下终止。 2. 算法复杂度：算法的复杂度主要包括时间复杂度和空间复杂度。 (1) 算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：算法的工作量=其中n是问题的规模。在同一问题规模下，如果算法执行所需的基本运算次数取决于某特定输入时，可以用以下两种方法来分析算法的工作量。平均性态分析，是指用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。算法的平均性态定义为：其中：x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，Dn表示当规模为n时，算法执行时所有可能输入的集合。最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。它定义为： 显然，W(n)的计算要比A(n)的计算方便得多。由于W(n)实际上是给出了算法工作量的一个上界，因此，它比A(n)更具有实用价值。 (2)算法的空间复杂度一个算法的空间复杂度一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)工作的。存许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。1.2 数据结构1. 数据结构的基本概念数据结构是指反映数据元素之间关系的数据元素集合的表示。通俗地说，数据结构是指带有结构的数据元素的集合。(1) 数据的逻辑结构：一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的种结构。在数据处理领域中，通常把数据之间的这种固有的关系简单地用前后关系（或直接前驱与直接后继关系）来描述。所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R。即一个数据结构可以表示成B=（R，D）其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设a与b是D中的两个数据，则二元组(a，b)表示a是b的前件，b是a的后件。这样，在D中的每两个元素之间的关系都可以用这种二元组来表示。例如，一年四季的数据结构可以表示成B=（R，D）D=春，夏，秋，冬R=（春，夏），（夏，秋），（秋，冬）家庭成员数据结构可以表示成B=（R，D）D=父亲，儿子，女儿R=（父亲，儿子），（父亲，女儿）(2)数据的存储结构各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。例如在一年四季的数据结构中，“春”是“夏”的前件，但在对它们进行处理时，在计算机存储空间中，“春”这个数据元素的信息不一定被存储在“夏”这个数据元素信息的前面，而可能在后面，也可能不是紧邻在前面，而是中间被其他的信息所隔开。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。由于数据元素在计算机存储间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系)，在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。2. 数据结构的图形表示一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点：为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。结点（D）关系（R）例如，一年四季的数据结构可以用图l.2所示的图形来表示。又如，反映家庭成员间辈分关系的数据结构可以用图1.3所示的图形来表示。3. 线性结构与非线性结构根据数据结构中个数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：有且只有一个根结点。每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。如一年四季这个数据结构。如果一个数据结构不是线性结构则称之为非线性结构。如1.3中家庭成员辈分关系数据结构。需要特别说明的是：在一个线性结构中插入或删除任何一个节点后还应该是线性结构。如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。线性结构和非线性结构都可以是空的数据结构。空数据结构是否属于线性结构，满足对一个空数据结构的运算是按线性结构规则来处理，则属于线性结构；否则属于非线性结构。4. 线性表及其存储结构（1）线性表的基本概念线性表是由n（n0）个数据元素a1，a2，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个浅见，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为：其中ai（i=1，2，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。非空线性表有如下一些结构特征： 有且只有一个根结点a1，它无前件。 有且只有一个终端结点an，它无后件 除根结点与终端结点外，其他所有结点有且只有一个前件，有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0是，称为空表。（2）线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点： 线性表中所有元素所占的存储空间是连续的。 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。 在顺序存储结构中，线性表中每个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。 在程序设计语言中，通常定义个一维数组来表示线性表的顺序存储空间。(3) 顺序表的插入运算设长度n的线性表为：要在线性表的第i个元素ai之前插入一个新元素b，插入后得到长度为n+1的线性表为：则插入前后的两线性表中的元素满足如下关系：在一般情况下，要在第i(1in)个元素之前插入一个新元素时，首先要从最后一个(即第n个)元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后线性表的长度就增加了1。显然，在线性表采用顺序存储结构时，如果插入运算在线性表的未尾进行即在第n个元素之后(可以认为是在第n+1个元素之前)插入新元素，则只要在表的末尾增加一个元素即可，不需要移动表中的元素；但如果要在线性表的第1个元素之前插入一个新元素，则需要移动表中所有的元素。在一般情况，如果插入运算在第i(1in)个元素之前进行，则原来第i个元素之后(包括第i个元素)的所有元素都必须移动。在平均情况下，要在线性表中插入一个新元素，其效率是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。（4）顺序表的删除运算设长度为n的线性表为：现在要删除第i个元素，删除后得到的长度为n-1的线性表为：，则删除前后的两线性表中元素满足如下关系：在一般情况下，要删除第i(1in)个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。显然，在线性表采用顺序存储结构时，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动表中的元素：但如果要删除线性表中的第1个元素，则需要移动表中所有的元素。在一般情况，如果要删除第i(1in)曲个元素则原来第i个元素之后的所有元素都必须依次往前移动一个位置。在平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下要删除一个元素，其效率也是很低的，特别是在线性表比较大的情况下更为突出，由于数据元象的移动而消耗铰多的处理时间。5. 栈(1)栈的概念栈(stack)是限定在一端进行插入与删除的线性表。在这种特殊的线性表中其插入与删除运算都只在线性表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，最先删除的元素；栈底元素总是最先被插入的元素最后被删除的元素。栈是按照“先进后出”(FILOFirst In Last Out)或“后进先出”(LIFOLast In First Out)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可吐看出栈具有记忆作用。通常用指针top来指示栈顶的位置，用指针buttom指向栈底。往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。栈项指针top动态反映了栈中元素的变化情况。(2)栈的顺序存储及其运算在程序设计语言中，用一维数组S(1：m)作为栈的顺序存储空间其中m为栈的最大容量。在栈的顺序存储空间S(1：m)中，S(bottom)通常为栈底元素(在栈非空的情况下)，S(top)为栈顶元素。top=0表示栈空：top=m表示栈满。入栈运算。入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进一(即top加1)，然后将新元素插入到栈项指针指向的位置。退栈运算。退栈运算是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈项元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针退一(即top减1)。当栈顶指针为0时，说明栈空不可能进行退栈操作。这种情况称为栈“下溢”错误。读栈顶元素。读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈项元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。6. 队列(1) 队列的概念队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针(rear)的指针指向队尾元素，即尾指针总是指向最后被插入的元素：允许删除的一端称为排头(也称为队头)，通常也用一个排头指针(front)指向排头元素的前一个位置。显然，在队列这种数据结构中，最先插入的元素将最先被删除，反之，最后插入的元素将最后才能被删除。因此，队列又称为“先进先出”(FIFOFirst In Firs tout)或“后进后出”(LILOLast In Last Out)的线性表它体现了“先来先服务”的原则。在队列中，队尾指针rear与排头指针front共同反映了队列中元素动态变化的情况。(2) 循环队列及其运算所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。在循环队列中用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态威尔空，即rear=front=m循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就进一。当队尾指针rear=m+1时，则置rear=1。每进行一次退队运算，排头指针就进一。当排头指针疗front=m+l时，则置舶front=1。在实际使用循环队列时，为了能区分队列满还是队列空通常还需增加一个标志s，s值的定义如：由此可以得出队列空与队列满的条件如下： 队列空的条件为s=0。 队列满的条件为(s=1)且(盱front=rear)。循环队列入队与退队算法如下： 假设循环队列的初始状态为空，即：s=0，且front=rear=m。 入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针进一(即rear=front+1)，并当rear=m+1时置rear=l：然后将新元素插入到队尾指针指向的位置。当循环队列非空(s=1且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。退队运算是指在循环队列的排头位置推出一个元素并赋给指定的变量。这个运算有两个基本操作：首先将排头指针进一(即front=front+1)，并当front=m+1时置front=l；然后将排头指针指向的元素赋给指定变量。当循环队列为空(s=0)时，不能进行退队运算。这种情况称为“下溢”。7. 线性链表由于线性表的顺序存储结构存在很多缺点，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用链式存储结构。在链式存储结构中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。(1) 线性链表线性表的链式存储结构称为线性表。为了适应线性表的链式存储结构计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。为了存储线性表中的每一个元素， 一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域：另一部分用于存放下一个数据元素的存储序号(即存储结点的地址)，即指向后件结点，称为指针域。在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点(存放线性表中第一个数据元素的存储结点的序号)线性表中最后一个元素没有后件，指针域为空(用NULL或0表示)，表示链表终。线性链表的逻辑结构如图l.4所示图1.4线性链表的逻辑结构一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。在线性链表中，并数据元素之间的前后件关系是曲各结点的指针域来指示的。指向线性表中第一个结点的指针HEAD称为头指针。当HEAD=NULL(或0)时称为空表。栈和队列也是线性表，也可以采用链式存储结构。(2) 线性链表的基本运算在非空线性链表中寻找包含指定元素值x的前一个结点P的基本方法如下：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号：当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。为了要在线性链表中插入个新元素，首先要给该元乘分配一个新结点，以便用于存储该元素的值。新结点可以从可利用栈中取得。然后将存放新元素值的结点链接到线性链表中指定的位置。线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点。为了在线性表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除的结点放回到可利用栈。(3) 循环链表及其基本运算循环链表的结构与一般单链表的相比，具有以下两个特点： 在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。 循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了个环状链。在实际应用中，循环链表主要有以下两个方面的优点： 在循环链表中只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。而线性单链表做不到这一点。 由于在循环链表中设置了个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。8. 树与二又树(1) 树的基本概念树(tree)是一种简单的非线性结构。图1.5表示了一棵一般的树。在树图形表示中，总是认为在用直线连起来的两端点中，上端点是前件，下端点是后件，这样，表示前后件关系的箭头就可以省略。图1.5 一般的树(2)树结构中的基本特征和基本术语树结构中，每一个结点只有一个前件，称为父结点。在树中，没有前件的结点只有一个，称为树的根结点，简称为树的根。如，在图15中，结点R是树的根结点。在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。如，在图1.5中，结点C、M、F、X、G、S、L、Z、A为叶子结点。在树结构中，一个结点所拥有的后件个数称为该结点的度。如，在图1.5中，根结点R的度为4；结点T的度为3。叶子结点的度为0。树结构具有明显的层次关系，树是一种层次结构。根结点在第l层。同层上所有结点的所有子结点在下一层。树的最大层次称为树的深度。在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。如，在图1.5中，结点R有四棵字数，它们分别以K、P、Q、D为根结点。D结点有一棵子树，其根结点为T。在树中，叶子结点没有子树。(3) 二叉树的特点 非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 在二叉树中，每一个结点的度最大为2，即所有子树(左子树或右子树)也均为二叉树。而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每一个结点的子树被明显地分为左子树与右子树。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点。（4) 二叉树的性质在二叉树的第k层上，最多有个结点。深度为m的二叉树最多有个结点。在任意一棵二叉树中度为O的结点(即叶子结点)总是比度为2的结点多一个。具有n个结点的二义树，其深度至少为，其中表示取的整数部分。(5)满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊形态的二叉树。 满二叉树。除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有个结点且深度为m的满二叉树有个结点。 完全二叉树。除每后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从l到n的结点一一对应时称之为完全二叉树。对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+l。由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。完全二叉树还具有以下两个性质。 具有n个结点的完全二叉树的深度为。设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左到右)用自然数1，2，n给结点进行编号，则对于编号为k(k=l，2，n)的结点有以下结沦： 若k=1，则该结点为根结点，它没有父结点：若k1则该结点的父结点编号为。 若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点(显然也没有右子结点)。 若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左于结点和右子结点的位置。(6) 二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件(即两个子结点)因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。由于二叉树的存储结构中每一个存储结点有两个指针域，因此，二叉树的链式存储结构也称为二叉链表。对于满二叉树与完全二叉树来说，根据完全二叉树的性质，可以按层序进行顺序存储，这样，不仅节省了存储空间，又能方便地确定每一个结点的父结点与左右子结点的位置。顺序存储结构对于一般的二叉树不适用。(7) 二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。前序遍历(DLR)。所谓前序遍历是首先访问根结点然后遍历左子树最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。因此，前序遍历二叉树的过程是一个递归的过程。中序遍历(LDR)。所谓中序遍历是首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。后序遍历(LRD)。所谓后序遍历是首先遍历左子树，然后遍历右子树，最后访问根结点，并且在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。9. 查找技术(1) 顺序查找顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素。基本方法是：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到(查找成功)：若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素(查找失败)。如果线性表中的第一个元索就是被查找元素，则只需做一次比较就查找成功，最坏的情况是被查元素是线性表中的最后个元素，或者被查元素在线性表中根本不存，则为了查找这个元素需要与线性表中所有的元素进行比较。平均情况下，利用顺序查找法在线性表中查找个元素，大约要与线性表中一半的元素进行比较。(2) 二分法查找二分法查找只适用于顺序存储的有序表。有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素相等)。设有序线性表的长度为n，被查元素为x，则对分查我的方法如：将x与线性表的中间项进行比较，如果中间项的值等于x，则说明查到，查找结束：如果x小于中间项的值。则在线性表的前半部分以相同的方法进行查找：如果大于中间项的值，则在线性表的后半部分以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有该元素)为止。当有序线性表为顺序存储时才能采用二分法直找，效率比顺序查找高得多。对于长度为n的有序线性表，在最坏的情况下，二分法查找只需要比较次。10. 排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。(1) 交换类排序法交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法和快速排序法部属于交换类的排序方法。 冒泡排序冒泡排序基本过程如下：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的太小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，最后线性表中的最大者换到了表的最后面。然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，最后就将剩下线性表中的最小者换到了表的最前面。对剩下的线性表重复上述过程，直到剩下的线性表变空为止。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。 快速排序快速排序法的基本思想为：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分，T插入到分界线的位置处，这个过程称为线性表的分隔。如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。(2) 插入排序法所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。 简单插入排序法在线性表中，只包含第1个元素的子表显然可以看成是有序表。接下来的问题是，从线性表的第二个元素开始直到最后一个元素逐次将其中的每一个元素插入到前面已经有序的子表中。一般来说，假设线性表中前j1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，插入过程如下：首先将第j个元素放到一个变量T中。然后从有序子表的最后一个元素(即线性表中第j-1个元素)开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止此时就将T(即原线性表中的第j个元素)插入到刚移出的空位置上有序子表的长度就变为j了。在简单插入排序中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。 希尔排序法希尔排序发的基本思想如下：将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法如下：将相隔某个增量h的元素构成个子序列。在排序过程中逐次减小这个增量，最后当h减到l时进行一次插入排序，排序就完成。增量序列一般取，其中n为待排序序列的长度。希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列，则在最坏的情况下，希尔排序发所需要的比较次数为 (3) 选择类排序 简单选择排序选择排序的基本思想如下：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面(这是它应有的位置)：然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第个元素进行交换。简单选择排序在最坏情况下需要比较n(n-1)/2次。 堆排序堆的定义如下：具有n个元素的序列，当且仅当满足时称之为堆。这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素(即第一个元素)必为最大项。调整建堆：在一棵具有n个结点的完全二叉树(用维数组H(1：n)表示)中，假设结点H(m)的左右子树均为堆。现要将以H(m)为根结点的子树也调整为堆。调整建堆的具体方法是，将根结点值与左、右子树的根结点值进行比较若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。无序序列建堆：假设正序序列H(1：n)以完全二叉树表示。从完全二义树的最后一个非叶子结点（即第一个元素）为止，对没一个结点进行调整建堆，最后就可以得到与该序列对应的堆。根据堆的定义，可以得到对排序的方法如下：首先将一个无序序列建成堆。然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做此步，直到剩下的子序列为空为止。在最坏的情况下，堆排序需要比较的次数为第二章 程序设计基础2.1 程序设计方法与风格就程序设计方法和技术的发展而言，程序设计主要经过了结构化程序设计和面向对象的程序设计阶段。要形成良好的程序设计风格，主要应注意和考虑下述一些因素。1. 源程序文档化源程序文档化应注重和考虑下述一些因素。 符号的命名：符号名应具有一定的实际含义，以便于对程序功能的理解。 程序注释；正确的注释能够帮助读者理解程序。注释一般分为序言性注释和功能性注释。 视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。2. 数据说明的方法数据说明的风格一般应注意如下几点： 数据说明的次序规范化。 说明语句中变量安排有序化。 使用注释来说明复杂数据的结构。3. 语言结构程序应简单易懂，语句构造应简单直接。一般应注意如下：1. 在一行内只写一条语句。2. 程序编写应优先考虑清晰性。3. 除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。4. 首先要保证程序正确然后才要求提高速度。5. 避免使用临时变量而使程序的可读性下降。6. 避免不必要的转移。7. 尽可能使用库函数。8. 避免采用复杂的条件语句。9. 尽量减少使用“否定”条件的条件语句。10. 数据结构要有利于程序的件化。11. 要模块化，使模块功能尽可能单一化。12. 利用信息隐蔽，确保每一个模块的独立性。13. 从数据出发去构造程序。14. 不要修补不好的程序要重新编写。4. 输入和输出输入和输出方式和格式应尽可能方便用户的使用。在设计和编程时应考虑如下原则： 对所有的输入数据都要检验数据的合法性。 检查输入项的各种重要组合的合理性。 输入格式要简单，以使得输入的步骤和操作尽可能简单。 输入数据时，应允许使用自由格式。 应允许缺省值。 输入一批数据时，最好使用输入结束标志。 在以交互输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息。 当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性给所有的输出加注释，并设计输出报表格式。2.2 结构化程序设计1. 结构化程序设计的原则结构化程序设计方法的主要原则为自顶向下，逐步求精，模块化，限制使用goto语句。 自项向下：程序设计时，应先考虑总体，后考虑细节：先考虑全局目标，后考虑局部目标。先从最上层总目标开始设训逐步使问题具体化。 逐步求精：对复杂问题，应设计些子目标作过渡，逐步细化。 模块化：一个复杂问题，是由若干个简单问题构成的。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。 限制使用goto语句：滥用goto语句有害应尽量避免。2. 结构化程序的基本结构和特点采用结构化程序设计方法编写程序可使程序结构良好、易读、易理解、易维护。程序设计语言仅用顺序、选择、重复三种基本控制结构就可以表达出各种其他形式结构的程序设计方法。 顺序结构：顺序结构是顺序执行结构，所谓顺序执行，就是按照程序语句行的自然顺序一条语句、一条语句地执行程序。 选择结构：又称为分支结构，它包括简单选择和多分支选择结构。这种结构根据设定的条件判断应该选择哪一条分支来执行相应的语句。 重复结构：又称循环结构，它根据给定的条件判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。重复结构有两类循环语句，先判断后执行循环体的称为当型循环结构，先执行循环体后判断的称为直到型循环结构。遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有的优点为：其一，程序易于理解、使用和维护。其二，提高了编程工作的效率，降低了软件开发成本。3结构化程序的设计原则和方法的应用在结构化程序设计具体实施中，要注意把握如下因素： 使用程序设计语言的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。 选用的控制结构只准许有一个入口和一个出口。 程序语句组成容易识别的块，每块只有一个入口和一个出口。 复杂结构应该应用嵌套的基本控制结构进行组合嵌套来实现。 语言种所没有的控制结构，应该采用前后一致的方法来模拟。 严格控制goto语句的使用。其意思是指：(1) 用一个非结构化的程序设计语言去实现一个结构化的构造；(2) 若不使用GOT0语句会使功能模糊；(3) 在某种可以改善而不是损害程序可读性的情况下。2.3 面向对象的程序设计1. 面向对象方法的主要优点面向对象方法的主要优点如下：与人类习惯的思维方式一致；稳定性好：可重用性好；易于开发大型软件产品；可维护性好。2. 面向对象技术的基本概念(1) 对象(object)面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作类改变。对象可以做的操作表示它的动态行为，在面向对象分析和面向对象设计中，通常把对象的操作也称为方法或服务。对象有如下一些基本特点： 标识惟一性。指对象是可以区分的。由它的内在本质来区分。 分类性。指将具有相同属性和操作的对象抽象成类。 多态性。指同一个操作可以是不同对象的行为。 封装性。从外部看只能看到对象的外部特征性，即只需知道数据的取值范围和可以对该数据施加的操作，而无需知道数据的具体结构以及实现操作的算法。对象内部，即处理能力的实行和内部状态对外不可见。 模块独立性好。对象是面向对象软件的基本模块。对象以数据为中心，操作围绕对其数据所需做的处理来设置，没有无关的操作。因此，对象内部各种元素彼此结合得很紧密，内聚性强。(2) 类(class)和实例(Instance)类是具有共同属性、共同方法的对象的集合。类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象是其对应类的一个实例。类同对象一样，也包括一组数据属性和在数据上的一组合法操作。(3) 消息(message)消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。消息的使用类似于函数调用，消息中指定了某一个实例，一个操作和一个参数表。(4) 继承(inheritance)继承是使用已有的类定义作为基础建立新类的定义技术。在面向对象技术中，把类组成一个层次结构的系统：一个类的上层可以有父类，下层可以有子类。一个类直接继承其父类的描述(数据和操作)或特性，子类自动地共享基类中定义的数据和方法。继承分为单继承与多继承。单继承是指一 个类只允许有一个父类，即类等级为树形结构。多重继承是指，一个类允许有多个父类。使用多重继承的类可以组合多个父类的性质构成所需要的性质。(5) 多态性对象根据所接受的信息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。在面向对象技术中，多态性是指子类对象可以像父类对象那 样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。第三章 软件工程基础3.l软件工程基本概念1. 软件及软件工程的定义软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。程序是软件开发人员根据用户需求开发的，用程序设计语言描述的、适合计算机执行的指令序列。数据是使程序能正常操纵信息的数据结构。文档是与程序开发、维护和使用有关的图文资料。软件的特点：1. 软件是一种逻辑实体，而不是物理实体，具有抽象性。2. 软件的生产与硬件不同，它没有明显的制作过程。3. 软件在运行、使用期间不存在磨损、老化问题4. 软件的开发、运行对计算机系统具有依赖性，受其限制5. 软件复杂性高，成本昂贵。6. 软件开发涉及诸多的社会因素。软件按功能可分为：应用软件，系统软件，支撑软件（工具软件）。软件工程学是用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法的的一门工程学科。软件危机：泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。其可以归结为成本、质量生产率等问题。软件工程就是试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法。其主要思想是强调在软件开发过程中需要应用工程化原则。软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素，即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。软件工程过程是是把输入转化为输出的一组彼此相关的饿资源和活动。其通常包含4种基本活动：P-软件规格说明D-软件开发C-软件确认A-软件演进2. 软件生命周期软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。还可将软件生命周期分为软件定义、软件开发及软件运行维护三个阶段。软件定义：分可行性研究与计划制定、需求分析两个阶段；软件开发：分软件设计（概要设计和详细设计）、软件编码和软件测试三大阶段。软件运行维护阶段包括使用、维护、退役。软件维护活动包括以下积累：改正性维护、适应性维护、完善性维护、预防性维护。软件维护是软件生命周期的最后一个阶段，也是持续时间最长、花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护的代价。软件生命周期的主要活动阶段是： 可行性研究与计划指定。确定待开发软件系统的开发目标和总的要求给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实施计划。 需求分析。对待开发软件提出的需求进行分析并给出详细定义。编写软件说明书及初步的用户手册，提交评审。 软件设计。系统设计人员和程序设计人员应该在反复理解软件需求的基础上，给出软件的结构、模块的划分、功能的分配以及处理流程。在系统比较复杂的情况下，设计阶段可分解成概要阶段和详细设计阶段。编写概要设计说明书、详细设计说明书和测试计划初稿，提交评审。 软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源程序的编码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划。 软件测试。在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。 运行和维护。将已交付的软件投入运行，并在运行使用中不断地维护，根据新提出的需求进行必要且可能的扩充和删改。3. 软件开发工具与软件开发环境软件开发工具与软件开发环境的使用提高了软件的开发效率、维护效率和软件质量。(1) 软件开发工具软件开发工具的完善和发展促进软件开发方法的进步和完善促进软件开发的高速度和高质量。软件开发工具的发展是从单项工具的开发逐步走向集成工具发展的，软件开发工具为软件工程方法提供了自动或半自动的软件支持环境。同时，软件开发方法的有效应用也必须得到相应工具的支持，否则方法将难以有效的实施。（2）软件开发环境软件开发环境或软件工程环境是全面支持软件开发全过程的软件工具集合。这些软件工具按照一定的方法或模式组合起来，支持软件生命周期内的各个阶段和各项任务的完成。计算机辅助软件工程（CASE）将各种软件工具、开发器和一个存放开发过程信息的中心数据库组合起来，形成软件工程环境。3.2 结构化分析方法1需求分析与需求分析方法软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析阶段的工