串的顺序存储结构及顺序串算法设计方法。
时间: 2024-06-04 20:13:18 浏览: 13
顺序串是采用一段连续的存储空间存储串中的字符,通常用字符数组来表示。串的顺序存储结构包含一个指向存储串的字符数组的指针和一个记录串长度的变量。
顺序串的常用算法包括串的构造,串的赋值,串的比较,串的连接,子串的取出,串的插入,串的删除等。其中,串的连接和子串的取出是比较常用的操作。
为了实现串的操作,需要设计一些算法。一般来说,可以根据具体的需求,设计相应的算法,比如可以使用循环实现串的操作。此外,还可以使用递归算法来实现一些操作。
相关问题
字符串采用顺序存储结构,设计求子串的算法
1. 首先输入原字符串和子串,确定它们的长度。
2. 从原字符串的第一个字符开始,依次比较原字符串和子串的每个字符是否相等。
3. 如果相等,则继续比较下一个字符,直到子串的最后一个字符。
4. 如果子串的所有字符都与原字符串中的一段连续字符相等,则找到了子串,返回该子串在原字符串中的起始位置。
5. 如果子串的某个字符与原字符串中的某个字符不相等,则从原字符串的下一个字符开始重新比较,直到找到子串或者原字符串遍历完毕。
6. 如果原字符串遍历完毕仍未找到子串,则说明原字符串中不存在该子串。
字符串采用顺序存储结构,设计求子串的算法;
假设原字符串为S,子串为T,S的长度为n,T的长度为m。
1. 遍历S的每一个字符,从第一个字符开始,对于每个字符i,都与T的第一个字符j进行比较。
2. 如果S中的字符i与T中的字符j相等,则从i+1和j+1开始继续比较下一个字符,直到T中的所有字符都比较完毕。
3. 如果在比较过程中发现有字符不相等,则继续遍历S的下一个字符i+1,并重复步骤2。
4. 如果在比较过程中T中的所有字符都已经比较完毕,且都相等,则找到了子串,返回子串在S中的起始位置i-m+1。
5. 如果遍历完S中的所有字符,仍然没有找到子串,则返回-1,表示没有找到。
算法时间复杂度为O(n*m),空间复杂度为O(1)。
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)