当前位置:编程学习 > C/C++ >>

c++程序代码

c++程序代码,数据排序的课程设计,有详细注释!谢谢
补充:尽量长一点,差不多有个100行左右吧!
		
答案:你好,这个我以前做过,一下代码,给你做做参考吧,

基本上能满足,你提出的三点要求,有两点点不同:

1.数据时随机产生的(产生1000个随机数),不能手动输入,这个你可以根据需要修改一下;

2.每一次数据排序之后,都可以看到排序的移动,交换次数以及排序的时间,

提示:排序的时间与电脑配置,性能和排序算法的有关

要是电脑配置,性能好的话,时间太快,可能会出现时间为0 的情况

代码:

#define CPP C++ //比较
#define MPP M++ //移动
#define MP2 M+=2
#define MP3 M+=3

#include<iostream.h>
#include <string.h>
#include<stdlib.h>
#include <iomanip.h>
#include <math.h>
#include<time.h>

//存储结构(数组)
const int maxsize=1000; //排序表容量,假设为100..
typedef int datatype; //假设存储元素是整形类型
typedef struct {
datatype key; //关键字域
}rectype; //记录类型
typedef rectype list[maxsize+1]; //排序表类型,0号单元不用;

__int64 C,M; //比较和移动次数

void checkup(list R,int n) { //检验升序排序结果
int i;
for(i=2;i<=n;i++)
if(R[i].key<R[i-1].key) {cout<<"Error!\n";return;}
cout<<"Correct! "<<endl;
}

void checkdown(list R,int n) { //检验降序排序结果
int i;
for(i=2;i<=n;i++)
if(R[i].key>R[i-1].key) {cout<<"Error!\n";return;}
cout<<"Correct! "<<endl;
}

void disp(list R,int n) { //显示数组中的数据
int i;
for(i=1;i<=n;i++) {
cout<<setw(8)<<R[i].key;
if(i%10==0) cout<<endl;
}
cout<<endl;
}

int random1(int num) {return rand();} //0~RAND_MAX=32767

int random2(int num) {//素数模乘同余法,0~M
int A=16807; // 16807,39722040,764261123,630360016 48271?
int M=2147483647; //有符号4字节最大素数,2^31-1
int Q=M/A;
int R=M%A;
static int x=1; //seed(set to 1)
int x1;
x1=A*(x%Q)-R*(x/Q);
if(x1>=0) x=x1;
else x=x1+M;
return x;
}


//直接插入排序(有监视哨)
void InsertSort(list R,int n){
int i,j;
for(i=2;i<=n;i++) { //依次插入R[2],R[],R[]... ....R[]
if(CPP,R[i].key>=R[i-1].key) continue; //R[i]插入时刚好是升序序列无需移动
MPP,R[0]=R[i]; //R[0]作为监视哨
j=i-1;
do{
MPP,R[j+1]=R[j]; j--;
}while(CPP,R[0].key<R[j].key);
MPP,R[j+1]=R[0];
}
}

//希尔排序(无设置监视哨)
void ShellInsert(list R,int n,int h){ //一趟插入排序,h为本趟增量
int i,j,k;
for(i=1;i<=h;i++) { //i为组号
for(j=i+h;j<=n;j+=h){ //每组从第2个记录开始插入
if(CPP,R[j].key>=R[j-h].key) continue; //R[j]大于有序区最后一个记录,则不需要插入
MPP,R[0]=R[j];
k=j-h;
do{ //查找正确的插入位置
MPP,R[k+h]=R[k]; k=k-h; //后移记录,继续向前搜索
}while(CPP,k>0 && R[0].key<R[k].key);
MPP,R[k+h]=R[0];
}
}
}

//希尔排序(调用若干趟插入排序)
void ShellSort(list R,int n,int d[],int t) {//d[]为增量序列,t为增量序列长度
int i;
for(i=0;i<t;i++) //各趟插入排序
ShellInsert(R,n,d[i]);
}

/* 交换排序 */
//上升冒泡排序
void BubbleSort(list R,int n) {
int i,j,flag;
for(i=1;i<n-1;i++){ //做 n-1 趟扫描
flag=0; //直末交换标志
for(j=n;j>=1;j--) //从下往上扫描
if(CPP,R[j].key<R[j-1].key){
flag=1;
MP3,R[0]=R[j]; R[j]=R[j-1]; R[j-1]=R[0];
}
if(!flag) break;
}
}
//下沉冒泡排序
void BubbleSort0(list R,int n) {
int i,j,flag;
for(i=n-1;i>=1;i--){ //做 n-1 趟扫描
flag=0; //直末交换标志
for(j=n;j>=1;j--) //从下往上扫描
if(CPP,R[j].key>R[j-1].key){
flag=1;
MP3,R[0]=R[j]; R[j]=R[j-1]; R[j-1]=R[0];
}
if(!flag) break;
}
}

