清华大学数据结构课件第四章.ppt

第四章 串的基本概念 串连接算法Concat（T，S1，S2） * 4.1 串类型的定义 串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作 s=〃a1a2…an〃 (n≥0) 其中：s为串名，用双引号括起来的字符序列是串的值；ai(0≤i≤n)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；串中字符的数目n称为串的长度。 空串——零个字符的串，通常以两个相邻的双引号来表示空串（Null string），如：s=〃〃，它的长度为零； 空格串——仅由空格组成的的串，如：s=〃└┘〃；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=〃I’m a student〃的长度为13。 串的抽象数据定义：P71 对于串的基本操作集可以有不同的定义方法，读者在使用高级语言中的串类型时，应该以语言的参考手册为准。 定位算法（P72） —— Index（S，T，pos） 4.2 串的表示和实现 对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。 串的3种机内表示方式： 定长顺序存储表示 堆分配存储表示 串的块链存储表示 4.2.1 定长顺序存储表示 实现：用一组地址连续的存储单元存储串值的字符序列。 存储表示 #define MAXSTRLEN 255 Typedef unsigned char String[MAXSTRLEN+1] 截断——超过与定义长度的串值被舍去。 串长的两种表示： 下标为0的分量存放串的实际长度，如：pascal 在串尾加一个不计入串长的结束标记符。如：C中的‘\0’ 求子串算法SubString（Sub，S，pos，len） 串操作特点： 原操作为——字符序列的复制 操作的时间复杂度基于复制序列的长度 截断处理 串的动态存储结构 串的各种运算与串的存储结构有着很大的关系，在随机取子串时，顺序存储方式操作起来比较方便，而对串进行插入、删除等操作时，就会变得很复杂。因此，有必要采用串的动态存储方式。 串的动态存储方式采用堆存储结构和链式存储结构两种形式： 4.2.2堆存储结构 特点 仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。 在C语言中，存在一个称为“堆”的自由空间，由动态分配函数malloc( )分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由free( )释放串不再需要的空间。 存储结构： typedef struct{ char *ch; //若是非空串，按串长分配空间，否则ch为NULL int length; //串长 } HString; 基本算法（P76-77） 4.2.3链式存储结构 串的链式存储结构中每个结点包含字符域和结点链接指针域，字符域用于存放字符，指针域用于存放指向下一个结点的指针，因此，串可用单链表表示。 用单链表存放串，每个结点仅存储一个字符，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构。 #define CHUNKSIZE 80 //用户定义块的大小 typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; } Chunk; typedef struct Chunk{ Chunk *head，*tail; //串的头尾指针 int curlen; //串的当前长度 } Chunk; 用块链表存放字符串时，其结构用C语言定义如下： 4.4 文本编辑 文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的输入、查找、修改、删除、输出等。 例如有下列一段源程序： main() {int a,b,c; scanf(〃%d,%d〃,a,b); c=a+b; printf(“%d”,c); } 我们把这个源程序看成是一个文本，为了编辑的方便，总是利用换行符把文本划分为若干行，还可以利用换页符将文本组成若干页，这样整个文本就是一个字符串，简称为文本串，其中的页为文本串的子串，行又是页的子串。将它们按顺序方式存入计算机内存中，如表4-2所示