39 串的顺序和链式存储结构：定长数组与动态数组
你好，我是王健伟。
前面我带你一起学习了各种各样的排序算法。从这节课开始，我们就要进入到字符串的学习了。
字符串作为一种数据结构，在计算机科学领域也有着比较广泛的应用。比如在搜索引擎中搜索一个关键词、在文章或发言中过滤或屏蔽一些敏感词等。这些关键词、敏感词都属于字符串。
提到这些，估计你就对它熟悉很多了。不过别着急，我们还是从一些基本的概念和术语学起。
串有哪些基本概念？
字符串简称串，是由零个或者多个字符组成的有限序列。计算机上非数值处理的对象通常指的就是串数据。在C语言中，针对串的处理函数常用的有这几个：strlen()、strcat()、strcmp()、strcpy()等。
看如下两行C++风格的代码：
上述代码行中用双引号括起来的“Hello World！”，就是一个串，在C或者C++语言中，用双引号括起来的是串，用单引号括起来的是字符。其中mystr称为串名，串中字符的个数n称为串的长度。当n=0时的串称为空串。空串可以用希腊字母Φ表示。
这里有两个概念咱们看一下。一个是子串，也就是串中任意个连续的字符组成的子序列。当然，如果是零个字符，就叫做空串。还有一个叫主串，包含子串的串叫做主串。
字符在主串中的位置，也就是字符在主串中的序号。序号（位置编号）从1开始算起。比如字符‘e’在“Hello World！”这个字符串中的位置是2。而空格字符‘ ’在“Hello World！”这个字符串中的位置是6，注意，空格符也是一个正常的字符。
而子串在主串中的位置，也就是子串的第一个字符在主串中的序号。
可以看到，串是一种特殊的线性表，数据元素之间呈线性关系，或者说相邻字符之间有前趋和后继关系。串中的数据对象一般都会限定为字符集，比如中文字符、英文字符、数字字符、标点符号等等。
串的基本操作比如增加、删除、修改、查询等一般都是以子串为操作对象，因为人类语言通常针对多个字符组成的字符序列才有现实意义。比如在搜索引擎中输入一个串（子串）就可以查询到包含了给定子串的各种信息。
串的基本操作包括串赋值、串拷贝（串复制）、判断空串、求长度、串连接、串比较、获取串的一部分内容（求子串）、串插入、串删除、串清空、定位（求某个串在另一个串中第一次出现的位置）等等。不过，不管对串进行什么样的操作，首先要解决的是串的存储问题，那么这节课咱们先说说串是如何存储的。
串的顺序存储结构
串的存储结构主要分为两种——顺序存储结构和链式存储结构。其中串的顺序存储结构是用一块地址连续的内存保存串中的字符序列。
定长数组（静态数组）存储结构及基本操作的实现
众所周知，在C语言中，用‘\0’作为串结束标记。在后续的实现代码中，我还是沿用这个标记作为串结束标记。当然，如果你愿意也可以专门拿出位置空间保存串长度信息。
对于串的各种基本操作都是比较简单的，写代码时要注意细节，考虑周到。另外值得一提的是程序的写法有很多种，不必拘泥于某一种，关键是理解代码的实现意图。这里直接看实现代码。
#define MAX_LEN 250 //最大字符串长度（定长）
//采用定长数组存储结构
class MySString
{
public:
MySString()//构造函数
{
ch[0] = '\0'; //字符串结束标记，其实'\0'就是数字0，所以写成ch[0] = 0;也没问题
length = 0; //字符串长度
}
//串赋值
void StrAssign(const char* pcontent)
{
size_t iLen = strlen(pcontent);
if (iLen >= MAX_LEN) //内容太长，容纳不下，字符串存储中要给字符串结束标记'\0'留出位置
return;
for (int i = 0; i < iLen; ++i)
{
ch[i] = pcontent[i];
} //end for
ch[iLen] = '\0'; //设置字符串结束标记，该标记不计入字符串长度中
length = iLen; //记录字符串长度
}
//串拷贝（串复制）
void StrCopy(const MySString &tmpstr)
{
for (int i = 0; i < tmpstr.length; ++i)
{
ch[i] = tmpstr.ch[i];
} //end for
length = tmpstr.length;
ch[length] = '\0';
}
//判断空串
bool IfStrEmpty()
{
if (ch[0] == '\0')
return true;
return false;
}
//串比较，比较其实就是逐个比较两个字符串中每个字符的ASCII码
//结果大于返回1，等于返回0，小于返回-1
int StrCmp(const MySString& tmpstr)
{
if (length == 0 && tmpstr.length ==0) //两个字符串都是空的，相等
return 0;
const char* p1 = ch;
const char* p2 = tmpstr.ch;
int result = 0;
while (*p1 != '\0' && *p2 != '\0')
{
result = (*p1) - (*p2);
if (result != 0)
{
if (result > 0)
return 1;
else
return -1;
}
p1++;
p2++;
} //end while
if (*p1 == '\0' && *p2 == '\0') //长度相同且内容相等
return 0;
//能走到下边流程的都是两个字符串一个长一个短，但长的和短的字符串的前面内容相同，比如字符串"ab"和"abc"
if (*p1 == '\0') //p1小，因为长度少
return -1;
//else if (*p2 == '\0')
return 1;
}
//串连接
bool StrCat(const MySString& tmpstr)
{
if (length + tmpstr.length >= MAX_LEN) //空间不够保存不下，这里直接返回false以通知开发者
return false;
int idx = 0;
size_t i;
for (i = length; i < (length + tmpstr.length); ++i)
{
ch[i] = tmpstr.ch[idx++];
}
ch[i] = '\0'; //字符串结束标记
length += tmpstr.length;
return true;
}
//获取串的一部分内容（求子串）
void SubString(MySString& resultstr, int pos, int len) //求得的子串给到resultstr。pos：从该位置开始[注意位置从0开始计算]，截取len个字符
{
//注意pos位置从0开始计算
if(pos < 0 || (pos + 1) > length || len <= 0)//pos位置要合法，len长度值要合法
return;
int icount = 0;
while(true)
{
resultstr.ch[icount] = ch[pos+ icount];
icount++;
if (icount == len) //截取够数量了
break;
if (ch[pos + icount] == '\0') //到主串末尾了，不够截取，截取多少算多少，直接跳出循环
break;
} //end while
resultstr.length = icount;
resultstr.ch[resultstr.length] = '\0';
return;
}
//串插入
//在当前串的pos位置（从0开始计算），插入子串substr
void StrInsert(int pos, const MySString& substr)
{
if (pos < 0 || pos > length) //插入位置不合法
return;
if (length + substr.length >= MAX_LEN) //容纳不下插入的新内容，则直接返回
return;
//把原来的必须的内容向后挪动
int i = (int)(length - 1); //i为int类型，这样就可以为负数，保证下面这个for循环可以正确结束
for (; i >= pos; --i)
{
ch[i + substr.length] = ch[i];
}
//把子串插入进来
for (size_t i = 0; i < substr.length; ++i)
{
ch[pos + i] = substr.ch[i];
}
length += substr.length;
ch[length] = '\0';
return;
}
//串删除
//在当前串的pos位置（从0开始计算），删除len个字符
void StrDelete(int pos, int len)
{
//注意pos位置从0开始计算
if (pos < 0 || (pos + 1) > length || len <= 0)//pos位置要合法，len长度值要合法
return;
if (pos + len > length)
{
//要删除的字符太多，串中没那么多可删的字符
len = int(length - pos); //只能删除这么多
}
//把剩余的字符串搬位置（向左搬）
for (int i = pos; i < length; ++i)
{
ch[i] = ch[i + len];
} //end for
length = length - len;
ch[length] = '\0';
return;
}
//串清空
void StrClear()
{
ch[0] = '\0';
length = 0;
return;
}
public:
//显示字符串内容
void DispContent()
{
cout << ch << endl;
}
public:
char ch[MAX_LEN]; //串内容。每个位置保存一个字符
size_t length; //串实际长度，专门引入该变量保存，提高程序运行效率
};
在main主函数中，加入下面的代码。
//串赋值
MySString mys;
mys.StrAssign("我爱你中国！");
mys.DispContent();
//串拷贝（串复制）、判断空串
MySString mys2;
cout <<"mys2为空吗？"<< mys2.IfStrEmpty() << endl;
mys2.StrCopy(mys);
mys2.DispContent();
cout <<"mys2为空吗？"<< mys2.IfStrEmpty() << endl;
//串比较
MySString mys3,mys4;
mys3.StrAssign("abc");
mys4.StrAssign("xyz");
cout <<"mys3和mys4字符串的比较结果为："<< mys3.StrCmp(mys4) << endl;
//串连接
MySString mys5;
mys5.StrAssign("Hello China!");
MySString mys6;
mys6.StrAssign("Hello this World!");
mys6.StrCat(mys5);
cout <<"mys6和mys5连接的结果为："<< mys6.ch << endl;
//获取串的一部分内容（求子串）
MySString mys7;
mys6.SubString(mys7, 0, 12); //子串放入mys7中
cout <<"子串mys7的内容是："<< mys7.ch << endl;
//串插入（在当前串的pos位置（从0开始计算），插入子串substr）
MySString mys8;
mys8.StrAssign("我爱北京，我爱中国！");
mys5.StrInsert(12, mys8);
cout <<"插入新内容后的mys5串内容是："<< mys5.ch << endl;
//串删除，在当前串的pos位置（从0开始计算），删除len个字符
MySString mys9;
mys9.StrAssign("Hello China!");
mys9.StrDelete(1, 10);
cout <<"删除部分内容后的mys9串内容是："<< mys9.ch << endl;
//串清空
mys9.StrClear();
cout <<"清空内容后的mys9串内容是："<< mys9.ch << endl;
执行结果如下：
动态数组（堆中分配内存）存储结构及基本操作的实现
采用定长数组存储结构存储串的方式虽然编码方便，但缺乏灵活性。所以引入了在堆中分配内存来保存串，实现不复杂，但要写好需要比较细心，下面是实现代码。
//采用堆中分配内存的存储结构
class MyHString//H表示Heap（堆）
{
public:
MyHString()//构造函数
{
ch = nullptr;
length = 0;
}
~MyHString()//析构函数
{
if (length > 0)
delete[] ch;
}
//串赋值
void StrAssign(const char* pcontent)
{
size_t iLen = strlen(pcontent);
if (length > 0)
delete[] ch;
ch = new char[iLen];
//拷贝字符串
for (int i = 0; i < iLen; ++i)
{
ch[i] = pcontent[i];
} //end for
length = iLen;
}
//串拷贝（串复制）
void StrCopy(const MyHString& tmpstr)
{
if (length > 0)
{
delete[] ch;
}
ch = new char[tmpstr.length];
for (int i = 0; i < tmpstr.length; ++i)
{
ch[i] = tmpstr.ch[i];
}
length = tmpstr.length;
return;
}
//判断空串
bool IfStrEmpty()
{
if (length == 0)
return true;
return false;
}
//串比较，比较其实就是逐个比较两个字符串中每个字符的ASCII码
//结果 大于返回1，等于返回0，小于返回-1
int StrCmp(const MyHString& tmpstr)
{
if (length == 0 && tmpstr.length == 0) //两个字符串都是空的，相等
return 0;
const char* p1 = ch;
const char* p2 = tmpstr.ch;
int result = 0;
int i = 0;
int j = 0;
while (i < length && j < tmpstr.length)
{
result = ch[i] - tmpstr.ch[j];
if (result != 0)
{
if (result > 0)
return 1;
else
return -1;
}
i++;
j++;
} //end while
if(i >= length && j >= tmpstr.length)//长度相同且内容相等
return 0;
//能走到下边流程的都是两个字符串一个长一个短，但长的和短的字符串的前面内容相同，比如字符串"ab"和"abc"
if (i >= length) //p1小，因为长度少
return -1;
return 1;
}
//串连接
void StrCat(const MyHString& tmpstr)
{
if (tmpstr.length <= 0) //目标是空串，无须连接
return;
char* tmp = new char [length + tmpstr.length];
for (int i = 0; i < length; ++i)
{
tmp[i] = ch[i];
}
for (int i = 0; i < tmpstr.length; ++i)
{
tmp[i + length] = tmpstr.ch[i];
}
if (length > 0) //原来内存释放掉
delete[] ch;
ch = tmp;
length = length + tmpstr.length;
return;
}
//获取串的一部分内容（求子串）
//求得的子串给到resultstr。pos：从该位置开始[注意位置从0开始计算]，截取len个字符
void SubString(MyHString& resultstr, int pos, int len)
{
//注意pos位置从0开始计算
if (pos < 0 || (pos + 1) > length || len <= 0)//pos位置要合法，len长度值要合法
return;
if (resultstr.length > 0)
delete[] resultstr.ch;
resultstr.ch = new char[len];
int icount = 0;
while (true)
{
resultstr.ch[icount] = ch[pos + icount];
icount++;
if (icount == len) //截取够数量了
break;
if (pos + icount >= length) //到主串末尾了，不够截取，截取多少算多少，直接跳出循环
break;
} //end while
resultstr.length = icount;
return;
}
//串插入
//在当前串的pos位置（从0开始计算），插入子串substr
void StrInsert(int pos, const MyHString& substr)
{
if (pos < 0 || pos > length) //插入位置不合法
return;
char* tmp = new char[length + substr.length];
for (int i = 0; i < length; ++i) //把原来的数据先拷贝到新位置去
{
tmp[i] = ch[i];
}
if (length > 0) //先把原来的内存释放了
delete[] ch;
ch = tmp;
//把原来的必须的内容向后挪动
int i = (int)(length - 1); //i为int类型，这样就可以为负数，保证下面这个for循环可以正确结束
for (; i >= pos; --i)
{
ch[i + substr.length] = ch[i];
}
//把子串插入进来
for (size_t i = 0; i < substr.length; ++i)
{
ch[pos + i] = substr.ch[i];
}
length += substr.length;
return;
}
//串删除
//在当前串的pos位置（从0开始计算），删除len个字符
void StrDelete(int pos, int len)
{
//注意pos位置从0开始计算
if (pos < 0 || (pos + 1) > length || len <= 0)//pos位置要合法，len长度值要合法
return;
if (pos + len > length)
{
//要删除的字符太多，串中没那么多可删的字符
len = int(length - pos); //只能删除这么多
}
//把剩余的字符串搬位置（向左搬）
for (int i = pos; i < length; ++i)
{
ch[i] = ch[i + len];
} //end for
length = length - len;
return;
}
//串清空
void StrClear()
{
if (length > 0)
delete[] ch;
length = 0;
return;
}
public:
//显示字符串内容
void DispContent()
{
for (int i = 0; i < length; ++i)
{
cout << ch[i];
}
cout << endl; //这里可以换一下行
}
public:
char *ch; //空间用new动态分配
size_t length; //串实际长度
};
在main主函数中，注释掉以往的代码，新增下面的测试代码。
//串赋值
MyHString mys;
mys.StrAssign("我爱你中国！");
mys.DispContent();
//串拷贝（串复制）、判断空串
MyHString mys2;
cout <<"mys2为空吗？"<< mys2.IfStrEmpty() << endl;
mys2.StrCopy(mys);
mys2.DispContent();
cout <<"mys2为空吗？"<< mys2.IfStrEmpty() << endl;
mys.StrAssign("我爱你中国，我爱你中国人！");
mys2.StrCopy(mys);
mys2.DispContent();
//串比较
MyHString mys3, mys4;
mys3.StrAssign("abc");
mys4.StrAssign("xyz");
cout <<"mys3和mys4字符串的比较结果为："<< mys3.StrCmp(mys4) << endl;
//串连接
MyHString mys5;
mys5.StrAssign("Hello China!");
MyHString mys6;
mys6.StrAssign("Hello this World!");
mys6.StrCat(mys5);
cout <<"mys6和mys5连接的结果为：";
mys6.DispContent();
//获取串的一部分内容（求子串）
MyHString mys7;
mys7.StrAssign("abcdefghijklmnopqrstuvwxyz!");
mys6.SubString(mys7, 2, 12); //子串放入mys7中
cout <<"子串mys7的内容是：";
mys7.DispContent();
//串插入（在当前串的pos位置（从0开始计算），插入子串substr）
MyHString mys8, mys82;
mys8.StrAssign("我爱北京，我爱中国！");
mys82.StrInsert(0, mys8);
cout <<"插入新内容后的mys82串内容是：";
mys82.DispContent();
//串删除，在当前串的pos位置（从0开始计算），删除len个字符
MyHString mys9;
mys9.StrAssign("Hello China!");
mys9.StrDelete(1, 11);
cout <<"删除部分内容后的mys9串内容是：";
mys9.DispContent();
//串清空
mys9.StrClear();
cout <<"清空内容后的mys9串内容是：";
mys9.DispContent();
执行结果如下：
上述代码其实是有改进空间的。比如在分配ch（串）所占内存空间时可以记录new出的内存大小，当进行字符串赋值、拷贝、连接等操作时，如果空间足够则不需要delete原有内存而是直接用这块内存实现相应功能，有兴趣可以自行改进代码。
串的链式存储结构
串的链式存储结构会使用到链表。比如字符串“abcde”，采用链式存储结构可能会如图1所示：
可以看到，每个链的节点中保存着一个字符。那么节点可以像下面这样定义：
图1的问题是每个节点保存一个字符，而一个字符只占1个字节，但一个next指针域在32位平台却占了4个字节，这种存储方式的存储密度非常低，因为实际有用的信息占的内存比例太小，造成了内存空间的巨大浪费。改进方式是让每个链的节点中保存多个字符比如保存4个字符，下面是改进后的字符节点。
此时，每个节点中实际有用的信息占的内存比例会提高，从而提高了存储密度。如图2所示：
从图2可以看到，第二个节点只有e和f两个字符，并没有填满，可以在字符f后面用字符串结束标记‘\0’标记字符串的结束。
串的链式存储不需要大块连续的内存空间。插入、删除等操作通过修改指针即可实现，不需要大量的移动字符数据。但串的链式存储不具备串的顺序存储中的随机存取特性，所以其基本操作实现代码可能会更加复杂，因而也不如串的顺序存储常用。
这里我就不提供串的链式存储相应代码了，如果你有兴趣可以自行实现。
小结
这节课我带你认识了串，给出了串、串的长度、空串的定义，也给出了串的常用处理函数。在编写代码时，注意串需要用双引号引起来。
接下来，为了引出与串相关的算法，又给出了子串、主串、字符在主串中位置概念。我希望你把串理解成一种数据元素之间呈线性关系的特殊线性表。接着我还向你介绍了串的基本操作——串赋值、串拷贝、判断空串、求长度、串连接、串比较、获取串的一部分内容、串插入、串删除、串清空、定位。
串的存储结构主要分为顺序存储结构和链式存储结构。顺序存储结构是用一块地址连续的内存保存串中的字符序列，而串的链式存储结构会使用链表来保存串中的各个字符序列。
在串的顺序存储结构介绍中，我们首先展示了用定长数组作为串的存储结构及在该结构之上实现的各种针对串的各种基本操作。然后为了进一步增加对串操作的灵活性，又展示了在堆中分配内存来保存串以及针对串的各种基本操作。
串的链式存储结构在本节中只做了简单介绍，这种存储结构有两个好处。
- 不需要大块连续的内存空间。
- 插入、删除等操作通过修改指针即可实现，不需要大量的移动字符数据。
但是，我们要知道，串的链式存储不具备串的顺序存储中的随机存取特性，所以它的实用性其实是不如串的顺序存储的。
思考题
请你实现串的链式存储代码，并使用串的链式存储实现：输入一个字符串，将其中的大写字母转换为小写字母并输出转换后的字符串。
欢迎你在留言区和我分享成果。如果觉得有所收获，也可以把课程分享给更多的朋友一起学习。我们下节课见！
- 阿阳 👍（0） 💬（0）
看链式存储的定义，字符串的插入和删除，逻辑都不简单。
2024-12-13 - 阿阳 👍（0） 💬（0）
在使用动态数组存储中，StrCat()方法，申请内存的语句为： char* tmp = new char [length + tmpstr.length]; 请问老师，这里是不是还应该加个1，因为连接后的字符串，要多个字符'\0'，用于表示字符串结束？
2024-12-13 - 鲁米 👍（0） 💬（0）
链式存储第一次接受到
2023-07-17 - Se7en 👍（0） 💬（0）
细致，重温一遍技术基础
2023-05-18