数据结构实验三实验报告(9)

数据结构实验报告

printf("S=%s\n",&S);

}

实验结果：

4-19

4-20

总结与思考

本次试验对串类型的实现方法有所了解，同时也对简单文字处理的设计方法有了初步的了解， 熟悉C语言的字符和把字符串处理的原理和方法，C语言把字符串字面量作为字符数组来处理。当C语言编译器在程序中遇到长度为n的字符串字面量时，它会为字符串字面量分配长度为n+1的内存空间，在末尾增加一个额外的字符——空字符(\0)。

了解实践了模式匹配算法。

BF算法的基本思想是：

从目标串T的起始比较位置pos开始（在后面的案例中，我们默认pos = 0），和模式串P的第一个字符比较之，若匹配，则继续逐个比较后继字符，否则从串T的下一个字符起再重新和串P的字符比较之。依此类推，直至串P中的每个字符依次和串T中的一个连续的字符序列（即匹配子串）相等，则称匹配成功，返回该匹配子串的首字符下标；否则成匹配不成功，返回-1。BF算法的思想很直接，也很容易理解，其时间复杂度为O（lenT*lenP），其中lenT和lenP分别为串T和串P的长度。

KMP算法：

这是三个人提出的算法，三人的姓氏首字母命名。其思想很简单，却很有效。这种思想同时也是后面三种算法的基础。KMP算法的基本思想是：若某趟匹配过程中T[i]和P[j]不匹配，而前j-1个字符已经匹配。此时只需右移模式串P，文本串T不动，即指针i不回溯，让P[k]与T[i]继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串S无关，因此K可以事先确定。若定义函数next(j)=K，则next函数的定义应为： next(j)=Max{k| P[1..K-1]=P[j-k+1.. j-1] } 本次试验过程中，最重要的是看书，通过看书再实践，对知识点有更多的了解。