探索数据结构：顺序串与链式串的深入理解

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 串的定义

串是一种特殊的顺序表，即每一个元素都是单独一个字符。在C语言中我们学习的字符串便是串的一种，它在我们的数据搜索与文本编译中起着不可或缺的作用。

img

特别注意：空格也是一个字符！！

下面是与串相关概念：

  • 串的长度：指串中有效元素的个数(不包括字符\0)。
  • 空串：不含任何元素的串，即长度为0。
  • 子序列：抽取串的一些字符，按照原字符串的顺序进行放置的新串。
  • 子串：串中任意连续字符组成的子序列称为该串的子串，其中空串是任意串的子串。
  • 主串：包含子串的串称为该子串的主串。

2. 串的实现方式

串是一种特殊的顺序表，所以实现方式也与顺序表类似，分别以顺序表和链表来实现。

  1. 顺序实现

img

  1. 链式实现

img

3. 串的功能

  1. 串的初始化
  2. 串的生成。
  3. 串的复制。
  4. 判断两个串是否相等。
  5. 返回串的长度。
  6. 链接两个串。
  7. 取子串。
  8. 在串1的指定位置插入串2。
  9. 删除指定位置长度为n的某个子串。

4. 串的声明

4.1. 顺序串

顺序串的存储自然是以顺序表的形式，但是在定义其长度有三种实现方式，如下：

  1. 初始化一个头结点作为长度的存储。

img

但是这种存储有一个明显的缺点就是char类型的最大表示范围为255，所以这种方式并不可取。

  1. 以字符\0作为结束标志。

img

C/C++中的字符串就是以这种实现方式，但是这种实现方式每次求长度都需要遍历整个顺序表。所以在这里也不是特别好。

  1. 添加为结构体成员。

img

这种实现方式相较于前两种更加合理，后续我们也将以这种方式实现。

同时为了方便扩容，我们可以再增加一个结构体成员capacity。

#define MAXSIZE 50
typedef struct string
{
	char *data;
	int length;
	int capacity;
}Sstring;

4.2. 链式串

链式串我们使用单链表来实现，为了方便操作我们可以添加一个头节点。

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

5. 串的初始化

5.1. 顺序串

void StrInit(Sstring* s)//初始化串
{
	char *arr = (char*)malloc(sizeof(char) * MAXSIZE);
	if (arr == NULL)
	{
		perror("malloc fail");
		return;
	}
	s->data = arr;
	s->length = 0;
	s->capacity = MAXSIZE;
}

5.2. 链式串

链式串并不需要单独初始化，可以在具体的实现中初始化。

5.3. 复杂度分析

  • 时间复杂度：顺序串花费时间是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：初始化开辟了MAXSIZE的空间。可以视为O(N)的复杂度。

6. 串的生成

6.1. 顺序串

在对串进行拷贝时，要检查是否需要扩容，放置越界。

void CheckCapacity(Sstring* s, int len)
{
	if (s->length + len > s->capacity)
	{
		char* tmp = (char*)realloc(s->data, sizeof(char) * (s->length + len));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->data = tmp;
		s->capacity = MAXSIZE + len;
	}
}
void StrAssign(Sstring* s, char*str)//生成串
{
	assert(s && str);
	int i = 0;
	int len = strlen(str);
	CheckCapacity(s, len);
	for (i = 0; str[i] != '\0'; i++)
	{
		s->data[i] = str[i];
	}
	s->length = len;
}

6.2. 链式串

链式串每次插入都要生成一个节点，所以我们可以单独封装成一个函数。

LinkStrNode* BuyListNode()
{
	LinkStrNode*tmp= (LinkStrNode*)malloc(sizeof(LinkStrNode));
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	return tmp;
}
void StrAssign(LinkStrNode** s, char*str)
{
	assert(str);
	LinkStrNode* r, * p;
	*s = BuyListNode();
	r = *s;
	for (int i = 0; str[i] != '\0'; ++i)
	{
		p = BuyListNode();
		p->data = str[i];
		r->next = p;	
		r = p;
	}
	r->next = NULL;
}

6.3. 复杂度分析

  • 时间复杂度：无论是顺序串还是链式串都需要遍历一遍目标串，间复杂度可以视为O(N))。
  • 空间复杂度：顺序串可能会扩容，链式串需要开辟等量节点，所以空间复杂度可以视为O(N)。

7. 串的复制

7.1. 顺序串

串的复制也需要检查是否需要扩容，然后再依次拷贝。

