1. Toy模板网首页
  2. > Toy博客

【数据结构】串的基本操作及应用

10月前 作者：Jesonary 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】串的基本操作及应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

分别定义两个结构体——串的定长顺序存储、串的堆式顺序存储

typedef struct
{
	char ch[MAXSTRLEN+1];
	int length;
}SString;
typedef struct
{
	char *ch;
	int length;
}HString;

 

问题：

1、编写函数，串用定长顺序存储表示来实现串的基本操作；

2、 编写串的匹配算法，实现查找功能。

算法思想阐述：

BF算法：首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则S向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。

该算法最坏情况下要进行M*(N-M+1)次比较， 时间复杂度为O(M*N)。

 

一、各函数代码如下  

  解题一：

//生成串 
Status StrAssign(SString &S,char chars[])
{
	int i;	
	S[0]=strlen(chars);
	for(i=0;chars[i]!='\0'&&i+1<MAXSTRLEN;i++){
		S[i+1]=chars[i]; 
	}
	S[i+1]='\0';
	return OK; 
}
//输出串
void PrintStr(SString S)
{
	int i;
	for(i=1;i<S[0]+1;i++){
		cout<<S[i];
	}
	cout<<endl;
}
//求串长
Status StrLength(SString S)
{
 	return S[0];
}
//判空
Status StrEmpty(SString S)
{
	if(S[0]==0){
		return OK;
	}
	else{
		return FALSE;
	}
}
//比较字符串
Status StrCompare(SString S,SString T)
{
 	int i=0;
 	for(i=0;i<S[0]&&i<T[0];i++){
 		if(S[i]!=T[i])
 		    return S[i]-T[i];
	 }
	return S[0]-T[0];
}
//字符串连接:用T返回由S1和S2连接成的新串 
Status Concat(SString &T,SString S1,SString S2)
{
 	int i,j;
 	if(S1[0]+S2[0]<=MAXSTRLEN){
 		//未超出用户定义的最大串长
		 for(i=1;S1[i]!='\0';i++){
		 	T[i]=S1[i];
		 } 
		 for(j=1;S2[j]!='\0';j++){
		 	T[S1[0]+j]=S2[j];
		 }
		 //两次循环连接两串
		 T[S1[0]+j+1]='\0';
		 T[0]=S1[0]+S2[0]; 	 
	 }
	 else if(S1[0]<MAXSTRLEN){
	 	//超出用户定义的最大串长,这里会出现截断情况 
	 	for(i=1;S1[i]!='\0';i++){
		 	T[i]=S1[i];
		 } 
		for(j=1;j<=MAXSTRLEN-S1[0];i++){
			T[S1[0]+j]=S2[j];
			
		}
		  T[0]=MAXSTRLEN;
	 }
	 else{
	 	//条件是S1[0]>MAXSTRLEN,这里仅截断S1
		 for(i=1;S1[i]!='\0';i++){
		 	T[i]=S1[i];
		 }
		 T[i+1]='\0';
		 T[0]=S1[0]; 
	 }
	 return OK;	
}
//取子串:用Sub返回串S的第pos个字符起长度为len的子串 
//注意：1<=pos<=StrLength(S),0<=len<=StrLength(S)-pos+1 
Status SubString(SString &Sub,SString S,int pos,int len)
{
 	int i,j;
 	if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1){
 		return ERROR;
	 }
	for(i=1,j=pos;i<=len&&j<=pos+len-1;i++,j++){
		Sub[i]=S[j];
	}
	Sub[i+1]='\0';
	Sub[0]=len;
	return OK;
}
//串的模式匹配：返回子串T(非空)在主串中第pos个字符之后的位置。若不存在，则返回0 
Status Index(SString S,SString T,int pos)
{
	int i=pos;
	int j=1;
	while(i<=S[0]&&j<=T[0]){
		if(S[i]==T[j]){
			++i;
			++j;
		}else{
			i=i-j+2;
			j=1;
		}
	}
	if(j>T[0]){
		return i-T[0];
	} 
	else return FALSE;
}
//串插入
Status StrInsert(SString& S, int pos, SString T)
{
	int i;
	if (StrEmpty(T))
	return ERROR;
	if (pos<1||pos>S[0]+1)
		return ERROR;
	else
	{
		for (i=S[0]-1;i>=pos-1;i--)
			S[i+T[0]]=S[i];

		for (i=0;i<T[0];i++)
			S[pos+i-1]=T[i];

		S[0] += T[0];
	}
	return OK;
}
//删除：删除串S指定的位置开始的长度为len的子串
Status StrDelete(SString &S,int pos,int len)
{
	int i;
	if(pos<1||len>S[0]-pos+1){
		return ERROR;
	}
	for(i=pos+len;i<=S[0];i++){
		S[i-len]=S[i];
	}
	S[0]-=len;
	return OK;
}
//串替换
Status Replace(SString	&S, SString T, SString V)//最终以S返回 
{
	int i;
	if (StrEmpty(T))
		return ERROR;
	i = Index(S, T, 1);
	while (i != 0)
	{
		StrDelete(S, i, StrLength(T));
		StrInsert(S, i, V);
		i += StrLength(V);
		i = Index(S, T, i);
	}
	return OK;
}
//清空串
Status ClearString(SString &S)
{
	int i;
	for(i=1;S[i]!='\0';i++){
		S[i]='\0';
	}
	S[0]=0;
	return OK;
}

