数据结构C语言描述7(图文结合)--串的实现与BP算法、KMP算法讲解与模版提供

ops/2024/12/23 3:46:03/

前言

  • 这个专栏将会用纯C实现常用的数据结构和简单的算法；
  • 有C基础即可跟着学习，代码均可运行；
  • 准备考研的也可跟着写，个人感觉，如果时间充裕，手写一遍比看书、刷题管用很多，这也是本人采用纯C语言实现的原因之一；
  • 欢迎收藏 + 关注，本人将会持续更新。

文章目录

    • 串的定义
    • 串相关概念
    • 串常见操作
    • 串代码的实现
      • 创建串
      • 万金油函数
      • 插入
      • 删除
    • BF算法与模版
    • KMP算法与模版
        • 部分匹配表
    • 总代码

串的定义

串:是一种特殊的线性表，它是由字符组成的，是由零个或多个字符组成的有限序列。一般记为:

S = “a1a2a3……an” (n≥0)
如：A= “BEIJING”， B= “JING”

串相关概念

  • 空串(null string)：长度为零的串，它不包含任何字符。
  • 空格串(black string):任由一个或多个空格组成的串，长度大于等于1
  • 子串(sub string):串中任意个连续字符的组成的子序列称为该串的“子串”
  • 主串(master string):包含子串的串相应的称为“主串”，因此子串是主串的一部分
  • 串长度:当前字符串的元素个数，不包含字符串结束标记\0
  • 前缀:除了最后一个字符以外，一个字符串的全部头部组合
  • 后缀:除了第一个字符以外，一个字符串的全部尾部组合

串常见操作

串的操作不局限于插入、删除元素，而是各种查找，替换的操作，串的数据对象限制为字符，并且一般以串作为整体进行操作，主要有以下操作:

  • 创建串
  • 插入子串
  • 查找子串
    • BF匹配
    • KMP匹配
  • 删除串
    • 区间删除
    • 删除子串
  • 求串长度
  • 串连接
  • 串比较
  • 串拷贝

串代码的实现

创建串

typedef struct String {char* data;int size;
}String;String* create_string(const char* str) 
{if (str == NULL) {return NULL;}int len = strlen(str);String* string = (String*)calloc(1, sizeof(String));assert(string);string->data = (char*)calloc(1, sizeof(char) * len);assert(string->data);for (int i = 0; i < len; i++) {string->data[i] = str[i];}string->size += len;return string;
}

万金油函数

// 万金油函数
bool empty(String* str)
{assert(str);return str->size == 0;
}
int size(String* str)
{assert(str);return str->size;
}

插入

插入方式有很多，我这里实现在pos位置后插入，实现思路也很多，我这里的思路是：

  • 重新申请一块大内存，可以存放插入的字符串；
  • 先讲在插入位置后的字符串，全部移到最后面；
  • 后一个一个进行插入。
// 向后插入, pos 从0开始
void insert(String* str, int pos, const char* data)
{assert(str);assert(str->data);// 获得插入数据大小int len = strlen(data);// 扩容char* new_data = (char*)realloc(str->data, sizeof(char) * str->size + len);assert(new_data);str->data = new_data;   // 保证realloc申请内存失败而导致原来数据为空// 规则：如果pos大于字符串长度，或者无效，则插入末尾if (pos >= str->size || pos < 0) {for (int i = 0; i < len; i++) {str->data[str->size++] = data[i];}}else {// 先腾位置int st = pos + len + 1;int i = pos + 1;for(; st < str->size + len; st++) {str->data[st] = str->data[i++];}for (int i = 0; i < len; i++) {str->data[pos + 1 + i] = data[i];}}str->size += len;
}

删除

我这里也是实现一个简单粗暴的方法，从新省钱内存，将满足条件的字符串一个一个插入：

// 简单方法：重新申请内存, 左闭右开
void erase(String* str, int begin, int end)
{assert(str);int dSzie = end - begin;int count = str->size - dSzie;char* temp = (char*)calloc(count, sizeof(char));assert(temp);int index = 0;for (int i = 0; i < str->size; i++) {if (i >= begin && i < end) {continue;}else {temp[index++] = str->data[i];}}free(str->data);str->data = temp;str->size = count;
}

BF算法与模版

BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果，时间复杂度O(n^2)

在这里插入图片描述

实现：

int bf_string(String* str1, String* str2)
{assert(str1);assert(str2);int i = 0, j = 0;while (i < str1->size && j < str2->size) {int t = i;if (str1->data[i] == str2->data[j]) {i++;j++;}else {i = t + 1;j = 0;}if (j == str2->size) {return i - j;}}return -1;
}

KMP算法与模版

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。

KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

参考资料：[代码随想录KMP](代码随想录 (programmercarl.com))

