清华962数据结构 --- Ch4 串
一、串
1、定义
由零个或多个字符组成的有限序列,一般可以记为 ,其中
- 可以是字母、数字或其他字符
- 指的是该字符在串中的位置
- 指的是该字符串的长度
- 零个字符的串则被称之为空串
2、基本概念
- 子串:串中任意个连续的字符组成的子系列
- 主串:包含子串的串
- 位置:字符在序列中的序号(从 1 可开始)
- 空格串:只包含空格的串,注意与空串的区别(‘ ’与 )
3、基本操作
- StrAssign (&T, chars):赋值,把串 T 赋值为 chars
- StrCopy (&T, S):复制,由串 S 复制得串T
- StrEmpty (S):判空
- StrCompare (S, T):比较两个字符串长度
- 若 S>T,返回值>0
- 若 S=T,返回值=0
- 若 S<T,返回值<0
- StrLength (S):求串长度
- ClearString (&S):清空串
- Concat (&T, S1, S2):拼接,用 T 返回 S1和 S2 平拼接而成的新串
- SubString (&Sub, S, pos, len):求子串,用 Sub 返回串 S 的第 pos 个字符串起长度为 len 的子串
- Index (S, T,pos):定位,若主串 S 中存在与串 T 相同的子串,则返回它在主串 S 中第一次出现的位置,否则返回 0
- Replace (&S, T, V):用 V 替换主串 S 在中出现的所有与 T 相等的不重叠的子串
- StrInsert (&S, pos, T):在串 S 的第 pos 个字符之前插入串 T
- StrDelete (&S, pos, len):从串 S 在中删除第 pos 个字符起长度为 len 的子串
- DestoryString (&S):销毁(释放空间)
4、存储结构
(1)顺序表示
用一组地址连续的存储单元来存储串中的字符序列,在字符串的末尾用 ‘\0’
表示结束,它不算做字符串的长度,但是需要占用存储空间
(2)链式表示
与线性表不同,在串的存储过程中存在结点大小的问题,每个结点可以只存放一个字符,也可以存放多个字符。没占满的位置用 #
补齐
第一种方法存储密度较低,每个结点空间利用不充分;第二种方法相对存储密度更高
注: 存储密度小(如结点大小为 1 时),运算处理方便,但是存储用量过大;但是如果在串处理过程中需要进行内、外存交换的话,则会因为内外存操作过多而影响处理的总效率。
串值的链式存储结构对某些串操作有一定的方便之处(如联接操作等),但是总的来说,另外两种存储结构更加灵活。
5、串的模式匹配
子串的定位操作称为串的模式匹配
(1)朴素模式识别算法
朴素算法是一种纯暴力算法,他将主串中所有长度为 m 的子串依次与模式串对比,直到找到一个完全匹配的子串/或者全部不匹配为止
int Index(String S,String T,int pos)
{
//字符串从1位置开始存储
int i=1;//i指针指向主串S
int j=1;//j指针指向模式串T
int k=i;//k用来记录下次主串回溯的位置
while(i<=S.len && j<=T.len)
{
if(S[i]==T[j])
{
++i;
++j;
}
else//不匹配
{
j=1;//模式串从第一个位置继续开始匹配
i=++k;//主串从k+1位置开始比较
}
}
if(j>T.len)//如果是模式串扫描完了,说明匹配到了,那么此时k记录的就是模式串起始位置
return k;
else
return 0;
}
算法效率分析
- 最好情况:时间复杂度为
- 平均情况:平均查找次数为 ,时间复杂度为
- 最坏情况:
(2)KMP 算法
难点 KMP 算法是对朴素算法的优化,每当一趟匹配过程中出现字符比较不相等时,不需要回溯 i 指针,而是利用已经得到的“部分匹配”的结果,将模式向右“滑动”尽可能远的一段距离后,继续进行比较
Next[j]的计算方法:
- 第一位为 0, 的第二位为 1
- 如果存在最长相等前后缀
n
,则等于n+1
- 如果不存在,则为 1
Nextval[j]的计算方法:
- 第一位为 0
- 如果第二位的值等于第一位的值,则为 0;反之为 1
- 从第三位开始,由 next[j]指路,若当前值=next 在指向的值,则为别人的 nextval 值;反之则为当前的 next 值
计算 next 数组的函数
c
void get_next(string T,int next[])
{
int i=1,j=0;
next[1]=0;
while(i<T[0])
{
if(j==0 || T[i]==T[j])
{
i++;
j++;
next[i]=j;
}
else
{
j=next[j];
}
}
}