串的基本操作

数据结构课程设计报告井冈山大学电子与信息工程学院

数据结构课程设计报告（2012——2013年度第一学期）课程名称： 数据结构课程设计题目一：4.2串基本操作演示系统院系：计算机科学系班级：10软件本2班姓名：xxx学号：100913017指导教师：孙凌宇老师成绩：2012年12月10日成绩评定、指导教师评语、成绩备注指导教师：日期：年月日

设计题目＜一＞： 4.2串基本操作演示系统一、设计要求1．问题描述如果计算机语言没有把串作为一个预先定义好的基本类型对待，又需要用该语言写一个涉及串操作的软件系统时，用户必须自己实现串类型。试着实现串类型，并写一个串的基本操作演示系统。2．需求分析实现若干串的常用基本操作，如串赋值、求串长、串替换、串比较、求子串及串的模式匹配等。为了实现以上功能，可以从3个方面着手设计。1．主界面设计为了实现串基本操作演示系统各功能的管理，本系统设计一个含有多个菜单项的主控单，方便用户使用。本系统主控菜单运行界面如图1所示。□|x艸C:\Docu>entsandSettings\Ad*inistrator\桌面\fuzhihui\4.2串的基本操作演吕吕吕ALsIRcQ111.+■H+■H士宜士宜+宜+宜□|x艸C:\Docu>entsandSettings\Ad*inistrator\桌面\fuzhihui\4.2串的基本操作演吕吕吕ALsIRcQ111.+■H+■H士宜士宜+宜+宜-吕吕吕吕吕吕位度聖養值长番替比岀赋亲退晴看菜单输入您要进行的操作并回车龙全部用大写〉:图1串演示系统主菜单2．存储结构设计使用串的堆分配存储表示，结构描述如下：typedefstruct{char*ch; //串存放的数组intcurLen; //串的长度}HString;3．系统功能设计本系统设置了主界面菜单，并在主界面上完成7个功能的结果显示。7个功能的设计描述如下。赋值(A-Assign)。由函数intstrAssign()实现。当用户选择A功能时，输入待赋值的新串串值，系统完成串赋值并输出新串值。求长度(L-Length)。由函数intStrLength()实现。当用户选择L功能时，系统输出串的长度。求子串(S-SubString)。由函数intsubstring()实现，参数pos和len分别代表子串sub在原串S上的起始位置和子串长度。当用户选择S功能时，系统输出子串的串值。子串定位(I-Index)。子串定位又称串的模式匹配，由函数intIndex()实现。当用户选择I功能时，系统根据用户输入的原串ob1和子串ob2的值输出子串在原串上的位置。替换(R-Replace)。由函数voidReplace()实现。当用户选择R功能时，系统根据用户输入的原串ob1、子串ob2和插入串ob3的值，输出用插入串替换了原串中所有指定子串后的串值。判相等(C-Compare)。由函数intCompare()实现。当用户选择C功能时，系统根据用户输入的s1与s2的串值进行比较。若s1>s2则显示“s1>s2”；若s1=s2则显示“s1=s2”；若s1<s2则显示“s1<s2”。退出(Q-Quit)。当用户选择Q功能时，即退出串基本操作演示系统，有main()函数中的if语句实现。三、模块设计1．模块设计本程序包含两个模块：主程序模块、串操作模块。其调用关系如图2所示。主程序模块 >串操作模块图2模块调用关系示意图2．系统子程序及功能设计intinitString(HString*T) //串类的初始化函数intstrAssign(HString*T,char*chars) //串赋值函数，调用malloc函数分配内存空间intStrLength(HStringS) //求串长函数intsubstring(HString&Sub,HStringS,intpos,intlen)//求串S的子串，pos代表子串sub的起始字符序号(位置)，len代表子串sub的长度intIndex(HString&obl,HString&ob2,intpos)〃从第pos个字符起的子串定位(串的模式匹配)函数，调用(3).voidReplace(HString&obl,HString&ob2,HString&ob3)〃将原串ob1的所有子串ob2都替换为插入串ob3，调用(3)和(5)intCompare(HStringsl,HStrings2) //串比较函数，调用(3)voidmain() //主函数，设定界面，调用操作模块函数4．函数主要调用关系图串基本操作演示系统8个子程序之间的主要调用关系如图3所示。图中字母是各函数四、详细设计1．数据类型定义(1)字符串的定义typedefstruct

char*ch;intcurLen;}HString;(2)全局变量声明#defineOK1#defineOVERFLOW0//串存放的数组//串的长度////串存放的数组//串的长度//操作成功//溢出2．系统主要子程序详细设计(1)主程序模块设计主函数。设定用户操作界面，调用操作模块函数。voidmain(){输出操作菜单；Switch(1){输出操作序号c；switch(c){调用相应函数执行相应操作；输出操作结果；}}}(2)求子串intsubstring(HString&Sub,HStringS,intpos,intlen){/串sub返回串S的第pos个字符起长度为len的子串inti;if(pos<0||pos>S.curLen||len<0||len>S.curLen-pos){ //若位置或长度不合法，退出

