跪求基数排序算法设计。要求：（1）设计基于顺序队列的基数排序函数。（2）设计一个测试主函数，测试所设

答案:4 悬赏:30 手机版

解决时间 2021-01-21 14:12

提问者网友：佞臣
2021-01-20 20:17

最佳答案

五星知识达人网友：零点过十分
2021-01-20 20:40

C语言源代码：
#include
#include
#define N 1024
int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen)
{
    int* pnCount  = (int*)malloc(sizeof(int)* nMax);        //保存计数的个数
    int i=0;
    for (i = 0; i < nMax; ++i)
    {
        pnCount[i] = 0;
    }
    for (i = 0; i < nLen; ++i)    //初始化计数个数
    {
        ++pnCount[npIndex[i]];
    }
    for (i = 1; i < 10; ++i)  //确定不大于该位置的个数。
    {
        pnCount[i] += pnCount[i - 1];
    }
    int * pnSort  = (int*)malloc(sizeof(int) * nLen);    //存放零时的排序结果。
    //注意：这里i是从nLen-1到0的顺序排序的，是为了使排序稳定。
    for (i = nLen - 1; i >= 0; --i)
    {
        --pnCount[npIndex[i]];
        pnSort[pnCount[npIndex[i]]] = npData[i];
    }
    for (i = 0; i < nLen; ++i)        //把排序结构输入到返回的数据中。
    {
        npData[i] = pnSort[i];
    }
    free(pnSort);                        //记得释放资源。
    free(pnCount);
    return 1;
}
//基数排序
int RadixSort(int* nPData, int nLen)
{
    //申请存放基数的空间
    int* nDataRadix    = (int*)malloc(sizeof(int) * nLen);
    int nRadixBase = 1;    //初始化倍数基数为1
    int nIsOk = 0; //设置完成排序为false
    int i;
    //循环，知道排序完成
    while (nIsOk==0)
    {
        nIsOk = 1;
        nRadixBase *= 10;
        for (i = 0; i < nLen; ++i)
        {
            nDataRadix[i] = nPData[i] % nRadixBase;
            nDataRadix[i] /= nRadixBase / 10;
            if (nDataRadix[i] > 0)
            {
                nIsOk = 0;
            }
        }
        if (nIsOk==1)        //如果所有的基数都为0，认为排序完成，就是已经判断到最高位了。
        {
            break;
        }
        RadixCountSort(nDataRadix, 10, nPData, nLen);
    }
    free(nDataRadix);
    return 1;
}
int main(int argc,char *argv[])
{
    int i=0;
    int j;
    int nData[N];
    printf("请输入你要排序的个数：");
    scanf("%d",&j);
    if(j==0) return 0;
    printf("请输入的%d个整数：",j);
    for(i=0;i    {
        scanf("%d",&nData[i]);
    }
    RadixSort(nData, j);

    printf("基数排序法排序后：
");    for (i = 0; i < j; ++i)
    {
        printf("%d ", nData[i]);
    }

printf("
"); return 0;
}
运行效果如图

全部回答

1楼网友：神的生死簿
2021-01-20 22:33

#include
#include
typedef struct QNode
{
int data;
struct QNode *next;
int Queusize;
}
QNode,*QueuePtr;//定义队列结点类型
typedef struct
{
QueuePtr front;
QueuePtr rear;
}
LinkQueue;//队列的类型
void InitQueue(LinkQueue *Q)//创建队列
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->front->next=NULL;
}
void EnQueue(LinkQueue *Q,int e)//将元素插入队列
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
int DeQueue(LinkQueue *Q)//将元素出列且返回元素的位置
{
int e;
QueuePtr p;
p=Q->front->next;
e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return (e);
}
int QueueEmpty(LinkQueue *Q)//判断队列是否为空
{
if(Q->front==Q->rear )
return 1;
else
return 0;
}
void Select(LinkQueue *Q,int a)
{
int b,i;QueuePtr p;
if(a==1)
{
printf("请输入元素，以0结束：\n");
scanf("%d",&b);
while(b!=0)
{
EnQueue(Q,b);
scanf("%d",&b);
}
}
if(a==2)
{
printf("请输入出对元素个数\n");
scanf("%d",&b);
for(i=0;i {
if(!QueueEmpty(Q))
DeQueue(Q);
else
printf("队列为空！\n");break;
}
}
if(a==3)
{
printf("队内元素为\n");
p=Q->front->next;
while(p!=Q->rear)
{
printf("%d ",p->data);
p=p->next;
}
printf("%d ",p->data);
}
}
int main()
{
LinkQueue Q;int a,b;
InitQueue(&Q);
printf("1、入队列 2、出队列 3、显示队列的内容 4、退出\n");
scanf("%d",&a);
if(a==4)
return 0;
else
{
Select(&Q,a);
printf("请输入选择：0结束，1继续\n");
scanf("%d",&b);
while(b)
{
printf("1、入队列 2、出队列 3、显示队列的内容 4、退出\n");
scanf("%d",&a);
if(a==4)
return 0;
Select(&Q,a);
printf("请输入选择：0结束，1继续\n");
scanf("%d",&b);
}
return 1;

}
}
这个程序基本涵盖了以上方法。

2楼网友：千夜
2021-01-20 22:19

设计一个主函数(保存于lqueue.c)，对链式队列（保存于lqueue.h）进行测试，测试方法为：依次所数据元素1，2，3，4，5入栈，然后出队并在屏幕上显示出栈的数据元素。
运行结果:
输入数据元素:1 2 3 4 5
输出数据元素:1 2 3 4 5

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息

跪求 基数排序算法设计。要求：（1）设计基于顺序队列的基数排序函数。（2）设计一个测试主函数，测试所设

跪求基数排序算法设计。要求：（1）设计基于顺序队列的基数排序函数。（2）设计一个测试主函数，测试所设