【数据结构】串的基本定义及操作-Toy模板网

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

🎇[数据结构]串的基本定义及操作🎇

🌈积薪高于山，焉用先后别 🌈

串的基本操作,数据结构,数据结构,串,c++

🌟 正式开始学习数据结构啦~此专栏作为学习过程中的记录🌟

🍰一.串的定义及实现

概念熟记:

串是由0个或多个字符组成的有限的序列，记作 $S='a_1a_2...a_n'$ ，其中，当 $n = 0$ 时表示空串

串中任意多个连续的字符组成的子序列称为子串，包含子串的串称为主串

若两个串的长度相等且每一个元素都相同，则这两个串相等

串的基本操作,数据结构,数据结构,串,c++

✅ 比较线性表和串：

在逻辑结构上：串和线性表即为相似，区别仅为串的数据对象为字符集（如：数字，英文，中文，符号等）
在操作上：串和线性表的操作大有不同，主要体现在操作对象上：
$①$ 线性表的操作对象一般为单个元素
$②$ 串的操作对象一般为子串

串的基本操作,数据结构,数据结构,串,c++

🎯 怎么理解操作对象为子串？
因为往往需要多个字符才能表达出完整的实际意义，比如： $^{'} w or d^{'}$ ，若把他们拆解为 ${'w','o','r','d'\}$ ，并不能很好地体现它的实际含义，中文也类似，一个汉字也难以体现，所以将他们看做是一个整体来处理，与单个元素不同

🍰二.串的实现

🚀1.串的存储方式

🔆1.顺序存储

顺序存储，即用一片连续的内存空间存储字符串序列

//静态存储
#define Maxsize 50

typedef struct {
	char ch[Maxsize]; //字符串数组
	int len;
}SString;

💊注意：当串的长度超过最大长度时，串会被截断，也就是之后的字符将不会保留

串的表示方式：

✳️字符从数组下标为0的位置开始存放，长度单独开辟一个变量空间存储:

串的基本操作,数据结构,数据结构,串,c++

优点：长度变量 $l e n g t h$ 为 $in t$ 型变量，可以存放的数据范围大；
缺点：字符的位置与下标不对齐

✳️数组的首位置用len填充

优点：字符位置与数组下标对齐
缺点：此时的长度变量 $l e n g t h$ 只能为 $c ha r$ 类型，若长度 $> 255$ ，则会溢出，无法记录

✳️在字符串数组的后面添加一个结束标志’\0’

串的基本操作,数据结构,数据结构,串,c++

优点：不用单独存放长度变量，到结束标志符’\0’时自动结束
缺点：若要频繁使用长度时，每一次都需要遍历得到长度，效率低

✅首元素不存放，从下标为1开始，且单独开辟空间存放长度变量

串的基本操作,数据结构,数据结构,串,c++

优点：既可以满足数组下标与字符位置对齐，又可以保证变量足够表示长度

🔆2.堆存储

堆分配存储依然需要开辟一片连续的存储单元去存放字符串数组，但不同的是，他们的 存储空间是在使用过程中动态分配获得的

#include<iostream>
using namespace std;

typedef struct {
	char *ch; //字符串数组
	int len;
}HString;

🔆3.块链存储

类似地，串也可以用链式存储，由于串的特殊性，每个元素只有一个字符，因此，我们可以构造每个结点，既可以存放一个字符，也可以存放多个字符，则将每个结点称为块，整个链表称为块链结构

串的基本操作,数据结构,数据结构,串,c++

由于指针占4B，每一个字符占1B，因此，我们可以存放四个结点，尽可能降低存储密度

#include<iostream>
using namespace std;

typedef struct {
	char ch[4]; //字符串数组,每个结点存多个字符
	struct StringNode *next;
}StringNode,*String;

🚀2.串的基本操作

🔆1.串的初始化

将字符串数组的长度设为0，实现逻辑上的空串

void InitString(SString& S) {
	S.len = 0; //逻辑上的初始化
}

🔆2.求子串

