串基本操作的演示.doc

.信息科学与技术学院数据结构课程设计报告题目名称：串的基本操作演示专业班级：学生姓名：学生学号：指导教师：完成日期：目录一、需求分析1二、概要设计2三、详细设计21、自定义数据类型22、基本操作函数33、主函数8四、调试分析10五、用户手册10六、测试结果11七、实验中出现的问题、解决方法和心得体会11八、附录11;.一、需求分析【问题描述】如果语言没有把串作为一个预先定义好的基本类型对待,又需要用该语言写一个涉及串操作的软件系统时,用户必须自己实现串类型。试实现串类型,并写一个串的基本操作的演示系统。【基本要求】在教科书4.2.2节用堆分配存储表示实现HString串类型的最小操作子集的基础上,实现串抽象数据类型的其余基本操作(不使用C语言本身提供的串函数)。参数合法性检查必须严格。利用基本操作函数构造以下系统:它是一个命令解释程序,循环往复地处理用户键入的每一条命令,直至终止程序的命令为止。命令定义如下:(1)赋值。格式:A用所表示的串的值建立新串,并显示新串的内部名和串值。例:AHi!(2)判相等。格式:E若两串相等,则显示EQUAL,否则显示UNEQUAL。(3)联接。格式:C将两串拼接产生结果串,它的内部名和串值都显示出来。(4)求长度。格式:L串标识显示串的长度。(5)求子串。格式:S+如果参数合法,则显示子串的内部名和串值。不带正负号。(6)子串定位。格式:I显示第二个串在第一个串中首次出现时的起始位置。(7)串替换。格式:R将第一个串中所有出现的第二个串用第三个串替换,显示结果串的内部名和串值,原串不变。(8)显示。格式:P显示所有在系统中被保持的串的内部名和串值的对照表。(9)删除。格式:D删除该内部名对应的串,即赋值的逆操作。(10)退出。格式:Q结束程序的运行。在上述命令中,如果一个自变量是串,则应首先建立它。基本操作函数的结果(即函数值)如果是一个串,则应在尚未分配的区域内新辟空间存放。【测试数据】自定。但要包括以下几组:(1)E,应显示EQUAL。(2)Eabcabcd,应显示UNEQUAL。(3)C,应显示。(4)Ia,应报告:参数非法。(5)Raaaaab,应显示ba(6)Raaabcaaab,应显示aabaabaabbc。(7)RFaaaaaaaaaaaaab,应显示Fabab。二、概要设计 实现串的抽象数据类型和实现其基本操作，程序中将涉及下列抽象数据类型： 1定义串的基本主结构 ADT String 数据对象：D=ai| aicharcaterset,i=1,2,n,n=0 数据关系：R1=|ai-1,aiD, i=1,2,n 基本操作： compare(hstring s,hstring t) 初始条件：S和T是已存在的Hstring类型。 操作结果：比较其值，显示结果“UNEQUAL”或“EQUAL”。 length(hstring s) 初始条件：S是已存在的Hstring类型。 操作结果：返回该串的长度。 concat(hstring &t,hstring s1,hstring s2) 初始条件：S1和S2是已存在的Hstring类型。 操作结果：由S1和S2联接成新串。 index(hstring s,hstring t,int pos) 初始条件：S和T是已存在的Hstring类型。 操作结果：显示第二个串在第一个串中首次出现的起始位置。 replace(hstring &s,hstring t,hstring v) 初始条件：M、t和v是已存在的Hstring类型。 操作结果：将第一个串中所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。 sub (hstring &sub,hstring s,int pos,int len) 初始条件：S是已存在的Hstring类型。 操作结果：如果参数合法，则显示子串的内部名和串值 。 display(HString S) 初始条件：S是已存在的Hstring类型。 操作结果：显示串S的内部名和串值 。 copy(hstring &t,hstring s) 初始条件：S是已存在的Hstring类型。 操作结果：由串s复制得串tgetin(int n) 初始条件：处理命令串S1, 操作结果：把串值存入串头表中 ADT String三、详细设计1、自定义数据类型typedef struct hstring char *ch; int length; hstring; hstring headlist100; /串头数组2、基本操作函数1、赋值void strassign() char c; int i; char a20; while(c=getchar()!=n) if(c=) i=0; while(c=getchar()!=) ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;iheadlistcurnum.length;i+) headlistcurnum.chi=ai; curnum+; printf(内部名：%d 串值:,curnum-1); for(i=0;i=48&c=48&c=57)/还是数字 bi+=c; bi=0; sj=atoi(b); j+; if(c=) i=0; while(c=getchar()!=) ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i=curnum|s1=curnum) printf(参数不合法n); else j=strcompare(headlists0,headlists1); if(j=0) printf(EQUALn); else printf(UNEQUALn); 3、求长void length() char c; int i,m,n,j=0; while(c=getchar()!=n) if(c=48&c=48&c=57)/还是数字 bi+=c; bi=0; sj=atoi(b); j+; if(c=) i=0; while(c=getchar()!=) ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i=curnum) printf(参数不合法n); return; printf(%dn,headlists0.length); 4、连接void concat() char c; int i,m,n,j=0; while(c=getchar()!=n) if(c=48&c=48&c=57)/还是数字 bi+=c; bi=0; sj=atoi(b); j+; if(c=) i=0; while(c=getchar()!=) ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i=curnum|s1=curnum) printf(参数不合法n); else printf(连接后串内部名:%d 串值:,curnum); strconcat(headlistcurnum+,headlists0,headlists1); 5、子串定位void index() char c; int i,m,n,j=0; while(c=getchar()!=n) if(c=48&c=48&c=57)/还是数字 bi+=c; bi=0; sj=atoi(b); j+; if(c=) i=0; while(c=getchar()!=) ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i=curnum|s1=curnum) printf(参数不合法n); else printf(%dn,strindex(headlists0,headlists1,1); 6、显示void display() int i,j; char c; while(c=getchar()!=n); for(i=0;icurnum;i+) printf(n内部名%d ,i); for(j=0;j=48&c=48&c=curnum) printf(参数不合法n); else clearstring(headlists0); 8 求子串void sub() char c; int i,m,n,j=0; while(c=getchar()!=n) if(c=48&c=48&c=57)/还是数字 bi+=c; bi=0; sj=atoi(b); j+; if(c=) i=0; while(c=getchar()!=) ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i=curnum) printf(参数不合法n); return; j=substring(headlistcurnum,headlists0,s1,s2); if(j=1) printf(子串内部名:%d ,curnum); for(i=0;is2;i+) printf(%c,headlistcurnum.chi); curnum+; 9、替换void replace() char c; int i; char a20; while(c=getchar()!=n) if(c=) i=0; while(c=getchar()!=) ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;iheadlistcurnum.length;i+) headlistcurnum.chi=ai; curnum+; strcopy(headlistcurnum,headlistcurnum-3); strreplace(headlistcurnum-1,headlistcurnum-3,headlistcurnum-2); for(i=0;iheadlistcurnum-1.length;i+) printf(%C,headlistcurnum-1.chi); printf(n); 3、主函数void main() char c; printf(*n); printf( A:赋值 E：判相等 C：联接 L：求长度 n S：求子串 I：子串定位 R：串替换 P:显示n D：删除 Q：退出n); printf(*n); printf(请输入命令：n); while(c=getchar()!=Q) switch(c) case E: compare();printf(串数：%dn,curnum); break; case A: strassign(); printf(串数：%dn,curnum);break; case L: length(); printf(串数：%dn,curnum);break; case C: concat(); printf(n串数：%dn,curnum);break; case I: index(); printf(n串数：%dn,curnum);break; case P: display();printf(n); break; case D: Delete(); break; case S: sub(); break; case R: replace(); break; 四、调试分析五、用户手册1. 本程序的运行环境为DOS操作系统，执行文件为：数据结构课程设计.exe.2. 进入程序后即会显示可以使用的命令和命令用途和对应命令的语法格式的列表，用户可以根据命令列表输入正确的命令。如果输入正确就会显示相应的结果，接着可以输入下一条命令。如果输入错误，会显示相应的错误的原因并提示重新输入命令。3. 命令是以回车为结束的标志。4. 本程序只能输入字符串，且字符串支持空格符，不过字符串必须用双单引号括住。所以Delete命令需要输入的数字也必须用双单引号括住。但命令Substring并不需要如此，在提示“请输入子串的开始位置:”和“请输入子串的结束中位置:”直接输入数字即可。5. 命令Subsring在输出正确结果后会接着输出“此命令不存在！请重新输入！”此提示，此问题一直都没有解决，也是该程序的缺陷，但是结果是正确的。6. 若要退出程序，请键入命令：Q。六、测试结果 (1)E 命令输出的结果为:EQUAL (2)E abc abcd 命令输出的结果为:UNEQUAL (3) I a 语法格式错误！请重新输入！ (4)R aaa aab 命令输出的结果为：ba (5)R aaabca aab 命令输出的结果为:aabaabaabbc (6)R aaaaaaaa aaaa ab 命令输出的结果为:abab (7)A string 命令输出的结果为: 新赋值的字符串的内部名为:4，串值为:string七、实验中出现的问题、解决方法和心得体会这个实验是对串的操作的时间，实现串操作的基本函数，在接受命令的输入格式方面，试了很多种方法。开始时尝试过用getchar（）函数来接收命令，并根据接受到的指令进行操作。在调试程序的过程中，遇到一些结果不正确或超出范围的情况，又要重新返回相应的函数进行检查和修改补充，才能使程序更加健壮和完整，才能做出一个更加实用的软件八、附录源程序#include #include #include #include typedef struct hstring char *ch; int length; hstring; hstring headlist100; int curnum=0; /系统中现有的串的数目int s3; /命令的串参数的内部名（最多3）char a20; char b5; int strcompare(hstring s,hstring t) /若st,则返回值0;若s=t,则返回值=0；若st,则返回值0; int i; for(i=0;is.length&it.length;+i) if(s.chi!=t.chi) return s.chi-t.chi; return s.length-t.length; void clearstring(hstring &s) /将s清为空串 if(s.ch) free(s.ch); s.ch=0; s.length=0; void strconcat(hstring &t,hstring s1,hstring s2) /用t返回由s1和s2联接而成的新串 int i,j; if(t.ch) free(t.ch); if(!(t.ch=(char*)malloc(s1.length+s2.length+1)*sizeof(char) printf(overflown);return; for(i=0;i=s1.length-1;i+) t.chi=s1.chi; t.length=s1.length+s2.length; for(i=s1.length,j=0;i=t.length-1;i+,j+) t.chi=s2.chj; for(i=0;it.length;i+) printf(%c,t.chi); int substring(hstring &sub,hstring s,int pos,int len) /用sub返回串s的第pos个字符起长度为len的子串 /其中，1=pos=strlength(s)且0=len=strlength(s)-pos+1 int i,j; if(poss.length | lens.length-pos+1) printf(参数不合法n); return 0; if(!len)sub.ch=0; sub.length=0; else sub.ch=(char*)malloc(len+1)*sizeof(char); for(i=0,j=pos-1;i=len-1;i+,j+) sub.chi=s.chj; sub.length=len; return 1; /else int strindex(hstring s,hstring t,int pos)/子串定位 int m,n,i; hstring sub; n=s.length; m=t.length; i=pos; if(m=0) return 0; while(i=n-m+1) substring(sub,s,i,m); if(strcompare(sub,t)!=0) +i; else return i; /while return 0; void strcopy(hstring &t,hstring s) /复制；由串s复制得串t int i; if(!s.length) t.ch=0; t.length=0; else t.ch=(char*)malloc(s.length+1)*sizeof(char); for(i=0;i=s.length-1;i+) t.chi=s.chi; /for t.length=s.length; curnum+; /else int strempty(hstring s) if(s.length=0) return 1; else return 0; void strreplace(hstring &s,hstring t,hstring v) /将串s中所有子串t替换为v int i,j,k,l; for(i=0;i=s.length-t.length;i+) for(j=i,k=0;t.chk & kt.length & s.chj=t.chk;j+,k+); if(k=t.length)/找到了与t匹配的子串：分三种情况处理 if(t.length=v.length) for(l=1;l=t.length;l+)/新子串长度与原子串相同时：直接替换 s.chi+l-1=v.chl-1; else if(t.length=i+t.length;l-) s.chl+v.length-t.length=s.chl; for(l=1;l=v.length;l+) s.chi+l-1=v.chl-1; else/新子串长度小于原子串时：先将后部左移 for(l=i+v.length;l=s.length+v.length-t.length-1;l+) s.chl=s.chl-v.length+t.length; for(l=1;l=v.length;l+) s.chi+l-1=v.chl-1; s.length=s.length-t.length+v.length; i+=v.length-1; /if /for void strassign() char c; int i; char a20; while(c=getchar()!=n) if(c=) i=0; while(c=getchar()!=) ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;iheadlistcurnum.length;i+) headlistcurnum.chi=ai; curnum+; printf(内部名：%d 串值:,curnum-1); for(i=0;i=48&c=48&c=57)/还是数字 bi+=c; bi=0; sj=atoi(b); j+; if(c=) i=0; while(c=getchar()!=) ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i=curnum|s1=curnum) printf(参数不合法n); else j=strcompare(headlists0,headl