串的基本操作-数据结构课程设计

1、数据结构课程设计报告井冈山大学电子与信息工程学院数据结构课程设计报告 ( 20122013年度第一学期)课程名称： 数据结构课程设计 题 目 一： 4.2串基本操作演示系统 院 系： 计算机科学系 班 级： 10软件本2班 姓 名： xxx 学 号： 100913017 指导教师： 孙凌宇老师 成 绩： 2012 年 12 月 10 日成 绩 评 定一、 指导教师评语二、 成绩成绩备注 指导教师： 日 期： 年 月 日设计题目<一>： 4.2串基本操作演示系统一、设计要求1问题描述如果计算机语言没有把串作为一个预先定义好的基本类型对待，又需要用该语言写一个涉及串操作的软件系统时，用

2、户必须自己实现串类型。试着实现串类型，并写一个串的基本操作演示系统。2需求分析实现若干串的常用基本操作，如串赋值、求串长、串替换、串比较、求子串及串的模式匹配等。二、概要设计为了实现以上功能，可以从3个方面着手设计。1 主界面设计为了实现串基本操作演示系统各功能的管理，本系统设计一个含有多个菜单项的主控单，方便用户使用。本系统主控菜单运行界面如图1所示。图1串演示系统主菜单2 存储结构设计使用串的堆分配存储表示，结构描述如下：typedef structchar *ch; /串存放的数组int curLen; /串的长度HString;3 系统功能设计本系统设置了主界面菜单，并在主界面上完成7

3、个功能的结果显示。7个功能的设计描述如下。(1)赋值（A-Assign）。由函数int strAssign()实现。当用户选择A功能时，输入待赋值的新串串值，系统完成串赋值并输出新串值。(2)求长度（L-Length）。由函数int StrLength()实现。当用户选择L功能时，系统输出串的长度。(3)求子串（S-SubString）。由函数int substring()实现，参数pos和len分别代表子串sub在原串S上的起始位置和子串长度。当用户选择S功能时，系统输出子串的串值。(4)子串定位（I-Index）。子串定位又称串的模式匹配，由函数int Index()实现。当用户选择I功能

4、时，系统根据用户输入的原串ob1和子串ob2的值输出子串在原串上的位置。(5)替换（R-Replace）。由函数void Replace()实现。当用户选择R功能时，系统根据用户输入的原串ob1、子串ob2和插入串ob3的值，输出用插入串替换了原串中所有指定子串后的串值。(6)判相等（C-Compare）。由函数int Compare()实现。当用户选择C功能时，系统根据用户输入的s1与s2的串值进行比较。若s1>s2则显示“s1>s2”；若s1=s2则显示“s1=s2”；若s1<s2则显示“s1<s2”。(7)退出（Q-Quit）。当用户选择Q功能时，即退出串基本操作

5、演示系统，有main()函数中的if语句实现。三、模块设计1模块设计本程序包含两个模块：主程序模块、串操作模块。其调用关系如图2所示。主程序模块串操作模块图2 模块调用关系示意图2系统子程序及功能设计(1) int initString(HString *T) /串类的初始化函数(2) int strAssign(HString *T,char *chars) /串赋值函数，调用malloc函数分配内存空间(3) int StrLength(HString S) /求串长函数(4) int substring(HString &Sub,HString S,int pos,int len

6、)/求串S的子串，pos代表子串sub的起始字符序号（位置），len代表子串sub的长度(5) int Index(HString &ob1,HString &ob2,int pos)/从第pos个字符起的子串定位（串的模式匹配）函数，调用(3).(6) void Replace(HString &ob1,HString &ob2,HString &ob3)/将原串ob1的所有子串ob2都替换为插入串ob3，调用（3）和（5）(7) int Compare(HString s1, HString s2) /串比较函数，调用（3）(8) void main

7、() /主函数，设定界面，调用操作模块函数4 函数主要调用关系图串基本操作演示系统8个子程序之间的主要调用关系如图3所示。图中字母是各函数的编号。8 main()23675413图3 系统函数调用关系图四、详细设计1数据类型定义(1) 字符串的定义typedef structchar *ch; /串存放的数组int curLen; /串的长度HString;(2) 全局变量声明#define OK 1 /操作成功#define OVERFLOW 0 /溢出#define ERROR 0 /出错2系统主要子程序详细设计(1)主程序模块设计主函数。设定用户操作界面，调用操作模块函数。void ma

