数据结构实验(串的定义，基本操作及模式匹配)

末蓝、 2023-06-15 06:55 8阅读 0赞

## 实验名称：串的定义，基本操作及模式匹配 ##

## 实验目的： ##

掌握这种抽象数据类型的特点；熟练掌握串的顺序存储结构表示和基本操作，并能利用这些基本操作实现串的其他各种操作。

## 实验要求： ##

*  定义串的定长顺序存储结构；
 *  实现串赋值，求串长，求子串，串连接，串比较等基本操作，以及简单模式匹配：检索子串在主串中出现的次数及相应的位置。

## 代码： ##

分别用两种存储方式实现

1.  串的定长顺序存储实现

//串的定长顺序存储结构
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    
    typedef int Status;
    
    #define MAXSTRLEN 255//可在255以内定义最大串长
    typedef unsigned char SString[MAXSTRLEN+1];
    //0号单元存放串长
    
    //串赋值
    Status StrAssign(SString &S,char *chars)
    {
        	
    	int i,j;char *c;
    	for(i=0,c=chars;*c;++i,++c);
    	if(i>MAXSTRLEN) return ERROR;
    	else
    	{
        
    	S[0]=i;
    	for(j=1;j<=S[0];j++)
    		S[j]=*(chars+j-1);
    	}
    	return OK;
    }//StrAssign
    
    //创建串
    Status CreateString(SString &T)
    {
        
    	 char chars1[50];
    	 int k;
    	 gets(chars1);
    	 k=StrAssign(T,chars1);
    	if(!k)
    	{
        
    		printf("串长超过MAXSTRLEN(=%d)\n",MAXSTRLEN);
    		exit(0);
    	}
    	return OK;
    }//CreateString
    
    
    //求串长
    int StrLength(SString S)
    {
        
    	return S[0];
    }
    
    
    //输出字符串
    void StrPrint(SString S)
    {
        
    	int i;
    	for(i=1;i<=S[0];i++)
    	{
        
    	  printf("%c",S[i]);
    	}
    	printf("\n");
    
    }//StrPrint
    
    
    //求子串
    Status SubString(SString &Sub, SString S,int pos,int len)
    {
        //用Sub返回串S的第pos个字符起长度为len的字串
    	int i,j;
    	if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)
    		return ERROR;
    	if(!len)
    	{
        
    		Sub[0]=0;
    	}
    	else
    	{
        
    	for(i=1,j=pos;i<=len-1,j<=pos+len-1;i++,j++)
    			Sub[i]=S[j];
    			Sub[0]=len;
    	}
    		return OK;
    }//SubString
    
    
    
    //串连接
    Status Concat(SString &T,SString S1,SString S2)
    {
        //用T返回由S1和S2连接成的新串.
    	//若未截断,则返回TRUE,否则返回FALSE.
    	int i,j;
    	Status uncut;
    	if(S1[0]+S2[0]<=MAXSTRLEN)//未截断
    	{
        
    		T[0]=S1[0]+S2[0];
    	for(i=1;i<=S1[0];i++)
    	{
        
    		T[i]=S1[i];
    	}
    	for(j=1;j<=S2[0];j++)
    	{
        
    		T[S1[0]+j]=S2[j];
    	}
    		uncut=TRUE;
    	}
    	else if(S1[0]<MAXSTRLEN)//截断
    	{
        
    		T[0]=MAXSTRLEN;
    		for(i=1;i<S1[0];i++)
    		{
        
    			T[i]=S1[i];
    		}
    		for(j=1;j<=MAXSTRLEN-S1[0];j++)
    		{
        
    			T[S1[0]+j]=S2[j];
    		}
    		uncut=FALSE;
    		}
    		else//S1[0]>MAXSTRLEN
    		{
        
    			T[0]=MAXSTRLEN;
    			for(i=1;i<=MAXSTRLEN;i++)
    			{
        
    			T[i]=S1[i];
    			}
    			uncut=FALSE;
    		}
            return uncut;
    }//Concat
    
    
    
    //串比较
    int StrCompare(SString S,SString T)
    {
        //若S>T,则返回>0;若S=T,返回值=0;若S<T,返回值<0.
    	int i;
    	for(i=1;i<=S[0]&&i<=T[0];i++)
    	{
        
    	if(S[i]!=T[i])
    		return S[i]-T[i];
    
    	}
    	return S[0]-T[0];
    }//StrCompare
    
    
    
    //串的简单模式匹配
    int Index(SString s1,SString s2,int pos)
    {
        //返回子串在主串中第pos个字符之后出现的位置,
    	//若不存在,返回0.
    	//建议先判断pos值是否合法
    	//其中,s2非空,1<=pos<=StrLength(S)
    	int i=pos; int j=1;
    
    	while(i<=s1[0]&&j<=s2[0]){
        
    		if(s1[i]==s2[j]){
        
    		++i;++j;
    		}
    		else{
        i=i-j+2;j=1;}
    	}
    	if(j>s2[0]) return i-s2[0];
    	else return 0;
    }//Index
     
       
    void main(){
        
    	int i,j,opp=1;	int pos;
    	char s;
    	SString t,s1,s2,sub;
    	Status k;
    	printf("\n 1,StrAssign 生成串 \n 2,StrLength 求串长");
    	printf("\n 3,StrCompare 串比较\n 4,Concat 串连接");
    	printf("\n 5,SubString 求子串 \n 6,Index 串匹配");
    	printf("\n 0,退出\n");
    	printf("请输入你的操作:\n");
    	while(opp!=0){
        
    	scanf("%d",&opp);
    	getchar();//add
    	switch(opp)
    	{
        
    	case 1:
    		//k=StrAssign(s1,"DOorDIE");
    		printf("Please input s1:  ");	CreateString(s1);
    		printf("串s1为:  ");		StrPrint(s1);
    		printf("\n");break;
    	case 2:
    		printf("串长为%d\n",StrLength(s1));
    		break;
    	case 3:
    		//k=StrAssign(s2,"YOUCAN");
    		printf("Please input s2:  ");	CreateString(s2);
    		printf("串s2为:  ");		StrPrint(s2);
    		printf("\n");
    		i=StrCompare(s1,s2);
    		if(i<0)	s='<';
    		else if(i==0)	s='=';
    		else s='>';
    		printf("串s1%c串s2\n",s);     break;
    	case 4:
    		Concat(t,s1,s2);
    		StrPrint(t);
    		break;
    	case 5:
    		printf("求串s1的子串,请输入子串起始位置:  ");
    		scanf("%d",&i);
    		printf("请输入子串的长度: ");
    		scanf("%d",&j);
    		printf("起始位置: %d，子串长度:  %d",i,j);
    		k=SubString(sub,s1,i,j);
    		if(k)
    		{
        
    		printf(" 子串 sub为:  ");
    		StrPrint(sub);
    		}
    		break;
    	case 6:
    		int wz[80];//wz数组记录子串出现的位置
    		i=0;//计数器清零
    		printf("Please input s1:");	CreateString(s1);
    		printf("Please input s2:");	CreateString(s2);
    
    		pos=1;//初始化起始检索位置
    		while(pos<=s1[0])//检索整个主串
    		{
        
    		j=Index(s1,s2,pos);//调用串匹配算法
    		if(j<2)		break;
    		else
    		{
        
    			i++;wz[i]=j;pos=j+s2[0];
    		}//继续下一个子串的检索
    		}if(i==0)  printf("没有检索到需要的子串!  ");
    //如果退出循环后,i仍为0,说明不存在匹配的子串
    		else{
        
    		printf("子串在主串中出现%d次\n",i);
    			printf("%d次匹配的位置分别为:",i);
    			for(k=1;k<=i;k++)printf("%4d",wz[k]);} 
    		printf("\n");  break;
    	case 0:
    		exit(0);}//switch
    	printf("请选择你的操作:\n");
    	}//while
    }//main

