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

1、3.4串的基本操作演示一、 需求分析 1用堆分配存储表示实现Hstring 串类型的最小操作子集。 2实现串抽象类型的其余基本操作（如联接、删除等），且不能使用c语言本身提供的串函数，必须自己构造新的函数实现串的基本操作。 3本演示系统是一个命令解释程序，循环往复的处理用户输入的每一条命令，直至终止程序的命令为止。 4参数的合法性必须严格检查，要严格按照命令的输入格式进行输入，否则程序可能无法正确执行指令。二、概要设计 实现串的抽象数据类型和实现其基本操作，程序中将涉及下列抽象数据类型： 1定义串的基本主结构 ADT String 数据对象：D=ai| aicharcaterset,i=1,2

2、,n,n>=0 数据关系：R1=<ai-1,ai>|ai-1,aiD, i=1,2,n 基本操作： StrCompare(HString S,HString T) 初始条件：S和T是已存在的Hstring类型。 操作结果：比较其值，显示结果“UNEQUAL”或“EQUAL”。 StrLength(HString S) 初始条件：S是已存在的Hstring类型。 操作结果：返回该串的长度。 Concat(HString S1,HString S2) 初始条件：S1和S2是已存在的Hstring类型。 操作结果：由S1和S2联接成新串。 Index(HString S,HStri

3、ng t) 初始条件：S和T是已存在的Hstring类型。 操作结果：显示第二个串在第一个串中首次出现的起始位置。 Replace(HString M, HString t, HString v) 初始条件：M、t和v是已存在的Hstring类型。 操作结果：将第一个串中所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。 SubString(HString S,int pos,int len) 初始条件：S是已存在的Hstring类型。 操作结果：如果参数合法，则显示子串的内部名和串值 。 Strprint(HString S) 初始条件：S是已存在的Hstring类型。

4、操作结果：显示串S的内部名和串值 。 getin(int n) 初始条件：处理命令串S1, 操作结果：把串值存入串头表中 Insert(int n) 初始条件：要给指定的串赋值,n为指定的串的内部名 操作结果：为指定内部名的串赋值 show() 初始条件：要求查看输入格式 操作结果：输出各种命令的输入格式ADT String二存储结构及相应的类型定义公用头文件header.h#include <conio.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <

5、ctype.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAXLEN 100#define MAXSIZE 50typedef int Status;（1）顺序存储结构typedef struct ResultType int CmdNo; /命令号或命令符int s3; /命令的串参数的内部名（最多3） int num2; /命令的数值参数（最多2个）ResultType,*Result ; typedef struct char * ch; /若为非空串，则按

6、串长分配存储区，否则ch为NULLint length; /串长度int state; /状态量HString,*String;typedef struct HString StrHead100; /串头数组 int CurNum; /系统中现有的串的数目StrHeadList,*StrHead; 三、详细设计 void StrCompare(HString S,HString T) /比较两串的串值，显示结果“UNEQUAL”或“EQUAL” int i; if(S.length!=T.length) /先判长度是否相等，若不相等则显示“UNEQUAL” printf("“UNEQ

7、UAL”n");return; else for(i=0;i<S.length &&i<T.length;i+) /比较两串的串值，遇到不等就显示“UNEQUAL” if(S.chi!=T.chi) printf("“UNEQUAL”n");return; printf("“EQUAL”n"); /比较完后，相等则显示“EQUAL”void Concat(HString S1,HString S2) /由S1和S2联接成新串int i,j; j=KK->CurNum+; /为串头指针分配位置，申请(S1.len

8、gth+S2.length)大小空间 if(KK->StrHeadj.ch=(char*)malloc(S1.length+S2.length) *sizeof(char)=NULL) exit(OVERFLOW); for(i=0;i<S1.length;i+) /先将串S1内容复制到新串 KK->StrHeadj.chi=S1.chi; for(i=0;i<S2.length;i+)/将串S2容复制到新串 KK->StrHeadj.chS1.length+i=S2.chi; KK->StrHeadj.length=S1.length+S2.length;

9、 /(S1.length+S2.length)赋值给新串 printf("结果串的内部名和串值为：n");/显示结果串名和串值 printf("%5d",j); printf("%c",' '); printf("'"); for(i=0;i<KK->StrHeadj.length;i+) printf("%c",KK->StrHeadj.chi); printf("'"); printf("n"); in

10、t StrLength(HString S)/返回S串的长度 return S.length;void Strprint(HString S) int i; printf("%c",' '); printf("'"); for(i=0;i<S.length;i+) /输出串值printf("%c",S.chi); printf("'"); printf("n"); Status SubString(HString S,int pos,int len)/求串S

