全国计算机等级考试-二级-公共基础知识.ppt

,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,*,二级公共基础知识,二级公共基础知识,第一章 算法与数据结构,第二章 程序设计基础,第三章 软件工程基础,第四章 数据库设计基础,第一章 算法与数据结构,本章要求,算法的基本概念、算法复杂度的概念和意义（时间复杂度与空间复杂度）。,数据结构的定义、数据的逻辑结构与存储结构、数据结构的图形表示、线性结构与非线性结构的概念。,线性表的定义、线性表的顺序存储结构及其插入与删除运算。,栈和队列的定义、栈和队列的顺序存储结构及其基本运算。,线性单链表、双向链表与循环链表的结构及其基本运算。,树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中序和后序遍历。,顺序查找与二分法查找算法、基本排序算法（交换类排序、选择类排序与插入类）。,第一章 算法与数据结构,一、算法,二、数据结构,三、线性表,四、栈,五、队列,六、线性链表,七、树与二叉树,八、查找技术,九、排序技术,一、算法,1.,算法的基本概念,算法,是指为了解决某类问题而规定的一个有限长度的操作（指令）序列。,（,1,）算法的,特点,：,可行性、确定性、有穷性、拥有足够的情报。,（,2,）算法的两个,基本要素,：一是对数据对象的运算和操作，具体包括算术运算、逻辑运算、关系运算和数据传输等；二是算法的控制结构，具体包括顺序结构、选择结构和循环结构。,2.,算法的复杂度,算法的复杂度,(,代价,),是,衡量算法好坏的量度,，具体可分为,两种,:,时间复杂度和空间复杂度。,（,1,）,时间复杂度,是指执行算法所需要的,计算工作量,，即算法执行过程中所需要的,基本运算次数,。通常记作：常见的时间复杂度有：,（,2,）,空间复杂度,是指执行该算法,所需要的内存空间,。,具体包括,（,1,）,算法程序所占的空间；（,2,）输入的初始数据所占的存储空间；（,3,）算法执行过程中的额外空间,二、数据结构,1.,数据结构的基本概念,数据结构,就是,相互之间存在一种或多种特定关系的数据元素的集合,。在此概念中,:,（,1,）,数据,是指所有能输入到计算机中并被计算机程序处理的,符号的总称,;,（,2,）,数据元素是指数据的基本单位,，在计算机程序中通常作为一个整体进行考虑和处理,;,（,3,）一个,数据元素,可以由若干个,数据项,组成,数据项是数据的最小单位。,数据结构有三个方面的内容：,数据的逻辑结构、数据的存储结构、数据的运算。,2.,数据的逻辑结构,数据的逻辑结构,是,指数据元素之间的逻辑关系,，从逻辑关系上描述数据，它,与数据的存储无关，是独立于计算机的。,数据的逻辑结构的表示方法表示数据的逻辑结构时必须表示清楚两个关键点，一个是数据元素的集合,D,，另一个是数据元素之间的前后关系,R,。,表示数据结构的方法,有两种：二元关系表和图形表示方法。,A.,二元关系表示方法,：一个数据结构可以表示为,B=,（,D,、,R,）,，其中,R,用二元组来表示,(a,、,b),。,a,表示,前件,，,b,表示,后件,。,例如,，一年四季的数据结构可以表示成,:B=,（,D,、,R,）,D=,春，夏，秋，冬,R=,（春，夏），（夏，秋），（秋，冬）,B.,在,图形表示方法,中，用中间标有元素值的方框来表示数据元素，称为,数据结点,，,简称为结点,；用一条有向线段从前件结点指向后件结点（注意：有时可以省略箭头）来表示元素之间的,前后关系,。,例如，同样是一年四季的数据结构，若用图形方法表示则如图所示。,数据的逻辑结构一般分为两种,:,线性结构和非线性结构。,线性结构：,有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。如：一年四季。,非线性结构：,线性以外的数据结构。如：反映家庭成员间辈分关系的数据结构。,A.,线性结构,线性表,例,:,英文字母表,(A,B,C,，,X,Y,Z),例,:,学生成绩表,栈,后进先出,队列,先进先出,86,胡孝臣,95,刘忠赏,100,张卓,成绩,姓名,学号,B.,非线性结构,树形结构例,:,全校学生档案管理的组织方式,例,:,计算机文件管理系统也是典型的树形结构,图形结构,结点间的连结是任意的例,:,数据结构,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,4,2,3,2,1,3,3.,数据的存储结构,数据的存储结构,(,又称,物理结构,):,是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。,数据的存储结构有,4,种,：顺序存储方式、链式存储方式、索引存储方式和散列存储方式。,需要注意的是,，对于同一个逻辑结构来说，采用不同的存储结构时，其数据处理的效率是不同的。,4.,数据的运算：检索、排序、插入、删除、修改等。,三、线性表,线性表是,最简单的、最常用,的一种线性结构。,1.,线性表的定义,:,线性表是,n,个元素的有限序列，它们之间的关系可以排成一个线性序列：,a1，a2，,，ai，,，an,，其中,n,称作表的长度，当,n=0,时，称作空表。,线性表（非空线性表）必须同时满足以下,3,个条件：（,1,）,有且只有一个,根结点,a1,，它无前件。（,2,）,有且只有一个,终端结点,an,，它无后件。（,3,）除根结点与终端结点外，,其他所有结点有且只有一个前件，也有且只有一个后件,。,如下图所示的数据结构就是线性表,注：线性表的概念是从逻辑结构的角度说的，所以，判断是否为线性表时并不考虑其存储结构，线性表可以用四种不同的存储结构来表示。,2.,线性表的顺序存储结构 特点：（,1,）线性表中所有元素所占的,存储空间是连续的,;,（,2,）线性表中各数据元素在存储空间中的存放顺序是,按逻辑顺序依次存放的。,例：正确表示线性表,(A1,，,A2,，,A3,，,A4),的顺序结构是,()A)B)C),分析：选,C,，选项,C,中线性表各元素的存储空间是连续的，而且元素的存储顺序与逻辑顺序一致。选项,A,中各元素的物理顺序与逻辑顺序不同。选项,B,中各元素所占的存储空间并不连续。,A1 A2 A3 A4,顺序存储,存储地址,存储内容,an,.,ai,.,a2,a1,ADR(a1),ADR(a1)+k,ADR(a1),+(i-1)k,ADR(a1)+,(n-1)k,ADR(a,i,)=ADR(a,1,)+（i-1),k,每个元素所占用,的存储单元个数,首地址,起始地址,基地址,在线性表的顺序存储结构中可以计算各数据元素（数据起点）的起始地址。,顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点,:(1),随机存取。,(2),作插入或删除操作时，需移动大量元素。,(3),长度变化较大时，需按最大空间分配。,(4),表的容量难以扩充。,通常定义一个一维数组来表示线性表的顺序存储空间。,3.,线性表的顺序存储结构的插入运算设顺序表的结构如图所示，其插入运算的步骤如下：,(1),判断是否上溢,:,首先判断为线性表开辟的存储空间是否已满，如果已满则不能插入，如果未满则继续做第二步。,(2),空出第,i,个位置,:,从最后一个元素开始到插入的位置上的元素，将其中的每个元素均依次往后移动一位。,(3,),插入,:,把新元素放入所插入的位置。,插入位置与需要移动的元素个数之间存在着一定的关系。当线性表很大时，其插入运算的效率是比较低的。,具体情况如下所述：,(1,),最好的情况,:,如果插入位置在线性表的末尾，即在第,n,个元素之后插入新元素，则不需要移动线性表中的其他任何元素。,(2),最坏的情况,:,如果插入位置在线性表的第,1,个元素之前，则需要移动表中的所有元素。,(3),如果插入位置在第,i,（,1in,）个元素之前，则原来的第,i,个元素之后,(,包括第,i,个元素,),的所有元素都必须移动。,(4),在,平均情况下,，要在线性表中插入一个新元素，需要移动线性表中一半的元素。（,n/2,个）,3.,线性表的顺序存储结构的删除运算具体运算,步骤,如下,:,如果删除第,i,（,1in,）个元素，,从第,i+1,个元素开始,直到最后一个元素，将其中的每个元素均依次往前移动一位。此时，线性表的长度变成了,n-1,。如下图：,在线性表的顺序存储结构的删除运算中，删除一个数据元素之后，应移动原来的元素，而且,删除位置与需要移动的元素个数之间存在着一定的关系。所以当线性表很大时,，,其删除运算的效率也是比较低的,。具体情况如下所述：,(1),最好的情况,:,如果删除位置在线性表的末尾，即删除第,n,个元素，则不需要移动线性表中的其他任何元素。,(2),最坏的情况,:,如果删除线性表的第,1,个元素，则需要移动表中的所有元素。,(3),在,平均情况下,，要删除线性表中的一个元素，需要移动表中的,(n-1)/2,个元素。,四、栈,1.,栈的定义：栈是一种,特殊的,线性表，,特殊在,其数据操作上，,即限定在一端进行插入与删除的线性表,。在栈中，允许插入和删除的一端称为,栈顶,，而不允许插入和删除的另一端称为,栈底,。,往栈中插入一个元素叫入栈运算（压栈）,从栈中删除一个元素称为退栈运算（弹栈）,栈的数据操作原则是先进后出,FILO,（,FirstIn Last Out,）或后进先出,LIFO,。栈具有一定的记忆作用。,2.,栈的存储结构在程序设计语言中，,与普通线性表一样,，用,一维数组,作为栈,S(l:m),的顺序存储结构，其中,m,为栈的最大容量,。通常用指针,top,来指示栈顶的位置，用指针,bottom,指向栈底。当,top=0,时为空栈，当,top,等于数组的最大下标值时则栈满。,3.,栈的基本运算 有三种,:,入栈、退栈和读栈顶元素,。,(1),入栈运算的步骤,：首先，,判断栈是否为满,，如果满则不能入栈,(,方法,top=n),；其次，将栈顶,指针进一,(,即,top,加,1),；,最后，将新元素,放入,栈顶指针指向的位置中。,值得注意的是,，在入栈运算中应避免上溢错误的出现。上溢错误是指当栈顶指针己经指向存储空间的最后一个位置时，说明栈的空间己满，不能再进行入栈操作，这种情况称为栈,“,上溢,”,错误。,(2),退栈运算的步骤：,首先,，判断栈是否为空,(,方法,top=0);,其次，将栈顶元素,赋值,给一个指定的变量,;,最后，,栈顶指针退一,(,即,top,减,1),。,值得注意的是,，退栈运算中应避免,下溢,错误的出现。,(3),读栈顶元素的步骤,：读栈顶元素是指将栈顶元素,赋值,给一个指定的变量。读枝顶元素过程中,应注意的问题有,:,第一，,读栈顶元素不是删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变，这是与入栈运算的区别,;,第二,，当栈顶指针为,0,时，说明栈为空，读不到栈顶元素。,五、队列,1.,队列的基本概念：,队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种特殊的线性表。允许插入的一端叫,队尾,(,尾指针，,Rear,，指向队尾元素,),，,允许删除的一端叫,队头,(,头指针，,Front,，指向队头元素的前一个位置,),。,队列的,数据操作方法,:,先进先出,FIFO/LILO,。,队列的一个,重要应用是,在操作系统中的管理用户程序上。即,在操作系统中，用队列来组织管理用户程序的排队执行，其原则是,:(1),初始时该队列为空,;(2),当有用户程序到来时，将该用户程序加入到队列的末尾进行等待,;(3),当计算机系统执行完当前的用户程序后，就从队列头部取出一个用户程序执行。,与栈一样，程序设计中用一维数组作为队列的顺序存储空间。,2.,循环队列在实际应用中，队列的顺序存储结构一般采用,循环队列的形式,。,原理,:,循环队列是指当队列存储空间的最后一个位置己被使用而仍要进行入队运算，这时只要存储空间的第一个位置空闲，便可以将元素加入到这个位置，即将存储空间的第一个位置作为队尾，如图所示。,在循环队列中，从头指针,front,指向的后一个位置直到队尾指针,rear,指向的位置之间所有的元素均为队列中的元素。,循环队列的初始状态为空，即：,rear=front=m,，如图所示。,循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就进一。当队尾指针,rear=m+1,时，则置,rear=1,；每进行一次退队运算，排头指针就进一。当排头指针,front=m+1,时，则置,front=1,例：图（,a,）是一个容量为,8,的循环队列存储空间，且其中已有,6,个元素。图（,b,）是在图（,a,）的循环队列中又加入了两个元素后的状态。图（,c,）是在图（,b,）的循环队列中退出了,1,个元素后的状态。,Q(1:8),8,rear7 F,6 E,5 D,4 C,3 B,2 A,front1,Q(1:8),8 X,7 F,6 E,5 D,4 C,3 B,2 A,front,rear,1 Y,Q(1:8),8 X,7 F,6 E,5 D,4 C,3 B,front 2,rear,1 Y,（,a,）具有,6,个元素的循环队列 （,b,）加入,X,、,Y,后的循环队列 （,c,）退出一个元素后的循环队列,从图（,b,）可以看出，当循环队列满时有,front=rear,，而当循环队列空时也有,front=rear,。即在循环队列中，当,front=rear,时，不能确定是队列满还是队列空。,为了能区分队列满还是队列空，通常还需增加一个标志,s,，,s,值的定义如下：,s=0,表示队列空,s=1,表示队列非空由此可以得出队列空与队列满的条件如下：队列空的条件为,s=0,；队列满的条件为,s=1,且,front=rear,。,循环队列入队与退队的运算注意点当循环队列非空（,s=1,）且,front=rear,时，说明循环队列已满，不能入队运算，这种情况称为,”,上溢,“,。当循环队列为空（,s=0,）时，不能进行退队运算，这种情况称为,”,下溢,“,。,六、线性链表,1.,链式存储结构对于大的线性表或者变动频繁的线性表不宜用顺序存储，应该采用链式存储。链式存储的过程如图所示。,每个结点都由两部分组成：数据域和指针域。,数据域,存放元素值，,指针域,存放指针。,数据元素之间逻辑上的联系由指针来体现。,注：链式存储方式中的存储结点不一定是连续的；各结点的存储顺序与数据元素之间的逻辑关系可以不一致；链式存储方式可以用于线性结构，也可用于非线性结构。,2.,线性链表线性链表是,指线性表的链式存储结构,。为了适应线性链表的链式存储结构，计算机存储空间被划分为一个一个小块，每个小块占若干个字节，通常称这些小块为,存储结点。,在线性链表中，头指针(head)很关键，不得丢失；,线性链表的最后一个结点的指针域为空，用NULL或0来表示；,空表(线性链表):当head(指向线性表的第一个结点的指针head称为头指针)等于NULL或0时，称为空表;,单链表的缺点是只能找到后件，不能找到前件；,为了克服单链表的缺点，出现了双向链表的概念。在双向链表中，把每个结点修改为由以下3部分组成:,左指针 数据元素 右指针,双向链表的结点结构如下图所示：,双向链表克服了,单向链表的只能找到后件不能找到前件的缺陷。,3.,栈的链式存储结构（带链的栈）,在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。当计算机系统需要存储结点时，退栈,;,当计算机系统释放存储结点时，入栈。,4.,队列的链式存储结构（带链的队列）,对带链的队列的操作如下图所示：,5.,线性链表的基本运算线性链表的基本运算有,3,种,:,查找、插入和删除数据元素。,（,1,）在线性链表中,查找,指定元素在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素值的前一个结点。当找到包含指定元素的前一个结点后，就可以在该结点后插入新结点或删除该结点后的一个结点。在非空线性链表中寻找包含指定元素值,x,的前一个结点,p,的基本方法如下：,从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为,x,为止。因此，由这种方法找到的结点,p,有两种可能：当线性链表中存在包含元素,x,的结点时，则找到的,p,为第一次遇到的包含元素,x,的前一个结点序号；当线性链表中不存在包含元素,x,的结点时，则找到的,p,为线性链表中的最后一个结点号。,（,2,）线性链表中的,插入,运算为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素的值。新结点可以从可利用栈中取得。然后将存放新元素值的结点链接到线性链表中指定的位置。,在线性链表中包含,x,的结点之前插入一个新元素,b,。其插入过程如下：（,1,）从可利用栈取得一个结点，设该结点号为,p,（即取得结点的存储序号存放在变量,p,中），并置结点,p,的数据域为插入的元素值,b,。（,2,）在线性链表中寻找包含元素,x,的前一个结点，设该结点的存储序号为,q,。（,3,）将结点,p,插入到结点,q,之后。为了实现这一步，只要改变两个结点的指针域内容即可：使结点,p,指向包含元素,x,的结点（即结点,q,的后件结点）。使结点,q,的指针域内容改为指向结点,p,。,在线性链表中包含x的结点之前插入一个新元素b。其插入过程如下图：,（,3,）线性链表的,删除,为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。在线性链表中删除包含元素,x,的结点，其删除过程如下：,（,1,）在线性链表中寻找包含元素,x,的前一个结点，设该结点序号为,q,。（,2,）将结点,q,后的结点,p,从线性链表中删除，即让结点,q,的指针指向包含元素,x,的结点,p,的指针指向的结点。（,3,）将包含元素,x,的结点,p,送回可利用栈。,在线性链表中删除包含元素x的结点，其删除过程如下图所示：,6.,循环链表,循环链表与单链表的主要区别,:,(1),在循环链表中增加了表头结点，其数据域为任意或根据需要来设置，指针域为指向线性表的第一个元素的结点；,(2),循环链表中的最后一个结点的指针域不为空，而是指向表头结点。,循环链表的特征如下,:,(1),循环链表中永远至少有一个结点存在,(,表头结点,),；,(2),在对循环链表进行插入和删除的过程中，实现了空表和非空表的运算的统一；,(3),在循环链表中，只要指出表中的任何一个结点的位置，就可以从它出发访问到表中的其他所有结点，而线性单链表做不到这一点；,(4),在循环链表的运算过程中，不必单独考虑对空表和第一结点的处理问题。,七、树与二叉树,1.,树,树是一种非线性结构,，树的数据结构为,B=(D,R),，其中，,D,代表数据对象，是具有相同特性的数据元素的集合；,R,代表数据关系。若,D,为空集，则称为空树，否则：（,1,）在,D,中存在唯一的称为根的数据元素,root,；（,2,）当,n,1,时，其余结点可分为,m,（,m,0,）个互不相交的有限集,T1,T2,T3,其中每一个子集本身又是一颗符合本定义的树，称为根（,root,）的子树。,在树结构中，每个结点只有一个前件，称为,父结点,，没有前件的结点只有一个，称为树的,根结点,，简称为树的根。如图所示的结点,A,就是树的根。,在树结构中，每个结点可以有多个后件，它们都称为该结点的,子结点,。没有后件的结点称为叶子结点。如图所示的结点,K,L,F,G,M,I,J,都是,叶子结点,。,在树结构中，每个结点所拥有的后件个数称为该,结点的度,。例如图中结点,D,的度为,3,。,在树中所有结点中的最大的度称为,树的度,。如图示的树的度为,3,树结构具有明显的层次关系，,即树是一种层次结构,。在树结构中，一般有如下分层,:,根结点在,第一层,，依次类推。,树的最大层次称为,树的深度,。如图所示的树的深度为,4,。,在树中，以某结点的子结点为根构成的树称为该结点的,一颗子树,。例如在图所示的树中,B,结点有两颗子树,在树中，叶子结点没有子树。,树在计算机中通常用多重链表来表示。,2.,二叉树,（,1,）二叉树的定义二叉树是一种特殊的树，非空二叉树只有一个根结点,。如图所示，每个根结点,最多有两棵子树,，分别称为该结点的,左子树和右子树,。,（,2,）二叉树的性质：,性质,1,:,在二叉树的第,k,层上，最多有,2,k-1,（,k1,）个结点。,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,第三层上,(k=3),，有,2,3-1,=4,个节点。,第四层上,(k=4),，有,2,4-1,=8,个节点。,性质,2,：,深度为,m,的二叉树最多有,2,m,-1,个结点。,性质,3,：在任意一棵二叉树中，度为,0,的结点,(,叶子结点,),总比度为,2,的结点多一个。,性质,4,：具有,n,个结点的二叉树，其深度至少为,log,2,n+1,。其中，,log,2,n,表示取,log,2,n,的整数部分。,（,3,）满二叉树满二叉树是特殊的二叉树。满二叉树是指除最后一层之外，每一层上的所有结点都有两个子结点。,性质,5,：满二叉树上的第,k,层上有,2,k-1,个结点。结构如图所示：,（,4,）完全二叉树完全二叉树也是一种特殊的二叉树。,特殊在,:,除最后一层之外，每一层上的结点数均达到了最大值，在最后一层上只缺少右边的若干个结点。,性质,6:,设完全二叉树共有,n,个结点。如果从根结点开始，按层序,(,每一层从左到右,),用自然数,1,，,2,，,3,n,给结点进行编号。对于编号为,k(k=1,，,2,，,3,n),的结点有以下结论：若,k=1,，则该结点为根结点，它没有父结点,;,若,k1,则编号为,k,的结点的父结点为,k/2,。,若,2kn,，则编号为,k,的结点的左子结点编号为,2k,，否则该结点无左子结点，当然也没有右子结点。若,2k+1n,，则编号为,k,的结点的右子结点编号为,2k+1,，否则该结点无右子结点。,例：,k=1,，是树的根,无父结点,;,其左子结点为,2*k=2,右子结点为,2*k+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,其无左、右子结点,11,2,3,4,5,6,7,8,9,10,12,1,性质,7,：具有,n,个结点的完全二叉树的深度为,log,2,n+1,。例：,n=2 k=2 n=6 k=3 n=7 k=3 n=8 k=4 n=12 k=4,11,2,3,4,5,6,7,8,9,10,12,1,（,5,）二叉树的存储结构,常见的二叉树的存储结构有两种,:,顺序存储结构和链式存储结构。,顺序存储结构,：用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左至右的顺序存储。,链式存储结构,：用链表来表示,一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表存储形式。链表中每个结点由,3,个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左子结点和右子结点所在的链结点的存储地址。,Lchild data Rchild,二叉树链式存储结构示意图,（,6,）二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。,二叉树的遍历分为三种：前序遍历、中序遍历、后序遍历。（,1,）前序遍历（根、左、右）访问根结点；前序遍历左子树；前序遍历右子树。（,2,）中序遍历（左、根、右）中序遍历左子树；访问根结点；中序遍历右子树。（,3,）后续遍历（左、右、根）后续遍历左子树；后续遍历右子树；访问根结点。,例：,（,7,）表达式树,表示表达式的树叫,表达式树,。用树来表示算术表达式的,原则,如下：（,1,）表达式中的每个运算符在树中对应一个结点，称为运算符结点；（,2,）运算符的每一个运算对象在树中为该运算符结点的子树，在树中的顺序为从左到右；（,3,）运算对象中的单变量均为叶子结点；（,4,）表达式树的表示方法必须按照特定的遍历方法,例如，假设表达式为a(b+c/d)+ef-g，则其中序遍历的表达式树如图所示。,八、查找技术,查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法。,常见的查找方法有两种：,顺序查找、二分法查找,。,查找是数据处理中的重要环节，一般认为查找的效率将直接影响到数据处理的效率。,（,1,）顺序查找,顺序查找,是指从线性表的一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示查找成功；若找不到相等的元素则查找失败。,顺序查找的,最好的查询次数,是指所查找的元素是线性表的第一个元素时的查询次数。,最差的查询次数,是指所查找的元素是线性表的最后一位元素或者在线性表中根本不存在这个元素时的查询次数。顺序查找的平均,查询次数,为大约需要与线性表中一半的元素进行比较的次数。对于庞大的线性表来说，顺序查找的效率是很低的。,但是在下列两种情况下只能采用顺序查找,：（,1,）线性表是无序表，即表中的元素的排列是无序的，则不管是顺序结构还是链式结构，都只能用顺序查找；（,2,）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,（,2,）二分法查找二分法查找,只适用于,顺序存储的有序表。其中，,“,有序表,”,是指已对顺序存储结构排序，但允许相邻元素值相等。设有序列表的长度为,n,，被查找的元素为,x,，则,二分法查找的方法如下,：将,x,与线性表中的中间项进行比较：若中间项的值等于,x,，则说明查到，查找结束；若,x,小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若,x,大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。上述过程一直进行到查找成功或子表长度为,0(,说明线性表中没有这个元素,),为止。,二分法查找的优点,主要有两个,:,（,1,）二分法查找的效率比顺序查找高得多；（,2,）对于长度为,n,的有序线性表，在最坏的情况下，二分法查找只需要比较,log,2,n,次,而顺序查找需要比较,n,次。,九、排序技术,排序,是指将一个无序的列表整理成按值递减（或递增）顺序排列的有序序列。,常见的排序方法,有,:,交换类排序、插入类排序和选择类排序。,（,1,）交换式排序交换类排序法是指借助数据元素之间的相互交换进行排序的一种方法。典型交换类排序法实例,有两种,：冒泡排序和快速排序。,冒泡排序,:,通过相邻数据元素交换逐步将线性表变换成有序的。,快速排序,:,将原问题分解成若干个小规模的同结构的问题，递归解决每个子问题。,（,2,）插入类排序 插入类排序方法是指将无序列表中的各元素依次插入到已经有序的线性表中。插入类排序的典型实例有：简单插入排序法和希尔排序法（,Shell sort,）。,简单插入排序法：将无序列表中的各元素依次插入到已有序的线性表中。,希尔排序法,:,这是对简单插入排序法的改进，先选取第一个增量，把距离为第一个增量的倍数的记录放在同一组中，在组内进行直接插入排序，再取小于第一个增量的第二个增量，重复上述操作。,（,3,）选择类排序选择类排序法的典型实例有,:,简单选择排序方法和堆排序方法。,简单选择排序,:,扫描整个线性表，从中选出最小的元素，将它交换到表的最上面。然后对剩下的子表采取相同的方法，直到子表空为止。,（,4,）,各种排序方法的性能,不同排序方法的时间复杂度、空间复杂度可能是不同的。如下表所示：,假设线性表长度为,n,在最坏的情况下，各种排序方法的比较次数如下：（,1,）冒泡排序需要经过,n/2,遍的从前往后的扫描和,n/2,次的从后往前的扫描，需要的比较次数为,n(n-1)/2,（,2,）快速排序方法的比较次数为,O(n,2,)=n(n-1)/2,（,3,）简单插入排序需要的比较次数为,n(n-1)/2;,（,4,）希尔排序的比较次数为,O(n,1.5,),；（,5,）简单选择排序的比较次数为,n(n-1)/2,；（,6,）堆排序的比较次数为,O(nlog,2,n)=nlog,2,n+nC(1),，其中,C(1),表示对长度为,1,的区间进行快速排序所需的比较次数。,第二章 程序设计基础,本章要求,程序设计方法与风格。,结构化程序设计。,面向对象的程序设计方法，对象、方法、属性及继承与多态性。,第二章 程序设计基础,一、程序设计方法和风格,二、结构化程序设计,三、面向对象的程序设计,一、程序设计方法和风格,良好的程序设计风格 良好的程序设计风格应遵循一个总体原则，即,“,清晰第一、效率第二,”,。具体应注意以下几个问题。（,1,）源程序文档化。符号命名的技巧。应具有一定的实际含义，以便于对程序功能的理解。程序注释。注释一般分为序言性注释和功能型注释两种。序言性注释通常位于程序的开头部分，它是对程序进行整体说明。功能性注释的位置一般嵌在源程序之中，主要描述其后的语句或程序做什么。,视觉组织。为了使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。,(2),数据说明的方法。设计原则,:,易于理解和维护。,(3),语句的结构。设计原则,:,清晰第一、效率第二、简单易懂。,(4),程序的输入输出。设计原则,:,方便用户的使用。,二、结构化程序设计,1.,结构化程序设计的原则结构化程序设计的基本原则是,:,自顶向下、逐步求精、模块化、限制使用,goto,语句。,“,自顶向下、逐步求精,”,是指应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。,“,模块化,”,是指把一个总目标分为多个分目标，一个分目标进一步分为多个小目标，每一个小目标称为一个模块。,“,限制使用,goto,语句,”,是指为了提高程序清晰性，除了以下,3,种需况，应严格限制,goto,语句的使用。这,3,种情况如下所述。,(1),用一个非结构化的程序设计语言去实现一个结构化的构造。,(2),若不使用,goto,语句会使功能模糊，,(3),在某种可以改善而不是损害程序可读性的情况下可以使用,goto,语句。,2.,结构化程序设计的基本结构有,3,种,:,顺序结构、选择结构和重复结构,3.,在结构化程序设计的具体实施中，要注意把握以下几小问题：（,1,）使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。（,2,）选用的控制结构只准许一个入口和一个出口。（,3,）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。（,4,）程序语句组成容易识别的块，每块只有一个入口和一个出口。（,5,）语言中所没有的控制结构，应采用前后一致的方法来模拟。（,6,）严格控制,goto,语句的使用。,4.,结构化程序设计的优缺点 优点,:,易于理解、使用和维护,;,提高了编程的工作效率，降低了软件开发成本。缺点,:,结构化程序设计中存一个严重问题，即对于大型、复杂的软件，由于其中内在的高耦合、低内聚，特别是当时团体开发的管理方法的不足，所以在,20,世纪,70,年代出现了,软件危机、难以对系统进行维护。,三、面向对象的程序设计,1.,面向对象方法的定义：面向对象方法是一种运用,对象、类、继承、封装、聚合、关联、消息、多态性等概念来构造系统,的软件开发方法。面向对象的方法与技术开始走向实用（成熟）的,标志性语言,是,smalltalk,。,传统结构化程序设计方法的核心是算法，面向对象的核心是对象（类）。,2.,面向对象方法的优点面向对象方法的,主要优点,如下：（,1,）与人类思维习惯一致,:,主要强调模拟现实世界中的概念而不强调算法。（,2,）稳定性好,:,当对系统功能的需求发生变化时并不会引起软件结构的整体变化，往往仅需要作一些局部性的修改即可。（,3,）可重用性好,:,传统算法中的重用技术是利用标准库函数；在面向对象方法中有两种方法可