1.  串的堆分配存储

//串的堆分配存储
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<malloc.h>
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    
    typedef int Status;
    typedef struct
    {
        
    	char *ch;
    	int length;
    }HString;
    
    
    
    
    Status StrInit(HString &T)
    {
        //初始化串
    T.ch=NULL;
    T.length=0;
    return OK;
    }
    
    
    
    
    Status StrAssign(HString &T,char *chars)
    {
        //串赋值
    	if(T.ch)  free(T.ch);
    	char* c=chars;
    	for(int i=0; *c; i++,++c);
    	if(!i)
    	{
        
    		T.ch=NULL;  T.length=0;
    	}
    	else{
        
    	if(!(T.ch=(char*)malloc(i*sizeof(char))))
    		exit(OVERFLOW);
    	for(int j=0;j<i;j++)
    	{
        
    		T.ch[j]=chars[j];
    	}
    	T.length=i;
    	}
    	printf("串创建成功！");
    	return OK;
    }//StrAssign
    
    
    Status CreateString(HString &T)
    {
        //创建串
    	 char chars1[50];
    	 int k;
    	 gets(chars1);
    	 k=StrAssign(T,chars1);
    
    	return OK;
    }//CreateString
    
    
    
    
    
    int StrLength(HString S)
    {
        //求串长
    	return S.length;
    }//StrLength
    
    
    
    Status StrPrint(HString S)
    {
        //输出字符串
    	for(int i=0;i<S.length;i++)
    	{
        
    	  printf("%c",S.ch[i]);
    	}
    	printf("\n");
    	return OK;
    }//StrPrint
    
    
    
    Status SubString(HString &Sub, HString S,int pos,int len)
    {
           //求子串
    	//用Sub返回串S的第pos个字符起长度为len的字串
    	
    	if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
    		return ERROR;
    	if(Sub.ch) free(Sub.ch);
    	if(!len)
    	{
        
    		Sub.ch=NULL;
    		Sub.length=0;
    	}
    	else
    	{
        
    		Sub.ch=(char *)malloc(len*sizeof(char));
    		if(!Sub.ch)   exit(OVERFLOW);
    		for(int i=0;i<len;i++)	
    		Sub.ch[i]=S.ch[pos+i-1];
    		Sub.length=len;
    	}
    		return OK;
    }//SubString
    
    
    
    //串连接
    Status Concat(HString &T,HString S1,HString S2)
    {
        //用T返回由S1和S2连接成的新串.
    	//若未截断,则返回TRUE,否则返回FALSE.
    
    	if(T.ch)  free(T.ch);
    	if(!(T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char))))
    		exit(OVERFLOW);
    	for(int i=0;i<S1.length;i++)
    	T.ch[i]=S1.ch[i];
    	T.length=S1.length+S2.length;
    	for(i=S1.length;i<T.length;i++)
    	T.ch[i]=S2.ch[i-S1.length];
    	return OK;
    
    }//Concat
    
    
    
    //串比较
    int StrCompare(HString S,HString T)
    {
        //若S>T,则返回>0;若S=T,返回值=0;若S<T,返回值<0.
    	int i;
    	for(i=0;i<S.length&&i<T.length;i++)
    	{
        
    		if(S.ch[i]!=T.ch[i])
    		return S.ch[i]-T.ch[i];
    	}
    	return S.length-T.length;
    }//StrCompare
    
    
    
    //串的简单模式匹配
    int Index(HString s1,HString s2,int pos)
    {
        //返回子串在主串中第pos个字符之后出现的位置,
    	//若不存在,返回0.
    	//建议先判断pos值是否合法
    	//其中,s2非空,1<=pos<=StrLength(S)
    	if(pos<1||pos>s1.length)  return ERROR;
    	int i=pos-1,j=0;
    	while(i<s1.length&&j<s2.length)
    	{
        
    		if(s1.ch[i]==s2.ch[j])
    		{
        
    		++i;++j;
    		}
    		else
    		{
        
    		i=i-j+1;
    			j=0;
    		}	
    	}
    
    	if(j>=s2.length) return i-s2.length+1;
    	else return 0;
    }//Index
     
       
    void main(){
        
    	int i,j,opp=1;	int pos;
    	char s;
    	char chars1[10],chars2[10];
    	HString t,s1,s2,sub;
        StrInit(t);
    	StrInit(s1);
    	StrInit(s2);
    	StrInit(sub);
    	Status k;
    	printf("\n 1,StrAssign 生成串 \n 2,StrLength 求串长");
    	printf("\n 3,StrCompare 串比较\n 4,Concat 串连接");
    	printf("\n 5,SubString 求子串 \n 6,Index 串匹配");
    	printf("\n 0,退出\n");
    	printf("请输入你的操作:\n");
    	while(opp!=0){
        
    	scanf("%d",&opp);
    	getchar();//add
    	switch(opp)
    	{
        
    	case 1:
    		//k=StrAssign(s1,"DOorDIE");
    		printf("Please input s1:  ");CreateString(s1);
    		printf("串s1为:  ");		StrPrint(s1);
    		printf("\n");break;
    	case 2:
    		printf("串长为%d\n",StrLength(s1));
    		break;
    	case 3:
    		//k=StrAssign(s2,"YOUCAN");
    		printf("Please input s2:  ");	CreateString(s2);
    	printf("串s2为:  ");		StrPrint(s2);
    		printf("\n");
    		i=StrCompare(s1,s2);
    		if(i<0)	s='<';
    		else if(i==0)	s='=';
    		else s='>';
    		printf("串s1%c串s2\n",s);     break;
    	case 4:
    		Concat(t,s1,s2);
    		StrPrint(t);
    		break;
    	case 5:
    		printf("求s1的子串,请输入子串起始位置:  ");
    		scanf("%d",&i);
    		printf("请输入子串的长度: ");
    		scanf("%d",&j);
    		printf("起始位置: %d,子串长度:  %d",i,j);
    		k=SubString(sub,s1,i,j);
    		if(k)
    		{
        
    		printf("子串sub为:  ");
    		StrPrint(sub);
    		}else printf("未检索到子串！");
    		break;
    	case 6:
    		int wz[80];//wz数组记录子串出现的位置
    		i=0;//计数器清零
    		printf("Please input s1:");	CreateString(s1);
    		printf("Please input s2:");CreateString(s2);
    		pos=1;//初始化起始检索位置
    		while(pos<=s1.length)//检索整个主串
    		{
        
    		j=Index(s1,s2,pos);//调用串匹配算法
    		if(j<1)		break;
    		else
    		{
        
    			i++;wz[i]=j;pos=j+s2.length;
    		}//继续下一个子串的检索
    		}if(i==0)  printf("没有检索到需要的子串!  ");
    //如果退出循环后,i仍为,说明不存在匹配的子串
    		else{
        
    		printf("子串在主串中出现%d次\n",i);
    			printf("%d次匹配的位置分别为:",i);
    			for(k=1;k<=i;k++)printf("%4d",wz[k]);} 
    		printf("\n");  break;
    	case 0:
    		exit(0);}//switch
    	printf("请输入你的操作:\n");
    	}//while
    }//main

*  运行结果  
    ![在这里插入图片描述][20191120220751427.png]
 *  串

*to be continued*  
*how  
2019/11/20*

[20191120220751427.png]: https://img-blog.csdnimg.cn/20191120220751427.png