二级公共基础知识,2,二级公共基础知识,第一章 算法与数据结构 第二章 程序设计基础 第三章 软件工程基础 第四章 数据库设计基础,3,第一章 算法与数据结构,本章要求 算法的基本概念、算法复杂度的概念和意义（时间复杂度与空间复杂度）。 数据结构的定义、数据的逻辑结构与存储结构、数据结构的图形表示、线性结构与非线性结构的概念。 线性表的定义、线性表的顺序存储结构及其插入与删除运算。 栈和队列的定义、栈和队列的顺序存储结构及其基本运算。 线性单链表、双向链表与循环链表的结构及其基本运算。 树的基本概念，二叉树的定义及其存储结构，二叉树的前序、中序和后序遍历。 顺序查找与二分法查找算法、基本排序算法（交换类排序、选择类排序与插入类）。,4,第一章 算法与数据结构,一、算法 二、数据结构 三、线性表 四、栈 五、队列 六、线性链表 七、树与二叉树 八、查找技术 九、排序技术,5,一、算法 1.算法的基本概念 算法是指为了解决某类问题而规定的一个有限长度的操作（指令）序列。 （1）算法的特点：可行性、确定性、有穷性、拥有足够的情报。 （2）算法的两个基本要素：一是对数据对象的运算和操作，具体包括算术运算、逻辑运算、关系运算和数据传输等；二是算法的控制结构，具体包括顺序结构、选择结构和循环结构。,6,2.算法的复杂度 算法的复杂度(代价)是衡量算法好坏的量度，具体可分为两种:时间复杂度和空间复杂度。 （1）时间复杂度是指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数。 通常记作：常见的时间复杂度有： （2）空间复杂度是指执行该算法所需要的内存空间。 具体包括（1）算法程序所占的空间；（2）输入的初始数据所占的存储空间；（3）算法执行过程中的额外空间,7,二、数据结构 1.数据结构的基本概念 数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。在此概念中:（1）数据是指所有能输入到计算机中并被计算机程序处理的符号的总称; （2）数据元素是指数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理;（3）一个数据元素可以由若干个数据项组成,数据项是数据的最小单位。,8,数据结构有三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。 2.数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系，从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 数据的逻辑结构的表示方法表示数据的逻辑结构时必须表示清楚两个关键点，一个是数据元素的集合D，另一个是数据元素之间的前后关系R。 表示数据结构的方法有两种：二元关系表和图形表示方法。,9,A.二元关系表示方法：一个数据结构可以表示为B=（D、R），其中R用二元组来表示(a、b)。 a表示前件， b表示后件。例如，一年四季的数据结构可以表示成:B=（D、R）D=春，夏，秋，冬R=（春，夏），（夏，秋），（秋，冬） B.在图形表示方法中，用中间标有元素值的方框来表示数据元素，称为数据结点，简称为结点；用一条有向线段从前件结点指向后件结点（注意：有时可以省略箭头）来表示元素之间的前后关系。,10,例如，同样是一年四季的数据结构，若用图形方法表示则如图所示。 数据的逻辑结构一般分为两种:线性结构和非线性结构。 线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。如：一年四季。非线性结构：线性以外的数据结构。如：反映家庭成员间辈分关系的数据结构。,11,A.线性结构 线性表例:英文字母表 (A , B , C , ，X ,Y , Z)例:学生成绩表 栈后进先出 队列先进先出,12,B.非线性结构 树形结构例:全校学生档案管理的组织方式 例:计算机文件管理系统也是典型的树形结构,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),14,3.数据的存储结构 数据的存储结构(又称物理结构):是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。 数据的存储结构有4种：顺序存储方式、链式存储方式、索引存储方式和散列存储方式。需要注意的是，对于同一个逻辑结构来说，采用不同的存储结构时，其数据处理的效率是不同的。 4.数据的运算：检索、排序、插入、删除、修改等。,15,三、线性表 线性表是最简单的、最常用的一种线性结构。 1.线性表的定义:线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2， ，ai， ，an ，其中n称作表的长度，当n=0时，称作空表。 线性表（非空线性表）必须同时满足以下3个条件： （1）有且只有一个根结点a1，它无前件。（2）有且只有一个终端结点an，它无后件。（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。,16,如下图所示的数据结构就是线性表 注：线性表的概念是从逻辑结构的角度说的，所以，判断是否为线性表时并不考虑其存储结构，线性表可以用四种不同的存储结构来表示。 2.线性表的顺序存储结构 特点：（1）线性表中所有元素所占的存储空间是连续的;（2）线性表中各数据元素在存储空间中的存放顺序是按逻辑顺序依次存放的。,17,例：正确表示线性表(A1，A2，A3，A4)的顺序结构是( ) A) B) C)分析：选C，选项C中线性表各元素的存储空间是连续的，而且元素的存储顺序与逻辑顺序一致。选项A中各元素的物理顺序与逻辑顺序不同。选项B中各元素所占的存储空间并不连续。,18,顺序存储,存储地址,存储内容,an,.,ai,.,a2,a1,ADR(a1),ADR(a1)+k,ADR(a1)+(i-1)k,ADR(a1)+(n-1)k,ADR(ai)=ADR(a1)+（i-1)k,每个元素所占用 的存储单元个数,首地址 起始地址 基地址,在线性表的顺序存储结构中可以计算各数据元素（数据起点）的起始地址。,19,顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点:(1)随机存取。(2)作插入或删除操作时，需移动大量元素。(3)长度变化较大时，需按最大空间分配。(4)表的容量难以扩充。 通常定义一个一维数组来表示线性表的顺序存储空间。,20,3.线性表的顺序存储结构的插入运算设顺序表的结构如图所示，其插入运算的步骤如下：(1)判断是否上溢:首先判断为线性表开辟的存储空间是否已满，如果已满则不能插入，如果未满则继续做第二步。(2)空出第i个位置:从最后一个元素开始到插入的位置上的元素，将其中的每个元素均依次往后移动一位。(3)插入:把新元素放入所插入的位置。,21,插入位置与需要移动的元素个数之间存在着一定的关系。当线性表很大时，其插入运算的效率是比较低的。具体情况如下所述：(1)最好的情况:如果插入位置在线性表的末尾，即在第n个元素之后插入新元素，则不需要移动线性表中的其他任何元素。(2)最坏的情况:如果插入位置在线性表的第1个元素之前，则需要移动表中的所有元素。(3)如果插入位置在第i（1in）个元素之前，则原来的第i个元素之后(包括第i个元素)的所有元素都必须移动。(4)在平均情况下，要在线性表中插入一个新元素，需要移动线性表中一半的元素。（n/2个）,22,3.线性表的顺序存储结构的删除运算具体运算步骤如下:如果删除第i（1in）个元素，从第i+1个元素开始直到最后一个元素，将其中的每个元素均依次往前移动一位。此时，线性表的长度变成了n-1。如下图：,23,在线性表的顺序存储结构的删除运算中，删除一个数据元素之后，应移动原来的元素，而且删除位置与需要移动的元素个数之间存在着一定的关系。所以当线性表很大时，其删除运算的效率也是比较低的。具体情况如下所述：(1)最好的情况:如果删除位置在线性表的末尾，即删除第n个元素，则不需要移动线性表中的其他任何元素。(2)最坏的情况:如果删除线性表的第1个元素，则需要移动表中的所有元素。 (3)在平均情况下，要删除线性表中的一个元素，需要移动表中的(n-1)/2个元素。,24,四、栈 1.栈的定义：栈是一种特殊的线性表，特殊在其数据操作上，即限定在一端进行插入与删除的线性表。在栈中，允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。 往栈中插入一个元素叫入栈运算（压栈） 从栈中删除一个元素称为退栈运算（弹栈） 栈的数据操作原则是先进后出FILO（FirstIn Last Out）或后进先出LIFO。栈具有一定的记忆作用。,25,2.栈的存储结构在程序设计语言中，与普通线性表一样，用一维数组作为栈S(l:m)的顺序存储结构，其中m为栈的最大容量。通常用指针top来指示栈顶的位置，用指针bottom指向栈底。当top=0时为空栈，当top等于数组的最大下标值时则栈满。 3.栈的基本运算 有三种:入栈、退栈和读栈顶元素。 (1)入栈运算的步骤 ：首先，判断栈是否为满，如果满则不能入栈(方法top=n)；其次，将栈顶指针进一(即 top加1)；,26,最后，将新元素放入栈顶指针指向的位置中。值得注意的是，在入栈运算中应避免上溢错误的出现。上溢错误是指当栈顶指针己经指向存储空间的最后一个位置时，说明栈的空间己满，不能再进行入栈操作，这种情况称为栈“上溢”错误。 (2)退栈运算的步骤：首先，判断栈是否为空(方法top=0);其次，将栈顶元素赋值给一个指定的变量;最后，栈顶指针退一(即top减1)。值得注意的是，退栈运算中应避免下溢错误的出现。,27,(3) 读栈顶元素的步骤：读栈顶元素是指将栈顶元素赋值给一个指定的变量。读枝顶元素过程中应注意的问题有:第一，读栈顶元素不是删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变，这是与入栈运算的区别;第二，当栈顶指针为0时，说明栈为空，读不到栈顶元素。,28,五、队列 1.队列的基本概念： 队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种特殊的线性表。允许插入的一端叫队尾(尾指针， Rear，指向队尾元素)，允许删除的一端叫队头(头指针， Front，指向队头元素的前一个位置)。队列的数据操作方法:先进先出FIFO/LILO。,29,队列的一个重要应用是在操作系统中的管理用户程序上。即在操作系统中，用队列来组织管理用户程序的排队执行，其原则是:(1)初始时该队列为空; (2)当有用户程序到来时，将该用户程序加入到队列的末尾进行等待;(3)当计算机系统执行完当前的用户程序后，就从队列头部取出一个用户程序执行。 与栈一样，程序设计中用一维数组作为队列的顺序存储空间。,30,2.循环队列在实际应用中，队列的顺序存储结构一般采用循环队列的形式。 原理:循环队列是指当队列存储空间的最后一个位置己被使用而仍要进行入队运算，这时只要存储空间的第一个位置空闲，便可以将元素加入到这个位置，即将存储空间的第一个位置作为队尾，如图所示。,31,在循环队列中，从头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。 循环队列的初始状态为空，即：rear=front=m，如图所示。 循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就进一。当队尾指针rear=m+1时，则置rear=1；每进行一次退队运算，排头指针就进一。当排头指针front=m+1时，则置front=1,32,例：图（a）是一个容量为8的循环队列存储空间，且其中已有6个元素。图（b）是在图（a）的循环队列中又加入了两个元素后的状态。图（c）是在图（b）的循环队列中退出了1个元素后的状态。,（a）具有6个元素的循环队列 （b）加入X、Y后的循环队列 （c）退出一个元素后的循