数据结构期末复习总结

第第 1 章章绪论绪论 1 数据 Data 是描述客观事物的数字 字符以及所有能输入到计算机中并能被计算机接 受的各种符号集合的统称 包括数值数据和非数值数据 字符串 图形 图像 音频 视频 2 数据元素 Data Element 表示一个事物的一组数据称为一个数据元素 结点顶点 记录 数据元素是数据的基本单位 3 数据项 Data Item 是数据元素中有独立含义的 不可分割的最小标识单位 字段 域 属性 一个数据元素可由若干个数据项组成 4 数据对象 Data Object 是性质相同的数据元素的集合 是数据的一个子集 如字符集合 C A B C 数据 Data 是描述客观事物的数字 字符以及所有能输入到计算机中并能被计算机接受 的各种符号集合的统称 包括数值数据和非数值数据 字符串 图形 图像 音频 视频 数据元素 Data Element 表示一个事物的一组数据称为一个数据元素 结点 顶点 记录 数据元素是数据的基本单位 数据项 Data Item 是数据元素中有独立含义的 不可分割的最小标识单位 字段 域 属性 一个数据元素可由若干个数据项组成 数据对象 Data Object 是性质相同的数据元素的集合 是数据的一个子集 如字符集 合 C A B C 数据的逻辑结构指数据元素之间的逻辑关系 用一个数据元素的集合和定义在此集 合上的若干关系来表示 四种逻辑结构 集合 线性结构 树型结构 图状结构 数据结构的形式定义是一个二元组 Data Structure D S 其中 D 是数据元素的有限集 S 是 D 上关系的有限集 例 1 设数据逻辑结构 B K R K k1 k2 k9 R 有时候关系图不唯一 一般是无向图 数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示 两种不同的存储结构 顺序存储结构和链式存储结构 顺序结构 数据元素存放的地址是连续的 链式结构 数据元素存放的地址是否连续没有要求 用该指针来表示数据 元素之间的逻辑结构 关系 顺序存储 使用一组连续的内存单元依次存放数据元素 元素在内存中的物理存储 次序体现它们的逻辑次序 通常使用程序设计语言中的数组来实现 链式存储 使用若干地址分散的存储单元存储数据元素 逻辑上相邻的数据元素在 物理位置上不一定相邻 数据元素间的逻辑关系通过结点间的链接关系来体现 通 常使用指针记载直接前驱元素或直接后继元素的存储地址 数据操作指对一种数据结构中的数据元素进行各种运算或处理 每种数据结构都有一组数 据操作 初始化 判断是否空状态 统计元素的个数 遍历 按某种次序访问所有元素 每个元素只被访问一次 取值 获取指定元素值 置值 设置指定元素值 插入 增加指定元素 删除 移去指定元素 查找 在数据结构中寻找满足给定条件的数据元素 排序 将数据元素 数据操作定义在数据的逻辑结构上 数据操作的实现依赖于数据的存储结构 数据结构三方面的关系 数据的逻辑结构 数据的存储结构及操作这三方面是一个整体 例 6 线性表是一种逻辑结构 若采用顺序存储 可称其为顺序表 若采用链式存 储 则可称其为链表 若采用散列存储 则可称为散列表 在给定了数据的逻辑结构和存储结构之后 按定义的操作集合及其操作的性质不同 也可能导致完全不同的数据结构 类型 type 是具有相同逻辑意义的一组值的集合 数据类型是指一个类型和定义在这个类型上的操作集合 数据类型定义了数据的性质 取值范围以及对数据所能进行的各种操作 例 7 Java 中整型类型 int 的值集是 231 2 1 0 1 2 231 1 这个值集上的操作集合 抽象数据类型 Abstract Data Type 简称 ADT 是指一个数学模型以及 定义在该模型上的一组操作 ADT 的定义仅是一组逻辑特性描述 与其在计算机内的表示和实现无关 因此 不论 ADT 的内部结构如何变化 只要其数学特性不变 都不影响其外部使 用 ADT 的形式化定义是三元组 ADT D S P 其中 D 是数据对象 S 是 D 上的关系集 P 是对 D 的基本操作集 ADT 的一般定义形式是 ADT 数据对象 数据关系 基本操作 ADT 例 8 复数抽象数据类型描述如下 ADT Complex double real imag Complex double real double imag Complex add Complex c Complex sub Complex c 1 算法定义 一个算法 algorithm 是一个有穷规则的集合 其规则确定一个解决某一特 定类型问题的操作序列 D Knuth 算法的规则必须满足以下 5 个特性 有穷性 一个算法必须总是在执行有穷步之后结束 且每一步都在有穷时间内完成 确定性 算法中每一条指令必须有确切的含义 不存在二义性 且算法只有一个入口和 一个出口 可行性 一个算法是能行的 即算法描述的操作都可以通过已经实现的基本运算执行 有限次来实现 输入 一个算法有零个或多个输入 这些输入取自于某个特定的对象集合 输出 一个算法有一个或多个输出 这些输出是同输入有着某些特定关系的量 2 算法设计目标 正确性 健壮性 高时间效率 高空间效率 可读性 3 算法描述 自然语言描述 伪码描述 传统流程图描述 程序设计语言描述 本课程选 Java 4 算法与数据结构 算法建立在数据结构之上 对数据的操作需用算法来描述 算法设计依赖数据的逻辑结构 算法实现依赖数据的存储结构 实现一种抽象数据类型 需要选择合适的存储结构 求解同一问题可能有许多不同的算法 如何去评价这些算法的优劣 主要考虑如下三点 A 执行算法所耗费的时间 B 执行算法所耗费的存储空间 其中主要考虑辅助存储空间 C 算法应易于理解 易于编码 易于调试等等 1 时间代价分析 算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势 通常采用时间复杂度 来度量算法的时间效率 用大 O 表示法来记 T n O f n 例 1 void fun x s 0 将 x 自增看成是基本操作 则语句频度为 即时间复杂度为 1 如果将 s 0 也看成是基本操作 则语句频度为 其时间复杂度仍为 1 即常量阶 一个简单语句的时间复杂度为 1 例 2 for i 1 i n i x s x 语句频度为 2n 其时间复杂度为 n 即为线性阶 一个循环的时间复杂度为 n 例 3 for i 1 i n i for j 1 j n j x s x 语句频度为 2n2 其时间复杂度为 O n2 即为平方阶 定理 若 A n a m n m a m 1 n m 1 a1n a0是一个 m 次多项式 则 A n O n m 例 4 两个 n 阶方阵的乘法 for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j a i k b k j 由于是一个三重循环 每个循环从 1 到 n 则总次数为 n n n n3 时间复杂度为 T n n3 例 5 for i 2 i n i for j 2 j i 1 j x a i j x 语句频度为 1 2 3 n 2 1 n 2 n 2 2 n 1 n 2 2 n2 3n 2 时间复杂度为 O n2 即此算法的时间复杂度为平方阶 例 6 int n 8 count 0 for int i 1 i n i 2 for int j 1 j n j count 循环次数为 时间复杂度为 O nlog2n 例 7 int n 8 count 0 for int i 1 i n i 2 for int j 1 j i j count 总的循环次数为 时间复杂度为 O n 以下六种计算算法时间的多项式是最常用的 其关系为 O 1 O n O n O n n O n2 O n3 指数时间的关系为 O 2n O n 0 时 将非空的线性表记作 a0 a1 an 1 线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素 用顺序存储实现的线性表称之为顺序表 线性表的逻辑顺序与物理顺序一致 顺序表是一种随机存取结构 通常采用数组存储数据元素 设线性表的每个元素需占用 c 个存储单元 public boolean isEmpty 时间复杂度时间复杂度 O 1 return this len 0 public int length 时间复杂度时间复杂度 O 1 return this len public T get int i 时间复杂度时间复杂度 O 1 if i 0 for int i 1 i this len i str this element i toString return str 两个线性表相等是指 它们长度相同并且各对应元素相等 链式存储 用一组任意的存储单元存储线性表中的数据元素 存储链表中结点的 一组任意的存储单元可以是连续的 也可以是不连续的 甚至是零散分布在内存中 的任意位置上的 链表中结点的逻辑顺序和物理顺序不一定相同 链表中的结点结构 数据域和地址域 n 个结点构成的链表表示为 a0 a1 an 1 链表中每个结点只含一个地址域 又称为线性链表或单链表 每个结点有两个地址域的线性链表称为双链表 单链表是由表头唯一确定 因此单链表可以用头指针的名字来命名 头结点的作用是 使所有链表 包括空表 的头指针非空 则对单链表的插入 删除操作 不需要区分操作位置 头结点中不存储数据 头插入和头删除操作不会改变 head 指针 总结总结 顺序表和链表的比较顺序表和链表的比较 1 直接访问元素的性能 直接访问元素的性能 顺序表能够直接访问数据元素 即只要给出顺序表底层数组顺序表能够直接访问数据元素 即只要给出顺序表底层数组 element 的下标就可以的下标就可以 访问数组中的任何一个数据元素 访问数组中的任何一个数据元素 随机存取 随机存取 而链表中不能随机地直接访问大多数元素 只能从链表的第一个结点开始 沿着链而链表中不能随机地直接访问大多数元素 只能从链表的第一个结点开始 沿着链 的方向 依次查找后续结点 直至到达所需访问的结点 的方向 依次查找后续结点 直至到达所需访问的结点 顺序存取 顺序存取 2 存储空间的利用 存储空间的利用 由于需要估计顺序表底层数组由于需要估计顺序表底层数组 element 的大小 顺序表的容量 的大小 顺序表的容量 因此顺序表存在 因此顺序表存在 存储空间的浪费问题 存储空间的浪费问题 顺序表在进行插入操作时 要判断顺序表是否为满 如果满 则需要扩充容量 顺序表在进行插入操作时 要判断顺序表是否为满 如果满 则需要扩充容量 而链表每插入一个结点 就向系统申请一个存储单元 只要系统资源足够 系统就而链表每插入一个结点 就向系统申请一个存储单元 只要系统资源足够 系统就 会为该结点分配存储空间 会为该结点分配存储空间 3 存储密度 存储密度 存储密度 存储密度 Storage Density 是指结点数据本身所占的存储量和整个结点结构所占 是指结点数据本身所占的存储量和整个结点结构所占 的存储量之比 即 的存储量之比 即 结点数据本身所占的存储量 结点数据本身所占的存储量 整个结点所占的存储总量 整个结点所占的存储总量 顺序表的全部空间都用来存放数据元素 因此存储密度顺序表的全部空间都用来存放数据元素 因此存储密度 1 而链表中每个结点都要包含其后继结点或者前驱结点的链 因此存储密度而链表中每个结点都要包含其后继结点或者前驱结点的链 因此存储密度 0 个相同类型的数据元素 a0 a1 an 1组成的有限序列 记为 a0 a1 an 1 其中 n 为数据元素的个数 称为栈的长度 n 0 时 为空栈 栈的溢出 当栈满时进栈运算称为 上溢 当栈空时退栈运算称为 下溢 栈上溢是一种出错状态 应该设法避免之 而下溢则可能是正常现象 通 常下溢用来作为程序控制转移的条件 由于栈是运算受限的线性表 因此线性表的存储结构对栈也适应 栈的顺序存储结构简称为顺序栈 Sequential Stack 它是运算受限的线性表 因 此 可用数组来实现顺序栈 因为栈底位置是固定不变的 所以可以将栈底位置设置在数组的两端的任何一个端 点 栈顶位置是随着进栈和退栈操作而变化的 一般需用一个整型变量 top 栈的顺序存储结构及操作实现 public class SeqStack implements Stack 顺序栈类 实现栈接口 Object element 存储栈数据元素的数组 int top 栈顶元素下标 注意 element 数组存储栈的数据元素 top 表示当前栈顶元素的下标 经典实现 1 栈的初始化 public SeqStack int size 构造容量为 size 的空栈 this element new Object Math abs size this top 1 public SeqStack 构造默认容量的空栈 this 64 2 判读栈是否为空 public boolean isEmpty 判断栈是否空 若空返回 true return this top 1 判读栈是否为满 本实现采用与顺序表同样的处理 当容量不够时 则将数组容量扩充一倍 3 入栈 public void push T x 元素 x 入栈 空对象不能入栈 if x null return 空对象不能入栈 if this top element length 1 若栈满 则扩充栈容量 Object temp this element 重新申请一个容量更大的数组 this element new Object temp length 2 for int i 0 i temp length i 复制数组元素 O n this element i temp i this top this element this top x 4 出栈 栈不空时 取走 top 位置处栈顶元素 top 减 1 下一位置数据元素作为新的栈顶元素 public T pop 出栈 返回栈顶元素 若栈空返回 null return this top 1 null T this element this top 5 获得栈顶数据元素 栈不空时 获取 top 位置处栈顶元素 此时数据元素未出栈 top 值不变 public T get 取栈顶元素 未出栈 若栈空返回 null return this top 1 null T this element this top 顺序栈类 最终类 实现栈接口 T 表示元素类型 public final class SeqStack implements Stack private SeqList list 顺序表 public SeqStack int capacity 构造栈 public SeqStack 构造空栈 public boolean isEmpty 判空 public void push T x x 入栈 public T peek 返回栈顶 未出栈 public T pop 出栈 返回栈顶元素 栈的链式存储 称为链栈 链式栈的基本运算同顺序栈 定义也同线性表的链表定义 它是对链表实现的简单 化 因为它只是对链表的头部操作 可用单链表实现链栈 它的元素只能在表头进行插入和删除 在链式存储结构中 不需要给出表头结点 head 因为其中惟一的已知条件是栈顶指针 top 它是指向链式栈的第一个结 点 相当于头指针 栈的各种运算比链式存储的普通线性表运算实现时要方便得多 主要原因是栈的各 种运算只能在栈的一端操作 栈是特殊的线性表 我们只要考虑对线性表的一端操 作的情况 并且只能在一端插入删除 栈顶 而线性表除此之外 不限定一端插入删除 还需要考虑另外一端结点以及中间的 结点的插入 删除 查询等操作 理解时 我们可以把栈的入出栈运算当作线性表 的一端进行插入删除的特例即可 链式栈实现 经典实现 栈的链式存储结构及操作实现 public class LinkedStack implements Stack private Node top 1 栈的初始化 public LinkedStack 构造空栈 this top null 2 判读栈是否为空 public boolean isEmpty 判断栈是否空 若空返回 true return this top null 3 入栈 public void push T x 元素 x 入栈 空对象不能入栈 if x null this top new Node x this top 头插入 x 结点作为新的栈顶结点 4 出栈 public T pop 出栈 返回栈顶元素 若栈空返回 null if this top null return null T temp this top data 取栈顶结点元素 this top this top next 删除栈顶结点 return temp 5 获得栈顶元素 public T get 取栈顶元素 未出栈 若栈空返回 null return this top null null this top data 链式栈实现 基于单链表 链式栈类 最终类 实现栈接口 T 表示数据元素的数据类型 public final class LinkedStack implements Stack private SinglyList list 使用单链表 第 2 章 存储栈元素 public LinkedStack 构造空栈 this list new SinglyList 构造空单链表 public boolean isEmpty 判断栈是否空 若空返回 true return this list isEmpty public void push T x 元素 x 入栈 空对象不能入栈 this list insert 0 x 单链表头插入元素 x public T peek 返回栈顶元素 未出栈 若栈空返回 null return this list get 0 public T pop 出栈 返回栈顶元素 若栈空返回 null return this list remove 0 若栈不空 单链表头删除 返回删除元素 public String toString 返回栈所有元素的描述字符串 形式为 return this getClass getName this list toString 顺序栈和链式栈的比较 实现链式栈和顺序栈的操作 都是需要常数时间 即时间复杂度为 O 1 主要两 者从空间和时间两个方面考虑 初始时 顺序栈必须说明一个固定的长度 当栈不够满时 造成一些空间 的浪费 而链式栈的长度可变则是长度不需要预先设定 相对比较节省空 间 但是在每个结点中 设置了一个指针域 从而产生了结构开销 当需要多个栈共享时 顺序存储中可以充分利用顺序栈的单向延伸性 可 以使用一个数组存储两个栈 使每个栈从各自的端点向中间延伸 这样浪 费的空间就会减少 但这种情况只有当两个栈的空间需求有相反的需求时 这种方法才有效 也就是说 最好一个栈增长 一个栈缩短 反之 如果 两个栈同时增长 则可能比较容易造成栈的溢出 如果多个顺序栈共享空 间 则可能需要大量的数据移动 造成时间的开销增大 而链式栈由于存 储的不连续性 一般不存在栈满的问题 所以一般不需要栈的共享 例 3 使用栈计算算术表达式值 算术表达式有三种表示方法 如 A B 称为中缀 infix 表示 如 AB 称为前缀 prefix 表示 如 AB 称为后缀 postfix 表示 中缀表达式 1 2 3 4 5 其对应的后缀表达式为 1234 5 习题 中缀表达式如下 写出后缀表达式 A B C D E F G H I J K 习题解答 ABCDEF G H IJ K 队列的定义 队列 Queue 也是一种运算受限的特殊线性表 其插入和删除操作分别在线 性表的两端进行 只允许在表的一端进行插入 而在另一端进行删除 允 许删除的一端称为队头 front 允许插入的一端称为队尾 rear 当队列中没有元素时称为空队列 在空队列中依次加入元素 a1 a2 an之后 a1是队头元素 an是队尾元素 显然退出队列的次序也只能是 a1 a2 an 也就是说队列的修改是依先进先出的原则进行的 例如 排队购物 先进入队列的成员总是先离开队列 因此队列亦称作先进先出 First In First Out 的线性表 简称 FIFO 表 队列的操作 一般情况下 入队 enqueue 操作又称为队列的插入 出队 dequeue 操作又称为队列的删除 队列的数据元素 队列的数据元素和线性表的数据元素完全相同 即队列的数据元素是 n n 0 个相同类型的数据元素 a0 a1 an 1组成的有限序列 记为 a0 a1 an 1 其中 n 为数据元素的个数 称为队列的长度 n 0 时 为空队列 队列的溢出 队列在顺序存储时 经常出现 假溢出假溢出 现象 解决 假溢出 现象的方 法有很多种 但通常采用循环队列方式存储 使用顺序表 出队效率低 因此不使用顺序表作为队列的成员变量 顺序循环队列 现在解决 假溢出 比较好的解决方案是使用循环向量 存储在循环向量 中的队列称为循环队列 Circular Quene 将顺序队列设计成在逻辑上首尾相接的循环结构 则可循环使用顺序队列 的连续存储单元 循环队列的操作 假设数组的空间是 m 只要在入 出队列时 将队首和队尾的指针对 m 做 求模运算即可实现队首和队为指针的循环 即队首和队尾指针的取值范围 是 0 到 m 1 之间 队空 front rear 队满 front rear 1 maxSize 或另外设一个标志以区别队空 队满 入队 rear rear 1 maxSize 出队 front front 1 maxSize 求队长 rear front maxSize maxSize 链式队列的基本概念 定义链队列的存储结构基本和线性表的定义相同 它是对链表实现的简单 化 队列的各种运算比链式存储的普通线性表运算实现时要方便得多 主要原 因是队列的各种运算只能在队列的两端操作 队列是特殊的线性表 我们只要考虑对线性表的两端操作的情况 并且只能一端插入 队首 另一端删除 队尾 而线性表除此之外 不限定一端插入 一端删除 还需要考虑中 间的结点的插入 删除 查询等操作 理解时 我们可以把队列的入 出队运算当作线性表两端进行插入 删除的特例即可 于是 一个链队列由头指针和尾指针唯一确定 使用单链表 入队效率低 单链表设计 增加尾指针 以不带头结点的单链表实现链式队列 队列的应用队列的应用 一 合并两个队列 一 合并两个队列 假设有两个队列 要求将两个队列合并到一起 合并时交替使用两 个队列中的元素 并把剩余的队列中的元素添加在最后 将产生的 新队列返回 二 模拟客户服务系统 二 模拟客户服务系统 三 三 主机与外部设备之间速度不匹配的问题 以主机和打印机为例来说明 主机输出数据给打印机打印 主机输 出数据的速度比打印机打印的速度要快得多 若直接把输出的数据 送给打印机打印 由于速度不匹配 显然是不行的 所以解决的方 法是设置一个打印数据缓冲区 主机把要打印输出的数据依此写如 到这个缓冲区中 写满后就暂停输出 继而去做其它的事情 打印 机就从缓冲区中按照先进先出的原则依次取出数据并打印 打印完 后再向主机发出请求 主机接到请求后再向缓冲区写入打印数据 这样利用队列既保证了打印数据的正确 又使主机提高了效率 第第 5 章章 数组和广义表数组和广义表 数组是数据结构的基本结构形式 它是一种顺序式的结构 数组是存储同一类型数 据的数据结构 数组是顺序存储的随机存取结构 数组是其他数据结构实现顺序存储的基础 使用数组时需要定义数组的大小和存储数据的数据类型 数组分为一维数组和多维数组 数组的维数是由数组下标的个数确定的 一个下标称为一维数组 一个下标以上的数组称为多维数组 从这个意义上讲 确定了对于数组的一个下标总有一个相应的数值与之对 应的关系 或者说数组是有限个同类型数据元素组成的序列 数组是二元组的一个集合 一维数组具有线性表的结构 但操作简单 一般不进行插入和删除操作 只定义给 定下标读取元素和修改元素的操作 声明的格式一般是 new 如 int element new int 5 一维数组的存储 一维数组的数据存储按照顺序存储 逻辑地址和物理地址都是连续 的 如果已知第一个数据元素的地址 loc a0 则第 i 个元素的地址 loc ai 为 Loc ai Loc a0 i c 数组分配内存空间的方式有 2 种 静态数组 声明时给出数组元素个数 当程序开始运行时 数组即获得系 统分配的一块地址连续的内存空间 静态数组所占用的内存空间由系统自 动管理 int 3 1 2 3 动态数组 声明时不指定数组长度 当程序运行中需要使用数组时 向系 统申请数组的存储单元空间 并给出数组长度 当数组使用完之后 需要 向系统归还所占用的内存空间 数组容量不够时 不能就地扩容 前面的做法是 申请一个更大容量的数组并进行 数组元素复制 在 Java 中 数组元素既可以简单数据类型 也可以是引用类型 而且 Java 中的数 组都是动态数组 多维数组 Multi Array 多维数组是指下标的个数有两个以上 我们比较常用的是二维数组 因为 三维以上的数组存储可以简化为二维数组的存储 多维数组是线性表的扩展 理解 二维数组是 元素为一维数组 的一维数组 二维数组的声明同一维数组 格式为 new size1 size2 如 int element new int 4 5 例如 设 A 是一个有 m 行 n 列的二维数组 则 A 可以表示为 在此 可以将二维数组 A 看成是由 m 个行向量 X0 X1 Xm 1 T组成 其中 Xi ai0 ai1 ain 1 0 i m 1 也可以将二维数组 A 看成是由 n 个列向量 y0 y1 yn 1 组成 其中 yi a0i a1i am 1i 0 i n 1 a0 0a0 1 a1 0a1 1 a0 ja0 n 1 a1 ja1 n 1 ai 0ai 1 am 1 0am 1 1 ai jai n 1 am 1 jam 1 n 1 行行 m 1 列列 jn 1 0 1 01 i ai j ai 1 j ai 1 j ai j 1ai j 1 列列前前驱驱列列后后继继 行行前前驱驱 行行后后继继 二维数组的遍历 行优先顺序 行主序 存储时先按行从小到大的顺序存储 在每 一行中按列号从小到大存储 列优先顺序 列主序 存储时先按列从小到大的顺序存储 在每 一列中按行号从小到大存储 二维数组的顺序存储结构 假设二维数组是 m n 的二维数组 共有 m 行 每行有 n 列 第一个数据 元素的地址是 loc a00 行主序 列主序 O 1 随机存取结构 例 数组 A 8 6 9 按行存放 设第一个元素的首地址是 54 每个元素的长度为 5 求 元素 A 2 4 5 的存储地址 Loc 2 4 5 54 5 6 2 9 4 9 5 799 但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下我们 可以对这类矩阵进行压缩存储 即为多个相同的非零元素只分配一个存储空间 对 零元素不分配空间 三角矩阵的压缩存储 以主对角线划分 三角矩阵有下三角和上三角两种 如图所示 在大多数情况下 三角矩 阵常数为零 1 下三角矩阵下三角矩阵 重复元素 c 可共享一个存储空间 其余的元素正好有 n n 1 2 个 因此 三角矩阵 可压缩存储到数组 element 0 n n 1 2 中 其中 c 存放在数组的最后一个元素中 1 线性压缩存储三角矩阵 2 上三角矩阵上三角矩阵 和下三角矩阵的存储类似 共需 n n 1 2 1 个存贮单元 假设仍按行优先顺序 存放 这时 s k 与 a i j 的对应关系为 cjniaLocaLoc ij 00 cimjaLocaLoc ij 00 1 1 1 22 2 1 12 111 1 02 00100 000 00 0 nn nnnn nn nn nn a aa aaa aaaa A njij ini a ijinnnaaij 0 2 12 Loc 1 1 Loc Loc 00 00 对称矩阵 如果用一维数组存储一个对称矩阵 只要将对称矩阵存储在一个最大下标为 n n 1 2 的一维数组 S 中即可 此时按照行优先顺序存储 数据元素 aij 与数组 S 的下标 k 的对应关系为 i i 1 2 j 当 i j k j j 1 2 i 当 i j 稀疏矩阵 Sparse Matrix 对稀疏矩阵很难下一个确切的定义 它只是一个凭人们的直觉来理解的概 念 一般认为 一个较大的矩阵中 零元素的个数相对于整个矩阵元素的 总个数所占比例较大时 该矩阵就是一个稀疏矩阵 稀疏矩阵 稀疏矩阵的压缩存储采用三元组的方法实现 其存储规则 每一个非零元素占有一行 每 行中包含非零元素所在的行号 列号 非零元素的数值 书 120 页 稀疏矩阵 如果每个非零元素按照此种方法存储 虽然能够完整地描述非零元素 但 如果矩阵中有整行 或整列 中没有非零元素 此时可能不能够还原成原 来的矩阵 所以为了完整地描述稀疏矩阵 在以上描述的情况下 如果增加一行的内 容 该行包括矩阵的总的行数 矩阵的总的列数 矩阵中非零元素的个数 就可以还原为原来的矩阵描述了 三元组顺序表类 public class SeqMatrix int rows columns 行数 列数 SortedSeqList list 排序顺序表 public int get int i int j 返回第 i 行第 j 列的元素 if i rows j columns throw new IndexOutOfBoundsException outofBound Triple item new Triple i j 0 int k 0 1 12 11 10 1 1 22 21 20 2 1 12 11 10 1 1 02 01 00 0 nnnnnn nnnnnn nn nn nn aaaa aaaa aaaa aaaa A njii jj a nijj ii a a ji 0 2 1 Loc 0 2 1 Loc Loc 0 0 0 0 Triple elem this list get k while k 0 if pareTo elem 0 return elem value k return 0 public void set int row int column int value if value 0 return if row this rows column this columns throw new IllegalArgumentException outofBound Triple elem new Triple row column value int i 0 while i 0 i else break this list insert i elem 不存在该元素 将新元素插入 广义表的定义 广义表是线性表的扩展 具体定义为 n n 0 个元素的有限集合 其中元素有以下两种 类型 1 一个原子元素 指不可再分的元素 2 一个可以再分的元素 或称为一个子表 如果所有元素都是原子元素 则称为线性表 如果含有子表则是广义表 n 的值是广义表 的长度 如果 n 0 称为空表 广义表定义 矩矩阵阵 三三角角矩矩阵阵 三三元元组组顺顺序序表表 排排序序 二二维维数数组组矩矩阵阵 特特殊殊矩矩阵阵 零零元元素素分分布布规规律律 不不存存储储分分布布规规律律的的零零元元素素 对对称称矩矩阵阵 线线性性压压缩缩 存存储储非非零零 元元素素区区域域 稀稀疏疏矩矩阵阵 零零元元素素分分布布不不规规律律 不不存存储储零零元元素素 三三元元组组行行的的单单链链表表 排排序序 三三元元组组十十字字链链表表 排排序序 三三元元组组单单链链表表 排排序序 一一维维数数组组 三三角角形形的的二二维维数数组组 对对角角矩矩阵阵 GList a0 a1 an 1 中国 北京 上海 江苏 南京 苏州 浙江 杭州 广东 广州 L a b 线性表 长度为 2 深度为 1 T c L c a b L 为 T 的子表 T 的长度为 2 深度为 2 G d L T d a b c a b L T 为 G 的子表 G 的长度为 3 深度为 3 S 空表 长度为 0 深度为 1 S1 S 元素是一个空表 长度为 1 深度为 2 Z e Z e e e 递归表 Z 的长度为 2 深度无穷 广义表的特性 1 线性结构 3 可共享 2 多层次结构 有深度 4 可递归 广义表的三个重要结论 列表的元素可以是子表 而子表的元素还可以是子表 由此 列表是一 个多层次的结构 可以用图形象地表示 广义表的存储方法有很多种 一般采用链表存储 第第 6 章章 树和二叉树树和二叉树 树结构是一类重要的非线性结构 树结构是结点之间有分支 并且具有层次关系的结构 它非常类似于自然界中的树 树定义 树 Tree 是由 n n 0 个结点组成的有限集合 n 0 的树称为空树 n 0 的 树由以下两个条件约定构成 1 有且仅有一个特殊的称为根 Root 的结点 它只有后继结点 没有前驱结点 2 其余的结点可分为 m n m 0 个互不相交的子集 T0 T1 T2 Tm 1 其中 每个子集又是一棵树 并称其为子树 Subtree 以上定义中 结点的双亲结点或父母结点 parent 结点上面的相邻结点 或指结点 的前驱结点 结点 n 的孩子结点 child 任何一个以 n 作为双亲结点的结点 或指结 点 n 的后继结点 树的根 root 有且仅有的一个特定的结点 它没有双亲结点 结点 n 的祖先结点 ancestor 包括 n 的双亲结点 n 的双亲结点的双 亲结点 等等 即指从根结点到其父母结点所经过的所有结点 根是树中所有结点的公共祖先结点 结点 n 的子孙 后代 结点 descendant 任何一个以 n 作为祖先结点 的结点 即指结点的所有孩子结点 以及孩子的孩子等 兄弟结点 sibling 如果结点 m 和 n 共有一个双亲结点 则称 m 和 n 为 兄弟结点 叶子结点 终端结点 leaf 没有孩子结点的结点 分支结点 非终端结点 叶子结点之外的结点称为分支结点或者非终端 结点 子树 subtree 在树 T 中 n 的子孙结点组成了以 n 作为根的 T 的子树 结点 n 的度 degree of node n 的孩子结点的数量 树的度 degree of a tree 树中所有结点的最大度数 结点 n 的层次 level 结点 n 所处的树中的层次位置 可以假设根的层 次是 0 或 1 本书中所有都假设根的层次为 1 其他结点的层次是其父母结 点的层次加 1 树的高度 heigh 或深度 depth 树中结点的最大层次数 边 edge 设树中 X 结点是 Y 结点的父母结点 有序对 X Y 称为连 接这两个结点的分支 也称为边 路径 path 从一个结点 n 到另一个结点的边序列 路径长度 length 路径中涉及到边的数量 若把树中每个结点的各子树看成从左到右有次序的 即不能互换 则称该 树为有序树 Ordered Tree 否则称为无序树 Unordered Tree 森林 forest m 棵互不相交的树的集合 如 T0 T1 T2 Tm 1 但可能 为空 二叉树定义 二叉树是 n 个结点的有限集合 n 0 时 为空二叉树 n 0 时 由一个根结点 两棵互不相交的左子树和右子树的子二叉树组成 二叉树结点的子树要区分左子树和右子树 即使只有一棵子树也要进行区 分 说明它是左子树 还是右子树 这是二叉树与树的最主要的差别 二叉树结点的子树要区分左子树和右子树 即使只有一棵子树也要进行区分 说明 它是左子树 还是右子树 这是二叉树与树的最主要的差别 二叉树具有下列重要性质 性质 1 若根结点的层次为 1 则二叉树第 i 层最多有 2i 1 i 1 个结点 性质 2 在高度为 h 的二叉树中 最多有 2h 1 个结点 h 0 性质 3 设一棵二叉树的叶子结点数为 n0 2 度结点数为 n2 则 n0 n2 1 性质 3 设二叉树结点个数为 n 1 度结点个数为 n1 则 n n0 n1 n2 且 n n1 2 n2 1 满二叉树 full binary tree 一棵高度为 h 且有 2h 1 h 0 个结点的二叉树称为 满二叉树 以下说法是否正确 二叉树中所有非叶结点的度数都为 2 的二叉树 一个高度为 h 的满二叉树中 只在 h 层有叶结点 而且每一个非叶子结点 都是满的 完全二叉树 complete binary tree 删除高度为 h 的满二叉树中第 h 层的 0 个或 多个最右边叶结点的树 如果深度为 h 由 n 个结点的二叉树中每个结点能够与深度为 h 的顺序编 号的满二叉树从 1 到 n 标号的结点相对应 则称这样的二叉树为完全二叉 树 满二叉树是完全二叉树的特例 完全二叉树的特点是 在 h 层二叉树中 所有的叶结点都出现在第 h 层或 h 1 层 对任一结点 如果其右子树的最大层次为 h 则其左子树的最大层次为 h 或 h 1 性质 4 一棵具有 n 个结点的完全二叉树 其高度为 因为 2h 1 1 n 0 则 i 的父母结点序号为 i 1 2 若 2i 1 n 则 i 的左孩子结点在 2i 1 否则 i 无左孩子 若 2i 2 n 则 i 的右孩子结点在 2i 2 否则 i 无右孩子 先根次序 访问根结点 遍历左子树 遍历右子树 中根次序 遍历左子树 访问根结点 遍历右子树 后根次序 遍历左子树 遍历右子树 访问根结点 顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素 顺序存储结构的特点 存储单元仅仅存储结点的值 二叉树结点之间的逻辑关系由数组中下标的顺序来体现 不管给定的二叉树是不是完全二叉树 都看作完全二叉树 即按完全二叉树的层次 次序 从上到下 从左到右 把各结点依次存入数组中 对于一棵二叉树 若采用顺序存贮时 当它为完全二叉树时 比较方便 若为非完全二叉 树 将会浪费大量存贮存贮单元 最坏的非完全二叉树是全部只有右分支 设高度为 K 则需占用 2K 1 个存贮单元 而实 际只有 k 个元素 实际只需 k 个存储单元 因此 对于非完全二叉树 宜采用下面的链式存储结构链式存储结构 链式存储结构 由二叉树的定义可知 二叉树的结点由一个数据元素和两个分别指向其左 右子树的两个分支构成 所以二叉树的结点包括两个部分 数据域 左 右指针域 有时候为了方便找到该结点的双亲还会在设置一个指针域指向其双亲结点 若一棵二叉树有 n 个结点 采用二叉链表作存贮结构时 共有 2n 个指针域 其 中只有 n 1 个指针指向左右孩子 其余 n 1 个指针为空 没有发挥作用 被白白 浪费掉了 二叉树的遍历指的是沿某条搜索路径访问二叉树 对二叉树中的每个结点访问一次 且仅一次 这里的 访问 实际上指的是对结点进行某种操作 二叉树的遍历方法 先根遍历 中根遍历 后根遍历 层次遍历 求结点个数 public int size 返回二叉树的结点 数 return size root public int size BinaryNode p 返回以 p 结点为根的子树的结点数 if p null return 0 return 1 size p left size p right 求高度 必须采用后跟次序遍历算法 只有先分别计算出左 右子树高度的情况下 才能计算当前子树高度 public int height 返回二叉树的高度 return height root public int height BinaryNode p 返回以 p 结点为根的子树高度 后根 次序遍历 if p null return 0 int lh height p left 返回左子树的高度 int rh height p right 返回右子树的高度 return lh rh lh 1 rh 1 当前子树高度为较高子树的高度加 1 public BinaryNode searchNode T key 查找并返回首次出现的关键字为 key 元素结点 return searchNode root key 在以 p 为根的子树中查找并返回首次出现的关键字为 key 元素结点 若未找到返回 null 先根次序遍历 public BinaryNode searchNode BinaryNode p T key if p null key null return null if p data equals key return p 查找成功 返回找到结点 BinaryNode find searchNode p left key 在左子树中查找 if find null 若在左子树中未找到 find searchNode p right key 则继续在右子树中查找 return find 返回查找结果 返回 node 结点的父母结点 若空树 未找到或 node 为根 则返回 null public BinaryNode getParent BinaryNode node if root null node null node root return null return getParent root node 在以 p 为根的子树中查找并返回 node 结点的父母结点 public BinaryNode getParent BinaryNode p BinaryNode node if p null return null if p left node p right node return p BinaryNode find getParent p left node if find null find getParent p right node return find 构造一棵二叉树必须明确以下两种关系 结点与其双亲结点及孩子结点间的层次关系 兄弟结点间左或右的次序关系 关系的确定 先根遍历和后跟遍历反映双亲与孩子结点之间的层次关系 中跟遍历反映兄弟结点之间的左右关系 总之 由二叉树的一种遍历序列不能唯一确定一颗二叉树 书上介绍的建立二叉树的方法 1 按先根和中根次序遍历序列建立二叉树 以先根和中根序列创建一棵子树 子树根结点值是 prelist preStart n 指定子序 列长度 返回所创建子树的根结点 private BinaryNode create T prelist T inlist int preStart int inStart int n if n 0 return null T elem prelist preStart 根结点值 BinaryNode p new BinaryNode elem 创建叶子结点 int i 0 while i n p le