C语言数据结构——串

冷不防 2022-12-19 00:48 142阅读 0赞

**串的定义：**  
串是由零个或多个字符串组成的有限序列，又叫字符串。  
![在这里插入图片描述][20201104193400941.png_pic_center]  
**串的长度：**  
（1<=i<=n）可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串，他的长度为0。  
串可以是空串，即没有字符，直接由" "表示（注意里面没有空格哦！）。  
例如：  
a=‘BEI’  
b=‘JING’  
c=‘BEIJING’  
d=‘BEI JING’  
则a,b,c,d 它们的长度分别为3，4，7，8；并且a和b都是c和d的子串，a在c和d中的位置都是1，而b在C中的位置是4，在d中的位置则是5.  
**注意：**  
由一个或者多个空格组成的串，称为空格串，它的长度为串中空格字符的个数。  
**总结：**  
通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。  
**串的相等：**  
如果两个串相等，当且仅当这两个串的值相等，也就是说，只有当两个串的长度相等，并且各个对应的位置的字符都相等才相等。

**子串和主串：**  
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。  
例如：  
“over”是“lover”的子串  
“end”是“friend”的子串  
“lie”是“believe”的子串  
\*\*注意：\**串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。例如：  
X=‘123’  
则表明X是一个串变量名，赋给它的值是字符序列123。  
**串的存储结构：**  
串的存储结构和线性表相同，也分顺序存储结构和链式存储结构。  
串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。  
按照预定义的大小，为每个定义的字符串变量分配一个固定长度的存储区，一般用定长数组来定义。  
与线性表相似，既然是固定长度的存储区，就存在一个空间分配不灵活的问题，那么会考虑用链式存储结构。  
**串的基本操作：**  
![在这里插入图片描述][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算法：**  
BF算法属于复苏的模式匹配算法，它的核心思想是：  
![在这里插入图片描述][20201104200333192.png_pic_center]  
该算法最坏的情况下要进行M*(N-M+1)次比较，时间复杂度为O（M\*N）。  
在这里S是主串、T为子串，这种子串的定位操作通常称作串的模式匹配。  
例如;  
![在这里插入图片描述][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]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][2020110420075010.png_pic_center]  
希望大家在学习C语言的数据结构都能坚持学下去！！！  
我感觉太难了，最近有点懈怠！！！  
晚安！

[20201104193400941.png_pic_center]: /images/20221120/03234c960ad24933bef831d40a85626c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201104203541526.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/20201104203609885.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[20201104200333192.png_pic_center]: https://img-blog.csdnimg.cn/20201104200333192.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201104200645410.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/20201104200712916.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/20201104200734104.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx,size_16,color_FFFFFF,t_70#pic_center
[2020110420075010.png_pic_center]: https://img-blog.csdnimg.cn/2020110420075010.png#pic_center