数据结构——串_串的存储密度

串又称字符串，是由零个或多个字符组成的有限序列，是一种特殊的线性表。由串中若干个连续字符组成的子序列称为子串。

利用字符数组或字符指针表示串：

char str1[] = { 'a','b','c','d','\0' };
char str2[] = "abcdef";
char* str3 = str1;

上述三种表示串的方法其实就是顺序表的简化形式。由于在上述表达方法中，字符串的最后都有一个结束符“/0”，从而不需要指定顺序表的长度。

串的另一种表示方法是采用双向链表表示，称之为链串。存储密度为有效空间与所占用总空间的比值，若每个结点只存放一个字符，那么字符串的存储密度只有1/（2*4+1）=0.11（next，pre指针所占用空间都为4个字节），空间利用率低。
为提高空间效率，可以在每一个结点中存放多个字符。

在头文件<string.h>中有针对字符数组和字符指针所表示字符串的相关操作。例如，求字符串的长度（strlen）、字符串赋值（strcpy）、字符串比较（strcmp）、字符串连接（strcat）等。

链串的组织形式与一般的链表类似。主要的区别在于，链串中的一个节点可以存储多个字符。通常将链串中每个节点所存储的字符个数称为节点大小。

链串节点大小的选择与顺序串的格式选择类似。节点大小越大，则存储密度越大。但存储密度越大，一些操作（如插入、删除、替换等）有所不便，且可能引起大量字符移动，因此它适合于在串基本保持静态使用方式时采用。节点大小越小（如节点大小为1时），运算处理越方便，但存储密度下降。为简便起见，这里规定链串节点大小均为1。                                                                     

//str = (chainString)malloc(sizeof(csNode));

不采用该方式进行分配空间，会出现黄色警告

采用如下方式：

str = new csNode;

 代码如下所示：

#include<iostream>
using namespace std;
typedef char datatype;
 
typedef struct csNode {
	datatype data;
	csNode* next;
	csNode() :next(NULL) {
		data = '\0';
	};
}*chainString;
 
void cs_insert(chainString p, datatype ch) {
	chainString q = new csNode;
	if (q == NULL) {
		cout << "插入结点失败" << endl;
		return;
	}
	q->data = ch;
	q->next = p->next;
	p->next = q;
}
 
/*生成串*/
void createChainString(chainString h, datatype cstr[], int n)
{
	if (h == NULL) h = new csNode;
	for (int i = n - 1; i >= 0; i--)
		cs_insert(h, cstr[i]);
}
 
//串的第一个数据结点删除
void cs_delete(chainString p) {
	if (p == NULL) return;
	chainString q = p->next;
	if (q == NULL)
		return;
	p->next = q->next;
	delete q;
	q = NULL;
}
 
/*摧毁串*/
void destroyString(chainString& h)
{
	while (h->next != NULL) {
		cs_delete(h);
	}
	delete h;
	h = NULL;
}
 
/*串的复制,t赋值*/
void StrCopy(chainString& s, chainString t)
{
	if (s == NULL) s = new csNode;
	chainString p = t->next;
	while (p != NULL)
	{
		cs_insert(s, p->data);
		p = p->next;
	}
}
 
/*判断串相等*/
bool StrEqual(chainString s, chainString t)
{
	chainString p = s->next, q = t->next;
	while (p != NULL && q != NULL && p->data == q->data)
	{
		p = p->next;
		q = q->next;
	}
	if (p == NULL || q == NULL)		//表明此时已经扫描到串尾
		return true;
	else
		return false;
}
 
/*求串长*/
int StrLength(chainString s)
{
	int i = 0;
	chainString p = s->next;
	while (p != NULL)
	{
		i++;
		p = p->next;
	}
	return i;
}
 
/*串的连接,但不改变原本的s和t*/
chainString ConCat(chainString s, chainString t)
{
	chainString str, p, q, r;
	str = new csNode;
	r = str;
	//先将s存放到str中
	p = s->next;
	while (p != NULL)
	{
		q = new csNode;
		q->data = p->data;
 
		r->next = q;	r = q; //通过r指针的不断移动，构建str的后面部分，str作为一个不变的头，进行遍历
 
		p = p->next;
	}
	//再循环利用变量将t也存入str中，即接在s之后
	p = t->next;
	while (p != NULL)
	{
		q = new csNode;
		q->data = p->data;
 
		r->next = q;	r = q;
 
		p = p->next;
	}
	r->next = NULL;
	return str;
}
 
