《Chapter04_串_数据结构(C语言版)_严蔚敏_配套ppt课件》由会员分享，可在线阅读，更多相关《Chapter04_串_数据结构(C语言版)_严蔚敏_配套ppt课件（88页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 串串 4 1 串类型的定义串类型的定义 4 2 串的表示和实现串的表示和实现 4 3 串的模式匹配算法串的模式匹配算法 4 1 串类型的定义串类型的定义 一 串的定义一 串的定义 二 串的抽象数据类型的定义如下二 串的抽象数据类型的定义如下 一 串的定义一 串的定义 串串 string 或字符串 是由零个或多个字符组成的有限 序列 一般记为 string 或字符串 是由零个或多个字符组成的有限 序列 一般记为 s s a a1 1a a2 2a a3 3 a an n n 0 n 0 其中 其中 s s是是串名串名 单引号括起来的字符序列是 单引号括起来的字符序列是串的值串的值
2、a ai i可以是字母 数字或其他字符 可以是字母 数字或其他字符 串中的字符个数称为串中的字符个数称为串的长度串的长度 零个字符的串称为零个字符的串称为空串空串 Null string 其长度为零 Null string 其长度为零 串中任意个连续的字符组成的子序列称为该串的串中任意个连续的字符组成的子序列称为该串的子串子串 包含子串的串相应地称为包含子串的串相应地称为主串主串 字符在序列中的序号为该字符在串中的字符在序列中的序号为该字符在串中的位置位置 子串在主串中的位置则以子串的第一个字符在主串中的位 置来表示 子串在主串中的位置则以子串的第一个字符在主串中的位 置来表示 由一个或多个空
3、格字符组成的串称为由一个或多个空格字符组成的串称为空格串 空格串 例 串a b c d e五个串如下 例 串a b c d e五个串如下 a a very difficultvery difficult b b c c d d veryvery e e difficultdifficult 串a的长度为14 串a的长度为14 串b是长度为3的空格串 串b是长度为3的空格串 串c是空串 长度为0 串c是空串 长度为0 串d和e是串a的子串 串d在串a中的位置 是1 串e在串a中的位置是6 串d和e是串a的子串 串d在串a中的位置 是1 串e在串a中的位置是6 串相等串相等 当且仅当两个串的值相等
4、 即只有当两个 串的长度相等 并且各个对应位置的字符都相等时 才相等 当且仅当两个串的值相等 即只有当两个 串的长度相等 并且各个对应位置的字符都相等时 才相等 空串是任意串的子串 空串是任意串的子串 任意串又是自己的子串任意串又是自己的子串 注意 注意 串值必须用一对单引号括起来 但单引号本身不属 于串 串值必须用一对单引号括起来 但单引号本身不属 于串 空串与空白串截然不同 空串不包含任何字符 空串与空白串截然不同 空串不包含任何字符 二 串的抽象数据类型的定义如下 二 串的抽象数据类型的定义如下 ADT String 数据对象数据对象 D ai ai CharacterSet i 1 2
5、 n n 0 数据关系数据关系 R1 ai 1 ai D i 2 n 基本操作基本操作 StrAssign 否则返回 FALSE 表示空串 空串的长度为零 StrCompare S T 初始条件 初始条件 串 S 和 T 存在 操作结果 操作结果 若S T 则返回值 0 若S T 则返回值 0 若S T 则返回值 0 例如 例如 StrCompare data state 0 StrLength S 初始条件 串 S 存在 操作结果 返回 S 的元素个 数 称为串的长度 Concat m StrLength T i pos while i n m 1 SubString sub S i m i
6、f StrCompare sub T 0 i else return i while if return 0 S中不存在与中不存在与T相等的子串相等的子串 Index 又如串的置换函数 S 串 T 串V 串 V 串 pospos sub i news 串 sub 串的逻辑结构和线性表极为相似 区 别 区 别仅在于串的数据对象约束为字符集 串的基本操作和线性表有很大差别 串的基本操作和线性表有很大差别 在线性表的基本操作中 大多以大多以 单个 元素 单个 元素 作为操作对象作为操作对象 在串的基本操作中 通常以通常以 串的整体串的整体 作为操作对象作为操作对象 在程序设计语言中 串只是作 为输入
7、或输出的常量出现 则只需 存储此串的串值 即字符序列即可 但在多数非数值处理的程序中 串 也以变量的形式出现 4 2 串的表示和实现串的表示和实现 一 串的定长顺序存储表示一 串的定长顺序存储表示 二 串的堆分配存储表示二 串的堆分配存储表示 三 串的块链存储表示三 串的块链存储表示 串有三种机内表示方法 串有三种机内表示方法 将串中的字符顺序地存 放在内存一片连续的存储单 元中 设串S 将串中的字符顺序地存 放在内存一片连续的存储单 元中 设串S a a1 1 a a2 2 a an n 则 顺序存贮结构在内存贮器中 的存贮示意图如图所示 则 顺序存贮结构在内存贮器中 的存贮示意图如图所示
8、a1 a2 a3 an 一 串的定长顺序存储表示一 串的定长顺序存储表示 串的定长顺序存储表示 P73 define MAXSTRLEN 255 用户可在255以内定义最大串长 typedef unsigned char SString MAXSTRLEN 1 0号单元存放串的长度 按这种串的表示方法实现的串的运算 时 其基本操作为 字符序列的复制字符序列的复制 串串的实际长度可在这个予定义长度的 范围内随意设定 超过予定义长度的串 值则被舍去 称之为 截断截断 特点特点 下面以串联接和求子串为例讨论之 1 串联接串联接 Concat Concat T 1 S1 0 S1 1 S1 0 T S
9、1 0 1 S1 0 S2 0 S2 1 S2 0 T 0 S1 0 S2 0 uncut TRUE if S1 0 S2 0 MAXSTRLEN 未截断未截断 else if S1 0 MAXSTRSIZE 截断截断 else 截断截断 仅取仅取S1 T 1 S1 0 S1 1 S1 0 T S1 0 1 MAXSTRLEN S2 1 MAXSTRLEN S1 0 T 0 MAXSTRLEN uncut FALSE T 0 MAXSTRLEN S1 0 MAXSTRLEN T 0 S1 0 MAXSTRLEN uncut FALSE 2 求子串求子串 SubString Sub 1 len
10、S pos pos len 1 Sub 0 len return OK SubString 综上两个操作可见 在顺序存储结构中 实现串操作的原操作为 综上两个操作可见 在顺序存储结构中 实现串操作的原操作为 字符序列的复制字符序列的复制 操 作的时间复杂度基于复制的字符序列的长度 另一操作特点是 如果在操作中出现串值 序列的长度超过上界 操 作的时间复杂度基于复制的字符序列的长度 另一操作特点是 如果在操作中出现串值 序列的长度超过上界MAXSTRLEN时 约定用 截尾法处理 这种情况下不仅在求联接串时可 能发生 在串的其它操作中 如插入 置换等 也可能发生 克服这个弊病唯有不限定串长的 最大
11、长度 即动态分配串值的存储空间 时 约定用 截尾法处理 这种情况下不仅在求联接串时可 能发生 在串的其它操作中 如插入 置换等 也可能发生 克服这个弊病唯有不限定串长的 最大长度 即动态分配串值的存储空间 仍以一组地址连续的存储单元存放串值字符序 列 但它们的存储空间是在程序执行过程中动态分配 而得 在C语言中 存在一个称之为 仍以一组地址连续的存储单元存放串值字符序 列 但它们的存储空间是在程序执行过程中动态分配 而得 在C语言中 存在一个称之为 堆堆 的自由存储 区 并由C语言的动态分配函数malloc 和free 来管理 利用函数malloc 为每个新产生的串分配 一块实际串长所需的存储
12、空间 若分配成功 则返回 一个指向起始地址的指针 作为串的基址 同时 为 了以后处理方便 约定串长也作为存储结构的一部分 例 的自由存储 区 并由C语言的动态分配函数malloc 和free 来管理 利用函数malloc 为每个新产生的串分配 一块实际串长所需的存储空间 若分配成功 则返回 一个指向起始地址的指针 作为串的基址 同时 为 了以后处理方便 约定串长也作为存储结构的一部分 例 ch char malloc len sizeof char 申请分配一个串长度为申请分配一个串长度为len 的存储空间 的存储空间 二 串的堆分配存储表示二 串的堆分配存储表示 串的堆分配存储表示 P75
13、typedef struct char ch int length HString 通常 C语言中提供的串类型就是以这种 存储方式实现的 系统利用函数malloc 和 free 进行串值空间的动态管理 为每一个 新产生的串分配一个存储区 称串值共享的存 储空间为 通常 C语言中提供的串类型就是以这种 存储方式实现的 系统利用函数malloc 和 free 进行串值空间的动态管理 为每一个 新产生的串分配一个存储区 称串值共享的存 储空间为 堆堆 C语言中的串以一个空字符为结束符 串C语言中的串以一个空字符为结束符 串 长是一个隐含值 长是一个隐含值 这类串操作这类串操作实现的算法实现的算法为
14、为 先为新生成的串分配一个存储空间 然后先为新生成的串分配一个存储空间 然后 进行串值的复制 进行串值的复制 例如 串复制操作例如 串复制操作StrCopy pos不合法不合法 if T length T非空 则重新分配空间 插入非空 则重新分配空间 插入T if S ch char realloc S ch S length T length sizeof char exit OVERFLOW for i S length 1 i pos 1 i 为插入为插入T而腾出位置而腾出位置 S ch i T length S ch i S ch pos 1 pos T length 2 T ch 0
15、 T length 1 插入插入T S length T length return OK SubInsert 以上两种存储表示通常为高级程序设计语 言所采用 由于堆分配存储结构的串既有顺序 存储结构的特点 处理方便 操作中对串长又 没有任何限制 更显灵活 因此 在串处理的 应用程序中也常被选用 以上两种存储表示通常为高级程序设计语 言所采用 由于堆分配存储结构的串既有顺序 存储结构的特点 处理方便 操作中对串长又 没有任何限制 更显灵活 因此 在串处理的 应用程序中也常被选用 以下所示为只含最小操作子集的以下所示为只含最小操作子集的Hstring串 类型的模块说明 串 类型的模块说明 typ
16、edef struct char ch 若是非空串 则按串长分配存储区若是非空串 则按串长分配存储区 否则否则ch为为NULL int length 串长度串长度 HString 串的堆分配存储表示 串的堆分配存储表示 P76 基本操作的函数原型说明 基本操作的函数原型说明 Satus StrAssign Hstring 生成一个其值等于串常量生成一个其值等于串常量chars的串的串T int StrLength Hstring S 返回返回S的元素个数 称为串的长度的元素个数 称为串的长度 int Strcompare Hstring S Hstring T 若若S T 则返回值 则返回值 0 若若S T 则返回值 则返回值 0 若若S T 则返回值 则返回值T 则返回值 则返回值 0 若若S T 则返回值 则返回值 0 若若S T 则返回值 则返回值 0 for i 0 i S length i if S ch i T ch i return S ch i T ch i return S length T length Strcompare Satus ClearString Hs
