数据结构——串

大家好，欢迎来到IT知识分享网。

• 语言：C语言
• 软件：Visual Studio 2022
• 笔记书籍：数据结构——用C语言描述
• 如有错误，感谢指正。若有侵权请联系博主

 一、串的基本概念

子串：串中任意连续的字符组成的子序列称为该串的子串。

主串：包含子串的串称为主串。即，子串是主串的一部分。

子串在主串中的位置：通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

串相等：当且仅当两个串的值相等时，称这两个串是相等的，即只有当两个串的长度相等，并且每个对应位置的字符都相等时才为串相等。

串的抽象数据类型定义

ADT String{ 数据对象：D={a(n)|a(n)∈CharacterSet,n=1,2,...,n,n>=0} 结构关系：R={<a(n),a(n+1)> | a(n),a(n+1)∈D,i=1,...,n-1,n>=1} 基本操作： 1、StrAssign(S,chars) 操作前提：chars时字符串常量 操作结果：生成一个值等于chars的串s。 2、StrInsert(S,pos,T) 操作前提：串S存在，1<=pos<=StrLength(S)+1。 操作结果：在串S的第pos个字符之前插入串T。 3、StrDelete(S,pos,len) 操作前提：串S存在，1<=pos<=StrLength(S)+1。 操作结果：从串S中删除第pos个字符起长度为len的子串。 4、StrCopy(S,T) 操作前提：串S存在。 操作结果：由串T复制的串S。 5、StrEmpty(S) 操作前提：串S存在。 操作结果：若串S为空串，则返回TRUE，否则返回FALSE。 6、StrCompare(S,T) 操作前提：串S和T存在。 操作结果：若S>T，则返回值大于0；如S=T，则返回值0；若S<T，则返回值小于0。 7、StrLength(S) 操作前提：串S存在。 操作结果：返回串S的长度，即串S中的字符个数。 8、StrClear(S) 操作前提：串S存在。 操作结果：将S清为空串。 9、StrCat(S,T) 操作前提：串S和T存在。 操作结果：将串T的值连接在串S的后面。 10、SubString(Sub,S,pos,len) 操作前提：串S存在，1<=pos<=StrLength(S)且1<=len<=StrLength(S)-pos+1。 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。 11、StrIndex(S,pos,T) 操作前提：串S和T存在，T是非空串，1<=pos<=StrLength(S)。 操作结果：若串S中存在和串T相同的子串，则返回它在串S中第pos个字符之后第一个出现的位置；否则返回0。 12、StrReplace(S,T,V) 操作前提：串S、T和V存在，且T是非空串。 操作结果：用V替换串S中出现的所有与T相等的不重叠的子串。 13、StrDestroy(S) 操作前提：串S存在。 操作结果：销毁串S。 }

二、串的存储实现——定长顺序串

定长顺序串是将串设计成一种静态结构类型，串的存储分配是在编译时完成的。与前面所讲的线性表的顺序存储结构类似，可用一组地址连续的存储单元来存储串的字符序列。

1.定长顺序串存储结构

typedef struct { char ch[MAXString]; int len; }SString;

2.StrAssign初始化字符串

int StrAssign(SString *S,const char *chars) { S->len = 0; if (*chars == NULL) return TRUE; if (strlen(chars)>MAXString) return FALSE; while(chars[S->len] != '\0') { S->ch[S->len] = chars[S->len]; S->len++; } return TRUE; }

3.StrInsert在第pos个字符前插入字符串T

int StrInsert(SString* S, int pos, SString T) { if (pos<1 || pos>S->len+1) return FALSE; int i; if (S->len + T.len <= MAXString) { printf("S的长度%d，T的长度%d\n", S->len, T.len); for (i = S->len + T.len - 1; i >= T.len -1 + pos; i--){ S->ch[i] = S->ch[i - T.len]; } for (i = 0; i < T.len; i++) S->ch[i - 1 + pos] = T.ch[i]; S->len = S->len + T.len; } else if (pos + T.len <= MAXString) { for (i = MAXString; i > T.len + pos; i--) S->ch[i] = S->ch[i - T.len+1]; for (i = 0; i < T.len; i++)S->ch[i + pos] = T.ch[i]; S->len = MAXString; } else { for (i = 0; i < MAXString - pos; i++) S->ch[i + pos] = T.ch[i]; S->len = MAXString; } return TRUE; }

在进行顺序串的插入时，插入位置pos将串分为俩部分（假设为A、B，长度为LA、LB）及待插入部分（假设C，长度为LC），则串由插入前的AB变为ACB。由于时顺序串，插入会引起元素的移动，可能出现一下三种情况：

1. 插入后串长（LA+LC+LB）<=MAXString，则将B往后移LC个元素位置，再将C插入。
2. 插入后串长>MAXSting且pos+LC<MAXSting,则B后移会有部分字符被舍弃。
3. 插入后串长>MAXSting且pos+LC>MAXSting，则B的全部字符被舍弃（不需要后移），并且C在插入时也有部分字符被舍弃。

