数据结构课件(c语言(1).ppt

第4章 串 1 第4章 串 本章知识点 u 串的概念和基本术语 u 串的基本运算和操作 u 串的存储方式：顺序存储和链式存储 u 串的模式匹配 本章学习要求 （1）了解串的概念 （2）掌握串的逻辑结构、存储结构、及各种基本操作和实现 （3）了解串的模式匹配算法的基本思想 第4章 串 4.1串的基本概念及其基本运算 4.1.1 串的基本概念 串（字符串）：是由零个或多个字符组成 的有限序列。 一般标记为： s = “ “ ( n0) 注意：空串不等同于空格串 串中任意的一个连续的字符构成的序列称为 这个串的子串，相应的，我们称包含该子串 的串为主串。 串是可以进行比较的。 从逻辑上看，串和线性表非常类似，区 别仅在于串的数据对象是字符的集合。 但是由于字符串往往将整个串作为操作 的对象，而不是像线性表那样，以单个 元素作为操作对象，所以在基本操作上 ，串与线性表有较大的区别。 第4章 串 4.1.1 串的基本概念 串在实际应用中经常出现。如程序设计语言中的源程序和目标 程序都是字符串数据，事物处理中的顾客的姓名、地址等都用 字符串来描述。 【例4.1】 如有下列四个字符串，求出各串的长度，判断其中 是否有子串，如果有，求出其在主串中的位置。 S1=“ILOVEFUJIAN”; S2=“ILOVE”; S3=“FUJIAN”; S4=“FUJIAN”; 以上字符串的长度为：S1长度13；S2长度6；S3长度6；S4长度7 ； 其中，S2和S3均为S1的子串，它们在主串S1的位置分别为1和8； 但是S4并不是S1的子串，且这个四个串均不相等。 第4章 串 4.1.2 串的基本操作 1、求串的长度 StrLen( s ) 2、串比较 StrCmp（s1 , s2) 3、串连接 Concat（s1，s2） 4、求子串 SubStr（s，start，len） 5、串复制 StrCopy(s1, s2 ) 6、插入子串 StrInsert (s1, pos , s2) 7、删除子串：StrDelete (s, pos, len ) 8、串置换 StrReplace(s1, pos , s2) 9、串赋值 StrAssign(s1, s2) 10、串定位 Index（s1, s2） 第4章 串 4.2 串的存储结构 串实际是一种特殊的线性表，它的结点仅由一个字符组成，存储结构和线性表 也类似。一般来说，常见的有两种存储方法：顺序存储、链式存储和堆存储。 4.2.1 串的顺序存储结构 和线性表的顺序存储一样，串的顺序存储结构也称为静态存 储结构，就是采用与逻辑结构相对应的存储结构，即将串的各 个字符按顺序存入地址连续的存储单元中，因此逻辑上相邻的 字符在内存中的存储的位置也是相邻的，这样的串称为顺序串 。 由于一个字符只占一个字节，因此采用顺序存储结构的串有 非压缩格式（一个字存储单元中存放一个字符）和压缩格式（ 根据机器字的长度，尽可能将多个字符存放在一个内存单元内 ，如一个字节存放一个字符）两种形式。 第4章 串 4.2.1 串的顺序存储结构 例如，串S =“CHINAFUJIAN”的顺序存储结构如图4.1（a） 所示： 串的顺序结构类型可定义如下： Const maxlen=100 typedef struct char str maxlen ; int len ; SeqString ; 提示：C语言中，数组以0开始作为下标，每个字符占内存一个 字节，且具体存储时每个字符串最后都会使用字符串结束标志 “0”，遇到“0”即认为字符串结束。 第4章 串 串的顺序存储结构的部分基本操作 1、求串长StrLen算法实现： 2、串复制StrCopy算法实现： SeqString *StrCopy(SeqString *s1, SeqString * s2 ) int i; for (i=0 ; ilen ;i+) s1-stri=s2-stri ; s1-len = s2-len ; /*设置s1的长度*/ return (s1) ; 第4章 串 3、求子串SubStr的算法实现：从串s中的第pos个字符开始取长度为 len的子串，并返回给sub。 SeqString *SubStr（SeqString s, int pos, int len , SeqString *sub） int i; if (pos=s.len | lens.len-pos+1) /*判断pos和len是否合法*/ printf(“pos or len error ! ”) ; return NULL ; for (i=0 ; istri = s.strpos+i-1 ; /* 将子串复制给sub */ sub-len = len ; return (sub) ; 第4章 串 4、删除子串StrDelete算法实现：从串s 中的pos位置开始，删除len个 字符，并返回串s。 SeqString *StrDelete(SeqString *s ,int pos , int len ) int i; if (pos = s-len | len s-len-pos+1) printf( “pos o r len error !”) retrun NULL ; for (i=pos+len-1;ilen ;i+) s-stri-len = s-stri ; s-len= s-len len ; return (s); 思考：串的插入操作如何实现？ 第4章 串 4.2.2 串的链式存储结构 由于串的特殊性结构中的每个数据元素是一个 字符，则使用链表存储串值时，每个结点可以存放 一个字符，也可以存放多个字符，结点中存放字符 的个数称为“结点大小”。 图4.2（a）是结点大小为3的链表 headabcefghij headaeh headabcefghijheadabcefghij 第4章 串 串的链式结构类型可定义如下： const nodesize=80 Typedef struct node char datanodesize ; /*一个结点存多个字符*/ struct node *next ; /*链指针*/ linkstring ; 或Typedef struct node char data ; /*一个结点存一个字符*/ struct node *next ; LinkString ; 第4章 串 链式存储结构的插入串操作StrInsert的算法 将串s2插入到串s1中的第i个字符开始的位置上(第i个结点之后）*/ linkstring *StrInsert（linkstring *s1， linkstring *s2，int i） int k ; linkstring *p ,*q ; p=s1 ; k=1 ; while (knext ; k+ ； if (p=NULL) printf(“overflow ! n”) ; else q=s2 ; while (q!=NULL) q=q-next ; q-next=p-next ; p-next = s2 ; return (s1) ; 第4章 串 4.3 串的模式匹配运算 4.3.1 基本的模式匹配算法 子串定位操作又称为串的模式匹配（pattern matching），就是判断一 个串是否是另一个已知串的子串,如果是其子串，则给出该子串的起始 点（即是从已知串的哪个字符开始），则称匹配成功，否则则匹配失 败。该操作是各种串处理系统的重要操作之一。例如，在文本编辑程 序中，我们经常要查找某一特定单词在文本出现的位置。显然，高效 的模式匹配算法能大大地提高文本编辑程序效率。本章只讨论简单的 模式匹配算法。 假设存在主串S （又称目标）和子串T（又称模式） ,模式匹配算法基 本思想:从主串的第一个字符起与子串T 的第一个字符进行比较，若相 等则继续比较它们的后续字符，否则从主串S 的下个字符起重新与子 串T的第一个字符进行比较。以此类推，直到子串T中的每一个字符依 次与主串S中的每一个连续的字符序列相等，则匹配成功，否则匹配 失败。 第4章 串 设有两个串S 和 T ,其中：目标S=”abbaba”,模式T=”aba” ,匹配过 程如图所示： 第一次匹配： S= a b b a b a i=3 T=a b a j=3 失败 第二次匹配： S= a b b a b a i=2 T= a b a j=1 失败 第三次匹配： S= a b b a b a i=3 T= a b a j=1 失败 第四次匹配： S= a b b a b a i=6 T= a b a j=3 成功 第4章 串 简单模式匹配算法 int StrIndex (SeqString *S, SeqString *T ) int i, j ; i= ; j= ; /注从字符数组的第个字符开始比 while(ilen /*字符比较不成功，i指针回溯，并充T的第一个字符起重新比较*/ else i=i-j+;j= ; if (jT-len ) return (i-T-len+1 ); /*匹配成功*/ else return （0）; /*匹配失败*/ 第4章 串 简单模式匹配算法分析 在某趟匹配过程中，若出现字符比较不相等，则指 向主串的指针需要回溯，需要从模式串的第一个字 符重新开始比较。没有利用已经比较成功的工作。 设主串和模式串的长度分别为n、m，在最坏的情况 下（即第i趟匹配成功，前面的i-1趟不成功），每趟 比较了m次，第i趟也比较了m次，那么上述算法所 执行的字符比较总数为m *(n-m+1)。如果用比较次 数来衡量算法的时间复杂度，则上诉算法的时间复 杂度为O(m*(n-m),若nm ，则时间复杂度为 O(m*n). 第4章 串 4.3.2 模式匹配的改进算法KMP算法 该算法相较于StrIndex的改进之处在于：每当一趟匹 配过程出现字符比较不等时，指向主串的指针i不回溯 ，而是利用已经得到的“部分匹配”结果将模式串向右 滑动一段距离后继续进行比较。该算法可以在O(m+n) 的数量级上完成串的模式匹配。 如在匹配过程中：第一次回，当S0=T0 ,S1=T1,S2T2 时，算法中取i=1，j=0，比较S1 和T0 因为T0T1,一 定有S1T0,所以可直接在第二次匹配时取i=2，j=0去 比较S2和T0。这样，模式匹配过程主串指针i就不用回 溯。 第4章 串 希望