数组和广义表07869

2020年4月6日星期一 第五章数组和广义表 2020年4月6日星期一 课前思考 在学习了C语言之后 同学们可能会误认为 数组 是一组地址连续的内存 数组也是一种线性的数据结构 它可以看成是线性表的一种扩充 因为在高级编程语言中实现的一维数组正是用的这种顺序存储的映象方式 2020年4月6日星期一 学习目标 1 理解数组类型的特点及其在高级编程语言中的存储表示和实现方法 并掌握数组在 以行为主 的存储表示中的地址计算方法 2 掌握特殊矩阵的存储压缩表示方法 3 理解稀疏矩阵的两类存储压缩方法的特点及其适用范围 领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法 4 掌握广义表的结构特点及其存储表示方法 2020年4月6日星期一 重点和难点 本章重点是学习数组类型的定义及其存储表示 知识点 数组的类型定义 数组的存储表示 特殊矩阵的压缩存储表示方法 随机稀疏矩阵的压缩存储表示方法 广义表的类型定义 广义表的存储表示 广义表操作的实现 2020年4月6日星期一 学习指南 从学习利用高级语言编制程序开始 数组是大家惯用的存储批量数据的工具 前几章讨论的线性结构的顺序存储结构也都是利用数组来描述的 那么数组本身又是怎么实现的呢 因此本章的学习目的主要是了解数组类型的特点以及在高级编程语言中的实现方法 对于本章讨论的随机稀疏矩阵运算的各个算法主要是理解问题的处理方法 由于广义表本属线性类型的数据结构 它和数组类似 每个数据元素本身又可以是一个数据结构 因此在教材中和 数组 合为一章 但由于广义表比数组更为复杂 它兼有 多层次 的特点 特别是它的存储表示和操作的实现和树的操作极为类似 因此在本章的学习中应善于和第六章的内容相对照 反之通过本章的学习恰好是对实现树操作的递归算法的复习和巩固 本章算法设计题 完成5 21 5 23 2020年4月6日星期一 5 1数组的类型定义 5 3稀疏矩阵的压缩存储 5 2数组的顺序表示和实现 5 4广义表的类型定义 5 5广义表的存储结构 5 6广义表操作的递归函数 2020年4月6日星期一 一 数组的概念 1 一维数组 一维数组可以看成是一个线性表或一个向量 第二章已经介绍 它在计算机内是存放在一块连续的存储单元中 适合于随机查找 这在第二章的线性表的顺序存储结构中已经介绍 2 二维数组 二维数组可以看成是向量的推广 5 1数组的定义 2020年4月6日星期一 例如 设A是一个有m行n列的二维数组 则A可以表示为 在此 可以将二维数组A看成是由n个列向量A 1 2 n 组成 其中 i a1i a2i ami 0 i n 图5 2 也可以将二维数组A看成是由m个行向量B 1 2 m T组成 其中 i ai1 ai2 ain 0 i m 图5 3 图5 1Am n的二维数组 2020年4月6日星期一 图5 2矩阵Am n看成n个列向量的线性表 2020年4月6日星期一 图5 3矩阵Am n看成m个行向量的线性表 由此可知二维数组中的每一个元素最多可有二个直接前驱和两个直接后继 边界除外 故是一种典型的非线性结构 2020年4月6日星期一 以上我们以二维数组为例介绍了数组的结构特性 实际上数组是一组有固定个数的元素的集合 也就是说 一旦定义了数组的维数和每一维的上下限 数组中元素的个数就固定了 例如二维数组A3 4 它有3行 4列 即由12个元素组成 由于这个性质 使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入或删除一个元素 对于数组的操作一般只有两类 1 获得特定位置的元素值 2 修改特定位置的元素值 3 多维数组同理 三维数组最多可有三个直接前驱和三个直接后继 三维以上数组可以作类似分析 因此 可以把三维以上的数组称为多维数组 多维数组可有多个直接前驱和多个直接后继 故多维数组是一种非线性结构 2020年4月6日星期一 数组的抽象类型定义 ADTArray 数据对象 D aj1 j2 ji jn ji 0 bi 1 i 1 2 n 数据关系 R R1 R2 Rn Ri 0 jk bk 1 1 k n且k i 0 ji bi 2 i 2 n ADTArray 基本操作 2020年4月6日星期一 二维数组的定义 数据对象 D aij 0 i b1 1 0 j b2 1 数据关系 R ROW COL ROW 0 i b1 2 0 j b2 1 COL 0 i b1 1 0 j b2 2 2020年4月6日星期一 基本操作 InitArray A n bound1 boundn DestroyArray A Value A e index1 indexn Assign A e index1 indexn 2020年4月6日星期一 InitArray A n bound1 boundn 操作结果 若维数n和各维长度合法 则构造相应的数组A 并返回OK 2020年4月6日星期一 DestroyArray A 操作结果 销毁数组A 2020年4月6日星期一 Value A e index1 indexn 初始条件 A是n维数组 e为元素变量 随后是n个下标值 操作结果 若各下标不超界 则e赋值为所指定的A的元素值 并返回OK 2020年4月6日星期一 Assign A e index1 indexn 初始条件 A是n维数组 e为元素变量 随后是n个下标值 操作结果 若下标不超界 则将e的值赋给所指定的A的元素 并返回OK 2020年4月6日星期一 5 2数组的顺序表示和实现 由于数组一般不作插入或删除操作 也就是说 一旦建立了数组 则结构中的数组元素个数和元素之间的关系就不再发生变动 即它们的逻辑结构就固定下来了 不再发生变化 因此 采用顺序存储结构表示数组是顺理成章的事了 本章中 仅重点讨论二维数组的存储 三维及三维以上的数组可以作类似分析 怎样将多维数组中元素存入到计算机内存中呢 由于计算机内存结构是一维的 线性的 因此 用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列 然后将这个线性序列顺序存放在存储器中 2020年4月6日星期一 一 行优先顺序 1 存放规则 行优先顺序也称为低下标优先或左边下标优先于右边下标 具体实现时 按行号从小到大的顺序 先将第一行中元素全部存放好 再存放第二行元素 第三行元素 依次类推 在BASIC语言 PASCAL语言 C C 语言等高级语言程序设计中 都是按行优先顺序存放的 例如 对刚才的Am n二维数组 可用如下形式存放到内存 a00 a01 a0n 1 a10 a11 a1n 1 am 10 am 11 am 1n 1 即二维数组按行优先存放到内存后 变成了一个线性序列 线性表 数组的顺序存储结构有两种 一种是按行序存储 如高级语言BASIC COBOL和PASCAL语言都是以行序为主 另一种是按列序存储 如高级语言中的FORTRAN语言就是以列序为主显然 2020年4月6日星期一 因此 可以得出多维数组按行优先存放到内存的规律 最左边下标变化最慢 最右边下标变化最快 右边下标变化一遍 与之相邻的左边下标才变化一次 因此 在算法中 最左边下标可以看成是外循环 最右边下标可以看成是最内循环 2 地址计算 由于多维数组在内存中排列成一个线性序列 因此 若知道第一个元素的内存地址 如何求得其它元素的内存地址 我们可以将它们的地址排列看成是一个等差数列 假设每个元素占l个字节 元素aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的单元数 而aij的前面有i行 0 i 1 共i n个元素 而本行前面又有j个元素 故aij的前面一共有i n j个元素 设a00的内存地址为LOC a00 则aij的内存地址按等差数列计算为LOC aij LOC a00 i n j l 同理 三维数组Am n p按行优先存放的地址计算公式为 LOC aijk LOC a000 i n p j p k l 2020年4月6日星期一 二 列优先顺序 1 存放规则 列优先顺序也称为高下标优先或右边下标优先于左边下标 具体实现时 按列号从小到大的顺序 先将第一列中元素全部存放好 再存放第二列元素 第三列元素 依次类推 在FORTRAN语言程序设计中 数组是按列优先顺序存放的 例如 对前面提到的Am n二维数组 可以按如下的形式存放到内存 a00 a10 am 10 a01 a11 am 11 a0m 1 a1m 1 am 1n 1 即二维数组按列优先存放到内存后 也变成了一个线性序列 线性表 2020年4月6日星期一 因此 可以得出多维数组按列优先存放到内存的规律 最右边下标变化最慢 最左边下标变化最快 左边下标变化一遍 与之相邻的右边下标才变化一次 因此 在算法中 最右边下标可以看成是外循环 最左边下标可以看成是最内循环 2 地址计算 同样与行优先存放类似 若知道第一个元素的内存地址 则同样可以求得按列优存放的某一元素aij的地址 对二维数组有 LOC aij LOC a00 j m i l对三维数组有 LOC aijk LOC a000 k m n j m i l 2020年4月6日星期一 三 3维数组存储实例假设有一个3 4 2的三维数组A 共有24个元素 其逻辑结构如图5 4所示 图5 4三维数组的逻辑结构图 2020年4月6日星期一 三维数组元素的标号由三个数字表示 即行 列 纵三个方向 a142表示第1行 第4列 第2纵的元素 如果对A3 4 2 下标从1开始 采用以行为主序的方法存放 即行下标变化最慢 纵下标变化最快 则顺序为 a111 a112 a121 a122 a331 a332 a341 a342 采用以列为主序的方法存放 即纵下标变化最慢 行下标变化最快 则顺序为 a111 a211 a311 a121 a221 a321 a132 a232 a332 a142 a242 a342 2020年4月6日星期一 以上的存放规则可推广到多维数组的情况 总之 知道了多维数组的维数 以及每维的上下界 就可以方便地将多维数组按顺序存储结构存放在计算机中了 同时 根据数组的下标 可以计算出其在存储器中的位置 因此 数组的顺序存储是一种随机存取的结构 四 多维数组地址计算以二维数组Am n为例 假设每个元素只占一个存储单元 以行为主 存放数组 下标从1开始 首元素a11的地址为Loc 1 1 求任意元素aij的地址 aij是排在第i行 第j列 并且前面的第i 1行有n i 1 个元素 第 行第j个元素前面还有 个元素 由此得到如下地址计算公式 Loc i j Loc 1 1 n i 1 j 1 2020年4月6日星期一 根据计算公式 可以方便地求得aij的地址是Loc i j 如果每个元素占size个存储单元 则任意元素aij的地址计算公式为 Loc i j Loc 1 1 n i 1 j 1 size 三维数组A 1 r 1 m 1 n 可以看成是r个m n的二维数组 如图5 5所示 图5 5三维数组看成r个m n的二维数组 2020年4月6日星期一 假定每个元素占一个存储单元 采用以行为主序的方法存放 即行下标r变化最慢 纵下标n变化最快 首元素a111的地址为Loc 1 1 1 求任意元素aijk的地址 显然 ai11的地址为Loc i 1 1 Loc 1 1 1 i 1 m n 因为在该元素之前 有 个 的二维数组 由ai11的地址和二维数组的地址计算公式 不难得到三维数组任意元素aijk的地址 Loc i j k Loc 1 1 1 i 1 m n j 1 n k 1 其中1 i 1 j 1 k 2020年4月6日星期一 如果将三维数组推广到一般情况 即 用j1 j2 j3代替数组下标i j k 并且j1 j2 j3的下限为c1 c2 c3 上限分别为d1 d2 d3 每个元素占一个存储单元 则三维数组中任意元素a j1 j2 j3 的地址为 Loc j1 j2 j3 Loc c1 c2 c3 l d2 c2 1 d3 c3 1 j1 c1 l d3 c3 1 j2 c2 l j3 c3 其中l为每个元素所占存储单元数 令 1 l d2 c2 1 d3 c3 1 2 l d3 c3 1 3 1 则 Loc j1 j2 j3 Loc c1 c2 c3 1 j1 c1 2 j2 c2 3 j3 c3 Loc c1 c2 c3 i ji ci 1 i 3 2020年4月6日星期一 由公式可知Loc j1 j2 j3 与j1 j2 j3呈线性关系 对于 维数组A c1 d1 c2 d2 cn dn 我们只要把上式推广 就可以容易地得到 维数组中任意元素aj1j2 jn的存储地址的计算公式 其中 1 i n 2020年4月6日星期一 假设m行n列的矩阵含t个非零元素 则称为稀疏因子 通常认为 0 05的矩阵为稀疏矩阵 5 3稀疏矩阵的压缩存储 何谓稀疏矩阵 2020年4月6日星期一 以常规方法 即以二维数组表示高阶的稀疏矩阵时产生的问题 1 零值元素占了很大空间 2 计算中进行了很多和零值的运算 遇除法 还需判别除数是否为零 2020年4月6日星期一 1 尽可能少存或不存零值元素 解决问题的原则 2 尽可能减少没有实际意义的运算 3 操作方便 即 能尽可能快地找到与下标值 i j 对应的元素 能尽可能快地找到同一行或同一列的非零值元 2020年4月6日星期一 1 特殊矩阵非零元在矩阵中的分布有一定规则例如 三角矩阵对角矩阵 2 随机稀疏矩阵非零元在矩阵中随机出现 有两类稀疏矩阵 2020年4月6日星期一 随机稀疏矩阵的压缩存储方法 一 三元组顺序表 二 行逻辑联接的顺序表 三 十字链表 2020年4月6日星期一 defineMAXSIZE12500typedefstruct inti j 该非零元的行下标和列下标ElemTypee 该非零元的值 Triple 三元组类型 一 三元组顺序表 typedefunion Tripledata MAXSIZE 1 intmu nu tu TSMatrix 稀疏矩阵类型 2020年4月6日星期一 如何求转置矩阵 2020年4月6日星期一 用常规的二维数组表示时的算法 其时间复杂度为 O mu nu for col 1 col nu col for row 1 row mu row T col row M row col 2020年4月6日星期一 用 三元组 表示时如何实现 1214 15 5 22 7 3136 3428 2114 51 5 22 7 1336 4328 2020年4月6日星期一 首先应该确定每一行的第一个非零元在三元组中的位置 cpot 1 1 for col 2 col M nu col cpot col cpot col 1 num col 1 2020年4月6日星期一 StatusFastTransposeSMatrix TSMatrixM TSMatrix FastTransposeSMatrix 转置矩阵元素 2020年4月6日星期一 Col M data p j q cpot col T data q i M data p j T data q j M data p i T data q e M data p e cpot col 2020年4月6日星期一 分析算法FastTransposeSMatrix的时间复杂度 时间复杂度为 O M nu M tu for col 1 col M nu col for t 1 t M tu t for col 2 col M nu col for p 1 p M tu p 2020年4月6日星期一 三元组顺序表又称有序的双下标法 它的特点是 非零元在表中按行序有序存储 因此便于进行依行顺序处理的矩阵运算 然而 若需随机存取某一行中的非零元 则需从头开始进行查找 二 行逻辑联接的顺序表 2020年4月6日星期一 defineMAXMN500typedefstruct Tripledata MAXSIZE 1 intrpos MAXMN 1 intmu nu tu RLSMatrix 行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义 增加一个数据成员rpos 其值在稀疏矩阵的初始化函数中确定 2020年4月6日星期一 例如 给定一组下标 求矩阵的元素值 ElemTypevalue RLSMatrixM intr intc p M rpos r while M data p i r value 2020年4月6日星期一 矩阵乘法的精典算法 for i 1 i m1 i for j 1 j n2 j Q i j 0 for k 1 k n1 k Q i j M i k N k j 其时间复杂度为 O m1 n2 n1 2020年4月6日星期一 Q初始化 ifQ是非零矩阵 逐行求积for arow 1 arow M mu arow 处理M的每一行ctemp 0 累加器清零计算Q中第arow行的积并存入ctemp 中 将ctemp 中非零元压缩存储到Q data forarow if 两个稀疏矩阵相乘 Q M N 的过程可大致描述如下 2020年4月6日星期一 StatusMultSMatrix RLSMatrixM RLSMatrixN RLSMatrix MultSMatrix 2020年4月6日星期一 ctemp 0 当前行各元素累加器清零Q rpos arow Q tu 1 for p M rpos arow pMAXSIZE returnERROR Q data Q tu arow ccol ctemp ccol if 处理的每一行 M 2020年4月6日星期一 分析上述算法的时间复杂度 累加器ctemp初始化的时间复杂度为 M mu N nu 求Q的所有非零元的时间复杂度为 M tu N tu N mu 进行压缩存储的时间复杂度为 M mu N nu 总的时间复杂度就是 M mu N nu M tu N tu N mu 若M是m行n列的稀疏矩阵 N是n行p列的稀疏矩阵 则M中非零元的个数M tu M m n N中非零元的个数N tu N n p 相乘算法的时间复杂度就是 m p 1 n M N 当 M 0 05和 N 0 05及n 1000时 相乘算法的时间复杂度就相当于 m p 2020年4月6日星期一 三 十字链表 30050 1002000 1 1 3 1 4 5 2 2 1 3 1 2 2020年4月6日星期一 5 4广义表的类型定义 ADTGlist 数据对象 D ei i 1 2 n n 0 ei AtomSet或ei GList AtomSet为某个数据对象 数据关系 LR ei 1 ei D 2 i n ADTGlist 基本操作 广义表 顾名思义 也是线性表的一种推广 广义表被广泛地应用于人工智能等领域的表处理语言LISP语言中 在LISP语言中 广义表是一种最基本的数据结构 就连LISP语言的程序也表示为一系列的广义表 2020年4月6日星期一 广义表是递归定义的线性结构 LS 1 2 n 其中 i或为原子或为广义表 例如 A F d e D a b c F C A D F B a B a a a 2020年4月6日星期一 广义表是一个多层次的线性结构 例如 D E F 其中 E a b c F d e D E F a d b c e 2020年4月6日星期一 广义表LS 1 2 n 的结构特点 1 广义表中的数据元素有相对次序 2 广义表的长度定义为最外层包含元素个数 3 广义表的深度定义为所含括弧的重数 注意 原子 的深度为0 空表 的深度为1 4 广义表可以共享 5 广义表可以是一个递归的表 递归表的深度是无穷值 长度是有限值 2020年4月6日星期一 6 任何一个非空广义表LS 1 2 n 均可分解为表头Head LS 1和表尾Tail LS 2 n 两部分 例如 D E F a b c F Head D ETail D F Head E aTail E b c Head b c b c Tail b c Head b c bTail b c c Head c cTail c 2020年4月6日星期一 结构的创建和销毁InitGList 基本操作 状态函数GListLength L GListDepth L GListEmpty L GetHead L GetTail L 插入和删除操作InsertFirst GL 遍历Traverse GL L Visit 2020年4月6日星期一 由于广义表LS a1 a2 a3 an 中的数据元素既可以是单个元素 也可以是子表 因此对于广义表来说 我们难以用顺序存储结构来表示它 通常我们用链式存储结构来表示 表中的每个元素可用一个结点来表示 广义表中有两类结点 一类是单个元素结点 另一类是子表结点 任何一个非空的广义表都可以分解成表头和表尾两部分 反之 一对确定的表头和表尾可以唯一地确定一个广义表 由此 一个表结点可由三个域构成 标志域 指向表头的指针域和指向表尾的指针域 而元素结点只需要两个域 标志域和值域 方法一 5 5广义表的存储结构 2020年4月6日星期一 广义表的头尾链表存储结构 typedefenum ATOM LIST ElemTag ATOM 0 原子 LIST 1 子表 typedefstructGLNode ElemTagtag 标志位tag用来区别原子结点和表结点 union AtomTypeatom 原子结点的值域atom struct structGLNode hp tp ptr 表结点的指针域ptr 包括表头指针域hp和表尾指针域tp 原子结点的值域atom和表结点的指针域htp的联合体域 GList 表结点 原子结点 2020年4月6日星期一 图广义表A B C D的存储结构 存储实例 D A a b c B A A D C a C 2020年4月6日星期一 图广义表的另一种结点结构 表结点 原子结点 方法二 在上述存储方法中 1 除空表的表头指针为空外 任何非空列表的表头指针均指向一个表结点 且该结点的hp域指示列表的表头 tp域指示列表的表尾 2 容易分清列表中的原子和子表所在的层次 3 最高层的表结点数即为列表的长度 2020年4月6日星期一 图广义表的第二种存储结构 D A a b c B A A D C a C 2020年4月6日星期一 这种存储结构的形式说明如下 typedefenum ATOM LIST ElemTag ATOM 0 表示原子 LIST 1 表示子表 typedefstructGLNode ElemTagtag union AtomTypeatom structGLNode hp 原子结点的值域atom和表结点的表头指针域hp的联合体域 structGLNode tp GList 2020年4月6日星期一 5 6广义表操作的递归函数 递归函数一个含直接或间接调用本函数语句的函数被称之为递归函数 它必须满足以下两个条件 1 在每一次调用自己时 必须是 在某种意义上 更接近于解 2 必须有一个终止处理或计算的准则 2020年4月6日星期一 例如 梵塔的递归函数 voidhanoi intn charx chary charz if n 1 move x 1 z else hanoi n 1 x z y move x n z hanoi n 1 y x z 2020年4月6日星期一 二叉树的遍历 voidPreOrderTraverse BiTreeT void Visit BiTreeP if T Visit T data PreOrderTraverse T lchild Visit PreOrderTraverse T rchild Visit PreOrderTraverse 2020年4月6日星期一 一 分治法 DivideandConquer 又称分割求解法 如何设计递归函数 二 后置递归法 Postponingthework 三 回溯法 Backtracking 2020年4月6日星期一 对于一个输入规模为n的函数或问题 用某种方法把输入分割成k 1 k n 个子集 从而产生l个子问题 分别求解这l个问题 得出l个问题的子解 再用某种方法把它们组合成原来问题的解 若子问题还相当大 则可以反复使用分治法 直至最后所分得的子问题足够小 以至可以直接求解为止 分治法的设计思想为 2020年4月6日星期一 在利用分治法求解时 所得子问题的类型常常和原问题相同 因而很自然地导致递归求解 2020年4月6日星期一 例如 梵塔问题 Hanoi n x y z 可递归求解Hanoi n 1 x z y 将n个盘分成两个子集 1至n 1和n 从而产生下列三个子问题 1 将1至n 1号盘从x轴移动至y轴 3 将1至n 1号盘从y轴移动至z轴 2 将n号盘从x轴移动至z轴 可递归求解Hanoi n 1 x z y 2020年4月6日星期一 又如 遍历二叉树 Traverse BT 可递归求解Traverse LBT 将n个结点分成三个子集 根结点 左子树和右子树 从而产生下列三个子问题 1 访问根结点 3 遍历右子树 2 遍历左子树 可递归求解Traverse RBT 2020年4月6日星期一 广义表从结构上可以分解成 广义表 表头 表尾 或者 广义表 子表1 子表2 子表n 因此常利用分治法求解之 算法设计中的关键问题是 如何将l个子问题的解组合成原问题的解 2020年4月6日星期一 广义表的头尾链表存储表示 typedefenum ATOM LIST ElemTag ATOM 0 原子 LIST 1 子表typedefstructGLNode ElemTagtag 标志域union AtomTypeatom 原子结点的数据域struct structGLNode hp tp ptr GList tag 1 hptp ptr 表结点 2020年4月6日星期一 例一求广义表的深度 例二复制广义表 例三创建广义表的存储结构 2020年4月6日星期一 广义表的深度 Max 子表的深度 1 例一求广义表的深度 可以直接求解的两种简单情况为 空表的深度 1原子的深度 0 将广义表分解成n个子表 分别 递归 求得每个子表的深度 2020年4月6日星期一 intGlistDepth GlistL 返回指针L所指的广义表的深度for max 0 pp L pp pp pp ptr tp dep GlistDepth pp ptr hp if dep max max dep returnmax 1 GlistDepth if L return1 if L tag ATOM return0 2020年4月6日星期一 1 1 1 L for max 0 pp L pp pp pp ptr tp dep GlistDepth pp ptr hp if dep max max dep 例如 pp pp ptr hp pp pp pp ptr hp pp ptr hp 2020年4月6日星期一 例二复制广义表 新的广义表由新的表头和表尾构成 可以直接求解的两种简单情况为 空表复制求得的新表自然也是空表 原子结点可以直接复制求得 将广义表分解成表头和表尾两部分 分别 递归 复制求得新的表头和表尾 2020年4月6日星期一 若ls NIL则newls NIL否则构造结点newls 由表头ls ptr hp复制得newhp由表尾ls ptr tp复制得newtp并使newls ptr hp newhp newls ptr tp newtp 复制求广义表的算法描述如下 2020年4月6日星期一 StatusCopyGList Glist CopyGList 分别复制表头和表尾 2020年4月6日星期一 CopyGList T ptr hp L ptr hp 复制求得表头T ptr hp的一个副本L ptr hpCopyGList T ptr tp L ptr tp 复制求得表尾T ptr tp的一个副本L ptr tp 语句CopyGList T ptr hp L ptr hp 等价于CopyGList newhp L ptr tp T ptr hp newhp 2020年4月6日星期一 例三创建广义表的存储结构 对应广义表的不同定义方法相应地有不同的创建存储结构的算法 2020年4月6日星期一 假设以字符串S 1 2 n 的形式定义广义表L 建立相应的存储结构 由于S中的每个子串 i定义L的一个子表 从而产生n个子问题 即分别由这n个子串 递归 建立n个子表 再组合成一个广义表 可以直接求解的两种简单情况为 由串 建立的广义表是空表 由单字符建立的子表只是一个原子结点 2020年4月6日星期一 如何由子表组合成一个广义表 首先分析广义表和子表在存储结构中的关系 先看第一个子表和广义表的关系 1 L 指向广义表的头指针 指向第一个子表的头指针 2020年4月6日星期一 再看相邻两个子表之间的关系 1 1 指向第i 1个子表的头指针 指向第i个子表的头指针 可见 两者之间通过表结点相链接 2020年4月6日星期一 若S 则L NIL 否则 构造第一个表结点 L 并从串S中分解出第一个子串 1 对应创建第一个子广义表L ptr hp 若剩余串非空 则构造第二个表结点L ptr tp 并从串S中分解出第二个子串 2 对应创建第二个子广义表 依次类推 直至剩余串为空串止 2020年4月6日星期一 voidCreateGList Glist 脱去串S的外层括弧 else 由sub中所含n个子串建立n个子表 2020年4月6日星期一 do sever sub hsub 分离出子表串hsub iif StrEmpty sub p ptr tp Glist malloc sizeof GLNode 建下一个子表的表结点 p ptr tp p p ptr tp while StrEmpty sub p ptr tp NULL 表尾为空表 创建由串hsub定义的广义表p ptr hp 2020年4月6日星期一 if StrLength hsub 1 p ptr hp GList malloc sizeof GLNode p ptr hp tag ATOM p ptr hp atom hsub 创建单原子结点 elseCreateGList p ptr hp hsub 递归建广义表 2020年4月6日星期一 后置递归的设计思想为 2020年4月6日星期一 递归的终结状态是 当前的问题可以直接求解 对原问题而言 则是已走到了求解的最后一步 链表是可以如此求解的一个典型例子 例如 编写 删除单链表中所有值为x的数据元素 的算法 2020年4月6日星期一 1 单链表是一种顺序结构 必须从第一个结点起 逐个检查每个结点的数据元素 分析 2 从另一角度看 链表又是一个递归结构 若L是线性链表 a1 a2 an 的头指针 则L next是线性链表 a2 an 的头指针 2020年4月6日星期一 a1 a2 a3 an L 例如 a1 a2 a3 an L a1 a2 a3 an L 已知下列链表 1 a1 x 则L仍为删除x后的链表头指针 2 a1 x 则余下问题是考虑以L next为头指针的链表 a1 L next L next p next p L next 2020年4月6日星期一 voiddelete LinkList delete 2020年4月6日星期一 删除广义表中所有元素为x的原子结点 分析 比较广义表和线性表的结构特点 相似处 都是链表结构 不同处 1 广义表的数据元素可能还是个广义表 2 删除时 不仅要删除原子结点 还需要删除相应的表结点 2020年4月6日星期一 voidDelete GL Glist 考察第一个子表if head tag Atom head atom x 删除原子项x的情况else 第一项没有被删除的情况 Delete GL 2020年4月6日星期一 p L L L ptr tp 修改指针free head 释放原子结点free p 释放表结点Delete GL L x 递归处理剩余表项 1 L 0 x 1 p L head 2020年4月6日星期一 if head tag LIST 该项为广义表Delete GL head x Delete GL L ptr tp x 递归处理剩余表项 1 L 0a 1 1 head L ptr tp 2020年4月6日星期一 回溯法是一种 穷举 方法 其基本思想为 假设问题的解为n元组 x1 x2 xn 其中xi取值于集合Si n元组的子组 x1 x2 xi i n 称为部分解 应满足一定的约束条件 对于已求得的部分解 x1 x2 xi 若在添加xi 1 Si 1之后仍然满足约束条件 则得到一个新的部分解 x1 x2 xi 1 之后继续添加xi 2 Si 2并检查之 2020年4月6日星期一 2020年4月6日星期一 例一 皇后问题求解 设四皇后问题的解为 x1 x2 x3 x4 其中 xi i 1 2 3 4 Si 1 2 3 4 约束条件为 其中任意两个xi和xj不能位于棋盘的同行 同列及同对角线 按回溯法的定义 皇后问题求解过程为 解的初始值为空 首先添加x1 1 之后添加满足条件的x2 3 由于对所有的x3 1 2 3 4 都不能找到满足约束条件的部分解 x1 x2 x3 则回溯到部分解 x1 重新添加满足约束条件的x2 4 依次类推 2020年4月6日星期一 voidTrial inti intn 进入本函数时 在n n棋盘前i 1行已放置了互不攻 击的i 1个棋子 现从第i行起继续为后续棋子选择 满足约束条件的位置 当求得 i n 的一个合法布局 时 输出之 if i n 输出棋盘的当前布局 elsefor j 1 j n j 在第i行第j列放置一个棋子 if 当前布局合法 Trial i 1 n 移去第i行第j列的棋子 trial 2020年4月6日星期一 回溯法求解的算法一般形式 voidB inti intn 假设已求得满足约束条件的部分解 x1 xi 1 本函 数从xi起继续搜索 直到求得整个解 x1 x2 xn if i n elsewhile Empty Si 从Si中取xi的一个值vi Si if x1 x2 xi 满足约束条件B i 1 n 继续求下一个部分解从Si中删除值vi B 2020年4月6日星期一 综合几点 1 对于含有递归特性的问题 最好设计递归形式的算法 但也不要单纯追求形式 应在算法设计的分析过程中 就事论事 例如 在利用分割求解设计算法时 子问题和原问题的