部分匹配表

KMP算法确实很绕啊，我感觉一定要结合图像进行学习，才能掌握，这里推荐：

  • [代码随想录KMP](代码随想录 (programmercarl.com))
  • B站，懒猫老师KMP讲解

我这里讲一下前缀和后缀匹配，方便理解:

  • 字符串ABCDABD，其实KMP的next数组就是代表第i个字符有多少前缀和最开始字符串相匹配(当然也有前移1位和后移1位，但是本质一样，就是前后缀匹配)。

在这里插入图片描述

求解过程：

子串前缀后缀部分匹配值
A空集空集0
ABAB0
ABCA,ABC,BC0
ABCDA,AB,ABCD,CD,BCD0
ABCDAA,AB,ABC,ABCDA,DA,CDA,BCDA1
ABCDABA,AB,ABC,ABCD,ABCDAB,AB,DAB,CDAB,BCDAB2
ABCDABDA，AB，ABC,ABCD,ABCDA,ABCDABD,BD,ABD,DABD,CDABD,BCDABD0

代码模版：

void getNext(int next[], String* str)
{assert(str);int j = -1;next[0] = j;for (int i = 1; i < str->size; i++) {while (j >= 0 && str->data[i] != str->data[j + 1]) {j = next[j];}if (str->data[i] == str->data[j + 1]) {j++;}next[i] = j;}
}int kmp_string(String* str1, String* str2)
{assert(str1);assert(str2);int* next = (int*)calloc(str2->size, sizeof(int));assert(next);getNext(next, str2);int j = -1, i = 0;for (; i < str1->size; i++) {if (str1->data[i] == str2->data[j + 1]) {j++;}else if (j >= 0) {j = next[j];}if (j == str2->size - 1) {free(next);return i - j;}}free(next);return -1;
}

总代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>typedef struct String {char* data;int size;
}String;String* create_string(const char* str) 
{if (str == NULL) {return NULL;}int len = strlen(str);String* string = (String*)calloc(1, sizeof(String));assert(string);string->data = (char*)calloc(1, sizeof(char) * len);assert(string->data);for (int i = 0; i < len; i++) {string->data[i] = str[i];}string->size += len;return string;
}// 万金油函数
bool empty(String* str)
{assert(str);return str->size == 0;
}
int size(String* str)
{assert(str);return str->size;
}// 向后插入, pos 从0开始
void insert(String* str, int pos, const char* data)
{assert(str);assert(str->data);// 获得插入数据大小int len = strlen(data);// 扩容char* new_data = (char*)realloc(str->data, sizeof(char) * str->size + len);assert(new_data);str->data = new_data;   // 保证realloc申请内存失败而导致原来数据为空// 规则：如果pos大于字符串长度，或者无效，则插入末尾if (pos >= str->size || pos < 0) {for (int i = 0; i < len; i++) {str->data[str->size++] = data[i];}}else {// 先腾位置int st = pos + len + 1;int i = pos + 1;for(; st < str->size + len; st++) {str->data[st] = str->data[i++];}for (int i = 0; i < len; i++) {str->data[pos + 1 + i] = data[i];}}str->size += len;
}void print_string(String* str)
{assert(str);for (int i = 0; i < str->size; i++) {printf("%c", str->data[i]);}printf("\n");
}// 简单方法：重新申请内存, 左闭右开
void erase(String* str, int begin, int end)
{assert(str);int dSzie = end - begin;int count = str->size - dSzie;char* temp = (char*)calloc(count, sizeof(char));assert(temp);int index = 0;for (int i = 0; i < str->size; i++) {if (i >= begin && i < end) {continue;}else {temp[index++] = str->data[i];}}free(str->data);str->data = temp;str->size = count;
}int bf_string(String* str1, String* str2)
{assert(str1);assert(str2);int i = 0, j = 0;while (i < str1->size && j < str2->size) {int t = i;if (str1->data[i] == str2->data[j]) {i++;j++;}else {i = t + 1;j = 0;}if (j == str2->size) {return i - j;}}return -1;
}
void erase_bf_string(String* str1, String* str2) 
{assert(str1);assert(str2);int begin = bf_string(str1, str2);assert(begin != -1);int end = begin + str2->size;erase(str1, begin, end);
}void getNext(int next[], String* str)
{assert(str);int j = -1;next[0] = j;for (int i = 1; i < str->size; i++) {while (j >= 0 && str->data[i] != str->data[j + 1]) {j = next[j];}if (str->data[i] == str->data[j + 1]) {j++;}next[i] = j;}
}int kmp_string(String* str1, String* str2)
{assert(str1);assert(str2);int* next = (int*)calloc(str2->size, sizeof(int));assert(next);getNext(next, str2);int j = -1, i = 0;for (; i < str1->size; i++) {if (str1->data[i] == str2->data[j + 1]) {j++;}else if (j >= 0) {j = next[j];}if (j == str2->size - 1) {free(next);return i - j;}}free(next);return -1;
}int main()
{String* string = create_string("IamYXZ!!");print_string(string);insert(string, 5, "loveLt");print_string(string);erase(string, 3, 8);print_string(string);String* str2 = create_string("am");printf("%d\n", bf_string(string, str2));erase_bf_string(string, str2);print_string(string);String* str3 = create_string("abcffabcdabcdehf");String* str4 = create_string("abcdabc");printf("%d\n", kmp_string(str3, str4));return 0;
}

