第四章 串--以下代码由C语言实现

  • 开发
  • 18

王道学习

4.1 知识框架

在这里插入图片描述

4.2 串的定义和实现

字符串简称串，计算机上非数值处理的对象基本都是字符串数据。我们常见的信息检索系统(如搜索引擎)、文本编辑程序(如 Word)、问答系统、自然语言翻译系统等，都是以字符串数据作为处理对象的。本章详细介绍字符串的存储结构及相应的操作。

4.2.1 串的定义

在这里插入图片描述
串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。在基本操作上，串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象，如查找、插入或删除某个元素等;而串的基本操作通常以子串作为操作对象，如查找、插入或删除一个子串等。
在这里插入图片描述

4.2.2 串的基本操作

在这里插入图片描述

4.2.3 顺序存储表示

在这里插入图片描述在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

//串--顺序存储--数组
#include <stdio.h>
#define MAXLEN 255

struct SString{
	//ch[0]不使用 
	char ch[MAXLEN];
	int length;
};

typedef struct SString SString;

/*
	初始化操作		 
*/
void initString(SString *sString){
	(*sString).length=0; 
}

/*
	注意：数组名作为函数参数，会自动转换为指针
	所以，写char chars[]与char *chars，道理相同 
	所以，需要额外传一个参数，来标识chars的长度
	数组名--首地址 
	
	赋值操作
		chars赋值给sString的ch  
	
	返回值
		1--成功
		0--失败 
*/
int strAssign(SString *sString,char *chars,int len){
	
	if(len-1>MAXLEN-1){
		return 0;
	}
	
	initString(sString);
	
	int i=0;
	for(;i<=len-1;i++){
		(*sString).ch[i+1]=chars[i];
		(*sString).length=(*sString).length+1;	
	} 
	
	return 1;
}

/*
	注意：数组名作为函数参数，会自动转换为指针
	所以，写char chars[]与char *chars，道理相同 
	所以，需要额外传一个参数，来标识chars的长度
	数组名--首地址 
	
	追加操作
		chars追加给sString的ch  
	
	返回值
		1--成功
		0--失败 
*/
int appendString(SString *sString,char *chars,int len){
	
	if(len-1>MAXLEN-1-(*sString).length){
		return 0;
	}
	
	int i=0;
	for(;i<=len-1;i++){
		(*sString).length=(*sString).length+1;
		(*sString).ch[(*sString).length]=chars[i];
	} 
	
	return 1;
}

/*
	复制操作
		sString的ch复制给t的ch 
	
	返回值
		1--成功
		0--失败 
	 
*/
int strCopy(SString *t,SString sString){

	int length=sString.length;
	int i=1;
	for(;i<=length;i++){
		(*t).ch[i]=sString.ch[i];
	}
	
	return 1;
	
}

/*
	判空操作
	
	返回值
		1--非空 
		0--空  
*/
int strEmpty(SString sString){
	
	if(sString.length>0){
		return 1;
	}else{
		return 0;
	}
	
} 

/*
	求串长 
*/
int strLength(SString sString){
	return sString.length;
}

/*
	清空操作 
*/ 
void clearString(SString *sString){
	(*sString).length=0;
}

/*
	销毁串操作--main运行结束，弹栈--自动销毁 
*/ 
void destoryString(SString *sString){
	(*sString).length=0;
}

/*
	拼接操作
		str1的ch与str2的ch拼接赋值给t的ch 
	
	返回值
		1--成功
		0--失败  
*/

int concat(SString *t,SString s1,SString s2){
	
	int len1=strLength(s1);
	int len2=strLength(s2);
	
	if(len1+len2>MAXLEN-1){
		return 0;
	}
	
	initString(t);
	
	int i=1;
	for(;i<=len1;i++){
		(*t).ch[i]=s1.ch[i];
		(*t).length=(*t).length+1;	
	}
	
	int j=1;
	for(;j<=len2;j++){
		(*t).length=(*t).length+1;	
		(*t).ch[(*t).length]=s2.ch[j];
	} 

  return 1;
	
}

