数据结构课件PPT110章全 第四章 串.ppt 30页

'数据结构 第四章串4.1串类型的定义4.2串的表示和实现4.2.1定长顺序存储表示4.2.2堆分配存储表示4.2.3串的块链存储表示4.3串的模式匹配算法4.3.1求子串位置的定位函数4.3.2模式匹配的一种改进算法4.4串操作应用举例4.4.1文本编辑4.4.2建立词索引表 4.1串类型的定义一、串和基本概念串(String)是零个或多个字符组成的有限序列。一般记作S=‘a1a2a3…an’，其中S是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(EmptyString)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(BlankString)注意：空串和空白串的不同，例如’‘和’’分别表示长度为1的空白串和长度为0的空串。 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为A=“Thisisastring”B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3特别地，空串是任意串的子串，任意串是其自身的子串。通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在 程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C++中，可定义constcharpath[]=“dir/bin/appl”;这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。二、串的抽象数据定义串的抽象数据类型定义：书P71 三、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件。定义下列几个变量：chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;intresult;求串长(length)intstrlen(char*s);//求串的长度例如：printf(“%d”,strlen(s1));输出13 （2）串复制(copy)char*strcpy(char*to,char*from);该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。例如：strcpy(s3,s1);//s3=“dirtreeformat”(3)联接(concatenation)charstrcat(char*to,char*from)该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。例如：strcat(s3,”/”)strcat(s3,s2);//s3=“dirtreeformat/file.mem” (4)串比较（compare)intstrcmp(char*s1,char*s2);该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2例如：result=strcmp(“baker”,”Baker”)result>0result=strcmp(“12”,”12”);result=0result=strcmp(“Joe”,”Joseph”);result<0（5）字符定位(index)charstrchr(char*s,charc);该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。例如：p=strchr(s2,”.”);p指向“file”之后的位置if(p)strcpy(p,”.cpp”);s2=“file.cpp” 上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp。串的其余操作可由这些基本操作组合而成。例1、求子串求子串的过程即为复制字符序列的过程，将串S中的第pos个字符开始长度为len的字符复制到串T中。voidsubstr(stringsub,strings,intpos,intlen){if(pos<0||pos>strlen(s)-1||len<0)error(“parametererror”)strncpy(sub,&s[pos],len);} 例2、串的定位index(s,t,pos)在主串中取从第pos个字符起、长度和串T相等的子串和T比较，若相等，则求得函数值为pos，否则值增1直至S中不存在和串T相等的子串为止。 intindex(strings,stringt,intpos){if(pos>0){n=strlen(s);m=strlen(t);i=pos;while(is.length+1)returnerror;if(t.length){/*重新分配字符串s的存储空间*/if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char)))exit(overflow);/*移动s中pos位置之后的字符*/for(i=s.length-1;i>=pos-1;--i)s.ch[i+t.length]=s.ch[i];/*插入字符串t并修改字符串s的长度*/s.ch[pos-1..pos+t.length-2]=t.ch[0..t.length-1];s.length+=t.length;}returnok;} /*求字符串s的长度*/intstrlen(hstrings){returns.length;}/*清除字符串s*/statusclearstring(hstring&s){if(s.ch){free(s.ch);s.ch=NULL;}s.length=0;returnok;} /*生成一个其值等于串常量chars的串t*/statusstrassign(hstring&t,char*chars){/*释放字符串t原有的空间*/if(t.ch)free(t.ch);/*计算字符串chars的长度*/for(i=0,(c=chars;c;++i),++c);if(!i){/*若chars长度为0，则设置字符串t为空字符串*/t.ch=null;t.length=0;}else{/*否则，分配空间并拷贝chars到字符串t中*/if(!(t.ch=(char*)malloc(I*sizeof(char))))exit(overflow);t.ch[0..i-1]=chars[0..i-1];t.length=i;}returnok;} /*比较字符串s,t的大小*/intstrcmp(hstrings,hstringt){/*在s和t的长度范围内逐个比较字符，找到一个不相等字符，返回该字符的比较结果*/for(i=0;is.length||len<0||len>s.length-pos+1)returnerror;/*释放sub的空间*/if(sub.ch)free(sub.ch);if(!len){/*若长度len为0，则设置sub为空串*/sub.ch=null;sub.length=0;}else{/*否则，分配空间，并拷贝第pos个字符起长度为len的子串，并设置长度*/sub.ch=(char*)malloc(len*sizeof(char));sub.ch[0..len-1]=s[pos-1..pos+len-2];s.length=len;}returnok;} 4.2.3串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。typedefstructnode{chardata;structnode*next;}lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。 为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。#defineCHUNKSIZE80typedefstructChunk{chardata[CHUNKSIZE];structChunk*next;}Chunk;Typedefstruct{Chunk*head,*tail;intcurlen;}LString; 4.3串的模式匹配算法子串定位运算又称为模式匹配(PatternMatching)或串匹配(StringMatching)，此运算的应用在非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。在串匹配中，一般将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设：S=“s0s1s2…sn-1”T=“t0t1…tm-1”串的匹配实际上是对于合法的位置0≦i≦n-m依次将目标串中的子串s[i..i+m-1]和模式串t[0..m-1]进行比较，若s[i..i+m-1]=t[0..m-1]， 则称从位置i开始的匹配成功，亦称模式t在目标s中出现；若s[i..i+m-1]≠t[0..m-1]，，则称从位置i开始的匹配失败。上述的位置i又称为位移，当s[i..i+m-1]=t[0..m-1]时，i称为有效位移；当s[i..i+m-1]≠t[0..m-1]时，i称为无效位移。这样，串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移。串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0≦i≦n-m)是否为有效位移 其算法段为：for(i=0;i<=n-m;i++){if(S[i..i+m-1]=T[0..m-1]returni;}下面以第二种定长的顺序串类型作为存储结构，给出具体的串匹配算法。 intindex(sstrings,sstringt,intpos){inti,j,k;intm=s.length;intn=t.length;for(i=0;i<=n-m;i++){j=0;k=i;while(jdata==p->data){q=q->next;p=p->next;}else{shift=shift->next;q=shift;p=t;}}if(p==null)returnshift;elsereturnnull;} 4.4串操作应用举例文本编辑1.插入2.删除3.修改建立词索引表1.建立索引表2.定位单词 基础知识题自己做习题4.12,4.17,4.24'