数据结构第4章.ppt

《数据结构第4章.ppt》由会员分享，可在线阅读，更多相关《数据结构第4章.ppt（34页珍藏版）》请在三一文库上搜索。

1、2,第4章 串,学习目标与要求： 了解串的基本概念和基本运算。 熟练掌握串的顺序存储结构，掌握串的堆式存储结构和串的链式存储结构。 熟练掌握串的顺序存储结构中的连接、相等判断、取子串、插入、删除和子串查找等算法的实现。,3,4.1 串的定义及基本操作,串即字符串，计算机处理的对象分为数值数据和非数值数据，字符串是最基本的非数值数据。 字符串的应用非常广泛，它是许多软件系统(如字符编辑、情报检索、词法分析、符号处理、自然语言翻译等系统)的操作对象。 在事务处理程序中，顾客的姓名和地址以及货物的名称、产地和规格等一般也是作为字符串处理的。字符串是一种特定的线性表，其特殊性在于组成线性表的每个元素都

2、是一个单字符。,4,4.1.1 串的基本概念,串(String)是零个或多个字符组成的有限序列。一般记为： S=“a1an“ (n0) 其中S是串的名字，用双引号括起来的字符序列是串的值，ai(1in)可以是字母、数字或其他字符。它称为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数。,5,4.1.1 串的基本概念,几个术语 （1）长度串中字符的个数，称为串的长度。 （2）空串长度为零的字符串称为空串。 （3）空格串由一个或多个连续空格组成的串称为空格串。 （4）串相等两个串是相等的，是指两个串的长度相等且对应字符都相等。 （5）子串串中任意连续的字

3、符组成的子序列称为该串的子串。 （6）主串包含子串的串称为该子串的主串。 （7）模式匹配子串的定位运算又称为串的模式匹配，是一种求子串的第一个字符在主串中序号的运算。被匹配的主串称为目标串，子串称为模式。,6,【例】字符串的长度及子串的位置。 字符串 字符串长度 S1=SHANG 5 S2=HAI 3 S3=SHANGHAI 8 S4=SHANGHAI 9 / 表示空格，下同 S1是S3、S4的子串，S1在S3、S4中的位置都为1。 S2也是S3、S4的子串，S2在S3中的位置为6； S2在S4中的位置为7。,4.1.1 串的基本概念,7,串的输入与输出 1字符串的输入 在C语言中，字符串的输

4、入有两种方法： （1）使用scanf () 函数 使用scanf () 函数时，输入格式中要设置%s，再加上字符数组名称。 【例】 char str10; printf(Input your str: ); scanf(%s,str); 使用scanf ()方式输入时，字符串中不能含有空格。,8,（2）使用gets() 函数 格式为：gets(字符数组名); 【例】 char str10; printf(Input your str: ); gets(str); 使用gets()方式输入时，字符串中允许含有空格。,9,2字符串的输出 字符串的输出也有两种方法： （1）使用printf () 函

5、数 使用printf () 函数时，输出格式中要设置%s，再加上字符数组名。 【例5-4】 printf(Your str is %s,str); （2）使用puts () 函数 格式为：puts (字符数组名); 【例5-5】 printf(Your str is ); puts (str);,10,4.1.2 串的基本操作,下面给出串的基本操作。 (1)StrAssign(S,chars)：串赋值操作。将字符串chars的值赋值给串S。 (2)StrLength(S)：串长度操作。返回串S的长度，即串S中的元素个数。 (3)StrInsert(S,T,pos)：串插入操作。如果1posSt

6、rLength(S)+1时，在串S的第pos个字符之前插入串T。 (4)StrDelete(S,pos,len)：串删除操作。如果1posStrLength(S)-len+1，则从串S中删除第pos个字符起长度为len的子串。,11,4.1.2 串的基本操作,(5)StrCopy(S,T)：串复制操作。将串T复制到串S中。 (6)StrEmpty(S)：串判空操作。若串S为空串，则返回1；否则返回0。 (7)StrCompare(S,T)：串比较操作。若串S与T相等则返回1；否则返回0。 (8)StrClear(S)：串清空操作。将串S清为空串。 (9)StrConcat(S,T)：串连接操作

