根据关键字进行字符串拷贝

1、数据结构上机实验报告 题目：根据关键字进行字符串拷贝 学生姓名 学生学号 学院名称 计算机学院 专 业 计算机科学与技术 时 间 2014.11.9 目 录 第一章 需求分析11.1 原题表述11.2 问题解决方案1 第二章 概要设计22.1 抽象数据类型22.2 主要算法分析2 第三章 详细设计33.1 程序代码3 第四章 调试分析64.1 出现的问题及解决方法6 第五章 测试分析75.1 测试样例7 I计算机学院2013级数据结构上机实验报告第1章 需求分析1.1 原题表述给出一个字符串A和一个字符串B，请你计算字符串B的所有旋转形式在字符串A中的出现总次数。说明：如果将字符串B描述成B1

2、B2.Bm的形式（m是B的长度），那么B1B2.Bm-1Bm，B2B3.BmB1，.，BmB1.Bm-2Bm-1就是字符串B的所有旋转形式。输入格式：输入包含多组测试数据。每组输入为两行，第一行输入字符串A，第二行输入字符串B。A的长度不超过1000，B的长度不超过100，所有字符串仅包含小写字母。输出：对于每组输入，输出字符串B的所有旋转形式在字符串A中的出现总次数。1.2 问题解决方案1. 依次输入字符串A和B。2. 建立一个函数Count（A,B）用于计算B在A中的次数。3. 建立一个函数XuanZhuan（B）产生字符串B的旋转形式。4. 用一个二维数组存储字符串B的旋转形式（相同的旋

3、转形式只存一次）。5. 计算B的旋转形式在A中出现的总次数。6. 输出总次数。 第二章 概要设计2.1 抽象数据类型ADT String 数据对象：D = ai | ai CharacterSet,i = 1,2,3,n, n >= 0数据关系：S = < ai - 1 ,ai > | ai -1 ,ai D, i = 2,3,4,，n基本操作：CreatString（&S）操作结果：建立一个字符串Count（A，B）初始条件：已建立字符串A，B操作结果：输出B在A中出现的次数XuanZhuan（&S)初始条件：已建立字符串S操作结果：将S的头移至尾SunCo

4、unt(A,B)初始条件：已建立字符串A,B操作结果：输出B的所有旋转形式在A中出现的次数2.2 主要算法分析算法CreatString(S) 的时间复杂度为O(n2)；算法Count(A,B) 的时间复杂度为 O(n2)；算法XuanZhuan（S）的时间复杂度为O(n2)；算法 IsSame（T,S,n）的时间复杂度为O（n2)；算法 SumCount（A,B）的时间复杂度为O（n2）；第三章 详细设计3.1 程序代码#include<stdio.h>#define MAXSIZE 1111typedef struct char dataMAXSIZE;int length;S

5、qString;typedef char SStringMAXSIZEMAXSIZE;/建立一个字符串 void CreatString(SqString &S)int i = 0;char ch;while(ch = getchar() != 'n')S.datai = ch;i+;S.length = i;/求字符串B在A中出现的次数 int Count(SqString A, SqString B)int lenA = A.length;int lenB = B.length;int count = 0;int k = 0, i = 0, j = 0;while(

6、k < lenA)i = k;while(i < lenA && j < lenB)if(A.datai = B.dataj)+i;+j;elsei = i - j + 1;j = 0;if(j >= lenB) count+;k = i - j + 1;j = 0;return count; /字符串S的旋转形式，将S的头移至尾 void XuanZhuan(SqString &S)int len = S.length;char temp = S.data0;for(int i = 0; i < len; i+)S.datai = S.d

7、atai+1;S.datalen-1 = temp; /判断字符串S旋转形式的重复bool IsSame(SString T, SqString S, int n)int len = S.length;bool same = false;for(int i = 0; i < n; i+)same = true;for(int j = 0; j < len; j+)if(Tij != S.dataj)same = false;break;if(same) return true;return false; /判断字符串B的所有旋转形式在A中出现次数 void SumCount(SqS

8、tring A, SqString &B)int sum = 0, len = B.length;SString T;sum += Count(A, B);for(int i = 0; i < len; i+)T0i = B.datai;for(int i = 1; i < len; i+)XuanZhuan(B);for(int j = 0; j < len; j+)Tij = B.dataj;/将字符串B的旋转形式存入二维数组T中 if(IsSame(T, B, i) continue;/判断此串是否与之前的串相同， else sum += Count(A, B);printf("%dn", sum); int main()while(1)SqString A, B;CreatString(A);CreatString(B);SumCount(A, B);return 0;第四章