解题一完整代码： 

#include <iostream.h>
#include <string.h>
#define OK 1
#define ERROR 1
#define FALSE 0
#define MAXSTRLEN 255
typedef int Status;
typedef unsigned char SString[MAXSTRLEN+1];//0号单元存放串的长度 
using namespace std;
/*********以下是各类函数的实现*********/ 
//初始化:0号单元存放串的长度 
Status InitStr(SString &S)
{
	S[0]=0; 
	return OK;
} 
//生成串 
Status StrAssign(SString &S,char chars[])
{
	int i;	
	S[0]=strlen(chars);
	for(i=0;chars[i]!='\0'&&i+1<MAXSTRLEN;i++){
		S[i+1]=chars[i]; 
	}
	S[i+1]='\0';
	return OK; 
 } 
//输出串
void PrintStr(SString S)
{
	int i;
	for(i=1;i<S[0]+1;i++){
		cout<<S[i];
	}
	cout<<endl;
 } 
 //求串长
Status StrLength(SString S)
{
 	return S[0];
} 
//判空
Status StrEmpty(SString S)
{
	if(S[0]==0){
		return OK;
	}
	else{
		return FALSE;
	}
} 
 //比较字符串
Status StrCompare(SString S,SString T)
{
 	int i=0;
 	for(i=0;i<S[0]&&i<T[0];i++){
 		if(S[i]!=T[i])
 		    return S[i]-T[i];
	 }
	return S[0]-T[0];
} 
 //字符串连接:用T返回由S1和S2连接成的新串 
Status Concat(SString &T,SString S1,SString S2)
{
 	int i,j;
 	if(S1[0]+S2[0]<=MAXSTRLEN){
 		//未超出用户定义的最大串长
		 for(i=1;S1[i]!='\0';i++){
		 	T[i]=S1[i];
		 } 
		 for(j=1;S2[j]!='\0';j++){
		 	T[S1[0]+j]=S2[j];
		 }
		 //两次循环连接两串
		 T[S1[0]+j+1]='\0';
		 T[0]=S1[0]+S2[0]; 	 
	 }
	 else if(S1[0]<MAXSTRLEN){
	 	//超出用户定义的最大串长,这里会出现截断情况 
	 	for(i=1;S1[i]!='\0';i++){
		 	T[i]=S1[i];
		 } 
		for(j=1;j<=MAXSTRLEN-S1[0];i++){
			T[S1[0]+j]=S2[j];
			
		}
		  T[0]=MAXSTRLEN;
	 }
	 else{
	 	//条件是S1[0]>MAXSTRLEN,这里仅截断S1
		 for(i=1;S1[i]!='\0';i++){
		 	T[i]=S1[i];
		 }
		 T[i+1]='\0';
		 T[0]=S1[0]; 
	 }
	 return OK;	
} 
 //取子串:用Sub返回串S的第pos个字符起长度为len的子串 
 //注意：1<=pos<=StrLength(S),0<=len<=StrLength(S)-pos+1 
