| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 590 人关注过本帖
标题:[求助]为什么测试的数据不能超过1000
只看楼主 加入收藏
wshingdc
Rank: 1
等 级:新手上路
帖 子:40
专家分:0
注 册:2006-3-30
收藏
 问题点数:0 回复次数:7 
[求助]为什么测试的数据不能超过1000

这是别人编的程序。。。。
是产生随机数,然后比较各种排序算法的时间。。。
要求是产生30000可是。。这个不能超过1000
望大虾指点一下

#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>
#define LS(a,b) ((a)<(b))
#define LL(a,b) ((a)>(b))
#define MAXSIZE 1000
typedef int KeyType;
typedef struct
{
int key;
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}SqList;
typedef SqList HeapType;
int compare=0;
int change=0;
int Create_Sq(SqList &L)
{
int i,k;
cout<<"请输入产生随机数的个数:";
cin>>k;
L.length=k;
for(i=1;i<=k;++i)
{

L.r[i].key=rand();
}
return 1;
}
void Bubble_sort(SqList &L)
{//冒泡排序
int i,j,l,k=L.length;
for(i=1;i<=L.length-1;++i)
{
for(j=1;j<=k-1;++j)
{
++compare;
if(LL(L.r[j].key,L.r[j+1].key))
{
l=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=l;
++change;
}
}
--k;
}
cout<<endl<<"-----冒泡排序后的序列-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;
cout<<endl;
cout<<"冒泡排序的比较次数:";
cout<<compare<<endl;
cout<<"冒泡排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
void InsertSort(SqList &L)
{//直接插入排序
int i,j;
cout<<endl;
for(i=2;i<=L.length;++i)
if(LS(L.r[i].key,L.r[i-1].key))
{
++compare;
++change;
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
for(j=i-2;LS(L.r[0].key,L.r[j].key);--j)
{
++compare;
L.r[j+1]=L.r[j];
}
L.r[j+1]=L.r[0];
}
cout<<"-----直接插入排序后的序列-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;
cout<<endl;
cout<<"直接插入排序的比较次数:";
cout<<compare<<endl;
cout<<"直接插入排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
void SelectSort(SqList &L)
{//简单选择排序
int l,i,j;
cout<<endl;
for(i=1;i<L.length;++i)
{
L.r[0]=L.r[i];
j=i+1;
l=i;
for(j;j<=L.length;++j)
{
++compare;
if(LL(L.r[0].key,L.r[j].key))
{
l=j;
L.r[0]=L.r[j];
}
}
if(l!=i)
{
++change;
L.r[l]=L.r[i];
L.r[i]=L.r[0];
}
}
cout<<"-----简单选择排序后的序列-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;
cout<<endl;
cout<<"简单选择排序的比较次数:";
cout<<compare<<endl;
cout<<"简单选择排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
int Partition(SqList &L,int low,int high)
{
int pivotkey;
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(low<high)
{
while(low<high&&L.r[high].key>=pivotkey)
{
++compare;
--high;
}
++change;
L.r[low]=L.r[high];
while(low<high&&L.r[low].key<=pivotkey)
{
++compare;
++low;
}
++change;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void QSort(SqList &L,int low,int high)
{//递归形式的快速排序算法
int pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L)
{
int i;
QSort(L,1,L.length);
cout<<"-----快速排序后的序列为-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;
cout<<endl;
cout<<"快速排序的比较次数:";
cout<<compare<<endl;
cout<<"快速排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
void ShellInsert(SqList &L,int dk)
{//希尔排序
int i;
int j;
for(i=dk+1;i<=L.length;++i)
if(LS(L.r[i].key,L.r[i-dk].key))
{
++compare;
L.r[0]=L.r[i];
for(j=i-dk;j>0&&LS(L.r[0].key,L.r[j].key);j-=dk)
{
++compare;
++change;
L.r[j+dk]=L.r[j];
}
L.r[j+dk]=L.r[0];
}
}
void ShellSort(SqList &L,int dlta[])
{//希尔排序
int k,j=L.length/2,t=0;
while(j>=0)
{
++t;
j-=2;
}
j=L.length/2;
for(k=0;k<t;++k)
{//计算每次的增量值
if(j==0)
j=1;//定义最后一趟排序的增量
dlta[k]=j;
j-=2;
}
for(k=0;k<t;++k)
ShellInsert(L,dlta[k]);
cout<<"-----希尔排序后的序列为-----"<<endl;
for(k=1;k<=L.length;k++)
cout<<" "<<L.r[k].key;
cout<<endl;
cout<<"希尔排序的比较次数:";
cout<<compare<<endl;
cout<<"希尔排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
void HeapAdjust(HeapType &H,int s,int m)
{//堆排序
int j;
RedType rc;
rc=H.r[s];
for(j=2*s;j<=m;j*=2)
{
if(j<m&&LS(H.r[j].key,H.r[j+1].key))
{
++compare;
++j;
}
if(!LS(rc.key,H.r[j].key))
{
++compare;
break;
}
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc;
}
void HeapSort(HeapType &H)
{
int i;
for(i=H.length/2;i>0;--i)
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{
++change;
H.r[0]=H.r[1];
H.r[1]=H.r[i];
H.r[i]=H.r[0];
HeapAdjust(H,1,i-1);
}
cout<<"-----堆排序后的序列为-----"<<endl;
for(i=1;i<=H.length;i++)
cout<<" "<<H.r[i].key;
cout<<endl;
cout<<"堆排序的比较次数:";
cout<<compare<<endl;
cout<<"堆排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}

void main()
{
int i;
int dlta[MAXSIZE];
SqList L;
Create_Sq(L);

cout<<"-----待排序序列为-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;



//冒泡排v序
SqList L1=L;
Bubble_sort(L1);
//直接插入排序
SqList L2=L;
InsertSort(L2);
//简单选择排序
SqList L3=L;
SelectSort(L3);
//快速排序
SqList L4=L;
QuickSort(L4);
//希尔排序
SqList L5=L;
ShellSort(L5,dlta);
//堆排序
SqList L6=L;
HeapSort(L6);
}

[此贴子已经被作者于2006-6-22 12:59:29编辑过]

搜索更多相关主题的帖子: 数据 
2006-06-22 12:23
aogun
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:638
专家分:0
注 册:2006-4-5
收藏
得分:0 
这个程序中最大个数是通过MAXSIZE宏来调节的,你可以修改MAXSIZE使得最大个数可以超过1000

世界上总共有 10 种人,一种懂得什么是二进制 ,一种不懂。
2006-06-22 13:10
wshingdc
Rank: 1
等 级:新手上路
帖 子:40
专家分:0
注 册:2006-3-30
收藏
得分:0 

我把MAXSIZE改过更大的数
可是一运行还是出错 好象是不能分配内存似的

是不是数组的大小有限制啊

[此贴子已经被作者于2006-6-22 14:01:57编辑过]


什么都不能加啊!!
2006-06-22 13:58
aogun
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:638
专家分:0
注 册:2006-4-5
收藏
得分:0 

不能太大,不过你说的30000还是可以的
最好将程序实现用的数组改成指针,用户输入多少就分配多少内存,这样也不用MAXSIZE来配置了,而且没有栈的限制

[此贴子已经被作者于2006-6-22 14:18:50编辑过]


世界上总共有 10 种人,一种懂得什么是二进制 ,一种不懂。
2006-06-22 14:17
wshingdc
Rank: 1
等 级:新手上路
帖 子:40
专家分:0
注 册:2006-3-30
收藏
得分:0 

恩 用动态分配是好
可惜的是,我改了几次都失败了。。。
aogun 你可以把程序,运行一下
把 MAXSIZE 改成30000
试试 一定是运行的时候出错。。。
编译连接都没问题


什么都不能加啊!!
2006-06-22 17:03
aogun
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:638
专家分:0
注 册:2006-4-5
收藏
得分:0 

动态分配不难改的,我试着改了下,就两个地方,试了下应该可以运行,不过没有释放内存,你再自己改改吧:
[CODE]#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define LS(a,b) ((a)<(b))
#define LL(a,b) ((a)>(b))
#define MAXSIZE 300000
typedef int KeyType;
typedef struct
{
int key;
}RedType;
typedef struct
{
RedType *r;
int length;
}SqList;
typedef SqList HeapType;
int compare=0;
int change=0;
int Create_Sq(SqList &L)
{
int i,k;
cout<<"请输入产生随机数的个数:";
cin>>k;
if (k <= 0 || k > MAXSIZE)
{
cout<<"超过程序最大限制"<<endl;
return 0;
}
L.r = new RedType[k];
L.length=k;
for(i=1;i<=k;++i)
{

L.r[i].key=rand();
}
return k;
}
void Bubble_sort(SqList &L)
{//冒泡排序
int i,j,l,k=L.length;
for(i=1;i<=L.length-1;++i)
{
for(j=1;j<=k-1;++j)
{
++compare;
if(LL(L.r[j].key,L.r[j+1].key))
{
l=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=l;
++change;
}
}
--k;
}
cout<<endl<<"-----冒泡排序后的序列-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;
cout<<endl;
cout<<"冒泡排序的比较次数:";
cout<<compare<<endl;
cout<<"冒泡排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
void InsertSort(SqList &L)
{//直接插入排序
int i,j;
cout<<endl;
for(i=2;i<=L.length;++i)
if(LS(L.r[i].key,L.r[i-1].key))
{
++compare;
++change;
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
for(j=i-2;LS(L.r[0].key,L.r[j].key);--j)
{
++compare;
L.r[j+1]=L.r[j];
}
L.r[j+1]=L.r[0];
}
cout<<"-----直接插入排序后的序列-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;
cout<<endl;
cout<<"直接插入排序的比较次数:";
cout<<compare<<endl;
cout<<"直接插入排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
void SelectSort(SqList &L)
{//简单选择排序
int l,i,j;
cout<<endl;
for(i=1;i<L.length;++i)
{
L.r[0]=L.r[i];
j=i+1;
l=i;
for(j;j<=L.length;++j)
{
++compare;
if(LL(L.r[0].key,L.r[j].key))
{
l=j;
L.r[0]=L.r[j];
}
}
if(l!=i)
{
++change;
L.r[l]=L.r[i];
L.r[i]=L.r[0];
}
}
cout<<"-----简单选择排序后的序列-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;
cout<<endl;
cout<<"简单选择排序的比较次数:";
cout<<compare<<endl;
cout<<"简单选择排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
int Partition(SqList &L,int low,int high)
{
int pivotkey;
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(low<high)
{
while(low<high&&L.r[high].key>=pivotkey)
{
++compare;
--high;
}
++change;
L.r[low]=L.r[high];
while(low<high&&L.r[low].key<=pivotkey)
{
++compare;
++low;
}
++change;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void QSort(SqList &L,int low,int high)
{//递归形式的快速排序算法
int pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L)
{
int i;
QSort(L,1,L.length);
cout<<"-----快速排序后的序列为-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;
cout<<endl;
cout<<"快速排序的比较次数:";
cout<<compare<<endl;
cout<<"快速排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
void ShellInsert(SqList &L,int dk)
{//希尔排序
int i;
int j;
for(i=dk+1;i<=L.length;++i)
if(LS(L.r[i].key,L.r[i-dk].key))
{
++compare;
L.r[0]=L.r[i];
for(j=i-dk;j>0&&LS(L.r[0].key,L.r[j].key);j-=dk)
{
++compare;
++change;
L.r[j+dk]=L.r[j];
}
L.r[j+dk]=L.r[0];
}
}
void ShellSort(SqList &L,int dlta[])
{//希尔排序
int k,j=L.length/2,t=0;
while(j>=0)
{
++t;
j-=2;
}
j=L.length/2;
for(k=0;k<t;++k)
{//计算每次的增量值
if(j==0)
j=1;//定义最后一趟排序的增量
dlta[k]=j;
j-=2;
}
for(k=0;k<t;++k)
ShellInsert(L,dlta[k]);
cout<<"-----希尔排序后的序列为-----"<<endl;
for(k=1;k<=L.length;k++)
cout<<" "<<L.r[k].key;
cout<<endl;
cout<<"希尔排序的比较次数:";
cout<<compare<<endl;
cout<<"希尔排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
void HeapAdjust(HeapType &H,int s,int m)
{//堆排序
int j;
RedType rc;
rc=H.r[s];
for(j=2*s;j<=m;j*=2)
{
if(j<m&&LS(H.r[j].key,H.r[j+1].key))
{
++compare;
++j;
}
if(!LS(rc.key,H.r[j].key))
{
++compare;
break;
}
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc;
}
void HeapSort(HeapType &H)
{
int i;
for(i=H.length/2;i>0;--i)
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{
++change;
H.r[0]=H.r[1];
H.r[1]=H.r[i];
H.r[i]=H.r[0];
HeapAdjust(H,1,i-1);
}
cout<<"-----堆排序后的序列为-----"<<endl;
for(i=1;i<=H.length;i++)
cout<<" "<<H.r[i].key;
cout<<endl;
cout<<"堆排序的比较次数:";
cout<<compare<<endl;
cout<<"堆排序的交换次数:";
cout<<change<<endl;
compare=0;
change=0;
}
void main()
{
int i;
int *dlta = NULL;
SqList L;
memset(&L, 0, sizeof(L));
int num = Create_Sq(L);
if (num == 0)
{
return;
}
dlta = new int[num];
//这里最好判断是否申请成功
cout<<"-----待排序序列为-----"<<endl;
for(i=1;i<=L.length;i++)
cout<<" "<<L.r[i].key;


//冒泡排v序
SqList L1=L;
Bubble_sort(L1);
//直接插入排序
SqList L2=L;
InsertSort(L2);
//简单选择排序
SqList L3=L;
SelectSort(L3);
//快速排序
SqList L4=L;
QuickSort(L4);
//希尔排序
SqList L5=L;
ShellSort(L5,dlta);
//堆排序
SqList L6=L;
HeapSort(L6);
}[/CODE]


世界上总共有 10 种人,一种懂得什么是二进制 ,一种不懂。
2006-06-22 17:33
woodhead
Rank: 3Rank: 3
等 级:新手上路
威 望:9
帖 子:1124
专家分:0
注 册:2005-7-18
收藏
得分:0 
楼主的程序可以运行,有的排序方法慢,30000的等一会,象卡住了一样,还是快速和堆排序快。

2006-06-22 18:37
wshingdc
Rank: 1
等 级:新手上路
帖 子:40
专家分:0
注 册:2006-3-30
收藏
得分:0 
谢谢 斑竹 偶搞好了
万分感谢

什么都不能加啊!!
2006-06-22 19:39
快速回复:[求助]为什么测试的数据不能超过1000
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026794 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved