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

二级公共基础知识，二级公共基础知识，第一章算法和数据结构第二章程序设计基础第三章软件工程基础第四章数据库设计基础，三，第一章算法和数据结构，本章包括算法的基本概念，算法复杂度的概念和意义(时间复杂度数据结构的定义、数据的逻辑结构和存储结构、数据结构的图形显示、线性结构和非线性结构的概念。 线性表的定义，线性表的顺序记忆结构及其插入和删除运算。 堆栈和队列的定义，堆栈和队列的顺序存储结构及其基本运算。 线性单链表，双向链表和循环链表的结构及其基本运算。 追溯树的基本概念、二叉树的定义及其记忆结构、二叉树的序言、中序和后序。 顺序搜索和二分法搜索算法、基本排序算法(交换类排序、选择类排序、插入类)。 4、第一章算法和数据结构、一、算法二、数据结构三、线性表四、堆栈五、矩阵六、线性链表七、树和二叉树八、检索技术九、排序技术、五、一、算法一.算法的基本概念算法为了解决某种问题(1)算法的特征：具有可行性、确定性、贫困性、充分的信息。 (2)算法的两个基本要素：一个是对数据对象的运算和操作，具体地说，包括算术运算、逻辑运算、关系运算和数据传输等，第二个是算法的控制结构，具体地说，包括序列结构、选择结构、循环结构。 6，2 .算法复杂度算法的复杂度(成本)是测量算法好坏的尺度，具体分为两种：小时复杂度和空间复杂度。 (1)时间复杂度是指算法的执行所需的计算工作量，即算法的执行所需的基本计算次数。 通常，典型地，时间复杂度描述为(2)空间复杂度是执行该算法所需的存储器空间。 具体地说，(1)包含算法程序占据的空间(2)输入的初始数据占据的存储区域(3)算法执行过程中的多馀的空间，7，2，数据结构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 )例：学生成绩表栏后方矩阵3354前方出，12，b .非线性构造例：全校学生文件管理的组织方式例：计算机夫13 模式结构的节点间的连接是任何示例：数据结构B(D，r ) d= 1，2 )、(1，3 )、(1，4 )、(2，3 )、(3，4 )、(2，4 ) 示例：数据结构C(D，r ) d= 1 14 .数据的存储结构数据的存储结构(也称为物理结构) :是指数据要素及其关系显示在计算机的存储器中，即数据的逻辑结构存储在计算机的存储空间中的形式。 数据的存储结构有顺序存储方式、链存储方式、索引存储方式、散列存储方式4种。 另外，当对同一逻辑结构采用不同的存储结构时，其数据处理的效率不同。 4 .数据运算：检索、排序、插入、删除、修改等。 15、3、线性表线性表是最简单最常用的线性结构。 1 .线性表的定义：线性表是n个元素的有限序列，其关系可以称为a1、a2、ai、an，其中n为表的长度，且在n=0时可称为空表。 线性表(非线性表)必须同时满足以下三个条件： (1)根节点a1只有一个，没有前件。 (2)只有一个终端节点an，没有后件。 (3)除根节点和终端节点以外，其他所有节点只有一个前件，只有一个后件。 16、下图所示的数据结构线性表注：线性表的概念是从逻辑结构的观点考虑的，因此在判断是否为线性表时不考虑其存储结构，线性表可以用4种存储结构表示。 2 .线性表的顺序存储结构的特征： (1)线性表中所有要素所占的存储空间是连续的(2)线性表中各数据要素向存储空间的存储顺序以逻辑顺序进行存储。 17，例如，准确表示线性表(A1、A2、A3、A4)的顺序结构为() A)B)C )分析：在选项c中，线性表的各要素的存储空间是连续的，且要素的存储顺序与逻辑顺序一致。 选项a元素的物理顺序和逻辑顺序不同。 选项b的各要素占据的存储区域是不连续的。 18、依次存储、存储地址、存储内容、an、ai、a2、a1、ADR(a1) k、ADR(a1) (n-1)k、ADR(ai)=ADR(a1) (i-1)k、各要素占有的存储单元的个数、开头另外，序列存储结构将逻辑上邻接的数据元素存储到物理上邻接的存储器单元中，有以下特征：(1)随机存取。 (2)进行插入或删除操作时，需要移动大量的要素。 (3)长度变化大时，有必要在最大空间分配。 (4)表的容量难以扩展。 通常定义表示线性表顺序存储区域的一维数组。 20、3 .线性表的顺序存储结构的插入运算设定顺序表的结构如图所示，其插入运算的顺序如下： (1)溢出：首先判断线性表打开的存储空间是否已满，若满则无法插入，若不满足则继续第二步骤(2)使第I个位置：为空，以便将该元素中的每个元素从最后的元素向后移动一位。 (插入：插入新元素的位置。 21、插入位置与移动要素的数量之间有一定的关系。 线性表大时，其插入运算的效率低。 (1)如果最佳情况：插入位置在线性表的末尾，即，在第n个元素之后插入新的元素，则不需要移动该线性表中的其他元素。 (2)最坏的情况是，插入位置如果在线性表中的第一个元素之前，则需要移动表中的所有元素。(3)如果插入位置在第I个(1In )元素之前，则原始第I个元素之后(包括第I个元素)的所有元素必须移动。 (4)平均在线性表中插入新元素时，需要移动线性表的一半要素。 (n/2个)、22、3 .线性表顺序存储结构的删除运算的具体运算步骤为：次。 如果删除第I个(1In )要素，则从第I个要素到最后的要素，将其中的各要素一位一位地向前移动。 此时，线性表的长度为n-1。 下图：23是线性表顺序记忆结构的删除运算，在删除了一个数据要素后，应该移动原始要素，并且删除位置和应该移动的要素的数量之间有一定的关系。 因此，在线性表大的情况下，删除运算的效率也低。 (1)在最佳情况：中，只要删除位置是线性表的末尾，即，第n个元素被删除，就不需要移动该线性表中的另一个元素。 (2)最坏的情况是，如果删除：线性表中的第一个要素，那么就需要移动表中的所有要素。 (3)平均地，为了删除线性表中的一个元素，需要移动表中的(n-1)/2两个元素。 堆栈的定义：堆栈是一种特殊的线性表，仅限于特殊的数据操作，即一端进行插入和删除的线性表。 在堆栈中，允许插入和删除的一侧称为堆栈顶部，不允许插入和删除的一侧称为堆栈底部。 在堆栈中插入元素调用堆栈运算(堆栈)并从堆栈中删除元素。被称为堆栈运算(堆栈)堆栈的数据操作原则是先进先出(firstinplastout )或后进先出(LIFO )。 堆栈有一定的记忆作用。 另外，25、2 .堆栈的存储结构在编程语言中与普通的线性表同样，是将一维排列作为堆栈S(l:m )的顺序存储的结构，m是堆栈的最大容量。 通常，指针top表示堆栈的顶部位置，指针bottom指向堆栈的底部。 top=0时为空堆栈，top等于数组的最大下标值时为全堆栈。 3 .堆栈的基本运算有三种：输入堆栈、退堆栈、读出堆栈要素。 (1)堆栈运算的步骤：首先，判定堆栈是否已满，如果已满则不进入堆栈(方法top=n )，接着，把堆栈顶部的指针前进1个(即top 1)，26，最后，把新元素配置在堆栈上的指针指向的位置上值得注意的是，避免在堆栈运算中发生溢出错误。 溢出错误是指堆栈上的指针指向存储空间的最后位置时，堆栈中的空间已满，无法进行堆栈操作，因此称为堆栈“溢出错误”。 (2)堆栈运算的步骤：首先，判断堆栈是否为空(方法top=0)，然后，将堆栈最上面的元素分配给指定的变量。最后，堆栈顶部的指针下降了1 (即从top中减去1 )。 值得注意的是，避免在堆栈后运算中发生“下溢”错误。27、(3)读取堆栈最上面的元素的步骤：读取堆栈最上面的元素时，将堆栈最上面的元素指定给指定的变量。 在阅读枝顶要素的过程中要注意的问题是：第一，枝顶要素不是删除枝顶要素，而是只给变量值，因此在这个运算中，枝顶指针不变。 其次，如果堆栈顶部指针为0，则说明堆栈为空，堆栈顶部元素不能读取。 28，5，队列1 .队列的基本概念：队列是只允许一方插入，另一方是允许删除的线性表，也是特殊的线性表。 允许插入的一侧称为队列尾(尾指针、Rear、队列元素)，允许删除的一侧称为队列头(头部指针、前端、队列头元素的前面的位置)。 先进的队列数据操作方法：fifo/lilo。 29、队列中的一个重要应用程序位于操作系统的管理用户程序上。 即，在操作系统中，以队列来管理用户程序的队列执行是以：(1)的初始该队列为空为原则的(2)若用户程序到达，则将该用户程序放入队列的末尾进行等待(3)。与堆栈同样，在程序设计中把一维排列作为队列的顺序存储空间。 30、2 .在循环队列或实际应用中，队列顺序存储结构一般采用循环队列的形式。 原理：循环队列可以将元素添加到队列存储空间的最后一个位置，只要存储空间的第一个位置可用，如图所示。 另外，在循环队列中，从开头指针front指示的下一位置到末尾指针rear指示的位置为止的所有要素都是队列中的要素。 循环队列的初始状态为空，即rear=front=m。 循环队列主要有入队运算和取消运算两种基本运算。 每次进行入队运算时，队伍的最后一个指针都会进入。 队后指针rear=m 1时，每次进行设rear=1的退队运算，开头的指针就前进1个。 开头指针front=m 1时，设置front=1，32。 (a )是容量为8的循环队列存储空间，其中已经有6个要素。 图(b )是在图(a )的循环队列中追加了两个要素的状态。 图(c )是在图(b )的循环队列中退出了一个要素的状态。 (a )在具有六个元素的循环队列(b )加入到x，y之后的循环队列(c )退出了一个元素之后的循环队列，从图(b )中可以看出，若循环队列满了，则front=rear，若循环队列空闲，则front=rear 也就是说，在循环队列中，当前端=rear时，不知道队列是满的还是空的。 33、通常需要添加标志s以区分队列是满的还是空的，s值的定义如下： s=0指示队列为空s=1指示队列不为空，从而使队列为空和空的条件如下：队列为空的条件为s=0； 队列满的条件是s=1并且前端=rear。 循环队列的入队和入队的运算注意点循环队列不为空(s=1)时，前端=rear时循环队列满，不能入队称为“溢出”。 当循环队列为空(s=0)时，不能进行取消运算称为“下溢”。34、6、线性链表1 .链式存储结构，对大线性表和变动频繁的线性表不应用顺序式存储，应采用链式存储。 链式存储的过程如图所示。 每个节点由两部分组成：数据域和指针域。 数据字段中存储元素值，指针字段中存储指针。 数据元素之间的逻辑联系通过指针来表示。35、注：链存储方式中的存储节点不一定是连续的各节点的存储顺序和数据元素的逻辑关系可能不一致链存储方式可以用于线性结构和非线性结构。 2 .线性链表的线性链表是指线性工作台链条的记忆结构。 为了适应线性链表的链存储结构，将计算机存储空间划分为一个小块，每个小块占用几个字节，通常将这些小块称为存储节点。36、在线性链表中，磁头指针(head )很重要，不应该丢失的链表最后一个节点的指针字段为空，空表(线性链表) :用空或0表示。 当head (指向线性表的第一个节点的指针head称为开头指针)等于NULL或0时，称为空表。单链表的缺点只发现后项，为了克服找不到前项的单链表的缺点，出现了双向链表的概念在双向链表中，将每个节点修改为由以下三部分构成的：37，并且，双向链表的节点结构如下图所示。 3 .在堆栈的链存储