求救啊!`````各位高手虾米帮下
数据库作业 要用TC编写!`````` 不是C语言 或者哪个大哥能帮我把VC代码变TC 我有第一题的/***********************************************
*author:JTF 2008.6.4 *
*show seven kinds of sort *
************************************************/
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <fstream.h>
#include <string.h>
template <class T> //简单选择排序
void SelectSort(T A[], int n)
{
int small;
for (int i=0; i<n-1; i++) { //执行n-1趟
small=i; //先假定待排序序列中第一个元素为最小
for (int j=i+1;j<n;j++) //每趟扫描待排序序列n-i-1次
if (A[j]<A[small]) small=j; //如果扫描到一个比最小值元素还小的,则记下其下标
Swap(A[i],A[small]); //最小元素与待排序序列中第一个元素交换
}
}
template <class T> //直接插入排序
void InsertSort(T A[], int n)
{
for(int i=1; i<n; i++){ //执行n-1趟
int j=i;
T temp=A[i]; //待插入元素存入临时变量
while (j>0 && temp<A[j-1]){ //从后往前查找插入位置
A[j]=A[j-1]; j--; //A[j-1]元素后移,j指针前移
}
A[j]=temp; //待插入元素存入找到的插入位置
}
}
template <class T> //冒泡排序
void BubbleSort(T A[], int n)
{
int i,j,last;
i=n-1;
while (i>0){ //最多进行n-1趟
last=0; //进入循环就将last置成0
for (j=0; j<i; j++) //从上往下进行相邻元素的两两比较
if (A[j+1]<A[j]){
Swap(A[j],A[j+1]); //由于后者小,故交换
last=j; //有交换就将last置成j
}
i=last; //如果一趟排序中没有交换元素,则last为0
}
}
template<class T>
void Swap(T &a,T &b)
{
T temp;
temp=a;
a=b;
b=temp;
}
template <class T> //快速排序
void QuickSort(T A[], int n)
{
QSort(A,0,n-1); //以初始序列为待排序序列开始快速排序
}
template <class T>
void QSort(T A[], int left, int right) //left和right为待排序序列的下界和上界
{
int i,j;
if (left<right){ //若待排序序列多于一个元素,则继续快速排序
i=left; j=right+1; //确定待排序序列的游动指针i,j
do{ //开始一趟快速排序,A[left]作为分割元素
do i++;while (A[i]<A[left]); //i指针从左往右找第一个 分割元素的元素
do j--; while (A[j]>A[left]);//j指针从右往左找第一个 分割元素的元素
if (i<j) Swap(A[i],A[j]); //若i<j,则交换两个元素
}while (i<j); //若i<j,则继续本趟排序
Swap(A[left],A[j]); //交换分割元素A[left]和A[j]的位置
QSort(A,left,j-1); //对低端序列快速排序
QSort(A,j+1,right); //对高端序列快速排序
}
}
template<class T> //改进的快速排序
void JTFQuickSort(T *A,int n)
{
JTFQSort(A,0,n-1);
}
template<class T>
void JTFQSort(T A[], int left, int right)
{
int i,j,k;
if (left<right && right-left>10)
{ //若待排序序列多于一个元素,则继续快速排序
i=left; j=right+1; //确定待排序序列的游动指针i,j
k=(left+right)/2;
if (A[left]<=A[right]) //选取分割元素,避免最大值或最小值
{
if (A[k]>A[left]&&A[k]<A[right]) A[left]=A[k];
}
else
if (A[k]<A[left]&&A[k]>A[right]) A[left]=A[k];
do{ //开始一趟快速排序,A[left]作为分割元素
do i++;while (A[i]<A[left]); //i指针从左往右找第一个 分割元素的元素
do j--; while (A[j]>A[left]);//j指针从右往左找第一个 分割元素的元素
if (i<j) Swap(A[i],A[j]); //若i<j,则交换两个元素
}while (i<j); //若i<j,则继续本趟排序
Swap(A[left],A[j]); //交换分割元素A[left]和A[j]的位置
JTFQSort(A,left,j-1); //对低端序列快速排序
JTFQSort(A,j+1,right); //对高端序列快速排序
}
if (left<right && right-left<=10)
{
InsertSort(A+left,right-left+1);
}
}
template <class T> //两路合并排序
void MergeSort(T A[], int n)
{
int i1,j1,i2,j2; //i1,j1是子序列1的下、上界,i2,j2是子序列2的下、上界
int size=1; //子序列中元素个数,初始化为1。
while (size<n){
i1=0;
while (i1+size<n){ //若i1+size<n,则说明存在两个子序列,需再两两合并
i2=i1+size; //确定子序列2的下界
j1=i2-1; //确定子序列1的上界
if (i2+size-1>n-1)
j2=n-1; //若第2个子序列中不足size个元素,则置子序列2的上界j2=n-1
else j2=i2+size-1; //否则有size个,置j2=i2+size-1
Merge(A,i1,j1,i2,j2); //合并相邻两个子序列
i1=j2+1; //确定下一次合并第一个子序列的下界
}
size*=2; //元素个数扩大一倍
}
}
template <class T>
void Merge(T A[],int i1,int j1,int i2,int j2)
{ // i1,j1是子序列1的下、上界,i1,j2是子序列2的下、上界
T *Temp=new T[j2-i1+1]; //分配能存放两个子序列的临时数组
int i=i1,j=i2,k=0; //i,j是两个子序列的游动指针,k是Temp的游动指针
while (i<=j1&&j<=j2) //若两个子序列都不空,则循环
if (A[i]<=A[j]) Temp[k++]=A[i++]; //将A[i]和A[j]中较小的存入Temp[k]
else Temp[k++]=A[j++];
while (i<=j1) Temp[k++]=A[i++]; //若第一个子序列中还有剩余的就存入Temp
while (j<=j2) Temp[k++]=A[j++]; //若第二个子序列中还有剩余的就存入Temp
for (i=0; i<k; i++) A[i1++]=Temp[i]; //将临时数组中的元素倒回A
delete [] Temp;
}
template <class T>
void AdjustDown(T A[], int r, int j)
{
int child=2*r+1; T temp=A[r];
while(child<=j) {
if((child<j)&&(A[child]<A[child+1])) child++; //找两个孩子中较大的孩子
if (temp>= A[child]) break;
A[(child-1)/2]=A[child];
child=2*child+1;
}
A[(child-1)/2]=temp;
}
template <class T> //堆排序
void HeapSort(T A[], int n)
{
for(int i=(n-2)/2; i>-1; i--) AdjustDown(A,i,n-1); //构造最大堆
for(i=n-1; i>0; i--){
Swap(A[0],A[i]); //堆顶和堆底元素交换位置
AdjustDown(A,0,i-1); //将A[0]向下调整为堆
}
}
template<class T>
void ReWrite(T *a,T *b,int n)
{
for (int i=0;i<n;i++)
b[i]=a[i];
}
double average(double *p,int n)
{
double result,add=0.0;
for(int i=0;i<n;i++) add+=p[i];
result=add/n;
return result;
}
char GUI()
{
char a;
cout<<"\t******************************"<<endl;
cout<<"\t\t排序算法测试系统"<<endl;
cout<<"\t\t0.生成测试序列"<<endl;
cout<<"\t\t1.简单选择排序"<<endl;
cout<<"\t\t2.直接插入排序"<<endl;
cout<<"\t\t3.冒泡排序"<<endl;
cout<<"\t\t4.快速排序"<<endl;
cout<<"\t\t5.JTF改进快排"<<endl;
cout<<"\t\t6.两路合并排序"<<endl;
cout<<"\t\t7.堆排序"<<endl;
cout<<"\t\t8.退出系统"<<endl;
cout<<"请选择:"<<endl;
cin>>a;
return a;
}
int main()
{
ofstream write,SWrite,IWrite,BWrite,QWrite,JTFWrite,MWrite,HWrite;
clock_t c_start, c_end;
int num,i,flag=0,times;
char b;
char *choice=new char[20];
int *test=new int[10];
int *testmp=new int[10];
double *elapsed=new double[10];
while(1)
{
b=GUI();
switch (b)
{
case'0':
flag=1;
char a;
cout<<"请输入测试序列的数目及测试次数,以空格隔开:";
cin>>num>>times;
delete[]elapsed;
delete[]test;
delete[]testmp;
test=new int[num];
testmp=new int[num];
elapsed=new double[times];
cout<<"请选择序列类型:A.生成随机序列 B.生成顺序序列 C.生成逆序序列 ";
cin>>a;
if (a=='A'||a=='a')
{
srand(time(NULL));
strcpy(choice,"随机序列");
write.open("test_random.txt",ios::trunc);
for ( i=0;i<num;i++)
{
test[i]=rand();
write<<test[i]<<"\n";
}
}
else if (a=='B'||a=='b')
{
strcpy(choice,"顺序序列");
write.open("test_order.txt",ios::trunc);
for ( i=0;i<num;i++)
{
test[i]=i;
write<<test[i]<<"\n";
}
}
else if (a=='C'||a=='c')
{
strcpy(choice,"逆序序列");
write.open("test_conorder.txt",ios::trunc);
for ( i=num-1;i>=0;i--)
{
test[i]=i;
write<<test[i]<<"\n";
}
}
else{cerr<<"输入错误!"<<endl;break;}
cout<<"测试序列成功生成!"<<endl;
break;
case'1' :
if (flag==0) {cerr<<"测试序列尚未产生!"<<endl;break;}
SWrite.open("SelectSort.txt",ios::trunc);
cout<<choice<<" 简单选择排序时间为:"<<endl;
for (i=0;i<times;i++)
{
ReWrite(test,testmp,num);
c_start= clock(); //获取进程运行的时钟节拍数
SelectSort(testmp,num);
c_end= clock();
elapsed[i]=difftime(c_end,c_start);
SWrite<<i<<": "<<elapsed[i]<<" ms\n";
cout<<i<<": "<<elapsed[i]<<" ms\n";
}
cout<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
SWrite<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
SWrite.close();
break;
case'2':
if (flag==0) {cerr<<"测试序列尚未产生!"<<endl;break;}
IWrite.open("InsertSort.txt",ios::trunc);
cout<<choice<<" 直接插入排序时间为:"<<endl;
for (i=0;i<times;i++)
{
ReWrite(test,testmp,num);
c_start= clock(); //获取进程运行的时钟节拍数
InsertSort(testmp,num);
c_end= clock();
elapsed[i]=difftime(c_end,c_start);
IWrite<<i<<": "<<elapsed[i]<<" ms\n";
cout<<i<<": "<<elapsed[i]<<" ms\n";
}
cout<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
IWrite<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
IWrite.close();
break;
case'3':
if (flag==0) {cerr<<"测试序列尚未产生!"<<endl;break;}
BWrite.open("BubbleSort.txt",ios::trunc);
cout<<choice<<" 冒泡排序时间为:"<<endl;
for (i=0;i<times;i++)
{
ReWrite(test,testmp,num);
c_start= clock(); //获取进程运行的时钟节拍数
BubbleSort(testmp,num);
c_end= clock();
elapsed[i]=difftime(c_end,c_start);
BWrite<<i<<": "<<elapsed[i]<<" ms\n";
cout<<i<<": "<<elapsed[i]<<" ms\n";
}
cout<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
BWrite<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
BWrite.close();
break;
case'4':
if (flag==0) {cerr<<"测试序列尚未产生!"<<endl;break;}
QWrite.open("QuickSort.txt",ios::trunc);
cout<<choice<<" 快速排序时间为:"<<endl;
for (i=0;i<times;i++)
{
ReWrite(test,testmp,num);
c_start= clock(); //获取进程运行的时钟节拍数
QuickSort(testmp,num);
c_end= clock();
elapsed[i]=difftime(c_end,c_start);
QWrite<<i<<": "<<elapsed[i]<<" ms\n";
cout<<i<<": "<<elapsed[i]<<" ms\n";
}
cout<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
QWrite<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
QWrite.close();
break;
case'5':
if (flag==0) {cerr<<"测试序列尚未产生!"<<endl;break;}
JTFWrite.open("JTFQuickSort.txt",ios::trunc);
cout<<choice<<" JTF改进快速排序时间为:"<<endl;
for (i=0;i<times;i++)
{
ReWrite(test,testmp,num);
c_start=clock(); //获取进程运行的时钟节拍数
JTFQuickSort(testmp,num);
c_end= clock();
elapsed[i]=difftime(c_end,c_start);
JTFWrite<<i<<": "<<elapsed[i]<<" ms\n";
cout<<i<<": "<<elapsed[i]<<" ms\n";
}
cout<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
JTFWrite<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
JTFWrite.close();
break;
case'6':
if (flag==0) {cerr<<"测试序列尚未产生!"<<endl;break;}
MWrite.open("MergeSort.txt",ios::trunc);
cout<<choice<<" 两路合并排序时间为:"<<endl;
for (i=0;i<times;i++)
{
ReWrite(test,testmp,num);
c_start= clock(); //获取进程运行的时钟节拍数
MergeSort(testmp,num);
c_end= clock();
elapsed[i]=difftime(c_end,c_start);
MWrite<<i<<": "<<elapsed[i]<<" ms\n";
cout<<i<<": "<<elapsed[i]<<" ms\n";
}
cout<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
MWrite<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
MWrite.close();
break;
case'7':
if (flag==0) {cerr<<"测试序列尚未产生!"<<endl;break;}
HWrite.open("HeapSort.txt",ios::trunc);
cout<<choice<<" 堆排序时间为:"<<endl;
for (i=0;i<times;i++)
{
ReWrite(test,testmp,num);
c_start= clock(); //获取进程运行的时钟节拍数
HeapSort(testmp,num);
c_end= clock();
elapsed[i]=difftime(c_end,c_start);
HWrite<<i<<": "<<elapsed[i]<<" ms\n";
cout<<i<<": "<<elapsed[i]<<" ms\n";
}
cout<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
HWrite<<"平均时间为:"<<average(elapsed,times)<<" ms"<<endl;
HWrite.close();
break;
case'8':
cout<<"谢谢使用!"<<endl;
delete[]test;
delete[]testmp;
delete[]choice;
write.close();
exit(0);
default:
cerr<<"输入错误,请重新输入!"<<endl;
}
}
return 0;
}
1.排序算法比较
利用随机函数产生30000个随机整数,利用所学的排序方法进行排序,并统计每一种排序上机所花费的时间。
2.图的深度遍历
对任意给定的图(顶点数和边数自定),建立它的邻接表并输出,然后利用堆栈的五种基本运算(清空堆栈、压栈、弹出、取栈顶元素、判栈空)实现图的深度优先搜索遍历。
3.图的广度遍历 对任意给定的图(顶点数和边数自定),建立它的邻接表并输出,然后利用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)实现图的广度优先搜索遍历。
4.二叉树的遍历
对任意给定的二叉树(顶点数自定)建立它的二叉链表存贮结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种遍历,输出三种遍历的结果。
随便选一题 我不会编程啊 要交课程设计 一个星期后就要交 93803021@ 本人邮箱 每次发的贴没一个人帮我解决 希望这次有个好心的帮我下忙