目录
前言
一、定义
二、串的表示和实现
1.定长顺序存储表示
1.定义
2.串拼接
3.求子串
4.完整代码
2.堆分配存储表示
1.定义
2.求串长
3.串比较
4.清空s串，释放空间
5.串拼接
6.求子串
7.完整代码
3.串的块链存储表示
1.定义
2.生成串
3.生成串
4.完整代码
前言
这篇文章主要记录下串的相关知识。
一、定义
串即字符串，是由零个或者多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。
串长：串中字符的个数(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为NULL
int 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为NULL
int 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插入字符串T
cout << "插入后：";
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;
}
3.串的块链存储表示
串的块链存储表示可以通过链表来实现，每个节点表示一个字符，串中的字符按顺序连接在一起。
1.定义
// 定义节点结构体
struct CharNode {
char data; // 数据域，存储字符
CharNode* next; // 指针域，指向下一个节点
};
// 定义串结构体
struct HString {
CharNode* head; // 头指针，指向串的第一个节点
int length; // 串的长度
};
2.生成串
生成串的时候，串的头结点置空，长度为0。
// 初始化串
void initString(HString& str) {
str.head = nullptr;
str.length = 0;
}
3.生成串
// 生成串
void assignStr(HString& str, const char* chars) {
initString(str); // 清空原有串
const char* p = chars;
CharNode* prev = nullptr; // 前一个节点指针
while (*p != '\0') {
CharNode* newNode = new CharNode; // 创建新节点
newNode->data = *p;
newNode->next = nullptr;
if (!str.head) {
str.head = newNode; // 如果头指针为空，将新节点设置为头节点
} else {
prev->next = newNode; // 否则将新节点链接到上一个节点
}
prev = newNode; // 更新前一个节点指针
str.length++; // 更新串长度
p++;
}
}4.完整代码
#include <iostream>
using namespace std;
// 定义节点结构体
struct CharNode {
char data; // 数据域，存储字符
CharNode* next; // 指针域，指向下一个节点
};
// 定义串结构体
struct HString {
CharNode* head; // 头指针，指向串的第一个节点
int length; // 串的长度
};
// 初始化串
void initString(HString& str) {
str.head = nullptr;
str.length = 0;
}
// 生成串
void assignStr(HString& str, const char* chars) {
initString(str); // 清空原有串
const char* p = chars;
CharNode* prev = nullptr; // 前一个节点指针
while (*p != '\0') {
CharNode* newNode = new CharNode; // 创建新节点
newNode->data = *p;
newNode->next = nullptr;
if (!str.head) {
str.head = newNode; // 如果头指针为空，将新节点设置为头节点
} else {
prev->next = newNode; // 否则将新节点链接到上一个节点
}
prev = newNode; // 更新前一个节点指针
str.length++; // 更新串长度
p++;
}
}
// 打印串
void printString(const HString& str) {
CharNode* p = str.head;
while (p) {
cout << p->data;
p = p->next;
}
cout << endl;
}
// 释放内存
void destroyString(HString& str) {
CharNode* p = str.head;
while (p) {
CharNode* temp = p;
p = p->next;
delete temp; // 释放节点内存
}
str.head = nullptr;
str.length = 0;
}
int main() {
HString str;
assignStr(str, "Hello, world!");
cout << "打印串: ";
printString(str);
destroyString(str);
return 0;
}
