4.1串的定义和实现

4.1.1串的定义

定义

串 V.S 线性表

串是一种特殊的线性表，数据元素之间呈线性关系；数据对象限定为字符集（如中英文字符、数字、标点等），串的基本操作，如增删改查等通常以子串为操作对象。

基本操作

• StrAssign(&T,chars)：赋值操作。把串T赋值为chars。
• StrCopy(&T,S)：复制操作。由串S复制得到串T。
• StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE。
• StrLength(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中第一次出现的
  位置；否则函数值为0。

• StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0（如下图）：
  

  字符集编码和乱码问题

  
  乱码：在你的文件中，原本采用某一套编码规则y=f(x)，打开文件时，你的软件以为你采用的是另一套编码规则y=g(x)，所以出现乱码。

  总结

  

4.1.2串的存储结构和基本操作

顺序存储

链式存储

基本操作的实现

取子串

比较

定位

总结

4.2串的模式匹配

4.2.1朴素模式匹配算法

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

朴素模式匹配算法：主串⻓度为n，模式串⻓度为 m，将主串中所有⻓度为m的⼦串依次与模式串对⽐，直到找到⼀个完全匹配的⼦串，或所有的⼦串都不匹配为⽌。（最多对比 n-m+1 个⼦串）

栗子：Index(S, T)

过程

若当前⼦串匹配失败，则主串指针 i 指向下⼀个⼦串的第⼀个位置，模式串指针 j 回到模式串的第⼀个位置。

若 j > T.length，则当前⼦串匹配成功，返回当前⼦串第⼀个字符的位置 —— i - T.length。

代码

设主串⻓度为 n，模式串⻓度为 m，则最坏时间复杂度 = O(nm)，最好时间复杂度 = O(n)

总结

4.2.2改进的模式匹配算法--KMP算法？？

朴素模式匹配算法不匹配的字符之前，⼀定是和模式串⼀致的

4.2.3 求next数组

练习？？

KMP算法性能分析

总结

4.2.4KMP算法的进一步优化

总结