Status SubString(SString &Sub,SString S,int pos,int len)
{
 	int i,j;
 	if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1){
 		return ERROR;
	 }
	for(i=1,j=pos;i<=len&&j<=pos+len-1;i++,j++){
		Sub[i]=S[j];
	}
	Sub[i+1]='\0';
	Sub[0]=len;
	return OK;
} 
//串的模式匹配：返回子串T(非空)在主串中第pos个字符之后的位置。若不存在，则返回0 
Status Index(SString S,SString T,int pos)
{
	int i=pos;
	int j=1;
	while(i<=S[0]&&j<=T[0]){
		if(S[i]==T[j]){
			++i;
			++j;
		}else{
			i=i-j+2;
			j=1;
		}
	}
	if(j>T[0]){
		return i-T[0];
	} 
	else return FALSE;
 }

//串插入
Status StrInsert(SString& S, int pos, SString T)
{
	int i;
	if (StrEmpty(T))
	return ERROR;
	if (pos<1||pos>S[0]+1)
		return ERROR;
	else
	{
		for (i=S[0]-1;i>=pos-1;i--)
			S[i+T[0]]=S[i];

		for (i=0;i<T[0];i++)
			S[pos+i-1]=T[i];

		S[0] += T[0];
	}
	return OK;
}

//删除：删除串S指定的位置开始的长度为len的子串
Status StrDelete(SString &S,int pos,int len)
{
	int i;
	if(pos<1||len>S[0]-pos+1){
		return ERROR;
	}
	for(i=pos+len;i<=S[0];i++){
		S[i-len]=S[i];
	}
	S[0]-=len;
	return OK;
}

//串替换
Status Replace(SString	&S, SString T, SString V)//最终以S返回 
{
	int i;
	if (StrEmpty(T))
		return ERROR;
	i = Index(S, T, 1);
	while (i != 0)
	{
		StrDelete(S, i, StrLength(T));
		StrInsert(S, i, V);
		i += StrLength(V);
		i = Index(S, T, i);
	}
	return OK;
}

//清空串
Status ClearString(SString &S)
{
	int i;
	for(i=1;S[i]!='\0';i++){
		S[i]='\0';
	}
	S[0]=0;
	return OK;
 } 
