堆串的朴素匹配,C\C++交流,技术交流,鱼C论坛

WFR 发表于 2024-9-18 21:14:21

堆串的朴素匹配

#include<stdio.h>
#include<stdlib.h>//声明内存的函数在这里
#include<string.h>

typedef struct {
char* str;
int length;
}String;
String* init_string(void)
{
String *L = (String*)malloc(sizeof(String));
L->str= NULL;
L->length = 0;
return L;

}
intSubString(String* L, String S, int pos, int len)//求子串，用*L返回子串从pos这个位置，选len长度的子串S
{
if (S.length < pos + len - 1||pos<0||len<0)
{
printf("子串出现错误");
return 0;
}
else
{
L->str = (char*)malloc((len + 1) * sizeof(char)); // +1 是为了存放末尾的 '\0'
for (int i = pos; i < pos + len; i++)
{
L->str = S.str;
}
L->str='\0';
L->length = len;
}
return 1;
}

int Index(String S, String L)//S是主串，L是子串
{
int i = 0, j = 0;
while (i <=S.length&& j <=L.length)
{
if (S.str == L.str)
{
i++;
j++;
}
else
{
i = i - j + 1;
j = 0;
}
}
if (j >L.length)
{
printf("找到子串首个位置：%d",i-j+1);
return i - j + 1;

}
else
{
printf("没找到！！！");
return 0;
}

}

int main(void)
{

String *S=init_string();
String *L=init_string();

char* ch = "hello world";
S->str = (char*)malloc(sizeof(char)*(strlen(ch)+1));

strcpy_s(S->str,strlen(ch)+1, ch);//进行安全的输入；
S->length = strlen(ch) + 1;//没有设置S的长度，导致SubString函数运行不了
SubString(L, *S, 1, 5);
printf("子串L：%s\n", L->str);
printf("子串S：%s\n", S->str);

Index(*L,*S);
free(S);
free(L);

}

Index返回值永远都是错误的

FishC 发表于 2024-9-18 21:15:38

你给出的代码部分有一些错误和疏漏，尤其是在字符串处理和指针操作方面。现针对这些问题，下面是修改后的版本，并添加了一些注释以解释每个修改点。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
char* str;
int length;
} String;

String* init_string(void) {
String* L = (String*)malloc(sizeof(String));
L->str = NULL;
L->length = 0;
return L;
}

int SubString(String* L, String S, int pos, int len) {
if (S.length < pos + len - 1 || pos <= 0 || len < 0) {
   return 0; // 参数不合理，返回失败
} else {
   L->str = (char*)malloc(sizeof(char) * (len + 1)); // 分配内存
   strncpy(L->str, S.str + pos - 1, len);// 注意pos - 1，因为字符串下标从0开始
   L->str = '\0'; // 字符串应该有结束符
   L->length = len;
}
return 1;
}

int Index(String S, String L) {
int i = 0, j = 0;
while (i < S.length && j < L.length) {
   if (S.str == L.str) {
         i++;
         j++;
   } else {
         i = i - j + 1; // 回溯
         j = 0;
   }
}
if (j == L.length) {
   return i - j + 1; // 返回匹配值的起始位置
} else {
   return -1; // 未找到
}
}

int main(void) {
String* S = init_string();
String* L = init_string();
char ch;
printf("输入主串S: ");
gets_s(ch, sizeof(ch)); // 使用gets_s防止输入过长

S->str = (char*)malloc(sizeof(char) * (strlen(ch) + 1));
strcpy(S->str, ch);
S->length = strlen(ch);

SubString(L, *S, 1, 5); // pos和len输入需要合理
printf("子串L: %s\n", L->str);
printf("主串S: %s\n", S->str);

int position = Index(*S, *L);
if (position != -1) {
   printf("子串L在主串S中的位置: %d\n", position);
} else {
   printf("未找到子串L\n");
}

free(S->str);
free(S);
free(L->str);
free(L);

return 0;
}

关键修改点有：
1. `SubString`函数中增加了对内存的分配，并确保正确拷贝和终止符结尾。
2. `Index`函数中的字符串匹配逻辑修正，并最终返回匹配的初始位置。
3. 提高了安全性，比如使用`gets_s`函数防止缓冲区溢出。
4. 在主程序中适当地设置字符串，并打印相应结果，防止内存泄漏，最后注意释放所有分配的内存。

以上修改确保了代码能够正常运行，并且`Index`函数返回正确的匹配位置。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

WFR 发表于 2024-9-18 21:27:17

FishC 发表于 2024-9-18 21:15
你给出的代码部分有一些错误和疏漏，尤其是在字符串处理和指针操作方面。现针对这些问题，下面是修改后的版 ...

不正确

FishC 发表于 2024-9-18 21:32:40

WFR 发表于 2024-09-18 21:27
不正确

明白，我们逐一来解决代码中的问题。您提到了两个主要功能：`SubString`（提取子串）和`Index`（简单匹配），同时提到`Index`返回值总是错误的。下面我们一步步修正代码。

### 完整代码：
以下是修正后的完整代码并添加了必要的注释：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义字符串结构体
typedef struct {
char* str;
int length;
} String;

// 初始化字符串
String* init_string(void) {
String* L = (String*)malloc(sizeof(String));
L->str = NULL;
L->length = 0;
return L;
}

// 求子串函数
int SubString(String* L, String S, int pos, int len) {
// 检查边界条件
if (S.length < pos + len - 1 || pos < 1) return 0;

L->str = (char*)malloc((len + 1) * sizeof(char));
strncpy(L->str, S.str + pos - 1, len);
L->str = '\0';
L->length = len;
return 1;
}

// 简单匹配算法
int Index(String S, String L) {
int i = 0, j = 0;
while (i < S.length && j < L.length) {
   if (S.str == L.str) {
         i++;
         j++;
   } else {
         i = i - j + 1;
         j = 0;
   }
}
// 如果匹配成功，返回子串的起始位置
if (j == L.length) {
   return i - j + 1;
}
return 0; // 未找到匹配子串
}

// 主函数
int main() {
String* S = init_string();
String* L = init_string();

char ch[] = "FishC.com";
S->str = (char*)malloc(sizeof(char) * (strlen(ch) + 1));
strcpy(S->str, ch);
S->length = strlen(ch);

// 提取子串
if (SubString(L, *S, 1, 5)) {
   printf("子串 L：%s\n", L->str);
} else {
   printf("提取子串失败\n");
}

// 查看子串位置
int position = Index(*S, *L);
if (position > 0) {
   printf("子串L在主串S中的位置是：%d\n", position);
} else {
   printf("未找到子串L\n");
}

// 释放内存
free(S->str);
free(S);
free(L->str);
free(L);

return 0;
}

### 修改点：
1. **内存分配和字符串长度管理**：
- 初始化字符串时分配合适的内存。
- 设置`String`结构体的`length`字段，使其正确描述字符串的长度。

2. **子串提取函数 `SubString`**：
- 调整边界检查条件。
- 使用`strncpy`提取子串，并在最后添加空字符以形成合法的C字符串。

3. **简单匹配算法 `Index`**：
- 维护两个索引`i`和`j`，遍历主串和子串。
- 匹配成功时返回起始位置，失败返回0。

### 测试和验证
- 初始化主串并提取子串。
- 验证`Index`函数返回正确子串位置。

希望这次的解释和代码修改能帮助你解决问题。如果还有其他问题，请随时提问！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

页: [1]

鱼C论坛's Archiver

堆串的朴素匹配