文章目录
- 基本概念
- 顺序存储结构
- 比较当前串与串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位置插入串S
String &erase(int pos, int num); //删除从 pos开始的 num个字符
const char* toCharStr() const{ return data;} // 获取字符数组 data
int 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的子串赋值给tmp
tmp.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; //修改数组的最大容量为1en
char *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);
else
return -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 '为例进行说明:
序号 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
模式串 | a | b | a | a | b | c |
next数组 | 0 | 1 | 1 | 2 | 2 | 3 |
有些版本是以-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;
}
else
j=next[j];
}
}
以主串S=“GoogleGooseGood”,子串="Good"为例,匹配过程如下:
nextVal数组
next数组的进一步优化。
nextVal数组的求解方法:
首位是0,剩下的根据next的找到对应序列的字母
若相等:根据next值找到对应的序列,=其序列的nextVal
若不同:nextVal=next
下面以’abaabc '为例进行说明:
序号 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
模式串 | a | b | a | a | b | c |
next数组 | 0 | 1 | 1 | 2 | 2 | 3 |
字母 | a | a | b | b | a | |
nextVal数组 | 0 | 1 | 0 | 2 | 1 | 3 |
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;
else
nextVal[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);
else
return -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.串的详细讲解