阳光计算机学校教学公共基础课件.ppt

二级公共基础知识 第一章 算法与数据结构 第二章 程序设计基础 第三章 软件工程基础 第四章 数据库设计基础 第一章 算法与数据结构 一、算法 二、数据结构 三、线性表 四、栈 五、队列 六、线性链表 七、树与二叉树 八、查找技术 九、排序技术 一、算法 1.算法的基本概念 算法是指解题方案准确而完整的描述。 （1）算法的特征：可行性、确定性、有穷性、拥有足够的情报。 （2）算法的两个基本要素：一是对数据对象的运算和操作，具体包括算术运算、逻辑运算、关系运算和数据传输等；二是算法的控制结构，具体包括顺序结构、选择结构和循环结构。 2.算法的复杂度 算法的复杂度：是衡量算法好坏的量度，具体可分为两种:时间复杂度和空间复杂度。 （1）时间复杂度是指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数。  （2）空间复杂度是指执行该算法所需要的内存空间。 具体包括（1）算法程序所占的空间；（2）输入的初始数据所占的存储空间；（3）算法执行过程中的额外空间 二、数据结构 1.数据结构的基本概念 数据结构就是相互有关联的数据元素的集合。 一年四季：春、夏、秋、冬 家庭成员：父亲、儿子、女儿 数据结构有三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。 数据的逻辑结构是指数据元素之间的逻辑关系，从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式；存储结构的存储方式有：顺序存储和链式存储。 数据的运算即算法。 在数据结构中，没有前件的节点称为根节点； 没有后件的节点称为终端节点（也称为叶子节点）；除了根节点与终端节点外的其他节点称为内部节点。 数据的逻辑结构分为两种:线性结构和非线性结构。 线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。如：一年四季。 非线性结构：如果一个数据结构不是线性结构，则称之为存储结构。如：反映家庭成员间辈分关系的数据结构。 A.线性结构 ①线性表②栈——先进后出的线性表 ③队列——先进先出的线性表 如下“学生成绩表”就是线性表 B.非线性结构 ①树型结构（树、二叉树）例:全校学生档案管理的组织方式 三、线性表 线性表是最简单的、最常用的一种线性结构。 线性表（非空线性表）必须同时满足以下3个条件： （1）有且只有一个根结点a1，它无前件。（2）有且只有一个终端结点an，它无后件。（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 1.线性表的顺序存储结构 特点：（1）线性表中所有元素所占的存储空间是连续的;（2）线性表中各数据元素在存储空间中的存放顺序是按逻辑顺序依次存放的。如图所示 例：正确表示线性表(A1，A2，A3，A4)的顺序结构是( )  A) B) C) 六、线性链表 1.链式存储结构对于大的线性表或者变动频繁的线性表不宜用顺序存储，应该采用链式存储。 四、栈 1.栈的定义：栈是一种特殊的线性表，特殊在其数据操作上，即限定在一端进行插入与删除的线性表。在栈中，允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。 往栈中插入一个元素叫入栈运算 从栈中删除一个元素称为退栈运算 栈的数据操作原则是先进后出或后进先出。 2.栈的基本运算 有三种:入栈、退栈和读栈顶元素。 (1)入栈运算： 值得注意的是，在入栈运算中应避免上溢错误的出现。上溢错误是指当栈顶指针己经指向存储空间的最后一个位置时，说明栈的空间己满，不能再进行入栈操作，这种情况称为栈“上溢”错误。 (2)退栈运算：值得注意的是，退栈运算中应避免“下溢”错误的出现。下溢错误是指当栈顶指针为0时，说明栈空，不可能在进行退栈操作，这种情况称为栈 “下溢”错误。 (3) 读栈顶元素：读栈顶元素是指将栈顶元素赋值给一个指定的变量 五、队列 1.队列的基本概念： 队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种特殊的线性表。允许插入的一端叫队尾(尾指针， Rear，指向队尾元素)，允许删除的一端叫队头(头指针， Front，指向队头元素的前一个位置)。队列的数据操作方法:先进先出。 2.循环队列在实际应用中，队列的顺序存储结构一般采用循环队列的形式。 原理:循环队列是指当队列存储空间的最后一个位置己被使用而仍要进行入队运算，这时只要存储空间的第一个位置空闲，便可以将元素加入到这个位置，即将存储空间的第一个位置作为队尾，如图所示。 例：图（a）是一个容量为8的循环队列存储空间，且其中已有6个元