数据结构（字符串）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
字符串简称串由零个或多个字符组成的有限序列一般记为s＝“a0 a1a2…an-1”,n≥0。其中s称作串名用双引号括起来的字符序列是串的值。字符ai0≤i≤n-1可以是字母、数字或其它字符n为串的长度。
如a=“SHANGHAI”a为串名串值为SHANGHAI串长度为8。
相关概念
- 空串串的长度为零但仍然为一个串。
- 空格串由一个或一个以上的空格组成的串串的长度为空格的个数。
- 单字符串串中只有一个字符串长度为1。
- 串相等当且仅当两个串长度相同且对应位置上的字符完全相同。
- 子串一个串中任意个连续的字符组成的子序列称为该串的子串子串在主串中的位置以子串的第一个字符在主串中的字符位置来表示。
- 主串包含子串的串称为主串。
如“”为空串“ ”为长度为1的空格串如果
a =“SHANDONG PROVINCE”、b =“SHANDONG”则b是子串、a为主串、b在a中的位置为0。
串的存储
顺序及链式两种存储方式
顺序方式字符序列在连续的存储空间中依次连续地存放
链式方式串中每个字符作为一个结点独立地存放在不连续的存储空间中。
链式存储
考虑以上因素在多数情况下串的存储采用顺序存储最为常见。
顺序存储一般分静态存储和动态存储两种方式。
比如当结果串存储空间大小为10时若将“SHANGHAI CITY”赋值给结果串则结果串串值为“SHANGHAI ”串长度为9最后1个空间留给串结束符’\0’。
常见错误
对于字符串”ok”的存储两个字符加上一个结束标志字符’\0’共占用了3个字节。常见错误是把该字符串长度计为3应该是2结束符不算入内。
串的基本操作
如 “SHANGHAI”和“SHANGHAI”相等
“SHANGHAI”和 “SHANGHAAI ”不等。
如t =“SHANGHAI”, s=“JIAOTONG”。连接t和s即操作t+=s之后得到字符串t =“SHANGHAIJIAOTONG”而连接s和 t即s+=t之后得到字符串t =“JIAOTONGSHANGHAI”。
如t =“SHANGHAI”, s = “HA”则s在t的第3个字符及其之后首次出现的位置序号为5。
求子串操作在一个主串中从指定的位置序号开始取得一定长度的字符序列。
如t =“SHANGHAI”, 对t取第2个字符开始的4个字符长度的子串为“ANGH”。
当要求的子串长度过长超出了主串在指定字符位置后的长度限制以主串所能提供的最大长度为准。如t =“SHANGHAI”, 对t取第2个字符开始的10个字符长度的子串实际变为取第2个字符开始的6个字符长度的子串结果为“ANGHAI”。
如t =“SHANGHAI”,在第5个位置上插入字符串“123”后得字符串“SHANG123HAI”。
如“SHANG123HAI”从第5个字符开始删除3个字符后为“SHANGHAI”。
C++中关于串的库
字符串类定义sstring.h:
#ifndef SSTRING_H_INCLUDED
#define SSTRING_H_INCLUDED
#include <iostream>
using namespace std;
class illegalSize{};
class outOfBound{};
class noSpace{};
class sstring
{ friend int* nextValue(const sstring &t); //外部函数计算失配函数
private:
char *str; //动态数组存储字符串
int maxSize; //数组的尺寸
public:
sstring(int size); //创建动态空间数组长度size字符串长度为0。
sstring(const char *t); //用字符串t初始化。
sstring(const sstring &t); //用同类对象t初始化。
int length() const; //实际存储的字符串长度
void disp() const {cout<<str<<endl;}; //显示字符串
//判断两个字符串是否内容一样。是返回true否返回false。
bool equal(const sstring &t) const;
void assign(const sstring &t); //赋值操作将t中字符串赋值给调用函数的对象
sstring &subString(int pos, int len) const; //求从pos开始长度为len的子串。
//从串的第start个字符起向后查找字符串t第一次在
//串中出现的位置找到返回位置序号未找到返回-1。
int BF_find(const sstring &t, int start )const;//BF算法
int KMP_find(const sstring &t, int start )const;//KMP算法
// 在串的第pos个字符位置位置上插入串t的字符串。
// 插入成功返回true否则返回false。
bool insert(int pos, const sstring &t);
// 从串的字符串的第pos个字符位置起删除长度为n的子串。
// 如果长度不够length,以实际长度为准。删除成功返回true否则返回false。
bool Remove(int pos, int n);
~sstring(){delete []str;};//释放动态空间
};
#endif // SSTRING_H_INCLUDED
插入操作分析
bool insert(int pos, const sstring &t)将串t插入到当前串的第pos个位置中。
如将“ Shanghai ”插入到“Hello SJTU”中其中pos=5。操作时先为插入串腾出空间之后将插入串中字符逐个抄入腾出的空间插入操作结束。
字符串类部分基本操作的实现 sstring.cpp
#include <iostream>
#include "sstring.h"
using namespace std;
sstring::sstring(int size)//创建动态空间数组长度size,字符串长度为0。
{
if (size <= 0) throw illegalSize();
str = new char[size];//动态申请数组空间
if (!str)throw noSpace();
maxSize = size;
str[0]='\0';
}
//求串中从pos开始长度为len的子串。
sstring & sstring::subString(int pos, int len)const
{ int i;
if (pos<0) throw outOfBound();
sstring *tmp = new sstring(len+1);
for (i=0; i<len; i++)
if (str[pos+i]=='\0') break;
else tmp->str[i]=str[pos+i];
tmp->str[i]='\0';
return *tmp; }
//判断两个对象中存储的字符串是否内容一样。是返回true否返回false。
bool sstring::equal(const sstring &t)const
{
int i=0;
if (length() !=t.length()) return false;
while (str[i]!='\0')
if (str[i]!=t.str[i]) return false;
else i++;
return true;
}
字符串类的调试main.cpp
#include <iostream>
#include "sstring.h"
using namespace std;
int main()
{ sstring s1(50), s2("abd"), s3(s2), s4("sjtu");
s1.disp(); s2.disp(); s3.disp();
cout<<"length of s2 is: "<<s2.length()<<endl;
if (s2.equal(s3)) cout<<"s2 is equal to s3"<<endl;
if (s1.equal(s3)) cout<<"s1 is equal to s3"<<endl;
s1.assign(s2); cout<<"after assign s1: "; s1.disp();
s1.insert(1,s4); cout<<"after insert s1: "; s1.disp();
s3.Remove(1,2); cout<<"after remove s3: "; s3.disp();
sstring &s6 = s1.subString(2,4);
s6.disp();
return 0;
}
常见错误