//快速排序
int Partition(list R,int p,int q) { //被无序区R[p]到R[q]划分,返回划分后基准的位置
int i,j;
i=p;
j=q;
MPP,R[0]=R[i]; //R[0]作辅助量,存放基准,基准取为无序区第一个记录
while(i<j) {
while(CPP,R[j].key>=R[0].key && i<j) j--; //从右向左扫描
if(i<j) { MPP,R[i]=R[j]; i++; } //交换 R[i] 和 R[i]
while(CPP,R[i].key<=R[0].key && i<j) i++; //从左向右扫描
if(i<j) { MPP,R[j]=R[i]; j--; } //交换 R[i] 和 R[i]
}
MPP,R[i]=R[0]; //将基准移到最后的正确位置
return i;
}
void QuickSort(list R,int s,int t) { //对R[s]到R[t]快速排序
int i;
if(s>=t) return; //只有一个记录或无记录时无需排序
i=Partition(R,s,t); //对R[s]到R[t]做划分
QuickSort(R,s,i-1); //递归处理左区间
QuickSort(R,i+1,t); //递归处理右区间
}

//直接选择排序
void SelectSort(list R,int n){
int i,j,k;
for(i=1;i<=n-1;i++){ //n-1趟排序
k=i;
for(j=i+1;j<=n;j++) //在当前无序区中找键值最小的记录R[k]
if(CPP,R[j].key<R[k].key) k=j;
if(k!=i) { MP3,R[0]=R[i]; R[i]=R[k]; R[k]=R[0]; }//交换R[k]和R[i]的值,R[0]坐中间辅助量
}
}

//堆排序
void Sift(list R,int p,int q){//堆范围为R[p]~R[q],调整R[p]为堆,非递归算法
int j;
MPP,R[0]=R[p]; //R[0]作辅助量
j=2*p; //j指向R[p]的左孩子
while(j<=q)
{
if(CPP,j<q && R[j].key<R[j+1].key) j++; //j指向R[p]的右孩子
if(CPP,R[0].key>R[j].key) break; //结点键值大于孩子结点,已经是堆,调整结束!
MPP,R[p]=R[j]; //将R[j]换到双亲位置上
p=j; //修改当前被调整结点
j=2*p; //j指向R[p]的左孩子
}
MPP,R[p]=R[0]; //原根结点放入正确位置
}

void HeapSort(list R,int n)
{
int i;
for(i=n/2;i>=1;i--) Sift(R,i,n); //建初始堆
for(i=n;i>=2;i--){ //进行n-1趟堆排序
MP3,R[0]=R[1];
R[1]=R[i];
R[i]=R[0]; //R[1]到R[i-1]重建成新堆
Sift(R,1,i-1);
}
}

/* 归并排序 */\

//两个子表合并
void Merge(list R,list R1,int low,int mid,int high){//合并R的两个子表,结果在R1中
int i,j,k;
i=low; j=mid+1; k=low;
while(i<=mid && j<=high)
if(CPP,R[i].key<=R[j].key) MPP,R1[k++]=R[i++]; //取小者复制
else MPP,R1[k++]=R[j++];
while(i<=mid) MPP,R1[k++]=R[i++]; //复制左子表的剩余记录
while(j<=high) MPP,R1[k++]=R[j++]; //复制右子表的剩余记录
}

//一趟归并
void MergePass(list R,list R1,int n,int len){ //对R做一趟归并,结果在R1中
int i=1,j; //i指向第一对子表的起始点
while(i+2*len-1<=n){ //归并长度为len的两个子表
Merge(R,R1,i,i+len-1,i+2*len-1);
i=i+2*len; //i指向下一子表起始点
}
if(i+len-1<=n) //剩下两个子表,其中一个长度小于 len
Merge(R,R1,i,i+len-1,n);
else for(j=i;j<=n;j++) MPP,R1[j]=R[j];
}

//二路归并
void MergeSort(list R,list R1,int n) { //对R二路归并排序,结果在R中(非递归算法)
int len;
len=1;
while(len<n) {
MergePass(R,R1,n,len); len=len*2; //一趟归并,结果在R1中
MergePass(R1,R,n,len); len=len*2; //再次归并结果在R中
}
}

void main()
{
rectype *R,*R1,*S; //R1用于归并排序的辅助存储,S用于保存初始排序数据
R=new list; if(R==NULL) { cout<<"数组为空!\n";exit(-1); }
R1=new list; if(R1==NULL) { cout<<"数组为空!\n";exit(-1); }
S=new list; if(S==NULL) { cout<<"数组为空!\n";exit(-1); }
int i,n=maxsize;
int choice;
clock_t t1,t2;
for(i=1;i<=n;i++)
S[i].key=random1(n); //生成0-n之间的随机数
disp(S,n); //输出0到n之间的随机数
do {
C=M=0;
for(i=1;i<=n;i++) R[i].key=S[i].key; //取出初始数据用于排序

cout<<"请选择排序方法(0: 退出): \n\
1:直接插入(带监视哨) \n\<

上一个:c++ include头文件
下一个:c++如何修改注册表?

CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,