《二级公共基础知识》-精选·课件.ppt

二级公共基础知识 ;二级公共基础知识;第一章 算法与数据结构;第一章 算法与数据结构;一、算法 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)例:学生成绩表 ②栈——后进先出 ③队列——先进先出;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)} ;3.数据的存储结构 数据的存储结构(又称物理结构):是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。 数据的存储结构有4种：顺序存储方式、链式存储方式、索引存储方式和散列存储方式。需要注意的是，对于同一个逻辑结构来说，采用不同的存储结构时，其数据处理的效率是不同的。 4.数据的运算：检索、排序、插入、删除、修改等。 ;三、线性表 线性表是最简单的、最常用的一种线性结构。 1.线性表的定义:线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，…… ，ai，…… ，an ，其中n称作表的长度，当n=0时，称作空表。 线性表（非空线性表）必须同时满足以下3个条件： （1）有且只有一个根结点a1，它无前件。（2）有且只有一个终端结点an，它无后件。（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 ; 如下图所示的数据结构就是线性表 注：线性表的概念是从逻辑结构的角度说的，所以，判断是否为线性表时并不考虑其存储结构，线性表可以用四种不同的存储结构来表示。 2.线性表的顺序存储结构 特点：（1）线性表中所有元素所占的存储空间是连续的;（2）线性表中各数据元素在存储空间