串、多维数组与广义表.ppt

第4章串 多维数组与广义表 4 1串 串又称字符串 是一种特殊的线性表 它的每个元素仅由一个字符组成 计算机上非数值处理的对象基本上是字符串数据 在较早的程序设计语言中 字符串仅作为输入和输出的常量出现 随着计算机应用的发展 在越来越多的程序设计语言中 字符串也可作为一种变量类型出现 并产生了一系列字符串的操作 在信息检索系统 文字编辑程序 自然语言翻译系统等等应用中 都是以字符串数据作为处理对象的 4 1 1串的定义 串 string 或字符串 是由零个或多个字符组成的有限序列 一般记为 S a1a2 an n 0 串名 串的名字S 串值 用双引号括起来的字符串序列 ai 1 i n 可以是字母 数字或其他字符 串的长度 串中字符的个数n称为串的长度 串相等 只有当两个串的长度相等 并且各个对应位置上的字符都相等时 才能称为串相等 4 1 1串的定义 子串 串中任意个连续的字符组成的子序列称为该串的子串 主串 包含子串的串称为该子串的主串 例如 S1 anhui S2 huaibei S anhuihuaibei 其中S1 S2都是S的子串 S为S1 S2的主串 空格串 由一个或多个空格组成的串称为空格串 空格串的长度不为零 空串 长度为0的串称为空串 通常用来表示 在C程序中表示成 它是任意串的子串 模式匹配 求子串在主串中的起始位置称为子串定位或模式匹配 例如 S1在S中的位置是1 而S2在S中的位置是7 4 1 1串的定义 ADTString 数据对象D D ai ai ElemSet i 1 2 n n 0 数据关系R R ai 1 ai D i 2 3 n 基本操作P 串赋值StrAssign S chars S是一个串变量 chars是一个串常量 将chars的值赋给串S 串比较StrCompare S T 若串变量S 串变量T 则返回值 0 若S T 则返回值为0 若S T 则返回值 0 求串长StrLength S 返回S中元素的个数 串联接Concat S T1 T2 用S返回T1和T2联接而成的新串 如 T1 xyz T2 abc 则Concat S T1 T2 xyzabc 注意Concat S T1 T2 Concat S T2 T1 求子串SubString T S pos len 1 pos StrLength S 0 len StrLength S pos 1 用T返回S中的第pos个字符起长度为len的子串 4 1 1串的定义 判断空串StrEmpty S 若S为空串 则返回TRUE 否则返回FALSE 串复制StrCopy T S 将串S复制到串T 串清空ClearString S 将S置空串 串定位StrIndex S T pos 串S和T存在 T是非空串 1 pos StrLength S 若T是S的子串 返回T在S中第一次出现的位置 否则返回0 串置换Replace S T V 串S T和V存在 T是非空串 用V替换主串S中出现的所有与T相等的不重叠的子串 例如 设S bbabbabba T ab V a 则Replace S T V 的结果是S bbababa 串插入StrInsert S pos T 1 pos StrLength S 1 在串S的第pos个字符之前插入串T 串删除StrDelete S pos len 1 pos StrLength S len 1 从串S中删去第pos字符起长度为len的子串 串销毁DestroyString S 串S被销毁 并回收串空间 ADTString 4 1 1串的定义 以上定义的13种操作 其中前五个操作是最基本的 被称为最小操作集 其他操作 串清空 串销毁除外 均可在这个最小操作集上实现 4 1 1串的定义 例如 用求串长 求子串和串比较实现串定位 算法描述如下 intStrIndex StringS StringT intpos intn m i Stringsub 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相等的子串 StrIndex 4 1 2串的表示和实现 串的表示有三种方式 顺序串 堆串和链串 4 1 2串的表示 串的定长顺序存储表示 方法一 defineMAXSIZE100typedefstruct charch MAXSIZE 字符数组存储串值intlength 整型变量表示串的长度 SString 例如 SStringS 串S的值 anhuihuaibei 串长为13 串的定长顺序存储结构如图4 1所示 4 1 2串的表示 串的定长顺序存储表示 方法二 定义字符数组s MAXSIZE 1 用串数组的第一个单元s 0 存放串的实际长度 串值存放在s 1 s MAXSIZE 中 用字符 0 作为串的结束符 这种方法字符的序号与存储位置是一致的 数据类型描述如下 defineMAXSIZE100 用户可在100以内定义最大串长typedefunsignedcharSString MAXSIZE 1 0号单元存放串的实际长度 4 1 2串的表示 串的定长顺序存储表示 1 串联接操作把两个串T1和T2首尾连接成一个新串S T1 0 T2 0 和S 0 分别存放串的实际长度 在操作时需考虑可能出现的三种情况 当T1 0 T2 0 MAXSIZE 即两串联接得到的串S是串T1和串T2联接的正常结果 S 0 T1 0 T2 0 当T1 0 MAXSIZE而T1 0 T2 0 MAXSIZE 将T2做截断处理 即将T2中多出部分舍去 S 0 MAXSIZE 当T1 0 MAXSIZE 不连接 则两串联接得到的S串实际上只是串T1的拷贝 串t2全部被截断 S 0 MAXSIZE 4 1 2串的表示 串的定长顺序存储表示 voidConcat SString Concat 4 1 2串的表示 串的定长顺序存储表示 2 求子串操作将串S中从第pos个字符开始长度为len的字符序列复制到串T中 为了增强算法的健壮性 应对指定的位置pos和长度len做合法性检查 4 1 2串的表示 串的定长顺序存储表示 SStringSubString SString SubString 4 1 2串的表示 串的堆分配存储表示 串的堆分配存储结构仍以一组地址连续的存储单元存放串的字符序列 但其存储空间是在算法执行过程中动态分配得到的 利用函数malloc 为每一个新产生的串分配一块实际需要的存储空间 若分配成功 则返回一个指针 指向串的起始地址 串的堆分配存储结构描述如下 typedefstruct char ch 若是非空串 则按串长分配存储区 否则ch为NULLintlength 串的实际长度 HString 4 1 2串的表示 串的堆分配存储表示 1 串联接操作voidConcat h HString Concat h 4 1 2串的表示 串的堆分配存储表示 2 求子串操作HStringSubString H HString SubString H 4 1 2串的表示 串的链式存储结构 a 结点大小为4的链表 b 结点大小为1的链表图4 2串值的链表存储方式 4 1 3串的模式匹配算法 布鲁特 Brute 福斯 Force 算法 简称为BF算法 Brute Force算法的设计思想 将主串S的第一个字符和模式T的第1个字符比较 若相等 继续逐个比较后续字符 若不等 从主串S的下一字符起 重新与T第一个字符比较 直到主串S的一个连续子串字符序列与模式T相等 返回值为S中与T匹配的子序列第一个字符的序号 即匹配成功 否则 匹配失败 返回值 1 操作示意图如图4 3所示 4 1 3串的模式匹配算法 4 1 3串的模式匹配算法 设主串s ababcabcacbab 模式t abcac BF算法的匹配过程如图4 4所示 4 1 4串的操作应用 文本编辑 文本编辑可以用于源程序的输入和修改 也可用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色 可用于文本编辑的程序很多 功能强弱差别很大 但基本操作是一致的 都包括串的查找 插入和删除等基本操作 对文本编辑程序来讲 可把整个文本看成一个长字符串 称文本串 页是文本串的子串 行又是页的子串 为简化程序复杂程度 可简单地把文本分成若干行 4 2数组 数组是一种常用的数据类型 多维数组可以视为线性表的扩展 即线性表中的数据元素本身也是一个数据结构 几乎所有高级语言程序设计中都设定了数组类型 4 2 1数组的定义 数组是由n n 1 个相同类型的数据元素a0 al ai an 1构成的有限序列 n是数组的长度 其中数组中的数据元素ai是一个数据结构 它可以是整型 实型等简单数据类型 也可以是数组 结构体 指针等构造类型 根据数组元素ai的组织形式不同 数组可以分为一维数组 二维数组以及多维 n维 数组 4 2 1数组的定义 1 一维数组一维数组可以看成是一个线性表或一个向量 它在计算机内是存放在一块连续的存储单元中 适合于随机查找 一维数组记为A n 或A a0 al ai an 1 一维数组中 已知a0的存储地址是LOC a0 一个数据元素占k个字节 则ai的存储地址LOC ai 为 LOC ai LOC a0 i k 0 i n 4 2 1数组的定义 2 二维数组二维数组 又称矩阵 matrix 每个数组元素都要受到两个关系即行关系和列关系的约束 例如 m行n列的二维数组Amn可以表示为 4 2 2数组的顺序存储结构 对于二维数组 常用两种存储方式 以行序 rowmajororder 为主序的存储方式和以列序 columnmajororder 为主序的存储方式 也称行优先顺序和列优先顺序 如图4 7所示 b 行优先顺序 c 列优先顺序 a00a01a02a10a11a12 a00a10a01a11a02a12 4 2 2数组的顺序存储结构 行优先顺序将数组元素按行排列 先存储第0行的全部元素 再存放第1行的元素 第2行的元素 直到第m 1行的元素 其线性序列为 a00 a01 a0 n 1 a10 a11 a1 n 1 a m 1 0 a m 1 1 a m 1 n 1 在C语言 VB等程序设计语言中 数组就是按行优先顺序存储的 对一个已知以行序为主序的计算机系统中 当二维数组第一个数据元素a00的存储地址是LOC a00 每个数据元素占k个字节 则aij的存储地址为 LOC aij LOC a00 i n j k其中n为每行中的列数 4 2 2数组的顺序存储结构 例如 二维数组floata 3 4 若数组a的起始地址为2000 且每个数组元素长度为32位 即4个字节 计算数组元素a 2 3 在行优先顺序存储时的内存地址 LOC a23 LOC a00 i n j k 2000 2 4 3 4 2044 4 2 2数组的顺序存储结构 列优先顺序将数组元素按列向量排列 先存储第0列的全部元素 再存放第1列的元素 第2列的元素 直到第n 1列的元素 其线性序列为 a00 a10 a m 1 0 a01 a11 a m 1 1 a0 n 1 a1 n 1 a m 1 n 1 在FORTRAN等少数程序设计语言中 数组就是按列优先顺序存储的 该二维数组中任一数据元素aij的存储地址为 LOC aij LOC a00 j m i k其中m为每列中的行数 如上例条件 计算数组元素a 2 3 在列优先顺序存储时的内存地址 LOC a23 LOC a00 j m i k 2000 3 3 2 4 2011 4 2 2数组的顺序存储结构 两种顺序存储方式 数组元素的存放地址都可以利用基地址 行列数以及每个数组元素所占用的字节数表示 如果m行n列的二维数组Amn表示为 以行优先顺序存储的二维数组中任一数据元素aij的存储地址为 LOC aij LOC a11 i 1 n j 1 k以列优先顺序存储的二维数组中任一数据元素aij的存储地址为 LOC aij LOC a11 j 1 m i 1 k 4 3矩阵的压缩存储 矩阵是数值计算程序设计中经常用到的数学模型 通常用二维数组表示 然而在数值分析过程中经常遇到一些比较特殊的矩阵 如对称矩阵 三角矩阵 带状矩阵和稀疏矩阵等 为了节省存储空间并且加快处理速度 下面讨论这些特殊矩阵的存储方法 4 3 1特殊矩阵 对称矩阵 1 对称矩阵对称矩阵是一个n阶方阵 其元素满足 aij aji 0 i j n 1 对称矩阵中的元素是关于主对角线对称的 因此在存储时只存储上三角或下三角 包括对角线 使得对称的元素共享一个存储空间 这样 n阶矩阵中的n n个元素就可以被压缩到n n 1 2个元素的存储空间中 4 3 1特殊矩阵 对称矩阵 第0行有1个元素 第1行有2个元素 第i行有i 1个元素 因此元素总数为 以行优先顺序对上面的对称矩阵存储其下三角 存储序列为 2 4 0 1 8 1 3 6 2 0 7 1 6 5 3 4 3 1特殊矩阵 对称矩阵 按行优先顺序存储到b数组后 数组元素aij 其下标特点是 i j且0 i n 1 行下标为0的行有一个元素 行下标为1的行有2个元素 行下标为i 1的行有i个元素 则0行到i 1行共有1 2 3 i i i 1 2个元素 在i行 aij的前面有j个元素 因此A中任一元素aij和b k 之间存在着如下对应关系 当i j时 aij是上三角中的元素 因为aij aji 访问上三角中的元素aij时则去访问和它对应的下三角中的aji即可 因此将上式中的行列下标交换就是上三角中元素在数组b中的对应关系 4 3 1特殊矩阵 三角矩阵 2 三角矩阵三角矩阵也是一个n阶方阵 有上三角和下三角矩阵 下 上 三角矩阵是主对角线以上 下 元素均为常数或零的n阶矩阵 如图4 11所示 4 3 1特殊矩阵 三角矩阵 2 三角矩阵 下三角矩阵下三角矩阵与对称矩阵的压缩存储类似 不同之处在于存储完下三角中的元素以后 紧接着存储对角线上方的常量 因为是同一个常数 只需存储一个即可 数组下标与元素之间存在着如下对应关系 上三角矩阵对于上三角矩阵 第一行存储n个元素 第二行存储n 1个元素 依次类推 aij的前面有i行 共存储n n 1 n i 1 i 2n i 1 2个元素 在i行 aij前有j i个元素 因此数组下标与元素之间存在着如下对应关系 4 3 1特殊矩阵 对角矩阵 3 对角矩阵若一个n阶方阵A满足所有的非零元素都集中在以主对角线为中心的带状区域中 则称其为n阶对角矩阵 或带状矩阵 常见的有三对角矩阵 五对角矩阵 七对角矩阵等 如图4 12是一个三对角矩阵A 4 3 1特殊矩阵 对角矩阵 对于三角矩阵 只存储其非零元素 按行优先顺序存储到数组b中 A中第0行和第n 1行都只有两个非零元素 其余各行均为3个非零元素 对于不在第0行的非零元素aij 在它前面存储了矩阵的前i行元素 这些元素共2 3 i 1 个 若aij是本行中要存储的第1个非零元素 则k 2 3 i 1 此时 j i 1 即k 2i i 1 2i j 若aij第是本行中要存储的第2个非零元素 则k 2 3 i 1 1 3i 此时 j i 即k 2i i 2i j 若aij第是本行中要存储的第3个非零元素 则k 2 3 i 1 2 3i 1 此时 j i 1 即k 2i i 1 2i j 因此 非零元素aij与数组b的下标之间存在着如下对应关系 k 2i j 4 3 2稀疏矩阵 如果矩阵中有很多零元素 即零元素的个数远远大于非零元素的个数时 称该矩阵为稀疏矩阵 为了节省存储空间 稀疏矩阵一般都采用压缩存储的方法来存储矩阵中的元素 这类矩阵一般零元素的分布没有规律 为了能找到相应的元素 在存储非零元素值的同时也要存储其所在的行和列信息 有两种常用的存储稀疏矩阵的方法 三元组表示法和十字链表法 4 3 2稀疏矩阵 1 三元组表示法 4 3 2稀疏矩阵 2 十字链表 结点中三元组 i j v 表示非零元素所在的行 列和值 两个链域 行指针域 right 用来指向本行中下一个非零元素 列指针域 down 用来指向本列中下一个非零元素 稀疏矩阵中同一列的所有非零元素通过down指针域链接成一个循环列链表 同一行的所有非零元素通过right指针域链接成一个带表头结点的循环行链表 因此 每个非零元素aij既是第i行循环链表中的一个结点 又是第j列循环链表中的一个结点 就像一个十字交叉路口 故称其为十字链表 4 4广义表 广义表 Lists 又称列表 是线性表的推广 线性表定义为n n 0 个元素a1 a2 a3 an的有限序列 线性表的元素仅限于原子项 即不可分割 而广义表中的元素既可以是原子项 也可以是子表 4 4广义表 广义表是n n 0 个元素a1 a2 a3 an的有限序列 记作LS a1 a2 a3 an 其中ai是LS的成员 可以是原子项 也可以是一个广义表 子表 LS是广义表的名字 n为它的长度 若ai是广义表 则称它为LS的子表 通常用圆括号将广义表括起来 用逗号分隔其中的元素 为了区别原子和广义表 书写时用大写字母表示广义表 用小写字母表示原子 4 4广义表 广义表的性质 广义表的元素可以是子表 而子表的元素还可以是子表 由此可得 广义表是一个多层次的结构 广义表可为其它表所共享 例如在上述例 中 广义表A B C为D的子表 则在D中可以不必列出子表的值 而是通过子表的名称来引用 广义表的递归性 一个广义表也可以是其自身的子表 这种广义表称为递归表 其深度是无穷值 长度是有限值 4 4广义表 广义表的例子如下 A A是一个空表 B e 表B只有一个原子e C a b c d 表C有两个元素分别为原子a和子表 b c d D A B C 表D的三个元素都是广义表 显然 将子表的值代入后 则有D e a b c d E a E 这是一个递归的表 它相当于一个无限的广义表E a a a a 4 4广义表 基本操作 1 求广义表的头部与尾部操作若广义表LS n 1 非空 则a1是LS的表头 其余元素组成的表 a2 an 称为LS的表尾 即GetHead LS a1 GetTail LS a2 an 例如 GetHead b k p h b GetTail b k p h k p h GetHead a b c d a b GetTail a b c d c d GetTail GetHead a b c d b GetTail e GetHead GetTail 4 4广义表 基本操作 2 求广义表的长度操作广义表的长度指该广义表中所包含的元素 包括原子和子表 的个数 例如 GLLength 0GLLength e 1GLLength a b c d 2GLLength A B C 3GLLength a E 2 4 4广义表 基本操作 3 求广义表的深度操作广义表的深度指该广义表中所包含括号的层数 例如 GLDepth 1GLDepth e 1GLDepth a b c d 2GLDepth A B C 3GLDepth a E 为无穷值 4 4广义表 存储 为了区分表结点和原子结点这两类结点 需设置一个标志域tag 如果tag 1 表示该结点为表结点 如果tag 0 表示该结点为原子结点 表结点的形式除了标志域还包括一个指向表头的指针域headp和一个指向表尾的指针域tailp 4 4广义表 存储