堆串的朴素匹配

WFR

#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)//求子串，用*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[i-pos] = S.str[i];
                }
                L->str[len]='\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[i] == L.str[j])
                {
                        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

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. typedef struct {
   
6.     char* str;
   
7.     int length;
   
8. } String;
   
9. 
   
10. String* init_string(void) {
    
11.     String* L = (String*)malloc(sizeof(String));
    
12.     L->str = NULL;
    
13.     L->length = 0;
    
14.     return L;
    
15. }
    
16. 
    
17. int SubString(String* L, String S, int pos, int len) {
    
18.     if (S.length < pos + len - 1 || pos <= 0 || len < 0) {
    
19.         return 0; // 参数不合理，返回失败
    
20.     } else {
    
21.         L->str = (char*)malloc(sizeof(char) * (len + 1)); // 分配内存
    
22.         strncpy(L->str, S.str + pos - 1, len);  // 注意pos - 1，因为字符串下标从0开始
    
23.         L->str[len] = '\0'; // 字符串应该有结束符
    
24.         L->length = len;
    
25.     }
    
26.     return 1;
    
27. }
    
28. 
    
29. int Index(String S, String L) {
    
30.     int i = 0, j = 0;
    
31.     while (i < S.length && j < L.length) {
    
32.         if (S.str[i] == L.str[j]) {
    
33.             i++;
    
34.             j++;
    
35.         } else {
    
36.             i = i - j + 1; // 回溯
    
37.             j = 0;
    
38.         }
    
39.     }
    
40.     if (j == L.length) {
    
41.         return i - j + 1; // 返回匹配值的起始位置
    
42.     } else {
    
43.         return -1; // 未找到
    
44.     }
    
45. }
    
46. 
    
47. int main(void) {
    
48.     String* S = init_string();
    
49.     String* L = init_string();
    
50.     char ch[50];
    
51.     printf("输入主串S: ");
    
52.     gets_s(ch, sizeof(ch)); // 使用gets_s防止输入过长
    
53.    
    
54.     S->str = (char*)malloc(sizeof(char) * (strlen(ch) + 1));
    
55.     strcpy(S->str, ch);
    
56.     S->length = strlen(ch);
    
57. 
    
58.     SubString(L, *S, 1, 5); // pos和len输入需要合理
    
59.     printf("子串L: %s\n", L->str);
    
60.     printf("主串S: %s\n", S->str);
    
61. 
    
62.     int position = Index(*S, *L);
    
63.     if (position != -1) {
    
64.         printf("子串L在主串S中的位置: %d\n", position);
    
65.     } else {
    
66.         printf("未找到子串L\n");
    
67.     }
    
68. 
    
69.     free(S->str);
    
70.     free(S);
    
71.     free(L->str);
    
72.     free(L);
    
73. 
    
74.     return 0;
    
75. }

复制代码

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

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

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

WFR

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

不正确

FishC

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

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

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. // 定义字符串结构体
   
6. typedef struct {
   
7.     char* str;
   
8.     int length;
   
9. } String;
   
10. 
    
11. // 初始化字符串
    
12. String* init_string(void) {
    
13.     String* L = (String*)malloc(sizeof(String));
    
14.     L->str = NULL;
    
15.     L->length = 0;
    
16.     return L;
    
17. }
    
18. 
    
19. // 求子串函数
    
20. int SubString(String* L, String S, int pos, int len) {
    
21.     // 检查边界条件
    
22.     if (S.length < pos + len - 1 || pos < 1) return 0;
    
23. 
    
24.     L->str = (char*)malloc((len + 1) * sizeof(char));
    
25.     strncpy(L->str, S.str + pos - 1, len);
    
26.     L->str[len] = '\0';
    
27.     L->length = len;
    
28.     return 1;
    
29. }
    
30. 
    
31. // 简单匹配算法
    
32. int Index(String S, String L) {
    
33.     int i = 0, j = 0;
    
34.     while (i < S.length && j < L.length) {
    
35.         if (S.str[i] == L.str[j]) {
    
36.             i++;
    
37.             j++;
    
38.         } else {
    
39.             i = i - j + 1;
    
40.             j = 0;
    
41.         }
    
42.     }
    
43.     // 如果匹配成功，返回子串的起始位置
    
44.     if (j == L.length) {
    
45.         return i - j + 1;
    
46.     }
    
47.     return 0; // 未找到匹配子串
    
48. }
    
49. 
    
50. // 主函数
    
51. int main() {
    
52.     String* S = init_string();
    
53.     String* L = init_string();
    
54. 
    
55.     char ch[] = "FishC.com";
    
56.     S->str = (char*)malloc(sizeof(char) * (strlen(ch) + 1));
    
57.     strcpy(S->str, ch);
    
58.     S->length = strlen(ch);
    
59. 
    
60.     // 提取子串
    
61.     if (SubString(L, *S, 1, 5)) {
    
62.         printf("子串 L：%s\n", L->str);
    
63.     } else {
    
64.         printf("提取子串失败\n");
    
65.     }
    
66. 
    
67.     // 查看子串位置
    
68.     int position = Index(*S, *L);
    
69.     if (position > 0) {
    
70.         printf("子串L在主串S中的位置是：%d\n", position);
    
71.     } else {
    
72.         printf("未找到子串L\n");
    
73.     }
    
74. 
    
75.     // 释放内存
    
76.     free(S->str);
    
77.     free(S);
    
78.     free(L->str);
    
79.     free(L);
    
80. 
    
81.     return 0;
    
82. }

复制代码

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

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

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

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

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

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