数据结构4_串.ppt

1 第四章串 2 本章目录 3 4 1串的定义 1 串的相关概念2 串的抽象数据类型定义3 串操作解析 4 微机上常用的字符集是标准ASCII码 由7位二进制数表示一个字符 总共可以表示128个字符 扩展ASCII码由8位二进制数表示一个字符 总共可以表示256个字符 足够表示英语和一些特殊符号 但无法满足国际需要 Unicode由16位二进制数表示一个字符 总共可以表示216个字符 即6万5千多个字符 能够表示世界上所有语言的所有字符 包括亚洲国家的表意字符 为了保持兼容性 Unicode字符集中的前256个字符与扩展ASCII码完全相同 串的数据对象 串的数据对象约束为某个字符集 5 串的相关概念 串 string 是由零个或多个字符组成的有限连续序列 即串是一串字符 一个非空串记为 S s1s2 sn 空串 nullstring 由零个字符组成的串 空格串 由一个或多个空格组成的串 子串 字符串中任意个连续的字符构成的子序列称为字符串的子串 空串是任何串的子串 主串 包含子串的字符串 位置 一个字符在序列中的序号称为该字符在串中的位置 子串在主串中的位置则以子串的第一个字符在主串中的位置来表示 串的比较 见后页 6 串的比较 例 abcd abcd abc abc 设有两个串 X x1x2 xm Y y1y2 yn 等于 当m n 且xi yi时 称X Y 小于 当m n 且xi yi i 1 2 n 或存在某个k min m n 使得xi yi i 1 2 k 1 xk yk时 称X Y 7 假设S abcaabcaaabc T bca Index S T 1 Index S T 3 Index S T 8 子串中的第一个字符在主串中的位序 2 6 0 子串在主串中的位置 8 串的抽象数据类型定义 ADTString Data D ai ai CharaterSet i 1 2 n n 0 Relation R ai 1 ai D i 2 n OperationStrAssign S T 串赋值StrLength S 求串长StrConcat S T 串联接StrSub S i len 求子串StrCmp S T 串比较StrIndex S T 串匹配StrInsert S i T 串插入StrDelete S i len 串删除StrRep S T R 串置换 ADT 9 i 3 len 3 i 7 len 4 空串 求子串 SubStr s i len 10 例如 sub SubString commander 4 3 sub sub SubString commander 1 9 sub sub SubString commander 9 1 sub man commander r 求子串示例 11 sub SubString commander 4 7 sub sub SubString beijing 7 2 sub SubString student 5 0 起始位置和子串长度之间存在约束关系 长度为0的子串为 合法 串 12 假设S abcaabcaaabca T bca 若V x 则经置换后得到S 若V bc 则经置换后得到S axaxaax abcabcaabc 串置换 13 例如 S chater T rac 则执行StrInsert S 4 T 之后得到S character 串插入 StrInsert S pos T 14 串的逻辑结构和线性表极为相似 区别仅在于串的数据对象约束为字符集 串的基本操作和线性表有很大差别 在线性表的基本操作中 大多以 单个元素 作为操作对象 在串的基本操作中 通常以 串的整体 作为操作对象 串与线性表 15 4 2串的存储结构 本章目录 1 串的顺序存储结构2 串的链式存储结构3 串的索引存储结构4 串的堆存储 16 串的顺序存储结构 用数组的0号单元存放串的长度 串值从1号单元开始存放 在串尾存储一个不会在串中出现的特殊字符作为串的终结符 用一变量存储串长 如顺序表一样 17 StatusConcat SStringS1 SStringS2 SString T 用T返回由S1和S2联接而成的新串 若未截断 则返回TRUE 否则FALSE Concat 顺序存储操作示例 串联接 case1 S1 0 S2 0 MAXSTRLEN 18 串连接 续 case2 S1 0 MAXSTRLEN case3 S1 0 MAXSTRLEN 19 串的链式存储结构 结点大小为1的链式存储结构 图4 4串的链式存储 图4 5块链存储结构 块链存储结构 20 串的索引存储结构 图4 6带头指针的名字索引表 图4 7带长度的名字索引表 图4 8带末指针的名字索引表 串的索引存储结构 用串变量的名字作为关键字组织起来的索引表 表中串名与串值之间一一对应 例 S1 please S2 seek 21 串的堆存储 4 9堆结构示意图 堆存储中 多个串连续存放在堆中 因此需建立一张索引表记载各个串的位置 如4 2 3所述 另需设一指针 指示未分配空间的首地址 如图4 9中的avail 基本思路 在内存中开辟能存储足够多的串 且地址连续的存储空间作为应用程序中所有串的可利用存储空间 称为 堆空间 22 4 3顺序串的实现 本章目录 1 常用C 串操作函数2 顺序串类的定义3 操作举例 23 常用C 字符串函数 串长度函数 intstrlen char str 串复制函数 char strcpy char str1 char str2 串比较函数 intstrcmp char str1 char str2 串联结函数 char strcat char str1 char str2 串输入 cin getchar getline 24 串长度函数intstrlen char str 设 chars1 Iwasagoodstudents chars2 3yearsago chars3 chars4 40 空串 cout 串s1长为 strlen s1 输出 串s1长为 21cout 串s3长为 strlen s3 输出 串s3长为 1cout 串s4长为 strlen s4 输出 串s4长为 0 功能 求串str的长度返回值 串str的长度 25 char strcpy char str1 char str2 设 chars1 Iwasagoodstudents chars2 3yearsago chars3 chars4 40 空串 功能 将字符串str2拷贝给串str1返回值 串str1的首地址 cout strcpy s3 s1 输出 Iwasagoodstudents 26 intstrcmp char str1 char str2 设 chars1 Iwasagoodstudents chars2 3yearsago chars3 chars4 40 空串 功能 比较串str1和str2返回值 str1 str2 返回0 str1str2 返回1 例 cout strcmp s1 s2 输出 1cout strcmp s1 s3 输出 0 27 char strcat char str1 char str2 功能 将串str2连接到串str1后面返回值 串str1的首地址 cout 串s1与s2连接为 strcat s1 s2 输出 串s1与s2连接为 Iwasagoodstudents3yearsago 设 chars1 Iwasagoodstudents chars2 3yearsago chars3 chars4 40 空串 28 4 3 2 串类AString的定义 classAString private char ch 串存放数组intcurLength 串的实际长度intmaxSize 存放数组的最大长度 public AString AString intsz 构造函数 构造一个最大长度为sz 实际长度为0的字符串AString constchar init 构造函数 构造一个最大长度为maxSize 由init初始化的新字符串对象AString constAString ob 复制构造函数 由一个已有的字符串对象ob构造一个新字符串 AString delete ch 29 intoperator AString ob 判断当前实例是否与ob串相等 若相等则返回1 否则返回0intoperator AString ob 判断当前实例是否与ob串不等 若不等则返回1 否则返回0intoperator AString ob 判断当前实例串是否大于ob串 若小于则返回1 否则为0intoperator AString ob 判断当前实例串是否大于等于ob串 若大于等于则返回1 否则为0 30 与C 串的比较运算 intoperator char str 判断当前实例是否与C 串相等 若相等则返回1 否则返回0intoperator char str 判断当前实例是否与C 串不相等 若不等则返回1 否则返回0intoperator char str 判断当前实例是否与大于C 串 若小于则返回1 否则返回0intoperator char str 判断当前实例是否与大于等于C 串 若大于等于则返回1 否则返回0 31 AString operator AString ob 将串ob赋值给当前实例 AString operator constchar str 将字符串赋值给字符串对象AString operator AString ob 若当前实例串长度与ob串长度之和不超过maxSize则把ob串接在当前实例的后面 AString operator constchar str 若当前实例串长度与str串长度之和不超过maxSize 则把str串接到串对象后面 char operator inti 取当前实例的第i个字符返回 32 串操作举例 构造函数赋值串连接串比较求子串 33 构造函数 构造函数 实现串的创建 通过多态考虑三种情况 创建一个空串用C 串生成串对象用串对象来生成串对象 34 构造函数操作步骤 功能 创建一个空串Step1 申请串对象所需空间Step2 若申请成功 为串属性赋值类C 语言描述 AString AString maxSize defaultSize 串容量等于缺省容量ch newchar maxSize 申请串空间ch 0 0 串结束符curLength 0 空串 串长为0 35 构造函数AString AString constchar init 用C 串生成串对象操作步骤 Step1 根据C 串常量的长度 申请串对象所需空间Step2 若申请成功 为串属性赋值Step3 把C 串常量的值复制给串对象类C 语言描述 AString AString constchar init intinitLength strlen init maxSize initLength defaultSize initLength defaultSize ch newchar maxSize 1 curLength initLength strcpy ch init 36 构造函数 用串对象来生成串对象操作步骤 Step1 根据串常量对象的长度 申请串对象所需空间Step2 若申请成功 为串属性赋值Step3 把串常量对象的值复制给串对象类C 语言描述 AString AString constAString ob maxSize ob maxSize Step1ch newchar maxSize 1 strcpy ch ob ch Step2curLength ob curLength AString AString constAString ob 37 赋值 赋值 为串对象赋值 赋值操作通过对操作符 重载实现 通过多态用串对象赋值通过多态用C 串赋值 38 通过多态用串对象赋值 操作步骤 Step1 若两串是同一对象 退出 否则 Step2Step2 清空目标串Step3 串长取源串对象长Step4 源串对象值复制给目标串对象类C 语言描述 AString AString operator AString ob if ob this Step1 Clear Step2curLength ob Length Step3strcpy ch ob ch elsecout 字符串自身赋值出错 n return this 39 赋值 通过多态用C 串赋值操作步骤 Step1 设置串对象长为C 串长与其自身长中较大的一个Step2 清空目标串Step3 把源C 串值复制给目标串对象类C 语言描述 AString AString operator constchar str 字符串赋值intstrLength strlen str Step1maxSize strLength maxSize strLength maxSize Clear Step2curLength strLength strcpy ch str Step3return this 40 串连接 把一个串连接到另一个串后 通过对操作符 重载实现通过多态实现两个串对象连接通过多态实现把一个C 串连接到串对象 41 通过多态实现两个串对象连接 操作步骤 Step1 初始化设置两个工作指针 分别指向源串和子串设置一工作串 串长为源串与子串长度之和 并按此申请存储空间Step2 把源串 目标串先后复制给工作串Step3 清空源串Step4 工作串的值复制给源串 并设置源串的新长度Step5 释放工作串空间 42 算法描述 类C 语言描述 AString AString operator AString ob 字符串对象连接char tempCH ch Step1char tempOb ob ch intaddLength curLength strlen tempOb maxSize maxSize addLength maxSize addLength char temp newchar maxSize 1 char tempT temp 43 续 while tempCH 0 Step2 tempT tempCH while tempOb 0 Step2 tempT tempOb tempT 0 Clear Step3strcpy ch temp Step4curLength strlen ch delete temp Step5return this 44 串比较 串比较 通过对关系运算符 等 重载实现通过多态实现两个串对象比较通过多态实现串对象与C 串的比较 45 通过多态实现两个串对象比较 intoperator AString ob const 判断当前实例是否与ob串相等 若相等则返回1 否则返回0 returnstrcmp ch ob ch 0 intoperator AString ob const 判断当前实例是否与ob串不等 若不等则返回1 否则返回0 returnstrcmp ch ob ch 0 intoperator AString ob const 判断当前实例串是否小于ob串 若小于则返回1 否则为0 returnstrcmp ch ob ch 0 46 求子串 从主串中取出连续的若干个字符 取出的子串取决于起始位置index和取出字符的个数length 操作步骤 Step1 如果串空或起始位置与子串长度不合理 不能取 否则 转Step2Step2 设置一工作串temp 按子串长 申请串空间Step3 把主串从index起的length个字符复制给工作串tempStep4 工作串复制给子串Step5 销毁工作串 47 求子串算法描述 AString AString StrSub intindex intlength if indexmaxSize length 0 Step1 cerr 或索引或者长度越界 n exit 1 if IsEmpty cerr 字符串对象为空 n exit 1 else Step2 char temp newchar length 1 if temp NULL cerr 内存分配错误 n exit 1 48 续 for inti 0 j index i length i j Step3 temp i ch j Clear strcpy ch temp Step4ch length 1 0 curLength strlen ch delete temp return this Step5 49 其它串操作 1 串插入将串T插入到主串S的第i个字符处 设串S s1s2 si sn 串T t1t2 tm 将T插入到S的第i 0 i n 1 个字符处后 S串为 s1s2 si 1t1t2 tmsi sn 串插入StrInsert S i T 2 串删除删除主串中若干个连续字符 串删除StrDelete S i len 用已定义的基本操作实现串的其它操作 50 串插入 voidStrInsert AString S inti AStringT 操作步骤 Step1 若i值不在插入范围 不能插入 否则Step2Step2 从S中取子串 s1s2 si 1 暂存于工作串tempStep3 将T连接到串temp后Step4 将temp串与S的子串 si sn 相联Step5 将temp赋给SStep6 销毁temp 51 串插入算法描述 voidStrInsert AString S inti AStringT 将串T插入到串S的第i个字符处s len S curLength 主串串长t len T currLength 插入串串长if iS size throw 插入位置异常 try 取子串 s1s2 si 1 temp S SubString 1 i 1 temp temp T T连接到temp后try 取子串 si sn 并连接到temp后 temp temp S SubString i s len i 1 S temp deletetemp str 销毁串temptemp size 0 Insert 52 串删除 操作步骤 Step1 删除位置或删除长度不合理 不能删除 否则 转Step2Step2 从起始位置开始到最后的字符个数不足len个 只需修改串长 否则 转Step3Step3 分别从主串中取子串 s1s2 si 1 和 si len sn 并把两个子串连结赋给工作串tempStep4 把工作串temp复制给主串 并销毁工作串 voidStrDelete AString S inti intlen 53 串删除StrDelete S i len voidStrDelete AString S inti intlen 删除串S的第i个字符起的len个字符s len S StrLength 主串串长if is len throw 删除位置异常 if s len i 1 len S size i S str i NULL 修改串长else 连接子串 s1s2 si 1 和 si len 1 sn try temp S SubString 1 i 1 S SubString i len s len S temp deletetemp str 销毁temp串temp size 0 54 4 4模式匹配 1 BF算法2 KMP算法 55 模式匹配 设S和T是两个给定的串 在串S中找等于T的子串的过程称为模式匹配 patternmatching 其中 S称为主串 T称为模式 pattern 如果找到 称为匹配成功 否则称为匹配失败 56 BF Brute Force 算法基本思想 基本思想 从主串S的第一个字符开始和模式T的第一个字符进行比较 若相等 则继续比较两者的后续字符 否则 从主串S的第二个字符开始和模式T的第一个字符进行比较 重复上述过程 若T中的字符全部比较完毕 则说明匹配成功 返回主串S在本趟比较中的起始位置 否则匹配失败 返回0 57 si 主串S 模式T tj BF算法示意图 58 si 主串S 模式T i BF算法示意图 续 59 si 主串S 模式T BF算法示意图 续 60 例 主串S ababcabcacbab 模式T abcac i 3 j 3失败 i回溯到2 j回溯到1 第1趟 abcac BF算法示例 61 例 主串S ababcabcacbab 模式T abcac i 3 j 3失败 i回溯到2 j回溯到1 j i 第1趟 abcac BF算法示例 第一趟 62 例 主串S ababcabcacbab 模式T abcac i 2 j 1失败i回溯到3 j回溯到1 第2趟 abcac BF算法示例 第二趟 63 例 主串S ababcabcacbab 模式T abcac i 2 j 1失败i回溯到3 j回溯到1 第2趟 i j abcac BF算法示例 第二趟 64 例 主串S ababcabcacbab 模式T abcac abcac i 7 j 5失败i回溯到4 j回溯到1 第3趟 BF算法示例 第三趟 65 例 主串S ababcabcacbab 模式T abcac abcac i 7 j 5失败i回溯到4 j回溯到1 第3趟 i j BF算法示例 第三趟 66 例 主串S ababcabcacbab 模式T abcac abcac i 4 j 1失败i回溯到5 j回溯到1 第4趟 BF算法示例 第四趟 67 例 主串S ababcabcacbab 模式T abcac abcac i 4 j 1失败i回溯到5 j回溯到1 第4趟 i j BF算法示例 第四趟 68 例 主串S ababcabcacbab 模式T abcac abcac i 5 j 1失败i回溯到6 j回溯到1 第5趟 BF算法示例 第五趟 69 例 主串S ababcabcacbab 模式T abcac ababcabcacbab abcac i 5 j 1失败i回溯到6 j回溯到1 第5趟 i j BF算法示例 第五趟 70 例 主串S ababcabcacbab 模式T abcac ababcabcacbab abcac i 11 j 6 T中全部字符都比较完毕 匹配成功 第6趟 BF算法示例 第六趟 71 BF算法操作步骤 Step1 初始化 设置两个工作指针i j 分别指向主串S比较起始位置和子串T的首字符位置Step2 只要主串和子串没有比完 重复下列操作 2 1如果s i t j 两指针均后移 即 i j 否则2 2如果没有到主串尾 指针回溯 i回到比较起始位置的后一个 j回到子串首字符位置 即 i i j 1 j 0 Step3 如果子串比完 则匹配成功 返回子串在主串中的位置 否则 匹配不成功 返回 1 72 BF算法描述 intIndexBF chars chart intpos 在主串S中找模式T 若找到 则返回T的首字符在S中的下标 否则返回 1i pos 1 j 0 设置比较的起始下标m strlen s 主串长n strlen t 模式串长while i n 成功 返回本趟匹配的主串的起始下标returni n 1 elsereturn 1 失败 返回 1 Index BF 73 BF算法分析 i主串S abcdadefghcd子串T efgh 最好 最坏 i主串S abcdabcgabcfabce子串T abce 74 BF算法分析 最好情况 每趟不成功的匹配总是发生模式串的第一个字符与主串中相应字符的比较 第i个位置匹配成功 例如 S aaaaaaaaaabcdccccc T bcd 75 设主串长为n 子串长为m第i个位置匹配成功之前 在前i 1趟匹配中字符共比较了 i 1次 第i趟成功匹配的字符比较次数为 m 则总比较次数为 i 1 m 可能成功匹配的位置有 1 n m 1 设每个位置匹配成功的概率相等 则最好情况下匹配成功的平均比较次数为 BF最好情况分析 例如 S aaaaaaaaaabcdccccc T bcd 76 BF算法最好情况下时间复杂度 最好情况下的时间复杂度是O n m 77 BF算法分析 最坏情况 最坏情况 不成功的匹配都发生在串T的最后一个字符 S aaaaaaaaaaabccccc T aaab 78 设主串长为n 子串长为m 第i个位置匹配成功之前i 1趟不成功匹配中每趟都比较了 m次 第i趟成功匹配的字符比较次数为 m次 则总比较次数为 i m 可能成功匹配的位置有 1 n m 1 每第个位置匹配成功的概率相等 则最坏情况下匹配成功的平均比较次数为 BF最坏情况分析 S aaaaaaaaaaabccccc T aaab 79 BF算法最坏情况下时间复杂度 最坏情况下的时间复杂度是O n m 80 BF改进 i 9S1S2S3S4S5S6S7S8S9S10S11S12S13S14S15 P1P2P3P4P5P6 j 6 由比较结果知 S4S5S6S7S8 P1P2P3P4P5 下一轮比较从P4开始 即 S6S7S8 P1P2P3 所以 i 9S1S2S3S4S5S6S7S8S9S10S11S12S13S14S15 P1P2P3P4 j 4 记next 6 4 设 P1P2P3 P3P4P5 81 KMP算法 iS1S2 Si j 1Si j 2 Si 2Si 1SiSi 1 P1P2 Pj 2Pj 1PjP1P2 Pk 2Pk 1PkPk 1 i不动 将模式串尽量向后移动 P1P2 Pk 1 Si k 1Si k 2 Si 1 Pj k 1Pj k 2 Pj 1 Si k 1Si k 2 Si 1 P1P2 Pk 1 Pj k 1Pj k 2 Pj 1