【数据结构】串（String）

news/2024/10/21 11:26:39/

文章目录

  • 基本概念
  • 顺序存储结构
    • 比较当前串与串s的大小
    • 取子串
    • 插入
    • 删除
    • 其他
      • 构造函数
      • 拷贝构造函数
      • 扩大数组空间。
      • 重载+
      • 重载=
      • 重载==
      • 重载[]
      • 重载>>
      • 重载<<
  • 链式存储结构
    • 链式存储结构
    • 链块存储结构
  • 模式匹配
    • 朴素的模式匹配算法(BF算法)
    • KMP算法
      • 字符串的前缀、后缀和部分匹配值
      • next数组
      • nextVal数组
      • KMP代码实现
  • 扩展与提高
  • 参考资料

基本概念

从数据结构角度讲，串属于线性结构。
特点：（1）串中的一个元素是一个字符 （2）操作对象是一组元素

字符串和普通数组的区别？
串的元素是字符，要在最后一个字符的后面多存放’\0’，作为结束符

串的长度：一个串所包含的字符的个数n
空串：串的长度=0。串内没有任何字符。
空格串：有空格字符组成的串。
子串：串中任意个连续字符组成的子序列
主串：包含子串的串
模式匹配（子串定位）：查找子串在主串中第一次出现的位置

class String
public:String(const char *str = NULL);		//构造函数String(const String &str);			//拷贝构造函数~String(){ delete []data;}			//析构函数int capacity( const { return maxSize;}	//最大存储容量int size()const {return curLength;} 	//求串长度bool empty() const {return curLength==0;}	//判空int compare(const String &s) const;			//比较当前串和串s的大小String subStr(int pos, int num)const;	//从pos位置开始取长度为num的子串String &insert(int pos,const String &s);	//在pos位置插入串SString &erase(int pos, int num);			//删除从 pos开始的 num个字符const char* toCharStr() const{ return data;}	// 获取字符数组 dataint bfFind(const String &s, int pos = 0) const;	// 朴素的模式匹配算法	int kmpFind(const String &t, int pos= 0);	// 改进的模式匹配算法void getNext(const String &t, int *next)；	//获取 next数组void getNextVal (const String&t, int *nextVal)；// 获取 nextVal 数组bool operator==(const String &str)const; 	//重载==，判断两个串是否相等String& operator+(const String &str);	//重载+，用于串的连接String& operator=(const String &str); 	//重载=，用于串间赋值char& operator[] (int n) const;	//重载[]，通过下标运算取串中字符friend istream& operator>>(istream &cin, String &str);//重载>>，用于输入串friend ostream& operator<<(ostream &cout, String &str)；// 重载<<，用于输出串private:char *data;		//存储串int maxSize；	//最大存储容量int curLength;	//串的长度void resize(int len);	//扩大数组空间
}:class outOfRange:public exception {		//用于检查范围的有效性
public: const char* what()const throw(){return "ERROR!OUT OF RANGE. \n";}
};class badSize:public exception {		//用于检查长度的有效性
public:const char* what()const throw(){return "ERROR! BAD SIZE.\n";}
};

顺序存储结构

比较当前串与串s的大小

两个串相等，返回0; 当前串大，返回1；当前串小，返回-1。

int String::compare(const String &s) const{int i = 0;while(s.data[i] != '\0' || this->data[i] !='\0'){if（this->data[i] > s.data[i])return 1;else if (this->data[i] < s.data[i])return -1:i++;}if (this->data[i] =='\0' && s.data[i] !='\0')	//s有剩余元素return -1;else if (s.data[i] =='\0' && this->data[i] !='\0')return 1;				//this有剩余元素return 0;							//均无剩余元素
}

上述代码中的函数体可替换成return strcmp( data , s.toCharStr() );语句，即调用头文件中的库函数strcmp 实现串比较。

取子串

从主串中下标为pos的位置开始取长度为num的子串
当poscurLength或num0时，取到的子串为空串
当 num > curLength - pos时，修改 num =curLengh-pos

