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

时间: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] } 本次试验过程中,最重要的是看书,通过看书再实践,对知识点有更多的了解。

数据结构实验三实验报告(9).doc 将本文的Word文档下载到电脑

精彩图片

热门精选

大家正在看

× 游客快捷下载通道(下载后可以自由复制和排版)

限时特价:7 元/份 原价:20元

支付方式:

开通VIP包月会员 特价:29元/月

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219