数据结构幻灯片-(4)

《数据结构幻灯片-(4)》由会员分享，可在线阅读，更多相关《数据结构幻灯片-(4)（41页珍藏版）》请在金锄头文库上搜索。

1、实用数据结构基础,第5章 串,第 5 章 串,知 识 点 串的有关概念和术语 串的基本运算 串的存储方法 串的模式匹配运算,难 点 串的模式匹配运算算法 要 求 掌握串的逻辑结构 掌握串的存储结构 熟练掌握串的基本运算 能设计串的计简单算法 了解串的匹配运算算法的基本思想,第 5 章 目录,5-1 串的定义和基本运算 5-2 串的表示和实现 5-3 串的基本运算 小 结 实验5 串子系统 习题5,5-1 串的定义和基本运算,5-1-1 串的定义 1. 串的定义 串（String）是由零个或多个任意字符组成的有限序列。一般记作： s=a1 a2 aian 其中s 是串名，用双引号括起来的字符序列

2、为串值，但引号本身并不属于串的内容。ai（1=i=n）是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数。,2几个术语 （1）长度串中字符的个数，称为串的长度。 （2）空串长度为零的字符串称为空串。 （3）空格串由一个或多个连续空格组成的串称为空格串。 （4）串相等两个串是相等的，是指两个串的长度相等且对应字符都相等。 （5）子串串中任意连续的字符组成的子序列称为该串的子串。 （6）主串包含子串的串称为该子串的主串。 （7）模式匹配子串的定位运算又称为串的模式匹配，是一种求子串的第一个字符在主串中序号的运算。被匹配的主串称为目标串

3、，子串称为模式。,【例5-1】字符串的长度及子串的位置。 字符串 字符串长度 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。,3串的应用 在汇编语言和高级语言的编译程序中，源程序和目标程序都是以字符串表示的。在事务处理程序中，如客户的姓名、地址、邮政编码、货物名称等，一般也是作为字符串数据处理的。另外，信息检索系统，文字编辑系统，语言翻译系统等，也都是以字符串数据作为处理对象的。,5-1-2

4、串的输入与输出 1字符串的输入 在C语言中，字符串的输入有两种方法： （1）使用scanf () 函数 使用scanf () 函数时，输入格式中要设置%s，再加上字符数组名称。 【例5-2】 char str10; printf(Input your str: ); scanf(%s,str); 使用scanf ()方式输入时，字符串中不能含有空格。 在C+中还可以用输入流对象cin 。,（2）使用gets() 函数 格式为：gets(字符数组名); 【例5-3】 char str10; printf(Input your str: ); gets(str); 使用gets ()方式输入时，字

5、符串中允许含有空格。,2字符串的输出 字符串的输出也有两种方法： （1）使用printf () 函数 使用printf () 函数时，输出格式中要设置%s，再加上字符数组名。 【例5-4】 printf(Your str is %s,str); 在C+中还可以用输出流对象cout 。 （2）使用puts () 函数 格式为：puts (字符数组名); 【例5-5】 printf(Your str is ); puts (str);,5-1-3 串的基本运算 求串长LenStr(s) 操作条件：串s存在 操作结果：求出串s的长度。 串连接：ConcatStr(s1,s2) 操作条件：串s，s1存

6、在。 操作结果：新串s1是串s1和串s2连接以后的新串，原串s2值不变，串s1的值则改变。 【例5-6】设 s1=Micsosoft，s2=Office， 求两个串连接的结果。 操作结果：s1=MicsosoftOffice； s2=Office。,3. 求子串SubStr (s,i,len)： 操作条件：串s存在。 操作结果：返回从串s的第i个字符开始的长度为 len 的子串。len=0得到的是空串。 【例5-7】 SubStr (abcdefghi,3,4) = cdef” 4. 串比较： EqualStr (s1,s2) 操作条件：串s1,s2存在。 操作结果：若s1= =s2，返回值为

7、0；若s1s2, 返回值0。 5. 子串查找 IndexStr (s,t)：找子串t在主串s中首次出现的位置（也称模式匹配）。 操作条件：串s，t存在。 操作结果：若t是s的子串，则返回t在s中首次出现的位置，否则返回值为0。,【例5-8】子串定位 IndexStr (abcdebda,bc)=2 IndexStr (abcdebda,ba)= 0 6. 串插入 InsStr (s,t,i) 操作条件：串s，t存在 操作结果：将串t插入到串s 的第i个字符前，s的串值发生改变。 7. 串删除 DelStr(s,i,len) 操作条件：串s存在 操作结果：删除串s 中第i个字符起长度为len的子

8、串，s的串值改变。,5-2 串的表示和实现,5-2-1 定长顺序存储 1定长存储的描述 在C+语言中，字符串顺序存储可以用一个字符型数组和一个整型变量表示，其中字符数组存储串值，整型变量表示串的长度。 #define MAXLEN 100 typedef Struct char vecMAXLEN; int len; Str ; / 可用Str来定义该类型的结构体变量,2存储方式 当计算机按字节（Byte）为单位编址时，一个存储单元刚好存放一个字符，串中相邻的字符顺序地存储在地址相邻的存储单元中。 当计算机按字（例如1个字为32位）为单位编址时，一个存储单元可以由4个字节组成。此时顺序存储结构

