数据结构__4-5章

第4章串 4 1串类型的定义4 2串的表示和实现4 3串的模式匹配算法4 4串操作应用举例 4 1串类型的定义 在计算机的应用中 非数值处理问题的应用越来越多 如在汇编程序和编译程序中 源程序和目标程序都是作为一种字符串数据进行处理的 在事务处理系统中 用户的姓名和地址及货物的名称 规格等也是字符串数据 4 1串类型的定义 字符串一般简称为串 可以将它看作是一种特殊的线性表 这种线性表的数据元素的类型总是字符型的 字符串的数据对象约束为字符集 在线性表的基本操作中 大多以 单个元素 作为操作对象 而在串中 则是以 串的整体 或一部分作为操作对象 因此 线性表和串的操作有很大的不同 4 1串类型的定义 串 或字符串 是由零个或多个字符组成的有限序列 一般记作 S a1a2a3 an n 0 其中 s为串名 用引号括起来的字符序列是串的值 ci 0 i n 1 可以是字母 数字或其它字符 i为ci在串中的位置 引号为串值的定界符 不是串的一部分 字符串字符的数目n称为串的长度 4 1串类型的定义 零个字符的串称为空串 通常以两个相邻的引号来表示空串 如 s 它的长度为零 仅由空格组成的的串称为空格串 如 s 若串中含有空格 在计算串长时 空格应计入串的长度中 如 s I mastudent 的长度为13 4 1串类型的定义 当两个串的长度相等且各对应位置上的字符都相同时 这两个串是相等的 串中任意个连续字符组成的序列称为该串的子串 包含子串的串被称为主串 例如 com om a 和 man 都是 commander 的子串 子串在主串中的位置是指子串中第一个字符在主串中的位置序号 如子串 man 在主串 commander 中的位置为4 4 1串类型的定义 特别地 空串是任意串的子串 任意串是其自身的子串 通常在程序中使用的串可分为两种 串变量和串常量 串常量和整常数 实常数一样 在程序中只能被引用但不能不能改变其值 即只能读不能写 通常串常量是由直接量来表示的 如 constcharpath dir bin appl 这里path是一个串常量 对它只能读不能写 串变量和其它类型的变量一样 其取值是可以改变的 4 1串类型的定义 串的抽象数据类型定义 ADTString 数据对象 D ai ai CharacterSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 4 1串类型的定义 基本操作 StrAssign T chars 初始条件 chars是字符串常量 操作结果 把chars赋为T的值 StrCopy T S 初始条件 串S存在 操作结果 由串S复制得串T 注意 不能T S 只能通过函数来实现 4 1串类型的定义 StrLength S 初始条件 串S存在 操作结果 返回S的元素个数 称为串的长度 StrEmpty S 初始条件 串S存在 操作结果 若S为空串 则返回TRUE 否则返回FALSE 4 1串类型的定义 StrCompare S T 初始条件 串S和T存在 操作结果 若S T 则返回值 0 若S T 则返回值 0 若S T 则返回值 0 Concat T S1 S2 初始条件 串S1和S2存在 操作结果 用T返回由S1和S2联接而成的新串 4 1串类型的定义 SubString Sub S pos len 初始条件 串S存在 1 pos StrLength S 且0 len StrLength S pos 1 操作结果 用Sub返回串S的第pos个字符起长度为len的子串 4 1串类型的定义 Index S T pos 初始条件 串S和T存在 T是非空串 1 pos StrLength S 操作结果 若主串S中存在和串T值相同的子串 则返回它在主串S中第pos个字符之后第一次出现的位置 否则函数值为0 4 1串类型的定义 Replace S T V 初始条件 串S T和V存在 T是非空串 操作结果 用V替换主串S中出现的所有与T相等的不重叠的子串 StrInsert S pos T 初始条件 串S和T存在 1 pos StrLength S 1 操作结果 在串S的第pos个字符之前插入串T 4 1串类型的定义 StrDelete S pos len 初始条件 串S存在 1 pos StrLength S len 1 操作结果 从串S中删除第pos个字符起长度为len的子串 DestroyString S 初始条件 串S存在 操作结果 串S被销毁 4 1串类型的定义 ClearString S 初始条件 串S存在 操作结果 将S清为空串 ADTString 4 1串类型的定义 ClearString S 初始条件 串S存在 操作结果 将S清为空串 ADTString 4 1串类型的定义 在上述抽象数据类型定义的13种操作中 串赋值StrAssign 串复制Strcopy 串比较StrCompare 求串长StrLength 串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集 即这些操作不可能利用其他串操作来实现 反之 其他串操作 除串清除ClearString和串销毁DestroyString外 可在这个最小操作子集上实现 4 1串类型的定义 例1 求子串求子串的过程即为复制字符序列的过程 将串S中的第pos个字符开始长度为len的字符复制到串T中 voidsubstr stringsub strings intpos intlen if posstrlen s 1 len 0 error parametererror strncpy sub s pos len 4 1串类型的定义 例2 利用判等 求串长和求子串等操作实现定位函数Index S T pos 算法的基本思想为 在主串S中取从第i i的初值为pos 个字符起 长度和串T相等的子串和串T比较 若相等 则求得函数值为i 否则i值增1直至串S中不存在和串T相等的子串为止 4 1串类型的定义 intIndex StringS StringT intpos if pos 0 n StrLength S m StrLength T i pos while i n m 1 SubString sub S i m if StrCompare sub T 0 i elsereturni while ifreturn0 S中不存在与T相等的子串 Index 4 2串的表示和实现 因为串是特殊的线性表 故其存储结构与线性表的存储结构类似 只不过组成串的结点是单个字符 串有三种机内表示方法 1 定长顺序存储表示2 堆分配存储表示3 串的块链存储表示 4 2串的表示和实现 1 定长顺序存储表示定长顺序存储表示 也称为静态存储分配的顺序表 它是用一组连续的存储单元来存放串中的字符序列 所谓定长顺序存储结构 是直接使用定长的字符数组来定义 数组的上界预先给出 defineMAXSTRLEN255typedefcharSString MAXSTRLEN 1 SStrings s是一个可容纳255个字符的顺序串 4 2串的表示和实现 一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束 例如 C语言中以字符 0 表示串值的终结 这就是为什么在上述定义中 串空间最大值MAXSTRLEN为256 但最多只能存放255个字符的原因 因为必须留一个字节来存放 0 字符 若不设终结符 可用下标为0的元素来存放串的长度 4 2串的表示和实现 此时顺序串的类型定义和顺序表类似 typedefcharSString MAXSTRLEN 1 其优点是涉及到串长操作时速度快 4 2串的表示和实现 采用此方式处理串联接的算法如下 设S1 S2和T都是SString类型的变量 将S1和S2连接放到T中 具体分三种情况处理 1 S1 0 S2 0 MAXSTRLEN 先取S1中所有字符 再取S2中MAXSTRLEN S1 0 个字符放到T中 3 S1 0 MAXSTRLEN 取S1放到T中 4 2串的表示和实现 StatusConcat SStringS1 SStringS2 SString 4 2串的表示和实现 elseif S1 0 MAXSTRSIZE T 1 S1 0 S1 1 S1 0 T S1 0 1 MAXSTRLEN S2 1 MAXSTRLEN S1 0 T 0 MAXSTRLEN uncut FALSE 4 2串的表示和实现 else T 0 MAXSTRLEN S1 0 MAXSTRLEN uncut FALSE returnuncut Concat 4 2串的表示和实现 按这种串的表示方法实现的串的运算时 其基本操作为 字符序列的复制 这种方法的缺点是固定分配的空间容易产生 上溢 其处理方法 截尾法 会造成数据的丢失 为克服这个缺点 可采用其他两种方法来表示串 4 2串的表示和实现 2 堆分配存储表示堆存储结构的特点是 仍以一组空间足够大的 地址连续的存储单元存放串值字符序列 但它们的存储空间是在程序执行过程中动态分配的 所以也称为动态存储分配的顺序表 在C语言中 存在一个称为 堆 的自由空间 由动态分配函数malloc 分配一块实际串长所需的存储空间 如果分配成功 则返回这段空间的起始地址 作为串的基址 由free 释放串不再需要的空间 4 2串的表示和实现 在C和C 语言中可利用malloc和free两个函数实现动态存储分配 函数malloc为每个新产生的串分配一块实际所需大小的空间 若分配成功 则返回一个指向该空间起始地址的指针 作为新串的基址 另外为了便于串的运算 在存储结构中包含串的长度 typedefstruct char str intlength HString 4 2串的表示和实现 仍以串联接操作为例 采用堆分配存储描述的算法如下 HstringConcat HString 释放旧空间 4 2串的表示和实现 if s str char malloc s1 length s2 length sizeof char exit overflow for i 0 i s1 length i s str i s1 str i for i 0 i s2 length i s str s1 length i s2 str i s length s1 length s2 length returnok 4 2串的表示和实现 3 串的块链存储表示顺序串上的插入和删除操作不方便 需要移动大量的字符 因此 我们可用单链表方式来存储串值 串的这种链式存储结构简称为链串 typedefstructnode chardata structnode next LString 4 2串的表示和实现 一个链串由头指针唯一确定 这种结构便于进行插入和删除运算 但存储空间利用率太低 为了提高存储密度 可使每个结点存放多个字符 通常将结点数据域存放的字符个数定义为结点大小 显然 当结点大小大于1时 串的长度不一定正好是结点的整数倍 因此要用特殊字符来填充最后一个结点 以表示串的终结 4 2串的表示和实现 对于结点大小不为1的链串 其类型定义只需对上述的结点类型做简单的修改即可 defineCHUNKSIZE80typedefstructChunk chardata CHUNKSIZE structChunk next Chunk 4 2串的表示和实现 以上为结点大小 1的链串中结点定义 链串这种表示方式占用存储量大且操作复杂 总体来说不如另外两种结构灵活 因此 除在特定情况下 一般不采用这种方式来处理串 4 3串的模式匹配算法 子串定位运算称为模式匹配 PatternMatching 或串匹配 StringMatching 模式匹配成功是指在目标串s中找到一个模式串t 模式匹配不成功则指目标串s中不存在模式串t 此运算的应用非常广泛 例如 在文本编辑程序中 经常要查找某一特定单词在文本中出现的位置 显然 解此问题的有效算法能极大地提高文本编辑程序的响应性能 4 3串的模式匹配算法 串匹配的定义 INDEX S T pos 初始条件 串S和T存在 T是非空串 1 pos StrLength S 操作结果 若主串S中存在和串T值相同的子串 则返回它在主串S中第pos个字符之后第一次出现的位置 否则函数值为0 4 3串的模式匹配算法 在串匹配中 一般将主串称为目标串 子串称之为模式串 设S为目标串 T为模式串 设 S s0s1s2 sn 1 T t0t1 tm 1 串的匹配实际上是对于合法的位置0 i n m依次将目标串中的子串s i i m 1 和模式串t 0 m 1 进行比较 若相等 则称从位置i开始的匹配成功 亦称模式t在目标s中出现 若s i i m 1 t 0 m 1 则称从位置i开始的匹配失败 4 3串的模式匹配算法 上述的位置i又称为位移 当s i i m 1 t 0 m 1 时 i称为有效位移 当s i i m 1 t 0 m 1 时 i称为无效位移 串匹配问题可简化为是找出某给定模式T在一给定目标S中首次出现的有效位移 串匹配的算法很多 这里我们讨论三种算法 1 简单算法2 首尾匹配算法 3 KMP D E Knuth V R Pratt J H Morris 算法 4 3串的模式匹配算法 1 简单算法又称为Brute Force算法 其基本思想是 从目标串s的第一个字符起和模式串t的第一个字符进行比较 若相等 则继续逐个比较后续字符 否则从串s的第二个字符起再重新和串t进行比较 依此类推 直至串t中的每个字符依次和串s的一个连续的字符序列相等 则称模式匹配成功 此时串t的第一个字符在串s中的位置就是t在s中的位置 否则模式匹配不成功 4 3串的模式匹配算法 假设s cddcdc t cdc 则模式匹配过程下图所示 4 3串的模式匹配算法 Brute Force算法描述如下 intIndex StringS StringT intpos i pos j 1 while iT 0 returni T 0 elsereturn0 Index 4 3串的模式匹配算法 2 首尾匹配算法先比较模式串的第一个字符 再比较模式串的最后一个字符 最后比较模式串中从第二个到第n 1个字符 4 3串的模式匹配算法 首尾匹配算法的描述如下 intIndex FL StringS StringT intpos i pos while i S 0 T 0 1 if S i T 1 i 重新查找匹配起始点elseif S i T 0 1 T T 0 i 模式串的 尾字符 不匹配 4 3串的模式匹配算法 else 检查中间字符的匹配情况k 1 j 2 while j T 0 4 3串的模式匹配算法 3 KMP D E Knuth V R Pratt J H Morris 算法上述两种算法的优点是算法简单明朗 便于实现记忆 缺点是进行了回溯 效率不高 而这些都是没有必要的 KMP算法对其进行了改进 消除了目标串指针的回溯 提高了算法的效率 4 4串操作应用举例 文本编辑是串的一个很典型的应用 它被广泛用于各种源程序的输入和修改 也被应用于信函 报刊 公文 书籍的输入 修改和排版 文本编辑的实质就是修改字符数据的形式或格式 在各种文本编辑程序中 它们把用户输入的所有文本都作为一个字符串 4 4串操作应用举例 尽管各种文本编辑程序的功能可能有强有弱 但是它们的基本的操作都是一致的 一般包括串的输入 查找 修改 删除 输出等 为了编辑方便起见 用户可以通过换页符和换行符将文本划分为若干页或将每页划分为若干行 可将整个文本看成是一个文本串 页是文本串的子串 而行则是页的子串 4 4串操作应用举例 假设有下列一段C源程序 main floata b max scanf f f 若用 n表示换行符 该文本串在内存中的存储映像如下表所示 4 4串操作应用举例 4 4串操作应用举例 为了管理文本串中的页和行 在进入文本编辑时 编辑程序先为文本串建立相应的页表和行表 即建立各子串的存储映像 页表的每一项列出页号和该页的起始行号 行表的每一项则指示每一行的行号 起始地址和该行子串的长度 4 4串操作应用举例 以上表为例 假设文本串只占一页 起始行号为100 起始地址为200 则该文本串的行表如下所示 4 4串操作应用举例 下面来讨论文本的编辑 1 插入一行时 首先在文本末尾的空闲工作区写入该行的串值 然后 在行表中建立该行的信息 插入后 必须保证行表中行号从小到大的顺序 2 删除一行时 则只要在行表中删除该行的行号 后面的行号向前平移 若删除的行是页的起始行 则还要修改相应页的起始行号 改为下一行 4 4串操作应用举例 3 修改文本时 在文本编辑程序中设立了页指针 行指针和字符指针 分别指示当前操作的页 行和字符 若在当前行内插入或删除若干字符 则要修改行表中当前行的长度 如果该行的长度超出了分配给它的存储空间 则应为该行重新分配存储空间 同时还要修改该行的起始位置 习题 1 设s IAMASTUDENT t GOOD q WORKER 试求 StrLength s 的返回值 执行StrInsert t 5 q 后串t的值 Index s A 4 的返回值 执行Replace s STUDENT q 后串s的值 执行SubString p s 8 4 后串p的值 习题 2 试写算法 在堆存储结构上实现串的基本操作StrDelete S pos len 提示 删除后要重新分配空间 满足堆分配存储结构的定义 习题 3 设串采用定长顺序存储结构 设计算法 求由所有包含在串s中而不包含在串t中的字符构成的新串r 串s中的重复字符在r中只出现一次 习题 2 参考答案 StatusStrDelete HString StrDelete 习题 3 参考答案 voidSub str SStrings SStringt SString 判断s的当前字符c是否 第一次出现 if j i 当前字符c是第一次出现for k 1 kt 0 r r 0 c 当前字符放入r if for Sub str 第5章数组和广义表 5 1数组的定义5 2数组的顺序表示和实现5 3矩阵的压缩存储5 4广义表的定义5 5广义表的存储结构 5 1数组的定义 数组和广义表可看成是一种特殊的线性表 其特殊在于 表中的数所元素本身也是一种线性表 数组是我们最熟悉的数据类型 在早期的高级语言中 数组是唯一可供使用的数据类型 由于数组中各元素具有统一的类型 并且数组元素的下标一般具有固定的上界和下界 因此 数组的处理比其它复杂的结构更为简单 5 1数组的定义 数组 Array 是由n n 1 个相同类型数据元素a0 al ai an 1构成的有限序列 n是数组的长度 其中数组中的数据元素ai是一个数据结构 即ai可以是线性表中的一个元素 本身也可以是一个线性表 而线性子表中的每一个数据元素还可以再分解 根据数组元素ai的组织形式不同 数组可以分为一维数组 二维数组以及多维 n维 数组 5 1数组的定义 有时也把一维数组称为向量 二维数组称为矩阵 在二维或多维数组中 每个数组元素都受到2个或n个关系的约束 当数组为n维时 其对应线性表中的每个元素又是一个线性表 在每个关系中 每个元素都有一个直接后继 因此 就其单个关系而言 这n个关系中的每一个仍然是一种线性关系 5 1数组的定义 数组中每个元素都是由一个值和一组下标来确定的 同线性表一样 数组中的所有数据元素都必须属于同一数据类型 元素下标的个数被称为数组的维数 显然 当维数为1时 数组就退化为定长的线性表 5 1数组的定义 1 一维数组一维数组可以看成是一个线性表或一个向量 它在计算机内是存放在一块连续的存储单元中 适合于随机查找 一维数组记为A n 或A a0 al ai an 1 一旦a0的存储地址 一个数据元素所占存储单元数k确定 则ai的存储地址LOC ai 就可求出 LOC ai LOC a0 i k 0 i n 5 1数组的定义 2 二维数组二维数组 又称矩阵 matrix 二维数组中的每一个元素又是一个定长的线性表 一维数组 都要受到两个关系即行关系和列关系的约束 也就是每个元素都同属于两个线性表 例如 设A是一个有m行n列的二维数组 则A可以表示为 5 1数组的定义 可以看成由m个行向量组成的向量 也可以看由n个列向量组成的向量 5 1数组的定义 数组中的每个元素由元素值aij及一组下标 i j 来确定 aij既属于第i行的行向量 又属于第j列的列向量 其中 ai ai 0ai 1 ai n 1 0 i n 可以认为Am n A A是这样的一维数组 A a0 al ai am 1 5 1数组的定义 显然 二维数组同样满足数组的定义 一个二维数组可以看作是每个数据元素都是相同类型的一维数组 以此类推 任何多维数组都可以看作一个线性表 这时线性表中的每个数据元素也是一个线性表 多维数组是特殊的线性表 是线性表的推广 5 1数组的定义 数组的性质 1 数组中的数据元素数目固定 一旦定义了一个数组 其数据元素数目不再有增减变化 它属于静态分配存储空间的数据结构 2 数组中的数据元素必须具有相同的数据类型 3 数组中的每个数据元素都有一组唯一的下标值 4 数组是一种随机存储结构 可随机存取数组中的任意数据元素 5 2数组的顺序表示和实现 数组一旦被定义 它的维数和维界就不再改变 因此 除了结构的初始化和销毁之外 数组的基本操作一般不会含有元素的插入或删除等操作 数组只有访问数组元素和修改元素值的操作 5 2数组的顺序表示和实现 1 value A indexl index2 indexd A是已存在的d维数组 indexl index2 indexd是指定的d个下标值 且这些下标均不超过对应维的上界 其运算结果是返回由下标指定的A中的对应元素的值 2 assign A e indexl index2 indexd A是已存在的d维数组 e为元素变量 indexl index2 indexd是指定的d个下标值 且这些下标均未越界 其运算结果是将e的值赋给由下标指定的A中的对应元素 5 2数组的顺序表示和实现 3 disp A 输出数组A的所有元素 在大多数程序设计语言中 取数组元素值操作value A indexl index2 indexd 通常直接写作A indexl index2 indexd 而对数组元素的赋值操作assign A e indexl index2 indexd 写作e A indexl index2 indexd 或者类似的形式 5 2数组的顺序表示和实现 由于数组一般不作删除或插入运算 所以一旦数组被定义后 数组中的元素个数和元素之间的关系就不再变动 通常采用顺序存储结构表示数组 对于一维数组 数组的存储结构关系为 LOC ai LOC a0 i k 0 i n 5 2数组的顺序表示和实现 对于二维数组 由于计算机的存储单元是一维线性结构 如何用线性的存储结构存放二维数组元素就有行 列次序问题 常用两种存储方法 以行序 rowmajororder 为主序的存储方式和以列序 columnmajororder 为主序的存储方式 5 2数组的顺序表示和实现 行优先顺序 将数组元素按行排列 第i 1个行向量紧接在第i个行向量后面 以二维数组为例 按行优先顺序存储的线性序列为 a11 a12 a1n a21 a22 a2n am1 am2 amn在PASCAL C语言中 数组就是按行优先顺序存储的 5 2数组的顺序表示和实现 列优先顺序 将数组元素按列向量排列 第j 1个列向量紧接在第j个列向量之后 A的m n个元素按列优先顺序存储的线性序列为 a11 a21 am1 a12 a22 am2 an1 an2 anm在FORTRAN语言中 数组就是按列优先顺序存储的 5 2数组的顺序表示和实现 5 2数组的顺序表示和实现 对一个以行序为主序的计算机系统 当二维数组第一个数据元素a0 0的存储地址LOC a0 0 以及每个数据元素所占用的存储单元k确定后 该二维数组中任一数据元素ai j的存储地址可由下式确定 LOC ai j LOC a0 0 i n j k其中n为每行中的列数 5 2数组的顺序表示和实现 例 对于给定的二维数组floata 3 4 计算 1 数组a中的数组元素数目 2 若数组a的起始地址为1000 且每个数组元素长度为32位 即4个字节 数组元素a 2 3 的内存地址 解 1 略 2 由于C语言采用行序为主序的存储方式 有 LOC a2 3 LOC a0 0 i n j k 1000 2 4 3 4 1044 5 3矩阵的压缩存储 矩阵是数值计算程序设计中经常用到的数学模型 它是由m行和n列的数值构成 当m n时称为方阵 在高级程序设计语言中 通常用二维数组表示矩阵 然而在数值分析过程中经常遇到一些比较特殊的矩阵 它们的阶数很高 矩阵中元素数量很大 而且有很多元素的值相同或零值元素 如对称矩阵 三角矩阵 带状矩阵和稀疏矩阵等 5 3矩阵的压缩存储 为了节省存储空间并且加快处理速度 需要对这类矩阵进行压缩存储 压缩存储的原则是 不重复存储相同元素 不存储零值元素 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵 主要形式有对称矩阵 三角矩阵 对角矩阵等 5 3矩阵的压缩存储 1 对称矩阵的压缩存储对称矩阵是一个n阶方阵 若一个n阶矩阵A中的元素满足 ai j aj i 0 i j n 1 则称A为n阶对称矩阵 15137a0050800a10a1118926a20a21a2330251 70613an 10an 11an 12 an 1n 1 5 3矩阵的压缩存储 在这个下三角矩阵中 第i行恰有i 1个元素 元素总数为n n 1 2个 由于对称矩阵中的元素关于主对角线对称 因此可以为每一对对称的矩阵元素分配1个存储空间 n阶矩阵中的n n个元素就可以被压缩到n n 1 2个元素的存储空间中去 5 3矩阵的压缩存储 称一维数组sa 0 n n 1 2 为n阶对称矩阵A的压缩存储 其存储对应关系如下图 5 3矩阵的压缩存储 2 三角矩阵的压缩存储三角矩阵也是一个n阶方阵 有上三角和下三角矩阵 下 上 三角矩阵是主对角线以上 下 元素均为零的n阶矩阵 设以一维数组sb 0 n n 1 2 作为n阶三角矩阵B的存储结构 仍采用按行存储方案 则B中任一元素bi j和sb k 之间存在着如下对应关系 5 3矩阵的压缩存储 其中 sb n n 1 2 中存放常数c或0 5 3矩阵的压缩存储 3 对角矩阵的压缩存储对角方阵 或称带状矩阵 是指所有的非零元素 简称非零元 都集中在以主对角线为中心的带状区域中 即除了主对角线上和紧靠着主对角线上下方若干条对角线上的元素外 所有其它元素皆为零的矩阵 常见的有三对角矩阵 五对角矩阵 七对角矩阵等 5 3矩阵的压缩存储 具有3条非零对角线的对角矩阵 5 3矩阵的压缩存储 对于n阶有m m必为奇数 因为副对角线关于主对角线对称 条非零元素带的对角矩阵 只需存放对角区域内的所有非零元素即可 对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中 不同的排列方案也就对应不同的存储方案 5 3矩阵的压缩存储 如果一个矩阵中有很多元素的值为零 即零元素的个数远远大于非零元素的个数时 称该矩阵为稀疏矩阵 根据存储时所附加信息的不同 稀疏矩阵的顺序存储方法包括 三元组表示法 带辅助行向量的二元组表示法和伪地址表示法 其中以三元组表示法最常用 5 3矩阵的压缩存储 三元组表示法就是在存储非零元的同时 存储该元素所对应的行下标和列下标 稀疏矩阵中的每一个非零元素由一个三元组 i j aij 唯一确定 矩阵中所有非零元素存放在由三元组组成的数组中 由线性表的两种不同存储结构可以得到稀疏矩阵压缩的不同的存储方法 5 3矩阵的压缩存储 假设有一个6 7阶稀疏矩阵A 其元素情况以及非零元对应的三元组表 以行序为主序 如图所示 三元组表中第一行表示行数 列数和非零元的个数 非零三元组按行号递增的顺序 相同行号的三元组按列号递增的顺序排列的 5 3矩阵的压缩存储 1 三元组顺序表假设以行序为主序 且以一维数组作为三元组表的存储结构 可以得到稀疏矩阵的一种压缩存储方法 称为三元组顺序表 三元组顺序表的数据结构定义如下 defineNUM100 矩阵中非零元素最大个数typedefstruct 三元组结构 intr c 行 列 号ElemTyped 元素值 tupletype 三元组定义 5 3矩阵的压缩存储 typedefstruct introws 矩阵行数值intcols 矩阵列数值intnums 非零元素个数tupletypedata NUM 三元组表 table 三元组顺序表定义 5 3矩阵的压缩存储 2 行逻辑链接的顺序表 带行表的三元组 有时为了方便某些矩阵运算 在按行优先存储的三元组中 加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置 当将行表作为三元组表的一个新增属性加以描述时 就得到了稀疏矩阵的另一种顺序存储结构 带行表的三元组表 称这种 带行链接信息 的三元组表为行逻辑链接的顺序表 5 3矩阵的压缩存储 其类型描述如下 definemaxrow100typedefstruct tripledata maxsize intrpos maxrow intn m t rtripletable 5 3矩阵的压缩存储 3 十字链表用三元数组的结构来表示稀疏矩阵 在某些情况下可以节省存储空间并加快运算速度 但在运算过程中 若稀疏矩阵的非零元素位置发生变化 必将会引起数组中元素的频繁移动 这时 采用链式存储结构 十字链表 表示三元组的线性表更为恰当 5 3矩阵的压缩存储 十字链表 orthogonallist 是稀疏矩阵的另一种存储结构 它是用多重链表来存储稀疏矩阵 十字链表适用于操作过程中非零元素的个数及元素位置变动频繁的稀疏矩阵 十字链表为矩阵中的每一行设置一个单独链表 同时也为每一列设置一个单独链表 这样 矩阵中的每个非零元就同时包含在两个链表中 即所在行和所在列的链表 这就大大降低了链表的长度 方便了算法中行方向和列方向的搜索 大大降低了算法的时间复杂度 5 3矩阵的压缩存储 在该方法中 每一个非零元用一个结点表示 结点中除了表示非零元所在的行 列和值的三元组 i j v 外 还需增加两个链域 行指针域 rptr 用来指向本行中下一个非零元素 列指针域 cptr 用来指向本列中下一个非零元素 5 3矩阵的压缩存储 稀疏矩阵中同一行的非零元通过向右的rptr指针链接成一个带表头结点的循环链表 同一列的非零元也通过cptr指针链接成一个带表头结点的循环链表 因此 每个非零元既是第i行循环链表中的一个结点 又是第j列循环链表中的一个结点 相当于处在一个十字交叉路口 故称链表为十字链表 5 3矩阵的压缩存储 另外 为了运算方便 我们规定行 列循环链表的表头结点和表示非零元的结点一样 也定为五个域 且规定行 列 域值为0 因此 为了使表头结点和表示非零元的表结点不发生混淆 三元组中 输入行和列的下标不能从0开始 而必须从1开始 并且将所有的行 列链表和头结点一起链成一个循环链表 5 3矩阵的压缩存储 在行 列 表头结点中 行 列域的值都为0 故两组表头结点可以共用 即第i行链表和第i列链表共用一个表头结点 这些表头结点本身又可以通过V域 非零元值域 但在表头结点中为next 指向下一个表头结点 相链接 另外 再增加一个附加结点 由指针hm指示 行 列域分别为稀疏矩阵的行 列数目 附加结点指向第一个表头结点 则整个十字链表可由hm指针惟一确定 5 3矩阵的压缩存储 对于一个m n的稀疏矩阵 每个非零元用一个含有五个域的结点来表示 如下图所示 其中各分量含义如下 1 矩阵中非零元素的行号i 2 矩阵中非零元素的列号j 3 矩阵中非零元素的值value 4 向右域right 用以链接同一行中下一个非零元素 5 向下域down 用以链接同一列中下一个非零元素 a 结点结构 b 头结点结构 5 3矩阵的压缩存储 例如 假设稀疏矩阵B3 4为 对应矩阵B3 4的十字链表如下图所示 为图示方便清楚 把每个行列头结点分别画成两个 一个行头结点和一个列头结点 而实际上 行头结点hi 0 i 4 与列头结点hi是存在于一个行列头结点中的 5 3矩阵的压缩存储 5 3矩阵的压缩存储 综上所述 稀疏矩阵的十字链表表示共有三种线性链表 1 由各行 列 表头结点组成的线性链表 其结点之间用各结点的next域相链接 2 由同一行中的非零元素结点组成的线性链表 其结点之间用各结点的right域相链接 3 由同一列中的非零元素结点组成的线性链表 其结点之间用各结点的down域相链接 5 3矩阵的压缩存储 十字链表结点结构和头结点的数据结构可定义如下 defineM3 矩阵行数 defineN4 矩阵列数 defineMax M N M N 矩阵行列较大者typedefstructmtxn introw intcol structmtxn right down union intvalue structmtxn next tag MatNode 5 4广义表的定义 1 广义表的定义广义表是线性表的推广 是一种多层次线性结构 线性表中的元素仅限于原子项 即不可以再分 而广义表中的元素既可以是原子项 也可以是子表 另一个线性表 主要用于人工智能领域的表处理语言LISP语言 5 4广义表的定义 广义表是n 0个元素a1 a2 an的有限序列 其中每一个ai或者是原子 或者是一个子表 广义表通常记为LS a1 a2 an 其中LS为广义表的名字 n为广义表的长度 ai为广义表的元素 但在习惯中 一般用大写字母表示广义表 小写字母表示原子 若n 0时为空表 记作 L 5 4广义表的定义 当广义表L非空 n 0 时 第一个数据元素a0被称为广义表的表头 head 其余数据元素组成的表 a1 an 1 被称为广义表L的表尾 tail 分别记为head A a0 tail a1 an 1 因此 一个广义表是由表头和表尾构成的 5 4广义表的定义 2 广义表举例