数据结构实验五 串.doc

实验5 串的基本操作与应用 一、实验目的 1. 掌握串作为顺序结构的特点及串的基本操作2. 掌握顺序串的综合应用3. 了解串在文字处理中的应用模式。1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验题目 注意：要求实验中注意顺序串实现与C语言中给定串的功能函数的区别，从而真正体会串结构的特点及应用。 1.验证顺序串的基本操作。仔细阅读程序str.h和str.c，将程序补充完整并上机运行测试。。。。t在串s中出现的次数。要求：分别用顺序串和链串实现。 四、基本思想、原理和算法描述 要求写出题目2、题目4、题目5的算法的设计思想。 五、源程序及测试结果 测试结果可以屏幕截图。 [题目1的源程序] /****************str.h*******************/ /* 串的顺序存储 */ #include stdlib.h /***类型定义****/ #define INITSTRLEN 100 typedef struct { char *ch; int length; int strsize; }string; /******函数说明********/ void initstring(string *s); void strassign(string *s1,char *s2); void assign(string *s1,string s2); int length(string s); void concat(string *s,string s1,string s2); int equal(string s,string t); int substr(string s,int i,int j,string *t); int replace(string *s,int i,int j,string t); int insert(string *s, int i, string t); int delete(string *s,int i,int j); int index(string s,string t,int pos); /**串的模式匹配Brute-Force算法*/ void list(string s); /*****函数定义*********/ /*1初始化：创建一个空串*/ void initstring(string *s) { s-ch=(ch*)malloc(INITSTRLEN*sizeof(char)); if(!s-ch) {printf(OVERFLOW!); exit(1);} s-length=0; s-strsize= INTISTRLEN; } /*2串赋值操作：将字符串常量s2赋给字符串变量s1*/ void strassign(string *s1,char *s2) { int i=0; while(s2[i]!=’\0’) i++;/*①计算s2的串长*/ if(is1-strsize)/*②存储空间不足，增加存储空间*/ { s1-ch=(char *)realloc(s1-ch,i*sizeof(char)); s1-strsize=i; } s1-length=i;/*更新s1的长度*/ for(i=0;is1-length;i++)/*③从第一个字符开始逐个复制字符*/ s1-ch[i]=s2[i]; } /*3串复制操作：将字符串变量s2的值复制到字符串变量s1中 */ void assign(string *s1,string s2) { int i; if(s1-strsizes2-length)/*①若s1存储空间不足，增加存储空间*/ { s1-ch=(char *)realloc(s1-ch,s2.length*sizeof(char)); s1-strsize=s2.length; } s1-length=s2-length;/*②修改串长*/ for(i=0;is1-length;i++)/*③从s2第一个字符开始，逐个复制字符到s1中*/ s1-ch[i]=s2-ch[i]; } /*4求串s的长度 */ int length(string s) { return s-length; } /*5串连接：将字符串s1和s2连接后存到串s中*/ void concat(string *s,string s1,string s2) { int i,j; if(s-str