二级公共基础知识.ppt

*,广东海洋大学,二 级 公 共 基 础 知 识,授课老师：,陈 小 瀚,授课时间：,2010,年,3,月,1,一、涉及面广，但难度小,你应该知道,公共基础知识考题特点及复习建议,计算机等级二级理论考试中有关公共知识部分的题目共有15道，涉及,算法及数据结构,、,程序设计基础,、,软件工程基础,和,数据库设计基础,等四门学科，但是从整体上分析，考试中的考核内容的难度不大，考点也相对集中些。,2,二、考核重点为基本概念、基本方法,和基本运算,你应该知道,计算机等级二级理论考试中涉及的题目都是,基本概念,、,基本方法,和,基本运算,，考核以概念和认识性内容为主，理解性、应用性内容极少。,3,三、考核重点是数据结构和算法,你应该知道,以下是对以往二级理论考试的大概统计：,算法及数据结构,：50%,程序设计基础,：12.5%,软件,工程基础,：18.75%,数据库设计基础,：18.75%,4,四、六点复习及应试建议,复习的关键是,考生必须准确判断和掌握常见考点,公共基础知识部分的知识点多、杂，考生在学习过程中应理,清其中的,脉络关系（即框架提纲）,，才能有效地组织和记住,各知识点,考生一开学习时,不要太追求灵活掌握该部分的内容,，经历一个“先熟记,再练习、熟能生巧”的过程，这是多数考生常用的一个方法。,答题技巧,：对不懂的题目，,不要拖时间，要考虑成本/效果的关系，为后面的题目提供时间,。,5,你应该知道,共讲授,6个学时，具体安排如下：,第,1,周周四（,3,月,11,日）晚上（,9-10,节）：,算法、数据结构（上）,（地点：,钟海楼,04025,）,第,2,周周一（,3,月,15,日）晚上（,9-10,节）,：,数据结构,(,下）、程序设计基础,（地点：钟海楼,04025,）,第,2,周周四（,3,月,18,日）晚上（,9-10,节）,：,软件工程、数据库系统,（地点：,钟海楼,04025,）,本 课 程 授 课 安 排,6,1、了解算法的基本概念和一些,常用的算法,，学会计算算法的,时间复杂度,；,2、掌握数据结构的基本概念，并了解数据的,逻辑结构,和,存储结构,，学会利,用图形的方式表示数据结构；,学,习,目,标,与,要,求,算法与数据结构：,3、了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的,线性表的基本运算；,4、了解栈和队列的基本概念，并掌握它们的基本运算；,5、了解线性链表的基本概念，并掌握线性链表的基本运算，同时，了解循,环链表的基本概念和基本操作；,6、理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存,储结构和遍历技术；,7、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据；,8、学会利用相关的排序技术实现无序数列的排序操作。,7,1、了解软件工程的基本概念；,2、了解软件工程过程与软件的,生命周期,，以及软件工程的,目标和原则,；,学,习,目,标,与,要,求,软件工程,：,3、了解利用结构化分析法进行软件工程中的需求分析的方法，并了解,需,求分析的方法和需要,完成的任务；,4、了解数据流图的使用方法；,5、了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些,常用工具；,6、了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件,测试方法的区别和各自的功能与特点；,7、了解程序调试的方法和原则。,8,1、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序,设计的基本规则；,2、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点;,学,习,目,标,与,要,求,程序设计基础,：,3、了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。,数据库系统,：,1、了解数据库系统的基本概念，以及数据库系统的发展；,2、了解数据模型的基本概念，并对,E-R,模型、层次模型、网状模型和关系模型,进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识；,3、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算；,4、了解数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。,9,程,序,设,计,基,本,概,念,一、计算机工作原理,通过工作原理了解，熟悉计算机内部执行功能的,基本意义。为理解程序打下基础，特别理解计算机是,机器。,二、程序的定义,指令的集合。（解释指令）,通过硬件控制系统自动完成某一功能。,通过一系列代码实现。,10,程,序,设,计,基,本,概,念,三、程序怎样执行、如何编写程序,计算机本身仅能识别二进制代码,“,0,”,、,“,1,”,。,编程最直接、最低级的就是机器语言。,为解决机器语言难理解、记忆等问题。出现符号语言。,为使编程接近自然语言，出现高级语言。如,C、PASCAL、FORTRAN,等。,为配合高级语言编程，出现了开发工具，提高效率、减轻劳动量。如,VB、VC、PB、Delphi、VFP,等。因此,VFP,不是编程语言。,11,程,序,设,计,基,本,概,念,不管什么形式编写代码，最终都应将代码翻译成机器语言，,这就是编译程序的工作。不同的语言有不同的编译器。,程序控制是一种逻辑控制。因此，严谨的逻辑思维是一个,程序员必备的基本素质。,用程序实现某一功能。有许多方法。具体用哪种完全取决,于程序员个人的思维方式。因此，程序是脑力劳动的结晶，,从某种意义上，编程又是一门艺术。,程序的特殊性决定了程序的复杂性，且与实现功能的复杂,性密切相关成正比。因此为使复杂的、智力的编程工作规,范化、科学化，便出现了各种编程设计方法。如结构化编,程方法、面向对象的程序设计方法等。,12,程,序,设,计,基,本,概,念,不管用什么方法编程，不管编程者智力程度如何，不管,采用什么样的编程语言和方法，程序最终完成的功能稳,定、可靠、实用、易维护和安全等是程序的最终目标，,也是程序员的追求。,程序设计是一个复杂艰巨的过程。编写代码仅是程序设,计的一部分。必须先有思想，再有方法，然后才是编写,代码，且要经过许多反复，不可急功近利。,13,程,序,设,计,基,本,概,念,四、程序设计语言或工具,程序设计语言指的是用来编写程序的语言。,人与计算机交流要使用语言，以便让计算机工作，计算,机也通过语言把结果告诉用计算机的人“人机对,话”。,人与计算机交流的语言非平常人与人之间交流的语言，,是专门的语言程序设计语言。,程序设计语言是计算机系统软件的重要组成部分。,14,程,序,设,计,基,本,概,念,执行程序设计的语言有很多，可分高级语言和低级语言，,区别在于接近自然语言的程度,高级语言一般与具体的计算机硬件无关，比较接近人类,自然语言的语法习惯及数学表达形式。,用高级语言编写的源程序不能被机器直接执行，需通过,编译成解释程序的翻译才可被机器执行（机器语言）。,四、程序设计语言或工具（续）,15,算,法,与,数,据,结,构,一、算法（,algorithm,）,1、算法的基本概念,(,汉诺塔的例子,),算法,是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。,算法具有,有穷性,、,确定性,、,可行性,、,输入,和,输出,（拥有足够的情报）等个重要特性。,16,学,习,目,标,与,要,求,2、算法的基本要素,对数据对象的,运算,和,操作,：,算术运算、逻辑运算、关系运算、数据传输,算法中各操作之间的执行顺序；,描述算法的工具通常有传统流程图、,N-S,结构化流程,图、算法描述语言等；,一个算法一般可以用,顺序,、,选择,、,循环,三种基本结构,组合而成。,算法的,控制结构,：,17,算,法,与,数,据,结,构,3、算法设计的基本方法,列举法,归纳法,递推,递归（以简洁的形式设计和描述算法）,减半递推技术,回溯法,18,算,法,与,数,据,结,构,二、算法的复杂度,1、时间复杂度,依据算法编制的程序在计算机上运行时所消耗的时间,来度量。通常有,事后统计法,和,事前分析估算法,。,一个算法是由,控制结构,（顺序、分支和循环）和,原操,作,构成的，算法时间取决于两者的综合效果。,算法中基本操作重复执行次数,n,和算法执行时间同步,增长，称作算法的,时间复杂度,。,19,算,法,与,数,据,结,构,2、空间复杂度,一般是指执行这个算法所需要的,内存空间,。,一个算法所占用的存储空间包括,算法程序,所占的空间、,输入的初始数据,所占的存储空间以及,某种数据结构,所需,要的附加存储空间。,一个上机执行的程序除了需要存储空间来寄存本身所用,指令、常数、变量和输入数据外，也需要一些对数据进,行操作的工作单元和存储一些为实现计算所需信息的辅,助空间。,20,算,法,与,数,据,结,构,3、例题讲解,算法的时间复杂度是指(,C,),A、,执行算法程序所需要的时间,B、,算法程序的长度,C、,算法执行过程中所需要的基本运算次数,D、,算法程序中的指令条数,算法的基本特征是可行性、确定性、,【1】,和拥有足够,的情报。,【答案】,:,有穷性,算法的空间复杂度是指(,D,),A),算法程序的长度,B),算法程序中的指令条数,C),算法程序所占的存储空间,D),执行过程中所需要的存储空间,21,算,法,与,数,据,结,构,在计算机中，算法是指（,B,）,A),加工方法,B),解题方案的准确而完整的描述,C),排序方法,D),查询方法,算法分析的目的是(,D,),A),找出数据结构的合理性,B),找出算法中输入和输出之间的关系,C),分析算法的易懂性和可靠性,D),分析算法的效率以求改进,算法的工作量大小和实现算法所需的存储单元多少分别称,为算法的,【1】,。,【答案】,:,时间复杂度和空间复杂度,22,算,法,与,数,据,结,构,三、数据结构（,Data Structure,）,1、数据结构研究的主要内容,当今计算机应用的,特点,：,1、所处理的数据量大且具有一定的关系；,2、对其操作不再是单纯的数值计算，而更多地是需,要对其进行组织、管理和检索。,对数据的讨论不单单是数据本身，还要包括数据与数据之间的关系。,23,特点：,每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；,表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；,对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。,应用举例,1学籍档案管理,假设一个学籍档案管理系统应包含如下表所示的学生信息。,24,应用举例,2,家庭血缘关系图,表示家庭成员的辈分关系，,使用下图1-1所示的形式描述。,图 1-1,家庭血缘关系图,特点：,在求解过程中，所处理的数据之间具有层次关系，这是我们,所说的,树形结构,；,对它的操作有：建立树形结构，输出最结点内容等等。,25,应用举例,3,制定教学计划,在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：,26,这种数据可以用下面的图来表示：,26,课程先后关系的图形描形式：,c1,c9,c4,c2,c12,c10,c11,c5,c3,c6,c7,c8,图 1-2 计算机专业必修课程开设先后关系,27,27,1、数据的,逻辑结构,2、数据的,存储结构,3、数据的,运算,：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),数据结构的主要研究问题：,28,28,2、基本概念和术语,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,例：,整数,(1,2)、,实数,(1.1,1.2),字符串,(,Beijing)、,图形,、,声音,。,计算机管理图书问题：,在图书馆里有各种卡片：有按书名编排的、有按作,者编排的、有按分类编排。如何将查询图书的这些信息,存入计算机中既要考虑查询时间短，又要考虑节省空间。,最简单的办法之一是建立一张表，每一本书的信息在表,中占一行，如：,29,29,数据元素在计算机中的表示,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？,目的不同，,最佳,的存储方方法就不同,。,从大到小排列：,9,8,7,6,5,4,3,2,1,0,输出偶数：,0,2,4,6,8,1,3,5,7,9,对数据结构中的节点进行操作处理,（插入、删除、修改、查找、排序）,30,30,数据元素(,Data Element),数据元素是数据的基本单位，即数据集合中的个体。,有时一个数据元素可由若干,数据项,(,Data Item,),组成。数据项是数据的最小单位。,数据元素亦称,节点,或,记录,。,数据结构可描述为,Group=（D，R）,有限个数据元素的集合,有限个节点间关系的集合,31,31,数据结构可描述为,Group=（D，R）,例,1,：一年四季的数据结构可表示成,B=,（,D,，,R,）,D=,春，夏，秋，冬,R=,（春，夏），（夏，秋），（秋，冬）,例,2,：家庭成员数据结构可表示成,B=,（,D,，,R,）,D=,父亲，儿子，女儿,R=,（父亲，儿子），（父亲，女儿）,冬,春,夏,秋,父亲,儿子,女儿,32,数据结构也可用图形表示,一年四季的数据结构可表示成,家庭成员数据结构可表示成,冬,春,夏,秋,父亲,儿子,女儿,（概念：结点、前件、后件、根结点、叶子）,33,树形结构,全校学生档案管理的组织方式,计算机程序管理系统也是典型的,树形结构,。,34,H,G,F,E,C,D,B,A,树形结构 结点间具有分层次的连接关系,H,B,C,D,E,F,G,A,35,1,4,2,3,D=1,2,3,4,R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),2,1,3,D=1,2,3,R=(1,2),(2,3),(3,2),(1,3),图形结构节点间的连结是任意的,36,3、例题讲解,数据处理的最小单位是(,C,),A),数据,B),数据元素,C),数据项,D),数据结构,数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及(,A,),A),数据的存储结构,B),计算方法,C),数据映象,D),逻辑存储,数据结构包括数据的逻辑结构、数据的,【4】,以及对数据的操作运算。,【答案,】,物理结构（或存储结构）,37,线性结构与非线性结构：,线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。,如：一年四季，,26,个英文字母,非线性结构：线性以外的数据结构。,如：反映家庭成员间辈分关系的数据结构,算,法,与,数,据,结,构,38,4,、线性表,（,Linear List）,学 生 成 绩 表,(,按成绩排列,),86,胡孝臣,9861103,95,刘忠赏,9861107,100,张卓,9861109,成 绩,姓 名,学 号,线性表结点间是以线性关系联结：,线性表,：具有线性结构的有限序列。,数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。,39,线性表的定义:,线性表,是,n,个元素的有限序列，它们之间的关系可以排成,一个线性序列：,a1，a2，,ai,，an,其中,n,称作表的,长度,，当,n=0,时，称作,空表,。,线性表的特点：,1、线性表中所有元素的性质相同。,2、除第一个和最后一个数据元素之外，其它数据元素有且,仅有一个前驱和一个后继。第一个数据元素无前驱，最,后一个数据元素无后继。,3、数据元素在表中的位置只取决于它自身的序号。,在线性表上常用的运算有：,初始化、求长度、取元素、修改、前插、删除、检索、排序,40,40,线性表的,顺序存储结构,及其,插入,与,删除,操作,特点：,1、线性表中数据元素类型一致，只有数据域，存储空间,利用率高。,2、所有元素所占的存储空间是连续的。,3、各数据元素在存储空间中是按逻辑顺序依次存放的,（,a）,做插入、删除时需移动大量元素。,（,b）,空间估计不明时，按最大空间分配。,算,法,与,数,据,结,构,连续：如同一个学院的人连着住，一个学院的人也可分散住，这就不连续了，但他们之间的逻辑关系还在，即他们还是一个学院的同学,41,顺序存储,存储地址,存储内容,元素,n,.,元素,i,.,元素2,元素1,L,o,L,o,+,m,L,o,+(i-1),m,Lo+（n-1),m,Loc(,元素,i)=L,o,+（i-1),m,每个元素所占用,的存储单元个数,线性表的,顺序存储结构,：,首地址,起始地址,基地址,42,元素,a,1,元素,a,2,.,元素,a,i+1,.,0,1,i,线性表的顺序存储结构,可用,C,语言中的一维数组来描述.,第,i,个元素的,a,i,存储地址：,Loc(a,i,)=Loc(a,1,)+(i-1)*,m,V,V,Vi,Vm-1,int VM;,其中：,V,是数组的名字，,M,是数组大小，,假设数组中的元素是整型类型,算,法,与,数,据,结,构,43,插入运算,.,a,2,a,1,a,n,.,a,i+1,a,i,0,1,i-1,i,n-1,a,i-1,.,a,2,a,1,a,length,a,i+1,a,i,x,a,i-1,.,a,2,a,1,X,a,i,a,i+1,.,a,length,插入算法的分析,假设线性表中含有,n,个数据元素，在进行插入操作时，若,假定在,n+1,个位置上插入元素的可能性均等，则平均移动元素,的个数为：,44,44,在进行删除操作时，若假定删除每个元素的可能性均等，,则平均移动元素的个数为：,分析结论,顺序存储结构表示的线性表，在做插入或删除操作时，平,均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,删除算法的分析,45,45,线性表的例题讲解,顺序存储方法是把逻辑上相邻的结点存储在物理位置,【1】,的存储单元中。,【答案,】,相邻,长度为,n,的顺序存储线性表中，当在任何位置上插入一个元,素概率都相等时，插入一个元素所需移动元素的平均个数,为,【2】,。,【答案,】,n/2,线性表,L=(a1,a2,a3,ai,，an)，,下列说法正确的是（,D,）,A),每个元素都有一个直接前件和直接后件,B),线性表中至少要有一个元素,C),表中诸元素的排列顺序必须是由小到大或由大到小,D),除第一个元素和最后一个元素外，其余每个元素都有一,个且只有一个直接前件和直接后件,46,46,数据结构中，与所使用的计算机无关的是数据的(,C,),A),存储结构,B),物理结构,C),逻辑结构,D),物理和存储结构,下列叙述中，错误的是（,B,）,A),数据的存储结构与数据处理的效率密切相关,B),数据的存储结构与数据处理的效率无关,C),数据的存储结构在计算机中所占的空间不一定是连续的,D),一种数据的逻辑结构可以有多种存储结构,数据的存储结构是指（,B,）,A）,数据所占的存储空间,B）,数据的逻辑结构在计算机中的表示,C）,数据在计算机中的顺序存储方式,D）,存储在外存中的数据,47,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成(,C,),A),动态结构和静态结构,B),紧凑结构和非紧凑结构,C),线性结构和非线性结构,D),内部结构和外部结构,数据的逻辑结构有线性结构和,【2】,两大类。,非线性结构,当线性表采用顺序存储结构实现存储时，其主要特点是,【1】,。,【答案,】,逻辑结构中相邻的结点在存储结构中仍相邻。,48,48,5、堆栈和队列,堆栈和队列的定义,栈和队列,是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为,限定性的数据结构。,堆栈的定义,堆栈：,限定只能在表的一端进行插入和删除的特殊的线性表,此种,结构称为,后进先出。,设栈,s=（a,1,，a,2,，a,i,，a,n,）,其中,a,1,是,栈底,元素，,a,n,是,栈顶,元素。,栈顶（,top)：,允许插入和删除的一端；,约定,top,始终指向新数据元素将存放的位置。,栈底,（,bottom):,不允许插入和删除的一端。,a,1,a,2,.,a,n,进栈,出栈,栈顶,栈底,49,49,队列的定义,队列：,一种特殊的线性结构，限定只能在表的一端进行插入，,在表的另一端进行删除的线性表 。此种结构称为,先进,先出（,FIFO）,表,。,a,1,a,2,a,3,a,4,a,n-1,a,n,队 列 示 意 图,队头,队尾,队列的主要运算,（,1）设置一个空队列；,（2）插入一个新的队尾元素，称为进队；,（3）删除队头元素，称为出队；,（4）读取队头元素；,50,50,堆栈和队列的例题讲解,栈和队列的共同特点是（,C,）,A),都是先进先出,B),都是先进后出,C),只允许在端点处插入和删除元素,D),没有共同点,如果进栈序列为,e1,e2,e3,e4，,则可能的出栈序列是（,B,）,A)e3,e1,e4,e2,B)e4,e3,e2,e1,C)e3,e4,e1,e2 D),任意顺序,一些重要的程序语言(如,C,语言和,Pascal,语言)允许过程的递归调用。而实现递归调用中的存储分配通常用（,A,）,A),栈,B),堆,C),数组,D),链表,51,51,当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为,【2】,。,答案：,上溢,由两个栈共享一个存储空间的好处是（,B,）,A),减少存取时间，降低下溢发生的机率,B),节省存储空间，降低上溢发生的机率,C),减少存取时间，降低上溢发生的机率,D),节省存储空间，降低下溢发生的机率,下列关于栈的叙述中正确的是（,D,）,)在栈中只能插入数据,B）,在栈中只能删除数据,C）,栈是先进先出的线性表,D）,栈是后进先出的线性表,下列关于队列的叙述中正确的是（,C,）,）在队列中只能插入数据,B）,在队列中只能删除数据,C）,队列是先进先出的线性表,D）,队列是后进先出的线性表,52,两个栈共享只有两个栈都多时才溢出。不共享的话，两个栈只有一个栈多就溢出，,52,栈底至栈顶依次存放元素,A、B、C、D，,在第五个元素,E,入栈前，栈中元素可以出栈，则出栈序列可能是（,B,）,A)ABCED,B)DCBEA,C)DBCEA D)CDABE,下列数据结构中，按先进后出原则组织数据的是（,B,）,A),线性链表,B),栈,C),循环链表,D),顺序表,53,53,顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个,缺点,：,1.作插入或删除操作时，需移动大量元数。,2.长度变化较大时，需按最大空间分配。,3.表的容量难以扩充。,存储内容,元素,n,.,元素,i,.,元素2,元素1,54,54,6、线性链表,线性链表的基本概念：,线性表的链式存储结构称为,线性链表,。,为了适应线性表的链式存储结构，计,算机存储空间被划分为一个一个小块，每,一小块占若干字节，通常称这些小块为存,储结点。,算,法,与,数,据,结,构,55,将存储空间中的每一个存储结点分为两部：,一部分称为,数据域,，用于存储数据元素的值,；,另一部分称为,指针域,，用于存放下一个数据元素的存储序号,（即存储结点的地址），,也就是指向后件结点,.,线性链表中存储结点的结构如图2.20所示,56,56,1、比顺序存储结构的存储密度小,(每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。,2、逻辑上相邻的节点物理上不必相邻。,3、插入、删除灵活,(不必移动节点，只要改变节点中的指针)。,4,、查找结点时链式存储要比顺序存储慢。,链接存储结构特点：,算,法,与,数,据,结,构,57,指向线性表中第一个结点的指针,HEAD,称为,头指针,。,当,HEAD=NULL,（或0）时称为,空表,。,对于线性链表，可以从头指针开始，沿着各,个结点的指针扫描到链表中的所有结点。,线性链表的逻辑结构图所示,58,59,59,60,线性链表的基本运算：,线性链表的运算主要有以下几个：,在线性链表中包含指定元素的结点之前,插入,一个新元素。,在线性链表中,删除,包含指定元素的结点。,将两个线性链表按要求,合并,成一个线性,链表。,61,线性链表的,插入,运算：,线性链表的插入,是指在链式存储结构下,的线性表中插入一个新元素。,为了要在线性链表中插入一个新元素，,首先要给该元素分配一个新结点，然后将存,放新元素值的结点链接到线性链表中指定的,位置。,算,法,与,数,据,结,构,62,63,63,线性链表的删除,指在链式存储结构下的,线性表中删除包含指定元素的结点。,为了在线性链表中删除包含指定元素的,结点，首先要在线性链表中找到这个结点，,然后将要删除结点放回到可利用栈。,线性链表的,删除,运算：,算,法,与,数,据,结,构,64,65,65,循环链表的结构与前面所讨论的线性链表相比，具有以下,两个特点：,循环链表的头指针指向表头结点。,在循环链表中，所有结点的指针构成了一个环状链。,图2.29是循环链表的示意图。,循环链表：,66,66,在实际应用中，循环链表与线性单链表相,比主要有以下两个方面的优点：,在循环链表中，只要指出表中任何一个结点,的位置，就可以从它出发访问到表中其他所,有的结点。,由于在循环链表中设置了一个表头结点，因,此，在任何情况下，循环链表中至少有一个,结点存在，,从而使空表与非空表的运算统一,。,算,法,与,数,据,结,构,67,链表不具有的特点是（,B,）,A),不必事先估计存储空间,B),可随机访问任一元素,C),插入删除不需要移动元素,D),所需空间与线性表长度成正比,数据结构分为逻辑结构与存储结构，线性链表属于,【1】,。,【答案,】,存储结构,线性表的顺序存储结构和线性表的链式存储结构分别是,(,B,),A),顺序存取的存储结构、顺序存取的存储结构,B),顺序存取的存储结构、随机存取的存储结构,C),随机存取的存储结构、随机存取的存储结构,D),任意存取的存储结构、任意存取的存储结构,线性链表的例题讲解,68,68,栈通常采用的两种存储结构是（,A,）,A),顺序存储结构和链表存储结构,B),散列方式和索引方式,C),链表存储结构和数组,D),线性存储结构和非线性存储结构,69,7、树与二叉树：,树的基本概念：,前面我们讨论的线性表，栈、队列和数,组等都是,线性结构,。而,树,是一种,非线性数据,结构,，它的每一个结点，都可以有不止一个,直接后继，除根外的所有结点，都有且只有,一个直接前趋。,这些数据结点按分支关系组,织起来，清晰地反映了数据元素之间的层次,关系。,70,算,法,与,数,据,结,构,现实世界中，能用树的结构表示的例子,：,学校的行政关系、书的层次结构、人类的家族血缘关系等。,71,72,72,73,73,二叉树,(,binary tree),是一种很有用的非线,性结构。,二叉树具有以下两个特点：,（1）非空二叉树只有一个根结点；,（2）每一个结点最多有两棵子树，且分别,称为该结点的左子树与右子树。,二叉树（,Binary Tree）：,因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树,的讨论。,74,74,75,75,性质1,：在任意一棵二叉树中，度为0的结点,（即叶子结点）总是比度为2的结点多,一个。,二叉树的性质：,特别要注意：,二叉树是,树的特殊情况。,a,a,b,b,两棵不同的二叉树,76,例子1,：某二叉树中度为2的结点有18个，则,该二叉树中有,19,个叶子结点。,76,性质2,：二叉树的第,i,层上,至多,有2,i-1,（i,1）,个结点,二叉树的性质：,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,第三层上(,i=3)，,有2,3-1,=4个节点。,第四层上(,i=4)，,有2,4-1,=8个节点。,77,二叉树的性质：,性质3,：,深度为,h,的二叉树中,至多,含有2,h,-1,个结点,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,此树的深度,h=4，,共有2,4,-1=15个节点。,78,满二叉树与完全二叉树,满二叉树,是指除最后一层外，每一层上的所,有结点都有两个子结点。,完全二叉树,是指这样的二叉树：除最后一层,外，每一层上的结点数均达到最大值；在最后一,层上只缺少右边的若干结点。,注意：,满二叉树是完全二叉树，完全二叉树,不一定是满二叉树。,算,法,与,数,据,结,构,79,满二叉树的特点：,每一层上都含有最大结点数。,80,80,完全二叉树的特点：,除最后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的若干位置,81,81,对于,完全二叉树,而言,如果它的结点个数为,偶,数，则该二叉树中：,叶子结点的个数=非叶子结点的个数,如果它的结点个数为,奇,数，则该二叉树中：,叶子结点的个数=非叶子结点的个数+1,（即叶子结点数比非叶子结点数,多一个,）,规律总结：,算,法,与,数,据,结,构,82,例题讲解,1、设一棵完全二叉树共有700个结点，则,在该二叉树中有,350,个叶子结点。,2、在深度为5的满二叉树中，,叶子,结点的,个数为（,C,）,(,即第,5,层的叶子个数,),A)32 B)31,C)16,D)15,算,法,与,数,据,结,构,83,二叉树的遍历,二叉树的遍历,是指不重复地访问二叉树中的,所有结点。,二叉树的遍历可以分为三种：,前序,遍历、,中,序,遍历、,后序,遍历。,设访问根结点记作,V；,遍历根的左子树记作,L；,遍历根的右子树记作,R；,前序：,VLR（,即,根,左右）,中序：,LVR（,即左,根,右）,后序：,LRV（,即左右,根,）,84,84,85,85,1、设一棵二叉树的中序遍历结果为,DBEAFC,前序遍历结果为,ABDECF，,则后序遍历结,果为：,DEBFCA,例题讲解,2、已知一棵二叉树前序遍历和中序遍历分别,为,ABDEGCFH,和,DBGEACHF，,则该二叉树,的后序遍历为（,B,）,A)GEDHFBCA,B)DGEBHFCA,C)ABCDEFGH D)ACBFEDHG,前序：,A,BDECF,（前序：根最先访问，,根,必在第一个）,中序：,DBE,A,FC,（由上可知中序,根,所在，划分出左右子树）,前序：,A,BDE CF,中序：,DBE,A,FC,前序：,A,B,DE,C,F,中序：,D,B,E,A,F,C,86,具有3个结点的二叉树有（,D,）,A)2,种形态,B)4,种形态,C)7,种形态,D)5,种形态,设有下列二叉树：,对此二叉树前序遍历的结果为（,B,）,A)ZBTTCPXA,B)ATBZXCTP,C)ZBTACTXP D)ATBZXCPT,87,87,8、查找和排序：,查找又称为,检索,查找算法的评价主要考虑算法的时间复杂,性，既可以采用数量级的形式表示，也可以采,用平均检索（查找）长度，即在查找成功情况,下的平均比较次数来表示。,查找可分为,顺序查找,和,二分法查找,两种。,算,法,与,数,据,结,构,88,（,a）,顺序查找：,顺序查找,又称,线性查找,。它是一种最简单、,最基本的查找方法。基本思想是：从表中第一,条记录开始，逐个进行记录的关键字和给定值,的比较。若某个记录的关键字和给定值相等，,则查找成功；否则，若直至最后一个记录，其,关键字和给定值都不相等，则表明表中没有所,查记录，查找不成功。,算,法,与,数,据,结,构,89,二分查找,又称,折半查找,。作为二分查找对,象的表必须是顺序存储的有序表，即各记录的,次序是按其关键字的大小顺序（以下假定按从,小到大的顺序）排列的表。,（,b）,二分查找：,算,法,与,数,据,结,构,90,二分查找的,具体做法,是:先取表,中间,位置的记录关,键字与给定值比较。若相等,则查找成功；否则,若给,定值比该记录的关键字小，则给定值必在表的前半部分。,在这前半部分中再取中间位置记录的关键字进行比较，,就又可以排除这部分的一半。依次反复进行，直到找到,给定值或找完全表而找不到为止。,对于,n,较大时，平均查找长度可以近似地表示为,算,法,与,数,据,结,构,91,排序,是将一组杂乱无章的数据按一定的规,律顺次排列起来。,通常数据对象有多个属性域，即由多个数,据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域称为,关键字（,key）,。,排序的时间开销是衡量算法好坏的最重要,的标志。对于长度为,n,的有序线性表，查找时最坏情况只需比较,n,次。,排序（,sort）,92,（,a）,交换类排序：,交换类排序法：,冒泡排序法,：需要比较的次数为,n(n-1)/2,快速排序法,：是对冒泡排序的改进，是目,前内部排序中速度最快的一种。,算,法,与,数,据,结,构,93,（,b）,插入类排序：,插入类排序的,基本方法,是：每步将一个待,排序的对象，按其关键字大小，插入到前面已,经排好序的一组对象的适当位置上，直到对象,全部插入为止,。,简单插入排序法：,最坏情况需要,n(n-1)/2,次比较；,希尔排序法：,最坏情况需要,O（n）,次比较。,算,法,与,数,据,结,构,94,（,c）,选择类排序：,选择类排序的,思想,是：每一趟（例如，第,i,趟，,i=0，1，n2）,在后面,ni,个待排序对象中选,出关键字最小（升序，若为降序，选出最大关键,字）的对象，作为有序对象序列的第,i,个对象。待,到第,n2,趟作完，待排序对象只剩下1个，不用再,选了，结束排序。,简单选择排序法,，最坏情况需要,n(n-1)/2,次比较；,堆排序法,，最坏情况需要,O（nlog,2,n）,次比较。,95,程,序,设,计,基,础,（一）程序设计方法与风格,如何形成良好的程序设计风格：,1、源程序内部文档化；,选择标识符的名字,注释（,序言性,和,功能性,注释）,程序的视觉组织,位于源程序,模块内部,一般位于模块的首部，用于说明模块的相关信息,96,显式地说明一切变量,数据说明的次序应该规范化,便于查找变量（按顺序排列）,对复杂数据结构应注释说明,2、数据说明,程,序,设,计,基,础,3、语句的结构,每条语句简单明了,尽量不用或少用,GOTO,语句,尽量只采用3种基本控制结构编程,97,4、输入和输出,对所有输入数据进行校验和合理性检查,输入输出格式保持一致,设计良好的输出报表,输入方式,应力求简单，尽量避免给用户带来不必要的麻烦；,交互式输入数据时应有必要的提示信息;程序应对输入数据的,合法性进行检查;若用户输入某些数据后可能产生严重后果,应,给用户输出必要的提示并要求用户确认；应根据系统的特点和,用户的习惯设计出令用户满意的输入方式。,输出数据的格式,应清晰，美观；输出数据时要加上必要的,提示信息。,98,98,结构化程序设计的,主要思想,是功能分解并,逐步求精。当一些任务十分复杂不易描述时，,可以将它拆分为一系列较小的功能部件，直到,这些子任务小到易于理解和实现的程度。,结构化程序的,特点,：程序结构仅由,顺序,、,选择,和,循环,3种结构复合而成。,程,序,设,计,基,础,（二）结构化程序设计,99,（三）面向对象的程序设计方法,面向对象的程序设计（,Object-Oriented,Programming，OOP,）,是一种把面向对象的,思想应用于软件开发过程中，指导开发活动,的系统方法，简称,OO,方法，它是建立在对,象概念（对象、类和继承）基础上的方法。,程,序,设,计,基,础,100,面向对象程序设计方法的优点：,（1）从认知学的角度来看，面向对象方法符,合人们对客观世界的认识规律。,（2）面向对象方