串的基本操作演示实验报告

第1页共11页串的基本操作演示实验报告学号：姓名：班级：第2页共11页一．实验环境问题描述：如果语言没有把串作为一个预先定义好的基本类型对待，又需要用该语言写一个涉及串操作的软件系统时，用户必须自己实现串类型。试实现串类型，并写一个串的基本操作的演示系统。基本要求：在教科书4.2.2节用堆分配存储表示实现HString串的最小操作子集的基础上，实现串抽象数据类型的其余基本操作（不使用C语言本身提供的串函数）。参数合法性检查必须严格。说明：（在格式中，Φ表示0个、1个或多个空格所组成的串。〈串标识〉表示一个内部名或一个串文字。前者是一个串的唯一标识，是一种内部形式的（而不是字符形式的）标识符。后者是两端由单引号括起来的仅可打印字符组成的序列。串内每两个连续的单引号表示一个单引号符。）利用上述基本操作函数构造以下系统：它是一个命令解释程序，循环往复地处理用户键入的每一条命令，直至终止程序的命令为止。命令定义如下：（1）赋值。格式：AΦ〈串标识〉Φ〈回车〉用〈串标识〉所表示的值建立新串，并显示新串的内部名和串值。如：A′Hi！′（2）判相等。格式：EΦ〈串标识1〉Φ〈串标识2〉Φ〈回车〉若两串相等，则显示“EQUAL”，否则显示“UNEQUAL”。（3）联接。格式：CΦ〈串标识1〉Φ〈串标识2〉Φ〈回车〉将两串联接产生结果串，它的内部名和串值都显示出来。（4）求长度格式：LΦ〈串标识〉Φ〈回车〉显示串的长度。（5）求子串格式：SΦ〈串标识〉Φ+〈数1〉Φ+〈数2〉Φ〈回车〉如果参数合法，则显示子串的内部名和串值。〈数〉不带正负号。（6）子串定位。格式：IΦ〈串标识1〉Φ〈串标识2〉Φ〈回车〉显示第二个串在第一个串中首次出现时的位置。（7）串替换格式：RΦ〈串标识1〉Φ〈串标识2〉Φ〈串标识2〉Φ〈回车〉将第一个串中出现所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。（0）退出格式：QΦ〈回车〉结束程序的运行。二、实验内容第3页共11页编写一个程序，实现顺序串的各种基本运算，并在此基础上设计一个主程序。具体如下：编写栈的基本操作函数顺序串类型定义如下所示：typedefstructnode{chardata;structnode*next;}linkstring;（1）串赋值Assign(s,t)将一个字符串常量赋给串s,即生成一个其值等于t的串s（2）串复制StrCopy(s,t)将串t赋给串s（3）计算串长度StrLength(s)返回串s中字符个数（4）判断串相等StrEqual(s,t)若两个串s与t相等则返回1；否则返回0。（5）串连接Concat(s,t)返回由两个串s和t连接在一起形成的新串。（6）求子串index(s,j)返回找到串t在串s中的位置（7）插入InsStr(s,i,t)将串t插入到串s的第i(1≤i≤StrLength(s)+1)个字符中,即将t的第一个字符作为s的第i个字符,并返回产生的新串（8）串删除DelStr(s,i,j)从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生的新串。（9）串替换RepStr(s,s1,s2)在串s中,将所有出现的子串s1均替换成s2。（10）输出串DispStr(s)输出串s的所有元素值（11）判断串是否为空IsEmpty(s)（12）输入串inputchuan(charstr[100],linkstring*&s)输入字符串str并将字符串传递给指针串s三：程序：#includestdio.h#includeiostream.h#includestdlib.htypedefstructnode{chardata;structnode*next;}linkstring;voidassign(linkstring*&s,chart[])//将字符串t赋值给指针串s,并返回s第4页共11页{inti=0;linkstring*q,*tc;s=(linkstring*)malloc(sizeof(linkstring));s-next=NULL;tc=s;//tc指向s串的最后一个结点while(t[i]!='\0')//实现字符数组顺序赋值到串s{q=(linkstring*)malloc(sizeof(linkstring));q-data=t[i];tc-next=q;//使得s中与tc同地址的next指向q,使tc与q相连接tc=q;//tc直接指向qi++;}tc-next=NULL;}voidstrcopy(linkstring*&s,linkstring*t)//将t串赋值给s串并返回s{linkstring*p=t-next,*q,*tc;s=(linkstring*)malloc(sizeof(linkstring));s-next=NULL;tc=s;//tc指向s串的最后一个结点while(p!=NULL)//实现字符数组顺序赋值到串s{q=(linkstring*)malloc(sizeof(linkstring));q-data=p-data;tc-next=q;//使得s中与tc同地址的next指向q,使tc与q相连接tc=q;//tc直接指向qp=p-next;}tc-next=NULL;}intstrlength(linkstring*s)//求s的长度{intn=0;linkstring*p;p=s-next;while(p!=NULL){n++;p=p-next;}returnn;}第5页共11页voiddispstr(linkstring*s)//输出串s{linkstring*p=s-next;while(p!=NULL){coutp-data;p=p-next;}coutendl;}intstrequal(linkstring*s,linkstring*t)//判断s串和t串是否相等{linkstring*p,*q;p=s-next;q=t-next;while(p!=NULL&&q!=NULL){if(p-data!=q-data){return0;}p=p-next;q=q-next;}if(p!=NULL||q!=NULL){return0;}elsereturn1;}linkstring*concat(linkstring*s,linkstring*t)//将t串连接到s串后{linkstring*p,*q,*tc,*r;r=(linkstring*)malloc(sizeof(linkstring));r-next=NULL;tc=r;p=s-next;while(p!=NULL){q=(linkstring*)malloc(sizeof(linkstring));q-data=p-data;tc-next=q;tc=q;p=p-next;第6页共11页}p=t-next;while(p!=NULL){q=(linkstring*)malloc(sizeof(linkstring));q-data=p-data;tc-next=q;tc=q;p=p-next;}tc-next=NULL;returnr;}intindex(linkstring*s,linkstring*t)//找到串t在串s中的位置{linkstring*p,*q,*p1;inti=0;p=s-next;while(p!=NULL){q=t-next;//q始终从头开始与p进行比对if(p-data==q-data){p1=p;while(p1!=NULL&&q!=NULL&&p1-data==q-data){p1=p1-next;q=q-next;}if(q==NULL){returni;break;}}p=p-next;i++;}return-1;}intinstr(linkstring*&s,inti,linkstring*t)//将t插入s串的第i个位置{linkstring*q=s-next,*p=s,*r;第7页共11页intk;r=(linkstring*)malloc(sizeof(linkstring));strcopy(r,t);//p=r;//考虑到如果k=1的情况r=r-next;//free(p);for(k=0;ki;k++){if(q==NULL){return0;}p=q;q=q-next;}p-next=r;while(r-next!=NULL){r=r-next;}r-next=q;p=p-next;//s-next=p;return1;}intdelstr(linkstring*&s,inti,intj)//删除串s中从第i个位置开始的j个字符{intk;linkstring*p,*q;//q=s;p=s-next;for(k=0;ki;k++)//先找到第i个结点，让q指向第i个结点，让p指向第i+1个结点{if(p==NULL)return0;q=p;p=p-next;}for(k=0;kj;k++){if(p==NULL)return0;第8页共11页p=p-next;}q-next=p;return1;}voidrepstr(linkstring*&s,linkstring*t,linkstring*r)//将s中出现的t替换成r{inti;i=index(s,t);while(i=0){delstr(s,i,strlength(t));instr(s,i,r);i=index(s,t);}}voidinputchuan(charstr[100],linkstring*&s)//输入字符串str并将字符串传递给指针串s{cinstr;assign(s,str);}voidmain(){linkstring*s,*t,*r;//也可以先定义多个串指针实现书上说的“显示”“删除”两个功能；charstr[100],str1[100],str2[100];inti,n;cout输入要执行操作的序号endl;cout1)赋值2)判相等3)连接4)求长度5)求子串6)子串定位7)串替换0)退出endl;cinn;while(n!=0){switch(n){case1:{cout输入要赋值的串：endl;inputchuan(str,s);dispstr(s);break;}第9页共11页case2:{cout输入要判定是否相等的两个串：endl;inputchuan(str1,s);inputchuan(str2,t);if(strequal(s,t)==1)coutequalendl;elsecoutunequalendl;break;}case3:{cout输入要连接的两个串：endl;inputchuan(str1,s);inputchuan(str2,t);r=concat(s,t);dispstr(r);coutendl;break;}case4:{cout输入要求长度的串：endl;inputchuan(str,s);coutstrlength(s)endl;break;}case5:{break;}case6:{cout输入第一个串并输入要定位的串endl;inputchuan(str1,s);inputchuan(str2,t);n=index(s,t);if(n==-1)cout找不到endl;elsecoutn+1endl;break;}case7:{第10页共11页cout将第一个串中所有出现的第二个串用第三个串替代endl;inputchuan(str,s);inputchuan(str1,t);inputchuan(str2,r);repstr(s,t,r);di