• 数据结构学习笔记——顺序存储结构实现串

    目录

    一、串的相关概念

    • 串由零个或多个字符组成的有限序列，其数据元素就是字符，它是一种特殊的线性表。由任意多个连续的字符组成的子序列称为串的子串，包含子串的串称为主串，线性表是以单个元素进行相关操作，而串是以子串进行相关操作的。
    • 串的长度等于0时的串称为空串，空串是任意串的子串，任意串是自身的子串。

    二、定长顺序存储和变长分配存储

    （一）定长顺序存储
    通过静态数组实现定长顺序存储，一组地址连续的存储单元存储串值的字符序列，其中每个串都被分配一个固定长度的ch[MAXLEN]数组。

    #include<stdio.h>
#define MAXLEN 255
typedef struct{
	char ch[MAXLEN];	//为每个串分配一个固定长度的数组 
	int length;		//串的实际长度 
}SString;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    （二）变长分配存储（堆分配存储）
    而当序列的长度超过事先限定的MAXLEN值时，则此时可以采用变长分配存储，适用于串长较灵活的情况。与定长顺序存储一样，也是采用一组地址连续的存储单元来存放串值的字符序列，但堆分配存储的存储空间是动态分配的，通过malloc()和free()函数来完成动态存储的分配和释放。

    • 分配成功时，返回一个指向起始地址的指针*ch作为串的基地址，它指向动态分配存储区首地址的字符指针，若分配失败则返回NULL。
    //堆分配存储的定义 
#include<stdio.h>
#include<stdlib.h>
typedef struct{
	char *ch;	//指向串的基地址 ，即指向动态分配存储区首地址的字符指针 
	int length;		//串的实际长度 
}HString;

HString S;
S.ch=(char *)malloc(MAXLEN*sizeof(char));	//malloc动态分配 
S.length=0;		//初始化length串长度 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    三、串的初始化

    /*初始化串S*/
void InitString(SString &S) {
	S.length = 0;		
}

    • 1
    • 2
    • 3
    • 4

    四、判断串是否为空

    /*判断串S是否为空*/