/*求子串*/
chainString SubStr(chainString s, int i, int j)
{
	chainString str, p, q, r;
	str = new csNode;
	str->next = NULL;		//若不将str置为空串，则输入放入会出现异常
	r = str;
 
	if (i <= 0 || i > StrLength(s) || j<0 || j>StrLength(s) || j - i + 1 > StrLength(s))
		return str;
 
	//利用指向p先行遍历到位置i
	p = s->next;
	for (int k = 1; k < i; ++k)
		p = p->next;
 
	//在从位置i开始遍历到位置j取出子串
	for (int k = i; k <= j; ++k)
	{
		q = new csNode;
		q->data = p->data;
 
		r->next = q;	r = q;
 
		p = p->next;
	}
	r->next = NULL;
	return str;
}
 
/*子串的插入*/
chainString InsStr(chainString s, int i, chainString t)
{
	int k = 1;
	chainString str, p, p1, q, r;
	str = new csNode;
	str->next = NULL;
	r = str;
 
	//判断下标i是否越界
	if (i <= 0 || i > StrLength(s) + 1)
		return str;
 
	//利用指针p,先将前0~i-1个字符存入str
	p = s->next;
	for (int k = 1; k < i; ++k)
	{
		q = new csNode;
		q->data = p->data;
		r->next = q;	r = q;
		p = p->next;
	}
 
	//利用指针p1,将串t中的结点顺势放入str中
	p1 = t->next;
	while (p1 != NULL)
	{
		q = new csNode;
		q->data = p1->data;
		r->next = q;	r = q;
		p1 = p1->next;
	}
 
	//此时的指针p，已然移动到i的位置，开始将后面的剩余结点继续存入串str中
	while (p != NULL)
	{
		q = new csNode;
		q->data = p->data;
		r->next = q;	r = q;
		p = p->next;
	}
	r->next = NULL;
	return str;
}
 
/*子串的删除*/
chainString DelStr(chainString s, int i, int j)
{
	int k = 1;
	chainString str, p, q, r;
	str = new csNode;
	str->next = NULL;
	r = str;
 
	if (i <= 0 || i > StrLength(s) || j - i + 1 > StrLength(s))
		return str;
 
	//利用指针p,先将前0~i-1个字符存入str
	p = s->next;
	for (int k = 1; k < i; ++k)
	{
		q = new csNode;
		q->data = p->data;
		r->next = q;	r = q;
		p = p->next;
	}
 
	//再利用指针p，直接遍历过j个位置
	for (k = i; k <= j; ++k)
		p = p->next;
 
	//此时的指针p，已然移动到j+1的位置，开始将后面的剩余结点继续存入串str中
	while (p != NULL)
	{
		q = new csNode;
		q->data = p->data;
		r->next = q;	r = q;
		p = p->next;
	}
	r->next = NULL;
	return str;
}
 
/*子串的替换*/
chainString RepStr(chainString s, int i, int j, chainString t)
{
	int k = 1;
	chainString str, p, p1, q, r;
	str = new csNode;
	str->next = NULL;
	r = str;
	//判断下标i是否越界
	if (i <= 0 || i > StrLength(s) + 1 || j<0 || j - i + 1>StrLength(s))
		return str;
 
	//利用指针p,先将前0~i-1个字符存入str
	p = s->next;
	for (int k = 1; k < i; ++k)
	{
		q = new csNode;
		q->data = p->data;	 q->next = NULL;
		r->next = q;	r = q;
		p = p->next;
	}
 
	for (k = i; k <= j; ++k)
		p = p->next;		//直接删除原本串s中从第i位开始长度为j的那一子串
 
	//利用指针p1,将串t中的结点顺势放入str中
	p1 = t->next;
	while (p1 != NULL)
	{
		q = new csNode;
		q->data = p1->data;	 q->next = NULL;
		r->next = q;	r = q;
		p1 = p1->next;
	}
 
	//此时的指针p，已然移动到i的位置，开始将后面的剩余结点继续存入串str中
	while (p != NULL)
	{
		q = new csNode;
		q->data = p->data;	 q->next = NULL;
		r->next = q;	r = q;
		p = p->next;
	}
	r->next = NULL;
	return str;
}
 