4.StrDelete删除S中从pos个字符起长度为len的子串

int StrDelete(SString* S, int pos, int len) { if (pos<1 || pos>(S->len - len + 1)) return FALSE; for (int i = pos + len - 1; i < S->len; i++) S->ch[i-len] = S->ch[i]; S->len -= len; return TRUE; }

5.StrCopy复制字符串

void StrCopy(SString *S, SString T) { //由后边参数复制的前边参数，即由T复制得S for (int i = 0; i < T.len; i++) S->ch[i] = T.ch[i]; S->len = T.len; }

6.StrEmpty判断字符串是否为空

int StrEmpty(SString* S) { if (S->len == 0) return TRUE; return FALSE; }

7.StrCompare判断俩字符串是否相等

int StrCompare(SString S, SString T) { int i; for (i = 0; i < S.len && i < T.len; i++) if (S.ch[i] != T.ch[i]) return(S.ch[i] - T.ch[i]); return S.len - T.len; }

8.StrLength获取字符串的长度

int StrLength(SString *S) { return S->len; }

9.StrClear将串清空为空串

void StrClear(SString* S) { for (int i = 0; i < MAXString; i++) S->ch[i] = NULL; S->len = 0; }

10.StrCat连接字符串

void StrCat(SString* S, SString T) { //将T连接在串S后边 if (S->len + T.len <= MAXString) { for (int i = 0; i < T.len; i++) S->ch[i + S->len] = T.ch[i]; S->len = S->len + T.len; } else { for (int i = 0; S->len + i < MAXString; i++) S->ch[i + S->len] = T.ch[i]; S->len = MAXString - 1; } }

11.SubString用一个串返回第pos个字符起长度为len的子串

int SubString(SString *Sub,SString S,int pos,int len) { if (pos<1 || pos>S.len || 1 > len || len > S.len - pos + 1) return FALSE; for (int i = 0; i < len; i++) Sub->ch[i] = S.ch[((pos - 1) + i)]; Sub->len = len; return TRUE; }

12.StrIndex定位函数

int StrIndex(SString S, int pos, SString T) { int i, j, start; if (T.len == 0) return FALSE; start = pos - 1; i = start; j = 0; while(i<S.len && j < T.len) if (S.ch[i] == T.ch[j]) { i++; j++;} else { start++; i = start; j = 0; } if (j >= T.len) return start+1; else return -1; }

定位函数：若S中存在和T相同的子串，则返回它在串S中第pos个字符之后第一次出现的位置。

简单模式匹配算法：

从主串S的pos位置起，与模式串T逐位匹配。

1. 初始化：主串从pos开始，模式串从头开始。
2. 两串逐位比较：当主串、模式串均未遍历完时，对应字符做比较，若相等则主串、模式串的当前比较位置均往后移；若不等则主串从开始比较位置的下一个开始，模式串从头开始。
3. 判别：若匹配成功则返回起始位置，若不成功则返回-1。

 13.StrReplace替换字符串

int StrReplace(SString* S, SString T, SString V) { if (0 == StrCompare(*S, T)) return FALSE; int pos = 1,i; while(1) { pos = StrIndex(*S, pos, T); if (S->len + V.len - T.len > MAXString) return FALSE; StrDelete(S,pos,T.len); StrInsert(S, pos, V); if (pos == -1) break; } return TRUE; }

先比较S和T是否是相等的；再用循环去逐个替换。循环内，先获取需要替换的位置，用字符串定位函数，顺便更新开始查找位置，再判断替换后会不会超出数据的存储范围，再根据替换位置，删除原本数据，再将需要更新的数据写入进去。

14、全部代码加测试

#include <stdio.h> #include <string.h> #define MAXString 50 #define TRUE 1 #define FALSE 0 typedef struct { char ch[MAXString]; int len; }SString; int StrAssign(SString *S,const char *chars) { S->len = 0; if (*chars == NULL) return TRUE; if (strlen(chars)>MAXString) return FALSE; while(chars[S->len] != '\0') { S->ch[S->len] = chars[S->len]; S->len++; } return TRUE; } int StrInsert(SString* S, int pos, SString T) { if (pos<1 || pos>S->len+1) return FALSE; int i; if (S->len + T.len <= MAXString) { printf("S的长度%d，T的长度%d\n", S->len, T.len); for (i = S->len + T.len - 1; i >= T.len -1 + pos; i--){ S->ch[i] = S->ch[i - T.len]; } for (i = 0; i < T.len; i++) S->ch[i - 1 + pos] = T.ch[i]; S->len = S->len + T.len; } else if (pos + T.len <= MAXString) { for (i = MAXString; i > T.len + pos; i--) S->ch[i] = S->ch[i - T.len+1]; for (i = 0; i < T.len; i++)S->ch[i + pos] = T.ch[i]; S->len = MAXString; } else { for (i = 0; i < MAXString - pos; i++) S->ch[i + pos] = T.ch[i]; S->len = MAXString; } return TRUE; } int StrDelete(SString* S, int pos, int len) { if (pos<1 || pos>(S->len - len + 1)) return FALSE; for (int i = pos + len - 1; i < S->len; i++) S->ch[i-len] = S->ch[i]; S->len -= len; return TRUE; } void StrCopy(SString *S, SString T) { //由后边参数复制的前边参数 for (int i = 0; i < T.len; i++) S->ch[i] = T.ch[i]; S->len = T.len; } int StrEmpty(SString* S) { if (S->len == 0) return TRUE; return FALSE; } int StrCompare(SString S, SString T) { int i; for (i = 0; i < S.len && i < T.len; i++) if (S.ch[i] != T.ch[i]) return(S.ch[i] - T.ch[i]); return S.len - T.len; } int StrLength(SString *S) { return S->len; } void StrClear(SString* S) { for (int i = 0; i < MAXString; i++) S->ch[i] = NULL; S->len = 0; } void StrCat(SString* S, SString T) { if (S->len + T.len <= MAXString) { for (int i = 0; i < T.len; i++) S->ch[i + S->len] = T.ch[i]; S->len = S->len + T.len; } else { for (int i = 0; S->len + i < MAXString; i++) S->ch[i + S->len] = T.ch[i]; S->len = MAXString - 1; } } int SubString(SString *Sub,SString S,int pos,int len) { if (pos<1 || pos>S.len || 1 > len || len > S.len - pos + 1) return FALSE; for (int i = 0; i < len; i++) Sub->ch[i] = S.ch[((pos - 1) + i)]; Sub->len = len; return TRUE; } int StrIndex(SString S, int pos, SString T) { int i, j, start; if (T.len == 0) return FALSE; start = pos - 1; i = start; j = 0; while(i<S.len && j < T.len) if (S.ch[i] == T.ch[j]) { i++; j++;} else { start++; i = start; j = 0; } if (j >= T.len) return start+1; else return -1; } int StrReplace(SString* S, SString T, SString V) { if (0 == StrCompare(*S, T)) return FALSE; int pos = 1,i; while(1) { pos = StrIndex(*S, pos, T); if (S->len + V.len - T.len > MAXString) return FALSE; StrDelete(S,pos,T.len); StrInsert(S, pos, V); if (pos == -1) break; } return TRUE; } void Print_SString(SString S) { for (int i = 0; i < S.len; i++) printf("%c ", S.ch[i]); printf("\n"); } void main() { SString s, t, v, q, * S, * T, * V,* Q; S = &s; T = &t; V = &v; Q = &q; printf("——————————初始化串，分别生成串S,T,V————————————\n"); StrAssign(S, "abcdabcd*fghijbcduuhds"); StrAssign(T, "abc"); StrAssign(V, ""); printf("串S为："); Print_SString(s); printf("\n串T为："); Print_SString(t); printf("\n串V为："); Print_SString(v); printf("\n————————————在S串中第三个字符前插入串V————————————\n"); StrInsert(S,3,*V); printf("插入后的S为："); Print_SString(*S); printf("\n————————————用串T返回S串中第5起8长的子串————————————\n"); SubString(T,*S,5,8); printf("\n串T为："); Print_SString(t); printf("\n————————————删除从第pos个字符起长度为len的子串————————————\n"); printf("删除是否成功（1成功，0不成功）：%d", StrDelete(S, 30, 5)); printf("\n删除是否成功（1成功，0不成功）：%d", StrDelete(S, 20, 15)); printf("\n删除是否成功（1成功，0不成功）：%d", StrDelete(S, -1, 5)); printf("\n删除是否成功（1成功，0不成功）：%d", StrDelete(S, 1, 2)); printf("\n删除后的S为："); Print_SString(*S); printf("\n————————————由串T复制得V————————————\n"); printf("串V复制前："); Print_SString(v); StrCopy(V,*T); printf("串V复制后："); Print_SString(v); printf("\n————————————将串V的值连接在串T后面————————————\n"); printf("串T连接前："); Print_SString(t); StrCat(T,*V); printf("串T连接后："); Print_SString(t); printf("\n————————————判断串是否为空串，以及清空串V————————————\n"); printf("串V清空前,空为1，非空为0：%d\n",StrEmpty(V)); StrClear(V); printf("串V清空后,空为1，非空为0：%d\n", StrEmpty(V)); int i, j, k; printf("\n———————————字符串之间的比较————————————\n"); StrAssign(Q, "c"); printf("串S为："); Print_SString(s); printf("\n串T为："); Print_SString(t); printf("\n串Q为："); Print_SString(q); printf("S与Q比较,从1开始：%d;S与Q比较,从16开始：%d;T与Q比较：%d", StrIndex(s, 1, q), StrIndex(s,6, q), StrIndex(v, 1, t)); printf("\n———————————字符串替换————————————\n"); StrAssign(V, ""); printf("串S替换前为："); Print_SString(s); StrReplace(S,*Q,*V); printf("串S替换后为："); Print_SString(s); }

 15.运行结果