printf("输入不合法\n");printf("输入不合法\n");exit(OVERFLOW);}else{if(Sub.ch)free(Sub.ch);if(!len){Sub.ch=NULL;Sub.curLen=0;}else//退出//释放子串sub原有空间〃若长度len为0//就爱那个子串置为空串〃若长度len不为0{Sub.ch=(char*)malloc(len*sizeof(char));for(i=0;i<len;i++){ //从串S的第pos个字符开始依次复制其后长度为len的字符串sub中Sub.ch[i]=S.ch[pos-1+i];Sub.curLen=len; //修改串sub的串长}}returnOK;}}(3)子串定位(串的模式匹配)intIndex(HString&ob1,HString&ob2,intpos){ 〃判断从第pos个字符起，ob2是否为obi的子串〃若是返回ob2在obi中的起始位置，否则返回-1if(pos<0||pos>obi.curLen){〃若输入的数值pos不在obi的串长范围内printf("输入有误\n");exit(ERROR);

for(inti=pos-1;i<=StrLength(ob1)-StrLength(ob2);i++){ //从ob1的第pos个字符起查找子串ob2intj=0; 〃从ob2的第一个字符起开始查找while(j<StrLength(ob2)) //j控制查找位置，逐个字符查找，直到超出子串串长if(ob1.ch[i+j]==ob2.ch[j])//若找到匹配字符j++; //则依次向后查找}return}return-1;//ob2不是ob1的子串，返回-1}(4)串替换}(4)串替换voidReplace(HString&ob1,HString&ob2,HString&ob3){ 〃将原串obi的所有子串ob2都替换为插入串ob3printf("原串：“)；for(inti=0;i<obi.curLen;i++)printf("%c",obi.ch[i]);printf("\n子串：");for(intj=0;j<ob2.curLen;j++)printf("%c",ob2.ch[j]);printf("\n");printf("插入串：")；for(intk=0;k<ob3.curLen;k++)printf("%c",ob3.ch[k]);printf("\n");intlen=StrLength(ob2);while(Index(obi,ob2,0)!=-i)//ob2的长度//当ob2是obi的子串，替换所有的ob2elsebreak; //一旦失配，则跳出查找，此时j还未能达到子串串长}if(j==StrLength(ob2))//若j达到子串串长，即ob2的所有字符都能和obi匹配returni;〃返回ob2在obi的起始位置i

intlen2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2);inti=Index(ob1,ob2,0);intlen2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2);char*p=newchar[StrLength(ob1)-i-len+1];char*q=newchar[len2];for(intj=i+len;j<StrLength(ob1);j++)p[j]=ob1.ch[j];for(intk=0;k<i;k++)q[k]=ob1.ch[k];for(intm=i;m<i+StrLength(ob3);m++)q[m]=ob3.ch[m-i];intb=i+len;for(intn=i+StrLength(ob3);n<len2;n++){ //将不用替换的后部分存入数组qq[n]=p[b];b++;}ob1.curLen=len2;for(intl=0;l<len2;l++)ob1.ch[l]=q[l];}printf("新串：")；for(inth=0;h<ob1.curLen;h++)printf("%c",ob1.ch[h])；}(5)串比较intCompare(HStrings1,HStrings2)//新串的长度//调用子串定位函数//临时数组//存储新串的数组〃将不用替换的后部分存入数组p〃将不用替换的前部分存入数组q//替换子串//数组//新串的长度//调用子串定位函数//临时数组//存储新串的数组〃将不用替换的后部分存入数组p〃将不用替换的前部分存入数组q//替换子串//数组q存储着新串〃将新串赋值给obi做循环替换inti;for(i=0；i<si.curLen&&i<s2.curLen；++i)if(s1.ch[i]!=s2.ch[i])

return(s1.ch[i]-s2.ch[i]);return(s1.curLen-s2.curLen);}五、测试分析系统运行主界面如图1所示。各子系统测试运行结果如下。1.赋值(A-Assign)在主菜单下，输入Ahello!并回车，运行结果如图4所示。grC:\Docu>entsandSettings\Ad*inistrator\桌面\fuzhihui\4.2串的基本搽作return(s1.ch[i]-s2.ch[i]);return(s1.curLen-s2.curLen);}五、测试分析系统运行主界面如图1所示。各子系统测试运行结果如下。1.赋值(A-Assign)在主菜单下，输入Ahello!并回车，运行结果如图4所示。grC:\Docu>entsandSettings\Ad*inistrator\桌面\fuzhihui\4.2串的基本搽作---I串窗吕吕吕位度聖養值长舌替比岀为为为为为为为式式式式式式式1i14-M+■H+■M+■H+■M+■H-吕吕吕吕吕吕-ALsIRcQ数2<2数1慣翥蕃里输入您要进行的操作并回车煌部用大写5hello?于役串为：hello!需着菜单输入您要进行的操作并回车徒部用大写〉.■|口凶图4字符串赋值2.求长度（L-Lengh）在主菜单下，输入Lstudent并回车，运行结果如图5所示。c**C:\Docu>entsandSettings\Ad»inistrator\桌面\fuzhihui\4.2串的基本操件---式式式式式式式111*+宜+包士宜士宜+宜+宜-吕吕吕吕吕吕student夢单严要进行的操作并回锂部用大写口

