数据结构第四章：串的基本概念和存储方式
在数据结构中，串是一种基本的数据结构，用于存储和处理字符序列。在本章节中，我们将学习串的基本概念、存储方式和基本运算。
**串的基本概念**
串是由零个或多个任意字符组成的字符序列，记作：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学时
我的内容管理
展开
