• 【图文并茂】C++介绍之串

    1.1串

    引子——

    ​ 字符串简称为串，串是由字符元素构成的，其中元素的逻辑关系也是一种线性关系。串的处理在计算机非数值处理中占用重要的地位，如信息检索系统，文字编辑等都是以串数据作为处理对象

    串是由零个或多个字符组成的有限序列。

    两个串相等，当且仅当两个串长度相等且对应位置上字符一样

    1.2串的抽象数据类型

    （如图所示）

    在这里插入图片描述

    1.3顺序串基本算法实现

    和线性表一样，串也要顺序存储结构和链式存储结构，前者称为顺序串，后者称为链串

    顺序串的存储方式又有两种。一种是每个字只存一个字符，这称为非紧缩格式。另一种是每个字存放多个字符，称为紧凑格式。

    （1）声明

    typedef struct
{
	char data[MaxSize]; 
	int length;
}SqString; //存放串字符//存放串长//顺序串类型

    • 1
    • 2
    • 3
    • 4
    • 5

    (2)生成串

    void StrAssign(SqString& s, char cstr[]) {
	int i;
	for (i = 0; cstr[i] != '\0'; i++)
		s.data[i] = cstr[i];
	s.length = i; //s为引用型参数//设置串s的长度
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    (3)销毁串

    void DestroyStr(SqString&s)
{ }

    • 1
    • 2

    (4)串的复制

    void StrCopy(SqString& s, SqString t)
{//s为引用型参数
	int i;
	for (i = 0; i < t.length; i++)
		s.data[i] = t.data[i];
	s.length = t.length;
	//复制t的所有字符//设置串s的长度
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    (5)判断串相等

    //判断串相等
bool StrEqual(SqString s,SqString t) {
	bool same=true; 
	int i; 
	if(s.length!=t.length)
		same=false; 
	else 
		for (i=0;i<s.length;i++) 
			if (s.data[i] = t.data[i])
			{
				same = false;
				break;
			}
	return same;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    (6)求串长

    int StrLength(SqString s)
{
	return s.length;
}

    • 1
    • 2
    • 3
    • 4

    (7)串的连接

    SqString Concat(SqString s, SqString t)
{
	SqString str;
	int i;
	str.length = s.length + t.length;
	for (i = 0; i < s.length; i++)
		str.data[i] = s.data[i];
	for (int i = 0; i < t.length; i++)
		str.data[s.length + i] = t.data[i];
	return str;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    (8)字串插入

    SqString InsStr(SqString s1, int i, SqString s2)
{
	int j;
	SqString str;	//定义结果串
	str.length = 0;
	if (i <= 0 || i > s1.length + 1)
		return str;
	for (j = 0; j < i - 1; j++)
		str.data[j] = s1.data[j];
	for (j = 0; j < s2.length; j++)
		str.data[i + j - 1] = s2.data[j];
	for (j = i - 1; j < s1.length; j++)
		str.data[s2.length + j] = s1.data[j];
	str.length = s1.length + s2.length;
	return str;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    (9)字串删除

    SqString DelStr(SqString s, int i, int j)
{
	int k;
	SqString str;
	str.length = 0;
	if (i <= 0 || i > s.length || i + j > s.length + 1)
		return str;
	for (k = 0; k < i - 1; k++)
		str.data[k] = s.data[k];
	for (k = i + j - 1; k < s.length; k++)
		str.data[k - j] = s.data[k];
	str.length = s.length - j;
	return str;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    (10)字串替换

    //字串的替换
SqString RepStr(SqString s, int i, int j, SqString t)
{
	int k;
	SqString str;
	str.length = 0;
	if (i <= 0 || i > s.length || i + j > s.length + 1)
		return str;
	for (k = 0; k < i - 1; k++)
		str.data[k] = s.data[k];
	for (k = 0; k < t.length; k++)
		str.data[i + k - 1] = t.data[k];
	for (k = i + j - 1; k < s.length; k++)
		str.data[t.length + k - j] = s.data[k];
	str.length = s.length - j + t.length; 
	return str;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    (11)输出串

    //输出串
void DispStr(SqString s)
{
	int i;
	if (s.length > 0)
	{
		for (i = 0; i < s.length; i++)
			printf("%c", s.data[i]);
		printf("\n");
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    1.4链串

    串的链式存储结构是链串，这里介绍采用带头结点的单链表作为链串。

    （如图）

    在这里插入图片描述

    1.5链串的基本算法实现

    （1）声明

    typedef struct snode {
	char data;
	struct snode* next;
}LinkStrNode;

    • 1
    • 2
    • 3
    • 4

    (2)尾插法生成串

    //尾插法建立链串
void StrAssign(LinkStrNode*& s, char cstr[])
{
	int i;
	LinkStrNode* r, * p;
	s = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	r = s;
	for (i = 0; cstr[i] != '\0'; i++)
	{
		p = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		p->data = cstr[i];
		r->next = p;
		r = p;
	}
	r->next = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    （3）销毁串

    //销毁串
void DestroyStr(LinkStrNode*&s)
{
	LinkStrNode* pre = s, * p = s->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = pre->next;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    (4)串的复制

    void StrCopy(LinkStrNode*& s, LinkStrNode* t)
{
	LinkStrNode* p = t->next, * q, * r;
	s = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	r = s;
	while (p != NULL)
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q; r = q;
		p = p->next;
	}
	r->next = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    (5)判断串相等

    //判断串相等
bool StrEqual(LinkStrNode* s, LinkStrNode* t)
{
	LinkStrNode* 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;
	return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    (6)求串长

    //求串长
int StrLength(LinkStrNode* s)
{
	int  i = 0;
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		i++;
		p = p->next;
	}
	return i;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    (7)串的连接

    LinkStrNode* contact(LinkStrNode * s, LinkStrNode * t)
{
	LinkStrNode* str, * p = s->next, * q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	r = str;
	while (p != NULL)
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = p;
		p = p->next;
	}
	p = t->next;
	while (p != NULL)
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q; r = q;
		p = p->next;
	}
	r->next = NULL;
	return  str;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    (8)求子串

    //求子串
LinkStrNode* SubStr(LinkStrNode* s, int i, int j)
{
	int k;
	LinkStrNode* str, * p = s->next, * q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	str->next = NULL;
	if (i <= 0 || i > StrLength(s) || j<0 || i + j - 1>StrLength(s))
		return str;
	for (k = 1; k < i; k++)
		p = p->next;
	for (k = 1; k <= j; k++)
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL;
	return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    (9)子串插入

    //子串插入
LinkStrNode* InsStr(LinkStrNode* s, int i, LinkStrNode* t)
{
	int k;
	LinkStrNode* str, * p = s->next, * pl = t->next, * q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	str->next = NULL;
	r = str;
	if (i <= 0 || i > StrLength(s) + 1)
		return str;
	for (k = 1; k < i; k++) //置结果串str为空串//:指向结果串的尾结点//参数不正确时返回空申//将s的前i个结点复制到str 
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q; r = q;
		p = p->next;
	}
	while (pl!=NULL) { 
	//将t的所有结点复制到str 
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = pl->data;
		r->next = q; r = q;
		pl = pl->next;
	}
	while (p != NULL) {
		//将t的所有结点复制到str 
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q; r = q;
		p = p->next;
	}
	r->next = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    (10)子串删除

    //字串删除
LinkStrNode* DelStr(LinkStrNode* s, int i, int j)
{
	int k;
	LinkStrNode* str, * p = s->next,*q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	str->next = NULL;
	r = str;
	if (i <= 0 || i > StrLength(s) || j<0 || i + j - 1>StrLength(s));
	return str;
	for (int k = 1; k < i; k++)
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q; r = q;
		p = p->next;
	}
	for (k = 0; k < j; k++)
		p = p->next;
	while (p != NULL)
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL;
	return str;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    (11)子串的替换

    //子串的替换
LinkStrNode* RepStr (LinkStrNode* s, int i, int j, LinkStrNode* t)
{
	int k;
	LinkStrNode* str, * p = s->next, * p1 = t->next, * q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	str->next = NULL;
	r = str;
	if (i <= 0 || i > StrLength(s) || j<0 || i + j - 1>StrLength(s))
		return str;
	for (int k = 0; k < i - 1; k++)
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data; q->next = NULL;
		r->next = q; r = q;
		p = p->next;
	}
	for (k = 0; k < j; k++)
		p = p->next;
	while(p1 !=NULL)
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p1->data; aa222q->next = NULL;
		r->next = q; r = q;
		p1 = p1->next;
	}
	while (p != NULL)
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data; q->next = NULL;
		r->next = q; r = q;
		p = p->next;
	}
	r->next = NULL;
	return str;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    (12)输出串

    输出串
void DispStr(LinkStrNode* s)
{
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    希望本文对你有所帮助！
    在这里插入图片描述

  • 相关阅读:
    [科研图像处理]用matlab平替image-j，有点麻烦，但很灵活！
    acwing算法基础之数学知识--中国剩余定理
    jdk动态代理使用详解
    Unity中Shader的矩阵加减法
    scratch三个数排序 电子学会图形化编程scratch等级考试四级真题和答案解析2022年9月
    计算机网络
    HIVE 表 DLL 基本操作（一）——第1关：Create/Alter/Drop 数据库
    软考-信息安全工程师-1
    nginx 配置反向代理
    前端实现可拖拽流程的js框架
  • 原文地址：https://blog.csdn.net/m0_73421035/article/details/132746459