数据结构与算法学习笔记五--串

前言

一、定义

二、串的表示和实现

1.定长顺序存储表示

1.定义

2.串拼接

3.求子串

4.完整代码

2.堆分配存储表示

1.定义

2.求串长

3.串比较

4.清空s串，释放空间

5.串拼接

6.求子串

7.完整代码

3.串的块链存储表示

前言

这篇文章主要记录下串的相关知识。

一、定义

串即字符串，是由零个或者多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。

串长：串中字符的个数(n>=0)。n=0的时候称为空串。

空格(白)串：由一个或者多个空格符组成的串。

子串：串S中任意个连续的字符序列叫做S的子串；S叫做主串。

子串位置:子串的第一个字符在主串中的序号。

字符位置：字符在串中的序号。

串相等：串长度相等，且对应位置上字符相等。

二、串的表示和实现

串有三种机内表示方法,分别为定长顺序存储表示、对分配存储表示、串的块链存储表示。

在了解串的几种表示之前，我们先复习下C++中的字符数组，以便您更好的理解代码，当然如果您已经非常熟悉这块的知识，可以直接看下面的实现。

字符数组是用来存放字符数据的数组。

字符数组的声明方式为:

char 数组名[常量表达式];

例如：

char c[11] = {'I','','a','m','','C','h','i','n','a'}

如果我们使用字符数组表示字符串的时候，需要在最后加一个'\0'表示字符串结束的标志。

1.定长顺序存储表示

类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中,按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区,则可用定长数组如下描述之。

1.定义

// ----- 串的定长顺序存储表示 -----

#define Maxstrlen 255

typedef unsigned char SString[Maxstrlen + 1];

定义好串之后，我们可以实现串的常用操作，例如拼接，求子串等操作

2.串拼接

拼接串的时候，我们要考虑下两个字符串的长度和是否超过我们定义的串的长度，超过之后我们要做截取处理。