//主函数 
int main(int argc, char *argv[])
{
	SString S1,S2,T,Sub,Rep; 
 	int len1,len2,cha,pos,len;
 	InitStr(T);
 	InitStr(Sub);
 	InitStr(Rep);
 	char s1[100];
 	char s2[100];
 	//避免s1.length+s2.length>MAXSTRLEN
 	cout<<"请输入字符串1:"<<endl;
    scanf("%s",s1);
 	StrAssign(S1,s1);
    //PrintStr(S1);
	cout<<"请输入字符串2:"<<endl;
    scanf("%s",s2);
	StrAssign(S2,s2);
	cout<<"1.字符串长度  ";
	cout<<"2.比较字符串  ";
	cout<<"3.取子串  ";
	cout<<"4.匹配模式  " ;
	cout<<"5.连接字符串  ";
	cout<<endl<<"6.字符串的插入  ";
	cout<<"7.字符串的替换  ";
	cout<<"8.删除子字符串  ";
	cout<<"9.清空字符串  "; 
	cout<<"10.退出程序"<<endl;
	int select;
	while(true){
		cout<<"请选择你想要的功能；"<<endl;
		cin>>select;
		switch(select){
		case 1:
			printf("串1的长度是：%d\n",StrLength(S1));
			printf("串2的长度是：%d\n",StrLength(S2));
		    break;
	    case 2:
	    	cha=StrCompare(S1,S2);
	    	cout<<"两串比较的结果是：";
	    	if(cha>0){
	    		cout<<"S1>S2"<<endl; 
			}else if(cha<0){
				cout<<"S1<S2"<<endl;
			}else cout<<"S1=S2"<<endl;
		   	break;
		case 3:
			int a;
			cout<<"请问想对哪个字符串进行取子串操作？(回复1或2)"<<endl;
			cin>>a;
			if(a==1){
				cout<<"输入你想取的S1的子串具体位置和长度：";
				cin>>pos>>len;
				if(SubString(Sub,S1,pos,len)){
				  cout<<"串1的第"<<pos<<"个位置开始长度为"<<len<<"的子串Sub为: ";
				  	PrintStr(Sub);
				}
				else{
					cout<<"查找子串失败！"<<endl;
				}
			   	break;
			}
			if(a==2){
				cout<<"输入你想取的S2的子串具体位置和长度：";
				cin>>pos>>len;
				if(SubString(Sub,S2,pos,len)){
				  cout<<"串2的第"<<pos<<"个位置开始长度为"<<len<<"的子串Sub为: ";
				  	PrintStr(Sub);
				}
				else{
					cout<<"查找子串失败！"<<endl;
				}
			   	break;
			}
			else{
				cout<<"输入错误！查找字串失败！"<<endl;
				break;
			}
		case 4:
			cout<<"请输入匹配的pos位置：";
			cin>>pos;
			if(Index(S1,S2,pos)){
				cout<<"串2在串1中位置是:"<<Index(S1,S2,pos)<<endl; 
			}else cout<<"匹配失败！"<<endl;
		
		   	break;
		case 5:
			Concat(T,S1,S2);
		    cout<<"串1和串2连接后的串为：";
			PrintStr(T);
		   	break;
  		case 6:
  			cout<<"欲实现串2对串1的插入！请输入插入的pos位置：";
			cin>>pos;
			if(StrInsert(S1,pos,S2)){
				PrintStr(S1);
				break;
			}
		case 7:
			Replace(Rep,S1,S2);
			cout<<"替换成功！";
			break;
  		case 8:
  			cout<<"请问想对哪个字符串进行删除操作？(回复1或2)"<<endl;
  			cin>>a;
  			if(a==1){
			  	cout<<"请输入对S1删除的pos位置和长度：";
				cin>>pos>>len;
				if(StrDelete(S1,pos,len)){
					PrintStr(S1);
				}
				else{
					cout<<"删除失败！"<<endl;
				}
				break;
		  	}
  			if(a==2){
			  	cout<<"请输入对S2删除的pos位置和长度：";
				cin>>pos>>len;
				if(StrDelete(S2,pos,len)){
					PrintStr(S2);
				}
				else{
					cout<<"删除失败！"<<endl;
				}
				break;
		  	}
		  	else{
	  			cout<<"输入错误！删除失败！"<<endl;
	  			break;
	  		}
		case 9:
  			cout<<"请问想对哪个字符串进行清空操作？(回复1或2)"<<endl;
  			cin>>a;
  			if(a==1){
  				if(ClearString(S1))	cout<<"已清空串1！"<<endl;
  				break;
  			}
  			if(a==2){
  				if(ClearString(S2))	cout<<"已清空串2！"<<endl;
  				break;
  			}
			else{
				cout<<"输入错误！清空失败！"<<endl;
	  			break;
			}	
		case 10:
		    cout<<"退出程序！";
		    exit(0);
		   	break;
	 	}
	}
}

 执行效果：

【数据结构】串的基本操作及应用

解题二（在题一基础上稍加修改即可）

/*用回溯法来实现模式匹配算法，寻找模式串t在主串s中从第pos位开始是否出现，若出现则返回第一次出现的位置，否则返回0*/
int StrIndex1(SString s,SString t,int pos)
{
	int s, t, i,j;
	s = S.length;
	t = T.length;
	i = pos;
	 j = 1;

    while(i<=S.length && j<=T.length)
    {
        if(S.ch[i]==T.ch[j]){
            ++i;++j;}
            else{
                i=i-j+2;j=1;}
                
    }
    if(j>T.length) return i-T.length;
    else return 0;
}
/*利用其他函数来实现模式匹配算法*/
int StrIndex2(SString s,SString t,int pos)
{
	int m,n,i;
	SString sub;
	n=StrLength(s);
	m=StrLength(t);
	i=pos;
	while(i<=n-m+1)
	{
		SubString(sub,s,i,m);
		if(StrCompare(sub,t)!=0) ++i;
		else return i;
	}
	return 0;
}
/*用KMP算法来实现模式匹配算法，效率较高*/
int StrIndex_KMP(SString s,SString t,int pos)
{
	int i,j;
	int next[MAX+1];
	i=1;
	next[i]=0;
	j=0;
	while(i<t[0])
	{
		if(j==0||t[i]==t[j])
		{
			i++;
			j++;
			if(t[i]!=t[j]) next[i]=j;
			else next[i]=next[j];
		}
		else j=next[j];
	}


	i=pos;
	j=1;
	while(i<=s[0]&&j<=t[0])
	{
		if(j==0 || s[i]==t[j])
		{
			i++;
			j++;
		}
		else
			j=next[j];
	}
	if(j>t[0])return i-t[0];
	else return 0;
}

 执行效果：

