字符串类课程设计说明书.doc

目 录 前言 .1 正文 .1 21 设计的目的和意义.1 22 目标与总体方案.1 23 设计方法和内容.2 231 开发环境 2 232 设计流程图 2 233 设计内容 3 24 设计创新和关键技术.4 25 结论.5 致谢 .6 参考文献 6 附录 7 塔里木大学信息工程学院课程设计 第 1 页 共 14 页 前言前言 在科技日新月异的今天，电脑成为人的生活中不可缺少的一部分。作为计算机专业的学生， 应该充分利用所学知识，把实际问题转移到电脑上去，通过电脑的编程，使复杂问题简单化，深 奥问题浅显化，抽象问题具体化。在学过面向对象的语言 C+后，我们对计算机有了更深的了解。 计算机科学是一种创造性思维活动，其教育必须面向设计。 “数据结构”正是一门面向设计，且处 于计算机学科核心地位的技术基础和主干必修课。 字符串数据是计算机非数值处理的主要对象之一。随着语言加工程序的发展，许多语言增加 了字符串类型，在程序中可以使用字符串变量进行一系列字符串操作1。例如：在事务处理程序 中，顾客的姓名和地址以及货物的名称、产地和规格等。要是将这些信息用计算机存储起来，进 行各种操作都会很方便了。在这里，我针对字符串的处理写了许多操作，这将对信息检索系统有 很大的作用。 本次设计主要设计的是关于字符串类的研究。在里面囊括了串的多种实现方式，如顺序存储； 建立一个值和某个字符串相等的串，块链存储。其次，在本次设计中，可以对串进行求长度，判 断是否为空，清空某个串，在主串中插入一个子串，在主串中删除一个子串，返回主串的的某个 子串，将字符串反转输出，将主串的某个子串用另一个串替换，复制一个串，将两个串进行比较， 将两个串联结在一起，求一个子串在主串中第一次出现的位置，查找字符串中元音字母的个数， 判断一个串是否是回文，串的大小写转换，将一个串转换成整数。 此次设计应用广泛，文字编辑程序、事务问答系统、自然语言翻译系统、音乐分析程序等都 可以应用这个原理实现。 正文正文 数据结构指的是数据之间的逻辑关系以及数据在计算机中的存储方式。我们现在所使用的计 算机的硬件结构主要是面向数值计算的需要，基本上没有提供处理字符串数据的操作指令，需要 用软件实现字符串数据类型，在不同的应用中，所处理的字符串具有不同的特点2。作为计算机 专业的学生，应该努力学好各种计算机语言，培养编程创新的能力。 21 设计的目的和意义 目的：程序=算法+数据结构。本次设计主要是研究串类的各种操作方式。集合了串的各种操 作算法并对此进行编程，熟悉了解并掌握串的各种算法，对以后做信息检索系统等都有很大的用 处。 意义：字符串是一个计算机进行输入输出的主要数据对象。在计算机内部计算和处理数据时， 这是一个数据的值和表示形式之间关系的问题。在 web 应用设计中，不同页面之间传递参数采用 字符串。当人们坐在计算机前面输入数据时，通过键盘操作和鼠标的点击，传递给计算机内部的 都是字符串数据。所以研究字符串的结构非常必要3。 22 目标与总体方案 目标：建立一个操作菜单。通过选择菜单里的选项，达到操作字符串，实现串的不同建立， 求串的长度，判断一个串是否为空，清空某个串，在主串中插入一个子串，在主串中删除一个子 串，返回主串的的某个子串，将字符串反转输出，将主串的某个子串用另一个串替换，复制一个 串，将两个串进行比较，将两个串联结在一起，串的大小写转换，将一个串转换成整数等目的。 总体方案：首先，建立一个字符串。建立字符串的方式有：顺序存储、建立一个值为某个串 的字符串、块链存储。再依次实现其它操作。 塔里木大学信息工程学院课程设计 第 2 页 共 14 页 23 设计方法和内容 231 开发环境 硬件环境：一台联想计算机，其配置为：CPU: Pentium(R)4 2.4GHz 内存：256MB 硬盘：40G 主板：SIS651-A201-8100. 软件环境：Microsoft Windows XP Professional 版本 2002 Service Pack 2 并且安装了可 供编程的 Microsoft visual C+6.0. 232 设计流程图 本次程序的类命名为 String，里面的成员函数包括：逻辑 bool 类型的有 StrAssign(char *chars) (利用已有的一个 char 串建立一个字符串)，Insert()(在主串中插入一个子串)，Delete()(在子串中删 除一个子串)，substring (String 转换函数大写：char *Mytoupper(char *src); 求串的长度：int Length(); 插入：bool Insert(); 删除：bool Delete(); 定位：int Index(); 定位：int Index();串的反转：void Strrev(); 复制：void Strcopy(); 比较：int Compare(String s); 返回子串：bool substring (String 联结：bool Concat(String s); 返回子串：bool Substring (String 计算元音个数：int count_Vowel(const char *s); 转换函数小写：char*Mytolower(char *src); 已知串 char：bool StrAssign(char *chars) 类 String 图图 2-12-1 设计流程图设计流程图 塔里木大学信息工程学院课程设计 第 3 页 共 14 页 233 设计内容 在各种高级语言的编译程序中，源程序和目标程序都被处理成字符串数据，各种源程序编辑 器的功能强弱有差异，但其基本操作是一致的，一般都包括串的查找、插入、删除、转换等4。 本设计中，整个程序分为三个独立的文档。其中包括：头文件 string.h，源文件 string.cpp 和 main.cpp。头文件包括一个类 class String，里面是对各个函数进行声明。类的私有成员有一维数组 str140。字符串的最大长度 maxlen；字符串的当前长度 curlen。 串是一种特殊的线性表，它的每一个元素仅有一个字符所组成。因此可以用线性表的存储方 法来存储串。串的实现方式大致分为三种：1.串的顺序存储；2.串的块链存储；3.串的堆分配存储。 串的顺序存储是用一组地址连续的储存单元存储字符串的字符序列，这样的存储结构访问一组连 续字符非常方便，体现了顺序表的优点：随机存储6。串的块链丰储类似线性表中的链表，不过 在一个结点中它储存的并不是一个字符，而是一个字符串，一般来说，以块链作为存储结构时实 现串的操作比较麻烦。串的堆分配存储的特点是串变量的存储空间是程序执行过程中动态分配而 得，程序中出现的所有串变量可用的存储空间是一个称之为“堆”的共享空间。在本设计中，运 用的是已知一个字符串再建立一个字符串。8存储方式的代码如下： bool SString:StrAssign(char *chars) /生成一个值为 chars 的串 if(strlen(chars)maxsize) /判断 chars 的长度是否比串的长度大 return false; /大，则错误 else curlen=strlen(chars); /令串的长度等于 chars 的长度 for(int i=1;icurlen 时，显示出错信息 并终止。 （2）当插入后的新串长度超出当前串的最大值，即 curlen+tlen=maxlen-1 时，重新分 配空间。 （3）将当前串中从 pos 开始至串尾的一些字符后移留出 tlen 个空位，然后将子串插入到 对应的空位中。 （4）更新当前串的长度为 curlen+tlen，返回当前串。删除操作是指删除当前串 中指定范围内的串值。删除的算法是：（1）输出所要删除的子串的位置 pos 及子串的长度 塔里木大学信息工程学院课程设计 第 4 页 共 14 页 tlen。 （2）检查位置的合法性。即当 poscurlen-1 或 poscurlen-pos 时，则按截尾法对 tlen 进行调整。 （3）确定新串的长度为 curlen-tlen，删除当前串中从 pos 开始的长度为 tlen 的子串，即重新 形成当前串中 pos 开始至新串串尾 cluren-1 的一些字符，这些字符分别由相隔 tlen 个位置的对 应字符前移而来。 （5）返回当前串。子串的定位操作通常称为字符串的模式匹配，是指在当前串 中查找与子串，若查找成功则返回该子串的位置。13定位操作的基本思想是：(1)设主串 S=s1,s2,sn，子串 P=p1,p2,pm。 （2）i 为指向 S 中字符的指针，j 为指向 P 中字符的指针， 从主串 S 中第 pos 个字符起和模式中第一个字符比较。若相等，则继续逐个比较后续字符；否则 从主串的下个字符起再重新和模式字符比较。 （3）匹配失败：si!=pj 时，(si-j+1 si-1) =(p1 pj-1)。 （4）回溯：i=i-j+1;j=0.此程序由于重复回溯太多，所以时间复杂度是 O(m*n)。 9改进后的模式匹配算法称作 KMP 算法。这个算法是同 D.E.Knuth, J.H.Morris, V.R.Pratt 同时 发现的。在该算法中指针 i 没有回溯。它的核心思想是利用已经得到的部分匹配信息来进行后面 的匹配过程 。改进后的算法如下： int String:Index_KMP(char *t,int k) /KMP 算法 int i,j,tlen; i=k;j=0;tlen=strlen(t); while(icurlen-1 或 pos #include using namespace std; class String public: bool StrAssign(char *chars); /生成一个其值为 chars 的串 char *Mytoupper(char *src); /转换函数大写 char*Mytolower(char *src); /转换函数小写 int Length(); /求串的长度 bool Insert(); /插入一个子串 bool Delete(); /删除一个子串 int Index(); /定位 void print(); /输出函数 void display(); /输出函数 void Strcopy(); /复制串 int compare(String s); /比较两个串的大小 bool concat(String s); /将两个串合成一个串 bool substring (String /返回子串 void strrev(); /串反转 int vowel(char a); int count_vowel(const char *s); /计算元音个数 int huiwen(char *str); /判断字符串是否是回文 private: int maxlen; /串的最大长度 int curlen; /串的当前长度 char str40; /建立一个数组 str ; /end of string.h 在源程序 string.cpp 中，代码如下： /string.cpp #include #include “string.h“ bool String:StrAssign(char *chars) /生成一个其值为 chars 的串 maxlen=100; if(strlen(chars)maxlen) /判断 chars 的长度是否大于串的最大长度 return false; else 塔里木大学信息工程学院课程设计 第 8 页 共 14 页 curlen=strlen(chars); /串的长度等于 chars 的长度 for(int i=0;ipos; int tlen; /要插入的子串 char s20; couts; tlen=strlen(s); if(poscurlen) /判断 pos 位置是否合法 return false; 塔里木大学信息工程学院课程设计 第 9 页 共 14 页 else for(int i=curlen-1;i=pos-1;i-) stri+tlen=stri; /移位，空出子串的位置 for(i=0;ipos; int tlen; /要删除的子串的长度 couttlen; if(poscurlen) /判断位置是否合法 return false; else for(int i=pos-1;it1; coutpos; int len; /子串的长度 coutlen; if(poscurlen|lencurlen+pos-1) /判断位置是否合法 return false; else for(int i=1;i=0;i-) /将串逆输出 cout=j flag=0; /不相等就终止 break; return (flag); void String:display() /输出 cout #inc