鲁菜单输入您要进行的操作并回车£全部用大写〉.student图5求字符串长度求子串(S-SubString)在主菜单下，输入Sstudent25并回车，运行结果如图6所示g*C:\DocuMentsandSettings\AdAinistrator\桌面\fuzhihui\4.2串的基本操件---二一一值长番替比岀一一赋亲rHw退二ffffff雳菜请子请为为为为为为为式式式式式式式111.+宜士宜士宜士宜士宜士宜-吕吕吕吕吕吕«-«■44-M-二一一值长番替比岀一一赋亲rHw退二ffffff雳菜请子请为为为为为为为式式式式式式式111.+宜士宜士宜士宜士宜士宜-吕吕吕吕吕吕«-«■44-M-数2®2数1I串窗44-M-44-M-«-M-«-M-«-M-student图6求子串子串定位(ITndex)在主菜单下，分别输入Imicrosoftvisualc++soft1并回车和Imicrosoftvisualc++soft8，运行结果如图7所示。c：\^C:\DocuAentsandSettIngs\Ad>inistrator\桌面\fuzhihui\4.2串的基本操件---|~|~Jk.31值

数串222

4-Hf-Mfnrl

吕吕吕-M-SJk.31值

数串222

4-Hf-Mfnrl

吕吕吕-M-S二O二PXC二iXmX二I二:X>一二芍•二乍-X」\二-4丿二Rn二X咅X._£二J.3X<二-RTX习X叵X卜干二+hXE—二申111演吕吕吕吕吕吕ALsIRC< 羽为为为为为为为十操墓式式式式式式式二的行■■毎活进$2进*要串要MI8一一您位您己一您值长番替比出二入的入「•赋0^|+^<退一一输」 =单原单二二二二i菜二二二r一请子请从请4<氐4<回侍的是的行不行:串-I图7子串定位替换(R-Replace)在主菜单下，输入Rchickenct并回车，运行结果如图8所示

