「数据结构」串_IT分享知识网

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

串的定义和实现

串的定义

串: 即字符串，零个或多个字符组成的有限序列
串的长度：串中字符的个数n
空串：n=0时的串
子串：串中任意多个连续的字符组成的子序列
主串：包含子串的串
字符在主串中的位置：字符在串中的序号（从1开始）
子串在主串中的位置：子串的第一个字符在主串中的位置
空串和空格串M = ‘’ 是空串；N =’ ‘ 是空格串；
串和线性表串是特殊的线性表，数据元素之间呈线性关系串的数据对象限定为字符集：中文字符、英文字符、数字字符、标点字符等串的基本操作，如增删改除通常以子串为操作对象

串的存储结构

串的顺序存储

静态数组实现（定长顺序存储）
1
2
3
4
5
6
#define MAXLEN 255 //预定义最大串长为255
typedef struct{
char ch[MAXLEN]; //每个分量存储一个字符
int length; //串的实际长度
}SString;
动态数组实现（堆分配存储）
1
2
3
4
5
6
7
typedef struct{
char *ch; //按串长分配存储区，ch指向串的基地址
int length; //串的实际长度
}HString;
HString S;
S.ch = (char *) malloc(MAXLEN * szeof(char)); //用完要手动free
S.length = 0;
串长表示法

用一个额外的变量length来存放串的长度
用ch[0]充当length优点：字符的位序和数组下标相同缺点：字符串最大长度只有256
没有length变量，以字符 ‘\0’ 表示结尾（对应ASCII码的0）缺点：需要从头到尾遍历
ch[0]废弃不用，声明int型变量length来存放串的长度

基本操作实现

ch[0]废弃不用，声明int型变量length来存放串的长度

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 37 38 39 40 41 42 43 44 45 46 47

#define MAXLEN 255 typedef struct{ char ch[MAXLEN]; int length; }SString; // 求子串 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.cn[i-pos+1] = S.ch[i]; Sub.length = len; return true; } // 比较两个串的大小 int StrCompare(SString S, SString T){ for (int i; 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; } // 定位操作 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); if(StrCompare(Sub,T)!=0) ++i; else return i; // 返回子串在主串中的位置 } return 0; //S中不存在与T相等的子串 }

串的链式存储

1 2 3 4

typedef struct StringNode{ char ch; //每个结点存1个字符 struct StringNode *next; }StringNode, * String;

缺点：存储密度低，每个字符1B，每个指针4B

改进方法
1
2
3
4
typedef struct StringNode{
char ch[4]; //每个结点存多个个字符
struct StringNode *next;
}StringNode, * String;

串的基本操作

假设有串 T = ‘’, S = ‘iPhone 11 Pro Max?’, W = ‘Pro’StrAssign(&T, chars): 赋值操作，把串T赋值为charsStrCopy(&T, S): 复制操作，把串S复制得到串TStrEmpty(S): 判空操作，若S为空串，则返回True，否则返回FalseStrLength(S): 求串长，返回串S的元素个数ClearString(&S): 清空操作，将S清为空串DestroyString(&S): 销毁串，将串S销毁（回收存储空间）Concat(&T, S1, S2): 串联联接，用T返回由S1和S2联接而成的新串———可能会导致存储空间的扩展SubString(&Sub, S, pos, len): 求子串，用Sub返回串S的第pos个字符起长度为len的子串Index(S, T): 定位操作，若主串S中存在与串T值相同的子串，则返回它再主串S中第一次出现的位置，否则函数值为0StrCompare(S, T): 串的比较操作，参照英文词典排序方式；若S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0

串的模式匹配

字符串模式匹配:在主串中找到与模式串相同的子串，并返回其所在位置

简单的模式匹配算法

朴素模式匹配算法: 将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串或所有的子串都不匹配为止

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

int Index(SString S, SString T){ int i=1; //扫描主串S int j=1; //扫描模式串T while(i<=S.length && j<=T.length){ if(S.ch[i] == T.ch[j]){ ++i; ++j; //继续比较后继字符 } else{ i = i-j+2; j=1; //指针后退重新开始匹配 } } if(j>T.length) return i-T.length; else return 0; }

时间复杂度分析主串长度为n，模式串长度为m,大多数时候，n>>m最多比较n-m+1个子串最坏时间复杂度：每个子串都要对比m个字符(对比到最后一个字符才匹配不上)，共要对比n-m+1个子串，复杂度 = $O((n-m+1)m) = O(nm – m^2 + m) = O(nm)$最好时间复杂度 = O(n)每个子串的第一个字符就匹配失败，共要对比n-m+1个子串，复杂度 = O(n-m+1) = O(n)

串的模式匹配算法——KMP算法

根据模式串T，求出next数组，利用next数组进行匹配（主串指针不再回溯）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Index_KMP(SString S, SString T, int next[]){
int i=1; //主串
int j=1; //模式串
while（i<S.length && j<=T.length){
if(j==0 || S.ch[i]==T.ch[j]){ //第一个元素匹配失败时
++j;
++i; //继续比较后继字符
}
else
j=next[j] //模式串向右移动
}
if(j>T.length)
return i-T.length; //匹配成功
}
最坏时间复杂度：O(m+n)

求next数组时间复杂度O(m)
模式匹配过程最坏时间复杂度O(n)

求模式串的next数组

next数组的作用：当模式串的第j个字符失配时，从模式串的第 next[j] 个字符继续往后匹配
任何模式串都一样，第一个字符不匹配时，只能匹配下一个子串，因此，next[1]都等于 0
任何模式串都一样，第2个字符不匹配时，应尝试匹配模式串的第1个字符，因此，next[2]都等于 1
在不匹配的位置前边，划一根分界线，模式串一步一步往后退，直到分界线之前“能对上”，或模式串完全跨过分界线为止，此时j指向哪儿，next数组值就是多少

KMP算法的进一步优化

nextval[1]恒等于0
1
2
3
4
5
6
7
nextval[1]=0;
for (int j=2; j<=T.length; j++) {
if(T.ch[next[j]]==T.ch[j])
nextval[j]=nextval[next[j]];
else
nextval[j]=next[j];
}

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/92867.html

「数据结构」串