数据结构实验报告，串的练习（C语言）

作者：命运之光
专栏：数据结构

实验四 串的练习
实验环境：Visual C++或Dev C++
实验目的：
1、掌握串的定义；
2、掌握串在顺序存储方式下的求子串，模式匹配等相关操作。
实验内容：
题1：求子串
实验提示：

静态存储的字符串求子串问题的程序实现关键在于如何在主串中查找子串，具体实现是字符数组的基本操作。

1） 从pos位置开始取串S放到新串Sub中
2）手工添加字符串结束标记'\0'
题2： 字符串模式匹配BF算法
实验提示：

通过字符串模式匹配程序理解布鲁特—福斯算法。

从主串S的第pos个字符起和模式的第一个字符相比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，此时匹配成功，定位函数返回和模式T中第一个字符相等的字符在主串S中的序号。否则匹配不成功，定位函数返回零。

实验四 串的练习

一、需求分析

问题一：
静态存储的字符串求子串问题的程序实现在主串中查找子串。
1)从pos位置开始取串s放到新串Sub中；
2)手工添加字符串结束标记”/0”；
问题二：
通过字符串模式匹配程序理解布鲁特-福斯算法。
从主串S的第pos个字符起和模式的第一个字符相比较，若相等，则继续逐个比较后续字符;否则从主串的下一个字符起再重新和模式的字符比较。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等此时匹配成功，定位函数返回和模式T中第一个字符相等的字符在主串S中的序号。否则匹配不成功，定位函数返回零。

二、概要设计

1.用结构体定义一个串

typedef struct {
    char str[Maxsize];
    int length;
}String;

定义字符串大小char str[Maxsize];
定义串的长度int length;

2.主程序

int main() {
    String S;//定义主串 
    String sub;//定义的新串 
    char str[Maxsize];
    printf("请输入一串字符：\n");
    for (int i = 0; i < Maxsize; i++)//输入10个字符 
    {
        scanf("%c", &str[i]);
    }
    StrAssign(S, str);
    printf("子串为：\n");
    SubString(sub, S, 2, 5);// (sub, S, x, y),x,y来定义求出的子串 
    return 0;
}

在主程序中调用自定义函数SubString(String& sub, String S, int pos, int len)来求子串

三、详细设计

问题一：
1.串的定义顺序储存

typedef struct {
    char str[Maxsize];
    int length;
}String;

2.串赋值

int StrAssign(String& S, char str[])
{
    for (int i = 0; str[i] != '\0'; i++)
    {
        S.str[i] = str[i];
        S.length = i + 1;
    }
    return 0;
}

3.求字串

int SubString(String& sub, String S, int pos, int len) {
    if ((pos + len) > S.length)
    {
        return -1;
    }
    for (int i = pos; i < (pos + len); i++)//从pos位置开始放入新sub串中 
    {
        sub.str[i - pos] = S.str[i];
        printf("%c", sub.str[i - pos]);
    }
    return 0;
}

4.主函数

int main() {
    String S;//定义主串 
    String sub;//定义的新串 
    char str[Maxsize];
    printf("请输入一串字符：\n");
    for (int i = 0; i < Maxsize; i++)//输入10个字符 
    {
        scanf("%c", &str[i]);
    }
    StrAssign(S, str);
    printf("子串为：\n");
    SubString(sub, S, 2, 5);// (sub, S, x, y),x,y来定义求出的子串 
    return 0;
}

问题二：
1.串的BF模式匹配，B为主串，A为模式串。

int mate(char* B, char* A) {
    int i = 0, j = 0;
    while (i < strlen(B) && j < strlen(A)) {
        if (B[i] == A[j]) {
            i++;
            j++;
        }
        else {
            //匹配失败时，i 向后移动一位，j 重置
            i = i - j + 1;
            j = 0;
        }
    }
    //跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明模式串遍历完成，在主串中成功匹配
    if (j == strlen(A)) {
        return i - strlen(A) + 1;
    }
    //运行到此，为 i==strlen(B) 的情况，模式匹配失败
    return -1;
}