9、又有非紧凑格式和紧凑格式两种存储方式。 （1）非紧凑存储 设串S=String Structure，计算机字长为32位（4个yte），用非紧凑格式一个地址只能存一个字符，见图5-1。其优点是运算处理简单，但缺点是存储空间十分浪费。 （2）紧凑存储 同样存储S=String Structure，用紧凑格式一个地址能存四个字符，见图5-2。 紧凑存储的优点是空间利用率高，缺点是对串中字符处理的效率低。,图5-1 非紧凑格式 图5-2 紧凑格式,5-2-2 链接存储 对于长度不确定的字符串的输入，若采用定长字符串存储就会产生这样的问题：存储空间定的大，而实际输入字符串长度小，则造成内存空间的浪费；反

10、之，存储空间定的小，而实际输入字符串长度大，则不够存储。此时可采用链接存储的方法。 1链接存储的描述 用链表存储字符串，每个结点有两个域：一个数据域（data）和一个指针域（next）。,其中: 数据域（data） 存放串中的字符； 指针域（next） 存放后继结点的地址。 仍然以存储S=String Structure为例，链接存储结构如图5-3所示。,图5-3 链接存储结构 （1）链接存储的优点插入、删除运算方便； （2）链接存储的缺点存储、检索效率较低。 2串的存储密度 在各种串的处理系统中，所处理的串往往很长或很多。例如一本书的几百万个字符，情报资料的几千万个条目，这要求我们必须考虑字

11、符串的存储密度。 存储密度 = 串值所占的存储位 / 实际分配的存储位。 串链接存储的存储密度小，存储量比较浪费，但运算处理，特别是对串的连接等操作的实现比较方便。,图5-4 大结点结构表示 这样一来，存储空间利用率明显提高，但插入、删除极不方便，所以链接存储的优点也消失了。由于字符串的特殊性，用链表作为字符串的存储方式也不太实用，因此使用较少。,3大结点结构 为了提高存储空间的利用率，有人提出了大结点的结构（即串的链块表示）。 所谓大结点，就是一个结点的值域存放多个字符，以减少链表中的结点数量，从而提高空间的利用率。例如每个结点存放四个字符，如图5-4。,5-2-3 串的堆分配存储结构 在实

12、际应用中，往往要定义很多字符串，并且各字符串长度在定义之前又无法确定。在这种情况下，可以采用堆分配存储（也称为索引存储），这是一种动态存储结构。 1堆分配存储的方法 （1）开辟一块地址连续的存储空间，用于存储各串的值，该存储空间称为“堆”（也称为自由存储区）。 （2）另外建立一个索引表，用来存储串的名字（name）、长度（length）和该串在“堆”中存储的起始地址（Stradr）。 （3）程序执行过程中，每产生一个串，系统就从“堆”中分配一块大小与串的长度相同的连续空间，用于存储该串的值， 并且在索引表中增加一个索引项，用于登记该串的名字、 长度、和该串的起始地址。,2索引存储的例子 设字符

13、串：A=”Red” B=”Yellow” C=”Blue” D=”White” 用指针free指向堆中未使用空间的首地址。,图5-5 带长度的索引表,Name,A,B,C,D,Length,3,6,4,5,Stradr,堆：,R,e,d,Y,e,l,l,o,w,B,l,u,E,W,h,i,t,e,free,索引表：,考虑到对字符串的插入和删除操作，可能引起串的长度变化，在“堆”中为串值分配空间时，可预留适当的空间。这时，索引表的索引项应增加一个域，用于存储该串在“堆”中拥有的实际存储单元的数量。当字符串长度等于该串的实际存储单元时，就不能对串进行插入操作。 3带长度的索引表的C语言描述 如图5

14、-5所示，索引项的结点类型为： typedef Struct char nameMAXLEN; / 串名 int length; / 串长 char *Stradr; / 起始地址 LNode;,4 “堆”的管理 C语言中用动态分配函数malloc( )和free( )来管理“堆” 利用函数malloc( )为每个新串分配一块实际串长所需要的存储空间，分配成功则返回一个指向起始地址的指针，作为串的基址，同时，约定的串长也作为存储结构的一部分。函数free( )则用来吸收用malloc( )分配的存储空间。 在C+语言中malloc( )可用new替换，而free( )也可用delete代替。 在这里，我们仅仅简单的介绍了堆分配存储的基本思想，具体的算法及细节尚未涉及。在常用的高级语言及开发环境中，许多系统本身都提供了串的类型及串的库函数，用户可以直接调用，这样会使算法的设计和调试更方便容易，可靠性也更高。,本小节主要讨论定长串连接、求子串、串比较算法，顺序串的插入和删除等运算。 为了讨论方便我们再次描述定长顺序串的结构如下： #define MAXLEN 100 / 定义串的最大长度 typedef struct char vecMAXLEN; int len; / 串的实际长度 Str ; / 定义一个结构体类型Str 在串尾存储一个不会在串中出现的特殊字符作为串