《公共基础知识》PPT课件.ppt

第1章 数据与算法 第2章 程序设计基础 第3章 软件工程基础 第4章 数据库设计基础,1,公共基础知识,全国计算机等级考试,分值：10分，题型：选择题,1.1 算法 1.2 数据结构的基本概念 1.3 线性表及其顺序存储结构 1.4 栈和队列 1.5 线性链表 1.6 树与二叉树 1.7 查找技术 1.8 排序技术,2,第1章 数据结构与算法,重点掌握：概念和基本知识点； 难点内容：二叉树的计算和遍历，常用算法的时间复杂度等,算法是指解题方案的准确而完整的描述。 算法是一组明确的可执行步骤的有序集合。算法的概念要求步骤集是有序的，这就要求算法中的各个步骤必须拥有定义完好的顺序执行结构。 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 比如：做一道菜的方法，解一道数学题的方法，谱一首歌曲等，都可称为算法。,3,1.1 算法,1.1.1 算法的基本概念,1.算法的特征： (1) 可行性； (2) 确定性，算法的每一步骤必须有确定的含义，不会产生二义性； (3) 有穷性，算法必须在有限的时间完成，步骤是有限的； (4) 有足够的情报（数据的输入和输出）。 由此得到： 算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。,4,算法的基本要素： 对数据对象的运算和操作；算法的控件结构 (1)对数据的运算和操作 一般的计算机系统中，基本的运算和操作有： 算术运算、逻辑运算、关系运算、数据传输 (2)算法的控制结构 算法中的操作执行的顺序 三种基础结构：顺序结构、选择结构、循环结构,5,2. 算法基本要素,计算机解题的过程实际上是在实施某种算法，称为计算机算法，常用的计算机算法有： （1）列举法:如，求10000以内所有素数的个数。 （2）归纳法：从特殊 一般。比如在买水果的时候我们往往先尝一尝，如果都很甜，就归纳出所要买的水果都很甜的。 （3）递推法：如求fibonacci(斐波那契)数列。 （4）递归法：如汉诺塔问题。 （5）减半递推技术： （6）回溯法 ：,6,3. 算法设计的基本方法,评价一个算法一般从正确性、运行时间、占用空间和简单性4个方面进行。 算法的运行时间通常用时间复杂度表示； 算法占用的空间用空间复杂度表示。 1.算法的时间复杂度（渐近时间复杂度）: 为了便于比较同一问题的不同算法，通常是从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 记作：T(n)=O(f(n) 表示：随问题规模N的增大，算法执行时间的增长率真和f(n)的增长率相同。,7,1.1.2 算法复杂度,在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入，可以用以下两种方法来分析算法的工作量： （1）平均性态:A(n); （2）最坏情况复杂性：W(n);,8,是对一个算法在运行过程中所需要的内存空间，它是问题规模n的函数 。 记作S(n)=O(f(n) 其n为问题的规模大小。 一个算法在计算机存储器上所占用的存储空间，包括存储算法程序本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在执行过程中临时占用的存储空间这三个方面。,9,2.空间复杂度,数据结构是指： 按照某种逻辑关系组织起来的一批数据，按一定的存储方式把它存储在计算机的存储器中，并在这些数据上定义了一个运算的集合。即相互有关联的数据元素的集合。 数据元素：现实世界中客观存在的一切个体都可以是数据元素。如春、夏、秋、冬，字母表字母等。 在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。,10,1.2 数据结构的基本概念,1.2.1什么是数据结构,数据结构研究的内容： （1）数据的逻辑结构:数据集合中各数据元素之间所固有的逻辑关系； （2）数据的存储结构(物理结构)：各数据元素在计算机中的存储关系； （3）对各种数据结构进行的运算。 研究数据结构的目的： 提高数据处理的效率：一是提高数据处理的速度；二是尽量节省处理过程中所占用的计算机存储空间。,1.数据的逻辑结构 数据结构是带有结构的数据元素的集合，结构实际上就是指数据元素之间的前后件关系，即数据元素的逻辑关系，而与数据元素在计算机中的存储位置无关。 一个数据结构包含以下两个方面的信息： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 一个数据结构的逻辑关系可表示成： B=(D,R) 其中：B表示数据结构，D是数据元素的有限集，R是D上关系的有限集。 如：一年四季的数据结构。 表示为：Season=(D,R) D=春，夏，秋，冬 R=(春，夏),(夏，秋),(秋，冬),12,13,1.数据的存储结构 数据的存储结构是数据的逻辑结构在计算机存储空间中的存放形式。 数据的存储结构也称为数据的物理结构。 在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系。 注意：数据的逻辑关系与其存储结构不同。（如学号与入座次序） 常用的存储结构有：顺序、链接、索引等。,14,(数据结构的表示方法：二元组、图形表示) 1.2.2数据结构的图形表示 方框：结点 有向线段：关系 基本概念： 什么是根结点，终端结点，内部结点？,15,1.2.3 线性结构与非线性结构 根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。 如果一个非空的数据结构满足以下两个条件： 1、有且只有一个根结点； 2、每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构，又称为线性表。,线性结构,非线性结构,16,1.3 线性表及其顺序存储结构,1.3.1线性表的基本概念 （略，P15） 1.3.2线性表的顺序存储结构 在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。 线性表的顺序存储结构具有以下两个基本特点： 1、线性表中所有元素所占的存储空间是连续的； 2、线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。,1.4.1 栈及其基本运算 1. 什么是栈? 栈一种特殊的线性表，其插入与删除运算只在线性表的一端进行,后进先出线性表，简称LIFO，栈具有记忆作用。),17,1.4 栈和队列,2. 栈的顺序存储及其运算 与一般的线性表一样，用一维数组S(1：m)作为栈的顺序存储空间，其中m为栈的最大容量。 通常，栈底指针指向栈空间的低地址一端，在栈的顺序存储空间s(1：m)中，s(bottom)通常为栈底元素，s(top)为栈顶元素。 top=0表示栈空， top=m表示栈满。 栈的基本运算有三种：入栈、退栈、读栈顶元素。 注意： 什么是“上溢”？什么是“下溢”？,18,迷宫求解是数据结构中一个经典的程序设计题，一般情况下采用”穷举求解”的方法，即从迷宫的入口出发，沿着某一方向前进，若能走通则继续前进，若不通需原路退回后改变方向继续前进，直到找到出口为止，为了保证在任何位置都可以原路退回，自然使用“栈”就是很自然的了。,19,栈的应用：迷宫求解，从入口到出口所有路径。,1.4.2. 队列及其运算 1. 什么是队列 队列是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端为队尾，通常用一个称为尾指针（Rear)的指针指向队尾元素；允许删除的一端为排头，通常用一个排头指针(Front)指向排头元素的前一个位置。 一种运算受限的线性表，简称FIFO,如排队) 队列的先进先出示意图,20,2. 循环队列及其运算 在实际应用中，队列的顺序存储结构一般采用循环队列的形式 （P22,略）,21,22,队列应用：如操作系统中的作业队列 队列实现：,23,1.5 线性链表,1.5.1 线性链表的基本概念 1. 线性链表 线性表的链式存储结构称为线性链表。 为适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占有若干个字节，通常称为存储结点。 为存储线性表中的每一个元素，存储空间中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一入数据元素的存储序号（地址），即指向后件结点，称为指针域。,展览数据 后件地址,数据 域 指针域,“存储结点”图,24,在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点。线性链表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空，用NULL或0表示，表示链表终止。 注意： HEAD称为头指针，当HEAD=NULL（或0）时称为空表，如图所示：,25,31,头指针H,26,结点：数据元素的存储映象，包括两个域，即数据域，指针域。 数据域：存储数据元素信息。 指针域：存储的信息为指针或链,27,1.5.2 线性链表的基本运算 1. 在线性链表中查找指定元素 2. 线性链表的插入 3. 线性链表的删除,28,1.5.3 循环链表及其基本运算 1. 什么是循环链表？ 2. 循环链表有什么特点？ 3. 循环链表的好处是什么？,树型结构是一类重要的非线性数据结构。所有数据元素之间的关系具有明显的层次性。 树(tree)是n(n0)个结点的有限集，在任意一棵树中：(1)有且仅有一个特定的称为根(Root)的结点；(2)当n1时，其余的结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(Sub Tree) 树在计算机中通常用多重链表来表示。,29,1.6 树与二叉树,1.6.1 树的基本概念,30,A,B,C,D,E,F,G,H,I,J,M,L,K,树的示例,(1)树的结点包含一个数据元素及若干个指向其子树的分支。 (2)结点的度：指结点拥有的子树的数。 (3)叶子或终端结点：度为0的结点。 (4)非终端结点或分支结点：度不为0的结点。 (5)内部结点：除根结点之外的结点。 (6)树的度：指树内各结点的度的最大值。 (7)父结点：每个结点的前件。根结点：没有前件的结点。子结点：每个结点的后件。 (8)兄弟：同一个双亲的孩子之间互为兄弟。 (9)结点的层次从根开始定义起，根为第一层，根的孩子为第二层。 (10)堂兄弟：其双亲在同一层的结点互为堂兄弟。 (11)树的深度（高度）:树中结点的最大层次 (12)如果将树中结点的各子树看成从左到右是有次序的，则该树为有序树。 (13)森林：是m(m0)棵互不相交的树的集合。,31,相关术语,二叉树存储的示意图,32,1.6.2二叉树及其基本性质 1. 什么是二叉树 二叉树是另外一种树型结构，它的特点是:(1)非空二叉树只有一个根结点；(2)每个结点至多只有二棵子树，分别称为二叉树的左子树和右子树，其次序不能任意颠倒。,(1)在二叉树的第k层上至多有2(k-1)个结点(k1)。 (2)深度为m的二叉树至多有2m-1个结点(m1)。 (3)对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 (4)具有n个结点的二叉树，其深度至少为 log2n +1。,33,2.二叉树的性质,34,（1）满二叉树： 一棵深度为k，且有2k-1个结点的二叉树称为满二叉树。 （2）完全二叉树： 如果从根结点起，对二叉树的结点自上而下，自左至右用自然数进行连续编号，则深度为m的，有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树 。 若设二叉树的深度为h，除第 h 层外，其它各层 (1h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。 如图所示：,3.满二叉树与完全二叉树质,35,1,2,3,4,5,6,7,8,10,11,9,12,14,15,13,满二叉树,36,1,2,3,4,5,6,7,8,10,11,9,12,完全二叉树,37,38,1.6.3 二叉树的存储结构 在计算机中，二叉树通常采用链式存储结构。也称为二叉链表。 1.6.4 二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。 根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。 1、前序遍历（DLR）：先根，再左，后右 2、中序遍历（LDR）：先左，再根，后右 3、后序遍历（LRD）：先左，再右，后根,39,例：设一棵完全二叉树共有700个结点，则该二叉树中有_个叶子结点？ 假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0n21，则n= n0n1n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n11，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0（n1）/2或n0n/2，合并成一个公式：n0?（n1）/2 ?，就可根据完全二叉树的结点总数计算出叶子结点数。,40,前序遍历：F，C，A，D，B，E，G，H，P 中序遍历：A，C，B，D，F，E，H，G，P 后序遍历：A，B，D，C，H，P，G，E，F,41,题目：已知先序遍历，中序遍历 建立二叉树，然后求后序遍历。 先序：a b d e i j c f g 中序：d b i e j a f c g 后序：?d i j e b f g c a 解法：先序中的首元素a 必为该二叉树的根结点，在中序序列里a之前的元素一定是a的左子树部分，a之后的元素一定为a的右子树部分。 所以，可以看作，先序： root | 左子树 | 右子树 中序： 左子树 | root | 右子树,42,1.7 查找技术,1.7.1 顺序查找 顺序查找又称顺序搜索，一般是指在线性表中查找指定的元素。 顺序查找的基本方法：P39（略）； 顺序查找次数：平均情况下约为