w*C:\DocuMentsandSettings\Ad>inistrator\桌面\fuzhihui\4-2串的基本操作值长番替比岀<1+^*退式式式式式式式ill.+■>+■H+■H+■M+■H+■H-吕吕吕吕吕吕-ALsIRcQ数w*C:\DocuMentsandSettings\Ad>inistrator\桌面\fuzhihui\4-2串的基本操作值长番替比岀<1+^*退式式式式式式式ill.+■>+■H+■H+■M+■H+■H-吕吕吕吕吕吕-ALsIRcQ数2值2数11串窗w-*e**香X入请原子聾请ti箱h牡I:t:串：菜chicken口|其图8字符串替换6.判相等(C-Compare)在主菜单下，分别输入Conin并回车和Conon并回车，运行结果如图9所示。c：\^C:\DocuAentsandSettIngs\Ad>inistrator\桌面\fuzhihui\4.2串的基本操件-度聖叢

值长舌替比岀

赋^退宜凯1匚匚匚匚匚匚彩数；1演吕吕吕吕吕吕^malsircq< 本为为为为为为为基式式式式式式式31值

数串on

oninon话耆耒单输入您要进行的操作并回车龙全部用大写〉呛供斷曲结果:串1》串on

oninon青着杲单输入您要进行的操作并回车£全部用大写〉:C去嚼商结果:串"串2畚署菜单输入您要进行的操作并回车＜全部用大写〉.图9判两串相等7.退出(Q-Quit)在主菜单下，输入Q并回车，退出串基本操作演示系统。六、用户手册本程序执行文件为“串的基本操作演示.exe”进入本系统之后，随即显示系统主菜单界面。用户可在该界面下按提示信息输入命令七、调试报告(1)我不喜欢敲代码，写一个简单的程序时竟然老是出错，难一点的，复杂一点的程序竟然无从下手，程序的架构根本不懂，以至于程序存在许多bug，不过只要按着提示操作，

还是可以完成相应的功能。(2)如果有兴趣还可以对次程序进行深入研究，进行修改，添加等一些串的其他功能八、程序清单#include<stdlib.h>#include<iostream>#include<conio.h>#defineOK1#defineOVERFLOW0#defineERROR0usingnamespacestd; //使用名称空间std//****串的堆分配存储表示typedefstruct//串存放的数组//串存放的数组//串的长度char*ch;intcurLen;}HString;//****1.初始化字符串TintinitString(HString*T){(*T).ch=NULL;(*T).curLen=0;returnOK;}//****2.串赋值函数intstrAssign(HString*T,char*chars){//生成一个值等于串常量chars的串T并用指针返回,*chars为指针(数组名)inti,j;if((*T).ch)free((*T).ch); //释放T原有空间

i=strlen(chars);//数组chars的长度if(!i){(*T).ch=NULL;//若chars为空串，生成空串的堆分配存储表示(*T).curLen=0;}else{//chars不为空串if(!((*T).ch=(char*)malloc(i*sizeof(char))))exit(OVERFLOW); //分配串的堆空间，若失败则退出for(j=0;j<i;j++)(*T).ch[j]=chars[j];(*T).curLen=i;}returnOK;}//****3.求串长函数intStrLength(HStringS){returnS.curLen; //直接返回串长}//****4.求子串函数intsubstring(HString&Sub,HStringS,intpos,intlen){//串Sub返回串S的第pos个字符起长度为len的子串inti;if(pos<0||pos>S.curLen||len<0||len>S.curLen-pos){//若位置或长度不合法，退出//退出//释放子串sub原有空间//退出//释放子串sub原有空间exit(OVERFLOW);}else{if(Sub.ch)free(Sub.ch);if(!len) //若长度len为0{ //将子串置为空串Sub.ch=NULL;Sub.curLen=0;}else//若长度len不为0{Sub.ch=(char*)malloc(len*sizeof(char));for(i=0;i<len;i++){//从串S的第pos个字符开始依次复制其后长度为len的字符串到串Sub中Sub.ch[i]=S.ch[pos-1+i];Sub.curLen=len; //修改串Sub的串长}}returnOK;}}//****5.子串定位函数(串的模式匹配)intIndex(HString&ob1,HString&ob2,intpos){ //判断从第pos个字符起，ob2是否为ob1的子串//若是返回ob2在ob1中的起始位置，否则返回-1if(pos<0||pos>ob1.curLen){〃若输入的数值pos个字符起，ob2是否为obi的子串printf("输入有误\n");exit(ERROR);}for(inti=pos-1;iv=StrLength(ob1)-StrLength(ob2);i++){ 〃从obi的第pos个字符起查找子串ob2intj=0; 〃从ob2的第一个字符起开始查找while(j<StrLength(ob2)) //j控制查找位置，逐个字符查找，直到超出子串串长

