数据结构实验三实验报告(9)
时间:2025-07-11
时间:2025-07-11
数据结构实验报告
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] } 本次试验过程中,最重要的是看书,通过看书再实践,对知识点有更多的了解。
上一篇:2014年山东高职专科排名总表
下一篇:海鲜厨房教学设计