三维点通用排序

发布时间:2023年12月29日

前言

NWAFU 2021阶段二 C


一、题目描述

题目描述

在三维笛卡尔坐标系中,可以用X,Y,Z三个坐标分量表示三维空间中的一个点。现有一系列用X,Y,Z表示的三维点,需要对其按指定的X、Y或Z分量进行升序或降序排序。请用C语言实现这一排序过程,程序主体框架已完成。
其中,排序函数selection_sort()原型规定为:
????void selection_sort(Point *a, int n, char mode, AXIS ch);
用于对长度为n的Point类型结构体数组a,按指定的模式mode(字符A或D,D表示升序,A表示降序),根据指定的坐标分量ch(枚举值0、1或2,分别表示X轴、Y轴和Z轴)实现排序。
在程序主体框架中,已给出了三维点结构体的定义、AXIS坐标分量枚举类型定义、排序方式回调函数类型CallBack定义,及所有需要的函数原型。
请用wget命令从此处下载程序主体框架后,设计selection_sort()函数的实现以完成该通用排序功能,并在本地完成测试和调试工作。
注意:不能改变代码框架中所有的函数原型,只需提交要求的selection_sort()函数及其调用的没有列出的自定义函数的实现代码,禁止提交其他代码,否则会造成编译错误。

#include <stdlib.h>
#include <stdio.h>

typedef struct {
    int x, y, z;
} Point;

typedef enum { XAXIS, YAXIS, ZAXIS } AXIS;
typedef int (*CallBack)(int, int);  /* 定义一个函数指针类型CallBack,该类型的指针对应的函数要求返回值是一个整型数据,且含有两个整型形参。 */
int compareA(int, int);
int compareD(int, int);
Point *input(int n);
void selection_sort(Point * a, int n, char mode, AXIS ch);
CallBack setmode(char mode);         /* 返回一个CallBack类型的函数指针 */

int main()
{
    int i, ch, n;
    char k;

    scanf("%d%c%d", &n, &k, &ch);
    Point *pt = input(n);
    selection_sort(pt, n, k, ch);
    for (i = 0; i < n; i++)
        printf("%d %d %d\n", pt[i].x, pt[i].y, pt[i].z);
    free(pt);
    return 0;
}

Point *input(int n)
{
    int i;
    Point *a;
    a = (Point *) malloc(n * sizeof(Point));
    for (i = 0; i < n; i++)
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
    return a;
}

int compareA(int x, int y)
{
    return x > y;
}

int compareD(int x, int y)
{
    return x < y;
}

CallBack setmode(char mode)
{
    if (mode == 'D')
        return compareD;
    else
        return compareA;
}
输入?

三维点的个数n、排序方式mode、排序分量ch及n个三维点的X、Y、Z坐标,其中mode为字符D或A,分别表示升序和降序,ch为枚举值0、1、2,分别表示X轴、Y轴和Z轴坐标分量

输出

升序或降序排列的结果

样例输入
3A1
2 1 0 1 2 4 6 5 -2
样例输出
6 5 -2
1 2 4
2 1 0
提示

回调函数CallBack定义了一种函数指针类型,本题目中,要求在函数selection_sort()里调用其所定义的函数setmode()返回指向比较函数的指针,调用形式参考compareD()和compareA()。

二、设计步骤

理解题意后,这道题的重点在于理解已有的程序结构,对于不熟悉函数指针的初学者有一定难度。setmode()函数的实质是通过参数mode调用对应的compare函数,从而实现对两个数的判断功能,因此在调用时应当写为:

setmode(mode)(a,b)   //根据mode参数对a和b进行比较

同时还要注意该函数的返回值。程序的核心结构可以通过冒泡排序实现。?

代码实现:

void selection_sort(Point * a, int n, char mode, AXIS ch);
void Swap(Point *,Point *);         //Point交换函数

void selection_sort(Point * a, int n, char mode, AXIS ch)
{
    int i,j,temp;
    int *p;        //定义一个长度为n的整形数组,存储用于比较的坐标值
    p = (int *)malloc(n * sizeof(int));

    if(ch == XAXIS)    //根据ch给数组p赋值(也可以用switch)
    {
        for(i = 0;i < n;i++)
        {
            p[i] = a[i].x;
        }
    }
    else if(ch == YAXIS)
    {
        for(i = 0;i < n;i++)
        {
            p[i] = a[i].y;
        }
    }
    else
    {
        for(i = 0;i < n;i++)
        {
            p[i] = a[i].z;
        }
    }
    //冒泡排序
    for(i = 0;i < n - 1;i++)
    {
        for(j = n - 2 - i;j >= 0;j--)
        {
            if(!setmode(mode)(p[j],p[j+1]))
            {
                Swap(&a[j],&a[j+1]);       //交换坐标位置
                temp = p[j];               //交换p位置
                p[j] = p[j+1];
                p[j+1] = temp;
            }
        }
    }
}

void Swap(Point *x,Point *y)
{
    Point temp = *x;
    *x = *y;
    *y = temp;
}

三、补充

然鹅,当你经过上面的思考过程,信心满满地提交代码时,却被91%伤害得猝不及防:

Expected:
-2 0 0
0 1 2
3 2 1
1 2 3
4 6 5
------------------------------
Yours:
-2 0 0
0 1 2
1 2 3
3 2 1
4 6 5

?这个测试点为:

5D1
1 2 3
3 2 1
0 1 2
4 6 5
-2 0 0

这是此题的一个小bug,在这个样例中,它对{1,2,3}和{3,2,1}进行了交换,而在我们的程序中显然不需要这样的操作。本着顾客就是上帝的原则,我们添加一个判断条件,使得当mode判断y值相等时,按照x进行排序,即可通过。

在冒泡中添加以下代码:

if(ch == YAXIS && p[j] == p[j+1])     //补充部分
{
    if(!setmode('A')(a[j].x,a[j+1].x))
    {
        Swap(&a[j],&a[j+1]);
        temp = p[j];
        p[j] = p[j+1];
        p[j+1] = temp;
    }
}
       

总结

NWAFU 2021阶段二 C

文章来源:https://blog.csdn.net/2301_79520789/article/details/135265221
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。