串及其应用

article/2025/8/27 15:21:06

一、实验目的：
（1）掌握串的顺序存储结构及定长字符串的基本操作。
（2）掌握串的BF和KMP模式匹配算法

二、实验原理
串是一种特殊的线性表，其特性体现在数据元素的一个字符，即串是一种内容受限的线性表。
定义：零个或者多个字符组成的有限序列。
子串：串中任意个连续的字符组成的子序列称为该串的字串。
主串：包含字串的串称为该字串的主串。
子串在主串中位置：字符在串中的序号称为该字符在串中的位置。
字符在主串中位置则以子串的第一个字符在主串中的位置表示。
串相等：两个串长度相等，且对应位置的字符也相等。
BF–蛮力算法（必须熟练掌握）

三、实验内容及步骤
1、建立顺序串结构。
2、输入串1和串2，在主函数中实现。输出串。
3、串的模式匹配。
4、串比较。比较串1和串2的大小，相等返回0，S1<S2返回-1，否则返回1.
5、串连接。把串2连接在串1的后面。输出串1。
6、串替换。输入串3，替换串1中包含的串2的所有内容。输出串1。
7、求子串。从串1中的第i个元素开始截取n个元素形成子串。输出子串。

四、实验源代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#define FALSE 0
#define TRUE 1#define MAXSIZE 50     /*初始分配的顺序串长度*/
typedef char ElemType;  /*限定字符串元素值域必须为字符集*/typedef struct string {ElemType ch[MAXSIZE];      /*存储字符串的一维数组*/int length;           /*字符串的实际长度,不包括结束符*/
}SString;SString* Create_SeqStr(char* s)  /* 创建一个串，用字符串s初始化它 */
{int i;SString* pstr = (SString*)malloc(sizeof(SString));	/* 申请串空间 */if (pstr == NULL)printf("Out of space!!\n");else {pstr->length = 0;for (i = 0; *s != '\0'; i++)  //把串s存储到字符串pstr中，并输出字符串{//printf("%c,",*s);  pstr->ch[i] = *s++;//不会存‘\0’pstr->length++;}return pstr;}
}/*遍历顺序串s的所有字符*/
void Traverse_SString(SString* S) {int i;for (i = 0; i<S->length; i++)printf("%c", S->ch[i]);printf("\n");//	return TRUE;
}/*TraverseList*//*1、串插入：在串S的第pos个字符处开始，插入串T*/
int SStrInsert(SString* S, int pos, const SString* T)
{int i;int j;if (NULL == S || NULL == S->ch || NULL == T || pos<0 || pos>S->length)return FALSE;if (T->length+S->length<=MAXSIZE)//判断两个串长相加后是否溢出{for (i = S->length - 1; i >=pos - 1; i--) //先把S串中插入位置后的字符，移动位置S->ch[i+T->length] = S->ch[i];for (i = 0; i < T->length; i++)  //把串T插入到串S的第pos位S->ch[pos-1+i]=T->ch[i];S->length=S->length+T->length; //串S长度更新return  TRUE;}elsereturn FALSE;
}/*2、串删除：从串S中删除从第pos个字符开始连续len个字符后形成的子串*/
int SStrDelete(SString* S, int pos, int len)
{int i;if (NULL == S || NULL == S->ch || len < 0 || pos<0 || pos>S->length - len)return FALSE;else{for(i=pos-1+len; i<S->length; i++) //挪动元素实现从第pos个字符开始删除len个字符S->ch[i-len]=S->ch[i];S->length=S->length-len;//串S长度更新return TRUE;}
}/*3、串连接：将串T的值连接在串S的后面*/
int SStrCat(SString* S, SString* T)
{int i;if (NULL == S || NULL == S->ch || NULL == T->ch)return FALSE;if (S->length+T->length<=MAXSIZE)//判断是否符合连接条件{for (i=0;i<T->length; i++)//把T中字符依次存入S中S->ch[(S->length)+i] = T->ch[i];S->length=S->length+T->length;//串长更新return TRUE;}elsereturn FALSE;
}/*4、求子串：截取串S中从第pos个字符开始连续len个字符形成的子串，并复制给串T*/
int SStrSub(SString* T, SString* S, int pos, int len)
{int i;if (NULL == S || NULL == S->ch || NULL == T || NULL == T->ch || len<0 || len>S->length - pos + 1 || pos<0 || pos>S->length)return FALSE;for (i = 0; i < len; i++)T->ch[i] = S->ch[pos-1 + i];T->length = len;//设置串T长度return TRUE;
}/*5、串比较：比较串S和串T的大小，S等于T返回0，S>T返回1，S<T返回-1*/
int SStrCompare(SString* S, SString* T)
{int i;if (NULL == S || NULL == S->ch || NULL == T || NULL == T->ch)printf("串S或串T不存在，不能比较！\n");else {for (i = 0;i<T->length&&i<S->length; i++) //S和T中对应位置字符依次比较//T，S的length谁大谁小不明确if (S->ch[i] != T->ch[i])  //判断比较是否进行break;if (i==T->length||i==S->length)//串S和串T相等return 0;if (S->ch[i]>T->ch[i])//串S>串Treturn 1;if (S->ch[i] < T->ch[i])//串S<串Treturn -1;}
}
/* 6、串匹配：蛮力（朴素）模式匹配算法：BF算法 */
/*在串S中第pos个字符处开始查找，串T是否存在,若存在，返回查找成功位序，否则返回FASLE*/
int SStrIndex_BF(SString* S, int pos, SString* T) {int i, j;if (NULL == S || NULL == S->ch || NULL == T || NULL == T->ch || pos<0 || pos>S->length)return FALSE;for (i=pos-1; i<S->length; i++)//设置查找区域{for (j = 0; j<T->length; j++)  //从T中取出字符依次与S中字符比较 if (S->ch[i+j]!=T->ch[j])  //判断比较是否继续break;if (j==T->length)//查找成功，退出查找过程break;}if (j!=T->length)//查找失败或i==S->lengthreturn FALSE;elsereturn  i + 1;
}/*7、串替换：在主串S中查找子串T，若找到并把子串T替换为子串V */
int SStrReplace(SString* S, SString* T, SString* V)
{int i, j;if (NULL == S || NULL == S->ch || NULL == T || NULL == T->ch || NULL == &V || NULL == V->ch)return FALSE;else for (i = 0; i < S->length; i++){j= SStrIndex_BF(S, i+1, T);   //j用来存储,在串T中串S的位置if (j!=FALSE)  //判断是否具有替换的条件{SStrDelete(S, j, T->length);  //SStrDelete(SString *S, int pos, int len)，在串S中删除串TSStrInsert(S, j,  V);          //SStrInsert(SString *S, int pos, const SString T)，在串S中第j个位置开始插入串V}return TRUE;}
}int main() {int i, j;char str1[MAXSIZE];//=(char *)malloc(sizeof(char)*MAXSIZE) ;char* str2 = (char*)malloc(sizeof(char) * MAXSIZE);char* str3 = (char*)malloc(sizeof(char) * MAXSIZE);SString* StrS = (SString*)malloc(sizeof(SString));SString* StrT = (SString*)malloc(sizeof(SString));SString* StrV = (SString*)malloc(sizeof(SString));printf("\n   ******************************************************************\n");printf("\n   *********************** 顺 序 串 常 用 算 法 *********************\n");printf("\n   ******************************************************************\n");printf("\n1、串插入：在串S的第pos个字符处插入串T\n");printf("请输入串S:");scanf("%s", str1);StrS = Create_SeqStr(str1);printf("请输入串T:");scanf("%s", str2);StrT = Create_SeqStr(str2);printf("请输入pos值:");scanf("%d", &i);if (SStrInsert(StrS, i, StrT)){printf("插入成功！\n遍历串S:");Traverse_SString(StrS);}elseprintf("插入失败！\n");printf("\n\n2、串删除：从串S中删除从第pos个字符开始连续len个字符后形成的子串\n");printf("请输入串S:");scanf("%s", str1);StrS = Create_SeqStr(str1);printf("请输入pos值:");scanf("%d", &i);printf("请输入len值:");scanf("%d", &j);if (SStrDelete(StrS, i, j)){printf("删除成功！\n遍历串S:");Traverse_SString(StrS);}elseprintf("删除失败！\n");printf("\n\n3、串连接：将串T的值连接在串S的后面\n");printf("请输入串S:");scanf("%s", str1);StrS = Create_SeqStr(str1);printf("请输入串T:");scanf("%s", str2);StrT = Create_SeqStr(str2);if (SStrCat(StrS, StrT)){printf("连接成功！\n遍历串S:");Traverse_SString(StrS);}elseprintf("连接失败！\n");printf("\n\n4、求子串：截取串S中从第pos个字符开始连续len个字符形成的子串，并复制给串T\n");printf("请输入串S:");scanf("%s", str1);StrS = Create_SeqStr(str1);StrT->length = 0;printf("请输入pos值:");scanf("%d", &i);printf("请输入len值:");scanf("%d", &j);if (SStrSub(StrT, StrS, i, j)){printf("求子串成功！\n遍历串T:");Traverse_SString(StrT);}elseprintf("求子串失败！\n");printf("\n\n5、串比较：比较串S和串T的大小，S等于T返回0，S>T返回1，S<T返回-1\n");printf("请输入串S:");scanf("%s", str1);StrS = Create_SeqStr(str1);printf("请输入串T:");scanf("%s", str2);StrT = Create_SeqStr(str2);if (SStrCompare(StrS, StrT) == 0){printf("串S等于串T\n");/*Traverse_SString(StrS);printf("等于");printf("串T：");Traverse_SString(StrT);*/}elseif (SStrCompare(StrS, StrT) == 1){printf("串S大于串T\n");/*Traverse_SString(StrS);printf("");printf("：");Traverse_SString(StrT);*/}else{printf("串S小于串T\n");/*Traverse_SString(StrS);printf("小于");printf("串T：");Traverse_SString(StrT);*/}printf("\n\n6、串匹配：蛮力(BF)模式匹配算法:\n");printf("在串S中第pos个字符处开始查找，串T是否存在,若存在，返回查找成功位序，否则返回FALSE\n");printf("请输入串S:");scanf("%s", str1);StrS = Create_SeqStr(str1);printf("请输入串T:");scanf("%s", str2);StrT = Create_SeqStr(str2);printf("请输入pos值:");scanf("%d", &i);if (SStrIndex_BF(StrS, i, StrT)){printf("匹配成功！\n返回串T在串S中位序:");printf("   %d\n", SStrIndex_BF(StrS, i, StrT));}elseprintf("匹配失败！\n");printf("\n\n7、串替换：在主串S中查找子串T，若找到并把子串T替换为子串V\n");printf("请输入串S:");scanf("%s", str1);StrS = Create_SeqStr(str1);printf("请输入串T:");scanf("%s", str2);StrT = Create_SeqStr(str2);printf("请输入串V:");scanf("%s", str3);StrV = Create_SeqStr(str3);if (SStrReplace(StrS, StrT, StrV)){printf("替换成功！\n遍历串S:");Traverse_SString(StrS);}elseprintf("插入失败！\n");}

五、实验结果
在这里插入图片描述

六、实验总结
1.串的结构体
typedef struct string {
ElemType ch[MAXSIZE];
int length;
}SString;
2.字符串的实际长度,不包括结束符，即串中不储存‘\0’，数组中每一个元素都为char型
3.这里的ElemType为char型
4.pos作为接口，指代第几个字符，返回的也是第几个字符（i+1），注意返回和使用的区别
5.串插入
for (i = S->length - 1; i >=pos - 1; i–) //先把S串中插入位置后的字符，移动T->length
S->ch[i+T->length] = S->ch[i];
for (i = 0; i < T->length; i++) //把串T插入到串S的第pos位
S->ch[pos-1+i]=T->ch[i];

6.串删除
for(i=pos-1+len; ilength; i++) //挪动元素实现从第pos个字符开始删除len个字符
T->ch[i-len]=S->ch[i];
7.插入删除等操作不能忘记更新length的值
8.串比较中T，S的length谁大谁小不明确，故两者的length均要考虑


http://chatgpt.dhexx.cn/article/ro5chW9n.shtml

相关文章

数据结构——串

数据结构——串

目录 1.串的定义与基本操作 1.1定义 1.2基本操作 2.串的存储结构 2.1顺序存储 2.2链式存储 3.字符串的模式匹配算法&#xff08;“查找”章节&#xff09; 3.1朴素模式匹配算法 3.2KMP算法 3.2.1算法思想 3.2.2算法代码实现 3.2.3求next数组和nextval数组&#xff…
阅读更多...
数据结构之串

数据结构之串

1、串的概念 字符串简称串&#xff0c;是一种特殊的线性表&#xff0c;它的数据元素仅由一个字符组成。 2、串的定义 串(String)是由零个或多个字符组成的有限序列&#xff0c;又称字符串。 其中s是串名,用双引号括起来的字符序列为串值&#xff0c;但引号本身并不属于串的内容…
阅读更多...
串的详细讲解

串的详细讲解

1 串的基本概念 1.1 串的定义 串&#xff1a;( string)(或字符串)是由零个或多个字符组成的有限序列&#xff0c;一般记为s...&#xff0c;其中&#xff0c;s是串的名&#xff0c;用单引号括起来的字符序列是串的值&#xff1b;(1<i≤n)可以是字母、数字或其他字符&#xff…
阅读更多...
串（数据结构）

串（数据结构）

一、 串类型的定义 串的定义 串&#xff08;string&#xff09;&#xff08;或字符串&#xff09;是由零个或多个字符组成的有序序列&#xff0c;一般记为 S”a1a2…an” (n>0) 其中&#xff0c;s是串的名&#xff0c;用双引号括起来的字符序列是串的值&#xff1b;ai (…
阅读更多...
数据结构：串(String)【详解】

数据结构：串(String)【详解】

友情链接&#xff1a;数据结构专栏 目录 串【知识框架】一、串的定义二、串的存储结构1、定长顺序存储表示2、堆分配存储表示3、块链存储表示 三、串的基本操作四、串的模式匹配&#xff08;重点&#xff09;1、简单的模式匹配算法2、KMP算法&#xff08;1&#xff09;字符串的…
阅读更多...
idm下载器是免费的吗?有哪些功能

idm下载器是免费的吗?有哪些功能

对于PC用户来说&#xff0c;拥有一款好用和快速的下载工具&#xff0c;对我们来说至关重要&#xff0c;可以极大提高我们的工作效率和PC用户体验。IDM可以实现高速下载&#xff0c;其核心原理就是多线程下载&#xff0c;理论上可以达到带宽的峰值速度&#xff0c;深受用户的喜爱…
阅读更多...
IDM下载器|Windows系统经典下载工具idm6.41|IDM如何在线视频下载工具 |下载视频教程

IDM下载器|Windows系统经典下载工具idm6.41|IDM如何在线视频下载工具 |下载视频教程

IDM全称Internet Download Manager,是一种将下载速度提高最多5倍的专业下载工具,支持大部分文件格式下载和基本所有的下载链接,无视网址本身下载限速,直接达到电脑该有的网速。 下载更快更可靠 下载INTERNET DOWNLOAD MANAGER(IDM下载器)开始您的极速下载旅程&#xff0c;永远…
阅读更多...
【IDM】IDM下载器安装

【IDM】IDM下载器安装

下载链接 IDM_v6.41.2_Reрack.exe提取码: gj46 可能遇到的问题 1. 某些应用程序阻止了IDM集成到浏览器中 解决方法&#xff1a; 1.打开“Windows Update” 2.winr运行cmd 3.输入“services.msc” 4.找到“Windows Update”运行 5.关闭IDM&#xff0c;用管理员身份运行。…
阅读更多...
【百度网盘下载】用工具IDM下载器

【百度网盘下载】用工具IDM下载器

个人的一些学习资料和共享资料都是在百度网盘上&#xff0c;但是最近百度网盘的下载速度实在是太慢了。目前找到的比较好的方法是用IDM下载器。 微信公众号&#xff1a;北鼻不抠鼻 它详细介绍了这个软件的下载方式&#xff0c;还有相关配置。 重点是 绿色 嘿嘿 下载完在浏览器…
阅读更多...
怎么在火狐浏览器中添加IDM下载器扩展？

怎么在火狐浏览器中添加IDM下载器扩展？

Internet Download Manager&#xff08;简称“IDM”&#xff09;是一种将下载速度提高5倍&#xff0c;可以恢复和安排下载任务的工具。当在下载的过程中遇到连接丢失、网络问题、计算机关机或意外停电等问题&#xff0c;IDM可以全面恢复和重启中断的下载。 Internet Download M…
阅读更多...
internet download manager(IDM下载器) 6.40

internet download manager(IDM下载器) 6.40

软件下载 internet download manager(IDM下载器)是一款很不错的下载工具。有了internet download manager软件&#xff0c;可以提高你下载文件的速度&#xff0c;如果您在下载文件的时候&#xff0c;突然没网了&#xff0c;您可以使用IMD下载器的续传功能非常的方便&#xff0…
阅读更多...
idm下载器是什么软件?最新V6.41版本号Win下载工具

idm下载器是什么软件?最新V6.41版本号Win下载工具

Internet Download Manager &#xff08;IDM&#xff09;是一种将下载速度提高多达 5 倍&#xff0c;恢复和安排下载的软件。全面的错误恢复和恢复功能将由于连接丢失&#xff0c;网络问题&#xff0c;计算机关闭或意外断电而重新启动中断的下载或中断下载。IDM下载器是一款先进…
阅读更多...
IDM下载器插件 让浏览器不在限速

IDM下载器插件 让浏览器不在限速

IDM下载器 可提速&#xff08;2到n倍&#xff09;的使用方法&#xff0c;让浏览器不在限速 前言 IDM 最佳的 Windows 下载工具 官方网址: http://www.internetdownloadmanager.com/. 尽管现在要用到「下载工具」的时间相比过去有所减少&#xff0c;但电脑上总要备一款以防不…
阅读更多...
IDM下载器免费高质量的Win下载工具无使用限制

IDM下载器免费高质量的Win下载工具无使用限制

这是Windows 平台上的一款下载软件&#xff0c;它支持不同类型的浏览器&#xff0c;几乎能下载网页中所有的数据&#xff0c;还不会弹出广告。internetdownloadmanager(IDM下载器)是一款很不错的下载工具&#xff0c;很多人使用&#xff0c;这个软件好处就是免费 网上可以搜索到…
阅读更多...
idm下载器怎么下载网页视频？如何用idm自动下载网站文件？

idm下载器怎么下载网页视频？如何用idm自动下载网站文件？

随着互联网的快速发展&#xff0c;越来越多的资源都可以免费下载&#xff0c;而idm下载器凭借其独特的“多线程资源嗅探”&#xff0c;能轻松下载各种网页视频&#xff0c;因此idm也一直被称为下载神器&#xff0c;那idm下载器怎么下载网页视频&#xff0c;或者自动下载网站文件…
阅读更多...
chrome中下载文档时设置成不使用idm下载器的方法

chrome中下载文档时设置成不使用idm下载器的方法

wyn enterprise中用到导出功能时&#xff0c;自动调用idm但往往下载报错。 如何关闭idm自动弹出并下载功能呢&#xff1f; 1、设置。 2、选项。
阅读更多...
电脑版idm下载器好不好用?

电脑版idm下载器好不好用?

IDM&#xff08;Internet Download Manager&#xff09;是Windows上一款非常好用的下载管理器。在功能方面&#xff0c;它是主流下载器中的佼佼者&#xff0c; 更获得多种奖项&#xff0c; 是。下面&#xff0c;我列出了自己在使用Internet Download Manager的一些实用技巧和窍…
阅读更多...
idm下载器简介

idm下载器简介

Internet Download Manager是Windows、Mac用户比较喜欢的一款老牌下载器&#xff0c;它提供了许多贴心功能&#xff0c;用过的朋友应该深有体会。如果你没有用过IDM下载器&#xff0c;可以看看文章整理相关功能介绍&#xff0c;别错过哟。 1.自动捕获链接 在浏览器中下载文件时…
阅读更多...
IDM下载器下载百度网盘文件

IDM下载器下载百度网盘文件

郑重声明&#xff1a;本文章只作为个人学习研究中解决百度网盘下载速度慢的解决方法&#xff0c;不作为任何商业用途&#xff0c;所有工具均合法来自于互联网&#xff0c;本人支持正版&#xff0c;拒绝盗版。请读者严格遵守相关规定&#xff0c;本人不对他人通过本文章知识了解…
阅读更多...
【下载器篇】IDM下载器个性化设置

【下载器篇】IDM下载器个性化设置

【下载器篇】IDM下载器个性化设置 IDM个性化设置—【蘇小沐】 文章目录 【下载器篇】IDM下载器个性化设置1.实验环境 &#xff08;一&#xff09;下载类型扩展UA默认值 &#xff08;二&#xff09;工具栏样式&#xff08;改风格&#xff09;3D Style样式 &#xff08;三&#…
阅读更多...
推荐文章

Copyright @ 2022~2023