数据结构第四章：串的定义、存储和基本运算

数据结构第四章：串的基本概念和存储方式 在数据结构中，串是一种基本的数据结构，用于存储和处理字符序列。在本章节中，我们将学习串的基本概念、存储方式和基本运算。 **串的基本概念** 串是由零个或多个任意字符组成的字符序列，记作：s=”s1s2…sn”。其中s是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；ai(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号;n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。 **串的存储方式** 串的存储方式有两种：顺序存储和堆存储。顺序存储是将串的所有元素存储在一个数组中，使用一个指针来指向最后一个字符，以表示串的实际长度。例如： typedef struct { char data[MAXSIZE]; int curlen; } SeqString; 定义一个串变量：SeqString s; 这种存储方式可以直接得到串的长度：s.curlen+1。 **串的基本运算** 串的基本运算包括： * 求串长StrLength(s)：操作结果是求出串s的长度。 * 串赋值StrAssign(s1,s2)：s1是一个串变量，s2或者是一个串常量，或者是一个串变量，操作结果是将s2的串值赋值给s1，s1原来的值被覆盖掉。 * 连接操作StrConcat(s1,s2,s)或StrConcat(s1,s2)：两个串的连接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。 * 求子串SubStr(s,i,len)：串s存在并且1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果是求得从串s的第i个字符开始的长度为len的子串。 **串的应用** 串的应用非常广泛，在文本处理、数据 compression、pattern matching等领域都有广泛的应用。例如，在文本编辑器中，串可以用来存储和处理文本数据；在数据 compression 中，串可以用来存储和处理数据压缩后的结果。 **教学目标** * 了解串的定义和基本概念 * 理解和掌握串的存储方式和基本运算 * 掌握常用的串运算和应用 **教学难点** * 串的模式匹配算法 * 串的基本运算的综合应用 **学时安排** 4学时