KMP，next数组，左移动一位

  • 对比的时候以 j + 1与 i 对比
  • 除了-1外，下标 j 的值表示的是前 j 的个相同前缀最大数量

http://www.ppmy.cn/ops/144210.html

相关文章

ECharts柱状图-柱图35，附视频讲解与代码下载

ECharts柱状图-柱图35，附视频讲解与代码下载

引言&#xff1a; 在数据可视化的世界里&#xff0c;ECharts凭借其丰富的图表类型和强大的配置能力&#xff0c;成为了众多开发者的首选。今天&#xff0c;我将带大家一起实现一个柱状图图表&#xff0c;通过该图表我们可以直观地展示和分析数据。此外&#xff0c;我还将提供…
阅读更多...
亚矩阵云手机：跨境直播的超强助力

亚矩阵云手机：跨境直播的超强助力

在跨境直播的蓬勃浪潮中&#xff0c;网络卡顿、延迟以及诸多技术难题犹如重重迷雾&#xff0c;困扰着众多从业者&#xff0c;阻碍着业务的拓展与流量的获取。而亚矩阵云手机的出现&#xff0c;恰似一盏明灯&#xff0c;为跨境直播照亮了前行的道路&#xff0c;凭借其卓越的特性…
阅读更多...
.net core在linux导出excel,System.Drawing.Common is not supported on this platform

.net core在linux导出excel,System.Drawing.Common is not supported on this platform

使用框架 .NET7 导出组件 Aspose.Cells for .NET 5.3.1 asp.net core mvc 如果使用Aspose.Cells导出excel时&#xff0c;报错 &#xff1a; System.Drawing.Common is not supported on this platform 平台特定实现&#xff1a; 对于Windows平台&#xff0c;System.Drawing.C…
阅读更多...
mac uniapp 转为微信小程序开发

mac uniapp 转为微信小程序开发

mac uniapp 转为微信小程序开发 1.进入微信公众平台获取小程序Appid在manifest.json配置 2.打开微信开发者工具进入设置—安全设置 3.勾选服务端口 4.点击运行至微信开发工具可自动打开
阅读更多...
第十六周做题总结_数据结构_AVL与哈希查找

第十六周做题总结_数据结构_AVL与哈希查找

id:157 A. DS二叉平衡树构建 题目描述 在初始为空的平衡二叉树中依次插入n个结点，请输出最终的平衡二叉树。 要求实现平衡二叉树，不可以使用各类库函数。 AVL代码参考模板： #include <iostream> using namespace std;#define LH 1 // 左高 #define EH 0 // 等高 …
阅读更多...
go 聊天系统项目-5 客户端发消息

go 聊天系统项目-5 客户端发消息

一、前言 敬告:本文不讲解代码&#xff0c;只是把代码展示出来。 该代码之前的代码见 go 聊天系统项目-1 go聊天系统项目-2 redis 验证用户id和密码 go聊天系统项目-3 redis注册用户 go聊天项目4-显示用户列表 注意&#xff1a;本文使用 go mod 管理代码。详情见 go 包相关知识…
阅读更多...
linux中docker命令大全

linux中docker命令大全

基本命令 docker pull 拉取镜像 docker pull docker push 推送镜像到DockerRegistry docker push docker images 查看本地镜像 docker images docker rmi 删除本地镜像 docker rmi docker run 创建并运行容器&#xff08;不能重复创建&#xff09; docker run d…
阅读更多...
一个开源的自托管虚拟浏览器项目，支持在安全、私密的环境中使用浏览器

一个开源的自托管虚拟浏览器项目，支持在安全、私密的环境中使用浏览器

大家好&#xff0c;今天给大家分享一个开源的自托管虚拟浏览器项目Neko&#xff0c;旨在利用 WebRTC 技术在 Docker 容器中运行虚拟浏览器&#xff0c;为用户提供安全、私密且多功能的浏览体验。 项目介绍 Neko利用 WebRTC 技术在 Docker 容器中运行虚拟浏览器&#xff0c;提供…
阅读更多...
最新文章

Copyright @ 2022~2023