/*输出串*/
void DispStr(chainString s)
{
	chainString p = s->next;
	while (p != NULL)
	{
		cout << p->data << endl;
		p = p->next;
	}
	cout << endl;
}
 
void test1()
{
	printf("*测试串的生成*\n");
	chainString s1 = new csNode;
	datatype ch1[12] = "Hello World";
	createChainString(s1, ch1, 12);
	printf("串s初始化为：");
	DispStr(s1);
 
	printf("\n*测试串的复制*\n");
	chainString s2 = new csNode;
	datatype ch2[6] = "Frank";
	createChainString(s2, ch2, 6);
 
	StrCopy(s1, s2);
	printf("复制后的串s1为：");
	DispStr(s1);
 
	printf("\n*测试串是否相等*\n");
	chainString s3 = new csNode, s4 = new csNode, s5 = new csNode;
	datatype ch3[6] = "apple";
	datatype ch4[6] = "apple";
	datatype ch5[7] = "banana";
	createChainString(s3, ch3, 6);
	createChainString(s4, ch4, 6);
	createChainString(s5, ch5, 7);
	if (StrEqual(s3, s4))
		printf("s3与s4两串相等\n");
	else
		printf("s3与s4两串不相等\n");
 
	if (StrEqual(s3, s5))
		printf("s3与s5两串相等\n");
	else
		printf("s3与s5两串不相等\n");
 
	printf("\n*测试串的长度*\n");
	int len = StrLength(s5);
	printf("显示一下串s5：");
	DispStr(s5);
	printf("串s5的长度为：%d\n", len);
 
	printf("\n*测试串的连接*\n");
	chainString s6 = new csNode;
	chainString s7 = new csNode;
	chainString s8 = new csNode;
	datatype ch6[3] = "so";
	datatype ch7[6] = " good";
	createChainString(s6, ch6, 3);
	createChainString(s7, ch7, 6);
	s8 = ConCat(s6, s7);
	printf("串s6与串s7连接之后为：");
	DispStr(s8);
}
 
void test2()
{
	printf("*测试求子串*\n");
	chainString s1 = new csNode, s2 = new csNode;
	datatype ch1[10] = "wonderful";
	createChainString(s1, ch1, 10);
	printf("初始化的串s1为：");
	DispStr(s1);
	printf("串s1从第2个字符开始的连续4个字符的子串为：");
	s2 = SubStr(s1, 2, 4);
	DispStr(s2);
 
	printf("\n*测试子串的插入*\n");
	chainString s3 = new csNode, s4 = new csNode;
	datatype ch3[10] = "ok";
	createChainString(s3, ch3, 10);
 
	printf("在串s1的第3个位置插入串s3之后为：");
	s4 = InsStr(s1, 3, s3);
	DispStr(s4);
 
	printf("\n*测试子串的删除*\n");
	chainString s5 = new csNode, s6 = new csNode;
	datatype ch5[10] = "fantistic";
	createChainString(s5, ch5, 10);
 
	printf("将串s5的第5个字符开始的长度为2的子串删除后为：");
	s6 = DelStr(s5, 5, 2);
	DispStr(s6);
 
	printf("\n*测试子串的替换*\n");
	chainString s7 = new csNode;
	chainString s8 = new csNode;
	chainString s9 = new csNode;
	datatype ch7[15] = "accountability";
	datatype ch8[3] = "le";
	createChainString(s7, ch7, 15);
	createChainString(s8, ch8, 3);
 
	printf("将串s7从第10个字符开始的长度为2的子串替换成s8后为：");
	s9 = RepStr(s7, 10, 5, s8);
	DispStr(s9);
}
 
int main()
{
	test1();
	test2();
}

 参考：

数据结构 | 串的存储结构之链串_Fire_Cloud_1的博客-CSDN博客https://blog.csdn.net/Fire_Cloud_1/article/details/127414613?spm=1001.2014.3001.5501C++: 形参的*& 与 *的理解_福桐的博客-CSDN博客_c++ 形参&https://blog.csdn.net/weixin_40597170/article/details/95788150?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%BD%A2%E5%8F%82%20&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-95788150.142%5Ev70%5Ejs_top,201%5Ev4%5Eadd_ask&spm=1018.2226.3001.4187