三十九、字符串类的创建(上)
1、历史遗留问题
- C语言不支持真正意义上的字符串
- C语言用字符数组和一组函数实现字符串操作
- C语言不支持自定义类型,因此无法获得字符串类型
- 从C到C++的进化过程引入了自定义类型
- 在C++中可以通过类完成字符串类型的定义
C++中的原生类型系统是否包含字符串类型?
没有,通过标准库。
2、DTLib 中字符串类的设计
![](https://img-blog.csdnimg.cn/c9e29044cb0a41ef94a3f5c1d41fbe7b.png)
3、DTLib 中字符串类的实现
![](https://img-blog.csdnimg.cn/e48abfd9cab5487c8adcd0306080aae2.png)
4、实现时的注意事项
- 无缝实现 String对象与char*字符串的互操作
- 操作符重载函数需要考虑是否支持const版本
- 通过C语言中的字符串函数实现String的成员函数
5、编程实验:字符串类的实现
String.h
String.cpp
6、小结
- C /C++语言本身不支持字符串类型
- C语言通过字符数组和一组函数支持字符串操作
- C++通过自定义字符串类型支持字符串操作
- 字符串类型通过C语言中的字符串函数实现
四十、字符串类的创建(下)
1、字符串类中的常用成员函数
![](https://img-blog.csdnimg.cn/0b0a771e9ad149fab68c672c4c7c8f3b.png)
2、重载数组访问操作符[]
- char& operator [] (int i);
- char operator [] (int i) const;
- 注意事项
- 当i的取值不合法时,抛出异常
- 合法范围:( 0<=i ) && ( i < m_length )
3、判断是否以指定字符串开始或结束
- bool startWith(const char* s) const;
- bool startWith(const String& s) const;
- bool endOf(const char* s) const;
- bool endOf(const String& s) const;
![](https://img-blog.csdnimg.cn/87a58013ea784386853d113a69fa9fb2.png)
4、在指定位置处插入字符串
- String& insert(int i, const char* s);
- String& insert(int i, const String& s);
![](https://img-blog.csdnimg.cn/c6f449bd067f455bb5417b774d3c77e0.png)
5、去掉字符串两端的空白字符
![](https://img-blog.csdnimg.cn/78a2ef7347cd410893788a2a074d854c.png)
6、编程实验:常用成员函数的实现
string.h
string.cpp
7、To be continued ...
思考:
如何在目标字符串中查找是否存在指定的子串?
四十一、KMP 子串查找算法
1、问题
如何在目标字符串S中,查找是否存在子串P ?
2、朴素解法
![](https://img-blog.csdnimg.cn/78c81eabf78b46b6b6cd32a78b2afcaa.png)
3、朴素解法的一个优化线索
![](https://img-blog.csdnimg.cn/6bb81ec8bd974d05978400ae1f86933b.png)
4、示例
![](https://img-blog.csdnimg.cn/640ce705e7a9402e9c75c5df63ecbbdf.png)
5、伟大的发现
- 匹配失败时的右移位数与子串本身相关,与目标串无关
- 移动位数 = 已匹配的字符数 - 对应的部分匹配值
- 任意子串都存在一个唯一的部分匹配表
6、部分匹配表示例
![](https://img-blog.csdnimg.cn/67c76e0f629a4ad79adc0c38d25cd7a7.png)
7、问题:部分匹配表是怎么得到的?
示例: ABCDABD
![](https://img-blog.csdnimg.cn/d8a82a67e0d5460c9f28d4b6409947c2.png)
8、问题:怎么编程产生部分匹配表?
- 实现关键
- PMT[1] = 0(下标为0的元素匹配值为0)
- 从2个字符开始递推(从下标为1的字符开始递推)
- 假设PMT[n] = PMT[n-1]+1(最长共有元素的长度)
- 当假设不成立,PMT[n]在PMT[n-1]的基础上减小
9、编程实验:部分匹配表的递推与实现
10、部分匹配表的使用(KMP算法)
![](https://img-blog.csdnimg.cn/52593a92956f49108a064b18b1316f7f.png)
11、编程实验:KMP子串查找算法的实现
12、小结
- 部分匹配表是提高子串查找效率的关键
- 部分匹配值定义为前缀和后缀最长共有元素的长度
- 可以用递推的方法产生部分匹配表
- KMP利用部分匹配值与子串移动位数的关系提高查找效率
四十二、KMP 算法的应用
1、思考
如何在目标字符串中查 找是否存在指定的子串?
![](https://img-blog.csdnimg.cn/c72614fbfcd14fcea609deebf0c6066b.png)
2、字符串类中的新功能
![](https://img-blog.csdnimg.cn/cc0cdf1177b14656886d59ddc9ba1acc.png)
3、子串查找(KMP算法的直接运用)
- int indexOf(const char* s) const
- int indexOf(const String& s) const
4、在字符串中将指定的子串删除
- String& remove(const char* s)
- String& remove(const String& s)
- 根据KMP在目标字符串中查找子串的位置
- 通过子串位置和子串长度进行删除
5、字符串的减法操作定义( operator - )
![](https://img-blog.csdnimg.cn/fcf03a029c3f48e4a5ef1ecb7c9e3685.png)
6、字符串中的子串替换
- String& replace(const char* t, const char* s)
- String& replace(const String& t, const char* s)
- String& replace(const char* t, const String& s)
- String& replace(const String& t, const String& s)
7、从字符串中创建子串
- String sub(int i, int len) const
- 以i为起点提取长度为len的子串
- 子串提取不会改变字符串本身的状态
![](https://img-blog.csdnimg.cn/fedcf833b3bb42bb83b0f1f54e771db4.png)
8、编程实验:新成员函数的实现
string.h
string.cpp
9、小结
- 字符串类是工程开发中必不可少的组件
- 字符串中应该包含常用字符串操作函数
- 增:insert , operator + , .….
- 删:remove , operator -, …
- 查:indexOf , ...
- 改:replace , ...
补充、字符串匹配算法
1、BF算法,Brute Force(暴力算法)
第一轮,从主串的首位开始,把主串和模式串的字符逐个比较:
![](https://img-blog.csdnimg.cn/d019b2876e254802baa3a45d4d08da47.png)
显然,主串的首位字符是a,模式串的首位字符是b,两者并不匹配。
第二轮,把模式串后移一位,从主串的第二位开始,把主串和模式串的字符逐个比较:
![](https://img-blog.csdnimg.cn/b0eac30531c143209858f10c1a924da2.png)
主串的第二位字符是b,模式串的第二位字符也是b,两者匹配,继续比较:
![](https://img-blog.csdnimg.cn/5d511f634b74447b8b424ef56a1eefa4.png)
主串的第三位字符是b,模式串的第三位字符也是c,两者并不匹配。
第三轮,把模式串再次后移一位,从主串的第三位开始,把主串和模式串的字符逐个比较:
![](https://img-blog.csdnimg.cn/356fd07559634ddc8f773eb35b45dd15.png)
主串的第三位字符是b,模式串的第三位字符也是b,两者匹配,继续比较:
![](https://img-blog.csdnimg.cn/b7ed26726cd441d096fe2f726a84eae0.png)
主串的第四位字符是c,模式串的第四位字符也是c,两者匹配,继续比较:
![](https://img-blog.csdnimg.cn/5103d297a00a4421933638a50bc65b8f.png)
主串的第五位字符是e,模式串的第五位字符也是e,两者匹配,比较完成!
由此得到结果,模式串 bce 是主串 abbcefgh 的子串,在主串第一次出现的位置下标是 2:
![](https://img-blog.csdnimg.cn/a07217d9731b483fb436041c50a2c639.png)
假设主串的长度是m,模式串的长度是n,那么在这种极端情况下,BF算法的最坏时间复杂度是O(mn)。
2、RK 算法
全称Rabin-Karp,是由算法的两位发明者Rabin和Karp的名字来命名的。
① RK 算法的核心
BF算法只是简单粗暴地对两个字符串的所有字符依次比较,而RK算法比较的是两个字符串的[哈希值]。
每一个字符串都可以通过某种哈希算法,转换成一个整型数,这个整型数就是hashcode:
hashcode = hash(string)
② RK 算法的推演
给定主串和模式串如下(假定字符串只包含26个小写字母):
![](https://img-blog.csdnimg.cn/b39f0cc55ad64151b1d85a1ae32b0c85.png)
第一步,需要生成模式串的hashcode。
生成hashcode的算法多种多样,比如:
方法一:按位相加
这是最简单的方法,可以把a当做1,b当做2,c当做3......然后把字符串的所有字符相加,相加结果就是它的hashcode。
bce = 2 + 3 + 5 = 10
但是,这个算法虽然简单,却很可能产生hash冲突,比如bce、bec、cbe的hashcode是一样的。
方法二:转换成26进制数
既然字符串只包含26个小写字母,那么可以把每一个字符串当成一个26进制数来计算。
bce = 2*(26^2) + 3*26 + 5 = 1435
这样做的好处是大幅减少了hash冲突,缺点是计算量较大,而且有可能出现超出整型范围的情况,需要对计算结果进行取模。
后续采用的是按位相加的hash算法,所以bce的hashcode是10:
![](https://img-blog.csdnimg.cn/8e84cd8b20784f5f9cbd6b1e49eef8cc.png)
第二步,生成主串当中第一个等长子串的hashcode。
由于主串通常要长于模式串,把整个主串转化成hashcode是没有意义的,只有比较主串当中和模式串等长的子串才有意义。
因此,首先生成主串中第一个和模式串等长的子串hashcode,
即abb = 1 + 2 + 2 = 5:
![](https://img-blog.csdnimg.cn/ab239d07fe95475db8c91bb87929f79d.png)
第三步,比较两个hashcode。
显然,5!=10,说明模式串和第一个子串不匹配,继续下一轮比较。
第四步,生成主串当中第二个等长子串的hashcode。
bbc = 2 + 2 + 3 = 7:
![](https://img-blog.csdnimg.cn/4c8ddaed986d4904ae4f3ec07731d759.png)
第五步,比较两个hashcode。
显然,7!=10,说明模式串和第二个子串不匹配,继续下一轮比较。
第六步,生成主串当中第三个等长子串的hashcode。
bce= 2 + 3 + 5 = 10:
![](https://img-blog.csdnimg.cn/9860494bba6a42ada0435acbd24b8451.png)
第七步,比较两个hashcode。
显然,10 ==10,两个hash值相等!这是否说明两个字符串也相等呢?
别高兴的太早,由于存在hash冲突的可能,还需要进一步验证。
第八步,逐个字符比较两字符串。
hashcode的比较只是初步验证,之后还需要像BF算法那样,对两个字符串逐个字符比较,最终判断出两个字符串匹配。
![](https://img-blog.csdnimg.cn/f39bd3a489a243759d2f417b76f3a8a9.png)
最后得出结论,模式串bce是主串abbcefgh的子串,第一次出现的下标是2。
③ RK 算法的优化
每次hash的时间复杂度是0(n),如果把全部子串都进行hash,总的时间复杂度是0(mn)。
解决方法:对子串的hash计算并不是独立的,从第二个子串开始,每一个子串的 hash都可以由上一个子串进行简单的增量计算来得到:
![](https://img-blog.csdnimg.cn/890ccb65e52f4ae8ab93c09760386596.png)
上图中,我已知子串abbcefg的hashcode是26,那么如何计算下一个子串,也就是bbcefgd的hashcode呢?
![](https://img-blog.csdnimg.cn/66c8550a4ca84d309f44f367f4fb7c11.png)
由于新子串的前面少了一个a,后面多了一个d,所以:
新hashcode = 旧hashcode - 1 + 4 = 26-1+4 = 29
再下一个子串bcefgde的计算也是同理:
新hashcode = 旧hashcode - 2 + 5 = 29-2+5 = 32
④ RK 算法代码实现
⑤ RK 算法时间复杂度
RK算法计算单个子串hash 的时间复杂度是0 (n),但由于后续的子串hash是增量计算,所以总的时间复杂度仍然是0 (n)。
⑥ RK 算法缺点
RK算法的缺点在于哈希冲突。每一次哈希冲突的时候,RK算法都要对子串和模式串进行逐个字符的比较,如果冲突太多了,算法就退化成了BF算法。
3、BM 算法
BM算法的名字取自于它的两位发明者,计算机科学家Bob Boyer和JStrother Moore。
① BM 算法的核心
采用字符比较的思路,并且尽量减少无谓的比较,这就是BM算法的努力方向。
为了能减少比较,BM算法制定了两条规则,一个是[坏字符规则],一个是[好后缀规则]。
坏字符规则
② BM 算法 - 坏字符规则 推演
“坏字符” 是什么意思?就是指模式串和子串当中不匹配的字符。
当模式串和主串的第一个等长子串比较时,子串的最后一个字符T就是坏字符:
![](https://img-blog.csdnimg.cn/c2c9ecb2484f4e5f94985281feb92159.png)
为什么坏字符不是主串第2位的字符T呢?那个位置不是最先被检测到的吗?
BM算法的检测顺序相反,是从字符串的最右侧向最左侧检测。
当检测到第一个坏字符之后,只有模式串与坏字符T对齐的位置也是字符T的情况下,两者才有匹配的可能。
模式串的第1位字符也是T,直接把模式串当中的字符T和主串的坏字符对齐,进行下一轮的比较:
![](https://img-blog.csdnimg.cn/d240d13a72a04bba90a810c265112149.png)
坏字符的位置越靠右,下一轮模式串的挪动跨度就可能越长,节省的比较次数也就越多。这就是BM算法从右向左检测的好处。
接下来,继续逐个字符比较,发现右侧的G、C、G都是一致的,但主串当中的字符A,是又一个坏字符:
![](https://img-blog.csdnimg.cn/e7109905179b486cac71c2f6b44004da.png)
按照刚才的方式,找到模式串的第2位字符也是A,于是我们式串的字符A和主串中的坏字符对齐,进行下一轮比较:
![](https://img-blog.csdnimg.cn/59aa3e1ebe5148909a55ccba4e2d4a2b.png)
接下来,继续逐个字符比较,这次发现全部字符都是匹配的,比较公正完成:
![](https://img-blog.csdnimg.cn/a359b6aa5ee84f4c8734561314821005.png)
如果坏字符在模式串中不存在,又该如何挪动呢?
直接把模式串挪到主串坏字符的下一位:
![](https://img-blog.csdnimg.cn/896ea65a4fb44e499d39161169b60256.png)
③ BM 算法 - 坏字符规则 代码实现
BM算法的[阉割版](坏字符规则只是BM算法的两大法宝之一,除此之外它还具备另一件法宝:[好后缀规则]。)
好后缀规则
④ BM 算法 - 好后缀规则 推演
“好后缀” 又是什么意思?就是指模式串和子串当中相匹配的后缀。
![](https://img-blog.csdnimg.cn/41cd182097f64e2f8695cd0f0ed85df3.png)
对于上面的例子,如何继续使用“坏字符规则”,会有怎样的效果呢?
从后向前比对字符,发现后面三个字符都是匹配的,到了第四个字符的时候,发现坏字符G:
![](https://img-blog.csdnimg.cn/ebb53b36a71d4d948abd93a3fbc86b15.png)
接下来在模式串找到了对应的字符G,但是按照坏字符规则,模式串仅仅能够向后挪动一位:
![](https://img-blog.csdnimg.cn/dfa542f780974b48ad5672251b8a94a0.png)
这时候坏字符规则显然并没有起到作用,为了能真正减少比较次数,轮到好缀规则出场了。
![](https://img-blog.csdnimg.cn/9948f86c50bb4c55a7ec9c05094c3ee1.png)
回到第一轮的比较过程,发现主串和模式串都有共同的后缀“GCG”,这就是所谓的“好后缀”。
如果模式串其他位置也包含与“GCG”相同的片段,那么就可以挪动模式串,让这个片段和好后缀对齐,进行下一轮的比较:
![](https://img-blog.csdnimg.cn/ebb7288b7ae349fdbde7ed2ea590d621.png)
显然,在这个例子中,采用好后缀规则能够让模式串向后移动更多位,节省了更多无谓的比较。
那么,如果模式串当中并不存在其他与好后缀相同的片段,该怎么处理?是不是可以直接把模式串挪到好后缀之后?
![](https://img-blog.csdnimg.cn/5943192e103d4bdb921ab87d3ae60405.png)
不能直接挪动模式串到好后缀的后面,还要先判断一种特殊情况:
模式串的前缀是否和好后缀的后缀相匹配,免得挪过头了。
![](https://img-blog.csdnimg.cn/4b3c50d7c34245d688127b233f97dec7.png)
⑤ 在什么情况下应该使用坏字符规则,什么情况下应该使用好后缀规则呢?
举个例子,假设坏字符规则可以让模式串在下一轮挪动3位,好后缀规则可以让模式串在下一轮挪动5位,那就采用好后缀规则。
在每一轮的字符比较之后,按照坏字符和好后缀规则分别计算相应的挪动距离,哪一种距离更长,就把模式串挪动对应的长度。
⑥ BM 算法 - 好后缀规则 代码实现
四十三、递归的思想与应用(上)
1、递归是一种数学上分而自治的思想
- 将原问题分解为规模较小的问题进行处理
- 分解后的问题与原问题的类型完全相同,但规模较小
- 通过小规模问题的解,能够轻易求得原问题的解
- 问题的分解是有限的(递归不能无限进行)
- 当边界条件不满足时,分解问题(递归继续进行)
- 当边界条件满足时,直接求解(递归结束)
2、递归模型的一般表示法
![](https://img-blog.csdnimg.cn/ec28612140d64387806648e121655984.png)
3、递归在程序设计中的应用
- 递归函数
- 函数体中存在自我调用的函数
- 递归函数必须有递归出口(边界条件)
- 函数的无限递归将导致程序崩溃
4、递归思想的应用
![](https://img-blog.csdnimg.cn/515498be7ef64ab3ab988c2d43baf1a5.png)
5、编程实验:递归求和
unsigned int sum(unsigned int n);
![](https://img-blog.csdnimg.cn/33d369e62c214bb9962ff095fa64f5de.png)
6、斐波拉契数列
数列自身递归定义:1,1,2,3,5,8,13,21,...
![](https://img-blog.csdnimg.cn/f9bb6f106bce4dadac4192d8b0ad8e90.png)
7、编程实验:斐波拉契数列
unsigned int Fibonacci(unsigned int n);
![](https://img-blog.csdnimg.cn/d30c68c084154ae6bd444ee312ffa30b.png)
8、用递归的方法编写函数求字符串长度
![](https://img-blog.csdnimg.cn/52a705b4135d4e0695677de3c3c15659.png)
9、编程实验:求字符串长度
unsigned int strlen(const char* s);
![](https://img-blog.csdnimg.cn/42ce26f5a09b4ee196f13a62364e4e2b.png)
10、小结
- 递归是一种将问题分而自治的思想
- 用递归解决问题首先要建立递归的模型
- 递归解法必须要有边界条件,否则无解
- 不要陷入递归函数的执行细节,学会通过代码描述递归问题
四十四、递归的思想与应用(中)
1、单向链表的转置
![](https://img-blog.csdnimg.cn/859d6943163d427d80096747bddc9dbf.png)
![](https://img-blog.csdnimg.cn/d85b1b7f1399475db62d5b388d00d287.png)
2、编程实验:单向链表的转置
Node* reverse(Node* list)
![](https://img-blog.csdnimg.cn/d46f175b1da84425a93fe8313bce582f.png)
3、单向排序链表的合并
![](https://img-blog.csdnimg.cn/5f6e3bbf02dd4864b5b62f8aec88e612.png)
4、编程实验:单向排序链表的合并
Node* merge(Node* list1, Node* list2)
![](https://img-blog.csdnimg.cn/c02b4004a4ff488caff5461ace637402.png)
5、汉诺塔问题
- 将木块借助B柱由A柱移动到C柱
- 每次只能移动一个木块
- 只能出现小木块在大木块之上
![](https://img-blog.csdnimg.cn/1a56f643c20f404983a96c978c2a39fd.png)
6、汉诺塔问题分解
- 将n-1个木块借助C柱由A柱移动到B柱
- 将最底层的唯一木块直接移动到C柱
- 将n-1个木块借助A柱由B柱移动到C柱
![](https://img-blog.csdnimg.cn/f1b2f6d6ef8a4c5b98261a54c27d2e45.png)
7、编程实验:汉诺塔问题求解
void HanoiTower(int n, char a, char b, char c)
![](https://img-blog.csdnimg.cn/9f388a4ee7e845bf8ee275807ba7b42b.png)
8、全排列问题
![](https://img-blog.csdnimg.cn/078794009432485f9be77d599f2b7c4d.png)
9、编程实验:全排列的递归解法
void permutation(char* s)
![](https://img-blog.csdnimg.cn/7a27bd5bbd964c4a9521b1c60569d762.png)
10、小提示
递归还能用于需要回溯穷举的场合。
四十五、递归的思想与应用(下)
1、函数调用过程回顾
- 程序运行后有一个特殊的内存区供函数调用使用
- 用于保存函数中的实参,局部变量,临时变量,等
- 从起始地址开始往一个方向增长(如:高地址→低地址)
- 有一个专用“指针”标识当前已使用内存的”顶部”
2、程序中的栈区:一段特殊的专用内存区
![](https://img-blog.csdnimg.cn/0e50dc0434a24ebd95d15ea13f73ff68.png)
3、实例分析:逆序打印单链表中的偶数结点
![](https://img-blog.csdnimg.cn/7654f685c58f4a53a515b0699c06697d.png)
4、编程实验:函数调用栈分析
void r_print_even(Node* list)
![](https://img-blog.csdnimg.cn/0d98872d4c794616a9d68a1308d3dda6.png)
5、八皇后问题
在一个8×8的国际象棋棋盘上,有8个皇后,每个皇后占一格;要求皇后间不会出现相互“攻击”的现象
(不能有两个皇后处在同一行、同一列或同一对角线上)。
![](https://img-blog.csdnimg.cn/05cc7345347b4f8a84d7515927cb44eb.png)
6、关键数据结构定义
- 棋盘:二维数组( 10 * 10 )
- 位置:struct Pos;
- 方向
- 水平:(-1,0),(1,0)
- 垂直:(0,-1),(0,1)
- 对角线:(-1,1),(-1,-1),(1,-1),(1,1)
7、算法思路
1.初始化:j = 1
2.初始化:i = 1
3.从第j行开始,恢复 i 的有效值(通过函数调用栈进行回溯),判断第i个位置
a. 位置i可放入皇后:标记位置(i,j), j++,转步骤2
b. 位置i不可放入皇后:i++,转步骤a
c. 当i>8时,j--,转步骤3
结束:
第8行有位置可放入皇后
8、编程实验:八皇后问题的递归解法
class QueueSolution;
9、小结
- 程序运行后的栈存储区专供函数调用使用
- 栈存储区用于保存实参,局部变量,临时变量,等
- 利用栈存储区能够方便的实现回溯算法
- 八皇后问题是栈回溯的经典应用
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)