南京邮电大学通达学院
算法与数据结构设计
(2013 / 20## 学年 第 二 学期)
题 目:指定类型数据随机生成方法
专 业 计算机科学与技术(软件工程)
学 生 姓 名 吴昊
班 级 学 号 12003416
指 导 教 师 陈 蕾 _
指 导 单 位 计算机学院计算机科学与技术系 _
日 期 2014.4.28- 5.4 _
指定类型数据随机生成方法
一、课题内容和要求
1.内容:编程实现特定类型(如Int、Double、String、Date型等)数据随机生成方法;同时能使得生成数据满足适当的约束,如数据范围、字符串长度、一定包含或不包含某个特定数据等。
2.理解:及调用srand随机函数,生成整形数字,再根据题目的要求进行强制类型转换。在让生成不同的数据满足适当的约束条件即不可能存在的值或一定存在的值,在不同类型的数据也可使他们满足不同的条件,输出各种各样的结果。
3.开发平台vc6.0,编程语言为c++。
二、数据结构说明
数组和二维数组,其中二维数组用于存储字符串。
三、算法设计
流程图:
图1 Random类
图2 函数执行流程图
图3 randomdouble类生成
用面向对象的方法设计了3个不同的类,其中2个类中所用的函数基本相同如下:
limit()实现有范围限制的数据生成;
unlimit()实现无范围限制的数据生成;
special()实现一定产生某特定数据的功能;
special()实现一定不产生某特定数据的功能;
Print() 输出随机数。
Random类中的所用的函数基本功能如下:
Data(int y=0,int m=0,int d=0) 实现年月日的随机值,和相应的规范;
int Getyear();int Getmonth();int Getday();返回年月日;
void Printdata() 打印出年-月-日。
Randomdouble()类生成double类型数据
基本思想是调用不同类型的函数,对他们随机赋值,然后给他们约束条件或不给约束条件调用limit()或unlimit的,让他们输出含有一个或一定不含有某个特定值调用special()或unspecial(),然后函数进行输出。Random类中可以调用Data或randomdouble随机函数然后进行输出。
各个类中的成员变量和成员函数
Random类:
class Random
{
private:
int year,month,day;
public:
Data(int y=0,int m=0,int d=0);
~Random();
int Getyear();
int Getmonth();
int Getday();
double Randomdouble();
void Printdata();
void menu();
};
Int类:
class Int
{
public:
void RandomInt();
void limit(); //产生有范围限制的随机数
void unlimit(); //产生无范围限制的随机数
void special(); //实现一定包含某数
void special1(); //实现一定不包含某数
void Print();
private:
char q,spe,unspe; //spe指的是特定的数据,unspec不包含某个特定的数
int *a;
int n,min,max;
};
String类
class String
{
public:
void RandomStr();
void limit();
void unlimit();
void special();
void special1();
void Print();
private:
int n,length;
char **p; //存放生成的n个字符串
char fwei,tedg1,tedg2;
};
void String::RandomStr()
{
cout<<"您选择的是string型!\n";
cout<<"请选择数据生成要求!\n";
cout<<"要生成多少个字符串: ";
cin>>n;
cout<<"1.字符串是否有长度限制(Y/N) ";
cin>>fwei;
cout<<"2.是否包含某特定字符串(Y/N) ";
cin>>tedg1;
cout<<"3.是否不包含某特定字符串(Y/N) ";
cin>>tedg2;
if(fwei=='Y') limit();
else unlimit();
if(tedg1=='Y') special();
if(tedg2=='Y') special1();
}
四、详细设计
源程序:
#include<iostream>
#include<stdlib.h>
#include<string>
#include<time.h>
using namespace std;
int m;
class Random
{
private:
int year,month,day;
public:
Data(int y=0,int m=0,int d=0);
~Random();
int Getyear();
int Getmonth();
int Getday();
double Randomdouble();
void Printdata();
void menu();
};
class Int
{
public:
void RandomInt();
void limit(); //产生有范围限制的随机数
void unlimit(); //产生无范围限制的随机数
void special(); //实现一定包含某数
void special1(); //实现一定不包含某数
void Print();
private:
char q,spe,unspe; //spe指的是特定的数据,unspec不包含某个特定的数
int *a;
int n,min,max;
};
void Int::RandomInt()
{
cout<<" **********选择的是int型!*********"<<endl;
cout<<"请选择数据生成要求!\n";
cout<<"1.数据是否有范围(Y/N) ";
cin>>q;
cout<<"2.是否包含某特定数据(Y/N) ";
cin>>spe;
cout<<"3.是否不包含某特定数据(Y/N) ";
cin>>unspe;
if(q=='Y') limit();
else unlimit();
if(spe=='Y') special();
if(unspe=='Y') special1();
}
void Int::limit()
{
cout<<" 请输入数据的范围!\n";
cout<<" 要生成多少个数 ";
cin>>n;
do{
cout<<" 输入数据的下界 ";
cin>>min;
cout<<" 输入数据的上界 ";
cin>>max;
if(max-min+1<n)
cout<<"范围的随机数少于需要输出的个数!\n"<<"请重新输入!\n"; //随机数的个数应该大于范围内的数
}while(max-min+1<n);
srand(time(NULL));
a=new int [n];
int length=max-min+1;
int *b=new int [length];
for(int i=0;i<length;i++)
b[i]=min+i; //将min到max之间所有值赋值给b[i]
for(i=1;i<=n;i++)
{
int l;
l=rand()%length+1;
a[i-1]=b[l-1]; //随机产生b[l-1]赋值给a[i-1]
for(int j=l;j<length;j++) //减少计算量
b[j-1]=b[j]; //删去已产生的数b[l-1]
length--;
} //保证随机数在min到max之间
}
void Int::unlimit()
{
cout<<"要生成多少个数 ";
cin>>n;
srand(time(NULL));
a=new int [n];
for(int i=0;i<n;i++)
a[i]=rand();
}
void Int::special() //包含某个数
{
cout<<"要包含的数是: ";
int x,i=0;
cin>>x;
while(x<min||x>max)
{
cout<<"数据不在范围之内,请重新输入! ";
cin>>x;
}
while(i<n)
{
if(a[i]==x) break; //原数据中有x,直接跳出
else i++;
}
if(i==n) a[i-1]=x; //如果没有,最后一个值赋为x
}
void Int::special1()
{
cout<<"不要包含的数是: ";
int x,i=0;
cin>>x;
while(i<n) //检查所有的数据
{
if(a[i]==x)
{
if(q=='Y') a[i]=(x+1)%(max-min)+min; //如果有范围限制,产生范围内的值
else a[i]=x+1;
}
else i++;
}
}
void Int::Print()
{
cout<<"\n产生的随机数是:\n";
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl<<endl;
}
double Random::Randomdouble()
{ double q;
int t =rand();
int m=rand();
q=(double)t/(double)m;
cout<<q<<endl;
return 0;
}
Random::Data(int y,int m,int d)
{
srand((unsigned)time(NULL));
y=rand()%2500+1;
m=rand()%12+1;
if(m==2)
d=rand()%28+1;
if(m%2!=0)
d=rand()%31+1;
else
d=rand()%30+1;
if(year % 4 == 0 &&year % 100 != 0 || year % 400 == 0 )
{
if(month == 2)
{
day = rand() % 28 + 1;
}
}
year=y;
month=m;
day=d;
}
class String
{
public:
void RandomStr();
void limit();
void unlimit();
void special();
void special1();
void Print();
private:
int n,length;
char **p; //存放生成的n个字符串
char fwei,tedg1,tedg2;
};
void String::RandomStr()
{
cout<<"您选择的是string型!\n";
cout<<"请选择数据生成要求!\n";
cout<<"要生成多少个字符串: ";
cin>>n;
cout<<"1.字符串是否有长度限制(Y/N) ";
cin>>fwei;
cout<<"2.是否包含某特定字符串(Y/N) ";
cin>>tedg1;
cout<<"3.是否不包含某特定字符串(Y/N) ";
cin>>tedg2;
if(fwei=='Y') limit();
else unlimit();
if(tedg1=='Y') special();
if(tedg2=='Y') special1();
}
void String::limit()
{
cout<<"字符串的最大长度为: ";
cin>>length;
p=new char*[n];
srand(time(NULL));
for(int i=0;i<n;i++)
{
int m=rand()%length+1;
p[i]=new char [m+1];
for(int j=0;j<m;j++)
{
p[i][j]=rand()%74+48;
}
p[i][j]='\0';
}
}
void String::unlimit()
{
p=new char*[n];
srand(time(NULL));
for(int i=0;i<n;i++)
{
int m=rand()%10+1;
p[i]=new char [m+1];
for(int j=0;j<m;j++)
p[i][j]=rand()%74+48;
p[i][j]='\0';
}
}
void String::special()
{
char *x;
if(fwei=='Y') x=new char [length];
else
{
cout<<"要包含的字符串的长度为: ";
int l;
cin>>l;
x=new char [l];
}
cout<<"要包含的字符串是: ";
cin>>x;
int i=0;
while(i<n)
{
if(!strcmp(p[i],x)) break;
else i++;
}
if(i==n) p[i-1]=x;
}
void String::special1()
{
char *x;
cout<<"不包含的字符串的长度为: ";
int l;
cin>>l;
x=new char [l];
cout<<"不包含的字符串是: ";
cin>>x;
int i=0;
while(i<n)
{
if(!strcmp(p[i],x)) strncat(p[i],x,1);
else i++;
}
}
void String::Print()
{
cout<<"\n产生的字符串是:\n";
for(int i=0;i<n;i++)
cout<<p[i]<<endl;
cout<<endl;
}
Random::~Random()
{
cout<<"deconstructing..."<<endl;
}
int Random::Getyear()
{
return year;
}
int Random::Getmonth()
{
return month;
}
int Random::Getday()
{
return day;
}
void Random::Printdata()
{
cout<<Getyear()<<"-"<<Getmonth()<<"-"<<Getday()<<endl;
}
void Random::menu()
{
cout<<" **************************************"<<endl;
cout<<" >>>>>>>>>> 1.调用Data型 <<<<<<<<<<"<<endl;
cout<<" >>>>>>>>>> 2.调用 Int型 <<<<<<<<<<"<<endl;
cout<<" >>>>>>>>>> 3.调用double型 <<<<<<<<<<"<<endl;
cout<<" >>>>>>>>>> 4.调用str类 <<<<<<<<<<"<<endl;
cout<<" **************************************"<<endl;
cin>>m;
}
int main()
{ system("color 0A");
Random t;
Int p;
//Double q;
String s;
while(1){
t.menu();
switch(m)
{ case 1:
cout<<" *****************输出日期****************"<<endl;
t.Data (2014,2,3);
t.Printdata();break;
case 2 :
// cout<<" *********输出小余1000的整数**********"<<endl;
p.RandomInt();
p.Print();
break;
case 3 :
cout<<" *****输出double数*****"<<endl;
t.Randomdouble();
//q.Print();
break;
case 4 :
cout<<" **输出字符串**"<<endl;
s.RandomStr();
s.Print();
break;
}
}
return 0;
}
五、测试数据及其结果分析
1.Int型测试结果
图4 整型的实现
2.Double型测试结果
图5 双精度型实现
3.Data型测试结
图6 日期类实现
4.String型测试结果
图7 字符串类的实现
该算法调用时都是直接调用随机函数,产生一个调用一个且随机选取,时间复杂度为O(n)。但在由于再设计上为了避免数字的重复空间比较浪费。
六、调试过程中的问题
在进行Randomdouble调用是始终产生一个只有含有两位小数的数,把随机生成的两个整形数进行强制类型转换,然后在相除即可获得不一样小数位的double数。
在主菜单界面上,选择过一个类型数的生成程序就自动退出了,在主函数中加一个while(1)就让该主菜单一直执行下去。而不中断。
在调用整型字符串型函数是没有打印出结果,由于输出函数没有调用。
在主函数中调用不同类的函数时只定义了一个类的对象,当调用不通类中的函数也用该对象,结果报错。处理办法对于不同的类要定义不同的对象来实现函数的调用
算法改进的设想,程序中有许多重复的函数,可以设计一个模板类,或利用函数的抽象类,友元函数来进行程序的改进。由于是随机数的生成对于重复的产生可以不去考虑,来减少它的空间复杂度,及执行的时间效率。
七、课程设计总结
在程序中,调试问题的时候不会调试程序,从头找到尾部浪费了大量的时间,跟同学学习了断点调试,提高了解决问题找到错误并改正的效率,在分析设计是有时看不懂题目让我们对于所做的内容有哪些而不知到如何下手。问了老师得以解决,在编写程序的时候,有时还没做就感觉程序太难而不敢下手去做,先把函数的类体实现,把主要的函数写出然后逐步添加改错。
课程设计过程的收获和感受,知道了做事一定要有耐心,对于动手能了有了进一步的人加强,编程的能力也有了一定相应的提高,对于c++知识以及数据结构也有了一定的复习,但对于学习了随机调用函数的功能实现,学会了如何快速解决程序程序中的问题采用断点调试,课程设计目的数据结构是计算机科学的基础理论知识,也是软件设计的技术基础。本课程设计的性质是检验理论科学系的效果以及综合运用的能力,目的是训练我们进行复杂程序设计的技能和培养良好的程序设计习惯。本课程设计的任务是要求我们使用C或C++语言编程,解决具有一定规模的、具有实际意义的应用题,实现理论课所要求的数据组织、存储、处理的基本方法。
通过这次课程设计巩固和加深了我对数据结构的理解,提高自己综合运用本课程所学知识的能力。培养了我查阅手册及文献资料的能力以及独立思考、分析问题、解决问题的能力。。根据我在课程设计中遇到得问题,我将在以后的学习过程中认真上好专业实验课,多在实践中锻炼自己,在做设计的时候要有信心,有耐心,切勿浮躁。认真的学习课本知识,掌握课本中的知识点,并在此基础上学会灵活运用。在课余时间里多写程序,熟练掌握在调试程序的过程中所遇到的常见错误,以便能节省调试程序的时间。
经过一个星期的上机实践学习,使我对C++语言有了更进一步的认识和了解,要想学好它要重在实践,要通过不断的上机操作才能更好地学习它。通过实践的学习,我明白了学好计算机要重视实践操作,不仅仅是学习C++语言,还是其它的语言,以及其它的计算机方面的知识都要重在实践,因此,我以后会更加注视实践操作,使自己更好地学好计算机的相关知识。