设计一个算法,实现子串位置查找(在顺序串上实现)。 (1) 包括结构体定义和主函数 (2) 要求关键代码做好注释 (2)任务提交要求 (1) 提交解题思路,放在下面
时间: 2024-12-09 19:18:26 浏览: 13
查找子串程序
设计一个简单的线性搜索算法来查找子串在字符串中的位置。这里我们假设输入的子串不会超过原字符串长度。
首先,我们创建一个结构体`SubstringSearch`,用于包含必要的数据和功能:
```c++
// 结构体定义
typedef struct {
char* str; // 存储原始字符串
int len; // 原始字符串长度
char* sub; // 子串
int sub_len; // 子串长度
int index; // 当前找到的子串起始位置
} SubstringSearch;
// 主函数
void substring_search(SubstringSearch* ss) {
if (ss->str == NULL || ss->sub == NULL) {
printf("Error: Input strings cannot be NULL.\n");
return;
}
for (int i = 0; i <= ss->len - ss->sub_len; i++) { // 遍历整个字符串
bool found = true;
// 检查子串是否连续匹配
for (int j = 0; j < ss->sub_len; j++) {
if (ss->str[i + j] != ss->sub[j]) {
found = false;
break;
}
}
if (found) {
ss->index = i; // 找到子串的位置
printf("Substring found at position %d\n", ss->index);
break; // 如果找到了就立即退出循环
}
}
if (!found) {
printf("Substring not found in the given string.\n");
}
}
```
**任务提交要求**:
1. 解题思路说明:此算法采用的是线性查找(也叫朴素查找),从原始字符串的第一个字符开始,逐个字符对比子串,直到找到子串或遍历完整个字符串。如果找到匹配,则记录下起始位置;如果没有找到,则报告未找到。
2. 提交的关键代码部分已注释,解释了如何检查子串匹配以及遇到匹配后的处理。
3. 要求测试用例,例如输入字符串和子串,以验证函数的正确性。例如:
```sh
void test() {
SubstringSearch ss = {"Hello, World!", "World", 5};
substring_search(&ss);
}
```
运行这个测试用例,应该能输出子串"World"在"Hello, World!"中的位置。
阅读全文