| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1555 人关注过本帖
标题:[求助]大作业。急。咳血跪求。数据结构排序
只看楼主 加入收藏
rjwrjw1002
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2007-7-3
收藏
 问题点数:0 回复次数:3 
[求助]大作业。急。咳血跪求。数据结构排序
把折半插入排序和希尔排序做在一起。
选择进入其一。
各位帮忙。
感激中。。。。。。。。。。。。。

[此贴子已经被作者于2007-7-3 8:56:06编辑过]

搜索更多相关主题的帖子: 数据结构 希尔 作业 咳血 
2007-07-03 08:20
康elon
Rank: 2
来 自:西安
等 级:论坛游民
帖 子:179
专家分:24
注 册:2008-4-6
收藏
得分:0 
看这个行不?
#include<stdio.h>
#include<stdlib.h>
struct node
{
    int key;
}r[20];

struct rnode
{
    int key;
    int point;
};

main()
{
    void print(struct node a[20],int n);
    int creat();
    void shell(struct node a[20],int n);
    int hoare(struct node a[20],int l,int h);
    void quick1(struct node a[20],int n);
    void quick2(struct node a[20],int l,int h);
    void heap(struct node a[20],int i,int m);
    void heapsort(struct node a[20],int n);
    void merges(struct node a[20],struct node a2[20],int h1,int mid,int h2);
    void mergepass(struct node a[20],struct node a2[20],int l,int n);
    void mergesort(struct node a[20],int n);
    int yx(int m,int i);
    int radixsort(struct rnode a[20],int n);
    int num,l,h,c;
    struct rnode s[20];
    c=1;
    while(c!=0)
    {
        printf("        主菜单                       \n");
        printf("   1    输入关键字,以-9999表示结束。\n");
        printf("   2    希尔排序                     \n");
        printf("   3    非递归的快速排序             \n");
        printf("   4    递归的快速排序               \n");
        printf("   5    堆排序                       \n");
        printf("   6    归并排序                     \n");
        printf("   7    基数排序                     \n");
        printf(" 输入选择    (1--7,0表示结束):         ");
        scanf("%d",&c);
        switch(c)
        {
        case 1:num=creat();print(r,num);break;
        case 2:shell(r,num);print(r,num);break;
        case 3:quick1(r,num);print(r,num);break;
        case 4:l=0;h=num-1;quick2(r,l,h);
            printf("output quick2sort result:\n");
            print(r,num);break;
        case 5:heapsort(r,num);break;
        case 6:mergesort(r,num);print(r,num);break;
        case 7:radixsort(s,num);
        }
    }
}/*main end*/

void print(struct node a[20],int n)
{
    int i;
    for(i=0;i<n;i++)
        printf("%5d",a[i ].key);
    printf("\n");
}/*print end*/

int creat()
{
    int i,n;
    n=0;
    printf("input keys");
    scanf("%d",&i);
    while(i!=-9999)
    {
        r[n].key=i;
        n++;
        scanf("%d",&i);
    }
    return(n);
}/*creat end*/

void shell(struct node a[20],int n)/*希尔排序*/
{
    int i,j,k;
    for(i=n;i>=1;i--)
        a[i].key=a[i-1].key;
    k=n/2;
    while(k>=1)
    {
        for(i=k+1;i<=n;i++)
        {
            a[0].key=a[i].key;
            j=i-k;
            while((a[j].key>a[0].key)&&(j>=0))
            {
                a[j+k].key=a[j].key;
                j=j-k;
            }
            a[j+k]=a[0];
        }
        k=k/2;
    }
    for(i=0;i<n;i++)
        a[i].key=a[i+1].key;
    printf("输出希尔排序的结果:\n");
}/*shell end*/

/*//////////////////快速排序///////////////////////////*/

int hoare(struct node a[20],int l,int h)/*分区处理函数*/
{
    int i,j;
    struct node x;
    i=l;
    j=h;
    x.key=a[i].key;
    do
    {
        while((i<j)&&(a[j].key>=x.key))
            j--;
        if(i<j)
        {
            a[i].key=a[j].key;
            i++;
        }
        while((i<j)&&(a[i].key<=x.key))
            i++;
        if(i<j)
        {
            a[j].key=a[i].key;
            j--;
        }
    }while(i<j);
    a[i].key=x.key;
    return(i);
}/*hoare end*/

void quick1(struct node a[20],int n)
{
    int i,l,h,tag,top;
    int s[20][2];
    l=0;h=n-1;tag=1;top=0;
    do
    {
        while(l<h)
        {
            i=hoare(a,l,h);
            top++;
            s[top][0]=i+1;
            s[top][1]=h;
            h=h-1;
        }
        if(top==0)
            tag=0;
        else
        {
            l=s[top][0];
            h=s[top][1];
            top--;
        }
    }while(tag==1);
    printf("输出非递归快速排序结果:\n");
}/*quick end*/

void quick2(struct node a[20],int l,int h)/*递归的快速排序*/
{
    int i;
    if(l<h)
    {
        i=hoare(a,l,h);
        quick2(a,l,i-1);
        quick2(a,i+1,h);
    }
}//quick2 end

/*//////////////////快速排序结束////////////////////////*/

