文档库

最新最全的文档下载
当前位置:文档库 > 数据结构next函数的解析与练习

数据结构next函数的解析与练习

首先看看next 数组值的求解方法。

例如:

数据结构next函数的解析与练习

next 数组的求解方法是:第一位的next 值为0,第二位的next 值为1,后面求解每一位的next 值时,根据前一位进行比较。首先将前一位与其next 值对应的内容进行比较,如果相等,则该位的next 值就是前一位的next 值加上1;如果不等,向前继续寻找next 值对应的内容来与前一位进行比较,直到找到某个位上内容的next 值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next 值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next 值即为1。

看起来很令人费解,利用上面的例子具体运算一遍。

1.前两位必定为0和1。

2.计算第三位的时候,看第二位b 的next 值,为1,则把b 和1对应的a 进行比较,不同,则第三位a 的next 的值为1,因为一直比到最前一位,都没有发生比较相同的现象。

3.计算第四位的时候,看第三位a 的next 值,为1,则把a 和1对应的a 进行比较,相同,则第四位a 的next 的值为第三位a 的next 值加上1。为2。因为是在第三位实现了其next 值对应的值与第三位的值相同。

4.计算第五位的时候,看第四位a 的next 值,为2,则把a 和2对应的b 进行比较,不同,则再将b 对应的next 值1对应的a 与第四位的a 进行比较,相同,则第五位的next 值为第二位b 的next 值加上1,为2。因为是在第二位实现了其next 值对应的值与第四位的值相同。

5.计算第六位的时候,看第五位b 的next 值,为2,则把b 和2对应的b 进行比较,相同,则第六位c 的next 值为第五位b 的next 值加上1,为3,因为是在第五位实现了其next 值对应的值与第五位相同。

6.计算第七位的时候,看第六位c 的next 值,为3,则把c 和3对应的a 进行比较,不同,则再把第3位a 的next 值1对应的a 与第六位c 比较,仍然不同,则第七位的next 值为1。

7.计算第八位的时候,看第七位a 的next 值,为1,则把a 和1对应的a 进行比较,相同,则第八位c 的next 值为第七位a 的next 值加上1,为2,因为是在第七位和实现了其next 值对应的值与第七位相同。

在计算nextval 之前要先弄明白,nextval 是为了弥补next 函数在某些情况下的缺陷而产生的,例如主串为“aaabaaaab”、模式串为“aaaab”那么,比较的时候就会发生一些浪费的情况:比较到主串以及模式串的第四位时,发现其值并不相等,据我们观察,我们可以直接从主串的第五位开始与模式串进行比较,而事实上,却进行了几次多余的比较。使用nextval

可以去除那些不必要的比较

免费下载Word文档免费下载: 数据结构next函数的解析与练习

(共4页)