//字符串拼接
void concat(String &result, String s1, String s2) {if (length(s1)+length(s2) <= Maxstrlen) {//不需要截断int i = 0;while (s1[i] != '\0') {result[i] = s1[i];i++;}int j = 0;while (s2[j] != '\0') {result[i] = s2[j];i++;j++;}result[i] = '\0';}else if( length(s1) < Maxstrlen ){//截断S2//不需要截断int i = 0;while (s1[i] != '\0') {result[i] = s1[i];i++;}int j = 0;for (; i+j <= Maxstrlen; j++) {result[i+j] = s2[j];cout<<"j="<<j<<endl;}result[Maxstrlen] = '\0';}else{//不需要截断for (int i = 0; i< Maxstrlen; i++) {result[i] = s1[i];}result[Maxstrlen] = '\0';}
}

3.求子串

//求子串
bool substring(String &sub, String str, int pos, int len) {int strLen = length(str);if (pos < 0 || pos > strLen || len < 0 || len > strLen - pos + 1) {return false;}for (int i = 0; i < len; ++i) {sub[i] = str[pos + i];}sub[len] = '\0';return true;
}

4.完整代码

#include <iostream>
using namespace std;#define Maxstrlen 8
typedef unsigned char String[Maxstrlen + 1];void initString(String &str) {str[0] = '\0';
}int length(String str) {int len = 0;while (str[len] != '\0') {len++;}return len;
}
//字符串拼接
void concat(String &result, String s1, String s2) {if (length(s1)+length(s2) <= Maxstrlen) {//不需要截断int i = 0;while (s1[i] != '\0') {result[i] = s1[i];i++;}int j = 0;while (s2[j] != '\0') {result[i] = s2[j];i++;j++;}result[i] = '\0';}else if( length(s1) < Maxstrlen ){//截断S2//不需要截断int i = 0;while (s1[i] != '\0') {result[i] = s1[i];i++;}int j = 0;for (; i+j <= Maxstrlen; j++) {result[i+j] = s2[j];cout<<"j="<<j<<endl;}result[Maxstrlen] = '\0';}else{//不需要截断for (int i = 0; i< Maxstrlen; i++) {result[i] = s1[i];}result[Maxstrlen] = '\0';}
}
//求子串
bool substring(String &sub, String str, int pos, int len) {int strLen = length(str);if (pos < 0 || pos > strLen || len < 0 || len > strLen - pos + 1) {return false;}for (int i = 0; i < len; ++i) {sub[i] = str[pos + i];}sub[len] = '\0';return true;
}
//插入
bool insertString(String &str, int pos, String insertStr) {int strLen = length(str);int insertLen = length(insertStr);if (pos < 0 || pos > strLen || strLen + insertLen > Maxstrlen) {return false;}for (int i = strLen; i >= pos; --i) {str[i + insertLen] = str[i];}for (int i = 0; i < insertLen; ++i) {str[pos + i] = insertStr[i];}str[strLen + insertLen] = '\0';return true;
}
//删除
bool deleteString(String &str, int pos, int len) {int strLen = length(str);if (pos < 0 || pos > strLen || len < 0 || len > strLen - pos + 1) {return false;}for (int i = pos + len; i <= strLen; ++i) {str[i - len] = str[i];}return true;
}int main() {String str, sub, result;initString(str);// 测试初始化和长度计算cout << "字符串str长度: " << length(str) << endl;// 测试串的拼接String s1 = "Hello", s2 = "Worlda";concat(result, s1, s2);cout << "拼接之后的字符串: " << result << endl;// 测试子串的提取int pos = 2, len = 3;if (substring(sub, result, pos, len)) {cout << "从下标2开始的子字符串 " << pos << " 长度 " << len << ": " << sub << endl;} else {cout << "非法位置" << endl;}// 测试插入操作String insertStr = " C++";if (insertString(result, pos, insertStr)) {cout << "插入之后的字符串: " << result << endl;} else {cout << "插入失败." << endl;}// 测试删除操作len = 5;if (deleteString(result, pos, len)) {cout << "字符串删除: " << result << endl;} else {cout << "字符串删除失败." << endl;}return 0;
}

2.堆分配存储表示

在上述的使用定长存储表示串的时候，我们会发现再串的拼接、插入、置换等操作中有可能出现长度超过我们设定的最大长度。为了克服上述的弊端，我们可以不限定串长的最大长度，也就是动态分配串值的存储空间。

1.定义

这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。我们可以使用堆内存给串分配存储空间，调用C语言的malloc()和free()来管理。

typedef struct {char* ch;       // 若是非空串,则按照串长分配存储区,否则ch为NULLint length;     // 串长度
} HString;

2.求串长

返回串的长度即可。

//求表长
int length(HString &str){return str.length;
}

3.串比较

// 字符串比较
int compare(const HString& s1, const HString& s2) {int i = 0;while (s1.ch[i] != '\0' && s2.ch[i] != '\0') {if (s1.ch[i] != s2.ch[i]) {return s1.ch[i] - s2.ch[i];}i++;}return s1.ch[i] - s2.ch[i];
}

4.清空s串，释放空间

删除s占用的内存空间，串长置空。

// 释放内存
void destroyString(HString& str) {if (str.ch) {delete[] str.ch;}str.length = 0;
}

5.串拼接

// 字符串拼接
bool concat(HString& s1, const HString& s2) {// 计算拼接后的长度int newLength = s1.length + s2.length;char* newStr = new char[newLength + 1];// 将s1的字符复制到新串中for (int i = 0; i < s1.length; ++i) {newStr[i] = s1.ch[i];}// 将s2的字符复制到新串中for (int i = 0; i < s2.length; ++i) {newStr[s1.length + i] = s2.ch[i];}newStr[newLength] = '\0';// 释放原来的内存空间delete[] s1.ch;// 更新s1的指针和长度s1.ch = newStr;s1.length = newLength;return true;
}

6.求子串

// 截取子串
void subString(HString& str, int pos, int len) {// 判断参数合法性if (pos < 1 || pos > str.length || len < 0 || pos + len - 1 > str.length) {cout << "截取位置或长度非法" << endl;return;}// 释放原有的内存空间delete[] str.ch;// 更新指针和长度str.ch = new char[len + 1];str.length = len;// 复制子串到新的内存空间for (int i = 0; i < len; ++i) {str.ch[i] = str.ch[pos - 1 + i];}str.ch[len] = '\0';
}

7.完整代码

#include <iostream>using namespace std;typedef struct {char* ch;       // 若是非空串,则按照串长分配存储区,否则ch为NULLint length;     // 串长度
} HString;// 初始化
void initString(HString& str, const char* initial) {if (initial) {int len = 0;const char* p = initial;while (*p != '\0') {len++;p++;}str.length = len;str.ch = new char[len + 1];for (int i = 0; i < len; ++i) {str.ch[i] = initial[i];}str.ch[len] = '\0';} else {str.length = 0;str.ch = nullptr;}
}
// 为字符串赋值为常量字符串chars
void assignStr(HString& str, const char* chars) {if (str.ch) {delete[] str.ch; // 释放原有的空间}int len = 0;const char* p = chars;while (*p != '\0') {len++;p++;}str.length = len;str.ch = new char[len + 1];for (int i = 0; i < len; ++i) {str.ch[i] = chars[i];}str.ch[len] = '\0';
}//求表长
int length(HString &str){return str.length;
}
// 字符串比较
int compare(const HString& s1, const HString& s2) {int i = 0;while (s1.ch[i] != '\0' && s2.ch[i] != '\0') {if (s1.ch[i] != s2.ch[i]) {return s1.ch[i] - s2.ch[i];}i++;}return s1.ch[i] - s2.ch[i];
}// 字符串拼接
bool concat(HString& s1, const HString& s2) {// 计算拼接后的长度int newLength = s1.length + s2.length;char* newStr = new char[newLength + 1];// 将s1的字符复制到新串中for (int i = 0; i < s1.length; ++i) {newStr[i] = s1.ch[i];}// 将s2的字符复制到新串中for (int i = 0; i < s2.length; ++i) {newStr[s1.length + i] = s2.ch[i];}newStr[newLength] = '\0';// 释放原来的内存空间delete[] s1.ch;// 更新s1的指针和长度s1.ch = newStr;s1.length = newLength;return true;
}
// 截取子串
void subString(HString& str, int pos, int len) {// 判断参数合法性if (pos < 1 || pos > str.length || len < 0 || pos + len - 1 > str.length) {cout << "截取位置或长度非法" << endl;return;}// 释放原有的内存空间delete[] str.ch;// 更新指针和长度str.ch = new char[len + 1];str.length = len;// 复制子串到新的内存空间for (int i = 0; i < len; ++i) {str.ch[i] = str.ch[pos - 1 + i];}str.ch[len] = '\0';
}// 释放内存
void destroyString(HString& str) {if (str.ch) {delete[] str.ch;}str.length = 0;
}
// 插入
bool insertString(HString& s, int pos, const HString& T) {// 插入位置非法if (pos < 1 || pos > s.length + 1) {cout << "插入位置非法" << endl;return false;}// 计算插入后新串的长度int newLength = s.length + T.length;char* newStr = new char[newLength + 1];// 将s的前pos-1个字符复制到新串中for (int i = 0; i < pos - 1; ++i) {newStr[i] = s.ch[i];}// 将串T复制到新串中for (int i = 0; i < T.length; ++i) {newStr[pos - 1 + i] = T.ch[i];}// 将s中pos位置后的字符复制到新串中for (int i = pos - 1; i < s.length; ++i) {newStr[T.length + i] = s.ch[i];}newStr[newLength] = '\0';// 释放原来的内存空间delete[] s.ch;// 更新s的指针和长度s.ch = newStr;s.length = newLength;return true;
}// 打印字符串
void printString(const HString& str) {cout << str.ch << endl;
}int main() {HString s, T;initString(s, "Hello ");initString(T, "world!");cout << "插入前：";printString(s);insertString(s, 6, T); // 在位置6插入字符串Tcout << "插入后：";printString(s);// 测试赋值函数char chars[] = "Welcome";assignStr(s, chars);cout << "赋值后：";printString(s);// 测试字符串比较HString s1, s2;initString(s1, "abc");initString(s2, "abd");cout << "字符串比较结果：" << compare(s1, s2) << endl;// 测试字符串拼接concat(s1, s2);cout << "字符串拼接结果：";printString(s1);// 测试子串截取subString(s1, 2, 2);cout << "截取子串结果：";printString(s1);// 释放内存destroyString(s);destroyString(T);destroyString(s1);destroyString(s2);return 0;
}