/*
	求子串
		s的ch截取赋值给sub的ch
		
	返回值
		1--成功
		0--失败 
*/
int subString(SString *sub,SString s,int pos,int len){
	
	//子串范围越界
	if(pos+len-1>strLength(s)){
		return 0;
	}
	
	int i=pos;
	for(;i<pos+len;i++){
		(*sub).ch[i-pos+1]=s.ch[i];
	}
	(*sub).length=len; 
	
	return 1; 
}

/*
	字符串比较--s的ch与t的ch比较
	
	返回值
		正数--s>t
		0--相等
		负数--s<t 
*/
int strCompare(SString s,SString t){
	
	int len1=strLength(s);
	int len2=strLength(t);
	int i=1;
	for(;i<=len1&&i<=len2;i++){
		if(s.ch[i]!=t.ch[i]){
			return s.ch[i]-t.ch[i];
		}
	}
	
	return len1-len2;
}

/*
	定位操作
		若主串s中存在于串t值相同的子串，
		则返回主串s中第一次出现的位置
		否则函数值为0  
*/ 
int index(SString s,SString t){
	
	int i=1;
	int n=strLength(s);
	int m=strLength(t);
	
	SString sub;	 
	while(i<=n-m+1){
		subString(&sub,s,i,m);
		if(strCompare(s,sub)!=0){
			i++;
		}else{
			return i;
		}
	}
	
	return 0;
} 

/*
	输出串
	
	返回值
		1--成功
		0--失败  
*/
void printfSString(SString sString){
	
	int length=strLength(sString);
	
	if(length==0){
		return 0;
	} 
	
	printf("\n");
	int i=1;
	for(;i<=length;i++){
		printf("%c",sString.ch[i]);
	}
	
	//%s会输出ch[0] 
	//printf("%s",sString.ch);
	return 1;
}

int main(){
	SString sString;
	char str1[]="123";
	char str2[]="abc";
	initString(&sString);
	printf("%d\n",strLength(sString));
	printfSString(sString);

	
	return 0;
}
 

#include <stdio.h>
#define MAXLEN 255 

struct SString{
	char ch[MAXLEN];
	int length;
};

typedef struct SString SString;

void initString(SString *sString){
	sString->length=0;
}

int strAssign(SString *sString,char *chars,int len){
	if(len-1>MAXLEN-1){
		return 0;
	}
	
	initString(sString);
	
	int i=0;
	for(;i<=len-1;i++){
		sString->ch[i+1]=chars[i];
		sString->length=sString->length+1;	
	}
	
	return 1;
	 
}

int appendString(SString *sString,char *chars,int len){
	if(len-1>MAXLEN-1-sString->length){
		return 0;
	}
	
	int i=0;
	for(;i<=len-1;i++){
		sString->length=sString->length+1;
		sString->ch[sString->length]=chars[i];
	}
	
	return 1;
}

int strCopy(SString *t,SString sString){
	int length=sString.length;
	int i=1;
	for(;i<=length;i++){
		t->ch[i]=sString.ch[i];
	}
	
	return 1;
}

int strEmpty(SString sString){
	if(sString.length>0){
		return 1;
	}else{
		return 0;
	}
}

int strLength(SString sString){
	return sString.length;
}

void clearString(SString *sString){
	sString->length=0;
}

void destoryString(SString *sString){
	sString->length=0;
}

int concat(SString *t,SString s1,SString s2){
	int len1=strLength(s1);
	int len2=strLength(s2);
	
	if(len1+len2>MAXLEN-1){
		return 0;
	}
	
	initString(t);
	
	int i=1;
	for(;i<len1;i++){
		t->ch[i]=s1.ch[i];
		t->length=t->length+1;
	} 
	
	int j=1;
	for(;i<=len2;j++){
		t->length=t->length+1;
		t->ch[t->length]=s2.ch[j];
	}
	
	return 1;
}

int subString(SString *sub,SString s,int pos,int len){
	if(pos+len-1>strLength(s)){
		return 0;
	}
	
	int i=pos;
	for(;i<pos+len;i++){
		sub->ch[i-pos+1]=s.ch[i];
	}
	
	sub->length=len;
	
	return 1;
}

