DS04-串2010.pptVIP

基本概念 串的存储结构 串的基本操作 串的模式匹配 ;4.1 串的定义和基本操作; ; ;串的基本操作 求串长Strlen(s)：求串s的长度，Strlen(s)的值是一个非负整数。若s是一个空串，则Strlen(s)=0。 串赋值StringAssign(s,string_constant) ：给串s赋值。其中string_constant可为串变量、串常量或经过适当运算所得到的串值。 串复制Strcpy(s,t)：由串s复制得到串t。 串联接Strcat(s,t)：将串t联接到串s的末尾形成新串s。 ? 串比较Strcmp(s,t)：比较s和t的大小，若s＜t，则返回值小于0；若s＞t，则返回值大于0；若s=t，则返回值为0 。 ; ; ; ; ;顺序串的基本操作的实现 下面讨论串的部分基本操作的实现算法。 串的数据类型说明如下： #define MaxStrSize 256? typedef struct { ? char ch[MaxStrSize]; ?? int length; ?}SeqString; ; ; 串的顺序存储表示下，串操作的实现主要是进行“字符序列的复制”，操作的时间复杂度基于复制的字符序列的长度。在这种存储方式下，涉及串长的操作速度快，但也存在不足之处：一是需事先预定义串的最大长度，这在程序运行前是很难估计的；二是由于定义了串的最大长度，串值空间的大小在编译时刻就已确定，是静态的，使得串的某些操作受限，如串的联接、插入等操作受到串值空间大小的制约。这种串的定长顺序表示不够灵活，适应范围有一定局限。 ;4.2.2 串的堆存储结构 堆存储结构的特点是：仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但该存储空间的大小不是预定义，而是在程序执行过程中动态分配的。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。这种方式可以灵活地申请适当数目的存储空间，从而提高存储资源的利用率。 在C语言中，由动态分配函数malloc( )分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址。由函数free( )释放串不再需要的空间。 ;串的堆存储结构类型定义如下： typedef struct { char *ch; /*ch指向串起始地址*/ int length; /*串的实际长度*/ } Hstring； 在这种存储方式中，??向字符串存储空间的是字符指针而非数组。若串为空串，则ch为NULL。另外在使用分配函数后需要检查函数的返回值（若分配失败，则返回NULL），避免出现对空指针进行操作。 ;堆串的基本操作的实现 串的堆存储结构中，串中的字符也是顺序存放的，串操作的实现也是基于“字符序列的复制”方式。只是由于串长是可变的，所以在实施“插入”、“联结”等可能使串长发生变化的操作时，除了要修改串的实际长度，还要为串按新的长度重新分配空间。; ; ;4.2.3 串的块链存储结构 串的链式存储结构类型定义如下： typedef struct { char ch; struct cnode *next; }cnode,*LinkString; LinkString head; /*head是链串的头指针*/ 串的链式存储结构简称链串。 ;; 链串结构便于进行插入和删除运算，但每个结点的指针域所占空间比字符域所占空间要大得多，存储空间利用率较低。为了有效利用存储空间，可以在链串的每个结点中存放多个字符，称这样的结点为块，每个结点中所容纳的字符个数为块的大小，称这样的串存储结构为块链结构。 块链结构中，当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符”#”来填充最后一个结点，以表示串的终结。 ; 结点大小为1时，串的操作处理较方便，但是存储占用较大，空间利用率较低；提高结点的大小使得存储空间利用率增大，但是做插入、删除运算时，需要考虑结点的拆分与合并，可能会引起大量字符的移动，给运算带来不便。 在串的链式结构中，结点大小的选择很重要，直接影响到串的处理效率和内存空间利用率。;串的块链存储结构类型定义如下： #define CHUNKSIZE 4 /*定义块大小*/ typedef struct Chunk /*定义块链结点结构*/ { char s