/*//////////////////堆排序函数//////////////////////////*/

void heap(struct node a[20],int i,int m)/*调整堆的函数*/
{
    struct node x;
    int j;
    x.key=a[i].key;
    j=2*i;
    while(j<=m)
    {
        if(j<m)
            if(a[j].key>a[j+1].key)
                j++;
        if(a[j].key<x.key)
        {
            a[i].key=a[j].key;
            i=j;
            j=2*i;
        }
        else
            j=m+1;
    }
    a[i].key=x.key;
}/*heap end*/

void heapsort(struct node a[20],int n)/*堆排序的主体函数*/
{
    int i,v;
    struct node x;
    for(i=n;i>0;i--)
        a[i].key=a[i-1].key;
    for(i=n/2;i>=1;i--)
        heap(a,i,n);
    printf("输出堆排序结果:\n");
    for(v=n;v>=2;v--)
    {
        printf("%5d",a[1].key);
        x.key=a[1].key;
        a[1].key=a[v].key;
        a[v].key=x.key;
        heap(a,1,v-1);
    }
    printf("%5d",a[1].key);
    for(i=0;i<n;i++)
        a[i].key=a[i+1].key;
}/*heapsort end*/

/*///////////////堆排序函数结束///////////////////*/

/*////////////////归并函数////////////////////////*/

void merges(struct node a[20],struct node a2[20],int h1,int mid,int h2)
/*归并排序的核心算法*/
{
    int i,j,k;
    i=h1;j=mid+1;k=h1-1;
    while((i<=mid)&&(j<=h2))
    {
        k=k+1;
        if(a[i].key<=a[j].key)
        {
            a2[k].key=a[i].key;
            i++;
        }
        else
        {
            a2[k].key=a[j].key;
            j++;
        }
    }
    while(i<=mid)
    {
        k++;
        a2[k].key=a[i].key;
        i++;
    }
    while(j<=h2)
    {
        k++;
        a2[k].key=a[j].key;
        i++;
    }
}/*merges end*/

void mergepass(struct node a[20],struct node a2[20],int l,int n)
/*一趟归并*/
{
    int j,i,h1,mid,h2;
    i=0;
    while((n-i)>=2*l)
    {
        h1=i;
        mid=h1+l-1;
        h2=i+2*l-1;
        merges(a,a2,h1,mid,h2);
        i=i+2*l;
    }
    if((n-i)<=l)
        for(j=i;j<=n;j++)
            a2[j].key=a[j].key;
    else
    {
        h1=i;
        mid=h1+l-1;
        h2=n-1;
        merges(a,a2,h1,mid,h2);
    }
}/*mergepass end*/

void mergesort(struct node a[20],int n)
{
    int l;
    struct node a2[20];
    l=1;
    while(l<n)
    {
        mergepass(a,a2,l,n);
        l=2*l;
        mergepass(a2,a,l,n);
        l=2*l;
    }
    printf("输出归并排序的结果:\n");
}/*mergesort end*/

/*/////////////归并函数结束///////////////*/

/*/////////////基数排序///////////////////*/

int yx(int m,int i)/*分离关键字倒数第i位有效数字的算法*/
{
    int x;
    switch(i)
    {
    case 1:x=m%10;break;
    case 2:x=(m%100)/10;break;
    case 3:x=(m%1000)/100;break;
    case 4:x=(m%10000)/1000;break;
    }
    return(x);
}/*yx end*/

int radixsort(struct rnode a[20],int n)
{
    int f[11],e[11],i,j,k,l,p,d,t;
    for(i=1;i<=n;i++)
    {
        a[i].key=r[i-1].key;
        a[i].point=i+1;
    }
    a[n].point=0;
    p=1;
    printf("输出关键字有效位数 d\n");
    scanf("%d",&d);
    printf("输出基数排序的结果:\n");
    for(i=1;i<=d;i++)
    {
        for(j=0;j<=10;j++)
        {
            f[j]=0;
            e[j]=0;
        }
        while(p!=0)
        {
            k=yx(a[p].key,i);
            if(f[k]==0)
            {
                f[k]=p;
                e[k]=p;
            }
            else
            {
                l=e[k];
                a[l].point=p;
                e[k]=p;
            }
            p=a[p].point;
        }
        j=0;
        while(f[j]==0)
            j++;
        p=f[j];t=e[j];
        while(j<10)
        {
            j++;
            while((j<10)&&(f[j]==0))
                j++;
            if(f[j]!=0)
            {
                a[t].point=f[j];
                t=e[j];
            }
        }
        a[t].point=0;
        t=p;
        while(t!=0)
        {
            printf("%5d",a[t].key);
            t=a[t].point;
        }
        printf("\n");
    }
    return(p);
}

我很厉害。。。
2008-05-30 20:49
woo23778206
Rank: 1
等 级:新手上路
帖 子:40
专家分:0
注 册:2007-10-31
收藏
得分:0 
也太厉害了 吧
2008-06-05 18:49
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
贴了这么多代码,看死人呀,在排好的里拆半。然后插入就行了
2008-06-06 21:03
快速回复:[求助]大作业。急。咳血跪求。数据结构排序
数据加载中...
 
   



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

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