串的基本操作,数据结构,数据结构,串,c++

bool SubString(SString& Sub, SString S, int pos, int len) { //Sub为子串，S为主串
	if (pos + len - 1 > S.len) //如果求的子串长度比总长度要大，则返回
		return false;
	for (int i = pos; i <= pos + len - 1; i++) {
		Sub.ch[i - pos + 1] = S.ch[i]; //第一个元素不存
	}
	Sub.len = len;
	return true;
}

🔆3.比较串

串的基本操作,数据结构,数据结构,串,c++

int StrCompare(SString S, SString T) {
	for (int i = 1; i <= S.len && i <= T.len; i++) { //同时在两个串长以内
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i]; //返回该元素的ASCII差值
	}
	return S.len - T.len; //如果扫描过的字符全部相同，则长的更大
}

🔆4.定位串

串的基本操作,数据结构,数据结构,串,c++

int Index(SString S, SString T) { //定位子串T在主串S中的位置
	int i = 1, n = S.len, m = T.len;
	SString sub; //记录子串
	while (i <= n - m + 1) {
		SubString(sub, S, i, m); //求子串
		if (StrCompare(sub, T) != 0)  //每一次都比较子串和T，如果子串不等于T，继续遍历下一个子串
			++i;
		else
			return i;
	}
	return 0;
}

🔆5.串的赋值

将 $c ha rs$ 的值赋值给 $S$ 中的字符串数组

注意：由于字符串是以’\0’结束的，所以可以以此作为判断条件

void StrAssign(SString& S, char chars[]) {
	int len = strlen(chars);
	for (int i = 1; i <= len; i++) {
		if (chars[i-1] != '\0')
		{
			S.ch[i] = chars[i-1];
			S.len++;
		}
	}
}

完整代码实现：

#include<iostream>
#define Maxsize 50
#include<cstring>
using namespace std;

typedef struct {
	char ch[Maxsize]; //字符串数组
	int len;
}SString;

// 1.初始化
void InitString(SString& S) {
	S.len = 0; //逻辑上的初始化
}

//2.求子串
bool SubString(SString& Sub, SString S, int pos, int len) { //Sub为子串，S为主串
	if (pos + len - 1 > S.len) //如果求的子串长度比总长度要大，则返回
		return false;
	for (int i = pos; i <= pos + len - 1; i++) {
		Sub.ch[i - pos + 1] = S.ch[i]; //第一个元素不存
	}
	Sub.len = len;
	return true;
}

//3.比较串
int StrCompare(SString S, SString T) {
	for (int i = 1; i <= S.len && i <= T.len; i++) { //同时在两个串长以内
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i]; //返回该元素的ASCII差值
	}
	return S.len - T.len; //如果扫描过的字符全部相同，则长的更大
}


//4.定位
int Index(SString S, SString T) { //定位子串T在主串S中的位置
	int i = 1, n = S.len, m = T.len;
	SString sub; //记录子串
	while (i <= n - m + 1) {
		SubString(sub, S, i, m); //求子串
		if (StrCompare(sub, T) != 0)  //每一次都比较子串和T，如果子串不等于T，继续遍历下一个子串
			++i;
		else
			return i;
	}
	return 0;
}

//5.赋值
void StrAssign(SString& S, char chars[]) {
	int len = strlen(chars);
	for (int i = 1; i <= len; i++) {
		if (chars[i-1] != '\0')
		{
			S.ch[i] = chars[i-1];
			S.len++;
		}
	}
}

//6.输出
void Print(SString S) {
	for (int i = 1; i <= S.len; i++) {
		cout << S.ch[i];
	}cout << endl;
}


int main() {
	SString S, T;
	InitString(S);
	InitString(T);

	char s[] = "yanruixiaobao";
	char t[] = "ruixiao";

	StrAssign(S, s);
	StrAssign(T, t);

	//打印
	cout << "串S和T为：" << endl;
	Print(S);
	Print(T);

	cout << "子串T在S中的位置为:" << Index(S, T) << endl;

	system("pause");
	return 0;
}