前言

这期我们一起深入学习初级数据结构——串，数据结构中的串（String）是一种非常常见且基础的数据类型，它由零个或多个字符组成的有限序列。以下是对数据结构串的详细分析：

一、串的定义

串是由零个或多个字符组成的有限序列，一般记为S=“a1a2…an”（n>=0），其中S是串名，双引号（或单引号）括起来的字符序列是串的值，ai（1<=i<=n）可以是字母、数字或其他字符，n称为串的长度。当n=0时，称为空串。此外，只包含空格的串被称为空格串，它与空串的区别在于空格串有内容有长度。

二、串的存储结构

串的存储结构主要有以下几种：

定长顺序存储结构：为每个串变量分配一个固定长度的存储区，即定长数组。这种存储方式需要预定义一个最大串长，当实际串长超过这个预定义长度时，会发生截断。

堆分配存储结构：仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。这种方式可以克服定长顺序存储结构中串长受限的弊端。

链式存储结构：类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性（每个元素只有一个字符），在具体实现时，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。

三、串的基本操作

串的基本操作主要包括以下几种：

1.赋值操作：为串变量赋值。
2.复制操作：由串S复制得到串T。
3.判空操作：判断串是否为空。
4.比较操作：比较两个串的大小。
5.求串长操作：返回串的长度。
6.求子串操作：返回串S的第pos个字符起长度为len的子串。
7.串联接操作：用T返回由S1和S2联接而成的新串。
8.定位操作：若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则返回0。
9.清空操作：清空串的内容。
10.销毁串操作：销毁串并释放其占用的存储空间。

四、串的模式匹配

串的模式匹配是串操作中的一个重要问题，它求的是子串（常称模式串）在主串中的位置。常见的模式匹配算法有：

暴力匹配算法：一种简单直接的字符串匹配算法。它的基本思想是从主串的第一个字符开始，与模式串进行逐个字符比较，若匹配失败，则将模式串右移一位，继续比较，直到找到匹配或者主串被遍历完为止。该算法的时间复杂度为O(n*m)，其中n为主串的长度，m为模式串的长度。

KMP算法：一种高效的字符串匹配算法。它通过预处理模式串，利用模式串中的信息在匹配失败时尽可能地减少比较次数，从而提高匹配效率。KMP算法的核心思想是利用模式串内部的信息，在匹配失败时根据已匹配的部分，选择合适的位置进行模式串的移动。算法的关键在于部分匹配表（Next数组），它记录了模式串每个位置之前的子串中有多大长度的相同前缀和后缀。匹配过程中，当文本串的某个字符与模式串的对应字符不匹配时，利用Next数组确定模式串的移动位置，从而减少不必要的比较。KMP算法的时间复杂度为O(n+m)。

五、串的应用

串在编程中广泛应用，用于处理文本数据、用户界面、文件操作、网络通信等各种任务。它们也用于数据存储和传输。例如，在文本编辑器中，串操作被用于实现文本的查找、替换、插入和删除等功能；在搜索引擎中，串匹配算法被用于实现关键词的快速检索；在数据库系统中，串操作被用于实现数据的存储、检索和更新等功能。

六、c++代码模版

#include<iostream>
#include<cstring>
#include<string>

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
using namespace std;

class String {
private:
	char* str;
	size_t length;//表示字符串长度
public:
	String();//无参构造函数
	String(const String& s);//拷贝构造函数
	String(const char* s);//有参构造函数
	~String();//析构函数
	size_t getLength()const;
	char operator[] (size_t index) const;//运算符重载[]
	String& operator=(const String& s);//运算符重载=
	bool operator==(const String& s)const;//布尔类型==
	bool operator!=(const String& s)const;//布尔类型!=
	String copy() const;//字符串的拷贝
	String operator+(const String& s)const;
	bool empty();
	friend ostream& operator<<(ostream& out, const String& s);//运算符重载<<
};

String::String() {//构造一个空串的函数
	length = 0;//字符串长度为0
	str = new char[1];//申请一个char类型的内存空间
	str[0] = '\0';//'\0'这个代表空串
}

String::String(const String& s) {
	length = s.length;
	str = new char[length + 1];
	strcpy(str, s.str);
}

String::String(const char* s) {
	length = strlen(s);
	str = new char[length + 1];
	strcpy(str, s);
}

String::~String() {
	delete[]str;
}

size_t String::getLength() const {
	return length;
}

char String::operator[] (size_t index) const {
	return str[index];
}

String& String::operator=(const String& s) {//这个操作其实就是赋值操作
	if (this != &s) {//如果当前对象不等于传参对象
		delete[]str;//如果发现s不等于这个类本身的地址那么就释放掉str避免内存泄漏
		length = s.length;
		str = new char[length + 1];
		strcpy(str, s.str);
	}
	return *this;
}

bool String::operator==(const String& s) const {
	return strcmp(str, s.str) == 0;//如果这两个对象值相等就等于0
}

bool String::operator!=(const String& s) const {
	return strcmp(str, s.str) != 0;
}

String String::copy() const {
	String s = *this;
	return s;
}

String String::operator+(const String& s) const {
	String ret;
	ret.length = this->length + s.length;
	ret.str = new char[ret.length + 1];
	strcpy(ret.str, str);
	strcat(ret.str, s.str);//将s拷贝到ret的结尾
	return ret;
}

bool String::empty() {
	return length == 0;
}

ostream& operator<<(ostream& out, const String& s) {
	out << s.str;//out代表输出流的类型，将s对内容传到out的输出流中，函数返回输出流
	return out;
}

int main() {
	String s = "1234";
	String s1 = "567";
	cout << s[0] << endl;
	s = s + s1;
	cout << s << endl;
	cout << (s == s1) << endl;
	cout << (s != s1) << endl;
	cout << s.empty() << endl;
	return 0;
}

七、经典例题

1.汉字统计

（蓝色字体点进去看原题）

代码题解

#include<iostream>
#include<string>
using namespace std;


int main() {
	int t;
	cin >> t;
	char s[500];
	getchar();//把空格也算入字符
	while (t--) {
		gets_s(s);
		int len = strlen(s);
		int cnt = 0;
		for (int i = 0; i < len; i++) {
			if (s[i] < 0)cnt++;
		}
		cout << cnt / 2 << endl;//汉字占两个字节
	}

	return 0;
}

2.查找最大元素

代码题解

#include<iostream>
#include<string>
using namespace std;


int main() {
	string s;
	while (cin >> s) {
		int max = 0;
		string ret;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] > max)max = s[i];
		}
		for (int i = 0; i < s.size(); i++) {
			ret += s[i];
			if (s[i] == max)ret += "(max)";
		}
		cout << ret << endl;
	}

	return 0;
}

3.首字母变大写

代码题解

#include<iostream>
#include<cstring>
#include<string>
using namespace std;


int main() {
	char s[110];
	while (gets_s(s)) {
		int len = strlen(s);
		for (int i = 0; i < len; i++) {
			if (i == 0  || s[i - 1] == ' ') {
				if (s[i] != ' ') {
					if (s[i] >= 'a' && s[i] <= 'z') {
						s[i] -= 'a';
						s[i] += 'A';
					}
				}
			}
		}
		printf("%s\n", s);
	}

	return 0;
}

八、总结

综上所述，数据结构串是一种非常重要且基础的数据类型，在编程和算法设计中具有广泛的应用和重要的地位。

结语

通过此次学习相信大家已经对串有了更深刻的理解，希望大家多刷题巩固知识点，下期我会更新串的题库。

想看更多内容可以关注我，看我作品，关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家