第13章 数据结构与算法.ppt

13.1 算 法 13.2 数 据 结 构 13.3 线性表及顺序存储结构 13.4 栈 与 队 列 13.5 线 性 链 表 13.6 树与二叉树 13.7 查 找 技 术 13.8 排 序 技 术 13.1 算 法 13.1.1 算法的基本概念 算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。它是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或者多个操作 1．算法的基本特征 有穷性： 确定性： 可行性： 拥有足够情报： 2．算法的基本要素 （1）算法对数据的运算和操作 （2）算法的控制结构 3．算法设计的基本方法 列举法、归纳法、递推法、递归法、减半递推技术、回溯法 13.1.2 算法复杂度 算法复杂度的评价有两个指标：时间复杂度、空间复杂度 1．算法的时间复杂度 算法所执行的基本运算次数是问题规模的函数，即 算法工作量＝f(n) 2．算法的空间复杂度 13.2 数 据 结 构 13.2.1 数据结构的基本概念 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式 数据结构主要研究和讨论以下3个方面的问题： 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。 在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。 对各种数据结构进行的运算。 13.2.2 数据结构及其图形表示 数据结构主要指逻辑结构和存储结构。 1．数据的逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据逻辑结构应包含以下两方面信息： ① 表示数据元素的信息。 ② 表示各数据元素之间的前后件关系。 根据数据元素之间关系的不同特性，通常有4种基本结构：集合、线性结构、树形结构、图状结构或网状结构。 满足以下3个条件的非空数据结构称为线性结构，又称线性表。 ① 有且仅有一个根结点。 ② 每一个结点最多有一个前件和一个后件。 ③ 在线性结构中插入或删除一个结点后还应是线性结构。 2．数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式，称为数据的存储结构（也称数据的物理结构）。 3．数据结构的表示 （1）二元组表示法 数据逻辑结构仅反映数据元素之间的前后件关系，与它们在计算机中的存储位置无关。数据逻辑结构用二元组来表示，通常记为： B=(D,R) 其中，B表示数据结构，D表示数据元素的集合，R表示数据元素之间的前后件关系 （2）图形表示 数据结构除了用二元关系表示外，还可以用图形更直观的表示。用中间标有元素值的方框来表示数据集合，每一个方框称为结点；用一条有向线段从前件结点指向后件结点，来表示数据元素之间的前后件关系。例如： 13.3 线性表及顺序存储结构 13.3.1 线性表的基本概念 1．基本概念 线性表是n（n≥0）个元素构成的有限序列。表中每一个元素，除了第一个元素，有且只有一个前件；除了最后一个元素，有且只有一个后件。 线性表的表示和实现有两种标准，一是顺序表，二是线性链表。 线性表的逻辑特征是： ① 有且只有一个根结点a1，它无前件。 ② 有且只有一个终端结点an，它无后件。 ③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度，当n=0 时，称为空表。 2．线性表的顺序存储结构 线性表的顺序存储结构具有以下两个特点： ① 线性表的所有元素所占的存储空间是连续的。 ② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 13.3.2 顺序表的运算 1．顺序表的插入运算 2．顺序表的删除运算 顺序存储结构也存在以下缺点： ① 需要一块地址连续的存储单元作为线性表的存储空间。 ② 在插入操作和删除操作时要移动大量数据，插入与删除运算的效率很低。 ③ 存储空间不便于扩充，不能对存储空间进行动态分配。 13.4 栈 与 队 列 13.4.1 栈及其基本运算 1．栈的定义栈（stack）是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶（top），另一端为栈底（bottom）。栈也称为先进后出的线性表，或后进先出的线性表。 2．栈的顺序存储及其运算 栈的常用运算有3种：入栈、退栈、读栈顶元素 （1）入栈运算 入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一（即 top 加 1），然后将新元素插入到栈顶指针指向的位置。当栈顶指针指向栈的存储空间的最后一个位置，说