数据结构实验四字符串的应用

1、第四章字符串的应用 【实验目的】1. 熟练掌握字符串的数据类型定义以及字符串的五种基本操作的定义，并能利用这些基本操作实现字符串的其他基本操作的方法。2. 熟练掌握字符串串的定长顺序存储结构上实现字符串的各种操作的方法。3. 理解字符串的堆分配存储表示以及在其上实现字符串操作的基本方法。4. 熟练掌握串的基本操作类型的实现方法，其中文本模式匹配方法是一个难点，在掌握了BF算法的基础上理解改进的KMP算法。5. 了解一般文字处理软件的设计方法。第一节知识准备一、 有关串几个重要概念1. 串（字符串）：零个或多个字符组成的有限序列。一般记作s=a1a2an(n0)2. 长度：串中字符的数目3. 空

2、串：零个字符的串，其长度为零4. 子串和主串：串中任意个连续的字符组成的子序列称为该串的子串；包含子串的串相应地称为主串，字符在序列中的序号为该字符在串中的位置。5. 当两个串的长度相等，并且各个对应位置的字符都相等时称为两串相等。6. 空格串：由一个或多个空格组成的串，同空串是完全不同的。二、 串的抽象数据类型定义ADTString数据对象：D=|CharacterSet,i=1,2,.,n,n=0数据关系：R1=|,D,i=2,.,n基本操作： Assign(&s,t) 将串t的值赋给串sCreate(&s,ss) 将串s的值设定为字符序列ssEqual(s,t) 判定串s和串t是否相等L

3、ength(s) 求串s的长度Concat(&s,t) 将串s和串t连接成一个串，结果存于s中Substr(&sub,s,start,len)从s的第start个字符起，取长为len的子串存于subIndex(s,t) 求子串t在主串s中第一次出现的位置Replace(&s,t,v) 以串v替换串s中的所有的非空子串tInsert(&s,pos,t) 在串s的第pos个字符之前插入串t；Delete(&s,pos,len) 从串s中删去从第pos个字符起长度为len的子串；ADTString三、 串的存储结构1. 定长顺序存储表示用一组地址连续的存储单元来存放字符序列，并约定该结构能存放字符的

4、个数。#defineMAXLEN字符最大个数typedefstructintlen;charchMAXLEN;SString;2. 堆分配存储表示系统先分配一个容量很大的地址连续的存储空间作为字符串的存放空间，每建立一个新串，系统从该空间中分配一个大小和串长相同的空间来存放新串。typedefStructchar*ch;/存储空间基址intlength;/串的长度Hstring;3. 串的块链存储表示用链表形式来存储串，如果以串中每一个字符作为一个结点，使得相应的存储占用量增大，因此可采用将多个字符作为一个结点的形式来形成链表(即块链形式)#defineMAX80/用户定义块的大小typede

5、fstructstrcharchMAX;structstr*next;Chunk;typedefstructstringChunk*head,*tail;intlength;LString在串的处理操作中，我们可视不同的情况进行选择使用不同的定义形式，当对字符串进行连接，删除等操作时，采用链结构更为方便上些，但采用链结构在进行串的截取(求子串)等操作时则比采用静态结构效率更低。第二节串的基本操作示例【问题描述】用C语言实现串的一些基本操作算法。【数据描述】采用静态存储结构来表示串，用一维字符数组来存放字符序列，用整数len来表示当前串实际长度。#defineSTRINGMAX81/串最多存放字

6、符的个数structstringintlen;charchSTRINGMAX;typedefstructstringSTRING;【C源程序】本程序只设计了串的创建，联接，求子串和删除操作，其余各基本操作可在本程序基础上进行改进，补充。#includestdlib.h#includestdio.h#defineSTRINGMAX81#defineLENsizeof(structstring)/*串的定义*/structstringintlen;charchSTRINGMAX;typedefstructstringSTRING;voidcreat(STRING*s);voidprint(STRI