7、。将串T连接在串S的后面。,12,4.1.2 串的基本操作,(10)SubString(Sub,S,pos,len)：求子串操作。若存在位置1posStrLength(S)且1lenStrLength(S)-pos+1，则用Sub返回串S的第pos个字符起长度为len的子串。 (11)StrIndex(S,T)：串定位操作。若串S中存在和串T相同的子串，则返回它在串S中第一次出现的位置；否则返回0。 (12)StrReplace(S,T,pos,len)：串替换操作。当1posStrLength(S)且0lenStrLength(S)-pos+1时，用串T替换串S中从第pos个字符开始的len

8、个字符。 (13)StrDestroy(S)：串销毁操作。销毁串S。,13,4.2 串的存储结构,线性表的顺序和链式存储结构对于串都是适用的。但任何一种存储结构对于串的不同运算并非都是十分有效的。 对于串的插入和删除操作，顺序存储结构是不方便的，而链式存储结构则显得方便些。如果访问串中单个字符，对链表来说是不困难的；当要访问一组连续的字符时，用链式存储结构要比用顺序存储结构麻烦。,14,4.2.1 串的顺序存储结构,串的顺序存储就是把串所包含的字符序列依次存入连续的存储单元中去，也就是用向量来存储串。串的顺序存储结构如图4.1所示。 1定长存储的描述 在C+语言中，字符串顺序存储可以用一个字符

9、型数组和一个整型变量表示，其中字符数组存储串值，整型变量表示串的长度。,15,4.2.1 串的顺序存储结构,2存储方式 当计算机按字节（Byte）为单位编址时，一个存储单元刚好存放一个字符，串中相邻的字符顺序地存储在地址相邻的存储单元中。 当计算机按字（例如1个字为32位）为单位编址时，一个存储单元可以由4个字节组成。此时顺序存储结构又有非紧凑格式和紧凑格式两种存储方式。,16,4.2.1 串的顺序存储结构,（1）非紧凑存储 设串S=String Structure，计算机字长为32位（4个yte），用非紧凑格式一个地址只能存一个字符。其优点是运算处理简单，但缺点是存储空间十分浪费。,17,4

10、.2.1 串的顺序存储结构,（2）紧凑存储 同样存储S=String Structure，用紧凑格式一个地址能存四个字符。 紧凑存储的优点是空间利用率高，缺点是对串中字符处理的效率低。,18,4.2.1 串的顺序存储结构,定长顺序串是将串设计成一种结构类型，串的存储分配是在编译时完成的。 定长顺序串的存储结构使用C语言描述如下： #define MAXLEN 100 typedef struct char chMAXLEN; int len; SString;,19,4.2.1 串的顺序存储结构,下面是定长顺序串部分基本操作的实现。 1. 串连接操作 2. 串比较操作 3. 取子串操作 4.

11、串插入操作 5. 串删除操作 6. 串置换函数 7. 子串定位操作,20,4.2.1 串的顺序存储结构,串的模式匹配 模式匹配即子串定位运算。设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配。其中被匹配的主串s称为目标串，匹配的子串t称为模式。,21,4.2.1 串的顺序存储结构,（1）基本思想： 首先将s1与t1进行比较，若不同，就将s2与t1进行比较，直到s的某一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即i-j+2，t返回到t1，继续开始下一趟的比较，重复

12、上述过程。若t中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是ij+1，否则，匹配失败。 （2）模式匹配的例子 主串s=“ABABCABCACBAB”， 模式t=ABCAC“。,22,s=“ABABCABCACBAB” t=“ABCAC”,4.2.1 串的顺序存储结构,23,（2）时间复杂度分析 设串s长度为n，串t长度为m。匹配成功的情况下，考虑两种极端情况： 在最好情况下，每趟不成功的匹配都发生在第一对字符比较时： 例如：s=AAAAAAAAAABC t=BC 设匹配成功发生在si处，则字符比较次数在前面i-1趟匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i

