实验三字符串

《实验三字符串》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第3章串3.1知识点概述串是一种特殊的线性表，它的每个结点仅由一个字符组成。串是计算机中主要的非数值处理的对象，在计算机文字编辑、词法分析等方面有着广泛的应川。串的基本运算有：串赋值、串复制、判断串空否、求串长、串联接、求子串、子串位置、串比较、串置换、插入和删除等。申的存储有顺序存储（定长顺序存储和堆存储）和链式存储。3.2字符串的基本橾作一、实验目的1、掌握字符串的基本操作2、掌握字符串函数的基本使用方法3、熟悉串的模式匹配算法和一般的文字处理方法二、实验内容（一）验证实验1、串的模式匹配：设有一

2、0标串s和一模式串sl，判断目标串s屮是否包含模式串slo方法是：从目标串S屮的第一个字符开始，按si模式串的长度sl.len,与Sl子串屮的字符依次对应比较。若不匹配，则再从目标串s中的第二个字符开始，仍按sl模式串的长度sl.len,与51子串中的字符依次对应比较。如此反复进行比较。直到匹配成功或者0标串s中剩余的字符少于sl的长度为止。若匹配成功，则返回sl在s中的位置。若匹配不成功，则返冋函数值一1。2、串连接：将两个字符串连接。其中一个串接在另一个串的末尾，生成一个新串。（注意：串的末尾有

3、0）若给出两个串sl和s2,把s2连接在sl之后，生成一个新串s。3、两串相等判断：给定两个串sl和s2,当sUDS2相等吋，返回函数值1，否则返回函数值0。（二）设计实验K写一个串的基本操作演示系统。在该演示系统屮，能提供命令行的输入，能对输入的命令进行简单的编译并作出相应的出错处理，最后根据命令动词功能来执行命令行。命令定义如下：（1）赋值：assign串名1串名2例如输入命令assignsstt操作结果是将串tt赋值给了ss串（2）新建：creat串名1字符串常量例如输入命令creatss‘ab

4、cdefg’操作结果是将字符串常量赋值给串ss，注意：字符串常量两边川单引号括起来，不能省略(3)判断：equal串名1串名2例如输入命令equalsstt操作结果是根据两串比较的结果输出相应的信息(4)求串长:length串名例如输入命令lengthss操作结果是返回字符串的长度(5)字符串连接：concat串名1串名2新串名例如输入命令concatssttv操作结果是将申ss和申tt连接起来(ss在前，tt在后)形成一个新串，并输出新串(6)求子串：substr串名起始位置子串长度新子串名例如输入

5、命令substrss13t操作结果是将串ss从起始位置1开始的3个字符存入到串t中(7)子串定位：index串名1串名2起始位置例如输入命令indexsst1操作结果是返回串t在串ss从第1个字符后的字符序列中第一次出现的位置(8)退出：quit操作结果是结束演示系统运行的功能［数据描述］(1)定义串的数据类型为指向字符的指针typedefchar^STRING；//定义新的字符串类型，即指向字符的指针(2)在本程序中支持串名操作，因此耑要将各字符串所对应的串名和首地址都存放在一个串头表中：struc

6、tstrheadlistr1STRINGstrhead[100];//字符串首地址STRINGstrname[100];//字符串的串名intcurnum;//当前串头表中串的数目structresult{intnum;int.namctype[6];STRINGstr[6];(3)对于提示符下输入的每一行命令，在进行分析后，需要保留分析的结果(参数最多有6个)//命令行中参数的个数//命令行中各参数的类型//命令行中各参数都以字符串的形式返回注：参数类型以整型表示，如为1,则表示参数为命令动词；如为

7、2,则表示参数为字符串；如为3,则表示参数为整数；如为4,则表示参数为串名。并能将命可以仿照DOS操作系统来进行设计，提供命令行提示符，能输入相应命令令行拆分为不同的儿个部分（类似统计单词个数），再根据编译的结果进行相应的处理。2、文学研宄人员需要统计某篇英文小说中某些词的出现次数。输入一段英文，试写一个文字统计程序，统计该段英文中出现的单词和每个单词出现的次数。三、思考题1、以顺序存储结构表示串，没计算法，求串s中出现的第一个最长重复子串及其位置，并分析算法的时间复杂度。［简要分析1此题算法较多，较

8、好的算法时间复杂度为length^可以考虑从S长（/e邮沁）-1）的字符串入手进行比较，直到找到重复子串为止。2、假设以块链结构作串的存储结构，试编写判别给定串是否具有对称性的算法，并要求算法的时间复杂度为O（!ength（s））。