1、二级公共基础知识 2二级公共基础知识第一章 算法与数据结构第二章 程序设计基础第三章 软件工程基础第四章 数据库设计基础3第一章 算法与数据结构本章要求 算法的基本概念、算法复杂度的概念和意义（时间复杂度与空间复杂度）。 数据结构的定义、数据的逻辑结构与存储结构、数据结构的图形表示、线性结构与非线性结构的概念。 线性表的定义、线性表的顺序存储结构及其插入与删除运算。 栈和队列的定义、栈和队列的顺序存储结构及其基本运算。 线性单链表、双向链表与循环链表的结构及其基本运算。 树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中序和后序遍历。 顺序查找与二分法查找算法、基本排序算法（交换类排序、
2、选择类排序与插入类）。4第一章 算法与数据结构一、算法二、数据结构三、线性表四、栈五、队列六、线性链表七、树与二叉树八、查找技术九、排序技术5一、算法1.算法的基本概念算法是指为了解决某类问题而规定的一个有限长度的操作（指令）序列。 （1）算法的特点：可行性、确定性、有穷性、拥有足够的情报。（2）算法的两个基本要素：一是对数据对象的运算和操作，具体包括算术运算、逻辑运算、关系运算和数据传输等；二是算法的控制结构，具体包括顺序结构、选择结构和循环结构。62.算法的复杂度算法的复杂度(代价)是衡量算法好坏的量度，具体可分为两种:时间复杂度和空间复杂度。 （1）时间复杂度是指执行算法所需要的计算工作
3、量，即算法执行过程中所需要的基本运算次数。 通常记作：常见的时间复杂度有：（2）空间复杂度是指执行该算法所需要的内存空间。 具体包括（1）算法程序所占的空间；（2）输入的初始数据所占的存储空间；（3）算法执行过程中的额外空间 )()(nfOnT)2()3()2()2log()()2(log) 1 (nOnOnOnnOnOnOO7二、数据结构1.数据结构的基本概念数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。在此概念中:（1）数据是指所有能输入到计算机中并被计算机程序处理的符号的总称; （2）数据元素是指数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理;（3）一个数据元
4、素可以由若干个数据项组成,数据项是数据的最小单位。8数据结构有三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。 2.数据的逻辑结构数据的逻辑结构是指数据元素之间的逻辑关系，从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的逻辑结构的表示方法表示数据的逻辑结构时必须表示清楚两个关键点，一个是数据元素的集合D，另一个是数据元素之间的前后关系R。 表示数据结构的方法有两种：二元关系表和图形表示方法。 9A.二元关系表示方法：一个数据结构可以表示为B=（D、R），其中R用二元组来表示(a、b)。 a表示前件， b表示后件。例如，一年四季的数据结构可以表示成:B=（D、R）D
5、=春，夏，秋，冬R=（春，夏），（夏，秋），（秋，冬）B.在图形表示方法中，用中间标有元素值的方框来表示数据元素，称为数据结点，简称为结点；用一条有向线段从前件结点指向后件结点（注意：有时可以省略箭头）来表示元素之间的前后关系。10 例如，同样是一年四季的数据结构，若用图形方法表示则如图所示。 数据的逻辑结构一般分为两种:线性结构和非线性结构。 线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。如：一年四季。非线性结构：线性以外的数据结构。如：反映家庭成员间辈分关系的数据结构。11A.线性结构 线性表例:英文字母表 (A , B , C , ，X ,Y , Z)例:学生
6、成绩表 栈后进先出 队列先进先出8686胡孝臣胡孝臣986110398611039595刘忠赏刘忠赏98611079861107100100张卓张卓98611099861109成绩成绩姓名姓名学号学号12B.非线性结构 树形结构例:全校学生档案管理的组织方式 例:计算机文件管理系统也是典型的树形结构13 图形结构结点间的连结是任意的例:数据结构B(D,R) D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3), (3,4) , (2,4) 例:数据结构C(D,R)D= 1 , 2 , 3 R= (1,2), (2,3), (3,2), (1,3) 1
7、423213143.数据的存储结构数据的存储结构(又称物理结构):是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。数据的存储结构有4种：顺序存储方式、链式存储方式、索引存储方式和散列存储方式。需要注意的是，对于同一个逻辑结构来说，采用不同的存储结构时，其数据处理的效率是不同的。 4.数据的运算：检索、排序、插入、删除、修改等。 15三、线性表线性表是最简单的、最常用的一种线性结构。 1.线性表的定义:线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2， ，ai， ，an ，其中n称作表的长度，当n=0时，称作空表。线性表（非空线性
8、表）必须同时满足以下3个条件： （1）有且只有一个根结点a1，它无前件。（2）有且只有一个终端结点an，它无后件。（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 16 如下图所示的数据结构就是线性表 注：线性表的概念是从逻辑结构的角度说的，所以，判断是否为线性表时并不考虑其存储结构，线性表可以用四种不同的存储结构来表示。2.线性表的顺序存储结构 特点：（1）线性表中所有元素所占的存储空间是连续的;（2）线性表中各数据元素在存储空间中的存放顺序是按逻辑顺序依次存放的。 17 例：正确表示线性表(A1，A2，A3，A4)的顺序结构是( ) A) B) C)分析：选C
9、，选项C中线性表各元素的存储空间是连续的，而且元素的存储顺序与逻辑顺序一致。选项A中各元素的物理顺序与逻辑顺序不同。选项B中各元素所占的存储空间并不连续。 A1 A2 A3 A418顺顺序序存存储储存储地址存储地址存储内容存储内容an.ai.a2a1ADR(a1)ADR(a1)+kADR(a1)+(i-1)kADR(a1)+(n-1)kADR(aADR(ai i)=ADR(a)=ADR(a1 1)+)+（i-1)i-1)k每个元素所占用每个元素所占用的存储单元个数的存储单元个数首地址首地址起始地址起始地址基地址基地址 在线性表的顺序存储结构中可以计算各数据元素（数据起点）的起始地址。19顺序存
10、储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点:(1)随机存取。(2)作插入或删除操作时，需移动大量元素。(3)长度变化较大时，需按最大空间分配。(4)表的容量难以扩充。通常定义一个一维数组来表示线性表的顺序存储空间。203.线性表的顺序存储结构的插入运算设顺序表的结构如图所示，其插入运算的步骤如下：(1)判断是否上溢:首先判断为线性表开辟的存储空间是否已满，如果已满则不能插入，如果未满则继续做第二步。(2)空出第i个位置:从最后一个元素开始到插入的位置上的元素，将其中的每个元素均依次往后移动一位。(3)插入:把新元素放入所插入的位置。21插入位置与需要移动的元素个数
11、之间存在着一定的关系。当线性表很大时，其插入运算的效率是比较低的。具体情况如下所述：(1)最好的情况:如果插入位置在线性表的末尾，即在第n个元素之后插入新元素，则不需要移动线性表中的其他任何元素。(2)最坏的情况:如果插入位置在线性表的第1个元素之前，则需要移动表中的所有元素。(3)如果插入位置在第i（1in）个元素之前，则原来的第i个元素之后(包括第i个元素)的所有元素都必须移动。(4)在平均情况下，要在线性表中插入一个新元素，需要移动线性表中一半的元素。（n/2个）223.线性表的顺序存储结构的删除运算具体运算步骤如下:如果删除第i（1in）个元素，从第i+1个元素开始直到最后一个元素，将
12、其中的每个元素均依次往前移动一位。此时，线性表的长度变成了n-1。如下图： 23在线性表的顺序存储结构的删除运算中，删除一个数据元素之后，应移动原来的元素，而且删除位置与需要移动的元素个数之间存在着一定的关系。所以当线性表很大时，其删除运算的效率也是比较低的。具体情况如下所述：(1)最好的情况:如果删除位置在线性表的末尾，即删除第n个元素，则不需要移动线性表中的其他任何元素。(2)最坏的情况:如果删除线性表的第1个元素，则需要移动表中的所有元素。 (3)在平均情况下，要删除线性表中的一个元素，需要移动表中的(n-1)/2个元素。 24四、栈1.栈的定义：栈是一种特殊的线性表，特殊在其数据操作上
13、，即限定在一端进行插入与删除的线性表。在栈中，允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。往栈中插入一个元素叫入栈运算（压栈）从栈中删除一个元素称为退栈运算（弹栈）栈的数据操作原则是先进后出FILO（FirstIn Last Out）或后进先出LIFO。栈具有一定的记忆作用。 252.栈的存储结构在程序设计语言中，与普通线性表一样，用一维数组作为栈S(l:m)的顺序存储结构，其中m为栈的最大容量。通常用指针top来指示栈顶的位置，用指针bottom指向栈底。当top=0时为空栈，当top等于数组的最大下标值时则栈满。3.栈的基本运算 有三种:入栈、退栈和读栈顶元素。 (1
14、)入栈运算的步骤 ：首先，判断栈是否为满，如果满则不能入栈(方法top=n)；其次，将栈顶指针进一(即 top加1)；26 最后，将新元素放入栈顶指针指向的位置中。值得注意的是，在入栈运算中应避免上溢错误的出现。上溢错误是指当栈顶指针己经指向存储空间的最后一个位置时，说明栈的空间己满，不能再进行入栈操作，这种情况称为栈“上溢”错误。 (2)退栈运算的步骤：首先，判断栈是否为空(方法top=0);其次，将栈顶元素赋值给一个指定的变量;最后，栈顶指针退一(即top减1)。值得注意的是，退栈运算中应避免下溢错误的出现。 27 (3) 读栈顶元素的步骤：读栈顶元素是指将栈顶元素赋值给一个指定的变量。读
15、枝顶元素过程中应注意的问题有:第一，读栈顶元素不是删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变，这是与入栈运算的区别;第二，当栈顶指针为0时，说明栈为空，读不到栈顶元素。 28五、队列1.队列的基本概念：队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种特殊的线性表。允许插入的一端叫队尾(尾指针， Rear，指向队尾元素)，允许删除的一端叫队头(头指针， Front，指向队头元素的前一个位置)。队列的数据操作方法:先进先出FIFO/LILO。29队列的一个重要应用是在操作系统中的管理用户程序上。即在操作系统中，用队列来组织管理用户程序的排队执
16、行，其原则是:(1)初始时该队列为空; (2)当有用户程序到来时，将该用户程序加入到队列的末尾进行等待;(3)当计算机系统执行完当前的用户程序后，就从队列头部取出一个用户程序执行。 与栈一样，程序设计中用一维数组作为队列的顺序存储空间。302.循环队列在实际应用中，队列的顺序存储结构一般采用循环队列的形式。原理:循环队列是指当队列存储空间的最后一个位置己被使用而仍要进行入队运算，这时只要存储空间的第一个位置空闲，便可以将元素加入到这个位置，即将存储空间的第一个位置作为队尾，如图所示。 31在循环队列中，从头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元
17、素。循环队列的初始状态为空，即：rear=front=m，如图所示。循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就进一。当队尾指针rear=m+1时，则置rear=1；每进行一次退队运算，排头指针就进一。当排头指针front=m+1时，则置front=132例：图（a）是一个容量为8的循环队列存储空间，且其中已有6个元素。图（b）是在图（a）的循环队列中又加入了两个元素后的状态。图（c）是在图（b）的循环队列中退出了1个元素后的状态。Q(1:8)8rear7 F6 E5 D4 C3 B2 Afront1 Q(1:8)8 X7 F6 E5 D4 C3 B2 Afr
18、ontrear 1 YQ(1:8)8 X7 F6 E5 D4 C3 Bfront 2 rear 1 Y（a）具有6个元素的循环队列 （b）加入X、Y后的循环队列 （c）退出一个元素后的循环队列 从图（b）可以看出，当循环队列满时有front=rear，而当循环队列空时也有front=rear。即在循环队列中，当front=rear时，不能确定是队列满还是队列空。33为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下： s=0 表示队列空 s=1 表示队列非空由此可以得出队列空与队列满的条件如下： 队列空的条件为s=0； 队列满的条件为s=1且front=rear。循环队列入队与
19、退队的运算注意点当循环队列非空（s=1）且front=rear时，说明循环队列已满，不能入队运算，这种情况称为”上溢“。当循环队列为空（s=0）时，不能进行退队运算，这种情况称为”下溢“。34六、线性链表1.链式存储结构对于大的线性表或者变动频繁的线性表不宜用顺序存储，应该采用链式存储。链式存储的过程如图所示。 每个结点都由两部分组成：每个结点都由两部分组成：数据域数据域和和指指针域针域。数据域数据域存放元素值，存放元素值，指针域指针域存放指针。存放指针。数据元素之间逻辑上的联系由指针来体数据元素之间逻辑上的联系由指针来体现。现。35注：链式存储方式中的存储结点不一定是连续的；各结点的存储顺序
20、与数据元素之间的逻辑关系可以不一致；链式存储方式可以用于线性结构，也可用于非线性结构。2.线性链表线性链表是指线性表的链式存储结构。为了适应线性链表的链式存储结构，计算机存储空间被划分为一个一个小块，每个小块占若干个字节，通常称这些小块为存储结点。 36在线性链表中，头指针(head)很关键，不得丢失； 线性链表的最后一个结点的指针域为空，用NULL或0来表示； 空表(线性链表):当head(指向线性表的第一个结点的指针head称为头指针)等于NULL或0时，称为空表;单链表的缺点是只能找到后件，不能找到前件；为了克服单链表的缺点，出现了双向链表的概念。在双向链表中，把每个结点修改为由以下3部
21、分组成:左指针 数据元素 右指针37双向链表的结点结构如下图所示 ：双向链表克服了单向链表的只能找到后件不能找到前件的缺陷。3.栈的链式存储结构（带链的栈）38在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。当计算机系统需要存储结点时，退栈;当计算机系统释放存储结点时，入栈。4. 队列的链式存储结构（带链的队列）39对带链的队列的操作如下图所示：405.线性链表的基本运算线性链表的基本运算有3种:查找、插入和删除数据元素。（1）在线性链表中查找指定元素在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描
22、查找，在线性链表中寻找包含指定元素值的前一个结点。当找到包含指定元素的前一个结点后，就可以在该结点后插入新结点或删除该结点后的一个结点。在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下： 41 从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。（2）线性链表中的插入运算为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便
23、用于存储该元素的值。新结点可以从可利用栈中取得。然后将存放新元素值的结点链接到线性链表中指定的位置。42在线性链表中包含x的结点之前插入一个新元素b。其插入过程如下：（1）从可利用栈取得一个结点，设该结点号为p（即取得结点的存储序号存放在变量p中），并置结点p的数据域为插入的元素值b。（2）在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。（3）将结点p插入到结点q之后。为了实现这一步，只要改变两个结点的指针域内容即可： 使结点p指向包含元素x的结点（即结点q的后件结点）。 使结点q的指针域内容改为指向结点p。43在线性链表中包含x的结点之前插入一个新元素b。其插入过程如下图：4
24、4（3）线性链表的删除为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。在线性链表中删除包含元素x的结点，其删除过程如下：（1）在线性链表中寻找包含元素x的前一个结点，设该结点序号为q。（2）将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元素x的结点p的指针指向的结点。（3）将包含元素x的结点p送回可利用栈。45在线性链表中删除包含元素x的结点，其删除过程如下图所示：466.循环链表循环链表与单链表的主要区别:(1)在循环链表中增加了表头结点，其数据域为任意或根据需要来设置，指针域为指向线性表的第一个元素的结点；(2)循环链表
25、中的最后一个结点的指针域不为空，而是指向表头结点。 47循环链表的特征如下:(1)循环链表中永远至少有一个结点存在(表头结点)； (2)在对循环链表进行插入和删除的过程中，实现了空表和非空表的运算的统一；(3)在循环链表中，只要指出表中的任何一个结点的位置，就可以从它出发访问到表中的其他所有结点，而线性单链表做不到这一点；(4)在循环链表的运算过程中，不必单独考虑对空表和第一结点的处理问题。 48七、树与二叉树1.树树是一种非线性结构，树的数据结构为B=(D,R)，其中，D代表数据对象，是具有相同特性的数据元素的集合；R代表数据关系。若D为空集，则称为空树，否则：（1）在D中存在唯一的称为根的
26、数据元素root；（2）当n1时，其余结点可分为m（m0）个互不相交的有限集T1,T2,T3,其中每一个子集本身又是一颗符合本定义的树，称为根（root）的子树。 49在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。如图所示的结点A就是树的根。在树结构中，每个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。如图所示的结点K,L,F,G,M,I,J都是叶子结点。在树结构中，每个结点所拥有的后件个数称为该结点的度。例如图中结点D的度为3。50在树中所有结点中的最大的度称为树的度。如图示的树的度为3树结构具有明显的层次关系
27、，即树是一种层次结构。在树结构中，一般有如下分层:根结点在第一层，依次类推。树的最大层次称为树的深度。如图所示的树的深度为4。在树中，以某结点的子结点为根构成的树称为该结点的一颗子树 。例如在图所示的树中B结点有两颗子树在树中，叶子结点没有子树。树在计算机中通常用多重链表来表示。512.二叉树（1）二叉树的定义二叉树是一种特殊的树，非空二叉树只有一个根结点。如图所示，每个根结点最多有两棵子树，分别称为该结点的左子树和右子树。52（2）二叉树的性质：性质1: 在二叉树的第k层上，最多有2k-1（k1）个结点。423167891011121314155第三层上第三层上(k=3)(k=3)，有，有2
28、 23-13-1=4=4个节点。个节点。第四层上第四层上(k=4)(k=4)，有，有2 24-14-1=8=8个节点。个节点。53性质2：深度为m的二叉树最多有2m-1个结点。 性质3：在任意一棵二叉树中，度为0的结点(叶子结点)总比度为2的结点多一个。 性质4：具有n个结点的二叉树，其深度至少为log2n+1。其中，log2n表示取log2n 的整数部分。 122.2221210mm54（3）满二叉树满二叉树是特殊的二叉树。满二叉树是指除最后一层之外，每一层上的所有结点都有两个子结点。性质5：满二叉树上的第k层上有2k-1个结点。结构如图所示： 55（4）完全二叉树完全二叉树也是一种特殊的二
29、叉树。特殊在:除最后一层之外，每一层上的结点数均达到了最大值，在最后一层上只缺少右边的若干个结点。 56 性质6:设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左到右)用自然数1，2，3n给结点进行编号。对于编号为k(k=1，2，3n)的结点有以下结论：若k=1，则该结点为根结点，它没有父结点;若k1,则编号为k的结点的父结点为k/2。若2kn，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点，当然也没有右子结点。若2k+1n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。 57例： k=1，是树的根,无父结点;其左子结点为2*k=2,右子结点为2*k
30、+1=3 。k=6，其父结点为k/2= 3；其左子结点为2*k=12;2*k+1=1312 其无右子结点。k=9，其父结点为k/2= 4 ；2*k=1812，2*k+1=1912 其无左、右子结点11234567891012158性质7：具有n个结点的完全二叉树的深度为log2n+1。例：n=2 k=2 n=6 k=3 n=7 k=3 n=8 k=4 n=12 k=411234567891012159（5）二叉树的存储结构常见的二叉树的存储结构有两种:顺序存储结构和链式存储结构。 顺序存储结构：用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左至右的顺序存储。链式存储结
31、构：用链表来表示 一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表存储形式。链表中每个结点由3个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左子结点和右子结点所在的链结点的存储地址。Lchild data Rchild60二叉树链式存储结构示意图61（6）二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历分为三种：前序遍历、中序遍历、后序遍历。（1）前序遍历（根、左、右）访问根结点；前序遍历左子树；前序遍历右子树。（2）中序遍历（左、根、右）中序遍历左子树；访问根结点；中序遍历右子树。（3）后续遍历（左、右、根）后续遍历左子树；后续遍历右子树；访问根
32、结点。62例：63（7）表达式树 表示表达式的树叫表达式树。用树来表示算术表达式的原则如下：（1）表达式中的每个运算符在树中对应一个结点，称为运算符结点；（2）运算符的每一个运算对象在树中为该运算符结点的子树，在树中的顺序为从左到右；（3）运算对象中的单变量均为叶子结点；（4）表达式树的表示方法必须按照特定的遍历方法 64例如，假设表达式为a(b+c/d)+ef-g，则其中序遍历的表达式树如图所示。 65八、查找技术查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法。常见的查找方法有两种：顺序查找、二分法查找。查找是数据处理中的重要环节，一般认为查
33、找的效率将直接影响到数据处理的效率。（1）顺序查找顺序查找是指从线性表的一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示查找成功；若找不到相等的元素则查找失败。 66顺序查找的最好的查询次数是指所查找的元素是线性表的第一个元素时的查询次数。最差的查询次数是指所查找的元素是线性表的最后一位元素或者在线性表中根本不存在这个元素时的查询次数。顺序查找的平均查询次数为大约需要与线性表中一半的元素进行比较的次数。对于庞大的线性表来说，顺序查找的效率是很低的。但是在下列两种情况下只能采用顺序查找：（1）线性表是无序表，即表中的元素的排列是无序的，则不管是顺序结构还是链式结构，都只能用顺序
34、查找；（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 67（2）二分法查找二分法查找只适用于顺序存储的有序表。其中，“有序表”是指已对顺序存储结构排序，但允许相邻元素值相等。 设有序列表的长度为n，被查找的元素为x，则二分法查找的方法如下：将x与线性表中的中间项进行比较： 若中间项的值等于x，则说明查到，查找结束； 若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找； 若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。上述过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。 68二分法查找的优
35、点主要有两个:（1）二分法查找的效率比顺序查找高得多；（2）对于长度为n的有序线性表，在最坏的情况下，二分法查找只需要比较log2n次,而顺序查找需要比较n次。69九、排序技术排序是指将一个无序的列表整理成按值递减（或递增）顺序排列的有序序列。常见的排序方法有:交换类排序、插入类排序和选择类排序。（1）交换式排序交换类排序法是指借助数据元素之间的相互交换进行排序的一种方法。 典型交换类排序法实例有两种：冒泡排序和快速排序。 70冒泡排序:通过相邻数据元素交换逐步将线性表变换成有序的。快速排序:将原问题分解成若干个小规模的同结构的问题，递归解决每个子问题。（2）插入类排序 插入类排序方法是指将无
36、序列表中的各元素依次插入到已经有序的线性表中。插入类排序的典型实例有：简单插入排序法和希尔排序法（Shell sort）。 71简单插入排序法：将无序列表中的各元素依次插入到已有序的线性表中。希尔排序法:这是对简单插入排序法的改进，先选取第一个增量，把距离为第一个增量的倍数的记录放在同一组中，在组内进行直接插入排序，再取小于第一个增量的第二个增量，重复上述操作。（3）选择类排序选择类排序法的典型实例有:简单选择排序方法和堆排序方法。 简单选择排序:扫描整个线性表，从中选出最小的元素，将它交换到表的最上面。然后对剩下的子表采取相同的方法，直到子表空为止。72（4）各种排序方法的性能 不同排序方法
37、的时间复杂度、空间复杂度可能是不同的。如下表所示： 73假设线性表长度为n,在最坏的情况下 ，各种排序方法的比较次数如下：（1）冒泡排序需要经过n/2遍的从前往后的扫描和n/2次的从后往前的扫描，需要的比较次数为n(n-1)/2（2）快速排序方法的比较次数为O(n2)=n(n-1)/2 （3）简单插入排序需要的比较次数为n(n-1)/2;（4）希尔排序的比较次数为O(n1.5) ；（5）简单选择排序的比较次数为n(n-1)/2 ；（6）堆排序的比较次数为O(nlog2n)=nlog2n+nC(1)，其中C(1)表示对长度为1的区间进行快速排序所需的比较次数。 74第二章 程序设计基础本章要求程
38、序设计方法与风格。 结构化程序设计。 面向对象的程序设计方法，对象、方法、属性及继承与多态性。75第二章 程序设计基础一、程序设计方法和风格二、结构化程序设计三、面向对象的程序设计76一、程序设计方法和风格良好的程序设计风格 良好的程序设计风格应遵循一个总体原则，即“清晰第一、效率第二”。具体应注意以下几个问题。（1）源程序文档化。符号命名的技巧。应具有一定的实际含义，以便于对程序功能的理解。程序注释。注释一般分为序言性注释和功能型注释两种。序言性注释通常位于程序的开头部分，它是对程序进行整体说明。功能性注释的位置一般嵌在源程序之中，主要描述其后的语句或程序做什么。77 视觉组织。为了使程序的
39、结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。(2)数据说明的方法。设计原则:易于理解和维护。(3)语句的结构。 设计原则:清晰第一、效率第二、简单易懂。(4)程序的输入输出。设计原则:方便用户的使用。78二、结构化程序设计1.结构化程序设计的原则结构化程序设计的基本原则是:自顶向下、逐步求精、模块化、限制使用goto语句。 “自顶向下、逐步求精”是指应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。“模块化”是指把一个总目标分为多个分目标，一个分目标进一步分为多个小目标，每一个小目标称为
40、一个模块。79 “限制使用goto语句”是指为了提高程序清晰性，除了以下3种需况，应严格限制goto语句的使用。这3种情况如下所述。(1)用一个非结构化的程序设计语言去实现一个结构化的构造。(2)若不使用goto语句会使功能模糊，(3)在某种可以改善而不是损害程序可读性的情况下可以使用goto语句。2.结构化程序设计的基本结构有3种: 顺序结构、选择结构和重复结构 803.在结构化程序设计的具体实施中，要注意把握以下几小问题：（1）使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。（2）选用的控制结构只准许一个入口和一个出口。（3）复杂结构应该用嵌套的基本控制结构进行组合
41、嵌套来实现。（4）程序语句组成容易识别的块，每块只有一个入口和一个出口。（5）语言中所没有的控制结构，应采用前后一致的方法来模拟。（6）严格控制goto语句的使用。814.结构化程序设计的优缺点 优点: 易于理解、使用和维护; 提高了编程的工作效率，降低了软件开发成本。缺点:结构化程序设计中存一个严重问题，即对于大型、复杂的软件，由于其中内在的高耦合、低内聚，特别是当时团体开发的管理方法的不足，所以在20世纪70年代出现了软件危机、难以对系统进行维护。 82三、面向对象的程序设计1.面向对象方法的定义：面向对象方法是一种运用对象、类、继承、封装、聚合、关联、消息、多态性等概念来构造系统的软件开
42、发方法。面向对象的方法与技术开始走向实用（成熟）的标志性语言是smalltalk。传统结构化程序设计方法的核心是算法，面向对象的核心是对象（类）。 832.面向对象方法的优点面向对象方法的主要优点如下：（1）与人类思维习惯一致:主要强调模拟现实世界中的概念而不强调算法。（2）稳定性好:当对系统功能的需求发生变化时并不会引起软件结构的整体变化，往往仅需要作一些局部性的修改即可。（3）可重用性好:传统算法中的重用技术是利用标准库函数；在面向对象方法中有两种方法可以重复使用一个对象类，一是创建该类的实例，二是继承。（4）易于开发大型软件产品。（5）可维护性好。 843.对象对象是软件系统中用来描述客
43、观事物的一个实体，它是构成软件系统的一个基本单位。一个对象由一组属性和对这组属性进行操作的一组服务构成。其中，属性是指事务的特性，表示事务的静态特征；操作是指事务的功能，表示事务的动态特征。4. 类、对象、实例 类是具有相同属性和服务的一组对象的集合，它为属于该类的全部对象提供了统一的抽象描述，其内部包括属性和服务两个主要部分。类可以用来创建对象，对象是类的一个实例。注意：对象和实例是两个不同的概念。对象既可以指一个具体的对象，也可以泛指一般的对象；实例必须是指一个具体的对象。 855.封装 封装是指把对象的属性和服务结合成一个独立的系统单位，并尽可能隐蔽对象的内部细节。只是它要向外部提供接口
44、，这降低了对象间的耦合度。（耦合度是指对象和对象之间联系的紧密程度。对象之间的联系越紧密，其耦合度越大。耦合度越大，程序的可维护性越差。所以，在程序设计中强调“耦合度越低越好”。封装机制降低了对象间的耦合度。） 封装的目的：是实现信息隐蔽。 866.继承如果类A具有类B的全部属性和全部服务，而且具有自己特有的某些属性或服务，则A叫做B的特殊类，B叫做A的一般类。继承是指使用己经定义好的类来定义一个新类，原类与新类的关系是一般类与特殊类的关系，被继承与继承的关系。例如公司人员类、股东类和职员类之间存在继承关系，如图所示 继承是一种在多个类之间共享属性和操作的机制。继承分为两种：多继承和单继承87
45、7.消息消息是指一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，统一了数据流和控制流。 在面向对象中消息的使用与传统程序设计方法中函数的调用差不多。 例:Mycircle.show (blue)，其中mycircle是接受消息的对象的名字，show是操作名称，blue是消息的参数。 可见，消息只告诉接收者需要做哪些操作，但并不指示接收者应该怎样完成这些操作。 888.多态性多态是指同样的消息被不同的对象接收时可导致完全不同的行为。可以通过方法重载和方法重写来实现多态。利用多态性，用户能够发送一般形式的消息，而将所有的实现细节都留给接收信息的对象。9.关联与链类之
46、间的静态联系称作关联。链是关联的实例。 8910.总结下表是对传统程序设计方法与面向对象程序设计方法之间的对应关系的总结传统方法面向对象方法数据结构+算法+程序设计以对象为中心组织数据与操作数据对象的属性操作对象的服务类型与变量类与对象实例函数（过程）调用消息传递类型与子类型一般类与特殊类，继承构造类型整体-部分结构(配合)指针关联90第三章 软件工程基础本章要求软件工程基本概念、软件生命周期概念、软件工具与软件开发环境。结构化分析方法、数据流图、数据字典、软件需求规格说明书。结构化设计方法、总体设计与详细设计。软件测试的方法、白盒测试与黑盒测试、测试用例设计、软件测试的实施、单元测试、集成测
47、试和系统测试。程序的调试、静态调试与动态调试。91第三章 软件工程基础一、软件工程基本概念二、结构化分析方法三、结构化设计方法四、软件测试五、程序调试92一、软件工程基本概念1.软件软件是包括程序、数据及相关文档的完整集合，相对于硬件产品讲，软件是一种逻辑产品。软件按功能可以分为应用软件、系统软件和支撑软件3 种。（1）应用软件是为解决特定领域的应用而开发的软件，例如：事务处理软件、人工智能软件与会计软件等。（2）系统软件是为管理计算机本身而开发的软件，例如：操作系统、编译程序、汇编程序、网络软件与数据库软件等。（3）支撑软件是为开发软件和维护软件的软件。例如：计划进度管理软件、过程控制工具软
48、件与质量管理给配置管理工具软件等（软件工程有关）等。932.软件危机20 世纪60 年代末以后出现了软件危机。软件危机主要表现在成本、质量和生产率等3 个方面。产生的主要原因是软件开发和维护方法不正确。为了解决这种软件危机，出现了软件工程的概念。3.软件工程软件工程概念的出现源自软件危机。软件工程就是试图用工程、科学和数学的原理与方法研制、维护计算机软件的有关技术及管理方法。94软件工程有3 个要素：方法、工具和过程。其中，方法是完成软件工程项目的技术手段；工具用于支持软件的开发、管理、文档生成；过程用于支持软件开发的各个环节的控制和管理。软件工程的核心思想是把软件产品当作是一个工程产品来处理
49、，即强调在软件开发过程中需要应用工程化原则。4.软件工程过程软件工程过程是指把输入转化为输出的一组彼此相关的资源和活动。软件工程过程通常由4 个基本活动组成：plan （软件规格说明）、do（软件开发）、check（软件确认）、action（软件演进）。 955.软件生命周期软件的生命周期是指将软件产品从提出、实现、使用维护到停止使用退役的过程。软件的生命周期分为可行性分析与计划制定、需求分析、软件设计、软件实现、软件测试、运行和维护等阶段。6.软件工程的目标 软件工程的目标是在给定的成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互
50、操作性且满足用户需求的产品。 967.软件工程原则软件工程的原则有8 个：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。（1）抽象：抽取事务最基本的特征和行为，忽略非本质细节。（2）信息隐蔽：采用封装技术，将程序模块的实现细节隐藏起来，使模块接口尽量简单。（3）模块化：模块是程序中相对独立的成分，一个对立的编程单位，应有良好的接口定义。（4）局部化：保证模块之间具有松散藕合关系，模块内部具有较高的内聚性。 97 （5）确定性：软件开发过程中所有概念的表达应该是明确的，无歧义且规范的。（6）一致性：包括程序、数据和文档的整个软件系统的各模块应使用已知的概念、符号和术语；程序内