13、-1+m次，所有匹配成功的可能共有n-m+1种，设从si开始与t串匹配成功的概率为pi，在等概率情况下pi=1/(n-m+1)，因此最好情况下的平均比较次数是：,24,即最好情况下的时间复杂度是O(n+m)。 在最坏情况下，每趟不成功的匹配都发生在t的最后一个字符。 例如：s=AAAAAAAAAAAB t=AAAB 设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏情况下平均比较的次数是：,因为nm，所以最坏情况下的时间复杂度是O (n*m)。,25,4.2.2 串的堆式存储,采用堆分配存储表示的串称为堆串。堆

14、串仍然采用一组地址连续的存储单元，存放串中的字符。但是，堆串的存储空间是在程序的执行过程中动态分配的。 在C语言中，由函数malloc和free管理堆的存储空间。利用函数malloc为新产生的串动态分配一块实际的存储空间，如果分配成功，返回一个指向存储空间起始地址的指针，作为串的基地址（起始地址）。如果内存使用完毕，使用函数free释放内存空间。,26,4.2.2 串的堆式存储,堆串可定义如下： typedef struct char *ch; int len; HString;,27,4.2.2 串的堆式存储,由于这种类型的串变量的串值的存储位置是在程序执行过程中动态分配的，与定长顺序串和链

15、串相比，这种存储方式是非常有效和方便的，但在程序执行过程中会不断生成新串和销毁旧串。 1. 串赋值操作 2. 串插入操作 3. 删除子串函数 4. 串连接函数,28,4.2.3 串的块链式存储结构,由于串也是一种线性表，因此串也可以采用链式存储表示。 串的链式存储结构与线性表的链式存储类似，通过一个结点实现。结点包含两个域：数据域和指针域。采用链式存储结构的串称为链串。由于串的特殊性-每个元素只包含一个字符，因此，每个结点可以存放一个字符，也可以存放多个字符。,29,4.2.3 串的块链式存储结构,每个结点称为一个块，整个链表称为块链结构，为了便于操作，再增加一个尾指针。结点大小为数据域中存放

16、字符的个数。 例如，图4.3(a)是结点大小为4(即每个结点存放4个字符)的链表，图4.3(b)是结点大小为1的链表。,30,4.2.3 串的块链式存储结构,由于串长不一定是结点大小的整数倍，因此，链串中的最后一个结点不一定被串占满，可以补上特殊的字符如“#”。,31,4.2.3 串的块链式存储结构,其数据类型为： #define CHUNKSIZE typedef struct Chunk char chCHUNKSIZE; struct Chuank *next; Chunk; typedef struct Chunk *head,*tail; int curlen; /*当前长度*/ L

17、String;,32,4.3 串 的 应 用,【例4.1】文本编辑。 参见教材P81 【例4.2】设有一篇英文短文，每个单词之间是用空格分开的，试编写一算法，按照空格数统计短文中单词的个数。 参见教材P83,33,本 章 小 结,(1) 串是一种数据类型受到限制的特殊线性表，它的数据对象是字符集合，每个元素都是一个字符，一系列相连的字符组成一个串。 (2) 串虽然是线性表，但又有其自己的特点：不是作为单个字符进行讨论，而是作为一个整体(即字符串)进行讨论。 (3) 串的存储方式也有顺序存储结构和链式存储结构，其中顺序存储可以是静态存储也可以是动态存储，定长顺序存储结构是静态存储，堆式存储结构是动态存储。 (4) 串的基本运算有串连接、两串相等判断、取子串、插入子串、删除子串、子串定位和串置换等。,34,习 题,一、填空题 参见教材P84 二、选择题 三、判断题 四、算法设计题,