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

宁波工程学院电信学院计算机教研室 实验报告 课程名称： ___ 数据结构 ___ __ 姓 名： 实验项目： 链串的基本算法 学 号： 指导教师： 班 级： 计科 102 实验位置： 电子楼二楼机房 日 期： 2011/10/13 一、实验目的 1）熟悉串的定义和串的基本操作。 2）掌握链串的基本运算。 3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有 Visual C ＋＋6.0 的计算机。 三、实验内容 编写一个程序，实现 链串 的各种基本运算，并在此基础上设计一个主程序。 具体如下： 编写栈的基本操作函数 链串类型定义如下所示： typedef struct snode{ char data; struct snode *next; }listring; （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）求子串 SubStr(s,i,j) 返回串 s 中从第 i(1≤ i≤ StrLength(s)) 个字符开始的、由连续 j 个字符组成的子串。 （ 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) 编写主函数 调用上述函数实现下列操作： （ 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 是否相等，输出结果 程序清单： #includestdio.h #includestdlib.h typedef struct snode{ char 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;cstr[i]!=\0;i++){ p=(listring *)malloc(sizeof(listring)); p-data=cstr[i]; 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