int strCompare(SString s,SString t){
	int len1=strLength(s);
	int len2=strLength(t);
	int i=1;
	for(;i<=len1&&i<=len2;i++){
		if(s.ch[i]!=t.ch[i]){
			return s.ch[i]-t.ch[i];
		}
	}
	
	return len1-len2;
}

int index(SString s,SString t){
	int i=1;
	int n=strLength(s);
	int m=strLength(t);
	
	SString sub;
	while(i<=n-m+1){
		subString(&sub,s,i,m);
		if(strCompare(s,sub)!=0){
			i++;
		}else{
			return i;
		}
	}
	
	return 0;
}

void printfSString(SString sString){
	
	int length=strLength(sString);
	
	if(length==0){
		return 0;
	} 
	
	printf("\n");
	int i=1;
	for(;i<=length;i++){
		printf("%c",sString.ch[i]);
	}
	
	return 1;
	
}

int main(){
	
	SString sString;
	char str1[]="123";
	char str2[]="abc";
	initString(&sString);
	printf("%d\n",strLength(sString));
	printfSString(sString);
	
	return 0;
}

4.2.4 链式存储表示

在这里插入图片描述

4.3 串的模式匹配

4.3.1 简单的模式匹配算法

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

//串--顺序存储--数组
#include <stdio.h>
#define MAXLEN 255

struct SString{
	//ch[0]不使用 
	char ch[MAXLEN];
	int length;
};

typedef struct SString SString;

/*
	初始化操作		 
*/
void initString(SString *sString){
	(*sString).length=0; 
}

/*
	注意：数组名作为函数参数，会自动转换为指针
	所以，写char chars[]与char *chars，道理相同 
	所以，需要额外传一个参数，来标识chars的长度
	数组名--首地址 
	
	赋值操作
		chars赋值给sString的ch  
	
	返回值
		1--成功
		0--失败 
*/
int strAssign(SString *sString,char *chars,int len){
	
	if(len-1>MAXLEN-1){
		return 0;
	}
	
	initString(sString);
	
	int i=0;
	for(;i<=len-1;i++){
		(*sString).ch[i+1]=chars[i];
		(*sString).length=(*sString).length+1;	
	} 
	
	return 1;
}

/*
	求串长 
*/
int strLength(SString sString){
	return sString.length;
}


/*
	定位操作
		若主串s中存在于串t值相同的子串，
		则返回主串s中第一次出现的位置
		否则函数值为0  
*/ 
int indexFirst(SString s,SString t){
	
	int k=1;
	int i=k,j=1;
	
	while(i<=strLength(s)&&j<=strLength(t)){
		if(s.ch[i]==t.ch[j]){
			i++;
			j++;
		}else{
			k++;
			i=k;
			j=1;
		} 
	}
	
	if(j>strLength(t)){
		return k;
	}else{
		return 0;	
	}	

}

/*
	定位操作
		若主串s中存在于串t值相同的子串，
		则返回主串s中第一次出现的位置
		否则函数值为0  
*/ 
int indexSecond(SString s,SString t){
	
	int i=1,j=1;
	
	while(i<=strLength(s)&&j<=strLength(t)){
		if(s.ch[i]==t.ch[j]){
			i++;
			j++;
		}else{
			i=i-j+2;
			j=1;
		} 
	}
	
	if(j>strLength(t)){
		return i-strLength(t);
	}else{
		return 0;	
	}	

} 

/*
	输出串
	
	返回值
		1--成功
		0--失败  
*/
void printfSString(SString sString){
	
	int length=strLength(sString);
	
	if(length==0){
		return 0;
	} 
	
	printf("\n");
	int i=1;
	for(;i<=length;i++){
		printf("%c",sString.ch[i]);
	}
	
	//%s会输出ch[0] 
	//printf("%s",sString.ch);
	return 1;
}



int main(){
	SString sString;
	char str1[]="123";
	char str2[]="abc";
	initString(&sString);
	printf("%d\n",strLength(sString));
	printfSString(sString);

	
	return 0;
}

