第讲计算机软件基础知识解决方案.ppt

计算机软件基础知识 第三讲 3.1数据结构与算法 1.1 算法 算法：是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程。算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。 算法是一组严谨地定义运算顺序的规则，每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。所以其四个基本特征包括： (1) 确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性； (2) 有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止； (3) 可行性，算法原则上能够精确地执行； (4) 拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的三种基本控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 算法效率的度量—算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度：指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次数。通常，一个算法所用的时间包括编译时间和运行时间。 算法空间复杂度：指执行这个算法所需要的内存空间。包括算法程序所占的空间，输入的初始数据所占的空间，算法执行过程中所需的额外空间。 1.2 数据结构的基本概念 数据结构：指相互有关联的数据元素的集合。 数据结构研究的三个方面： (1) 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； (2) 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； (3) 对各种数据结构进行的运算。 数据的逻辑结构应包含： (1) 表示数据元素的信息； (2) 表示各数据元素之间的前后件关系(指逻辑关系，与存储位置无关)。 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构,也称数据物理结构。 数据的存储结构有顺序、链接、索引等。 线性结构的条件，(一个非空数据结构)： (1) 有且只有一个根结点； (2) 每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1.3栈和队列 栈：限定在一端进行插入与删除的线性表。 其允许插入与删除的一端称为栈顶，用指针top表示栈顶位置。 不允许插入与删除的另一端称为栈底，用指针bottom表示栈底。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。 栈的存储方式有顺序存储和链式存储。 栈的基本运算： （1）入栈运算，在栈顶位置插入元素； （2） 退栈运算，删除元素(取出栈顶元素并赋给一个指定的变量)； （3） 读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变化。 队列：指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。 用rear指针指向队尾，用front指针指向队头元素的前一个位置。 队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算包括：(1) 入队运算：从队尾插入一个元素； (2) 退队运算：从队头删除一个元素。 队列的顺序存储结构一般采用队列循环的形式。 循环队列s=0表示队列空；s=1且front=rear表示队列满。 计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可。 计算循环队列长度： ①front=rear，队列长度＝0； ②frontrear，队列长度＝rear-front； ③frontrear，队列长度＝rear+size -front 1.4 树与二叉树 树是一种简单的非线性结构，其所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的直接后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。 二叉树的特点： (1) 非空二叉树只有一个根结点； (2) 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点，深度为m的满二叉树有2m-1个结点。 完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。 二叉树基本性质： (1) 在二叉树