AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2023-05-08 177
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构实验报告，串的练习（C语言）

数据结构实验报告，串的练习（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语言版）

在这里插入图片描述

文章标签：
C++
C语言
算法
存储
关键词：
数据结构c语言
数据结构实验
实验C语言
数据结构实验C语言
命运之光
目录
相关文章
ephemerals__
|
21天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
104 9
XIAZHI
|
1月前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践，体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案，包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例，帮助读者掌握C语言的基本语法和常用算法，提升编程能力。
XIAZHI
66 4
ephemerals__
|
20天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
60 16
ephemerals__
|
20天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
71 8
ephemerals__
|
23天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
50 4
ephemerals__
|
24天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
56 3
初恋叫萱萱
|
24天前
|
存储 算法 C语言
C语言数据结构（2）
【10月更文挑战第21天】
初恋叫萱萱
32 2
XIAZHI
|
1月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】
《趣学C语言和数据结构100例》精选5个编程问题，涵盖求最大公约数与最小公倍数、字符统计、特殊序列求和及阶乘计算等，通过实例讲解C语言基础与算法思维，适合初学者实践学习。
XIAZHI
74 1
白子寰
|
1月前
|
C语言
大学生期末C语言实验（学生成绩和鞍点）
大学生期末C语言实验（学生成绩和鞍点）
白子寰
177 0
大学生期末C语言实验（学生成绩和鞍点）
GuGuStudy
|
1月前
|
存储 C语言
探索C语言数据结构：利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录，包括初始化、添加、删除、查找和保存联系人信息的操作，以及自定义结构体用于存储联系人详细信息。
GuGuStudy
21 2