串的知识点总结
1. 串的基本概念
串是由零个或多个字符组成的有限序列，通常用来表示文本数据。在编程语言中，串通常被定义为一个字符数组或字符串变量。例如，在C语言中，字符串通常被定义为char类型的数组，而在Java语言中，字符串则是一个类对象。
2. 串的存储结构
串的存储结构有两种常见形式：一是定长顺序存储结构，二是链式存储结构。定长顺序存储结构是将串的字符按照顺序存储在一块连续的存储空间中，这种方式可以通过下标来访问任意位置的字符，但是需要预先分配足够的存储空间。链式存储结构则是使用链表来存储串的字符，这种方式可以动态分配内存空间，但是访问任意位置的字符需要从链表头开始遍历，效率较低。
3. 串的基本操作
串的基本操作包括串的创建、复制、连接、比较、插入和删除等。创建串是指将一组字符转换成串的操作；复制是指将一个串的内容复制到另一个串中；连接是指将两个串连接在一起形成一个新的串；比较是指比较两个串的大小关系；插入是指在一个串中的指定位置插入一个子串；删除是指删除一个串中的指定子串。这些操作都是串的基本操作，它们在实际应用中有着重要的作用。
4. 串的模式匹配
串的模式匹配是指在一个主串中查找与给定模式串相匹配的子串的过程。常见的模式匹配算法有暴力匹配算法、KMP算法和Boyer-Moore算法等。暴力匹配算法是最简单的模式匹配算法，它的时间复杂度为O(m*n)，其中m为主串长度，n为模式串长度；KMP算法是一种高效的模式匹配算法，它的时间复杂度为O(m+n)，其中m为主串长度，n为模式串长度；Boyer-Moore算法是一种更加高效的模式匹配算法，它的时间复杂度为O(m*n)，其中m为主串长度，n为模式串长度。
5. 串的应用
串在计算机科学中有着广泛的应用，它在各种应用中都有着重要的作用。例如，在文本编辑器中，串被用来表示文本文件的内容；在数据库系统中，串被用来表示数据的各种属性；在网络通信中，串被用来表示网页的URL地址等。除此之外，串还被用来表示各种信息，如文件路径、电子邮件地址、电话号码等。串的应用无处不在，它是计算机科学中的一个重要概念。 总之，串是一种重要的线性数据结构，在计算机科学中有着广泛的应用。掌握串的基本概念、存储结构、基本操作和模式匹配算法等知识，对于提高程序员的编程能力和解决实际问题都有着重要的作用。希望本文能对读者有所帮助，谢谢！
串-数据结构实验报告
串 数据结构实验报告
一、实验目的
本次实验的主要目的是深入理解和掌握串这种数据结构的基本概念、存储方式以及相关的操作算法。通过实际编程实现串的基本操作，提高对数据结构的理解和编程能力，培养解决实际问题的思维和方法。
二、实验环境
本次实验使用的编程语言为 C+＋，开发工具为 Visual Studio 2019。
三、实验原理
（一）串的定义
串是由零个或多个字符组成的有限序列。在本次实验中，我们主要关注的是字符串。
（二）串的存储方式
1、 顺序存储
定长顺序存储：使用固定长度的数组来存储字符串，长度不足时用特定字符填充。
堆分配存储：根据字符串的实际长度动态分配存储空间。 2、 链式存储
每个节点存储一个字符，并通过指针链接起来。
（三）串的基本操作
1、 串的创建和初始化
2、 串的赋值
3、 串的连接
4、 串的比较
5、 求子串
6、 串的插入和删除
四、实验内容及步骤
（一）顺序存储方式下串的实现
1、 定义一个结构体来表示顺序存储的字符串，包含字符数组和字符串的实际长度。
｀｀｀cpp
struct SeqString ｛
char str;
int length;
｝； ｀｀｀
2、 实现串的创建和初始化函数
｀｀｀cpp
SeqString createSeqString(const char initStr) ｛
int len ＝ strlen(initStr)；
SeqString s;
sstr ＝ new charlen ＋ 1;
strcpy(sstr, initStr)；
slength ＝ len;
return s;
｝
｀｀｀
3、 串的赋值函数
｀｀｀cpp
void assignSeqString(SeqString& s, const char newStr) ｛
delete sstr;
int len ＝ strlen(newStr)；
习题四 串
一、单项选择题
1．下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
2．串是一种特殊的线性表，其特殊性体现在（ ）。
A．可以顺序存储 B．数据元素是一个字符
C．可以链接存储 D．数据元素可以是多个字符
3．串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A．求子串 B．联接 C．匹配 D．求串长
5．若串S=“software”,其子串的个数是（ ）。
A．8 B．37 C．36 D．9
二、填空题
1．含零个字符的串称为______串。任何串中所含______的个数称为该串的长度。
2．空格串是指__ __，其长度等于__ __。
3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。
4．INDEX（‘DATASTRUCTURE’， ‘STR’）=________。
5．模式串P=‘abaabcac’的next函数值序列为________。
6．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；
int f((1)__ ______)
第四章 串
一．单项选择题
1．串的连接运算不满足 。
A. 分配律 B. 交换律 C. 结合律 D. 都不满足
2．串是一种特殊的线性表，其特殊性体现在 。
A. 可以顺序存储 B. 数据元素是一个字符
C. 可以链接存储 D. 数据元素可以是多个字符
3．设有两个串p和q，求q在p中首次出现的位置的运算称作 。
A. 连接 B. 模式匹配 C. 求子串 D. 求串长
4．串是一个 的序列。
A. 不少于一个字母 B. 有限个字符 C. 不少于一个字符 D. 空格或字母
5．已知串s=’ABCDEFGH’，则s的所有不同子串的个数为 。
A. 8 B. 9 C. 36 D. 37
6. 设串 s1=’ABCDEFG’，s2=’PQRST’，函数 con(x，y)返回 x 和 y 串的连接串，subs(s，i，j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串，len(s)返回串 s 的长度，则
con(subs(s1，2，len(s2))，subs(s1，len(s2)，2))的结果串是 。
A. BCDEF B. BCDEFG
C. BCPQRST D. BCDEFEF
二．填空题
1．两个串相等的充分必要条件是 。
2．空格串是 ① ,其长度等于 ② 。3．模式串‘abaabade’的next函数值为 。
