当前位置: 首页 > 数据结构&&算法 > 正文

数据结构小结 (四) 串

第四章 串 及其一些算法

前言

其实字符串这里感觉就没有什么数据结构,应要说的话,KMP ,BF ,FF 这些其实是算法的范畴,但是国内的一些数据结构书非要把C 标准库的一些string 中的函数拿出来硬是凑出了数据结构串这章节的内容,也是够了。

概念

长度

空串

子串

主串

相等

空格串

求子串的个数

面试小技巧

这就是strcpy 的源码,是不是很难看懂?没事有我在,可以给你解释清楚,包括后边我们发现就算是glibc 库也有一些不尽人意的地方。

想看懂这段代码,需要一些你曾经不知道的东西。 首先注意const 的使用,这很关键。我们防止不小心修改我们的源信息,还是使用const 比较好。

其次注意类型转换,然后注意这个类型,估计很多程序猿都不知道这个类型,普及下,这是两个指针相减的结果类型,主要是求出两个指针的相对偏移量,unisgned long int 类型,接着看着两条语句:

这段代码还是很精致的,但是我为什么说还有缺陷呢?有点鸡蛋里挑骨头了,既然是让我们写,我们还必须考虑到判空的情况,所以增加两条判断是否有NULL 还是很出彩的。

例如:

再看一个strcat

下来说下KMP

KMP 暂时只说两种思路吧,一种是学校老师教偏经验的用法,另一种是更为通用的更一般的用法。 考试的形式主要以选择题,完成题为主。 KMP 相信大家上数据结构课的时候都学习过了,确实不容易理解,复杂的证明就不说了。 我们从几个方面来谈谈这个KMP。 以下所有都以

父串:a c a b a a b a a b c a c a a b c

子串:a b a a b c a c

为例。

KMP 干了什么?

首先给你两个字符串,A 与 B ,需要你判断A 是不是 在B中,如果是返回A的位置,如果我们无脑的使用循环比较,复杂读为O(lenth(A)*lenth(B)) ,使用KMP是O(lenth(A) + lenth(B)) .确实减少了时间复杂度。 KMP 就干了一件这事。

KMP 的两种用法

KMP 的两种用法就是根据我们使用计算next 的值的方法不同,使用next 的值的不同来区分的。

首先说下求next的广泛使用方式

求next值的代码:

以上就是使用比较广泛的一种用法,下来说学校学的一种方法。

KMP 的快速使用方式

学校教授的方法一种可以快速求出next值的方法,当然需要它自己的比较方法。

个人感觉这个方法有点“暴力”。

a b a a b c a c

0 1 1 2 2 3 1 2

得出next 值后进行匹配

第一趟

第二趟

第三趟

第四趟

总的来说想要精研算法的还是去看算法导论吧。

本文固定链接: http://zmrlinux.com/2015/12/20/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%b0%8f%e7%bb%93-%ef%bc%88%e5%9b%9b%ef%bc%89-%e4%b8%b2/ | Kernel & Me

该日志由 root 于2015年12月20日发表在 数据结构&&算法 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 数据结构小结 (四) 串 | Kernel & Me