C++实现串的顺序存储结构和堆存储结构。 具备设计串的古典模式匹配算法程序的能力。并分别运行
时间: 2024-03-16 21:43:38 浏览: 27
(1)串的顺序存储结构
在C++中,可以使用数组来实现串的顺序存储结构,具体代码如下:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXSIZE = 100; // 定义最大串长
// 串的顺序存储结构定义
typedef struct {
char str[MAXSIZE + 1]; // 存储串的字符数组
int length; // 串的实际长度
} SqString;
// 初始化串
void InitString(SqString &s, char *str) {
int len = strlen(str);
if (len > MAXSIZE) { // 如果串长超过最大长度,则截取前MAXSIZE个字符
len = MAXSIZE;
}
for (int i = 0; i < len; i++) {
s.str[i] = str[i];
}
s.str[len] = '\0'; // 添加串结束符
s.length = len;
}
// 打印串
void PrintString(SqString s) {
cout << s.str << endl;
}
// 古典模式匹配算法
int Index_KMP(SqString s, SqString t) {
int i = 0, j = 0, next[MAXSIZE + 1];
GetNext(t, next);
while (i < s.length && j < t.length) {
if (j == -1 || s.str[i] == t.str[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == t.length) {
return i - j;
} else {
return -1;
}
}
// 获取next数组
void GetNext(SqString t, int next[]) {
int i = 0, j = -1;
next[0] = -1;
while (i < t.length) {
if (j == -1 || t.str[i] == t.str[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
int main() {
char str1[] = "ababcabcacbab";
char str2[] = "abcac";
SqString s, t;
InitString(s, str1);
InitString(t, str2);
PrintString(s);
PrintString(t);
int pos = Index_KMP(s, t);
cout << "pos = " << pos << endl;
return 0;
}
```
(2)串的堆存储结构
在C++中,可以使用动态分配内存的方式来实现串的堆存储结构,具体代码如下:
```c++
#include <iostream>
#include <cstring>
using namespace std;
// 串的堆存储结构定义
typedef struct {
char *str; // 存储串的字符数组
int length; // 串的实际长度
} HeapString;
// 初始化串
void InitString(HeapString &s, char *str) {
int len = strlen(str);
s.str = new char[len + 1]; // 动态分配内存
strcpy(s.str, str);
s.length = len;
}
// 打印串
void PrintString(HeapString s) {
cout << s.str << endl;
}
// 古典模式匹配算法
int Index_KMP(HeapString s, HeapString t) {
int i = 0, j = 0, *next = new int[t.length + 1];
GetNext(t, next);
while (i < s.length && j < t.length) {
if (j == -1 || s.str[i] == t.str[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == t.length) {
return i - j;
} else {
return -1;
}
}
// 获取next数组
void GetNext(HeapString t, int next[]) {
int i = 0, j = -1;
next[0] = -1;
while (i < t.length) {
if (j == -1 || t.str[i] == t.str[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
int main() {
char str1[] = "ababcabcacbab";
char str2[] = "abcac";
HeapString s, t;
InitString(s, str1);
InitString(t, str2);
PrintString(s);
PrintString(t);
int pos = Index_KMP(s, t);
cout << "pos = " << pos << endl;
return 0;
}
```
以上两个程序分别实现了串的顺序存储结构和堆存储结构,并利用古典模式匹配算法进行了串匹配。可以根据实际需要选择使用哪种存储结构。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)