7、NG*s);voidconcat(STRING*s,STRING*t);STRING*substr(STRING*s,intstart,intlen);voiddelete(STRING*s,intstart,intlen);main()STRING*s,*t,*v; /*定义三个采用静态存储形式的串*/intstart,len;intposition;t=(STRING*)malloc(LEN); /*为三个串分配相应的存储空间*/s=(STRING*)malloc(LEN);v=(STRING*)malloc(LEN);printf(pleaseinputthestrings:); /*创

8、建S串*/creat(s);printf(pleaseinputthestringt:); /*创建T串*/creat(t);concat(s,t); /*连接并输出相应的串*/printf(thenewstrings:);print(s);printf(pleseinputthestartposition:);/*输入截取子串的起始位置*/scanf(%d,&start);printf(pleaseinputthelength:);/*输入截取子串的长度*/scanf(%d,&len);v=substr(s,start,len); /*截取子串*/printf(“thesubstring:”

9、);print(v);printf(pleseinputthestartposition:);/*输入删除串的起始位置*/scanf(%d,&start);printf(pleaseinputthelength:); /*输入删除串的长度*/scanf(%d,&len);delete(s,start,len); /*删除串*/printf(thedeletedstrings:);print(s);voiddelete(STRING*s,intstart,intlen)inti;if(startlen&len=0&start+lenlen)/*删除操作合法性验证*/for(i=start+len

10、;ilen;i+) /*从start位置开始移动元素*/s-chi-len=s-chi;s-len=s-len-len; /*置新的长度*/elseprintf(cannotdelete!n);STRING*substr(STRING*s,intstart,intlen)inti;STRING*t;t=(STRING*)malloc(LEN);if(start=s-len) /*取子串的合法性验证*/return(NULL);elseif(len=1&lenlen-start)for(i=0;ichi=s-chstart+i;t-len=len; /*置子串长度*/t-chi=0;return

11、(t);else return(NULL);voidconcat(STRING*s,STRING*t)inti,j;if(s-len+t-len(STRINGMAX-1) /*连接操作合法性验证*/printf(toolong!cannotconcat!);elsej=s-len;for(i=0;ilen;i+)s-chi+j=t-chi; /*将串t中字符序列放入串s的尾部*/s-chi+j=0;s-len=s-len+t-len; /*置新串s的长度*/voidcreat(STRING*s)charc;inti;for(i=0;(c=getchar()!=n&ichi=c; /*将输入的字

12、符序列放入串的字符数组中*/s-len=i; /*置串的长度*/s-chi=0;voidprint(STRINGs) /*输出串的字符序列*/inti;for(i=0;s-chi!=0;i+)printf(%c,s-chi);printf(n);【测试数据】pleaseinputthestrings:abcdpleaseinputthestringt:efgthenewstrings:abcdefgpleseinputthestartposition:3pleaseinputthelength:3thesubstring:defpleseinputthestartposition:3pleas

13、einputthelength:3thedeletedstrings:abcg【分析说明】1. 上述程序采用的是串的静态存储形式，在定义串时对串可能容纳的字符个数要正确估计，否则会造成存储空间的大量浪费；2. 在进行串的连接操作时，还必须考虑连接后形成的新串长度是否会大于串定义的最大长度；采用链式存储形式可以解决上述问题。3. 如果采用链式存储形式，在某些操作实现中时间效率将会降低，如在删除操作中需首先找到删除的第一个字符，这样就需先移动指针找到删除点才能进行，而静态形式可直接从下标为起始点的字符起即可进行操作，因此，在设计不同的串处理应用程序时应根据可能进行的操作而选择相应比较合适的数据存储

14、形式。【实验题】1 根据以上程序采用的静态存储形式，完成串的置换、串的定位、串的插入操作的实现。2 选择一种链式存储形式，完成串的基本操作。第三节 字符串操作演示系统【问题描述】用户自己实现串类型，并写一个串的基本操作的演示系统。在该演示系统中能提供命令行的输入，并能对输入的命令行进行简单的编译并作相应的出错处理，最后根据命令动词功能来执行命令行。命令定义如下：1.赋值：assign串名1串名2例如输入命令assignsstt操作的结果是将串tt赋值给了ss串2.新建：creat串名字符串常量例如输入命令creatssabcdefg操作的结果是将字符串常量赋值给串ss，注意：字符串常量两边用单

15、引号括起来，不能省略。3.判等：equal串名1串名2例如输入命令equalsstt操作的结果是根据两串比较的结果输出相应的信息4.求串长：length串名操作的结果是返回字符串长度5.字符串连接：concat串名1串名2新串名例如输入命令concatssttv操作的结果是将串ss和串tt连接起来(ss在前，tt在后)形成一个新串，并输出新串6.求子串：substr串名起始位置子串长度新子串名例如输入命令substrss13t操作的结果是将串ss从起始位置1开始的3个字符存入到串t中7.子串定位：index串名1串名2起始位置例如输入命令indexsst1操作的结果是返回串t在串ss从第1个字

16、符后的字符序列中第一次出现的位置8.退出：quit功能：结束演示系统运行【数据描述】1.定义串的数据类型为指向字符的指针typedefchar*STRING;/*定义新的字符串类型，即指向字符的指针*/2.在本程序中支持串名操作，因此需将各字符串所对应的串名和首地址都存放在一个串头表中structstrheadlistSTRINGstrhead100;/*字符串首地址*/STRINGstrname100;/*字符串的串名*/intcurnum;/*当前串头表中串的数目*/3.对于提示符下输入的每一行命令，在进行分析以后，需要保留分析的结果(参数最多有6个)structresultintnum;

17、/*命令行中参数的个数(含命令动词)*/intnametype6;/*命令行中各参数的类型*/STRINGstr6;/*命令行中各参数都以字符串的形式返回*/注：参数类型以整型表示，如为1，则表示参数为命令动词；如为2，则表示参数为字符串如为3，则表示参数为整数如为4，则表示参数为串名可以仿照DOS操作系统来进行设计，提供命令行提示符，并能输入相应命令，并将命令行拆分为不同的几个部分（类似统计单词个数），再根据编译的结果进行相应的处理。【C源程序】#includestdlib.h#includestdio.htypedefchar*STRING;/*定义新的字符串类型，即指向字符的指针*/st

18、ructstrheadlistSTRINGstrhead100;STRINGstrname100;intcurnum;/*定义指向字符串的字针数组，并存放各字符串的串名（串名也用字符串来表示），及当前堆中串的数目*/structresultintnum;intnametype6;STRINGstr6;/*定义命令行编译以后形成的命令及参数等数据*/intstrtoint(STRINGs);voidcreat(STRINGs,STRINGss);voidassign(STRINGs,STRINGt);intequal(STRINGs,STRINGt);intlength(STRINGs);voi

19、dconcat(STRINGs,STRINGt,STRINGv);voidsubstr(STRINGs,intstart,intlen,STRINGv);intindex(STRINGs,STRINGt,intstart);structresultcmdsyna(introw);intlookup(STRINGs);structstrheadlisthead;charcmd4080;main()structresultcomm;introw=0,i;charc;intequ;head.curnum=0;while(1)/*重复输入并处理相应命令*/printf(CMD);for(i=0;(c=

20、getchar()!=n;i+)cmdrowi=c;cmdrowi=0;comm=cmdsyna(row);/*对各命令动词进行判数并作参数分析*/if(strcmp(comm.str0,creat)=0)/*字符串创建*/if(comm.num!=2)printf(Parametersiswrong!n);elseif(lookup(comm.str1)!=-1)printf(String%scannotbecreat!n); elseif(type1=4&type2=2)creat(comm.str1,comm.str2);elseif(strcmp(c

21、omm.str0,assign)=0)/*字符串赋值*/if(comm.num!=2)printf(Parametersiswrong!n); elseassign(comm.str1,comm.str2);elseif(strcmp(comm.str0,equal)=0)/*字符串判等*/if(comm.num!=2)printf(Parametersiswrong!n);elseif(lookup(comm.str1)=-1|lookup(comm.str2)=-1)printf(String%sor%sisnotfound!n,comm.str1,comm.str2);elseif(eq

22、ual(head.strheadlookup(comm.str1),head.strheadlookup(comm.str2)=1)printf(Equal!n);elseprintf(Notequal!n);elseif(strcmp(comm.str0,length)=0)/*字符串求长*/if(comm.num!=1)printf(Parametersiswrong!n);elseif(lookup(comm.str1)=-1)printf(Thestring%sconnotbefound!n);elseprintf(String%s:%slengthis%dn,comm.str1,he

23、ad.strheadlookup(comm.str1),length(head.strheadlookup(comm.str1);elseif(strcmp(comm.str0,concat)=0)/*字符串连接并形成新的字符串*/if(comm.num!=3)printf(Parametersiswrong!n);elseif(lookup(comm.str1)=-1|lookup(comm.str2)=-1)printf(Thestring%sor%sisnotfound!n,comm.str1,comm.str2);elseif(lookup(comm.str3)!=-1)printf(

24、String%sconnotbecreat!n,comm.str3);elseconcat(head.strheadlookup(comm.str1),head.strheadlookup(comm.str2),comm.str3);elseif(strcmp(comm.str0,substr)=0)/*取字符串子串，并形成新的字符串*/if(comm.num!=4)printf(Parameterswrong!n);else if(lookup(comm.str1)=-1)printf(String%sisnotfound!n,comm.str1);elseif(lookup(comm.st

25、r4)!=-1)printf(String%sconnotbecreat!n,comm.str4);elseintstart,len;start=strtoint(comm.str2);len=strtoint(comm.str3);substr(head.strheadlookup(comm.str1),start,len,comm.str4);elseif(strcmp(comm.str0,index)=0)/*字符串定位*/if(comm.num!=3)printf(Parameterswrong!n);elseif(lookup(comm.str1)=-1|lookup(comm.st

26、r2)=-1)printf(String%sor%sisnotfound!n,comm.str1,comm.str2);elseintstart,flag=-1;start=strtoint(comm.str3);flag=index(head.strheadlookup(comm.str1),head.strheadlookup(comm.str2),start);if(flag=-1)printf(String%sstart%d,String%sisnotindex!n,comm.str1,start,comm.str2);elseprintf(String%sstart%d,String

27、%sisindex%d!n,comm.str1,start,comm.str2,flag);elseif(strcmp(comm.str0,quit)=0)/*退出演示系统*/printf(ByeBye!n);break;elseprintf(Badfilenameornocommand!n);/*错误命令动词提示*/row+;intstrtoint(STRINGs)/*将字符串转换成整数常量*/inti=0;inttotal=0;while(si!=0)total=total*10+si-48;i+;return(total);intlookup(STRINGs)/*查找串表中是否存在串名所

28、对应的字符串，如存在则返回所对应的位置，否则返回-1*/inti;intlook=-1;for(i=0;i=0&cmdrowstart=9) typeres.num=3; typeres.num=4;else if(typeres.num=2&c=39)cmdrowi=0;/*处理参数中字符串常量*/if(typeres.num=3&(c9)cmdrowi=0;/*处理参数中整数常量*/return(res);intindex(STRINGs,STRINGt,intstart)/*从串S起始置START开始查找串T，如找到

29、，则返回第一次出现的位置，否则返回-1*/inti,j;if(startlength(s)|(length(t)=0)return(-1);elsei=start;j=0;while(ilength(s)&jlength(t)if(si=tj)i+;j+;elsei=i-j+1;j=0;if(j=length(t)return(i-length(t);elsereturn(-1);voidsubstr(STRINGs,intstart,intlen,STRINGv)/*为新串开辟新的空间，并将从串S中START起始位置起取LEN长度的子串存放起来，把新串的串名和首地址存放于串表中*/inti;

30、charch80;if(start=length(s)printf(Cannotbesubstr!n);elseif(len=1&len=length(s)-start)head.strnamehead.curnum=v;head.strheadhead.curnum=ch;for(i=0;icreatssabcdef2. CMDassignttss3. CMDlengthss4. CMDconcatabcabctt5. CMDindexsstt06. CMDquit【说明】1. 由于C语言数组下标是以0开始，所以在本程序中使所用到的数组都是以下标0开始；2. 本程序在存放字符串时采用类似堆的存储结构，先定义了一个二维数组来读取每一行命令，在对每一行命令进行分析以后，将各参数以字符串的形式返回