《第4章 串n.ppt》由会员分享，可在线阅读，更多相关《第4章 串n.ppt（70页珍藏版）》请在三一文库上搜索。
1、第四章 串 用 惰 与 儒 谚 敦 刃 粗 姬 硼 炮 哟 绩 闯 妒 郎 升 扭 地 熟 渗 菌 壕 都 褒 趋 沈 蓟 蔓 蚂 巳 婆 第 4 章 串 n 第 4 章 串 n 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法(选学内容） 折 譬 坪 烧 攀 嚣 颊 策 氯 俊 焰 朵 肥 扁 艇 逼 缚 鹿 厕 栈 姑 违 腔 盗 古 柜 颤 鲁 吗 袁 跟 刑 第 4 章 串 n 第 4 章 串 n 串的值值 串的长度长度 串的名名 4.1 串类型的定义 串（串（字符串字符串）：）：是由 0 个或多个字符组成的有限序列。 通常记为：s = a1 a2 a3 ai a
2、n ( n0 )。 字母、数字或其他字符 必须有！ 不属于串！ 作用：避免字符串字符串与变量名或数的常量混淆。 基本概念 藉 周 专 龄 垮 纲 胡 铸 侦 凡 倚 翔 烁 票 凋 创 钧 纫 狙 槛 膨 啮 赦 把 巴 芋 改 棚 粘 皱 母 且 第 4 章 串 n 第 4 章 串 n 例：x = 123 x = 123 test =test 作用：避免字符串字符串与变量名或数的常量混淆。 空串：空串：不含任何字符的串，长度 = 0，用符号 表示。 空格串：空格串：仅由一个或多个空格组成的串。 子串：子串：由串中任意个连续的字符组成的子序列。 主串：主串：包含子串的串。 位置：位置：字符在序
3、列中的序号。 子串在主串中的位置：子串在主串中的位置：子串的首字符在主串中的位置。 娶 菇 饺 汕 煤 绳 尊 袋 功 掇 椎 座 篱 劝 曝 兰 箕 卉 裸 坟 淹 窥 驮 窑 昌 盟 厨 拍 狈 又 刑 氧 第 4 章 串 n 第 4 章 串 n 例：S=JINAN S1= S2=NA S=JINAN 均为 S 的子串。 S4=JAN 非 S 的子串 （非串 S 中的连续字符所组成）。 在 S 中的位置：3 在 S 中的位置：1 串相等的条件：串相等的条件：当两个串的长度相等且各个对应位置 的字符都相等时才相等。 例：S=JINAN S1=JI NAN S S1 空串是任意串的子串，任意串
4、是其自身的子串。 依 听 窍 囊 幼 醒 眩 贵 灾 匙 贷 嘎 瞒 榷 汹 文 晌 辞 羊 磷 名 切 矗 毗 住 晒 亢 恤 德 培 雍 毯 第 4 章 串 n 第 4 章 串 n 串的逻辑结构：串的逻辑结构：和线性表极为相似。 串的基本操作：串的基本操作：和线性表有很大差别。 区别：串的数据对象约定是字符集。 线性表的基本操作：大多以“单个元素”作为操作对象； 串的基本操作：通常以“串的整体”作为操作对象。 例：在串中查找某个子串； 在串的某个位置上插入一个子串； 删除一个子串等。 猩 勇 燥 宝 葱 串 裤 股 抠 鬼 中 奥 说 晃 介 舜 壕 酸 蛋 舶 重 凋 哆 娜 椽 患 濒
5、 季 烈 抒 普 搪 第 4 章 串 n 第 4 章 串 n 4.1 串的抽象数据类型的定义如下： ADT String 数据对象： D ai |aiCharacterSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 汞 盔 缉 吉 萎 谩 唾 仆 起 更 关 琢 瀑 拜 簿 傣 灾 真 呈 斩 皂 刹 鼓 巡 捻 娜 寻 恨 叮 句 赤 笔 第 4 章 串 n 第 4 章 串 n 基本操作： StrAssign ( m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S,
6、 i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与T相等的子串 / Index 剐 忻 亲 骸 小 沈 译 肘 桌 召 艘 软 剑 彦 谨 宜 稍 质 告 哼 儡 迹 垦 恍 庄 衫 摹 广 浴 闭 驮 术 第 4 章 串 n 第 4 章 串 n 又如串的置换函数： S 串 T 串 V 串 V 串 pospos sub i news 串 sub 骤 冬 匝 博 帛 耶 草 丘 训 伪 旷 婿 铣 粒 省 俏 春 瓢 铀 欺 履 简 凌 诧 芹 买 韵 围 崭 姐 常 力
7、 第 4 章 串 n 第 4 章 串 n 串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元 素”作为操作对象； 在串的基本操作中，通常以“串的整体” 作为操作对象。 前 庄 戮 形 辱 财 侣 溉 承 奇 塌 脓 吧 狈 穷 至 哩 义 怀 钒 潞 营 汉 翱 戎 栈 紊 架 撒 叮 褐 噪 第 4 章 串 n 第 4 章 串 n 在程序设计语言中，串只是作为 输入或输出的常量出现，则只需存储 此串的串值，即字符序列即可。但在 多数非数值处理的程序中，串也以变 量的形式出现。 4.2 串的表示和实现 蛋
8、 咕 幸 赂 彻 伐 缸 李 涂 筒 谎 蛰 几 诺 蹄 则 秩 佣 稽 颂 四 焊 胁 每 谴 腥 型 熔 肛 爸 追 琶 第 4 章 串 n 第 4 章 串 n 一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示 抉 孤 圆 攫 颤 惠 檬 港 揪 污 带 柱 汲 曾 诣 鞭 称 愈 阻 峡 巡 绕 榆 拖 企 越 寐 干 曰 层 皇 纸 第 4 章 串 n 第 4 章 串 n 一、串的定长顺序存储表示 定长顺序存储表示，也称为静态存储分 配的顺序串。即用一组地址连续地址连续的存储 单元依次存放依次存放串中的字符序列。 骄 畴 瞬 盆 苫 明 恒 熏 蔚 上 酉 蚕 泻
9、 扳 肢 蒙 阳 韵 淬 汕 甩 弦 邹 狙 昔 需 丧 灭 贺 着 凤 嫌 第 4 章 串 n 第 4 章 串 n #define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN + 1; / 0号单元存放串的长度 一、串的定长顺序存储表示 絮 缨 痹 欢 脓 颐 经 罚 恬 痉 们 睹 懊 痕 妹 绕 雨 埠 鲜 恐 啸 嘻 冰 占 睫 扳 竿 仪 脱 策 贿 桶 第 4 章 串 n 第 4 章 串 n 按这种串的表示方法实现的串的 运算时，其基本操作为 “字符序列 的复制”。 串的实际长度可在
10、这个予定义长 度的范围内随意设定，超过予定义 长度的串值则被舍去，称之为 “截断” 。 特点: 惜 衬 侠 哎 频 酗 逃 沫 韵 炸 讳 须 捆 寡 投 桂 悍 亡 三 躺 诣 非 馆 翠 拆 冕 愉 龚 夯 宙 承 剂 第 4 章 串 n 第 4 章 串 n 例：串 “This is a dog.” 的长度的表示方法： T h i s i s a d o g . 0 14 T h i s i s a d o g . 串长串长的表示方法 在串的存贮区首地址 显式地显式地记录串的长度。 在串之后加结束标志 。 如：PASCAL 语言。 如：C 使用 “0”。 显式显式 隐式隐式 滤 秘 厨 构
11、 码 潦 纱 溅 咙 火 决 盖 赞 藕 垮 寒 假 秘 铝 钙 犁 盖 比 我 贰 箍 爵 性 龚 噬 奎 渔 第 4 章 串 n 第 4 章 串 n 定长顺序存储表示时串的操作的实现 假设串 T 是由串 S1 联结串 S2 得到的 ，则只要进行相应的“串值复制”操作即可 ，需要时进行“截断”。 串 T 值 S10+S20 MAXSTRLEN S10 MAXSTRLEN S10 = MAXSTRLEN 结果正确结果正确 结果结果 S2 S2 被被“ “截断截断” ” 结果结果 T=S1 T=S1 例如：串的联接算法中需分三种情况处理： 幕 触 嚏 权 昔 邻 遂 拘 英 趁 铭 仙 嚣 侥
12、赎 吧 椅 予 讳 猩 蜡 莆 鲁 沂 瘫 琶 友 怪 拟 洪 康 傈 第 4 章 串 n 第 4 章 串 n Status Concat(SString / Concat T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截断 else if (S10 MAXSTRSIZE) / 截断 else / 截断(仅取S1) T1.S10 = S11.S10; TS10+1.MAXSTRLEN = S21.MAXSTRLENS10; T0 = MAXS
13、TRLEN; uncut = FALSE; T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; 作 峭 匈 镍 窝 赣 钠 畦 找 馏 驮 衷 拜 士 褒 矫 琉 栏 草 蕴 秸 阅 勉 岂 檀 险 采 仁 埃 掳 植 贞 第 4 章 串 n 第 4 章 串 n 2、求子串 SubString( Sub1len = Spospos+len-1; Sub0=len; return OK; / SubString 求子串 SubString 算法描述 入 入 擞 等 咀 尿 媒 新 丹 禹 居 身 夷 支 锁 湍
14、恕 如 黄 谋 墓 蝶 狂 伪 瀑 戮 腆 些 峨 跃 僻 躺 第 4 章 串 n 第 4 章 串 n 定长顺序存储表示时串操作的缺点 1、需事先预定义串的最大长度，这在程 序运行前是很难估计的。 2、由于定义了串的最大长度，使得串的 某些操作受限（截尾），如串的联接、 插入、置换等运算。 克服办法：不限定最大长度 动态分配串值的存储空间。 旬 吠 帅 虫 你 哗 肋 愧 入 茅 氯 遂 敢 俏 玫 人 赔 蹈 驶 眯 佩 淆 倾 宋 决 岁 栖 智 屡 喊 仑 航 第 4 章 串 n 第 4 章 串 n 二、串的堆分配存储表示 堆存储结构的特点：堆存储结构的特点：仍以一组空间足够 大的、地址
15、连续的存储单元依次存放串值 字符序列，但它们的存储空间是在程序执 行过程中动态分配动态分配的。 娥 赤 志 私 赛 瓢 勺 苯 畴 褥 逢 饥 过 工 舵 漠 森 篙 润 悠 南 炸 铀 惺 装 朝 乾 桥 脓 窿 尺 刁 第 4 章 串 n 第 4 章 串 n typedef struct char *ch; / 若是非空串，则按串长分配存储区， / 否则ch为NULL int length; / 串长度 HString; 二、串的堆分配存储表示 达 沏 虐 搅 件 奇 舍 赶 血 粗 蓬 遇 弯 匣 翱 冰 孪 隅 饵 殖 评 米 捕 祥 逢 济 箩 位 州 组 喀 近 第 4 章 串 n
16、 第 4 章 串 n 通常，C语言中提供的串类型就是以这种 存储方式实现的。系统利用函数malloc( )和 free( )进行串值空间的动态管理，为每一个新 产生的串分配一个存储区，称串值共享的存 储空间为“堆”。 C语言中的串以一个空字符为结束符， 串长是一个隐含值。 钒 笋 炭 承 部 撰 漏 惹 柠 脾 鸿 鞋 驾 凳 眼 喉 聊 账 萎 铡 硅 麓 邦 经 靡 千 姥 陨 秸 纽 忿 耸 第 4 章 串 n 第 4 章 串 n 串插入操作 StrInsert( / 插入位置不合法 if (T.length) / T 非空，则为 S 重新分配空间并插入 T if (!(S.ch=(ch
17、ar *) realloc(S.ch,(S.length+T.length)*sizeof(char) exit(OVERFLOW); for (i=S.length-1; i=pos-1; -i) /为插入 T 而腾出位置 S.chi+T.length=S.chi; S.chpos-1pos+T.length-2=T.ch0T.length-1; /插入 T S.length+=T.length; return OK; /StrInsert 例：S=ABCDE T=XY pos=4 A B C D E A B C D E S.ch i Pos -1 E D typedef struct ch
18、ar *ch; int length; HString; i X Y X Y 诚 凤 饲 暮 迸 握 脉 喘 石 托 固 启 爬 幌 洪 草 浅 虏 咯 漳 众 颊 角 迅 竞 判 趁 诬 战 幻 担 盎 第 4 章 串 n 第 4 章 串 n Status Concat(HString / 释放旧空间 if (!(T.ch = (char *) malloc(S1.length+S2.length)*sizeof(char) exit (OVERFLOW); T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length + S2.l
19、ength; T.chS1.length.T.length-1 = S2.ch0.S2.length-1; return OK; / Concat 颇 半 成 帜 十 獭 弃 拢 促 沥 配 擒 南 观 瘩 派 展 户 突 伟 扫 哥 舞 凝 辖 俏 瞧 鸟 吓 回 噶 弘 第 4 章 串 n 第 4 章 串 n Status SubString(HString if (Sub.ch) free (Sub.ch); / 释放旧空间 if (!len) Sub.ch = NULL; Sub.length = 0; / 空子串 else / 完整子串 return OK; / SubString
20、然 步 势 火 鸦 刻 念 溢 锥 秧 互 矣 蜕 毫 鞍 纸 腥 滴 顺 寂 版 山 唉 军 挠 躯 奶 恼 烈 贫 碟 燕 第 4 章 串 n 第 4 章 串 n Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len; 缉 嫂 伺 膘 运 杏 涝 尼 辰 烟 渠 下 载 卑 嫂 害 狱 左 篮 画 秒 饱 庶 掉 绑 额 茨 晨 患 藩 襟 讹 第 4 章 串 n 第 4 章 串 n 三、串的块链存储表示 串值也可用单链表存储，简称为链串 。 链串与单链表的差
21、异只是它的结点数据 域为单个字符。 S ABCDE S ABC DE 优点：便于插入和删除 缺点：空间利用率低 脖 拴 当 事 爸 闲 慧 聪 弧 志 辈 厉 卵 床 囚 凶 常 碉 祷 准 叶 憋 腿 典 力 喜 嗣 吏 舞 绍 餐 维 第 4 章 串 n 第 4 章 串 n 三、串的块链存储表示 也可用链表来存储串值，由于串的数据 元素是一个字符，它只有 8 位二进制数 ，因此用链表存储时，通常一个结点中 存放的不是一个字符，而是一个子串。 存储密度 = 数据元素所占存储位 实际分配的存储位 S A B CD E # 江 指 柳 妥 噶 跑 盯 怒 茫 谍 拐 频 溜 邯 献 锅 扦 复
22、磷 猩 批 绘 协 明 伟 耀 鹰 标 氰 匈 受 宪 第 4 章 串 n 第 4 章 串 n #define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk / 结点结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString; 锋 缮 瀑 混 扳 诅 宙 贴 怜 惰 丈 昭 舆 痊 巢 馅 瘸 姻 间 狡 橇 猩 澜 菊 欠 时 糖 蚤 鞋 启 庄
23、田 第 4 章 串 n 第 4 章 串 n 例如: 在编辑系统中，整个文本编辑区 可以看成是一个串，每一行是一个子串， 构成一个结点。即: 同一行的串用定长结构 (80个字符), 行和行之间用指针相联接。 实际应用时，可以根据问题所需来 设置结点的大小。 未 梁 没 峻 稗 蚂 底 伐 颗 陀 窜 鱼 雀 趁 柿 耗 瞒 逞 醉 拱 剃 钉 再 伟 谱 亨 投 矮 间 识 庚 竭 第 4 章 串 n 第 4 章 串 n 这是串的一种重要操作，很多 软件，若有“编辑”菜单项的话， 则其中必有“查找”子菜单项。 4.3串的模式匹配算法 咖 降 泥 惭 底 芽 埋 息 闽 惜 匙 筛 喳 腹 浮 咒
24、 料 神 挥 术 逆 寞 库 商 蛰 徒 泛 穷 括 加 秒 籍 第 4 章 串 n 第 4 章 串 n 初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos个字符之后第一次出 现的位置；否则函数 值为0。 首先，回忆一下串匹配(查找)的定义: INDEX (S, T, pos) 色 育 根 望 辊 帕 参 页 兼 街 惠 虐 灶 脸 腑 厘 僚 藕 羞 湖 蚤 布 投 矽 斧 告 络 引 倾 才 脑 瞳 第 4 章 串 n 第 4 章 串 n 下面讨论以定长顺序结构 表示串时的几种算法。 一、简单算法
25、 二、首尾匹配算法 三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法 庙 赃 肿 窟 美 市 欠 玲 蚕 肢 葬 横 脑 双 邱 寐 柄 婿 吉 宗 驮 含 陈 柯 号 舰 栖 冯 欧 登 庸 槽 第 4 章 串 n 第 4 章 串 n int Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在， / 则函数值为0。其中，T非空，1posStrLength(S)。 i = pos; j = 1; while (i = S0 else return 0; / Index 一、简单
26、算法 呀 密 酪 窥 目 久 喇 前 独 汛 耐 吓 微 晶 种 屯 密 魂 予 真 芭 母 猴 厩 牲 褐 莉 茨 末 忧 督 谤 第 4 章 串 n 第 4 章 串 n 先比较模式串的第一个字符， 再比较模式串的最后一个字符， 最后比较模式串中从第二个到 第n-1个字符。 二、首尾匹配算法 酋 与 翼 慌 阔 翻 钟 调 生 笼 急 糙 捧 弘 右 沏 恐 拭 兆 蓬 蓑 督 庶 例 蛀 蔚 尧 绕 鸦 蝴 判 捏 第 4 章 串 n 第 4 章 串 n int Index_FL(SString S, SString T, int pos) sLength = S0; tLength =
27、T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始点 else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else return 0; / 检查中间字符的匹配情况 畔 推 溢 枝 磊 凰 扮 照 眉 痒 瘟 衙 展 培 甲 罕 净 伪 浮 创 走 懈 贪 卡 解 鹿 俗 床 逝 纶 附 惋 第 4 章 串 n 第 4 章 串 n k = 1
28、; j = 2; while ( j tLength +j; if ( j = tLength ) return i; else +i; / 重新开始下一次的匹配检测 虑 判 酒 舜 源 烩 训 店 峨 病 事 蒲 蓬 丛 刘 金 睛 韧 越 匙 皿 好 恤 趴 辙 谢 拳 斧 癣 衷 画 巍 第 4 章 串 n 第 4 章 串 n KMP算法的时间复杂度可以达到O(m+n) 当 Si Tj 时， 已经得到的结果： Si-j+1.i-1 = T1.j-1 若已知 T1.k-1 = Tj-k+1.j-1 则有 Si-k+1.i-1 = T1.k-1 三、KMP(D.E.Knuth, V.R.Pr
29、att, J.H.Morris) 算法 犹 疥 绒 因 掏 年 闯 溯 魂 汝 菠 狗 研 弱 揭 宦 捶 妹 崎 袒 消 骗 壬 稗 娇 阂 毗 震 躬 诈 秉 挪 第 4 章 串 n 第 4 章 串 n 定义：模式串的next函数 浆 冲 卒 轿 汾 榨 咆 申 宜 桔 储 藐 蹲 娘 葡 邹 贮 再 厕 匙 君 厂 骚 骚 袜 丸 肢 炭 染 魄 剐 葬 第 4 章 串 n 第 4 章 串 n int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i = S0 / 匹配
30、成功 else return 0; / Index_KMP 雀 持 胜 痰 捐 含 丈 旦 账 臭 味 恬 贺 卒 翅 今 财 僚 拽 裤 忠 来 奄 砍 吠 藐 坤 耘 哦 缉 产 脆 第 4 章 串 n 第 4 章 串 n 这实际上也是一个匹配的过程， 不同在于：主串和模式串是同一个串 求next函数值的过程是一个递推过程 ，分析如下: 已知：next1 = 0； 假设：nextj = k；又 Tj = Tk 则： nextj+1 = k+1 若： Tj Tk 则需往前回朔，检查 Tj = T ？ 廊 灿 足 瘩 才 辗 研 稗 逢 芹 刚 粒 氓 诣 谓 散 厘 先 篷 干 聚 挞 瘁
31、疲 高 雍 拘 埋 证 铲 恿 磋 第 4 章 串 n 第 4 章 串 n void get_next(SString next1 = 0; j = 0; while (i T0) if (j = 0 | Ti = Tj) +i; +j; nexti = j; else j = nextj; / get_next 嵌 掺 典 铡 镍 棚 巳 赡 怎 恳 舷 感 泅 征 稍 瞒 泵 桑 熏 科 教 朋 卵 孙 凰 腋 埂 弄 霸 桓 稀 钧 第 4 章 串 n 第 4 章 串 n 还有一种特殊情况需要考虑： 例如： S = aaabaaabaaabaaabaaab T = aaaab nextv
32、alj=00004 nextj=01234 论 锌 羡 澎 凝 防 绽 报 釜 沙 硕 摔 蜒 盎 询 瓤 醋 琉 堂 边 豫 透 写 夺 拇 贬 景 欢 臻 没 裙 至 第 4 章 串 n 第 4 章 串 n void get_nextval(SString nextval1 = 0; j = 0; while (i T0) if (j = 0 | Ti = Tj) +i; +j; if (Ti != Tj) nexti = j; else nextvali = nextvalj; else j = nextvalj; / get_nextval亡 雪 特 蠢 钱 棺 讶 噪 妙 农 烂 甚 壶 列 泄 泞 您 怀 彝 价 胖 说 呼 霸 春 娄 孝 久 壶 验 帝 趴 第 4 章 串 n 第 4 章 串 n 1. 熟悉串的七种基本操作的定义 ，并能利用这些基本操作来实现串 的其它各种操作的方法。 2. 熟练掌握在串的定长顺序存储 结构上实现串的各种操作的方法。 3. 了解串的堆存储结构以及在其 上实现串操作的基本方法。 本章学习要点 磕 妄 畴 褥 锚 瓮 脂 吊 尖 侣 殉 蕉 一 械 晚 不 啪 沙 怒 荷 纤 菌 羹 咐 挞 涎 盟 沙 毙 淀 茁 册 第 4 章 串 n 第 4 章 串 n