数据结构课程设计+串的基本操作演示

1、 根据提示操作。n);printf(5)求子串。格式例子：Shelloventerprintf(5)求子串。Eventer提示操作.n);printf(6)子串定位。格式例子：Ihellollventer或只输入Iventer然后根据提示操作。n);printf(7)串替换。格式例子：Rhellollhliventer或只输入Rventer然后根据提示操作。n);printf(8)显示。格式例子：只输入Pventer然后根据提示操作。n);printf(9)删除。格式例子：只输入Dventer然后根据提示操作。StatusInsert(intn)/StatusInsert(intn)/为指定内

2、部名的串赋值n);printf(Q)退出。格式例子：只输入Qventer然后根据提示操作。n);inti,j,k=0;chars250;if(sk=)i=0;k+;while(sk!=)s2i+=sk+;elseprintf(格式输入错误！n);returnERROR;if(KK-StrHeadn.ch)KK-StrHeadn.ch=NULL;KK-StrHeadn.length=0;KK-StrHeadn.state=0;if(!(KK-StrHeadn.ch=(char*)malloc(i*sizeof(char)exit(OVERFLOW);KK-StrHeadn.length=i;KK

3、-StrHeadn.state=1;for(j=0;jStrHeadn.chj=s2j;returnOK;voidgetin(intn)处理命令串，n为要存入的串内部名inti,j;while(s1m=)m+;/s1为从键盘接收到的字符串，s1,m为局部变量，在getorder()函数内有效，减少需要传递的参数if(s1m=)i=0;m+;while(s1m!=)si+=s1m+;if(!(KK-StrHeadn.ch=(char*)malloc(i*sizeof(char)exit(OVERFLOW);KK-StrHeadn.length=i;for(j=0;jStrHeadn.chj=sj

4、;/将命令中的串值存入相应的串头表函数的调用关系图(只列出部分)四、调试分析#includeheader.hStrHeadKK;voidmain()charc;inti;四、调试分析#includeheader.hStrHeadKK;voidmain()charc;inti;/定义StrHead类型的全局变量Resultp;StatusInitResult(Resultp);Statusgetorder(Resultp);voidgetin(intn);voidStrprint();voidshow();/命令分析函数的初始化/命令处理函数/命令串处理函数/输出串值/显示输入格式voidStr

5、Compare(HStringS,HStringT);/串比较函数voidConcat(HStringS1,HStringS2);/串联接函数intStrLength(HStringS);/取串长度StatusSubString(HStringS,intpos,intlen);/取子串StatusReplace(HStringM,HStringt,HStringv);/子串替换StatusIndex(HStringS,HStringT);/子串定位StatusInsert(intn)/为指定内部名的串赋值KK=(StrHead)malloc(sizeof(StrHeadList);/申请空间f

6、or(i=0;iStrHeadi.ch=NULL;KK-StrHeadi.length=0;KK-StrHeadi.state=0;printf(*串的基本操作演示系统*n);printf(*A.进入系统*n);printf(*B.输入格式*n);printf(*C.退出系统*n);/申请空间/申请空间/scanf(%c,&c);getchar();switch(c)caseA:InitResult(p);getorder(p);break;caseB:show();break;caseC:break;default:printf(输入错误，请重新输入！n);break;while(c!=C)

7、;chars1100,s50;/定义局部变量intm;/定义局部变量Statusgetorder(Resultp)chars1100,s50;inti,j,n,m;doprintf(请输入指令：n);gets(s1);m=0;switch(s1m)/判断指令类型KK-CurNum+;caseA:while(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;m+;getin(p-s0);/将串值赋入串头表中printf(噺串的内部名和串值为：n);printf(%5d,p-s0);Strprint(KK-StrHeadp-s0);/回显

8、新串breakcaseE:m+;/串比较if(s1m=0)/比较内部已保存的串printf(输入第一个串的内部名：n);scanf(%d,&p-s0);getchar();printf(输入第一个串的内部名：n);scanf(%d,&p-s1);getchar();if(p-s0s0=KK-CurNum|p-s1s1=KK-CurNum)printf(超出当前串的范围n);elseStrCompare(KK-StrHeadp-s0,KK-StrHeadp-s1);elsewhile(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;w

9、hile(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s1=KK-CurNum+;getin(p-s0);m+;getin(p-s1);StrCompare(KK-StrHeadp-s0,KK-StrHeadp-s1);break;caseC:m+;/串联接if(s1m=0)/联接内部已存在的串printf(输入第一个串的内部名：n);scanf(%d,&p-s0);getchar();printf(输入第二个串的内部名：n);scanf(%d,&p-s1);getchar();if(p-s0s0=KK-CurNum|p-s1s1=KK-CurNum)pr

10、intf(超出当前串的范围n);elseConcat(KK-StrHeadp-s0,KK-StrHeadp-s1);elsewhile(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;while(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s1=KK-CurNum+;getin(p-s0);m+;getin(p-s1);Concat(KK-StrHeadp-s0,KK-StrHeadp-s1);break;caseL:m+;/求长度if(s1m=0)/求内部已存在的串长度printf(输入第一个

11、串的内部名：n);scanf(%d,&p-s0);getchar();if(p-s0s0=KK-CurNum)printf(超出当前串的范围n);elsej=StrLength(KK-StrHeadp-s0);printf(串长度为：dn,j);else/求新输入的串长度while(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;getin(p-s0);j=StrLength(KK-StrHeadp-s0);printf(串长度为：%dn,j);break;caseS:m+;if(s1m=0)/求内部已存在的串的子串printf(输

12、入第一个串的内部名：n);scanf(%d,&p-s0);getchar();if(p-s0s0=KK-CurNum)printf(超出当前串的范围n);elseprintf(请输入pos位置：n);scanf(%d,&p-num0);getchar();printf(请输入len长度：n);scanf(%d,&p-num1);getchar();SubString(KK-StrHeadp-s0,p-num0,p-num1);elsewhile(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;getin(p-s0);printf(请

13、输入pos位置：n);scanf(%d,&p-num0);getchar();printf(请输入len长度：n);scanf(%d,&p-num1);getchar();SubString(KK-StrHeadp-s0,p-num0,p-num1);break;caseI:m+;/子串定位if(s1m=0)/求内部已存在的串的子串的位置printf(输入第一个串的内部名：n);scanf(%d,&p-s0);getchar();printf(“输入第二个串的内部名：n);scanf(%d,&p-s1);getchar();if(p-s0s0=KK-CurNum|p-s1s1=KK-CurNu

14、m)printf(超出当前串的范围n);elseIndex(KK-StrHeadp-s0,KK-StrHeadp-s1);elsewhile(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;/求新输入的串的子串的位置p-s0=KK-CurNum+;while(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s1=KK-CurNum+;getin(p-s0);m+;getin(p-s1);Index(KK-StrHeadp-s0,KK-StrHeadp-s1);break;caseR:m+;/替换串if(s1m=0)/求内部已存在的

15、串的替换printf(输入第一个串的内部名：n);scanf(%d,&p-s0);getchar();printf(输入第二个串的内部名：n);scanf(%d,&p-s1);getchar();printf(输入第三个串的内部名：n);scanf(%d,&p-s2);getchar();if(p-s0s0=KK-CurNum|p-s1s1=KK-CurNum|p-s2s2=KK-CurNum)printf(超出当前串的范围n);elseReplace(KK-StrHeadp-s0,KK-StrHeadp-s1,KK-StrHeadp-s2);elsewhile(KK-StrHeadKK-Cu

16、rNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;while(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s1=KK-CurNum+;while(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s2=KK-CurNum+;getin(p-s0);m+;getin(p-s1);m+;getin(p-s2);Replace(KK-StrHeadp-s0,KK-StrHeadp-s1,KK-StrHeadp-s2);break;caseP:printf(“所有串的内部名和串值为：n);显示所有保留的

17、串for(i=0;iStrHeadi.ch!=NULL)printf(%5d,i);Strprint(KK-StrHeadi);break;caseD:printf(“请输入要删除的串的内部名：n);删除串scanf(%d,&p-num0);getchar();if(p-num0num0=KK-CurNum)printf(无此串！n);elseprintf(删除的串名和串值为：n);printf(%5d,p-num0);printf(%c,);Strprint(KK-StrHeadp-num0);KK-StrHeadp-num0.ch=NULL;KK-StrHeadp-num0.length=

18、0;break;caseW:printf(请输入要赋值的串的内部名和串值(以空格隔开)：n);scanf(%d%s,&p-num0,s);getchar();if(p-num0num0=100)printf(无此串！n);elseInsert(p-num0);printf(新串的内部名和串值为：n);printf(%5d,p-num0);Strprint(KK-StrHeadp-num0);break;caseQ:break;default:printf(输入错误！可返回上一界面查看输入格式n);while(s10!=Q);returnOK;(2)测试数据：赋值：AhelloventerAni

19、cetomeetyou!，venterAtooventer显示：Pventer/回显刚才输入的三条语句判相等：Ehellohiventer或只输入Eventer然后根据提示操作联接：Chellohiventer或只输入Cventer然后根据提示操作求长度：Lhelloventer或只输入Lventer然后根据提示操作求子串：Shelloventer然后根据提示操作或只输入Eventer提示操作.子串定位：Ihellollventer或只输入Iventer然后根据提示操作删除：输入Dventer然后根据提示操作Eg.Eventer，显示“EQUAL”Edadventer，显示“UNEQUAL”C

20、“，venter，显示，Chello,nicetomeetyouventer，显示hello,nicetomeetyouIaventer,应报告：参数非法Ihellollventer，显示:3Shelloventer，然后根据提示输入pos和len的值Raaaaabventer，显示：baRaaabcaaabventer，显示:aabaabaabbcRaaaaaaaaaaaaabventer，显示：abab五、用户手册1本程序的运行环境为DOS操作系统，执行文件为project.exe。2进入程序后即显示用户欢迎界面，用户可根据文字提示进行操作，本程序有两种命令输入格式（如Ehellohive

21、nter或只输入Eventer然后根据提示操作），具体可查看程序的输入格式。3本程序区分大小写，输入指令时请注意。4.本程序支持内部名操作，如在联接串的时候，可以先输入Cventer，然后按提示输入内部名，即可完成操作。或者可以直接输入Chellonicetomeetyouventer，结果串为hellonicetomeetyou；其它的函数也可以进行类似操作。5本程序是命令解释程序，循环往复地处理用户键入的每一条指令，直至终止程序的命令为止（本程序退出指令为Qventer）。六、测试结果下面是运行程序的操作流程（从运行窗口复制的）：project.exe1比较串相等时，因为要比较的两个串都已

22、存入串头表中。因此，开始可以先比较两串的长度，若不等则马上显示“UNEQUAL”并返回。长度相等则逐个比较串值，遇到不等则马上显示“UNEQUAL“并返回，比较完相等则显示“UNEQUAL”。2在串联接时，方法挺简单。只需申请两串长度之和的空间，然后按顺序赋值到新串即可。注释：上图为执行各项基本操作的效果图，可见验证结果的正确性。1上图是直接输入串值的命令，这样可以方便的一次性输入完指令。满足了程序的基本要求。2在子串定位函数中，要注意检查参数的合法性，当第二个串是空串时要正确处理这种情况。3在子串替换时，要注意设置循环结束的条件，如果设置不对，曾出现过RDaaaDaaDbD，结果却为bD的错

23、误结果，改正后结果正确。晴输入指令:幘输入要赋值的串的内部名和串值以空格隔开1:B,liello,断串的内部名和串值为：3JhelloJ猜输入指令：P所有串的内部名和串值为：3JhelloJ惰输入指令：慣输入要赋值的串的内部名和串值（以空格隔开）:pfchangef新串的内部名和串值为：31change1情输入指令：P祈有串的内部名和串值为：1change1情输入指令：pt*aaabc*1aJ*aabJ卡吉果串的内部名和串值为：aabaabaabbc幘输入指令：P所有串的内部名和串值为：01aaabc1JaJJaabf1change1*aabaabaabbc*慎输入指令：扁入两个串的内部名以逗

24、号隔开）：UNEQUAL”律输入指令：常入两个串的内部名以逗号隔开）：注释：上图为各项操ey嗣墮中巴密二一廊呂忌駕四龜莖1_在这里可以看出，本程序增加了Insert（）函r,_口r,_口j以在指定本程序还支持内部名操作，如上图所示，可以根据要求输入内部名，即可完成相应的串操作，这样可以对已存入的串进行联接、比较等操作，这样就大大增强了程序的实用性和可操作性。七、附录源程序文件名菜单：header.h/类型和变量说明main.c/主程序文件八、时间复杂度分析1由于本程序采用数组的顺序存储结构，虽然要开始定义一个较大的存储空间(如定义：HStringStrHead100),但由于每个Hstring

25、类型的结构体才两个元素，花费的整体空间并不比链式存储结构(要开辟指针域，花费一定空间)大多少，更重要的是采用数组的顺序存储结构执行串的基本操作非常方便，不必如链式那样从头指针出发查找，时间复杂度为O(n)，可以通过内部名直接找到某一个串，时间复杂度为O(1)。因此在执行诸如串的基本操作上很方便。假设串值的平均长度为n,则StrCompare的时间复杂度为o(n)；Concat的时间复杂度为o(n+n)；Index的时间复杂度为o(n*n)；Replace的时间复杂度为o(n*n*n)；SubString的时间复杂度为o(n)；在错误处理方面，本程序在几个方面做了考虑。比如在赋值指令时，如果输入

26、的命令为Aadas,这样虽然可以知道是赋值指令,但串值不能正确赋入相应的串中，这时系统应该报错；再者，在支持内部名操作的指令中，如果输入的内部名超出范围，则应该报错，其它类似的地方也应采取相应的处理方式。由于本程序采用字符数组s1来接收输入的命令，为了处理数据的方便，采用了定义局部变量的方法，这样可以减少需要传递的参数个数。比如在一条替换指令中有三个串，在赋值的时候采用同一个函数getin(intn)函数就可以完成三个串的赋值，而且只需传递目的串的内部名一个参数就足够啦。因为s1是在getorder函数的，把s1m定义为局部变量后就可以直接在getin函数调用，减少传递的参数，还可以使m增加到相应的位置，为下个getin函数取用方便且正