String String :: subStr(int pos, int num)const{int i;String tmp("");if (pos > curLength || pos < 0 )throw outOfRange():if (num < 0) throw badSize();	// num<O，抛出异常if (num > curLength - pos)		//num大于从pos开始到串尾的元素个数num = curLength - pos;		// 修改 num的值delete []tmp.data;				//释放 tmp原来的存储空间tmp.maxSize = tmp.curLength = num;tmp.data = new char[num+1];		//申请大小为num+1的存储空间for (i=0; i<num; i++){		//长度为num的子串赋值给tmptmp.data[i]=data[pos+i];tmp.data[i] ='\0';return tmp;
}

插入

在当前串的pos位置插入串s。

String & String::insert(int pos, const String &s){if (pos > curLength || pos < 0)	// pos 合法范围是[O..curLength]throw outOfRange();		//抛出异常if(curLength+s.curLength > maxSize)		//空间不够resize(2*(curLength+s.curLength));	//扩大数组空间for (int i = curLength; i >= pos: i--)	//下标在[curLength..pos]范围内的元素data[i+s.curLength]=data[i];		//往后移动s.curLength,包括`\0`for (int j = 0; j < s.curlength; j++) 	//存储s中的字符data[pos+j] = s.data[j];curLength += s.curLength;	//修改串的长度return *this;
}

删除

在当前串中删除从pos位置开始的长度为num的子串

String & String::erase(int pos, int num){if (pos < 0 || pos > curLength-1)	//合法的删除位置为[0..curLength-1]throw outOfRange();if(num < 0) throw badSize();		//num<0 抛出异常if (num > curLength - pos)		//num大于从pos开始到串尾元素个数num = curLength-pos;			//修改 num的值for (int j = pos+num; j<=curLength; j++)//下标在[posfnum curLength]内的元素data[j-num]= data[j];		//向前移动num，包括'\0'curLength -= num;				//修改串的长度return *this;}

其他

构造函数

String::String(const char *str) {maxSize = 2*strlen(str);data = new char [maxSize + 1];strcpy_s(data, maxSize+1, str);curLength = strlen(data);}

strcpy_s是一个字符串复制函数，它接受一个目标数组、目标数组的大小和一个源字符串作为参数，并防止缓冲区溢出。
strlen() 用于计算一个以空字符（即 ‘\0’）结尾的字符串的长度。这个函数返回的是字符串中字符的个数，不包括终止的空字符。

拷贝构造函数

String::String(const String &str){maxSize = str. maxSize;data = new char[maxSize + 1];strcpy_s(data, maxSize+1, str.toCharStr());curLength =str.curLength;}

toCharStr()是成员函数

扩大数组空间。

void String::resize(int len){maxSize = len;	//修改数组的最大容量为1enchar *temp = new char[maxSize + 1]; strcpy_s(temp, maxSize+1, data);delete []data;data=temp;
}

重载+

用于串的连接。

String& String::operator+(const String &str){if( maxSize < curLength + str.size());	//加上str后，数组空间不够了resize( 2*(curLength+str.size()) );strcat_s(data, maxSize+1, str.data);curlength += str.curlength;return *this;
}

strcat_s是一个字符串拼接函数，用于将源字符串追加到目标字符串的末尾。strcat_s(目标字符的指针, 字符串缓冲区的大小, 源字符的指针);

重载=

用于串赋值。

String& String::operator=(const String &str){if(this == &str) return *this;	//当前串和str是同一个串delete []data;		//释放原空间maxSize = str.maxSize;data = new char[maxSize + 1];	//重新申请一块新的存储空间strcpy_s(data, maxSize+1,str.toCharStr());curLength =str.curLength;return *this;
}

串的赋值运算会改变原有的串值，为了避免内存泄漏，最好释放原空间后再重新中新的存储空间。

重载==

用于判断两个串是否相等。

bool String::operator==(const String &str) const{if (curLength != str.curLength) return false;return strcmp(data,str.data) ? false : true;	//调用cstring库的strcmp函数
}

重载[]

用于通过下标运算存取串中字符。

inline char& String::operator[](int n) const{if(n<0 || n>= curLength) throw outOfRange();		//下标越界时抛出异常else return data[n];
}

重载>>

用于输入串。

istream& operator>>(istream &cin, String &str){char *temp=new char[10000];		//申请临时空间cin >> temp;	str.maxSize = 2*strlen(temp);str.data = new char[str.maxSize +1];strcpy _s(str.data, str.maxSize+1, temp);str.curLength=strlen(temp);delete []temp;return cin;
}

重载<<

用于输出串。

ostream& operator<<(ostream &cout, String &str){cout << str.data;return cout;
}

链式存储结构

链式存储结构

因为一个元素即为一个字符，最简单的结构是再一个结点的数据域中存放一个字符。
但存储密度较低，存储密度=串值所占的存储单元数 / 实际分配的存储单元数
在这里插入图片描述

链块存储结构

一个结点的数据与中存放多个字符。
但插入和删除操作会在字符间大量的移动字符。
在这里插入图片描述

综上，一般串采用顺序存储结构来表现和实现

模式匹配

设有主串S和子串T，如果在主串S中找到一个与子串T相等的子串，则返回子串T第一次在主串S中出现的位置，即子串T的第1个字符 在主串S中的位置。
主串又称为目标串，子串又称为模式串

朴素的模式匹配算法(BF算法)

从主串S=“S0S1…Sn-1”的第一个字符开始与子串T=“T0T1…Tm-1”中的第一个字符进行比较。
若Si与Tj相等，则指示两个串的指针 i 和 j 后移，继续下一个字符的比较；
若Si与Tj不相等，则主串指针i回溯到上一次比较的起始位置的后一位（即i=i-j+1),而子串指针j回溯到第一个字符（即j=0)，继续下一个字符的比较。
若匹配成功，则返回子串的第一个字符在主串的位置；否则，返回-1.