if(ob1.ch[i+j]==ob2.ch[j])//若找到匹配字符j++; //则依次向后查找}return}return-1;//ob2不是ob1的子串，返回-1elsebreak; //一旦失配，则跳出查找，此时j还未能达到子串串长}if(j==StrLength(ob2))〃若j达到子串串长，即ob2的所有字符都能和obi匹配returni；//返回ob2在ob1的起始位置i}//****6.串替换函数voidReplace(HString&ob1,HString&ob2,HString&ob3){ //将原串ob1的所有子串ob2都替换为插入串ob3printf(“原串：“)；for(inti=0;i<ob1.curLen;i++)printf("%c",ob1.ch[i])；printf("\n子串：“)；for(intj=0；j<ob2.curLen；j++)printf("%c",ob2.ch[j])；printf("\n")；printf("插入串：")；for(intk=0；k<ob3.curLen；k++)printf("%c",ob3.ch[k])；printf("\n")；intlen=StrLength(ob2)； //ob2的长度while(Index(ob1,ob2,0)!=-1) //当ob2是ob1的子串，替换所有的ob2{intlen2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2)；//新串的长度inti=Index(ob1,ob2,0)； //调用子串定位函数char*p=newchar[StrLength(ob1)-i-len+1]； //临时数组char*q=newchar[len2]； //存储新串的数组for(intj=i+len；j<StrLength(ob1)；j++)

p[j]=ob1.ch[j];for(intk=0;k<i;k++)p[j]=ob1.ch[j];for(intk=0;k<i;k++)q[k]=ob1.ch[k];for(intm=i;m<i+StrLength(ob3);m++)q[m]=ob3.ch[m-i];intb=i+len;〃将不用替换的后部分存入数组p//将不用替换的前部分存入数组q//替换子串for(intn=i+StrLength(ob3);nvlen2;n++){ 〃将不用替换的后部分存入数组qq[n]=p[b];b++; //数组q存储着新串}ob1.curLen=len2;for(intl=0;l<len2;l++)ob1.ch[l]=q[l]; //将新串赋值给ob1做循环替换}printf("新串：")；for(inth=0;h<ob1.curLen;h++)printf("%c",ob1.ch[h]);}//****7.串比较函数intCompare(HStrings1,HStrings2){ //若s1<s2则返回值<0;若s1=s2则返回值=0;若s1>s2则返回值>0inti;for(i=0;i<s1.curLen&&i<s2.curLen;++i)if(s1.ch[i]!=s2.ch[i])return(s1.ch[i]-s2.ch[i]);return(s1.curLen-s2.curLen);}//8.主函数voidmain(){printf(f串基本操作演示系统—***************、『）；printf(printf("**f.赋值格式为:A串值**\n");printf("**一.求长度格式为:L串值**\n");printf("**f.求子串格式为:S串值数1数2**\n");printf("**f.子串定位格式为:I串值1串值2数1**\n");printf("**f.串替换格式为:R串值1串值2串值3**\n");printf("**f.串比较格式为:C串值1串值2**\n");printf("**f.退出格式为:Q**\n");while(1){charc;printf(“请看菜单输入您要进行的操作并回车(全部用大写):");cin>>c; //输入大写字母if(c=='Q')break;//退出串基本操作演示系统switch(c) //用switch语句对输入的大写字母进行多向选择{case'A':{charcnew[50];HStringstr;initString(&str); //初始化串strscanf("%s",cnew);strAssign(&str,cnew);//调用串生成函数printf("字符串为:")；for(inti=0;i<str.curLen;i++)printf("%c",str.ch[i]);printf("\n");break;}case'L':

cha