资源预览内容
第1页 / 共18页
第2页 / 共18页
第3页 / 共18页
第4页 / 共18页
第5页 / 共18页
第6页 / 共18页
第7页 / 共18页
第8页 / 共18页
第9页 / 共18页
第10页 / 共18页
亲,该文档总共18页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
1.1 算法的复杂度 1. 算法的基本概念 利用计算机算法为计算机解题的过程实际上是在实施某种算法。 (1)算法的基本特征 算法一般具有 4 个基本特征:可行性、确定性、有穷性、拥有足够的 情报。 (2)算法的基本运算和操作 算法的基本运算和操作包括:算术运算、逻辑运算、关系运算、数据 传输。 (3)算法的 3 种基本控制结构 算法的 3 种基本控制结构是:顺序结构、选择结构、循环结构。 (4)算法基本设计方法 算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯 法。 (5)指令系统 所谓指令系统指的是一个计算机系统能执行的所有指令的集合。 2. 算法复杂度 算法复杂度包括时间复杂度和空间复杂度。注意两者的区别,无混淆, 见表 1-1。 表1-1 算法复杂性 名称 描述 时间复杂度 执行算法所需要的计算工作量 空间复杂度 执行这个算法所需要的内存空间 1.2 数据结构 1.2.1 逻辑结构和存储结构 1. 数据结构的基本概念 (1)数据结构 指相互有关联的数据元素的集合。 二级公共基础知识速学教程 2 (2)数据结构研究的 3 个方面 数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结 构; 在对数据进行处理时,各数据元素在计算机中的存储关系,即数 据的存储结构; 对各种数据结构进行的运算。2. 逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个 数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有 两个要素:一是数据元素的集合,通常记为 D;二是 D 上的关系,它反映 了数据元素之间的前后件关系,通常记为 R。一个数据结构可以表示成: B=(D,R)其中,B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系,一般用二元组来表示。例如,如果把一年四季看作一个数据结构,则可表示成:B =(D,R) D =春季,夏季,秋季,冬季 R =(春季,夏季),(夏季,秋季),(秋季,冬季)3. 存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构 (也称数据的物理结构) 。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同, 因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系 (即前后件关系) ,在数据的存储结构中,不仅要存放各数据元素的信息, 还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储 结构有顺序、链接等存储结构。 顺序存储方式主要用于线性的数据结构,它把逻辑上相邻的数据元素 存储在物理上相邻的存储单元里,结点之间的关系由存储单元的邻接关系 来体现。链式存储结构就是在每个结点中至少包含一个指针域,用指针来体现数据元素之间逻辑上的联系。1.2.2 线性结构和非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据 结构分为两大类型:线性结构与非线性结构。 (1)如果一个非空的数据结构满足下列两个条件: 有且只有一个根结点; 每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都为线性 结构。如果一个数据结构不是线性结构,则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。(2)线性表的顺序存储结构具有以下两个基本特点: 线性表中所有元素所占的存储空间是连续的; 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。元素 ai 的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,ADR(a1)为第一个 元素的地址,k 代表每个元素占的字节数。 (3)顺序表的运算有查找、插入、删除 3 种。 1.3 栈 1. 栈的基本概念栈(stack)是一种特殊的线性表,是限定只在一端进行插入与删除的线性表。在栈中,一端是封闭的,既不允许进行插入元素,也不允许删除元素;另一端是开口的,允许插入和删除元素。通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。栈是按照“先进后出”或“后进先出”的原则组织数据的。例如,枪 械的子弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的, 最后被压入弹匣的子弹总是最先被弹出,而最先被压入的子弹最后才能被 弹出。2. 栈的顺序存储及其运算栈的基本运算有 3 种:入栈、退栈与读栈顶元素。 入栈运算:在栈顶位置插入一个新元素; 退栈运算:取出栈顶元素并赋给一个指定的变量; 读栈顶元素:将栈顶元素赋给一个指定的变量。1.4 队列1. 队列的基本概念队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将 允许删除的这一端称为队头,允许插入的这一端称为队尾。当表中没有元 素时称为空队列。 队列的修改是依照先进先出的原则进行的,因此队列也称为先进先出 的线性表,或者后进后出的线性表。例如:火车进遂道,最先进遂道的是 火车头,最后是火车尾,而火车出遂道的时候也是火车头先出,最后出的 是火车尾。若有队列:Q =(q1,q2,qn)那么,q1 为队头元素(排头元素) ,qn 为队尾元素。队列中的元素是 按照 q1,q2,qn 的顺序进入的,退出队列也只能按照这个次序依次 退出,即只有在 q1,q2,qn-1 都退队之后,qn 才能退出队列。因最 先进入队列的元素将最先出队,所以队列具有先进先出的特性,体现“先 来先服务”的原则。队头元素 q1 是最先被插入的元素,也是最先被删除的元素。队尾元素 qn是最后被插入的元素,也是最后被删除的元素。因此,与栈相反,队列又称为“先进先出” (First In First Out,简称 FIFO) 或“后进后出”(Last In Last Out,简称 LILO)的线性表。2. 队列运算 入队运算是往队列队尾插入一个数据元素;退队运算是从队列的队头 删除一个数据元素。 队列的顺序存储结构一般采用队列循环的形式。循环队列 s=0 表示队 列空; s=1 且 front=rear 表示队列满。计算循环队列的元素个数:“尾指针减头指 针” ,若为负数,再加其容量即可。 1.5 链表 在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数 据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中指针 用于指向该结点的前一个或后一个结点(即前件或后件) 。链式存储方式既可用于表示线性结构,也可用于表示非线性结构。(1)线性链表线性表的链式存储结构称为线性链表。 在某些应用中,对线性链表中的每个结点设置两个指针,一个称为左 指针,用以指向其前件结点;另一个称为右指针,用以指向其后件结点。 这样的表称为双向链表。 在线性链表中,各数据元素结点的存储空间可以是不连续的,且各数 据元素的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除, 不需要移动链表中的元素。 线性单链表中,HEAD 称为头指针,HEAD=NULL(或 0)称为空表。如果是双项链表的两指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点。线性链表的基本运算:查找、插入、删除。(2)带链的栈栈也是线性表,也可以采用链式存储结构。带链的栈可以用来收集计 算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。 1.6 二叉树1.6.1 二叉树概念及其基本性质1. 二叉树及其基本概念二叉树是一种很有用的非线性结构,具有以下两个特点: 非空二叉树只有一个根结点; 每一个结点最多有两棵子树,且分别称为该结点的左子树和右子树。在二叉树中,每一个结点的度最大为 2,即所有子树(左子树或右子 树)也均为二叉树。另外,二叉树中的每个结点的子树被明显地分为左子 树和右子树。在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时,该结点即为叶子结点。例如,一个家族中的族谱关系如图 1-1 所示:A 有后代 B,C;B 有后代 D,E;C 有后代 F。典型的二叉树如图 1-1 所示:父结点(根) 在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结 点只有一个,称为树的根结点,简称树的根。例如,在图 1-1 中,结点 A 是树的根结点。 子结点和叶子结点 在树结构中,每一个结点可以有多个后件,称为该结点的子结点。没 有后件的结点称为叶子结点。例如,在图 1-1 中,结点 D,E,F 均为叶子 结点。 度 在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结 点中最大的度称为树的度。例如,在图 1-1 中,根结点 A 和结点 B 的度为 2,结点 C 的度为 1,叶子结点 D,E,F 的度为 0。所以,该树的度为 2。 深度 定义一棵树的根结点所在的层次为 1,其他结点所在的层次等于它的父结点所在的层次加 1。 树的最大层次称为树的深度。例如,在图 1-1 中,根结点 A 在第 1 层,结点 B,C 在第 2 层,结点 D,E,F 在第 3 层。该树的深度为 3。 子树 在树中,以某结点的一个子结点为根构成的树称为该结点的一棵子树。 详细讲解二叉树的基本概念,见表 1-2。父结点(根) 在树结构中,每一个结点只有一个前件,称 为父结点,没有前件的结点只有一个,称为树 的根结点,简称树的根。例如,在图1-1中,结 点A是树的根结点。 子结点和 叶子结点 在树结构中,每一个结点可以有多个后件,称 为该结点的子结点。没有后件的结点称为叶子 结点。例如,在图 1-1 中,结点 D,E,F 均为 叶子结点。 度 在树结构中,一个结点所拥有的后件的个数称 为该结点的度,所有结点中最大的度称为树的 度。例如,在图 1-1 中,根结点 A 和结点 B 的 度为 2,结点 C 的度为 1,叶子结点 D,E,F 的度为 0。所以,该树的度为 2。 深度 定义一棵树的根结点所在的层次为 1,其他结点 所在的层次等于它的父结点所在的层次加 1。树 的最大层次称为树的深度。例如,在图 1-1 中, 根结点 A 在第 1 层,结点 B,C 在第 2 层,结 点 D,E,F 在第 3 层。该树的深度为 3。子树 在树中,以某结点的一个子结点为根构成的树 称为该结点的一棵子树。 2. 二叉树基本性质 二叉树具有以下几个性质: 性质 1:在二叉树的第 k 层上,最多有 2k-1(k1)个结点。 性质 2:深度为 m 的二叉树最多有 2m-1 个结点。 性质 3:在任意一棵二叉树中,度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个。 性质 4:具有 n 个结点的二叉树,其深度至少为log2n+1,其中log2n表示取 log2n 的整数部分。 3. 满二叉树与完全二叉树 满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结 点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第 k 层上有 2k- 1 个结点,且深度为 m 的满二叉树有 2m-1 个结点。 完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在 最后一层上只缺少右边的若干结点。 对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点, 若其右分支下的子孙结点的最大层次为 p,则其左分支下的子孙结点的最大层次或为 p,或为 p+1。 完全二叉树具有以下两个性质: 性质 1:具有 n 个结点的完全二叉树的深度为log2n+1。 性质 2:设完全二叉树共有 n 个结点。如果从根结点开始,按层次(每一层从左到右) 用自然数 1,2,n 给结点进行编号,则对于编号为 k(k=1,2,n)的结 点有以下结论: 若 k=1,则该结点为根结点,它没有父结点;若 k1,则该结点的父结点编号为
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号