11、的子串int i,n; n=KK->CurNum+;/为串头指针分配位置 if(pos<0|pos>S.length|len<0|len>S.length-pos+1)/判断参数是否合法 printf("ERROR: 参数不合法n"); return ERROR; if(!len) /当子串长度为空 KK->StrHeadn.ch=NULL; KK->StrHeadn.length=0; else /申请len长度的空间存储新串 KK->StrHeadn.ch=(char *)malloc(len *sizeof(char);

12、 for(i=0;i<=len-1;i+) KK->StrHeadn.chi=S.chpos-1+i; KK->StrHeadn.length=len; printf("子串的内部名和串值为：n");/显示新串的内部名和串值 printf("%5d",n); Strprint(KK->StrHeadn); printf("n");return OK;Status Index(HString S,HString t) /显示第二个串在第一个串中首次出现的起始位置 int m,i,j; if(t.length=0)

13、/若t串的长度为0，则参数非法 printf("参数非法n"); else for(i=0;i<=S.length-t.length+1;i+)/查找第二个串在第一个串中首次出现的起始位置for(j=i,m=0;m<t.length&&S.chj=t.chm;m+,j+); if(m=t.length) printf("第二个串在第一个串中首次出现的起始位置：n"); printf("%dn",i+1); return OK; if(i>=0) printf("该位置不存在n");

14、/若找不到 return ERROR;Status Replace(HString M, HString t, HString v)/将第一个串中所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。int i,j,m,n,k,y=0; n=KK->CurNum+;/为串头指针分配位置 if(M.length<0) return ERROR;/判断 if(KK->StrHeadn.ch=(char*)malloc(M.length)*sizeof(char)=NULL) exit(OVERFLOW);/申请空间 for(i=0;i<M.length;i+

15、)/先将串M的值赋给新串 KK->StrHeadn.chi=M.chi; KK->StrHeadn.length=M.length; for(i=0;i<=KK->StrHeadn.length-t.length;i+)/新串与串t比较 for(j=i,m=0;m<t.length&&KK->StrHeadn.chj=t.chm;m+,j+); if(m=t.length)/在新串中找到和串t相等的子串 y=1; if(t.length>v.length)/串t的长度大于串v，修改新串内容 for(k=i,m=0;m<v.leng

16、th;k+,m+) KK->StrHeadn.chk=v.chm; for(k=i+v.length;k<KK->StrHeadn.length-t.length+v.length;k+) KK->StrHeadn.chk=KK->StrHeadn.chk-v.length+t.length; else if(t.length=v.length) /串t的长度等于串v，修改新串内容 for(j=i,m=0;m<v.length;m+,j+) KK->StrHeadn.chj=v.chm; else /串t的长度小于串v，修改新串内容if(KK->

17、StrHeadn.ch=(char*)realloc(KK->StrHeadn.ch,(KK->StrHeadn.length-t.length+v.length) *sizeof(char)=NULL) exit(OVERFLOW); for(k=KK->StrHeadn.length-t.length+v.length-1,m=KK->StrHeadn.length-1;k>=v.length+i;k-,m-) KK->StrHeadn.chk=KK->StrHeadn.chm; for(k=v.length+i-1,m=v.length-1;m&

18、gt;=0;k-,m-) KK->StrHeadn.chk=v.chm; KK->StrHeadn.length+=v.length-t.length; i=i+v.length-1; printf("结果串的内部名和串值为：n");/显示新串内容 printf("%5d",n); Strprint(KK->StrHeadn); printf("n"); if(y=1) return TRUE; else return FALSE; void show()/命令输入格式printf("输入格式如下：n&qu

19、ot;); printf("(1)赋值。 格式例子：A 'hello'<enter>n"); printf("(2)判相等。 格式例子：E 'hello' 'hi' <enter>或只输入E<enter>然后根据提示操作。n"); printf("(3)联接。 格式例子：C 'hello' 'hi' <enter>或只输入C<enter>然后根据提示操作。n"); printf("(4)

20、求长度。 格式例子：L 'hello' <enter>或只输入L<enter>然后根据提示操作。n"); printf("(5)求子串。 格式例子：S 'hello'<enter>然后根据提示操作或只输入E<enter>提示操作.n"); printf("(6)子串定位。格式例子：I 'hello' 'll' <enter>或只输入I<enter>然后根据提示操作。n"); printf("(7)串替

21、换。 格式例子：R 'hello' 'll' 'hli'<enter>或只输入R<enter>然后根据提示操作。n"); printf("(8)显示。格式例子：只输入P<enter>然后根据提示操作。 n"); printf("(9)删除。格式例子：只输入D<enter>然后根据提示操作。 n"); printf("(Q)退出。 格式例子：只输入Q<enter>然后根据提示操作。 n");Status Insert(i

22、nt n) /为指定内部名的串赋值int i,j,k=0; char s250; if(sk=''') i=0; k+; while(sk!=''') s2i+=sk+; else printf("格式输入错误！n");return ERROR; if(KK->StrHeadn.ch) KK->StrHeadn.ch=NULL; KK->StrHeadn.length=0; KK->StrHeadn.state=0; if(!(KK->StrHeadn.ch=(char *)malloc(i*si

23、zeof (char) exit(OVERFLOW); KK->StrHeadn.length=i; KK->StrHeadn.state=1; for(j=0;j<=i;j+) KK->StrHeadn.chj=s2j; return OK; void getin(int n) /处理命令串，n为要存入的串内部名int i,j; while(s1m=' ') m+; /s1为从键盘接收到的字符串，s1,m为局部变量，在getorder（）函数内有效，减少需要传递的参数 if(s1m=''') i=0; m+; while(s1m

24、!=''') si+=s1m+; if(!(KK->StrHeadn.ch=(char *)malloc(i*sizeof (char) exit(OVERFLOW); KK->StrHeadn.length=i; for(j=0;j<=i;j+) KK->StrHeadn.chj=sj; /将命令中的串值存入相应的串头表函数的调用关系图（只列出部分） endmainInitilizationgetorder() Getin()StrCompare()SubString()Concat()Index()Replace () Exit()四、调试分

25、析#include"header.h" StrHead KK; /定义StrHead类型的全局变量void main() char c; int i; Result p; Status InitResult(Result p); /命令分析函数的初始化 Status getorder(Result p); /命令处理函数void getin(int n); /命令串处理函数 void Strprint(); /输出串值 void show(); /显示输入格式 void StrCompare(HString S,HString T); /串比较函数 void Concat(

26、HString S1,HString S2); /串联接函数 int StrLength(HString S); /取串长度 Status SubString(HString S,int pos,int len); /取子串 Status Replace(HString M, HString t, HString v); /子串替换 Status Index(HString S,HString T); /子串定位Status Insert(int n) /为指定内部名的串赋值 KK=(StrHead )malloc(sizeof(StrHeadList); /申请空间for(i=0;i<

27、=100;i+) KK->StrHeadi.ch=NULL; KK->StrHeadi.length=0; KK->StrHeadi.state=0; KK->CurNum=0; p=(Result )malloc(sizeof(ResultType); /申请空间 do printf("*n"); printf("* 串的基本操作演示系统 *n"); printf("* A.进入系统 *n"); printf("* B.输入格式 *n"); printf("* C.退出系统 *n

28、"); printf("*n");scanf("%c",&c);getchar();switch(c)case'A':InitResult(p);getorder(p);break; case'B': show();break; case'C': break; default: printf("输入错误，请重新输入！n"); break; while(c!='C'); char s1100,s50; /定义局部变量int m; /定义局部变量Status

29、 getorder(Result p) char s1100,s50; int i,j,n,m; do printf("请输入指令：n"); gets(s1); m=0; switch(s1m) /判断指令类型 case'A':while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s0=KK->CurNum+; m+; getin(p->s0); /将串值赋入串头表中 printf("新串的内部名和串值为：n"); printf("%5d&q

30、uot;,p->s0); Strprint(KK->StrHeadp->s0); /回显新串 break case 'E': m+; /串比较 if(s1m='0') /比较内部已保存的串 printf("输入第一个串的内部名：n"); scanf("%d",&p->s0);getchar(); printf("输入第一个串的内部名：n"); scanf("%d",&p->s1);getchar(); if(p->s0<0|p

31、->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum)printf("超出当前串的范围n");elseStrCompare(KK->StrHeadp->s0,KK->StrHeadp->s1); else while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s0=KK->CurNum+;while(KK->StrHeadKK->CurNum.state=1) KK->Cu

32、rNum+; p->s1=KK->CurNum+; getin( p->s0); m+; getin(p->s1); StrCompare(KK->StrHeadp->s0,KK->StrHeadp->s1); break; case 'C': m+; /串联接 if(s1m='0') /联接内部已存在的串 printf("输入第一个串的内部名：n"); scanf("%d",&p->s0);getchar(); printf("输入第二个串的内部名：

33、n"); scanf("%d",&p->s1);getchar();if(p->s0<0|p->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum)printf("超出当前串的范围n");elseConcat(KK->StrHeadp->s0,KK->StrHeadp->s1); else while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->

34、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; case 'L': m+; /求长度 if(s1m='0') /求内部已存在的串长度printf("输入第一个串的内部名：n"); scan

35、f("%d",&p->s0); getchar(); if(p->s0<0|p->s0>=KK->CurNum)printf("超出当前串的范围n"); else j=StrLength(KK->StrHeadp->s0); printf("串长度为：%dn",j); else /求新输入的串长度 while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s0=KK->CurNum+; getin( p

36、->s0); j=StrLength(KK->StrHeadp->s0); printf("串长度为：%dn",j); break; case 'S': m+; if(s1m='0') /求内部已存在的串的子串printf("输入第一个串的内部名：n"); scanf("%d",&p->s0); getchar(); if(p->s0<0|p->s0>=KK->CurNum) printf("超出当前串的范围n"); el

37、se printf("请输入pos位置：n"); scanf("%d",&p->num0); getchar(); printf("请输入len长度：n"); scanf("%d",&p->num1); getchar(); SubString(KK->StrHeadp->s0,p->num0,p->num1); else while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s0=KK-

38、>CurNum+; getin( p->s0); printf("请输入pos位置：n"); scanf("%d",&p->num0); getchar(); printf("请输入len长度：n"); scanf("%d",&p->num1); getchar(); SubString(KK->StrHeadp->s0,p->num0,p->num1); break; case 'I': m+; /子串定位 if(s1m='0

39、') /求内部已存在的串的子串的位置 printf("输入第一个串的内部名：n"); scanf("%d",&p->s0); getchar(); printf("输入第二个串的内部名：n"); scanf("%d",&p->s1); getchar(); if(p->s0<0|p->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum)printf("超出当前串的范围n"

40、); else Index(KK->StrHeadp->s0,KK->StrHeadp->s1); else while(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->

41、StrHeadp->s0,KK->StrHeadp->s1); break; case 'R': m+; / /替换串 if(s1m='0') /求内部已存在的串的替换 printf("输入第一个串的内部名：n"); scanf("%d",&p->s0); getchar(); printf("输入第二个串的内部名：n"); scanf("%d",&p->s1); getchar(); printf("输入第三个串的内部名：n&

42、quot;); scanf("%d",&p->s2); getchar(); if(p->s0<0|p->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum|p->s2<0|p->s2>=KK->CurNum)printf("超出当前串的范围n"); else Replace(KK->StrHeadp->s0,KK->StrHeadp->s1, KK->StrHeadp->s2); el

43、se while(KK->StrHeadKK->CurNum.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

44、(p->s2); Replace(KK->StrHeadp->s0,KK->StrHeadp->s1, KK->StrHeadp->s2); break; case 'P': printf("所有串的内部名和串值为：n");/显示所有保留的串 for(i=0;i<100;i+) if(KK->StrHeadi.ch!=NULL) printf("%5d",i); Strprint(KK->StrHeadi) ; break; case 'D': printf(&q

45、uot;请输入要删除的串的内部名：n"); /删除串 scanf("%d",&p->num0); getchar(); if(p->num0<0|p->num0>=KK->CurNum) printf("无此串！n"); else printf("删除的串名和串值为：n"); printf("%5d",p->num0); printf("%c",' '); Strprint(KK->StrHeadp->num

46、0); KK->StrHeadp->num0.ch=NULL; KK->StrHeadp->num0.length=0; break; case 'W': printf("请输入要赋值的串的内部名和串值（以空格隔开）：n"); scanf("%d%s",&p->num0,s); getchar(); if(p->num0<0|p->num0>=100) printf("无此串！n"); else Insert(p->num0); printf(&quo

47、t;新串的内部名和串值为：n"); printf("%5d",p->num0); Strprint(KK->StrHeadp->num0); break; case 'Q': break; default: printf("输入错误！可返回上一界面查看输入格式n"); while(s10!='Q'); return OK;（2） 测试数据： 赋值：A hello<enter> A nice to meet you! <enter> A too <enter>

48、显示：P<enter> /回显刚才输入的三条语句 判相等：E 'hello' 'hi' <enter>或只输入E<enter>然后根据提示操作 联接： C 'hello' 'hi' <enter>或只输入C<enter>然后根据提示操作 求长度：L 'hello' <enter>或只输入L<enter>然后根据提示操作 求子串：S 'hello'<enter>然后根据提示操作或只输入E<enter&

49、gt;提示操作. 子串定位：I 'hello' 'll' <enter>或只输入I<enter>然后根据提示操作 删除：输入D<enter>然后根据提示操作 Eg. E <enter>,显示“EQUAL” E dad <enter>,显示“UNEQUAL” C <enter>,显示 C hello, nice to meet you <enter>,显示hello,nice to meet you I a <enter>,应报告：参数非法 I hello ll <

50、;enter>,显示:3 S hello <enter>,然后根据提示输入pos和len的值 R aaa aa b <enter>,显示: ba R aaabc a aab <enter>,显示: aabaabaabbcR aaaaaaaa aaaa ab <enter>,显示: abab五、用户手册1本程序的运行环境为DOS操作系统，执行文件为project.exe。2进入程序后即显示用户欢迎界面，用户可根据文字提示进行操作，本程序有两种命令输入格式（如E 'hello' 'hi' <enter>或只输入E<enter>然后根据提示操作）