bool EmptyString(SString &S) {
	if (S.length == 0)
		return false;
	else
		return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    五、串的建立

    串的建立中，通过从键盘读入一个字符串并赋给S，如下代码：

    /*串的建立*/
void CreateString(SString &S) {
	printf("请输入一个字符串：\n");
	scanf("%s",&S.ch);
}

    • 1
    • 2
    • 3
    • 4
    • 5

    六、串的遍历输出

    /*串的遍历输出*/
void PrintString(SString S) {
	for(int i=0; i<S.length; i++)
		printf("%c ", S.ch[i]);
}

    • 1
    • 2
    • 3
    • 4
    • 5

    七、求串的长度

    通过while()循环，每次读取一个字符然后S.length++，最后得到串的长度，如下代码：

    /*求串的长度*/
bool LengthString(SString &S) {
	if(S.ch[0]=='\0')
		return false;	//空串报错
	while(S.ch[S.length]!='\0')
		S.length++;
	printf("该串的长度为：%d\n",S.length);
	return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    八、求串的子串

    求子串的操作是从串S的第某位起，length为相关长度的子串S1，也就是截取串S的部分，首先要判断求的子串的相关参数是否正确合法，然后通过循环依次将串S的相应内容赋值给新串（子串）中 ，代码如下：

    /*求子串*/
//求串S的第pos位置开始，长度为length的子串，并将其存入到串Sub中
int SubString(SString &S,SString &Sub,int pos,int length) {
	if(pos<1||pos>S.length||length<1||length>S.length-pos+1) {
		return false;	//以上情况报错 
	} else {
		for(int i=0; i<length; i++)
			Sub.ch[i]=S.ch[pos+i-1];	//依次将串S的相应内容赋值给新串（子串）中 
		Sub.length=length;	//新串（子串）的长度 
		return true;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    例已知串S“ABCDEFGH”，求串S从第2位起，长度为4的子串子串，并将其存入到串S1中，最后输出串S1。

    代码如下：

    #include<stdio.h>
#define MAXLEN 255
typedef struct {
	char ch[MAXLEN];	//为每个串分配一个固定长度的数组
	int length;		//串的实际长度
} SString;

/*初始化*/
void InitString(SString &S) {
	S.length = 0;
}

/*求串的长度*/
bool LengthString(SString &S) {
	if(S.ch[0]=='\0')
		return false;	//空串报错
	while(S.ch[S.length]!='\0')
		S.length++;
	printf("该串的长度为：%d\n",S.length);
	return true;
}

/*串的建立*/
void CreateString(SString &S) {
	printf("请输入一个字符串：\n");
	scanf("%s",&S.ch);
}

/*串的遍历输出*/
void PrintString(SString S) {
	for(int i=0; i<S.length; i++)
		printf("%c ", S.ch[i]);
}

/*求子串*/
//求串S的第pos位置开始，长度为length的子串，并将其存入到串Sub中
int SubString(SString &S,SString &Sub,int pos,int length) {
	if(pos<1||pos>S.length||length<1||length>S.length-pos+1) {
		return false;	//以上情况报错 
	} else {
		for(int i=0; i<length; i++)
			Sub.ch[i]=S.ch[pos+i-1];	//依次将串S的相应内容赋值给新串（子串）中 
		Sub.length=length;	//新串（子串）的长度 
		return true;
	}
}

/*主函数*/
int main() {
	int pos,length;
	SString S,S1;
	InitString(S);	//初始化
	CreateString(S);	//串的创建
	LengthString(S);	//求串的长度
	PrintString(S);	//遍历串 
	printf("\n"); 
	printf("请输入从串的第几个字符开始求子串pos以及要取出的子串长度length：\n");
	scanf("%d %d",&pos,&length);
	SubString(S,S1,pos,length);
	LengthString(S1);	
	PrintString(S1);	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    运行结果如下：
    在这里插入图片描述

    九、插入子串

    插入子串的操作是在串S的第i个位置进行插入，插入子串S1，首先也是要判断插入的位置是否合法（要注意插入后两个串的长度相加之和是否超过存储空间长度），将从第i位开始的字符都向后移动S1串长度，然后通过循环依次将子串S1插入到串S的第i位开始的依次位置处，最后再修改串S的长度，并在新串S的末尾加上字符串结束标志“\0”，代码如下：

    /*插入子串*/
bool InsertString(SString &S,SString &S1,int i) {
	int n;
	if(i>S.length+1||S.length+S1.length>MAXLEN)		//报错 
		return false;
	else {
		for(n=S.length-1; n>=i-1; n--)	//从第i位开始的字符都向后移动S1串长度
			S.ch[S1.length+n]=S.ch[n];
		for(n=0; n<S1.length; n++)	//将子串S1依次插入到串S的第i位开始的依次位置处
			S.ch[i+n-1]=S1.ch[n];
		S.length=S.length+S1.length;	//修改串S的长度
		S.ch[S.length]='\0';	//加上字符串结束标志\0 
		return true;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    例已知串S“aaaaaa”和串S1“bbb”，将串S1插入至串S的第二位，最后输出串S。

    代码如下：

    #include<stdio.h>
#define MAXLEN 255
typedef struct {
	char ch[MAXLEN];	//为每个串分配一个固定长度的数组
	int length;		//串的实际长度
} SString;

/*初始化*/
void InitString(SString &S) {
	S.length = 0;
}

/*求串的长度*/
bool LengthString(SString &S) {
	if(S.ch[0]=='\0')
		return false;	//空串
	while(S.ch[S.length]!='\0')
		S.length++;
	printf("该串的长度为：%d\n",S.length);
	return true;
}

/*串的建立*/
void CreateString(SString &S) {
	printf("请输入一个字符串：\n");
	scanf("%s",&S.ch);
}

/*串的遍历输出*/
void PrintString(SString S) {
	for(int i=0; i<S.length; i++)
		printf("%c ", S.ch[i]);
}

/*插入子串*/
bool InsertString(SString &S,SString &S1,int i) {
	int n;
	if(i>S.length+1||S.length+S1.length>MAXLEN)		//报错 
		return false;
	else {
		for(n=S.length-1; n>=i-1; n--)	//从第i位开始的字符都向后移动S1串长度
			S.ch[S1.length+n]=S.ch[n];
		for(n=0; n<S1.length; n++)	//将子串S1依次插入到串S的第i位开始的依次位置处
			S.ch[i+n-1]=S1.ch[n];
		S.length=S.length+S1.length;	//修改串S的长度
		S.ch[S.length]='\0';	//加上字符串结束标志\0 
		return true;
	}
}

/*主函数*/
int main() {
	int i;
	SString S,S1;
	printf("请输入串S！");
	InitString(S);	//初始化
	CreateString(S);	//串S的创建
	printf("请输入要插入的子串S1！");
	InitString(S1);	//初始化
	CreateString(S1);	//串S1的创建
	LengthString(S);
	PrintString(S);
	printf("\n"); 
	LengthString(S1);
	PrintString(S1);
	printf("\n"); 
	printf("请输入从串的第几个字符插入子串i：");
	scanf("%d",&i);
	InsertString(S,S1,i);	//插入子串 
	printf("插入子串后的串S的长度,");
	LengthString(S);
	PrintString(S);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    运行结果如下：
    在这里插入图片描述

    十、删除子串

    删除子串的操作也就是删除从串S的某一位置起连续的字符，首先要判断删除的位置以及删除的串长度是否正确合法，否则报错，将第i+j-1位的字符向前移动到第i位依次移动字符，最后再修改串S的长度，并在新串S的末尾加上字符串结束标志“\0”，例如删除第2位长度为4的字符，串S总长度为8，删除后原先第5位的字符向前移动到第2位上，原先第6位的字符向前移动到第3位上，……，代码如下：

    /*删除子串*/
bool DeleteString(SString &S,int i,int j) {
	if(i+j-1>S.length)	//所删除的子串超过串S长度，则报错
		return false;
	else {
		for(int n=i+j-1; n<S.length; n++,i++)
			S.ch[i-1]=S.ch[n];	//从串的第i位删除长度为j多个字符
		S.length=S.length-j;	//修改串S的长度
		S.ch[S.length]='\0';	//加上字符串结束标志\0 
		return true;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    例已知串S“ABCDEFGHIJK”，删除串S中从第2位起，长度为6的子串，最后输出串S。

    代码如下：

    #include<stdio.h>
#define MAXLEN 255
typedef struct {
	char ch[MAXLEN];	//为每个串分配一个固定长度的数组
	int length;		//串的实际长度
} SString;

/*初始化*/
void InitString(SString &S) {
	S.length = 0;
}

/*求串的长度*/
bool LengthString(SString &S) {
	if(S.ch[0]=='\0')
		return false;	//空串
	while(S.ch[S.length]!='\0')
		S.length++;
	printf("该串的长度为：%d\n",S.length);
	return true;
}

/*串的建立*/
void CreateString(SString &S) {
	printf("请输入一个字符串：\n");
	scanf("%s",&S.ch);
}

/*串的遍历输出*/
void PrintString(SString S) {
	for(int i=0; i<S.length; i++)
		printf("%c ", S.ch[i]);
}

/*删除子串*/
bool DeleteString(SString &S,int i,int j) {
	if(i+j-1>S.length)	//所删除的子串
		return false;
	else {
		for(int n=i+j-1; n<S.length; n++,i++)
			S.ch[i-1]=S.ch[n];	//从串的第i位删除长度为j多个字符
		S.length=S.length-j;	//修改串S的长度
		S.ch[S.length]='\0';	//加上字符串结束标志\0 
		return true;
	}
}

/*主函数*/
int main() {
	int i,j;
	SString S;
	InitString(S);	//初始化
	CreateString(S);	//串的创建
	LengthString(S);	//求串的长度
	PrintString(S);	//遍历串
	printf("\n");
	printf("请输入从串的第几个字符开始删除位置i以及要删除的子串长度j：\n");
	scanf("%d %d",&i,&j);
	DeleteString(S,i,j);	//删除子串 
	LengthString(S);
	PrintString(S);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    运行结果如下：
    在这里插入图片描述

    十一、连接子串

    连接子串，也就是将第二个串S2连接到第一个串S1的后，最后形成一个新串S，首先要判断连接成功后的总长度是否预定的存储空间长度，若成功则形成串S，修改串S1的长度并设字符串结束标志；若连接后的串S大于预定的存储空间长度，则多余的部分字符序列将会被舍弃，代码如下：

    /*连接子串*/
bool ConnectString(SString &S,SString &S1) {
	int i;
	if(S.length==MAXLEN)	//当串S的长度等于预先设定的存储空间长度MAXLEN则报错 
		return false;
	if(S.length+S1.length<=MAXLEN) {	//连接后，串S的长度小于定的存储空间长度MAXLEN 
		for(i=S.length; i<S.length+S1.length; i++)
			S.ch[i]=S1.ch[i-S.length];
		S.ch[i]='\0';	//加上字符串结束标志\0
		S.length=S.length+S1.length;
	} else if(S.length<MAXLEN) {	//连接后，串S的长度大于MAXLEN，但串S1的长度小于MAXLEN，部分字符将被舍弃 
		for(i=S.length; i<MAXLEN; i++)
			S.ch[i]=S1.ch[i-S.length];
		S.length=MAXLEN;
	}
	return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    例已知串S“aaaa”和串S1“bbbbb”，将串S和串S1连接，最后输出串S。

    代码如下：

    #include<stdio.h>
#define MAXLEN 255
typedef struct {
	char ch[MAXLEN];	//为每个串分配一个固定长度的数组
	int length;		//串的实际长度
} SString;

/*初始化*/
void InitString(SString &S) {
	S.length = 0;
}

/*求串的长度*/
bool LengthString(SString &S) {
	if(S.ch[0]=='\0')
		return false;	//空串
	while(S.ch[S.length]!='\0')
		S.length++;
	printf("该串的长度为：%d\n",S.length);
	return true;
}

/*串的建立*/
void CreateString(SString &S) {
	printf("请输入一个字符串：\n");
	scanf("%s",&S.ch);
}

/*串的遍历输出*/
void PrintString(SString S) {
	for(int i=0; i<S.length; i++)
		printf("%c ", S.ch[i]);
}

/*连接子串*/
bool ConnectString(SString &S,SString &S1) {
	int i;
	if(S.length==MAXLEN)	//当串S的长度等于预先设定的存储空间长度MAXLEN则报错 
		return false;
	if(S.length+S1.length<=MAXLEN) {	//连接后，串S的长度小于定的存储空间长度MAXLEN 
		for(i=S.length; i<S.length+S1.length; i++)
			S.ch[i]=S1.ch[i-S.length];
		S.ch[i]='\0';	//加上字符串结束标志\0
		S.length=S.length+S1.length;
	} else if(S.length<MAXLEN) {	//连接后，串S的长度大于MAXLEN，但串S1的长度小于MAXLEN，部分字符将被舍弃 
		for(i=S.length; i<MAXLEN; i++)
			S.ch[i]=S1.ch[i-S.length];
		S.length=MAXLEN;
	}
	return true;
}

/*主函数*/
int main() {
	SString S,S1;
	printf("请输入串S！");
	InitString(S);	//初始化
	CreateString(S);	//串S的创建
	printf("请输入串S1！");
	InitString(S1);	//初始化
	CreateString(S1);	//串S1的创建
	LengthString(S);
	PrintString(S);
	printf("\n");
	LengthString(S1);
	PrintString(S1);
	printf("\n");
	ConnectString(S,S1);
	printf("连接后的串S的长度,");
	LengthString(S);
	PrintString(S);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72

    运行结果如下：
    在这里插入图片描述

    十二、比较子串

    比较两个串S1和串S2是否相等，代码如下：

    /*比较子串*/
bool CompareString(SString &S,SString &S1) {
	int i=0,flag=0;
	while(S.ch[i]!='\0'&&S1.ch[i]!='\0') {	//当串没到尾部时循环一直执行下去 
		if(S.ch[i]!=S1.ch[i]) {	//比较两个串对应位置的字符是否相同 
			flag=1;		//如果不相同，则将flag置为1 
			break;
		} else	//否则i++ 
			i++;
	}
	if(S.length==S1.length&&flag==0) {
		printf("两个串相等！");
		return true;	//相等
	} else {
		printf("两个串不相等！");
		return false;	//不相等
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    例已知串S“aaaa”和串S1“aaba”，比较这两个串。

    代码如下：

    #include<stdio.h>
#define MAXLEN 255
typedef struct {
	char ch[MAXLEN];	//为每个串分配一个固定长度的数组
	int length;		//串的实际长度
} SString;

/*初始化*/
void InitString(SString &S) {
	S.length = 0;
}

/*串的建立*/
void CreateString(SString &S) {
	printf("请输入一个字符串：\n");
	scanf("%s",&S.ch);
}

/*串的遍历输出*/
void PrintString(SString S) {
	for(int i=0; i<S.length; i++)
		printf("%c ", S.ch[i]);
}

/*比较子串*/
bool CompareString(SString &S,SString &S1) {
	int i=0,flag=0;
	while(S.ch[i]!='\0'&&S1.ch[i]!='\0') {	//当串没到尾部时循环一直执行下去 
		if(S.ch[i]!=S1.ch[i]) {	//比较两个串对应位置的字符是否相同 
			flag=1;		//如果不相同，则将flag置为1 
			break;
		} else	//否则i++ 
			i++;
	}
	if(S.length==S1.length&&flag==0) {
		printf("两个串相等！");
		return true;	//相等
	} else {
		printf("两个串不相等！");
		return false;	//不相等
	}
}

/*主函数*/
int main() {
	SString S,S1;
	printf("请输入串S！");
	InitString(S);	//初始化
	CreateString(S);	//串S的创建
	printf("请输入串S1！");
	InitString(S1);	//初始化
	CreateString(S1);	//串S1的创建
	LengthString(S);
	PrintString(S);
	printf("\n");
	LengthString(S1);
	PrintString(S1);
	printf("\n");
	CompareString(S,S1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    运行结果如下：
    在这里插入图片描述

    十三、串的模式匹配算法

    搜索串中的子串，若存在则返回子串在串S中第一次出现的位置，否则直到i、j指向两个串尾时结束循环，对应位置的相应字符相同则继续比较，若不相同则进行下一次字符进行比较（若第一个字符不相同，即i=i-j+1=1，j=0，开始将串S的第二个字符与串S1的第一个字符进行比较），代码如下：

    /*搜索子串,在串S中查找子串S1*/
bool IndexString(SString &S,SString &S1) {
	int i=0,j=0;
	while(i<S.length&&j<S1.length) {	//直到两个串的串尾时结束while循环
		if(S.ch[i]==S1.ch[j]) {	//若对应字符相同则继续比较下一个字符，i++、j++
			i++;
			j++;
		} else {	//否则进行下一次的字符串首字符比较
			i=i-j+1;
			j=0;
		}
	}
	if(j>=S1.length) {	//当串S中有串S1时，返回其首次出现的起始位置i，由于是数组下标i的值要减一
		printf("查找成功，该子串在主串中第一次出现的位置为%d",i-1);
		return true;
	} else {
		printf("查找失败，主串中没有该子串！");
		return false;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    例已知串S“ABCDEF”和子串S1“CDE”，查找子串S1是否在串S中。

    代码如下：

    #include<stdio.h>
#define MAXLEN 255
typedef struct {
	char ch[MAXLEN];	//为每个串分配一个固定长度的数组
	int length;		//串的实际长度
} SString;

/*初始化*/
void InitString(SString &S) {
	S.length = 0;
}

/*求串的长度*/
bool LengthString(SString &S) {
	if(S.ch[0]=='\0')
		return false;	//空串
	while(S.ch[S.length]!='\0')
		S.length++;
	printf("该串的长度为：%d\n",S.length);
	return true;
}

/*串的建立*/
void CreateString(SString &S) {
	printf("请输入一个字符串：\n");
	scanf("%s",&S.ch);
}

/*串的遍历输出*/
void PrintString(SString S) {
	for(int i=0; i<S.length; i++)
		printf("%c ", S.ch[i]);
}

/*搜索子串,在串S中查找子串S1*/
bool IndexString(SString &S,SString &S1) {
	int i=0,j=0;
	while(i<S.length&&j<S1.length) {	//直到两个串的串尾时结束while循环
		if(S.ch[i]==S1.ch[j]) {	//若对应字符相同则继续比较下一个字符，i++、j++
			i++;
			j++;
		} else {	//否则进行下一次的字符串首字符比较
			i=i-j+1;
			j=0;
		}
	}
	if(j>=S1.length) {	//当串S中有串S1时，返回其首次出现的起始位置i，由于是数组下标i的值要减一
		printf("查找成功，该子串在主串中第一次出现的位置为%d",i-1);
		return true;
	} else {
		printf("查找失败，主串中没有该子串！");
		return false;
	}
}

/*主函数*/
int main() {
	int i;
	SString S,S1;
	printf("请输入串S！");
	InitString(S);	//初始化
	CreateString(S);	//串S的创建
	printf("请输入串S1！");
	InitString(S1);	//初始化
	CreateString(S1);	//串S1的创建
	LengthString(S);
	PrintString(S);
	printf("\n");
	LengthString(S1);
	PrintString(S1);
	printf("\n");
	IndexString(S,S1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    运行结果如下：
    在这里插入图片描述

    例已知串S“ABCDEFGHJI”和子串S1“GI”，查找子串S1是否在串S中。

    代码如下：

    #include<stdio.h>
#define MAXLEN 255
typedef struct {
	char ch[MAXLEN];	//为每个串分配一个固定长度的数组
	int length;		//串的实际长度
} SString;

/*初始化*/
void InitString(SString &S) {
	S.length = 0;
}

/*求串的长度*/
bool LengthString(SString &S) {
	if(S.ch[0]=='\0')
		return false;	//空串
	while(S.ch[S.length]!='\0')
		S.length++;
	printf("该串的长度为：%d\n",S.length);
	return true;
}

/*串的建立*/
void CreateString(SString &S) {
	printf("请输入一个字符串：\n");
	scanf("%s",&S.ch);
}

/*串的遍历输出*/
void PrintString(SString S) {
	for(int i=0; i<S.length; i++)
		printf("%c ", S.ch[i]);
}

/*搜索子串,在串S中查找子串S1*/
bool IndexString(SString &S,SString &S1) {
	int i=0,j=0;
	while(i<S.length&&j<S1.length) {	//直到两个串的串尾时结束while循环
		if(S.ch[i]==S1.ch[j]) {	//若对应字符相同则继续比较下一个字符，i++、j++
			i++;
			j++;
		} else {	//否则进行下一次的字符串首字符比较
			i=i-j+1;
			j=0;
		}
	}
	if(j>=S1.length) {	//当串S中有串S1时，返回其首次出现的起始位置i，由于是数组下标i的值要减一
		printf("查找成功，该子串在主串中第一次出现的位置为%d",i-1);
		return true;
	} else {
		printf("查找失败，主串中没有该子串！");
		return false;
	}
}

/*主函数*/
int main() {
	int i;
	SString S,S1;
	printf("请输入串S！");
	InitString(S);	//初始化
	CreateString(S);	//串S的创建
	printf("请输入串S1！");
	InitString(S1);	//初始化
	CreateString(S1);	//串S1的创建
	LengthString(S);
	PrintString(S);
	printf("\n");
	LengthString(S1);
	PrintString(S1);
	printf("\n");
	IndexString(S,S1);	//串的搜索
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    运行结果如下：
    在这里插入图片描述

    顺序存储结构实现串的完整代码

    #include<stdio.h>
#define MAXLEN 255
typedef struct {
	char ch[MAXLEN];	//为每个串分配一个固定长度的数组
	int length;		//串的实际长度
} SString;

/*初始化*/
void InitString(SString &S) {
	S.length = 0;
}

/*判断串S是否为空*/
bool EmptyString(SString &S) {
	if (S.length == 0)
		return false;
	else
		return true;
}

/*求串的长度*/
bool LengthString(SString &S) {
	if(S.ch[0]=='\0')
		return false;	//空串
	while(S.ch[S.length]!='\0')
		S.length++;
	printf("该串的长度为：%d\n",S.length);
	return true;
}

/*串的建立*/
void CreateString(SString &S) {
	printf("请输入一个字符串：\n");
	scanf("%s",&S.ch);
}

/*串的遍历输出*/
void PrintString(SString S) {
	for(int i=0; i<S.length; i++)
		printf("%c ", S.ch[i]);
}

/*求子串*/
//求串S的第pos位置开始，长度为length的子串，并将其存入到串Sub中
int SubString(SString &S,SString &Sub,int pos,int length) {
	if(pos<1||pos>S.length||length<1||length>S.length-pos+1) {
		return false;	//以上情况报错
	} else {
		for(int i=0; i<length; i++)
			Sub.ch[i]=S.ch[pos+i-1];	//依次将串S的相应内容赋值给新串（子串）中
		Sub.length=length;	//新串（子串）的长度
		return true;
	}
}

/*插入子串,在串S中指定位置插入串S1*/
bool InsertString(SString &S,SString &S1,int i) {
	int n;
	if(i>S.length+1||S.length+S1.length>MAXLEN)		//报错
		return false;
	else {
		for(n=S.length-1; n>=i-1; n--)	//从第i位开始的字符都向后移动S1串长度
			S.ch[S1.length+n]=S.ch[n];
		for(n=0; n<S1.length; n++)	//将子串S1依次插入到串S的第i位开始的依次位置处
			S.ch[i+n-1]=S1.ch[n];
		S.length=S.length+S1.length;	//修改串S的长度
		S.ch[S.length]='\0';	//加上字符串结束标志\0
		return true;
	}
}

/*删除子串，删除串S中指定位置开始的字符*/
bool DeleteString(SString &S,int i,int j) {
	if(i+j-1>S.length)
		return false;
	else {
		for(int n=i+j-1; n<S.length; n++,i++)
			S.ch[i-1]=S.ch[n];	//从串的第i位删除长度为j多个字符
		S.length=S.length-j;	//修改串S的长度
		S.ch[S.length]='\0';	//加上字符串结束标志\0
		return true;
	}
}

/*连接子串，连接串S和串S1*/
bool ConnectString(SString &S,SString &S1) {
	int i;
	if(S.length==MAXLEN)	//当串S的长度等于预先设定的存储空间长度MAXLEN则报错
		return false;
	if(S.length+S1.length<=MAXLEN) {	//连接后，串S的长度小于定的存储空间长度MAXLEN
		for(i=S.length; i<S.length+S1.length; i++)
			S.ch[i]=S1.ch[i-S.length];
		S.ch[i]='\0';	//加上字符串结束标志\0
		S.length=S.length+S1.length;
	} else if(S.length<MAXLEN) {	//连接后，串S的长度大于MAXLEN，但串S1的长度小于MAXLEN，部分字符将被舍弃
		for(i=S.length; i<MAXLEN; i++)
			S.ch[i]=S1.ch[i-S.length];
		S.length=MAXLEN;
	}
	return true;
}

/*比较子串,比较串S和串S1是否相等*/
bool CompareString(SString &S,SString &S1) {
	int i=0,flag=0;
	while(S.ch[i]!='\0'&&S1.ch[i]!='\0') {	//当串没到尾部时循环一直执行下去
		if(S.ch[i]!=S1.ch[i]) {	//比较两个串对应位置的字符是否相同
			flag=1;		//如果不相同，则将flag置为1
			break;
		} else	//否则i++
			i++;
	}
	if(S.length==S1.length&&flag==0) {
		printf("两个串相等！");
		return true;	//相等
	} else {
		printf("两个串不相等！");
		return false;	//不相等
	}
}

/*搜索子串,在串S中查找子串S1*/
bool IndexString(SString &S,SString &S1) {
	int i=0,j=0;
	while(i<S.length&&j<S1.length) {	//直到两个串的串尾时结束while循环
		if(S.ch[i]==S1.ch[j]) {	//若对应字符相同则继续比较下一个字符，i++、j++
			i++;
			j++;
		} else {	//否则进行下一次的字符串首字符比较
			i=i-j+1;
			j=0;
		}
	}
	if(j>=S1.length) {	//当串S中有串S1时，返回其首次出现的起始位置i，由于是数组下标i的值要减一
		printf("查找成功，该子串在主串中第一次出现的位置为%d",i-1);
		return true;
	} else {
		printf("查找失败，主串中没有该子串！");
		return false;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
  • 相关阅读:
    uniapp 版本检查更新
    YOLOv5如何训练自己的数据集
    手把手带你玩摄像头模组
    stm32--独立看门狗
    PowerBI_一分钟了解POWERBI计算组_基础运用篇（环同比分析）
    java基础巩固16
    谈谈数据治理与数据管理
    【OJ比赛日历】快周末了，不来一场比赛吗？ #09.09-09.15 #15场
    Cpolar+Inis结合在Ubuntu上打造出色的博客网站，快速上线公网访问
    PostgreSQL按月计算每天值的累加
  • 原文地址：https://blog.csdn.net/qq_43085848/article/details/125559206