数据结构实验报告链串

1、宁波工程学院电信学院计算机教研室实验报告课程名称：_ 数据结构 _ _实验项目： 链串的基本算法 指导教师： 实验位置： 电子楼二楼机房 姓 名： 学 号： 班 级： 计科102 日 期： 2011/10/13 一、实验目的1）熟悉串的定义和串的基本操作。2）掌握链串的基本运算。3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C6.0的计算机。三、实验内容编写一个程序，实现链串的各种基本运算，并在此基础上设计一个主程序。具体如下：编写栈的基本操作函数链串类型定义如下所示：typedef struct snodechar data;struct snod

2、e *next;listring;（1）串赋值 Assign(s,t)n 将一个字符串常量赋给串s,即生成一个其值等于t的串s（2）串复制 StrCopy(s,t)n 将串t赋给串s（3）计算串长度 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插入到串

3、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，并输出t

4、1的长度（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<stdio.h>#include<stdlib.h>typedef struct snodechar data;struct snode *next;listring;/字符串赋

5、值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;

6、 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,

7、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(lis

8、tring); 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

9、,int i,int j)int k;listring *str,*p=s->next,*q,*r;str=(listring *)malloc(sizeof(listring);str->next=NULL;r=str;if(i<=0|i>strlength(s)|j<0|i+j-1>strlength(s)return str;for(k=0;k<i-1;k+)p=p->next;for(k=1;k<=j;k+) q=(listring *)malloc(sizeof(listring); q->data=p->data;r

10、->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(i<=0|i>strlength(s)+1)return str;for(k=1;k<i;k+) q=(listrin

11、g *)malloc(sizeof(listring); q->data=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-

12、>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(i<=0|i>strlength(s)|j<0|i+j-1>strlength(s)return str;for(k=0;k<i-1;k+) q=(listring *)malloc(sizeof(listr

13、ing); q->data=p->data;r->next=q;r=q; p=p->next;for(k=0;k<j;k+)p=p->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 *repstr(listring *s,int i,int j,listring *t)int k;listring *s

14、tr,*p=s->next,*p1=t->next,*q,*r; str=(listring *)malloc(sizeof(listring);str->next=NULL;r=str;if(i<=0|i>strlength(s)|j<0|i+j-1>strlength(s)return str;for(k=0;k<i-1;k+) q=(listring *)malloc(sizeof(listring); q->data=p->data;r->next=q;r=q; p=p->next;for(k=0;k<j;k

15、+)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;/字符串输出void dispstr(listring *s)listring *p

16、=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

17、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);

18、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;运行结果：四、实验心得与小结这次上机的内容是实现链串的基本算法，跟前面学的链表的基本算法是差不