1.串的实现
1.1 串的定义
-
定义
串，即字符串，是由零个或多个字符组成的有限序列。
串是一种特殊的线性表，数据元素间呈线性关系。
- 空串：串长度为0时；
- 子串：串中任意个连续的字符组成的子序列；
- 主串：包含子串的串；
- 字符在主串中的位置：字符在串中的符号；
- 子串在主串中的位置：子串的第一个字符在主串中的位置。
-
静态数组实现（定长顺序存储）
typedef struct{ char ch[MaxSize]; //用数组存储字符 int length; //串的长度 }SString; -
动态数组实现（堆分配存储）
用完需要手动free
typedef struct{ char*ch; //按串长分配存储区，ch指向串的基地址 int length; //串的长度 }HString; -
串的顺序存储
-
串的链式存储
typedef struct StringNode{ char ch[4]; //每个结点存多个字符，提高存储密度 struct StringNode *next; }StringNode,*String;
1.2 串的基本操作
- 基于静态数组
1.2.1 求子串
//用sub返回串s的第pos位置长度为len的子串
bool SubString(SString &Sub,SString S,int pos,int len){
if(pos+1en-1>S.length)return false; //子串越界
for(int i=pos;i<pos+len;i++){
Sub.ch[i-pos+1]=S.ch[i]
}
Sub.length=len;
return true;
}
1.2.2 比大小
-
字符串的大小比较方法：
从左往右逐个比较，哪个字符的编码大，就哪个串更加大；
若前面的字符都相同，哪个串长就哪个大。
//若S>T,返回值>0；若S=T，返回值=0；若S<T，返回值<0.
int StrCompare(SString S,SString T){
for(int i=1;i<=S.length&&i<=T.length;i++){
if(S.ch[i]!=T.ch[i])
return S.ch[i]-T.ch[i];
}
//扫描过的所有字符都相同，则长度长的串长
return S.length-T.length;
}
1.2.3 定位操作
- 若主串S中存在与T值相同的子串，则返回它在主串中第一次出现的位置，否则函数值为0。
int Index(SString S,SString T){
int i=1，n=StrLength(S),m=StrLength(T);
SString sub;
while(i<=n-m+1){
SubString(sub,S,i,m); //sub存放从i位置起，长为len的可能子串
if(StrCompare(sub,T)!=0) //如果不是子串，下一位置继续
i++;
else
return i;
}
return 0;
}
*完整代码 串
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define MaxSize 99
//定长顺序存储
typedef struct {
char ch[MaxSize];
int length;
}SString;
//赋值操作
//把T赋值为chars
void StrAssign(SString& T, char chars[]) {
for (int i = 0; i < strlen(chars); i++) {
T.ch[i + 1] = chars[i];
}
T.length = strlen(chars);
}
//复制操作
//由S复制得到T
void StrCopy(SString& T, SString S) {
T.length = S.length;
for (int i = 1; i <= T.length; i++) {
T.ch[i] = S.ch[i];
}
}
//判空
bool StrEmpty(SString S) {
if (S.length == 0)
return true;
else
return false;
}
//比较
//若S>T,返回值>0；若S=T，返回值=0；若S<T，返回值<0.
int StrCompare(SString S, SString T) {
for (int i = 1; i <= S.length && i <= T.length; i++){
if (S.ch[i] != T.ch[i])
return S.ch[i] - T.ch[i];
}
return S.length - T.length;
}
//求子串
//用sub返回串s的第pos位置长度为len的子串
bool SubString(SString& Sub, SString S, int pos, int len) {
if (pos + len - 1 > S.length)return false;
for (int i = pos; i < pos + len; i++) {
Sub.ch[i - pos + 1] = S.ch[i];
}
Sub.length = len;
return true;
}
//串连接
//用T返回由S1、S2组成的新串
void Concat(SString& T, SString S1, SString S2) {
T.length = S1.length + S2.length;
for (int i = 1; i <= T.length; i++) {
if (i <= S1.length) {
T.ch[i] = S1.ch[i];
}
else {
T.ch[i] = S2.ch[i - S1.length];
}
}
}
//定位
//若主串S中存在与T值相同的子串，则返回它在主串中第一次出现的位置，否则函数值为0。
int Index(SString S, SString T) {
int i = 1;
SString sub;
while (i < S.length - T.length + 1) {
SubString(sub, S, i, T.length);
if (StrCompare(sub, T) != 0)
i++;
else
return i;
}
return 0;
}
//清空
void ClearString(SString &S) {
S.length = 0;
}
void PrintS(SString S) {
printf("Str:");
for (int i = 1; i <= S.length; i++)
printf("%c", S.ch[i]);
printf("\n");
//printf(" , Length: %d\n", S.length);
}
int main() {
SString str1, str2, result, sub;
char c1[] = "Hello", c2[] = "World";
StrAssign(str1, c1);
StrAssign(str2, c2);
printf("\nAssign:\n");
PrintS(str1);
PrintS(str2);
// 测试复制操作
printf("\nCopy:\n");
StrCopy(result, str1);
PrintS(result);
// 测试判空操作
printf("\nStr1 is empty: %s\n", StrEmpty(str1) ? "Yes" : "No");
// 测试比较操作
printf("\nCompare Str1 and Str2: %d\n", StrCompare(str1, str2));
// 测试求子串操作
if (SubString(sub, str1, 2, 3)) {
printf("\nSubString of Str1 from 2, length 3: \n");
PrintS(sub);
}
else {
printf("\nSubString operation failed.\n");
}
// 测试串连接操作
Concat(result, str1, str2);
printf("\nConcatenated Str1 and Str2: \n");
PrintS(result);
// 测试定位操作
char c3[] = "ll";
StrAssign(sub, c3);
printf("\nIndex of 'll' in Str1: %d\n", Index(str1, sub));
// 测试清空操作
ClearString(str1);
printf("\nAfter Clear Str1: Length: %d\n", str1.length);
return 0;
}
