串基本操作的演示.doc

PAGE 信息科学与技术学院 《数据结构》课程设计报告 题目名称： 串的基本操作演示 专业班级： 学生姓名： 学生学号： 指导教师：  完成日期： 目录 TOC \o 1-3 \u 一、需求分析 1 二、概要设计 2 三、详细设计 2 1、自定义数据类型 2 2、基本操作函数 3 3、主函数 8 四、调试分析 10 五、用户手册 10 六、测试结果 11 七、实验中出现的问题、解决方法和心得体会 11 八、附录 11 PAGE PAGE 1 一、需求分析 【问题描述】? 如果语言没有把串作为一个预先定义好的基本类型对待,又需要用该语言写一个涉及串操作的软件系统时,用户必须自己实现串类型。试实现串类型,并写一个串的基本操作的演示系统。 ?【基本要求】? 在教科书4.2.2节用堆分配存储表示实现HString串类型的最小操作子集的基础上,实现串抽象数据类型的其余基本操作(不使用C语言本身提供的串函数)。参数合法性检查必须严格。? 利用基本操作函数构造以下系统:它是一个命令解释程序,循环往复地处理用户键入的每一条命令,直至终止程序的命令为止。命令定义如下:? (1)赋值。??格式:?A?串标识?回车? 用串标识所表示的串的值建立新串,并显示新串的内部名和串值。例:A?‘Hi!’? (2)判相等。格式:?E?串标识1?串标识2?回车?若两串相等,则显示EQUAL,否则显示UNEQUAL。?(3)联接。?格式:C?串标识1?串标识2?回车? 将两串拼接产生结果串,它的内部名和串值都显示出来。? (4)求长度。格式:L〈串标识?回车? 显示串的长度。? (5)求子串。格式:S?串标识?+数1+数2回车? 如果参数合法,则显示子串的内部名和串值。数不带正负号。 ?(6)子串定位。格式:I?串标识1?串标识2?回车? 显示第二个串在第一个串中首次出现时的起始位置。? (7)串替换。格式:?R?串标识1?串标识2?串标识3?回车? 将第一个串中所有出现的第二个串用第三个串替换,显示结果串的内部名和串值,原串不变。? (8)显示。格式:P?回车 显示所有在系统中被保持的串的内部名和串值的对照表。? (9)删除。格式:D?内部名?回车? 删除该内部名对应的串,即赋值的逆操作。 ?(10)退出。格式:Q?回车? 结束程序的运行。? 在上述命令中,如果一个自变量是串,则应首先建立它。基本操作函数的结果(即函数值)如果是一个串,则应在尚未分配的区域内新辟空间存放。 ?【测试数据】? 自定。但要包括以下几组:? (1)E??‘’?‘’回车,应显示EQUAL。? (2)E?‘abc’?‘abcd’回车,应显示UNEQUAL。?(3)C?‘?‘??‘?‘?回车,应显示。? (4)I?‘a’?‘’?回车,应报告:参数非法。?(5)R?‘aaa’?‘aa’?‘b’回车,应显示ba’? (6)R?‘aaabc’?‘a’?‘aab’回车,应显示’aabaabaabbc’。?(7)R?‘Faaaaaaaa’?‘aaaa’?‘ab’, PAGE PAGE 22 回车,应显示’Fabab’。 二、概要设计 实现串的抽象数据类型和实现其基本操作，程序中将涉及下列抽象数据类型： 1．定义串的基本主结构 ADT String{ 数据对象：D={ai| ai∈charcaterset,i=1,2,…,n,n=0} 数据关系：R1={ai-1,ai|ai-1,ai∈D, i=1,2,…,n} 基本操作： compare(hstring s,hstring t) 初始条件：S和T是已存在的Hstring类型。 操作结果：比较其值，显示结果“UNEQUAL”或“EQUAL”。 length(hstring s) 初始条件：S是已存在的Hstring类型。 操作结果：返回该串的长度。 concat(hstring t,hstring s1,hstring s2) 初始条件：S1和S2是已存在的Hstring类型。 操作结果：由S1和S2联接成新串。 index(hstring s,hstring t,int pos) 初始条件：S和T是已存在的Hstring类型。 操作结果：显示第二个串在第一个串中首次出现的起始位置。 replace(hstring s,hstring t,hstring v)