算法与数据结构实验报告——字符串

课程名称： 算法与数据结构课程设计

实验名称： 字符串的模式匹配

实验完成人：

日 期： 2019 年 10月 25 日

一、 实验目的

本次实验的目的是熟悉串类型的实现方法和文本模式匹配方法，熟悉串的键盘输入获取方式。

二、 实验内容 1、 数值转换问题

2、 3、 4、

[问题描述]

设有两个字符串s和t，首先将s1与t1进行比较，直到s的某一个字符si和ti相同，

再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si-j+2，t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部

5、 6、 7、

比较完，则说明本趟匹配成功，本趟的起始位置是i-j+1，否则，匹配失败。 [基本要求]

本实验要求学生掌握串的特点及顺序定长存储的方式，掌握模式匹配的基本思想及其算

法。由用户通过键盘输入建立一个主字符串和搜索串，如果主串中包含要搜索的子串，返回子串在主串中的起始位置，否则返回搜索失败。

三、 实验环境

Windows下利用vs 2019完成,语言c++

四、 实验过程描述

首先构造Astring类，内含字符数组string[],next[]，以及一些操作。

class AString

{

private:

char string[MAXLENGTH+1]; //字符数组 int length;

int next[MAXLENGTH + 1]; //KMP用 public:

AString();

static int Index(AString, AString); //暴力算法 static int Index_KMP(AString, AString); //KMP

void Get_next(); //KMP用 };

实现相应功能:

输入字符并判断，读到空格时停下。 写在构造函数中：

AString::AString() {

char temp=0; int i = 1; while (1) {

scanf(\"%c\", &temp);

if (temp == ' ' || temp == '\\n') break;

string[i] = temp; i++; }

length = i-1;

//读到回车或空格停下

string[0] = length; }

//第0位来存放长度

用暴力算法获得index：

int AString::Index(AString s,AString t) {

int i = 1, j = 1, index;

while (i <= s.length && j <= t.length) {

if (s.string[i] == t.string[j]) {

++i; ++j; } else {

i = i - j + 2; j = 1;

//分别比较，相同则同时后移

//不同则回溯

}

} }

if (j > t.length)

return i - t.length; else

return 0;

得到next[]:

void AString::Get_next() {

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

while (j <= this->length) {

if (k == 0 || this->string[j] == this->string[k]) {

++j; ++k;

this->next[j] = k; } else

k = this->next[k]; }

KMP算法：

int AString::Index_KMP(AString s, AString t) {

t.Get_next(); int i = 1,j = 1;

while (i <= s.length && j <= t.length) {

if (j == 0 || s.string[i] == t.string[j]) {

++i; ++j; }

else j =t.next[j]; }

if (j > t.length)

return i - t.length; else

return 0; }

五、 实验结果

查找成功，返回位置：

查找失败，返回0：

六、 源代码：

Astring.h #pragma once

#define MAXLENGTH 255 #include #include

using namespace std; class AString {

private:

char string[MAXLENGTH+1]; //字符数组 int length;

int next[MAXLENGTH + 1]; //KMP用 public:

AString();

static int Index(AString, AString); //暴力算法 static int Index_KMP(AString, AString); //KMP

void Get_next(); //KMP用

};

Astring.cpp

#include \"AString.h\" AString::AString() {

char temp=0; int i = 1; while (1) {

scanf(\"%c\", &temp);

if (temp == ' ' || temp == '\\n') break;

string[i] = temp; i++; }

length = i-1;

//读到回车或空格停下

string[0] = length; //第0位来存放长度 }

int AString::Index(AString s,AString t) {

int i = 1, j = 1, index;

while (i <= s.length && j <= t.length) {

if (s.string[i] == t.string[j]) {

++i; ++j; } else {

//分别比较，相同则同时后移

i = i - j + 2; //不同则回溯 j = 1; } }

if (j > t.length)

return i - t.length; else

return 0; }

void AString::Get_next() {

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

while (j <= this->length) {

if (k == 0 || this->string[j] == this->string[k]) {

++j; ++k;

this->next[j] = k; } else

k = this->next[k]; } }

int AString::Index_KMP(AString s, AString t) {

t.Get_next(); int i = 1,j = 1;

while (i <= s.length && j <= t.length) {

if (j == 0 || s.string[i] == t.string[j]) {

++i;

++j; }

else j =t.next[j]; }

if (j > t.length)

return i - t.length; else

return 0; }

Main.cpp #include #include \"AString.h\" int main() {

cout << \"输入主串\" << endl; AString a;

cout << \"输入字串\" << endl; AString b;

cout<<\"暴力算法得：\"<