数据结构实验报告3--链串.doc

. . . . 工程学院电信学院计算机教研室实验报告10 / 10课程名称：_ 数据结构 _ _实验项目： 链串的根本算法 指导教师： 实验位置： 电子楼二楼机房 姓 名： 学 号： 班 级： 计科102 日 期：2011/10/13 一、实验目的1熟悉串的定义和串的根本操作。2掌握链串的根本运算。3加深对串数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C6.0的计算机。三、实验容编写一个程序，实现链串的各种根本运算，并在此根底上设计一个主程序。具体如下：编写栈的根本操作函数链串类型定义如下所示：typedef struct snodechar data;struct snode *next;listring;1串赋值 Assign(s,t)n 将一个字符串常量赋给串s,即生成一个其值等于t的串s2串复制 StrCopy(s,t)n 将串t赋给串s3计算串长度 StrLength(s)n 返回串s中字符个数4判断串相等StrEqual(s,t)n 假设两个串s与t相等那么返回1；否那么返回0。5串连接 Concat(s,t) n 返回由两个串s和t连接在一起形成的新串。6求子串 SubStr(s,i,j)n 返回串s中从第i(1iStrLength(s)个字符开始的、由连续j个字符组成的子串。7插入InsStr (s,i,t)n 将串t插入到串s的第i(1iStrLength(s)+1)个字符中,即将t的第一个字符作为s的第i个字符,并返回产生的新串8串删除 DelStr (s,i,j)n 从串s中删去从第i(1iStrLength(s)个字符开始的长度为j的子串,并返回产生的新串。9串替换 RepStr (s,s1,s2)n 在串s中,将所有出现的子串s1均替换成s2。10输出串DispStr(s)n 输出串s的所有元素值11判断串是否为空 IsEmpty(s)编写主函数调用上述函数实现以下操作：（1） 建立串s=“abcdefghijklmn，串s1=“xyz，串t“hijk（2） 复制串t到t1，并输出t1的长度（3） 在串s的第9个字符位置插入串s1而产生串s2，并输出s2（4） 删除s第2个字符开始的5个字符而产生串s3，并输出s3（5） 将串s第2个字符开始的3个字符替换成串s1而产生串s4，并输出s4（6） 提取串s的第8个字符开始的4个字符而产生串s5，并输出s5（7） 将串s1和串t连接起来而产生串s6，并输出s6（8） 比拟串s1和s5是否相等，输出结果程序清单：#include#includetypedef struct snodechar data;struct snode *next;listring;/字符串赋值void strassign(listring *&s,char cstr)int i;listring *r,*p;s=(listring *)malloc(sizeof(listring);r=s;for(i=0;cstri!=0;i+)p=(listring *)malloc(sizeof(listring);p-data=cstri;r-next=p;r=p;r-next=NULL;/字符串复制void strcopy(listring *&s,listring *t)listring *p=t-next,*q,*r; s=(listring *)malloc(sizeof(listring);r=s;while(p!=NULL)q=(listring *)malloc(sizeof(listring);q-data=p-data;r-next=q;r=q;p=p-next;r-next=NULL;/字符串长度int strlength(listring *s)int i=0;listring *p=s-next;while(p!=NULL)i+;p=p-next;return i;/判断字符串是否相等int strequal(listring *s,listring *t)listring *p=s-next,*q=t-next;while(p!=NULL&q!=NULL&p-data=q-data)p=p-next;q=q-next;if(p=NULL&q=NULL)return 1;elsereturn 0;/字符串连接listring *concat(listring *s,listring *t)listring *str,*p=s-next,*q,*r; str=(listring *)malloc(sizeof(listring); r=str;while(p!=NULL)q=(listring *)malloc(sizeof(listring);q-data=p-data;r-next=q;r=q; p=p-next;p=t-next;while(p!=NULL)q=(listring *)malloc(sizeof(listring); q-data=p-data;r-next=q;r=q; p=p-next;r-next=NULL;return str;/字符串的子串listring *substr(listring *s,int i,int j)int k;listring *str,*p=s-next,*q,*r;str=(listring *)malloc(sizeof(listring);str-next=NULL;r=str;if(istrlength(s)|jstrlength(s)return str;for(k=0;knext;for(k=1;kdata=p-data;r-next=q;r=q; p=p-next;r-next=NULL;return str;/字符串插入listring *insstr(listring *s,int i,listring *t)int k;listring *str,*p=s-next,*p1=t-next,*q,*r;str=(listring *)malloc(sizeof(listring);str-next=NULL;r=str;if(istrlength(s)+1)return str;for(k=1;kdata=p-data;r-next=q;r=q; p=p-next; while(p1!=NULL)q=(listring *)malloc(sizeof(listring);q-data=p1-data;r-next=q;r=q; p1=p1-next; while(p!=NULL)q=(listring *)malloc(sizeof(listring);q-data=p-data;r-next=q;r=q; p=p-next;r-next=NULL;return str;/字符串删除listring *delstr(listring *s,int i,int j)int k; listring *str,*p=s-next,*q,*r; str=(listring *)malloc(sizeof(listring);str-next=NULL;r=str;if(istrlength(s)|jstrlength(s)return str;for(k=0;kdata=p-data;r-next=q;r=q; p=p-next;for(k=0;knext;while(p!=NULL) q=(listring *)malloc(sizeof(listring); q-data=p-data;r-next=q;r=q; p=p-next;r-next=NULL;return str;/字符串替换listring *repstr(listring *s,int i,int j,listring *t)int k;listring *str,*p=s-next,*p1=t-next,*q,*r; str=(listring *)malloc(sizeof(listring);str-next=NULL;r=str;if(istrlength(s)|jstrlength(s)return str;for(k=0;kdata=p-data;r-next=q;r=q; p=p-next;for(k=0;knext; while(p1!=NULL)q=(listring *)malloc(sizeof(listring);q-data=p1-data;r-next=q;r=q; p1=p1-next; while(p!=NULL)q=(listring *)malloc(sizeof(listring);q-data=p-data;r-next=q;r=q; p=p-next;r-next=NULL;return str;/字符串输出void dispstr(listring *s)listring *p=s-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);/判断字符串是否为空void empstr(listring *s)if(s-next=NULL)printf(字符串是空的!);elseprintf(字符串不为空!);void initstr(listring *&s)s=(listring *)malloc(sizeof(listring);s-next=NULL;/主函数int main(void)listring *s,*s1,*t,*t1,*s2,*s3,*s4,*s5,*s6; int l;strassign(s,abcdefghijklmn); strassign(s1,xyz); strassign(t,hijk); strcopy(t1,t);printf(输出t1的长度:%dn,strlength(t1); s2=insstr(s,9,s1); printf(输出s2:n);dispstr(s2); s3=delstr(s,2,5); printf(输出s3:n);dispstr(s3); s4=repstr(s,2,3,s1); printf(输出s4:n);dispstr(s4);s5=substr(s,8,4); printf(输出s5:n);dispstr(s5); s6=concat(s1,t); printf(输出s6:n);dispstr(s6); l=strequal(s1,s5);if(l=1) printf(s1与s5相等!);elseprintf(s1与s5不相等!);return 0;运行结果：四、实验心得与小结这次上机的容是实现链串的根本算法，跟前面学的链表的根本算法是差不多的，所以这次实验还是比拟简单的，但也曾出现过一点点小问题，直接把字符串赋值给指针s=abcdefghijklmn;s1=xyz;t=hijk;结果出现如下错误：通过调用函数void strassign(listring *&s,char cstr)将其订正为strassign(s,abcdefghijklmn);strassign(s1,xyz);strassign(t,hijk);后没有错误；编译、组建都没有错误的情况下，s2是在串s的第9个字符位置插入串s1而产生的，本应出现的结果为 可运行时却出现如下的结果查找了原因之后才发现在插入s1数据时，都把s的第九个字母的数据赋值给了s2，*p1=s1-next；q-data=p-data;把错误改为q-data=p1-data;后运行正确。 虽然链串的根本算法的操作还是比拟简单，但也会犯一些毛病，必须通过上机编译调试才能发现，上机之后才能把自认为对的代码重新纠正过来，从而有所进步。通过这次的上机实验，我熟悉了串的定义和串的根本操作，掌握了链串的根本运算，加深对串数据结构的理解并逐步培养解决实际问题的编程能力。五、指导教师评议成绩评定： 指导教师签名：