数据结构实验报告

进队

deQueue（）

出队

3、实验数据与结果

2.3实验3(exp4-3)

1、题目

编写一个程序exp4-3.cpp，实现顺序串的各种匹配模式运算，并在此基础上完成如下功

能：

(1) 建立“abcabcdabcdeabcdefabcdefg”目标串和“abcdeabcdefab”模式串t；

13

数据结构实验报告

(2) (3) (4) (5) 简单匹配算法求t在s中过的位置； 由模式串t求出next的值和nextval的值 采用KMP算法求t在s中的位置

采用改进的KMP算法求t在s中的位置

2、算法设计

(1) 设计思路

本题的关键是KMP算法的思路以及改进后的KMP算法思路，一般的模式串匹配算法

是按个扫描目标串和模式串，如果不匹配，则目标串跳转到下一个字母重新匹配，这在很大程度上做了很多重复匹配的工作，所以KMP算法就是在此基础上的改进

(2) 程序关系图

StrAssignDispStrIndexmainGetNextKMPIndexGetNextvalKMPIndexpro

(3) 函数功能描述 StrAssign（）

14

数据结构实验报告

将str[]中的字符串复制到s中 DispStr（）

输出字符串 Index（）

15

数据结构实验报告

简单的匹配算法

GetNext（）

根据模式串求出下一个字符的下标

KMPIndex（）

16