8、in()输出操作菜单；Switch (1)输出操作序号c；switch (c)调用相应函数执行相应操作；输出操作结果；(2)求子串int substring(HString &Sub,HString S,int pos,int len)/´串sub返回串S的第pos个字符起长度为len的子串int i;if(pos<0|pos>S.curLen|len<0|len>S.curLen-pos) /若位置或长度不合法，退出printf("输入不合法n"); exit(OVERFLOW); /退出elseif(Sub.ch) free(S

9、ub.ch); /释放子串sub原有空间if(!len) /若长度len为0 /就爱那个子串置为空串Sub.ch=NULL;Sub.curLen=0;else /若长度len不为0Sub.ch=(char*)malloc(len*sizeof(char);for(i=0; i<len; i+) /从串S的第pos个字符开始依次复制其后长度为len的字符串sub中Sub.chi=S.chpos-1+i; Sub.curLen=len; /修改串sub的串长return OK;(3)子串定位（串的模式匹配）int Index(HString &ob1,HString &ob2

10、,int pos) /判断从第pos个字符起，ob2是否为ob1的子串 /若是返回ob2在ob1中的起始位置，否则返回-1 if(pos<0|pos>ob1.curLen) /若输入的数值pos不在ob1的串长范围内printf("输入有误n");exit(ERROR);for(int i=pos-1; i<=StrLength(ob1)-StrLength(ob2); i+) /从ob1的第pos个字符起查找子串ob2int j=0; /从ob2的第一个字符起开始查找 while(j<StrLength(ob2) /j控制查找位置，逐个字符查找，直

11、到超出子串串长if(ob1.chi+j=ob2.chj) /若找到匹配字符j+; /则依次向后查找else break; /一旦失配，则跳出查找，此时j还未能达到子串串长if(j=StrLength(ob2) /若j达到子串串长，即ob2的所有字符都能和ob1匹配return i; /返回ob2在ob1的起始位置i return -1; /ob2不是ob1的子串，返回-1(4)串替换void Replace(HString &ob1,HString &ob2,HString &ob3) /将原串ob1的所有子串ob2都替换为插入串ob3printf("原串：&

12、quot;); for(int i=0; i<ob1.curLen; i+)printf("%c",ob1.chi); printf("n 子串："); for(int j=0; j<ob2.curLen; j+)printf("%c",ob2.chj); printf("n"); printf("插入串："); for(int k=0; k<ob3.curLen; k+)printf("%c",ob3.chk); printf("n")

13、; int len=StrLength(ob2); /ob2的长度 while(Index(ob1,ob2,0)!=-1) /当ob2是ob1的子串，替换所有的ob2 int len2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2); /新串的长度int i=Index(ob1,ob2,0); /调用子串定位函数char *p=new charStrLength(ob1)-i-len+1; /临时数组char *q=new charlen2; /存储新串的数组 for(int j=i+len; j<StrLength(ob1); j+)pj=ob

14、1.chj; /将不用替换的后部分存入数组pfor(int k=0; k<i; k+)qk=ob1.chk; /将不用替换的前部分存入数组qfor(int m=i; m<i+StrLength(ob3); m+)qm=ob3.chm-i; /替换子串int b=i+len;for(int n=i+StrLength(ob3); n<len2; n+) /将不用替换的后部分存入数组qqn=pb;b+; /数组q存储着新串 ob1.curLen=len2;for(int l=0; l<len2; l+)ob1.chl=ql; /将新串赋值给ob1做循环替换printf(&q

15、uot;新串："); for(int h=0; h<ob1.curLen; h+)printf("%c",ob1.chh); (5)串比较int Compare(HString s1, HString s2)/若s1<s2则返回值<0; 若s1=s2则返回值=0; 若s1>s2则返回值>0int i;for(i=0; i<s1.curLen&&i<s2.curLen; +i)if(s1.chi!=s2.chi)return (s1.chi-s2.chi);return (s1.curLen-s2.curLe

16、n);五、测试分析系统运行主界面如图1所示。各子系统测试运行结果如下。1. 赋值（A-Assign）在主菜单下，输入A hello!并回车，运行结果如图4所示。图4字符串赋值2. 求长度（L-Lengh）在主菜单下，输入L student并回车，运行结果如图5所示。图5求字符串长度3. 求子串（S-SubString）在主菜单下，输入S student 2 5 并回车，运行结果如图6所示。图6求子串4. 子串定位（I-Index）在主菜单下，分别输入I microsoftvisualc+ soft 1并回车和I microsoftvisualc+ soft 8，运行结果如图7所示。图7子串定位

17、5. 替换（R-Replace）在主菜单下，输入R chicken c t并回车，运行结果如图8所示。图8字符串替换6. 判相等（C-Compare）在主菜单下，分别输入C on in并回车和C on on并回车，运行结果如图9所示。图9判两串相等7. 退出（Q-Quit）在主菜单下，输入Q并回车，退出串基本操作演示系统。六、用户手册 (1)本程序执行文件为“串的基本操作演示.exe”。(2)进入本系统之后，随即显示系统主菜单界面。用户可在该界面下按提示信息输入命令。七、调试报告(1) 我不喜欢敲代码，写一个简单的程序时竟然老是出错，难一点的，复杂一点的程序竟然无从下手，程序的架构根本不懂，以

18、至于程序存在许多bug，不过只要按着提示操作，还是可以完成相应的功能。(2)如果有兴趣还可以对次程序进行深入研究，进行修改，添加等一些串的其他功能。八、程序清单#include <stdlib.h>#include <iostream>#include <conio.h>#define OK 1#define OVERFLOW 0 #define ERROR 0using namespace std; /使用名称空间std/*串的堆分配存储表示typedef struct char *ch; /串存放的数组 int curLen; /串的长度HString;

19、/*1. 初始化字符串T int initString(HString *T) (*T).ch=NULL;(*T).curLen=0;return OK;/*2. 串赋值函数int strAssign(HString *T,char *chars) /生成一个值等于串常量chars的串T并用指针返回,*chars为指针(数组名) int i,j; if(*T).ch) free(*T).ch); /释放T原有空间 i=strlen(chars); /数组chars的长度 if(!i) /若chars为空串，生成空串的堆分配存储表示 (*T).ch=NULL; (*T).curLen=0; el

20、se / chars不为空串 if(!(*T).ch=(char *)malloc(i*sizeof(char) exit(OVERFLOW); /分配串的堆空间，若失败则退出 for(j=0; j<i; j+) (*T).chj=charsj; (*T).curLen=i; return OK;/*3. 求串长函数int StrLength(HString S) return S.curLen; /直接返回串长/*4. 求子串函数int substring(HString &Sub,HString S,int pos,int len)/串Sub返回串S的第pos个字符起长度为l

21、en的子串int i;if(pos<0|pos>S.curLen|len<0|len>S.curLen-pos) /若位置或长度不合法，退出printf("输入不合法n"); exit(OVERFLOW); /退出elseif(Sub.ch) free(Sub.ch); /释放子串sub原有空间if(!len) /若长度len为0 /将子串置为空串Sub.ch=NULL;Sub.curLen=0;else /若长度len不为0Sub.ch=(char*)malloc(len*sizeof(char);for(i=0; i<len; i+) /从

22、串S的第pos个字符开始依次复制其后长度为len的字符串到串Sub中Sub.chi=S.chpos-1+i; Sub.curLen=len; /修改串Sub的串长return OK;/*5. 子串定位函数（串的模式匹配）int Index(HString &ob1,HString &ob2,int pos) /判断从第pos个字符起，ob2是否为ob1的子串/若是返回ob2在ob1中的起始位置，否则返回-1 if(pos<0|pos>ob1.curLen) /若输入的数值pos个字符起，ob2是否为ob1的子串printf("输入有误n");ex

23、it(ERROR);for(int i=pos-1; i<=StrLength(ob1)-StrLength(ob2); i+) /从ob1的第pos个字符起查找子串ob2int j=0; /从ob2的第一个字符起开始查找 while(j<StrLength(ob2) /j控制查找位置，逐个字符查找，直到超出子串串长if(ob1.chi+j=ob2.chj) /若找到匹配字符j+; /则依次向后查找else break; /一旦失配，则跳出查找，此时j还未能达到子串串长if(j=StrLength(ob2) /若j达到子串串长，即ob2的所有字符都能和ob1匹配return i;

24、/返回ob2在ob1的起始位置i return -1; /ob2不是ob1的子串，返回-1/*6. 串替换函数void Replace(HString &ob1,HString &ob2,HString &ob3) /将原串ob1的所有子串ob2都替换为插入串ob3printf("原串："); for(int i=0; i<ob1.curLen; i+)printf("%c",ob1.chi); printf("n子串："); for(int j=0; j<ob2.curLen; j+)printf

25、("%c",ob2.chj); printf("n"); printf("插入串："); for(int k=0; k<ob3.curLen; k+)printf("%c",ob3.chk); printf("n"); int len=StrLength(ob2); /ob2的长度 while(Index(ob1,ob2,0)!=-1) /当ob2是ob1的子串，替换所有的ob2 int len2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2);

26、/新串的长度int i=Index(ob1,ob2,0); /调用子串定位函数char *p=new charStrLength(ob1)-i-len+1; /临时数组char *q=new charlen2; /存储新串的数组 for(int j=i+len; j<StrLength(ob1); j+)pj=ob1.chj; /将不用替换的后部分存入数组pfor(int k=0; k<i; k+)qk=ob1.chk; /将不用替换的前部分存入数组qfor(int m=i; m<i+StrLength(ob3); m+)qm=ob3.chm-i; /替换子串int b=i+

27、len;for(int n=i+StrLength(ob3); n<len2; n+) /将不用替换的后部分存入数组qqn=pb;b+; /数组q存储着新串 ob1.curLen=len2;for(int l=0; l<len2; l+)ob1.chl=ql; /将新串赋值给ob1做循环替换printf("新串："); for(int h=0; h<ob1.curLen; h+)printf("%c",ob1.chh); /*7. 串比较函数int Compare(HString s1, HString s2)/若s1<s2则返回

28、值<0; 若s1=s2则返回值=0; 若s1>s2则返回值>0int i;for(i=0; i<s1.curLen&&i<s2.curLen; +i)if(s1.chi!=s2.chi)return (s1.chi-s2.chi);return (s1.curLen-s2.curLen);/8. 主函数void main() printf("*串基本操作演示系统*n"); printf("* . 赋值 格式为: A 串值 *n"); printf("* . 求长度 格式为: L 串值 *n"

29、;); printf("* . 求子串 格式为: S 串值 数1 数2 *n"); printf("* . 子串定位 格式为: I 串值1 串值2 数1 *n"); printf("* . 串替换 格式为: R 串值1 串值2 串值3 *n"); printf("* . 串比较 格式为: C 串值1 串值2 *n"); printf("* . 退出 格式为: Q *n"); printf("*n"); while(1)char c;printf("请看菜单输入您要进

30、行的操作并回车(全部用大写):"); cin>>c; /输入大写字母 if(c='Q') break; /退出串基本操作演示系统 switch(c) /用switch语句对输入的大写字母进行多向选择 case'A': char cnew50; HString str; initString(&str); /初始化串str scanf("%s",cnew); strAssign(&str,cnew); /调用串生成函数 printf("字符串为:"); for(int i=0;i <

31、;str.curLen; i+) printf("%c",str.chi); printf("n"); break; case 'L': char cnew50; scanf("%s",cnew); HString str; initString(&str); /初始化串str strAssign(&str,cnew); /调用串生成函数 printf("长度为：%dn",StrLength(str); /调用StrLength函数 break; case 'S':

32、char cnew50; int pos,len; cin>>cnew>>pos>>len; HString sub,str; initString(&sub); /初始化串sub initString(&str); /初始化串str strAssign(&str,cnew); /调用串生成函数 substring(sub,str,pos,len); /调用子串函数 printf("子串为:"); for(int i=0; i<sub.curLen; i+) printf("%c",sub.chi); printf("n"); break; case '