时间复杂度：O（mn）*

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

int String::bfFind(const String &s, int pos) const{int i=0, j=0;if(curLength < s.curLength)return -1;while(i<curLength && j < s.curLength){if(data[i]==s.data[j])i++,j++;else{i=i-j+1;j=0;}}if(j>=s.curLength)return (i-s.curLength);elsereturn -1;
}

KMP算法

特点：主串无需回溯，主串指针一直往后移动，只有子串指针回溯。
时间复杂度：O(m+n)

在这里插入图片描述
如上图所示，此时KMP算法的关键问题变成了如何求K的值。为了计算每次失配时子串指针j回溯的位置k，KMP采用空间换时间的方式，申请一个与子串长度相同的整型数组next。

字符串的前缀、后缀和部分匹配值

要了解子串的结构，首先要弄清楚几个概念:前缀、后缀和部分匹配值。
前缀：除最后一个字符以外，字符串的所有头部子串
后缀指除第一个字符外，字符串的所有尾部子串
部分匹配值则为字符串的前缀和后缀的最长相等前后缀长度。

下面以’ababa '为例进行说明:

前缀后缀最长相等前后缀的长度
‘a’空集空集0
‘ab’{a}{b}0
‘aba’{a,ab}{a,ba}1，即{a}
‘abab’{a,ab,aba}{b,ab,bab}2，即{ab}
‘ababa’{a,ab,aba,abab}{a,ba,aba,baba}3，即{aba}

所以字符串’ababa’的部分匹配值为00123。

next数组

表示在匹配失败后子串可跳过的字符的总数。
next数组的求解方法：
首两位是0，1.后面的规律是：数值=n+1 (n为最长相等前后缀的长度)

下面以’abaabc '为例进行说明:

序号123456
模式串abaabc
next数组011223

有些版本是以-1,0开头，但计算思路都一样。相当于以0，1开头的数组元素全部减1

代码实现：