#include <stdio.h>
#define MAXLEN 255

struct SString{
	char ch[MAXLEN];
	int length;
};

typedef struct SString SString;

void initString(SString *sString){
	sString->length=0;
}

int strAssign(SString *sString,char *chars,int len){
	if(len-1>MAXLEN-1){
		return 0;
	}
	
	initString(sString);
	
	int i=0;
	for(;i<=len-1;i++){
		sString->ch[i+1]=chars[i];
		sString->length=sString->length+1;	
	}
	
	return 1;
}

int strLength(SString sString){
	return sString.length;
}

int indexFirst(SString s,SString t){
	int k=1;
	int i=k,j=1;
	
	while(i<=strLength(s)&&j<=strLength(t)){
		if(s.ch[i]==t.ch[j]){
			i++;
			j++;
		}else{
			k++;
			i=k;
			j=1;
		}
	}
	
	if(j>strLength(t)){
		return k;
	}else{
		return 0;
	}
}

int indexSecond(SString s,SString t){
	int i=1,j=1;
	
	while(i<=strLength(s)&&j<=strLength(t)){
		if(s.ch[i]==t.ch[j]){
			i++;
			j++;
		}else{
			i=i-j+2;
			j=1;
		}
	}
	
	if(j>strLength(t)){
		return i=strLength(t);
	}else{
		return 0;
	}
}

void printfSString(SString sString){
	
	int length=strLength(sString);
	
	if(length==0){
		return 0;
	} 
	
	printf("\n");
	int i=1;
	for(;i<=length;i++){
		printf("%c",sString.ch[i]);
	}
	
	//%s会输出ch[0] 
	//printf("%s",sString.ch);
	return 1;
}

int main(){
	
	SString sString;
	char str1[]="123";
	char str2[]="abc";
	initString(&sString);
	printf("%d\n",strLength(sString));
	printfSString(sString);
	
	return 0;
}

4.3.2 改进的模式匹配算法——KMP算法

1、字符串的前缀、后缀和部分匹配值
要了解子串的结构，首先要弄清楚几个概念:前缀、后缀和部分匹配值。前缀指除最后一个字符以外，字符串的所有头部子串;后缀指除第一个字符外，字符串的所有尾部子串;部分匹配值则为字符串的前缀和后缀的最长相等前后缀长度。下面以’ ababa '为例进行说明:
在这里插入图片描述2、KMP算法介绍
由D.E.Knuth，J.H.Morris和V.R.Pratt提出，因此称为KMP算法
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
3、求next数组
在这里插入图片描述
在这里插入图片描述4、KMP算法性能分析
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

4.3.2 KMP算法的进一步优化

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

4.3.3 本节试题精选


在这里插入图片描述
在这里插入图片描述

阅读全部

相关推荐

  9. 第四章：c语言中的循环结构

    2024-03-25 02:24:02       14 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-03-25 02:24:02       19 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-03-25 02:24:02       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-03-25 02:24:02       19 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-03-25 02:24:02       20 阅读

热门阅读

  4. SpringMVC

    2024-03-25 02:24:02       24 阅读

  5. MySQL锁

    2024-03-25 02:24:02       18 阅读

  12. DFS进阶——混境之地5

    2024-03-25 02:24:02       18 阅读

  15. 【字节序】

    2024-03-25 02:24:02       18 阅读

  16. 优化大型语言模型表现的策略与方法

    2024-03-25 02:24:02       20 阅读

  17. C++函数重载

    2024-03-25 02:24:02       19 阅读

  19. LeetCode 678：有效的括号字符串 ← 贪心算法

    2024-03-25 02:24:02       19 阅读

  23. 目前可以运行的完整依赖

    2024-03-25 02:24:02       20 阅读

  26. 5.5.3、【AI技术新纪元：Spring AI解码】Milvus 向量数据库配置与使用指南

    2024-03-25 02:24:02       22 阅读

  27. Milvus 基本概念

    2024-03-25 02:24:02       18 阅读

  28. qualcomm导出分区之(UFS篇)

    2024-03-25 02:24:02       19 阅读