2.主函数

int main() {
    myString B = "ababcabcacbab";
    myString A = "abcac";
    int res = mate(B, A);
    if (res == -1) {
        printf("模式匹配失败，主串中不含模式串\n");
    }
    else
    {
        printf("匹配成功，主串中定义到模式串的位置为：%d", res);
    }
    return 0;
}

四、调试分析

简单分析：
问题一：
实现字符串中求子串，整的来说步骤简单，首先定义出顺序表用来装串，后对串进行赋值，再进行求子串，实现操作，其中要注意取地址传参的一些问题，因为实验要求并未要求传入指定字符串大小，所以我通过#define MAXSIZE宏定义来实现传入字符串的长度，同理实验未要求查找指定字符串，所以我通过(sub, S, x, y)，通过改变x，y来定义求出的子串。
问题二：
采用BF算法定位模式串在主串中的位置，就是简单粗暴的从主串的起始位置开始，不断地将模式串中的字符和主串中的字符进行对比。实现BF算法，首先要想好如何存储模式串和主串。
调试样例：
问题一：

问题二：

总结经验：
问题一：实验要求简单就简单来，不必多加一些奇奇怪怪的指令。传参时要注意规范，否则输出结果会与预期结果不同。
问题二：BF算法的实现过程很"无脑"，不包含任何技巧。程序中，借助i-strlen(A)+1 就可以得到成功模式匹配的次数，也就是模式串在主串中的位置。

五、测试结果

问题一：
输入主串求子串

问题二：
通过改变myString B = "ababcabcacbab";myString A = "abcac";的值来实现特定值模式匹配

附录：源程序代码（带注释）

问题一：

#include<string.h>
#include<stdio.h>
#define Maxsize 10
typedef struct {
    char str[Maxsize];
    int length;
}String;
//串赋值
int StrAssign(String& S, char str[])
{
    for (int i = 0; str[i] != '\0'; i++)
    {
        S.str[i] = str[i];
        S.length = i + 1;
    }
    return 0;
}
//求子串
int SubString(String& sub, String S, int pos, int len) {
    if ((pos + len) > S.length)
    {
        return -1;
    }
    for (int i = pos; i < (pos + len); i++)//从pos位置开始放入新sub串中 
    {
        sub.str[i - pos] = S.str[i];
        printf("%c", sub.str[i - pos]);
    }
    return 0;
}

int main() {
    String S;//定义主串 
    String sub;//定义的新串 
    char str[Maxsize];
    printf("请输入一串字符：\n");
    for (int i = 0; i < Maxsize; i++)//输入10个字符 
    {
        scanf("%c", &str[i]);
    }
    StrAssign(S, str);
    printf("子串为：\n");
    SubString(sub, S, 2, 5);// (sub, S, x, y),x,y来定义求出的子串 
    return 0;
}

问题二：

#include <stdio.h>
#include <string.h>
#define STR_LEN 100
typedef char myString[STR_LEN];
//串普通模式匹配算法的实现函数，其中 B是主串，A是模式串
int mate(char* B, char* A) {
    int i = 0, j = 0;
    while (i < strlen(B) && j < strlen(A)) {
        if (B[i] == A[j]) {
            i++;
            j++;
        }
        else {
            //匹配失败时，i 向后移动一位，j 重置
            i = i - j + 1;
            j = 0;
        }
    }
    //跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明模式串遍历完成，在主串中成功匹配
    if (j == strlen(A)) {
        return i - strlen(A) + 1;
    }
    //运行到此，为 i==strlen(B) 的情况，模式匹配失败
    return -1;
}
int main() {
    myString B = "ababcabcacbab";
    myString A = "abcac";
    int res = mate(B, A);
    if (res == -1) {
        printf("模式匹配失败，主串中不含模式串\n");
    }
    else
    {
        printf("匹配成功，主串中定义到模式串的位置为：%d", res);
    }
    return 0;
}

适用于：
大一数据结构实验课实验报告——串的练习（C语言版）