此篇需要结合OneNote上的笔记进行阅读 |
---|
串的基本操作
串操作的引申
1.Index操作:Index的定位操作可以拆分为一个while循环和一个比较操作;(当然这个循环是可以有很多种写法的,比如更高效的写法是先判断要比较的这句话有多长如果主串都没这么长那直接不比了)且这个可以由strlen去写,比如我们先把要比较的字符串有多长算出来然后再从主串中依次拿出这么长的子串去跟他进行比较;
2.StrCopy:StrCopy复制操作可以借由中间变量再加strcpy函数达到只需更改MaxSize即可一键复制完成,当然这里需要注意上面图片1中的情况即初始化节点的时候节点数据域可能不是单个字符而是字符串,或者在顺序存储的时候这些都是不一样的。
3.StrEmpty:判空操作这个不多说只需去判断头指针是否为NULL即可;
4.Replace:这里的要求有两个:第一个是全部替换既与之相同的不止替换一个,2.替换时不得重叠替换。这两个的解决方案参考Index函数,我们每次循环都是按照子串的长度去走的并且一旦匹配直接让主串的循环加上子串的长度并在加上之后继续寻找;
5.StrInsert:插入操作,这里的插入操作要求是可以指定位置的,也就是说给顺序表的插入带来了很多的麻烦,一旦在第一个进行插入后面的所有数据都要向后进行移动;对于链表来说就要方便的多,但是还是要注意你初始化的节点里面的单个字符还是整个字符串如果是字符串的话这个插入操作又要麻烦很多;
6.StrDelete:删除操作,删除操作跟上面的插入操作逻辑思想都是一样的,只不过要兼顾把他删除完成以后的连接工作(特指链表),这里的删除指的是长度可变的删除,那么我们还是需要一个循环并且把这些删掉的东西要Free掉,不能直接把后面的连接前面这样看起来很方便但是在程序一直运行的情况下必定产生大量冗余;
7.ClearString:清空操作,直接把S变成NULL(无头结点时),或者直接变成头结点所在的位置(有头结点时)即可;(但是我觉得这个只适用于顺序表的存储方式,因为链表只删数据不删节点的话必定产生冗余;)
8.DestroyString:销毁串这个对啥都是最简的无论你是线性表或者是链表一步到位;
KMP算法
1.KMP算法的灵魂就是找新字,老字在之前的比较的时候我们都是知道的所以我们找新字即可,且KMP的核心就是主串是不回溯的只有子串才回溯。
(问题:我们在知道不匹配跳过的原则后,假如我们要匹配的东西是带有重复的呢;)
解决:KMP算法虽然主串是不回溯的但是在第一次匹配失败后要扫描匹配的主串看是否有与子串首字符相同的字符,我们从那里开始而不是直接跳到匹配失败的地方;且我们要注意:跳的这个长度刚好是,失败的位置的前面这个字符串最长的相同真前缀和真后缀的长度;且总是这样;
手动制作Ntext表其实跟上面是一样的,我们还是
需要比较他的真前缀和真后缀并且找到最大的真前缀和真后缀
写在他的Next表中;
望江楼上望江江流的真后缀是:最后单独的字然后加上前面且不全等于他的字
流,江流,江江流,望江江流,上望江江流。。。。
真前缀是一样的不存在组合必读按照顺序,且注意前缀一定要包含第一个字;
且我们要注意通俗的来说后缀的最后一个字一定是要的,
前缀的第一个字一定是要的;如果没有最后一个字的话是叫子串,但是有最后一个字的才能叫后缀;
注:本章节的内容必须结合OneNote上的笔记和后序做的笔记去看,因为大部分东西都在OneNote上面;
下面是本章主要代码的实现
new12.1蛮力匹配算法。
首先遇到的问题就是返回值的问题,我们匹配算法是为了求在主串中第几位的,也就是说返回的是个int类型的变量;
且要传入的是两个串一个是主串一个是匹配的串;
接下来的蛮力匹配算法的思想等同于我们上面写的Index的思想;
8 //new12.1蛮力匹配算法
9 int InDex(char * chang,char * duan){
10 int Ichang = strlen(chang);
11 int Iduan = strlen(duan);
12 int TagChang = 0;int TagDuan = 0;
13 while((TagChang < Ichang )&&(TagDuan < Iduan)){
14 if(chang[TagChang] == duan[TagDuan]){
15 TagDuan++;
16 TagChang++;
17 }else{
18 TagDuan = 0;
19 TagChang = TagChang - (TagDuan - 1 );
20 }
21 }
22 return TagDuan == Iduan?TagChang - TagDuan:-1;
23 }