【数据结构】串的基本操作及应用

分享完毕~

欢迎小伙伴们在文下评论和私信喔~文章来源地址https://www.toymoban.com/news/detail-425629.html

到了这里，关于【数据结构】串的基本操作及应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构--图的基本操作

    数据结构--图的基本操作

    使用的存储模式： 图的基本操作： • Adjacent(G,x,y)：判断图G是否存在边x, y或(x, y)。 • Neighbors(G,x)：列出图G中与结点x邻接的边。 • InsertVertex(G,x)：在图G中插入顶点x。 • DeleteVertex(G,x)：从图G中删除顶点x。 • AddEdge(G,x,y)：若无向边(x, y)或有向边x, y不存在，则向图G中添加该

    2024年02月16日
    浏览(53)

  • (数据结构)链队列的基本操作

    2024年02月08日
    浏览(45)
  • 数据结构之栈的基本操作

    数据结构之栈的基本操作

    该顺序栈涉及到了存储整型数据的顺序栈还有存储字符型数据的顺序栈 实现的功能有：入栈、出栈、判断是否为空栈、求栈的长度、清空栈、销毁栈、得到栈顶元素 此外根据上述功能，编写了数值转换（十进制转化八进制）方法、括号匹配方法。 控制台界面展示： 进栈展示

    2024年01月23日
    浏览(50)
  • 数据结构——单链表基本操作实现 (c++)

    数据结构——单链表基本操作实现 (c++)

    单链表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这里存储单元可以是连续的，也可以是不连续的），为了表示每个数据元素a与其直接后继数据元素之间的逻辑关系，除了存储信息本身外还要存储一个指示其直接后继的信息（地址）. 这两部分信

    2024年02月03日
    浏览(68)

  • 数据结构---双向链表的基本操作

    头插法 遍历链表 尾插法 头删法 尾删法 按位置插入数据 按位置删除数据 dooublelinklist.c doublelinklist.h doublemain.c

    2024年02月22日
    浏览(53)
  • 【数据结构】队列基本操作的实现（C语言）

    【数据结构】队列基本操作的实现（C语言）

    🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。 🐌 个人主页：蜗牛牛啊 🔥 系列专栏：🛹数据结构、🛴C++ 📕 学习格言：博观而约取，厚积而薄发 🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与

    2024年02月16日
    浏览(51)
  • 数据结构实验4：二叉树的基本操作

    数据结构实验4：二叉树的基本操作

    一、问题描述 运用二叉链表实现二叉树的基本操作，包括：创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式：AB#C##D## 二、实验目的 掌握二叉链表及二叉树的基本操作。 三、实验内容及要求 1、构造

    2024年01月23日
    浏览(43)

  • 数据结构——单链表上基本操作的实现

    1.按位序插入（带头结点） ： ==ListInsert(L, i, e): ==在表L 中的第 i 个位置上插入指定元素 e = 找到第 i-1 个结点 ( 前驱结点 ) ，将新结点 插入其后；其中头结点可以看作第 0 个结点，故 i=1 时也适用。 typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; // 在第 i 个位置插入

    2024年01月21日
    浏览(57)
  • 【玩转408数据结构】线性表——定义和基本操作

    【玩转408数据结构】线性表——定义和基本操作

            线性表是算法题命题的重点，该类题目实现相对容易且代码量不高，但需要最优的性能（也就是其时间复杂度以及空间复杂度最优），这样才可以获得满分。所以在考研复习中，我们需要掌握线性表的基本操作，在平时多进行代码练习。当然在考场上，我们并不一

    2024年02月19日
    浏览(47)
  • 【数据结构】——单链表的基本操作（带头结点）

    【数据结构】——单链表的基本操作（带头结点）

            单链表解决了顺序表需要大量连续存储单元的缺点，但单链表附加指针域， 存储密度较顺序表低（考点！！） 。由于单链表的元素离散地分布在存储空间中，所以单链表是 非随机存取 的存储结构，即不能直接找到表中某个特定的结点。当查找某个特定结点时，需要

    2024年02月05日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包