一、串的定长顺序存储
类似于顺序表,用一组地址连续的存储单元存储串值中的字符序列。所谓定长是指按预定义的大小,为每一个串变量分配一个固定长度的存储区。例如:
#define MAXSIZE 256
char s[MAXSIZE];
则串的最大长度不能超过256。
如何标识实际长度呢?
- 类似顺序表,用C++串描述如下:
typedef struct {
char data[MAXSIZE];
int Length;
} SeqString;
定义一个串变量:SeqString s;
,这种存储方式可以直接得到串的长度:s.length
,如下图所示。
串的顺序存储1:
-
在串味存储一个不会再串中出现的特殊字符作为串的终结符,以此表示串的结尾。比如C语言中处理定长串的方法就是这样的,它用
\0
表示串的结束。这种存储方法不能直接得到串的长度,而是通过判断当前字符是否是\0
来确定串是否结束,从而邱的串的长度。串的顺序存储2:
-
设定长串存储空间:
char s[MAXSIZE+1];
,用s[0]
存放串的实际长度,串值存放在s[1]~s[MAXSIZE]
中,字符的序号和存储位置一致,应用更为方便。
二、顺序串的数据类型定义
(一)串的定义
class String {
private:
char *str; // 存储字符串
int size; // 字符串长度
public:
String(); // 初始化为空串
String(char *s); // 构造函数用于C++串来初始化
String(const String &obj); // 构造函数用于C++对象来初始化
~String() { // 析构函数
delete str;
}
String substr(int pos, int length); // 从pos位置取子串
void insert(const String &obj, int pos); // 从串对象pos的位置插入子串obj
void delete(int pos, int length); // 在串对象pos起位置删除长度为length的子串
int strsize() {
return (strlen(str));
}
String operator = (String &obj); // 串对象赋值
String operator = (char *s); // C++串赋值
String operator + (String &obj); // 串对象连接
String operator + (char *s); // 串对象与C++串连接
friend String operator + (char *s, String &obj); // C++串与连接串对象
int StrIndex_BF(int k, String &p); // 简单模式匹配
int StrIndex_KMP(int k, String &p); // KMP算法
GetNext(char *t, int next[]);
}
(二)部分成员函数的实现
String::String() {
size = 1;
str = new char[size];
if (str == NULL) {
cout << "申请空间失败" << endl;
exit(1);
}
str[0] = '\0';
}
String::String(char *s) { // 用C++串初始化
size = strlen(s) + 1;
str = new char[size];
if (str == NULL) {
cout << "申请空间失败" << endl;
exit(1);
}
strcpy(str, s);
}
String::String(const String &obj) { // 用串对象obj初始化串对象
size = obj.size;
str = new char[size + 1];
if (str == NULL) {
cout << "申请空间失败" << endl;
exit(1);
}
strcpy(str, obj.str);
}
String String::operator +(String &obj) { // 两个串对象的连接
int len;
String temp;
delete [] temp.str;
len = strlen(obj.str) + strlen(str) + 1;
temp.str = new char[len];
temp.size = len;
if (str == NULL) {
cout << "申请空间失败" << endl;
exit(1);
}
strcpy(temp.str, str);
strcat(temp.str, obj.str);
return temp;
}
String String::operator +(char *s) { // 一个串对象和一个字符串的连接
int len;
String temp;
delete [] temp.str;
len = strlen(obj.str) + strlen(str) + 1;
temp.str = new char[len];
temp.size = len;
if (str == NULL) {
cout << "申请空间失败" << endl;
exit(1);
}
strcpy(temp.str, str);
strcat(temp.str, s);
return temp;
}
String String::operator +(char *s, String &obj) { // 一个字符串和一个串对象的连接
int len;
String temp;
delete [] temp.str;
len = strlen(s) + strlen(obj.str) + 1;
temp.str = new char[len];
temp.size = len;
if (str == NULL) {
cout << "申请空间失败" << endl;
exit(1);
}
strcpy(temp.str, s);
strcat(temp.str, obj.str);
return temp;
}
String String::substr(int pos, int length) {
int i;
String temp;
temp.str = new char[length + 1];
for (i = 0; i < length; i++) {
temp.str[i] = str[i + pos];
}
temp.str[i] = '\0';
return (temp);
}
三、定长数据串的基本运算
(一)求串长
int strLength(char s[]) {
int i = 0;
while(s[i] != '\n') i++;
return i;
}
(二)串连接
把两个串s1和s2首尾连接成一个新串s。
int StrConcat1(char s1[], char s2[], char s[]) {
int i = 0, j, len1, len2;
len1 = StrLength(s1);
len2 = StrLength(s2);
if (len1 + len2 > MAXSIZE - 1) return 0; // s长度不够
j = 0;
while(s1[j] != '\0') {
s[i] = s1[j];
i++;
j++;
}
j = 0;
while(s2[j] != '\0') {
s[i] = s2[j];
i++;
j++;
}
s[i] = '\0';
return 1;
}
(三)求子串
// 用t返回串s中从第i个字符开始的长度为len的子串,1≤i≤串长
int StrSub(char *t, char *s, int i, int len) {
int slen;
slen = StrLength(s);
if (i < 1 || i > slen || len < 0 || len > slen - i + 1) {
cout << "参数不对" << endl;
return 0;
}
for (j = 0; j < len; j++)
t[j] = s[i + j - 1];
t[j] = '\0';
return 1;
}
(四)串比较
int StrComp(char *s1, char *s2) {
int i = 0;
while(s1[i] == s2[i] && s1[i] != '\0') i++;
return (s1[i] == s2[i]);
}