C语言数据结构——串（再学一次）

太过爱你忘了你带给我的痛 2022-12-19 09:17 145阅读 0赞

**串的定义：**  
是由零个或多个字符组成的有限序列。S=‘a1a1a3a4a5…an’(a≥0)  
其中：S为串名；n为串的个数;ai为串的元素。  
**空串：**  
空串是指长度n=0的串，它不包含任何字符。  
**空格串：**  
空格串是仅由一个或多个空格组成的串，长度大于等于1。  
**子串：**  
串中任意连续的字符组成的子序列为子串。  
**主串:**  
包含子串的串相应的称为主串。  
**位置:**  
字符在序列中的序号。子串在主串的位置则以**子串的第一个字符**在主串的位置来表示。  
**串相等：**  
两个串的长度相等，并且**对应位置的字符**都相等。  
**串的基本操作：**  
**1.串插入操作：**  
![在这里插入图片描述][20201106161107334.png_pic_center]  
![在这里插入图片描述][2020110616114162.png_pic_center]  
**2.串删除操作：**  
![在这里插入图片描述][20201106161220856.png_pic_center]  
![在这里插入图片描述][20201106161520456.png_pic_center]  
**3.串链接操作：**  
![在这里插入图片描述][20201106161549673.png_pic_center]  
![在这里插入图片描述][20201106161609284.png_pic_center]  
**4.求子串操作：**  
![在这里插入图片描述][20201106161755695.png_pic_center]  
![在这里插入图片描述][20201106161823354.png_pic_center]  
**注意:起始位置和子串长度之间存在约束关系！！**  
**5.求位置操作：**  
![在这里插入图片描述][20201106162102359.png_pic_center]  
![在这里插入图片描述][20201106162159511.png_pic_center]  
**6.串替换操作：**  
![在这里插入图片描述][20201106162307818.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]  
**替换操作只替换一次！！！**

串的模式匹配：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]  
**BF模式匹配算法（又称暴力匹配算法）**  
主串S中的**子串**与**模式串T**进行比较，直到找到相同的子串为止。  
如果存在相同的子串，则匹配成功，返回子串在主串S中的为止pos，否则匹配不成功。  
**子串与模式的比较策略**：*从前到后依次进行比较。*  
例子如下:  
![在这里插入图片描述][20201106163514535.png_pic_center]  
![在这里插入图片描述][20201106163529948.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]

**串的模式匹配思想：**  
从主串的第pos个字符起，和模式串的第一个字符比较  
如果两个串的第一个字符相等，继续逐个比较后续字符；如果第一个字符不相等，则从主串的下一个字符和模式串的第一个字符比较，依次比较，直到找到与模式串相等的子串，返回模式串第一个字符相对应在主串中的序号；如果不成功，返回0。  
**匹配算法的代码实现：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]  
该算法的时间复杂度为：O（n\*m）  
其中，n为主串的长度，m为模式串的长度！

**串的KMP算法：**  
![在这里插入图片描述][20201106170231103.png_pic_center]  
**该算法的特点:**  
在匹配的过程中，**不需要回溯主串的指针i**，而且时间复杂度可以达到O（m+n）。  
看实例：  
![在这里插入图片描述][20201106170440920.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]  
**串的模式匹配思想：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 7]  
算法代码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 10]  
该算法的时间复杂度为：O（n+m）。

[20201106161107334.png_pic_center]: /images/20221120/8d95047f52af41fbada6d068059daeca.png
[2020110616114162.png_pic_center]: /images/20221120/52a8a4707fcc4763bbbc535a572b4118.png
[20201106161220856.png_pic_center]: /images/20221120/eeb43cf1261b4fd8aa80308555a5111a.png
[20201106161520456.png_pic_center]: /images/20221120/abe93b8de6e9440b99c0a45034c6e155.png
[20201106161549673.png_pic_center]: https://img-blog.csdnimg.cn/20201106161549673.png#pic_center
[20201106161609284.png_pic_center]: https://img-blog.csdnimg.cn/20201106161609284.png#pic_center
[20201106161755695.png_pic_center]: https://img-blog.csdnimg.cn/20201106161755695.png#pic_center
[20201106161823354.png_pic_center]: https://img-blog.csdnimg.cn/20201106161823354.png#pic_center
[20201106162102359.png_pic_center]: https://img-blog.csdnimg.cn/20201106162102359.png#pic_center
[20201106162159511.png_pic_center]: https://img-blog.csdnimg.cn/20201106162159511.png#pic_center
[20201106162307818.png_pic_center]: https://img-blog.csdnimg.cn/20201106162307818.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201106162450184.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201106162958405.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[20201106163514535.png_pic_center]: https://img-blog.csdnimg.cn/20201106163514535.png#pic_center
[20201106163529948.png_pic_center]: https://img-blog.csdnimg.cn/20201106163529948.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201106163949646.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201106164157140.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/2020110616583322.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[20201106170231103.png_pic_center]: https://img-blog.csdnimg.cn/20201106170231103.png#pic_center
[20201106170440920.png_pic_center]: https://img-blog.csdnimg.cn/20201106170440920.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201106172817647.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201106172925146.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/2020110617310682.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201106173224538.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20201106173356370.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20201106173424140.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center