算法分析与设计实验报告 Microsoft Word 文档 (1)

华中师范大学计算机科学系

实验报告书

课程名： 《算法分析与设计》 班 级 ： 计科系0802 学 号 ： 2008210707 姓 名 ： 刘怀宁 指导老师 ： 张茂元

提交日期：2010-11-23

1

目录：

实验三·······················3 ——6 实验五·······················7 ——9 实验六·······················10——12 实验七·······················13——16 实验八·······················17——18

说明：单元实验报告包含五个内容

A． 实验题目 B． 实验目的 C． 实验要求

D． 程序代码及运行结果（分割为两面）E． 心得体会

程序代码实现语言：C++ 编程工具：visual C++

2

实验三 实验项目 ———串匹配问题

1．

实验题目

给定一个文本，在该文本中查找并定位任意给定的字符串 2．

实验目的

（1） 深刻理解并掌握蛮力法的设计思想; （2） 提高应用蛮力法设计算法的技能；

（3） 理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度

的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。

3．

实验要求

（1）实现BF算法；

（2）实现BF算法的改进算法：KMP算法和ＢＭ算法；

（3）对上述三个算法进行时间复杂性分析，并设计实验程序验证分析结果。 4．

程序代码及对应运行结果

（1）BF算法

#include

3

using namespace std;

int BF(char *text, char *pattern) { int i,j;//分别指向每一个S和T的字符 for( i=0;i

void main() { char *Text=\ char *Pattern=\ int s=BF(Text,Pattern); cout<

（2）KMP算法

#include #include

void get_nextval(const char *T, int next[]); int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的

值。 {

if( !Text||!Pattern|| Pattern[0]=='\\0' || Text[0]=='\\0' )//

return -1;//空指针或空串，返回-1。

int len=0;

const char * c=Pattern;

while(*c++!='\\0')//移动指针比移动下标快。

{

++len;//字符串长度。 }

int *next=new int[len+1];

get_nextval(Pattern,next);//求Pattern的next函数值

int index=0,i=0,j=0; while(Text[i]!='\\0' && Pattern[j]!='\\0' ) {

if(Text[i]== Pattern[j]) {

++i;// 继续比较后继字符

++j; } else {

index += j-next[j]; if(next[j]!=-1) j=next[j];// 模式串向右移动

else {

j=0; ++i; } } }//while

delete []next;

if(Pattern[j]=='\\0')

return index;// 匹配成功

4

else

return -1; }

int main()//abCabCad {

char* text=\ char*pattern=\ //getNext(pattern,n); //get_nextval(pattern,n);

cout<

void get_nextval(const char *T, int next[]) {

// 求模式串T的next函数值并存入数组 next。

int j = 0, k = -1; next[0] = -1;

while ( T[j/*+1*/] != '\\0' ) {

if (k == -1 || T[j] == T[k]) {

++j; ++k; if (T[j]!=T[k])

next[j] = k; else

next[j] = next[k];

}// if else

k = next[k]; }// while

}// get_nextval

（3）BM算法 #include using namespace std;

int Dist(char *t,char ch) { int len = strlen(t); int i = len - 1; if(ch == t[i])

return len;

i--;

while(i >= 0)

{

if(ch == t[i]) return len - 1 - i; else i--; }

return len; }

int BM(char *s, char *t) {

int n = strlen(s); int m = strlen(t); int i = m-1; int j = m-1;

while(j>=0 && i

if(s[i] == t[j]) { i--; j--; } else {

i += Dist(t,s[i]); j = m-1; } }

if(j < 0) { return i+1; }

return -1; }

void main()

5