void String::getNext(const String &t, int *next){int i = 0, j = -1;next[0] = -1;while(i < t.curLength-1){if((j==-1 || (t[i]==t[j])){++i,++j;next[i]=j;}elsej=next[j];}
}

以主串S=“GoogleGooseGood”，子串="Good"为例，匹配过程如下：
在这里插入图片描述

nextVal数组

next数组的进一步优化。

nextVal数组的求解方法：
首位是0，剩下的根据next的找到对应序列的字母
若相等：根据next值找到对应的序列，=其序列的nextVal
若不同：nextVal=next

下面以’abaabc '为例进行说明:

序号123456
模式串abaabc
next数组011223
字母aabba
nextVal数组010213

1.先用next的值去对应序列的值，把字母填上。
2.若字母不等于模式串，如序列2，4，6，则nextVal=next
3.若字母等于模式串，根据next的数值找到相同的序号值，再找到这个序号的nextVal值，这个值即是要寻找的数值

以主串S=“aaabaaabaaaab”，子串="aaab"为例，匹配过程如下：
在这里插入图片描述

若使用next数组，第二次匹配时，i=3,j=0

void String::getNextVal(const String&t, int *nextVal){int i=0,j=-1;nextVal[0]=-1;while(i<t.curLength){if((j==-1 || (t[i]==t[j])){++i,++j;if(t[i] !=t[j])nextVal[i]=j;elsenextVal[i] = nextVal[j];}else j = nextVal[j];}
}

代码说明：getNextVal函数在getNext函数的基础上增加了对子串中字符t[i]和t[j]是否相等的判断，若t[i]==t[j]，则将nextVal[j]的值传递给nextVal[i].否则，与getNext函数一样，nextVal[i]=j

KMP代码实现

int String::kmpFind(const String &t, int pos){if(t.curLength == 0)return 0;if(curLength < t.curLength)return -1;int i=0,j=0;int *next=new int[t.curLength];getNext(t,next);while(i<curLength && j < t.curLength){if(i<curLength && j<t.curLength)i++,j++;else j=next[j];}	delete []next;if(j>=t.curLength)return (i-t.curLength);elsereturn -1;
}

扩展与提高

在C++中，C++ 标准库提供了 string 类类型，支持上述所有的操作，另外还增加了其他更多的功能。

编程时加入头文件：

#include<string>	//或者万能头文件#include<bits/stdc++.h>
using namespace std;

String函数：
用string定义s类

定义什么都可以，只要把s变成定义的字母就可以调用C++中的函数

具体使用方法为：

常见操作
s.resize(10)设置字符串长度为10
string s(“ABC”)构造字符串s的值为ABC
s.empty()判断字符串是否为空
s.length()或者s.size()求解字符串是否为空
s.begin()开始值
s.end()结尾值
查找（查找成功返回元素位置，失败返回-1）
s.find(‘A’)查找字符A
s.find(“ABC”)查找字符串ABC
s.find(‘A’,2)从位置2开始查找字符A
s.find(“ABCD”,1,2)从位置1开始，查找ABCD的前两个字符
s.rfind()从字符串尾部开始查找
插入
s.insert(2,3,‘A’)在下标为2的地方添加三个A
s.insert(2,“ABC”)在下标为2的地方添加字符串ABC
s.insert(2,“ABC”,1)在下标为2的地方添加ABC中的一个
s.insert(2,“ABCD”, 2，2)在下标为2的地方从字符串ABCD中位置2开始的2个字符
s.push_back(‘A’)在尾部添加字符A
复制
s1=s.substring(2)提取字符串s从2到尾部赋值给s1
s1=s.substring(2,3)提取字符串s从2开始三个字符赋值给s1
const char*s1=s.data()将string类转为字符串数组
s.copy(s1,2,3)将s中从第3个位置拷贝2个字符到s1中
比较(假设原字符串为ABCD)
s.compare(“ABCD”)相等返回0，大于原字符串返回1,小于返回-1
删除
s.erase(2)删除下标2以后的全部元素
s.erase(2,1))删除下标2以后的第一个元素
翻转
reverse(s.begin(),s.end())翻转所有字符串，即逆序输出
清空
s.assign(“ABC”)清空字符串，并置为ABC
s.assign(“ABC”,2)清空字符串，并置为ABC的前2个字符AB
s.assign(“ABC”,2，1)清空字符串，并置为ABC的从2开始的1个字符
s.assign(5，‘A’)清空字符串，并置为5个A
s.clear()清空字符串所有字符

参考资料

1.【图解数据结构】串全面总结
2.串的详细讲解


http://www.ppmy.cn/news/1435703.html

相关文章

C++ | Leetcode C++题解之第48题旋转图像

C++ | Leetcode C++题解之第48题旋转图像

题目&#xff1a; 题解&#xff1a; class Solution { public:void rotate(vector<vector<int>>& matrix) {int n matrix.size();// 水平翻转for (int i 0; i < n / 2; i) {for (int j 0; j < n; j) {swap(matrix[i][j], matrix[n - i - 1][j]);}}//…
阅读更多...
【24届数字IC秋招总结】正式批面试经验汇总9——飞腾

【24届数字IC秋招总结】正式批面试经验汇总9——飞腾

文章目录 一、飞腾-IC验证工程师1.1 面试问题&#xff08;验证部&#xff09;1.2 面试问题&#xff08;处理器核&#xff09; 一、飞腾-IC验证工程师 面试时间&#xff1a;9.27 1.1 面试问题&#xff08;验证部&#xff09; 1、自我介绍 2、实习做什么 3、AHB协议的内容 4、…
阅读更多...
DHCP的原理与配置

DHCP的原理与配置

一.了解DHCP服务 1. DHCP (Dynamic Host Configuration Protocol)动态主机配置协议 是由Internet工作小组设计开发的&#xff0c;专门用于为TCP/IP网络中的计算机自动分配TCP/IP参数的协议 DHCP协议采用的是UDP作为传输协议&#xff0c;是给网络内的客户机自动分配IP地址&…
阅读更多...
鸿蒙开发实例：【配置OpenHarmony SDK】

鸿蒙开发实例：【配置OpenHarmony SDK】

配置OpenHarmony SDK 在设置OpenHarmony应用开发环境时&#xff0c;需要开发者在DevEco Studio中配置对应的SDK信息。 说明&#xff1a; 请注意&#xff0c;OpenHarmony SDK版本精简了部分工具链&#xff0c;因此不适用于HarmonyOS应用开发。 前提条件 已下载并安装好DevEco …
阅读更多...
推荐3个视频转文字的工具

推荐3个视频转文字的工具

如果是长视频转文字的话&#xff0c;我会推荐你三个专业的能够将视频文字提取出来的工具&#xff0c;操作无门槛&#xff0c;转换出的文字准确率高&#xff0c;可以直接导出文字。 1.一键识别王 https://www.xunjiepdf.com/yijianshibiewang 专业的图片文字识别软件&#xff0…
阅读更多...
企业微信hook接口协议,根据手机号搜索联系人

企业微信hook接口协议,根据手机号搜索联系人

根据手机号搜索联系人 参数名必选类型说明uuid是String每个实例的唯一标识&#xff0c;根据uuid操作具体企业微信 请求示例 {"uuid":"3240fde0-45e2-48c0-90e8-cb098d0ebe43","phoneNumber":"1357xxxx" } 返回示例 {"data&q…
阅读更多...
随机森林计算指标重要性—从决策树到随机森林Python实现

随机森林计算指标重要性—从决策树到随机森林Python实现

文章目录 前言一、节点二、决策树2.1 案例分析——优良的水稻2.2 案例分析——家庭财富水平 三、随机森林三、Python代码实现3.1 关键问题3.1.1 节点的表示3.1.2 决策树的表示** 根节点划分左右子树的依据 **3.1.3 随机森林的构造与重要性的表示 3.2 节点类3.2 决策树类3.2.1 初…
阅读更多...
物联网网关硬件和云端分别实现了哪些功能？-天拓四方

物联网网关硬件和云端分别实现了哪些功能？-天拓四方

在物联网&#xff08;IoT&#xff09;的广阔领域中&#xff0c;物联网网关硬件和云端各自扮演着不可或缺的角色。它们通过一系列功能&#xff0c;共同确保物联网系统的顺畅运行&#xff0c;为各类设备提供稳定、高效的数据传输与处理服务。本文将详细解析物联网网关硬件和云端分…
阅读更多...
最新文章

Copyright @ 2022~2023