void StrCopy(Sstring* s, Sstring* t)//复制串
{
	assert(s && t);
	if (s->capacity < t->capacity)
	{
		char* tmp = (char*)realloc(s->data, sizeof(char) * t->capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->data = tmp;
		s->capacity = t->capacity;
	}
	for (int i = 0; i < t->length; i++)
	{
		s->data[i] = t->data[i];
	}
	s->length = t->length;
}

7.2. 链式串

链式串的拷贝我们采用一种方法：即先将原串销毁，然后再拷贝。

void StrCopy(LinkStrNode** s, LinkStrNode* t)//复杂
{
	assert(t);
	DestroyStr(*s);//销毁
	LinkStrNode* r, * q;
	LinkStrNode* p = t->next;
	*s = BuyListNode();
	r = *s;
	while (p != NULL)
	{
		q = BuyListNode();
		q->data = p->data;		

		r->next = q;
		r = q;			

		p = p->next;
	}
	r->next = NULL;
}

7.3. 复杂度分析

  • 时间复杂度：需要遍历一遍被复制串，所以时间复杂度可以视为O(N)。
  • 空间复杂度：顺序串可能扩容，链式串需要复制等量节点，所以空间复杂度可以视为O(N)。

8. 串的比较

串的比较与C语言中strcmp函数功能类似，都是依次比较串中的字符，直至结束或者出现不同的字符为至。

若大于则返回>0，等于返回0，小于则返回<0。

列如：

  • 当串长度不同时：“aabc”>“abbca”，“aaa”<“aaab”。
  • 当串长度相同时：“acbc”>“bcbc”，“acac”=“acac”。

8.1. 顺序串

int StrCmp(Sstring* s, Sstring* t)//比较两个串
{
	assert(s && t);
	char* p1 = s->data;
	char* p2 = t->data;
	int i = 0;
	while (i < s->length && i < t->length && p1[i] == p2[i])
	{
		i++;
	}
	if (i == s->length&&i==t->length)
	{
		return 0;
	}
	if (i == s->length && i != t->length)
	{
		return -1;
	}
	if (i != s->length && i == t->length)
	{
		return 1;
	}
	return p1[i] - p2[i];
}

8.2. 链式串

int StrCmp(LinkStrNode* s, LinkStrNode* t)//比较两个串
{
	assert(s&&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 0;
	if (p == NULL && q != NULL)
	{
		return -1;
	}
	if (p != NULL && q == NULL)
	{
		return 1;
	}
	return p->data - q->data;
}

8.3. 复杂度分析

  • 时间复杂度：无论是链式串还是顺序串都可能遍历整个串，所以时间复杂度可以视为O(N)
  • 空间复杂度：无论是顺序串还是链式串花费空间是一个常数，所以空间复杂度为O(1)。

9. 返回串的长度

9.1. 顺序串

int StrLength(Sstring* s)//返回串的长度
{
	assert(s);
	return s->length;
}

9.2. 链式串

int StrLength(LinkStrNode* s)//返回串的长度
{
	assert(s);
	int count = 0;
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		count++;
		p = p->next;
	}
	return count;
}

9.3. 复杂度分析

  • 时间复杂度：顺序串是一个常数，所以时间复杂度为O(1)。但是链式串需要遍历整个串，所以为O(N)。
  • 空间复杂度：无论是顺序串还是链式串花费空间是一个常数，所以空间复杂度为O(1)。

10. 链接两个串

链接两个串十分简单，首先找个一个串的末尾，然后再链接即可。

10.1. 顺序串

链接两个串也需要判断该串是否需要扩容。

Sstring Strcat(Sstring* s, Sstring* t)//链接两个串
{
	assert(s && t);
	int len = t->length;
	CheckCapacity(s, len);
	for (int i = s->length; i < s->length + t->length; i++)
	{
		s->data[i] = t->data[i - s->length];
	}
	s->length = s->length + t->length;
	return *s;
}

10.2. 链式串

LinkStrNode*Strcat(LinkStrNode* s, LinkStrNode* t)//链接两个串
{
	assert(s && t);
	LinkStrNode* p = s->next, * q = t->next;
	while (p->next != NULL)
	{
		p = p->next;
	}
	LinkStrNode* str1 = p,*str2;
	while (q != NULL)
	{
		str2 = BuyListNode();
		str2->data =q->data;

		str1->next = str2;
		str1 = str2;

		q = q->next;
	}
	str1->next = NULL;
	return s;
}

10.3. 复杂度分析

  • 时间复杂度：无论是顺序串还是链式串都需要遍历两个串，所以时间复杂度为O(N)。
  • 空间复杂度：顺序串可能会扩容，链式串需要开辟等量节点，所以空间复杂度为O(N)

11. 取子串

我们通过传入的目标位置与长度来截取一段子串返回，如果长度过大则截取后续所有字符。

11.1. 顺序串

Sstring SubStr(Sstring* s, int i, int len)//取子串
{
	assert(i < s->length);
	assert(s);
	Sstring str;
	str.data = (char*)malloc(sizeof(char) * s->capacity);
	if (str.data == NULL)
	{
		perror("malloc fail");
		return *s;
	}
	str.capacity = s->capacity;
	if (i + len >= s->length)
	{
		for (int pos = i; pos < s->length; pos++)
		{
			str.data[pos-i] = s->data[pos];
		}
		str.length = s->length - i;
	}
	else
	{
		for (int pos = i; pos < i+len; pos++)
		{
			str.data[pos - i] = s->data[pos];
		}
		str.length = len;
	}
	return str;
}

11.2. 链式串

LinkStrNode*SubStr(LinkStrNode* s, int i, int len)//取子串
{
	assert(s);
	assert(i <= StrLength(s));
	int count = 0;
	LinkStrNode* r, * p;
	p = s->next;//跳过头节点
	r = BuyListNode();
	while (p != NULL)//找到第i个位置
	{
		count++;
		if (count == i)
		{
			break;
		}
		p = p->next;
	}
	LinkStrNode* str1=r,*str2;
	while (len--&&p!=NULL)
	{
		str2 = BuyListNode();
		str2->data = p->data;
		str1->next = str2;
		str1 = str2;
		p = p->next;
	}
	str1->next = NULL;//末尾置空
	return r;
}

11.3. 复杂度分析

  • 时间复杂度：都可能遍历整个串，所以时间复杂度为O(N)。
  • 空间复杂度：都需要开辟len个大小的空间，所以空间复杂度可以视为O(N)。

12. 指定位置插入

12.1. 顺序串

指定位置插入也许检查是否扩容，然后指定位置后续字符移动len个单位。

img

img

Sstring InsStr(Sstring* s1, int i, Sstring* s2)//指定位置插入
{
	assert(s1 && s2);
	assert(i < s1->length);
	int len = s2->length;
	CheckCapacity(s1, len);
	for (int pos = s1->length - 1; pos >= i; pos--)
	{
		s1->data[pos + len] = s1->data[pos];
	}
	for (int pos = i; pos < i + len; pos++)
	{
		s1->data[pos] = s2->data[pos - i];
	}
	s1->length += len;
	return *s1;
}

12.2. 链式串

LinkStrNode*InsStr(LinkStrNode* s1, int i, LinkStrNode* s2)//指定位置插入
{
	assert(s1&&s2);
	assert(i <= StrLength(s1));
	int count = 0;
	LinkStrNode* r, * p,*q;
	q=p = s1->next;//q为i之前的位置
	while (p != NULL)//找到第i个位置
	{
		count++;
		if (count == i)
		{
			break;
		}
		q = p;//记录前一个位置
		p = p->next;
	}
	r = q;
	LinkStrNode* str;
	LinkStrNode* ptr=s2->next;//跳过头节点
	while (ptr != NULL)
	{
		str = BuyListNode();
		str->data = ptr->data;
		r->next = str;
		r = str;
		ptr = ptr->next;
	}
	r->next= p;//链接
	return s1;
}

12.3. 复杂度分析

  • 时间复杂度：顺序串需要移动覆盖，链式串需要寻找目标位置，时间复杂度都可以视为O(N)。
  • 空间复杂度：顺序串可能扩容，链式串需要开辟等量空间，空间复杂度都可以视为O(N)。

13. 指定删除子串

13.1. 顺序串

如果删除的长度过长，只需要修改串的length。否则需要从前往后覆盖。

Sstring DelStr(Sstring* s, int i, int len)//指定删除子串
{
	assert(i < s->length);
	assert(s);
	if (i + len >=s->length)
	{
		s->length = i ;
	}
	else
	{
		for (int pos = i+len; pos <s->length; pos++)
		{
			s->data[pos-len] = s->data[pos];
		}
		s->length -= len;
	}
	return *s;
}

13.2. 链式串

LinkStrNode* DelStr(LinkStrNode* s, int i, int len)//指定删除子串
{
	assert(s);
	assert(i < StrLength(s));
	int count = 0;
	LinkStrNode* r, * p;
	p = s->next;
	r = p;//r为前一个节点
	while (p != NULL)
	{
		count++;
		if (count == i)
		{
			break;
		}
		r = p;
		p = p->next;
	}
	while (len-- && p != NULL)
	{
		LinkStrNode* str = p->next;
		free(p);
		p = str;
	}
	r->next = p;
	return s;
}

13.3. 复杂度分析

  • 时间复杂度：顺序串可能需要移动覆盖，链式串需要寻找目标位置，时间复杂度都可以视为O(N)。
  • 空间复杂度：顺序串与链式串都不需要开辟格外空间，空间复杂度都可以视为O(1)。

14. 串的打印

14.1. 顺序串

void PrintStr(Sstring* s)
{
	assert(s);
	char* p = s->data;
	for (int i = 0; i < s->length; i++)
	{
		printf("%c", p[i]);
	}
	printf("\n");
}

14.2. 链式串

void PrintStr(LinkStrNode* s)//打印
{
	assert(s);
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}

14.3. 复杂度分析

  • 时间复杂度：无论是顺序串还是链式串都需要遍历整个串，所以时间复杂度为O(N)。
  • 空间复杂度：顺序串与链式串都不需要开辟格外空间，空间复杂度都可以视为O(1)。

15. 串的销毁

15.1. 顺序串

void StrDestroy(Sstring* s)//销毁串
{
	free(s->data);
	s->data = NULL;
	s->length = s->capacity = 0;
}

15.2. 链式串

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

15.3. 复杂度分析

  • 时间复杂度：顺序串消耗时间固定，时间复杂度为O(1)。链式串需要遍历这个串，时间复杂度为O(N)
  • 空间复杂度：顺序串与链式串都不需要开辟格外空间，空间复杂度都可以视为O(1)。

16. 对比与应用

16.1. 对比

因为串也是一种顺序表，所以无论是顺序表还是链式串的优劣都与顺序表与链表差不多。这里就不在赘述。

16.2. 应用

串在计算机领域有着广泛的应用：

  1. **文本处理：**文本编辑器或处理器中，文本被表示为一个字符串，可以进行查找、替换、插入、删除等操作
  2. 加密和安全：加密算法中经常使用字符串表示数据，例如对称加密和非对称加密中的密钥和明文。

17. 完整代码

17.1. 顺序串

17.1.1. Sstring.h
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
#define MAXSIZE 50
typedef struct string
{
	char *data;
	int length;
	int capacity;
}Sstring;
void StrInit(Sstring* s);//初始化串
void StrAssign(Sstring* s, char str[]);//生成串
void StrCopy(Sstring* s, Sstring*t);//复制串
int StrCmp(Sstring*s, Sstring*t);//比较两个串
int StrLength(Sstring*s);//返回串的长度
Sstring Strcat(Sstring*s, Sstring*t);//链接两个串
Sstring SubStr(Sstring* s, int i, int len);//取子串
Sstring InsStr(Sstring* s1, int i, Sstring* s2);//指定位置插入
Sstring DelStr(Sstring* s, int i, int len);//指定删除子串
void PrintStr(Sstring* s);//打印
void StrDestroy(Sstring* s);//销毁串
17.1.2. Sstring.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sstring.h"
void CheckCapacity(Sstring* s, int len)
{
	if (s->length + len > s->capacity)
	{
		char* tmp = (char*)realloc(s->data, sizeof(char) * (s->length + len));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->data = tmp;
		s->capacity = MAXSIZE + len;
	}
}
void StrInit(Sstring* s)//初始化串
{
	char *arr = (char*)malloc(sizeof(char) * MAXSIZE);
	if (arr == NULL)
	{
		perror("malloc fail");
		return;
	}
	s->data = arr;
	s->length = 0;
	s->capacity = MAXSIZE;
}
void StrAssign(Sstring* s, char*str)//生成串
{
	assert(s && str);
	int i = 0;
	int len = strlen(str);
	CheckCapacity(s, len);
	for (i = 0; str[i] != '\0'; i++)
	{
		s->data[i] = str[i];
	}
	s->length = len;
}
void StrCopy(Sstring* s, Sstring* t)//复制串
{
	assert(s && t);
	if (s->capacity < t->capacity)
	{
		char* tmp = (char*)realloc(s->data, sizeof(char) * t->capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->data = tmp;
		s->capacity = t->capacity;
	}
	for (int i = 0; i < t->length; i++)
	{
		s->data[i] = t->data[i];
	}
	s->length = s->length > t->length ? s->length : t->length;
}
int StrCmp(Sstring* s, Sstring* t)//比较两个串
{
	assert(s && t);
	char* p1 = s->data;
	char* p2 = t->data;
	int i = 0;
	while (i < s->length && i < t->length && p1[i] == p2[i])
	{
		i++;
	}
	if (i == s->length&&i==t->length)
	{
		return 0;
	}
	if (i == s->length && i != t->length)
	{
		return -1;
	}
	if (i != s->length && i == t->length)
	{
		return 1;
	}
	return p1[i] - p2[i];
}
int StrLength(Sstring* s)//返回串的长度
{
	assert(s);
	return s->length;
}
Sstring Strcat(Sstring* s, Sstring* t)//链接两个串
{
	assert(s && t);
	int len = t->length;
	CheckCapacity(s, len);
	for (int i = s->length; i < s->length + t->length; i++)
	{
		s->data[i] = t->data[i - s->length];
	}
	s->length = s->length + t->length;
	return *s;
}
Sstring SubStr(Sstring* s, int i, int len)//取子串
{
	assert(i < s->length);
	assert(s);
	Sstring str;
	str.data = (char*)malloc(sizeof(char) * s->capacity);
	if (str.data == NULL)
	{
		perror("malloc fail");
		return *s;
	}
	str.capacity = s->capacity;
	if (i + len >= s->length)
	{
		for (int pos = i; pos < s->length; pos++)
		{
			str.data[pos-i] = s->data[pos];
		}
		str.length = s->length - i;
	}
	else
	{
		for (int pos = i; pos < i+len; pos++)
		{
			str.data[pos - i] = s->data[pos];
		}
		str.length = len;
	}
	return str;
}
Sstring InsStr(Sstring* s1, int i, Sstring* s2)//指定位置插入
{
	assert(s1 && s2);
	assert(i < s1->length);
	int len = s2->length;
	CheckCapacity(s1, len);
	for (int pos = s1->length - 1; pos >= i; pos--)
	{
		s1->data[pos + len] = s1->data[pos];
	}
	for (int pos = i; pos < i + len; pos++)
	{
		s1->data[pos] = s2->data[pos - i];
	}
	s1->length += len;
	return *s1;
}
Sstring DelStr(Sstring* s, int i, int len)//指定删除子串
{
	assert(i < s->length);
	assert(s);
	if (i + len >=s->length)
	{
		s->length = i ;
	}
	else
	{
		for (int pos = i+len; pos <s->length; pos++)
		{
			s->data[pos-len] = s->data[pos];
		}
		s->length -= len;
	}
	return *s;
}
void PrintStr(Sstring* s)
{
	assert(s);
	char* p = s->data;
	for (int i = 0; i < s->length; i++)
	{
		printf("%c", p[i]);
	}
	printf("\n");
}
void StrDestroy(Sstring* s)//销毁串
{
	free(s->data);
	s->data = NULL;
	s->length = s->capacity = 0;
}

17.2. 链式串

17.2.1. Sstring.h
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
typedef struct snode 
{
	char data;
	struct snode* next;
}LinkStrNode;
void StrInit(LinkStrNode* s);//初始化串
void StrAssign(LinkStrNode**s, char str[]);//生成串
void StrCopy(LinkStrNode**s, LinkStrNode*t);//复制串
int StrCmp(LinkStrNode*s, LinkStrNode*t);//比较两个串
int StrLength(LinkStrNode*s);//返回串的长度
LinkStrNode*Strcat(LinkStrNode*s, LinkStrNode*t);//链接两个串
LinkStrNode*SubStr(LinkStrNode* s, int i, int len);//取子串
LinkStrNode*InsStr(LinkStrNode* s1, int i, LinkStrNode* s2);//指定位置插入
LinkStrNode*DelStr(LinkStrNode* s, int i, int len);//指定删除子串
void PrintStr(LinkStrNode* s);//打印
void DestroyStr(LinkStrNode* s);//销毁串
17.2.2. Sstring.c
#include"Sstring.h"
LinkStrNode* BuyListNode()
{
	LinkStrNode*tmp= (LinkStrNode*)malloc(sizeof(LinkStrNode));
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	return tmp;
}
void StrAssign(LinkStrNode** s, char*str)
{
	assert(str);
	LinkStrNode* r, * p;
	*s = BuyListNode();
	r = *s;
	for (int i = 0; str[i] != '\0'; ++i)
	{
		p = BuyListNode();
		p->data = str[i];
		r->next = p;	
		r = p;
	}
	r->next = NULL;
}

void StrCopy(LinkStrNode** s, LinkStrNode* t)
{
	assert(t);
	DestroyStr(*s);
	LinkStrNode* r, * q;
	LinkStrNode* p = t->next;
	*s = BuyListNode();
	r = *s;
	while (p != NULL)
	{
		q = BuyListNode();
		q->data = p->data;		

		r->next = q;
		r = q;			

		p = p->next;
	}
	r->next = NULL;
}

int StrCmp(LinkStrNode* s, LinkStrNode* t)//比较两个串
{
	assert(s&&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 0;
	if (p == NULL && q != NULL)
	{
		return -1;
	}
	if (p != NULL && q == NULL)
	{
		return 1;
	}
	return p->data - q->data;
}
int StrLength(LinkStrNode* s)//返回串的长度
{
	assert(s);
	int count = 0;
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		count++;
		p = p->next;
	}
	return count;
}
LinkStrNode*Strcat(LinkStrNode* s, LinkStrNode* t)//链接两个串
{
	assert(s && t);
	LinkStrNode* p = s->next, * q = t->next;
	while (p->next != NULL)
	{
		p = p->next;
	}
	LinkStrNode* str1 = p,*str2;
	while (q != NULL)
	{
		str2 = BuyListNode();
		str2->data =q->data;

		str1->next = str2;
		str1 = str2;

		q = q->next;
	}
	str1->next = NULL;
	return s;
}
LinkStrNode*SubStr(LinkStrNode* s, int i, int len)//取子串
{
	assert(s);
	assert(i <= StrLength(s));
	int count = 0;
	LinkStrNode* r, * p;
	p = s->next;//跳过头节点
	r = BuyListNode();
	while (p != NULL)//找到第i个位置
	{
		count++;
		if (count == i)
		{
			break;
		}
		p = p->next;
	}
	LinkStrNode* str1=r,*str2;
	while (len--&&p!=NULL)
	{
		str2 = BuyListNode();
		str2->data = p->data;
		str1->next = str2;
		str1 = str2;
		p = p->next;
	}
	str1->next = NULL;//末尾置空
	return r;
}
LinkStrNode*InsStr(LinkStrNode* s1, int i, LinkStrNode* s2)//指定位置插入
{
	assert(s1&&s2);
	assert(i <= StrLength(s1));
	int count = 0;
	LinkStrNode* r, * p,*q;
	q=p = s1->next;//q为i之前的位置
	while (p != NULL)//找到第i个位置
	{
		count++;
		if (count == i)
		{
			break;
		}
		q = p;//记录前一个位置
		p = p->next;
	}
	r = q;
	LinkStrNode* str;
	LinkStrNode* ptr=s2->next;//跳过头节点
	while (ptr != NULL)
	{
		str = BuyListNode();
		str->data = ptr->data;
		r->next = str;
		r = str;
		ptr = ptr->next;
	}
	r->next= p;//链接
	return s1;
}
LinkStrNode* DelStr(LinkStrNode* s, int i, int len)//指定删除子串
{
	assert(s);
	assert(i < StrLength(s));
	int count = 0;
	LinkStrNode* r, * p;
	p = s->next;
	r = p;//r为前一个节点
	while (p != NULL)
	{
		count++;
		if (count == i)
		{
			break;
		}
		r = p;
		p = p->next;
	}
	while (len-- && p != NULL)
	{
		LinkStrNode* str = p->next;
		free(p);
		p = str;
	}
	r->next = p;
	return s;
}
void PrintStr(LinkStrNode* s)//打印
{
	assert(s);
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}
void DestroyStr(LinkStrNode* s)//销毁
{
	LinkStrNode* pre = s, * p = s->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/544719.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

关于机器学习/深度学习的一些事-答知乎问（四）

关于机器学习/深度学习的一些事-答知乎问（四）

如何评估和量化深度学习的可解释性问题&#xff1f; 针对深度学习模型&#xff0c;评估指标能够全面衡量模型是否满足可解释性。与分类的评估指标&#xff08;准确度、精确度和召回率&#xff09;一样&#xff0c;模型可解释性的评估指标应能从特定角度证明模型的性能。但是&a…
阅读更多...
AI服务平台replicate

AI服务平台replicate

Replicate是一个提供优秀AI模型和工具的平台&#xff0c;旨在帮助用户实现各种人工智能任务。该平台汇集了来自各个领域的顶尖模型&#xff0c;涵盖了文本到图像生成、语言模型、图像编辑、超分辨率等多个领域。用户可以通过Replicate平台快速获取和应用先进的模型&#xff0c;…
阅读更多...
基于Springboot的毕业生信息招聘平台

基于Springboot的毕业生信息招聘平台

基于SpringbootVue的毕业生信息招聘平台的设计与实现 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringbootMybatis工具&#xff1a;IDEA、Maven、Navicat 系统展示 用户登录 首页展示 空中宣讲会 招聘岗位 求职信息 论坛信息 招聘咨询 …
阅读更多...
代码随想录算法练习Day13:有效的字母异位词

代码随想录算法练习Day13:有效的字母异位词

题目&#xff1a; 给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意&#xff1a;若 s 和 t 中每个字符出现的次数都相同&#xff0c;则称 s 和 t 互为字母异位词。 题目链接&#xff1a;242.有效的字母异位词 卡哥的视频讲解&#xff…
阅读更多...
kali工具----网络映射器（Network Mapper）系统指纹

kali工具----网络映射器（Network Mapper）系统指纹

系统指纹识别 现在一些便携式计算机操作系统使用指纹识别来验证密码进行登录。指纹识别是识别系统的一个典型模式&#xff0c;包括指纹图像获取、处理、特征提取和对等模块。如果要做渗透测试&#xff0c;需要了解要渗透测试的操作系统的类型才可以。本节将介绍使用Nmap工具测试…
阅读更多...
小米温度计接入HA后，手机米家app里温度计就看不到温度数值了

小米温度计接入HA后，手机米家app里温度计就看不到温度数值了

环境&#xff1a; 小米温度计 HA OS Core 2023.12.1 Supervisor 2024.04.0 Operating System 11.1 问题描述&#xff1a; 小米温度计接入HA后&#xff0c;手机米家app里和HA里面温度计就看不到温度数值了 解决方案&#xff1a; 1.前往米家APP&#xff0c;解绑温度计和本地…
阅读更多...
都2024年了，线上部署你不会只会log 调试吧，Arthas了解下！

都2024年了，线上部署你不会只会log 调试吧，Arthas了解下！

文章目录 一、什么是Arthas&#xff1f;⛅背景⚡Arthas能为我们做什么 二、部署Arthas三、Arthas 基础命令四、Arthas 项目命令实战⌚thread 线程阻塞⏰watch命令演示⚡cpu飙升演示⛽方法演示 &#x1f6a8;小结 一、什么是Arthas&#xff1f; Arthas 是一款线上监控诊断产品&a…
阅读更多...
264：vue+openlayers 坐标转换 WGS84-GCJ02-BD09

264：vue+openlayers 坐标转换 WGS84-GCJ02-BD09

第264个 点击查看专栏目录 本示例演示如何在vue+openlayers中将 WGS84坐标转化为GCJ02坐标，然后再转换为BD09坐标，本示例中使用的是高德地图，所以转换来的GCJ02坐标是正确的位置。 84坐标系可以理解为是真实坐标系，是一个地点的实际坐标值。02坐标系是加密后的坐标系，是为…
阅读更多...
[通俗易懂:Linux标准输入/输出和重定向]Shell脚本之 ＞ /dev/null 2＞1命令详解

[通俗易懂:Linux标准输入/输出和重定向]Shell脚本之 ＞ /dev/null 2＞1命令详解

目录标题 一、> /dev/null 2>&1 命令解析二、/dev/null 文件浅显理解三、标准输入、标准输出、标准错误输出四、输入重定向、输出重定向五、命令作用与应用场景 如果想看命令意义&#xff0c;可以直接跳到第五部分 一、> /dev/null 2>&1 命令解析 我们在别…
阅读更多...
【Python深度学习系列】网格搜索选择神经网络超参数：隐含层神经元数量（案例+源码）

【Python深度学习系列】网格搜索选择神经网络超参数：隐含层神经元数量（案例+源码）

这是我的第259篇原创文章。 一、引言 在深度学习中&#xff0c;超参数是指在训练模型时需要手动设置的参数&#xff0c;它们通常不能通过训练数据自动学习得到。超参数的选择对于模型的性能至关重要&#xff0c;因此在进行深度学习实验时&#xff0c;超参数调优通常是一个重要的…
阅读更多...
探索 SAM 在遥感方面的能力

探索 SAM 在遥感方面的能力

分割任意模型 (SAM) 现在可在不同类型的数据（例如近距离图像和航空图像）中自由克隆和使用。在我看来，SAM 模型在近距离图像上效果更好，因为这些图像对目标特征和物体有独特的视角，使模型更容易准确地区分和分割它们。 现在，我们将探讨 SAM 模型在不同遥感数据上的能力，包…
阅读更多...
软考128-上午题-【软件工程】-白盒测试

软考128-上午题-【软件工程】-白盒测试

一、白盒测试&#xff08;结构测试&#xff09; 白盒测试也称为结构测试&#xff0c;根据程序的内部结构和逻辑来设计测试用例&#xff0c;对程序的路径和过程进行测试&#xff0c;检查是否满足设计的需要。 白盒测试常用的技术是&#xff1a;逻辑覆盖、循环覆盖和基本路径测…
阅读更多...
Web前端 JavaScript笔记4

Web前端 JavaScript笔记4

1、元素内容 属性名称说明元素名.innerText输出一个字符串&#xff0c;设置或返回元素中的内容&#xff0c;不识别html标签元素名.innerHTML输出一个字符串&#xff0c;设置或返回元素中的内容&#xff0c;识别html标签元素名.textContent设置或返回指定节点的文本内容&#x…
阅读更多...
LeetCode 678——有效的括号字符串

LeetCode 678——有效的括号字符串

阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 需要两个栈&#xff0c;一个用来保存左括号所在的位置索引&#xff0c;一个用来保存星号所在的位置索引。 从左往右遍历字符串&#xff0c;如果是左括号或者星号&#xff0c;则将位置索引分别入栈&#xff0c;如…
阅读更多...
linux shell脚本编写（2）

linux shell脚本编写（2）

Shell: 命令转换器&#xff0c;高级语言转换成二进制语言。是Linux的一个外壳&#xff0c;它包在Lniux内核的外面&#xff0c;用户和内核之间的交互提供了一个接口。 内置命令&#xff1a;在shell内部不需要shell编辑 外置命令&#xff1a;高级语言要用shell转换成二进制语言 …
阅读更多...
机器学习 | 使用Scikit-Learn实现分层抽样

机器学习 | 使用Scikit-Learn实现分层抽样

在本文中&#xff0c;我们将学习如何使用Scikit-Learn实现分层抽样。 什么是分层抽样&#xff1f; 分层抽样是一种抽样方法&#xff0c;首先将总体的单位按某种特征分为若干次级总体&#xff08;层&#xff09;&#xff0c;然后再从每一层内进行单纯随机抽样&#xff0c;组成…
阅读更多...
Kubernetes的Ingress Controller

Kubernetes的Ingress Controller

前言 Kubernetes暴露服务的方式有一下几种&#xff1a;LoadBlancer Service、ExternalName、NodePort Service、Ingress&#xff0c;使用四层负载均衡调度器Service时&#xff0c;当客户端访问kubernetes集群内部的应用时&#xff0c;数据包的走向如下面流程所示&#xff1a;C…
阅读更多...
计算机三级数据库技术备考笔记（十四）

计算机三级数据库技术备考笔记（十四）

第十四章 数据仓库与数据挖掘 决策支持系统的发展 决策支持系统及其演化 操作型数据(Operalional Data)是指由企业的基本业务系统所产生的数据,操作型数据及相应数据处理所处的环境,即用于支持企业基本业务应用的环境,一般被称为联机事务处理(0nLine Transaction Processing,0…
阅读更多...
COMSOL多孔介质流仿真

COMSOL多孔介质流仿真

使用Comsol进行多孔介质流仿真_哔哩哔哩_bilibili 目录 多孔介质 饱和多孔介质中的流动 达西定律 Brinkman方程&#xff1a;用于过渡区 裂隙流 变饱和多孔介质流 理查兹方程 多孔介质多相流 多物理场耦合 多孔介质中的传热 多孔弹性接口 多孔介质稀物质传递 多孔介质…
阅读更多...
c# 无处不在的二分搜索

c# 无处不在的二分搜索

我们知道二分查找算法。二分查找是最容易正确的算法。我提出了一些我在二分搜索中收集的有趣问题。有一些关于二分搜索的请求。我请求您遵守准则&#xff1a;“我真诚地尝试解决问题并确保不存在极端情况”。阅读完每个问题后&#xff0c;最小化浏览器并尝试解决它。 …
阅读更多...
最新文章

Copyright @ 2022~2023