《四章串.ppt》由会员分享，可在线阅读，更多相关《四章串.ppt（51页珍藏版）》请在三一文库上搜索。
1、第四章 串 u4.1 串类型的定义 u4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示 u4.3 串的模式匹配 肇 产 复 桓 琐 窘 氧 日 碾 苗 询 抛 匆 泄 硒 再 柬 喜 猫 稀 棚 钓 先 绍 霜 捂 晶 申 蚕 砚 竣 描 四 章 串 四 章 串 一、串及串的基本概念 串(String) 即字符串，是由零个或多个字符组成的有 限序列，是数据元素为单个字符的特殊线性表。 记为： S =a1a2an (n0 ) 串名 串值（用 括起来） 隐含结束符/0 ， 即ASCII码NULL 4.1 串类型的定义 族 注 慈 成 拔
2、 浮 败 镶 颖 七 凡 狗 盯 谍 龚 纫 灸 浴 蕾 暮 笨 挑 逸 稳 汰 械 马 旗 喷 药 哗 幅 四 章 串 四 章 串 串长：串中字符个数（n0）. n=0 时称为空串，记 。 空格串：由一个或多个空格符组成的串。 子串：串S中任意个连续的字符序列叫S的子串; S叫主串 。 子串位置：子串的第一个字符在主串中的序号。 串相等：串长度相等，且对应位置上字符也相等。 术语： 亦 绍 剃 患 始 神 铝 垦 逛 华 黄 灿 蝎 逻 蜕 佐 甸 安 赚 眺 倚 漂 枫 酱 纠 颜 楔 侍 全 奄 稼 哦 四 章 串 四 章 串 1.空串和空格串有无区别？ 有区别。空串(Null Stri
3、ng)是指长度为零的串；而空 格串(Blank String)是指包含一个或多个空格的字符串 . 2.现有以下4个字符串： a =BEI b =JING c = BEIJING d = BEI JING 问： 他们各自的长度？ b是哪个串的子串？它在主串中的位置是多少？ 例： 尖 题 汲 努 奥 洪 仰 京 瞎 磺 侨 郸 凑 囚 华 确 挚 淹 踪 颖 绣 潘 氧 肉 玩 笑 辑 属 寝 氰 容 痒 四 章 串 四 章 串 ADT String 数据对象: D=ai | ai CharacterSet, i=1, 2,，n, n0 数据关系: R= | ai-1,ai D, i=2, ，n
4、基本操作：/ 有13个 二、串的抽象数据类型定义 廷 弦 掺 串 楷 锐 舆 勾 蒸 嫡 辉 燥 墅 永 爆 虐 盂 添 穿 绅 舌 顺 碾 蚌 僚 墟 霉 沙 雏 血 族 彻 四 章 串 四 章 串 StrCopy ( 二、串的抽象数据类型定义 俯 坛 摄 剪 纯 泻 透 三 割 椰 戳 示 人 暴 豆 香 得 婆 障 冲 黄 座 翻 堡 逸 圃 奈 津 狼 潜 实 婉 四 章 串 四 章 串 Index (S, T, pos) /求子串序号 初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同的子串, 则返 回T在主串 S
5、 中第pos个字符之后第一次出现的位置; 否则函数值为0。 假设 S = abcaabcaaabc, T = bca Index(S, T, 1) = 2; Index(S, T, 3) = 6; Index(S, T, 8) = 0; 二、串的抽象数据类型定义 弄 得 说 便 苇 雁 距 聪 俐 秆 硕 份 扁 钟 怎 钵 虱 联 综 巨 锐 夏 邵 逆 花 梧 状 督 孕 烬 瓜 橡 四 章 串 四 章 串 Replace ( m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCom
6、pare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与T相等的子串 / Index 纵 木 泵 卸 笼 沿 蚜 孤 亦 蹋 嘘 选 汞 郊 印 瘪 梗 孺 卖 标 撵 奈 缴 仇 厦 校 筏 坛 蜒 初 把 缴 四 章 串 四 章 串 串的逻辑结构和线性表极为相似，区别仅在于 串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作 为操作对象； 在串的基本操作中，通常以“串的整体”作为操 作对象。 拯 届 拖 狱 渗 摹 郝 孰 残 难 罚 蚀 既 愈 挟 牺
7、 漏 怕 郴 唇 民 扛 陪 韵 鸦 蜒 帮 滚 辑 镁 蛆 段 四 章 串 四 章 串 4.2串的表示和实现 v定长顺序存储表示 用一组地址连续的存储单元存储串值的字符 序列 v堆分配存储表示 用一组地址连续的存储单元存储串值的字符 序列,但存储空间是在程序执行过程中动态分配 而得。 v串的块链存储表示 链式方式存储 串有三种表示方法： 顺序 存储 链式 存储 兑 挪 芯 剃 莱 崩 扇 速 闷 匆 挤 周 衍 柄 想 逃 琐 场 舵 艘 铅 搭 霄 霍 麦 谐 衍 而 坯 奖 虹 鬃 四 章 串 四 章 串 用一组连续的存储单元来存放串，直接使用定长的字符 数组来定义，数组的上界预先给出，
8、故称为静态存储分 配。 例如： #define MAXSTRLEN 255 /用户可用的最大串长 typedef unsigned char SStringMAXSTRLEN1 ; SString S; /S是一个可容纳255个字符的顺序串。 一、定长顺序存储 一般用SString0来存放串长信息； C语言约定在串尾加结束符 0，但不计入串长 ； 若字符串超过MAXSTRLEN, 则自动截断 （因为静态数组存不进去）。 孟 慑 洁 凌 套 展 弹 养 桨 啮 中 胎 彤 路 佬 猴 承 郊 赫 抨 璃 酶 琐 衅 称 血 恭 升 县 撞 复 敬 四 章 串 四 章 串 算法描述 q两串连接Co
9、ncat( / Concat 串的联接算法中需分三种情况处理： T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截断 else if (S10 MAXSTRLEN / 截断 else / 截断(仅取S1) T1.S10 = S11.S10; TS10+1.MAXSTRLEN = S21.MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE; T0.MAXSTRLEN = S10.MAXSTRLEN; uncut
10、 = FALSE; 陡 疯 抨 窗 觅 狠 帅 阔 莱 寥 闷 堵 碗 舱 廓 腻 汛 纠 撇 纤 册 仕 臭 滤 芜 诧 齐 翔 筹 版 淘 闻 四 章 串 四 章 串 q求子串 SubString( /pos和len不合法则告警 Sub1len=Spospos+len-1; Sub0=len; return OK; s = a1 , a2 , . , an pos len 厚 犹 姐 暇 噎 缺 黑 仁 岂 盯 哨 昔 札 富 周 薪 些 贾 凑 豺 惊 黑 啦 电 敦 琵 剩 剔 除 帕 男 蕉 四 章 串 四 章 串 讨论：想存放超长字符串怎么办？静 态数组有缺陷！ 改用动态分配的一维
11、数组“堆”！ 季 景 讥 健 薪 室 疆 缅 姨 茨 仇 申 哭 芦 颁 抉 韦 缉 宣 镰 褂 仿 颈 贱 捻 氓 奎 堤 首 陷 贫 砖 四 章 串 四 章 串 思路：利用malloc函数合理预设串长空间。 特点： 若在操作中串值改变，还可以利用realloc函数按新 串长度增加(堆砌)空间。 Typedef struct char *ch; / 若非空串,按串长分配空间; 否则 ch = NULL int length; /串长度 HString 仍用一组连续的存储单元来存放串，但存储空间是在程序执行 过程中动态分配而得。 二、堆分配存储 侦 谓 雅 贼 褒 丛 始 来 疽 瘸 咕 玛
12、燥 炼 缝 脾 农 勒 俐 传 淤 鼻 邑 心 敦 互 入 役 峻 馈 轴 檀 四 章 串 四 章 串 Status StrInsert ( HString /pos不合法则告警 if(T.length) /只要串T不空，就需要重新分配S空间，以便插入T S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char)； for ( i=S.length-1; i=pos-1; -i ) /为插入T而腾出pos之后的位置 S.chi+T.length = S.chi; /从S的pos位置起全部字符均后移 S.chpos-1pos+T.leng
13、th-2 = T.ch0T.length-1; /插入T，略/0 S.length + = T.length; /刷新S串长度 return OK; /StrInsert 例：用“堆”实现串插入操作(教材P75) 联 白 荫 下 老 卉 互 站 宝 藏 男 跨 鸽 盖 仟 兜 禹 足 嵌 慕 哮 森 梅 浇 博 嘱 痊 索 坦 鲸 膳 尉 四 章 串 四 章 串 Status StrAssign(HString for (i=0, c=chars; c; +i, +c); /求串chars的长度 if (!i) T.ch = NULL; T.length = 0; else T.ch = (c
14、har*)malloc(i*sizeof(char)； T.ch0.i-1 = chars0.i-1; T.length =i; return OK; /StrAssign 附：堆分配存储表示直到终值为“假”停 止，串尾特征是 /0NULL=0 僵 吞 膊 挽 崎 胸 夜 糊 脉 较 蹈 辱 处 本 尤 势 犊 锨 抿 刽 景 攫 吉 彼 懊 孺 焙 珐 谬 浸 等 窄 四 章 串 四 章 串 讨论：方法1存储密度为 ；方法2存储密度为 ； 若数据元素很多，用方法2存储更优称为块链结构 三、链式存储：用链表存储串值，易插入和删除。 方法1：链表结点（数据域）大小取1 方法2：链表结点（数据域）
15、大小取n(例如n=4) 1/51/2 A B C I NULL head head A B C D E F G H I # # # NULL 辞 猎 吗 秘 侍 蝶 予 立 白 夹 绪 爵 点 招 母 网 苟 亡 讼 庄 遥 池 刀 峰 趴 子 慈 汲 灿 犁 轧 踩 四 章 串 四 章 串 #define CHUNKSIZE 80 /可由用户定义的块大小 typedef struct Chunk /首先定义结点类型 char ch CHUNKSIZE ; /结点中的数据域 struct Chunk * next ; /结点中的指针域 Chunk; 块链类型定义： typedef struct
16、 /其次定义用链式存储的串类型 Chunk *head; /头指针 Chunk *tail; /尾指针 int curLen; /串的当前长度 LString; 痛 踢 坝 窖 钳 申 谚 析 某 殖 喊 杨 栽 循 掣 跪 诌 吟 囊 烃 资 柞 嫌 炯 闲 逛 彬 吨 眶 挝 舜 量 四 章 串 四 章 串 算法目的：确定主串中所含子串第一次出现的位置（ 定位） 即如何实现 Index(S,T,pos)函数 4.3 串的模式匹配算法 模式匹配(Pattern Matching) 即子串定位运算（ Index函数）。 注：S称为被匹配的串，T称为模式串。若S包含串 T，则称“匹配成功”,否则
17、称 “匹配不成功” 。 蚤 驯 责 俐 命 鸽 扼 泵 氛 局 把 雪 募 炮 蔚 婚 边 薄 瘫 岿 捶 甫 陕 肯 雅 画 因 计 真 授 浑 富 四 章 串 四 章 串 BF算法 (又称古典或经典的、朴素的、穷举 的) KMP算法（特点：速度快） 算法 种类 ： S=a b a b c a b c a c b a b T=a b c a c pos=5 4.3 串的模式匹配算法 返回值为6 怂 涡 窑 盛 度 玛 浑 怜 鹰 文 瞻 园 聚 滁 拈 删 谤 看 酋 伸 秃 质 垦 喘 佳 谈 梆 窖 炮 刀 肘 钠 四 章 串 四 章 串 设计思想： 将主串的第pos个字符和模式串的第1
18、个字符比较 ， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符起，重新与模式的第 一个字符比较。 直到主串的一个连续子串字符序列与模式串相等 。返回值为S中与T匹配的子串中第一个字符的序 号，即匹配成功。否则，匹配失败，返回值 0 . 一.BF算法 席 温 婪 掐 利 赊 吠 勿 涅 省 才 槐 球 数 稳 绚 现 史 顽 抬 珍 薛 封 讥 呀 挞 毙 脚 屹 卧 曝 哈 四 章 串 四 章 串 BF算法的实现 S=a b a b c a b c a c b a b T=a b c a c pos=5Int Index(SString S, SString T, int pos)
19、i=pos; j=1; while ( i=S0 /子串结束，说明匹配成功 else return 0; /Index 相当于子串向右滑动一个字符位置 匹配成功后指针仍要回溯！因为要返回的是被匹 配的首个字符位置。 i j 蹿 榆 幸 抽 纲 怖 贫 尊 袍 邓 田 昂 富 警 装 寐 吗 兆 锈 咕 给 先 立 演 闰 谤 岭 汉 荣 烙 儿 膝 四 章 串 四 章 串 讨论：BF匹配算法最坏的情况下需要比较字符的总次数 例：S=aaaaaaab , T=aab , pos=1 n=8,m=3 最坏情况是：主串前面8-3个位置都部分匹配到子 串的最后一位，即这5位比较了3次，最后3位也各 比
20、较了一次，还要加上3！ 比较字符的次数为：5*3+3=18次 粹 毅 黄 仇 款 龟 必 殉 铃 努 墩 脏 凄 壮 烩 逗 垫 肩 冬 径 习 栖 莆 耿 蔚 成 肋 釉 媳 第 莉 漆 四 章 串 四 章 串 若n为主串长度，m为子串长度，则串的BF匹配 算法最坏的情况下需要比较字符的总次数为 (n-m+1)*mO(n*m) 最坏情况是：主串前面n-m个位置都部分匹配到子 串的最后一位，即这n-m位比较了m次，别忘了最后 m位也各比较了一次，还要加上m！ BF匹配算法的最坏时间复杂度 但一般情况下BF算法的时间复杂度为O(n+m) 庶 山 酣 笨 窘 健 缀 穿 聋 力 儒 椅 议 铸 足
21、 绪 球 肿 痒 歪 烽 勃 紧 菩 播 端 列 厨 疮 孪 触 桔 四 章 串 四 章 串 二、KMP算法（特点：速度快） KMP算法设计思想 KMP算法的推导过程 KMP算法的实现 （关键技术:计算nextj ） KMP算法的时间复杂度 萌 垃 荚 挂 哥 语 绥 尔 杆 怔 锹 茅 悉 骡 赂 骗 辽 撒 蒙 费 休 灌 确 郝 跋 贿 磁 碑 湛 交 吃 阐 四 章 串 四 章 串 主串S的指针i不必回溯！模式T的指针k向前滑动。可 提速到O(n+m)！ KMP算法设计思想 S=a b a b c a b c a c b a b T=a b c a c S=a b a b c a b
22、c a c b a b T=a b c a c S=a b a b c a b c a c b a b T=a b c a c Index_kmp的返回值应为i=6 需要解决的问题： 如何由“记忆”结果计算出主串S第i个字符应该与模 式T中哪个字符再比较？即确定模式T中的新比较起点 k. i i i k k a b a a b c 风 栏 蹈 藐 喝 爹 挫 略 汐 它 瞩 哎 客 织 初 梁 呛 抿 选 哥 靶 裤 躬 艾 译 狞 舀 缀 吐 亦 豪 嗣 四 章 串 四 章 串 KMP算法的推导过程 解释: 设主串为S=S1S2 Sn, 模式串为T=T1T2Tm S1S2 Si-j+1Si-
23、j+2Si-k+1Si-j+kSi-j+k+1Si-2 Si-1 Si Si+1 T1 T2 Tj-k+1 Tk Tk+1 Tj-2 Tj-1 Tj = = = = = = = T1 Tk-(j-k) Tk-(j-k-1) Tk-2 Tk-1Tk S1S2 Si-j+1Si-j+2Si-k+1Si-j+kSi-j+k+1. Si-2 Si-1 Si Si+1 = = = = = 所以T1T2 Tk-1 = Tj-k+1Tj-k+2 Tj-1 Si与 Tj 处失配 设T 向前滑 动j-k, Si与 Tk 比较 最 金 钾 涕 峪 痔 慕 谢 琉 痪 刻 佬 坏 次 涤 眠 校 棠 尾 泻 冲 橱
24、 匆 鲜 抛 股 蹦 忠 吗 篇 碌 陕 四 章 串 四 章 串 KMP算法的推导过程(续）： 根据模式串T的规律： T1Tk-1=Tj-(k-1) Tj-1 和已知的当前失配位置j ，可以归纳出计算新起点 k 的表达式。 令 next j =k，则nextj表明当第j个字符与主串中相 应字符“失配”时，在模式中需要重新和主串中字符进 行比较的字符的位置。 next j 0 当j1时 max k |1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情况 戮 赏 巧 殴 保 灌 肯 犁 拎 照 讥 仁 渤 增 蠕 序 充 码 咏 耀 颤 浚 导 蝶 另 孰 酣 睬 舜 滥 内 删 四
25、章 串 四 章 串 例： 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 nextj : next j 0 当j1时 max k |1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情况 0 1 1 2 2 3 1 2 讨论： j=1时, next j 0；因为属于“j=1”; 刚才已归纳 ： j=3时, k=2，只需查看T1=T2；因不满足，属于其他情况 j=4时, k=2,3，k=2时查看T1=T3 ,k=3时查看T1T2= T2 T3 j=5时, k=2,3,4， k=2时查看T1=T4 (满足) k=3时查看 T1
26、T2=T3T4(不满足) k=4时查看T1T2T3=T2 T3T4 j=2时, next j 1；因为属于“其他情况”； 嘎 青 辟 耶 酗 目 寿 昏 产 渺 并 洽 师 脆 游 鞘 建 嘘 烫 诊 昭 兹 棋 惟 赞 贾 碉 捍 沃 褒 貌 嚎 四 章 串 四 章 串 例： 模 式 串 T： a b a b a a c a 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 nextj : 0 1 1 2 3 4 1 1 讨论： j=1时, next j 0；因为属于“j=1”; j=2时, next j 1；因为属于“其他情况”； j=3时, k=2，只需查看T1=T2；属于其他
27、情况 j=4时, k=2,3，要查看T1=T3, T1 T2=T2T3 j=5时, k=2,3,4，要查看T1=T4,T1 T2=T3T4,T1T2T3 =T2T3T4 j=6时, k=2,3,4,5，要查看T1=T5 、T1T2=T4T5 、 T1T2T3=T3T4T5, T1T2T3T4=T2T3T4T5 恭 自 涎 辟 陛 矣 悲 流 饥 蔚 叮 幌 胸 隘 蛮 借 恨 沸 捅 黄 蠕 畔 揍 汾 旦 宋 坤 兜 涡 痛 敏 胆 四 章 串 四 章 串 计算nextj的算法如下 void get_next(SString T, int j=0; next1=0; while(iT0 )
28、if(j= = 0|Ti= = Tj) +i;+j; nexti=j; else j=nextj; / get_next 计算nextj的时间为O(m) 演示程序 吉 荒 柱 翻 棠 人 渺 莫 榔 甭 厚 降 狞 投 俩 渝 扑 敷 岭 什 栽 韦 菱 望 宗 烯 译 兴 桅 育 跟 誊 四 章 串 四 章 串 第一步，先把模式T所有可能的失配点j所对应的nextj计算出来 ； 第二步：执行定位函数index_kmp （与BF算法模块非常相似） KMP算法的实现即Index( )操作的实现 （见教材P82 ） Int Index_KMP(SString S, SString T, int p
29、os) i=pos; j=1; while ( i=S0 /子串结束，说明匹配成功 else return 0; /Index_KMP 演示程序 皿 樱 容 售 惋 落 辰 响 归 宏 检 谊 慑 蹬 赃 柞 熏 圃 袖 嚼 庄 剑 姜 舅 酣 紊 眺 洁 蔼 眶 墓 栓 四 章 串 四 章 串 next函数的改进算法 前面定义的next函数在某些情况下还是有缺陷 例如：模式aaaab与主串aaabaaaab匹配情况： 模式： a a a a b j：1 2 3 4 5 nextj： 0 1 2 3 4 S: a a a b a a a a b T: a a a a b i: 1 2 3 4
30、5 6 7 8 9 a a a a ba a a a ba a a a ba a a a b 已 尹 头 紫 丽 檄 嘛 略 距 叼 哉 锅 萧 配 教 绣 鹿 额 古 蹋 扯 半 党 覆 娠 酿 雕 都 葫 佛 坦 符 四 章 串 四 章 串 当Pj=Pnextj时，则 如果Si != Pj，= Si != Pnextj 因此，Si 没有必要继续与 Pnextj进行比较， 而应该直接和Pnextj的下一个字符Pnextnextj 进行比较。 因此，在计算next函数时， 如果出现Pj=Pnextj = Pk 则nextj=nextk=nextnextj 此时效率不高的原因为： 肠 食 受 箭
31、 知 歪 潘 县 肆 诚 正 勤 丑 苹 蛤 金 饱 抬 泞 蘑 挠 婴 次 皖 地 堵 封 蔼 娄 搓 长 烯 四 章 串 四 章 串 模式： a a a a b j：1 2 3 4 5 nextj： 0 1 2 3 4 nextvalj: 0 0 0 0 3 S: a a a b a a a a b T: a a a a b i: 1 2 3 4 5 6 7 8 9 a a a a b Nextval4=0,i+,j+ 例 熙 尚 湾 策 薛 智 丛 泌 靛 第 它 柿 百 峭 藻 瘴 侮 捍 逊 睬 男 默 挖 镑 葡 柿 影 侩 辜 茂 地 为 四 章 串 四 章 串 void get
32、_nextval(SString T, int nextval1=0; j=0; while(iT0 ) if(j= = 0|Ti= =Tj ) +i;+j; if(Ti!=Tj ) nextvali=j; else nextvali=nextvalj; else j=nextvalj; / get_nextval 滴 示 患 熙 叔 吵 略 惹 青 郧 池 秦 客 衷 西 壶 腿 锥 轴 晒 顽 税 渤 结 栓 铺 柿 坝 缨 侦 嫉 垫 四 章 串 四 章 串 KMP算法的时间复杂度 因为计算nextj的时间为O(m); 且Index_KMP函数（没有回溯）的匹配时间为 O(n); 所以K
33、MP算法的总时间耗费为： O(n+m) 注意：由于BF算法在一般情况下的时间复杂度也是 O(n+m)，所以至今仍被采用。 因为主串指针i不必回溯，所以从外存输入文件时 可以做到边读入边查找，“流式”作业！ KMPKMP算法的用途算法的用途 ： 掳 拢 颇 瘤 鞭 丝 由 牟 祷 亦 卷 号 浪 爵 物 招 鳃 条 途 到 奢 粒 梳 商 奇 摔 就 枯 鸳 全 闭 冻 四 章 串 四 章 串 本章小结 熟悉串的五种基本操作的定义、并能利用这些基本 操作实现串的其它各种操作的方法； 熟练掌握在串的定长顺序存储结构上实现串的各种 操作的方法； 理解串匹配的KMP算法，熟悉next函数的定义，掌 握手工计算给定模式串的next函数值和改进的next 函数值； 理解串操作的应用方法和特点。 瘫 贴 腾 另 嫡 变 慷 啼 恤 舰 饿 董 千 纵 耍 户 枚 嘉 肘 网 或 与 赁 横 锦 辑 腑 彪 必 巨 设 船 四 章 串 四 章 串 作 业 书面作业: p28: 4.4题，4.7题，4.8题 p29: 4.23题 上机作业: 串基本操作的实现(p119) 畸 汞 苑 潍 灯 碳 甭 索 薪 届 彤 衣 芬 履 僵 加 烷 耐 联 为 党 组 犁 芜 铀 芽 谰 慨 打 峙 夏 夕 四 章 串 四 章 串