| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 531 人关注过本帖
标题:求救啊!`````各位高手虾米帮下
只看楼主 加入收藏
daibenlong
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2008-5-15
收藏
 问题点数:0 回复次数:0 
求救啊!`````各位高手虾米帮下
数据库作业     要用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@   本人邮箱  每次发的贴没一个人帮我解决  希望这次有个好心的帮我下忙
搜索更多相关主题的帖子: 虾米 
2008-06-05 19:50
快速回复:求救啊!`````各位高手虾米帮下
数据加载中...
 
   



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

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