logo标签列表

如何在C语言中编写一个通用函数来对字符串数组进行排序？

carrayssortingmacrosgeneric-programming
3
我正在尝试编写一个通用函数来对不同类型的数据进行排序。我的代码如下：
#include<stdio.h>
#define GENERIC_SORT(TYPE) \
TYPE ##_SORT(TYPE a[],int n) \
{  \
int i,j; \
TYPE aux; \
for(i=1;i<n;i++) \
    for(j=n-1;j>=i;j--) \
    if(a[j]<a[j-1]) \
{ \
    aux=a[j]; \
    a[j]=a[j-1]; \
    a[j-1]=aux; \
} \
}
GENERIC_SORT(int)
GENERIC_SORT(float)
GENERIC_SORT(double)
GENERIC_SORT(char)
int main(void)
{
int i,a[]={3,7,5,4,6,1};
int_SORT(a,6);
for(i=0;i<6;i++)
    printf("%d ",a[i]);
return 0;
}

我正在为考试做准备，在课程中有一个例子使用了GENERIC_MAX来查找两个值之间的最大值。我需要按照这种方式进行排序...... 它在int、float、double和char上运行良好。但是我如何使用它来对字符串数组（char a[][100]或char *a[]）进行排序？
4
为什么不使用qsort()？ - Iharob Al Asimi
我正在为一场考试做准备，在课程中有一个使用GENERIC_MAX的示例，它可以找到2个值之间的最大值。我应该按照这个方式进行排序... - flaviumanica
应该使用宏吗？你可以模仿qsort()并使用回调函数。 - Iharob Al Asimi
4个回答
5
一个通用排序算法的典型例子就是 C 运行库 qsort()。它最具有通用性的特点之一是它使用了一个“比较函数”作为参数。
那么为什么不采用这种方法呢？虽然大多数比较函数都很简单，但在访问对象时，它对于解释对象内部的内容是非常宝贵的。
3
您需要做的是使用泛型生成C++模板函数的C等效版本。这通常是将函数指针和重新转换`void*`数据相结合以实现所需结果。`qsort()`函数就是这样做的。下面包括一个代码清单和示例运行来自我之前某个答案的类似内容，展示了如何使用简单的冒泡排序实现多种数据类型。
要将其扩展到任何数据类型，您只需要：
  1. 创建自己的int compareDataType(void* a, void* b)函数
  2. 更新传递给BubbleSort()函数的sizeOfElement和compareFcn参数。
您的方法可能适用于已定义比较操作的原始数据类型，但不适用于抽象数据类型，例如`struct`等。 代码清单 
/*******************************************************************************
 * Preprocessor Directives
 ******************************************************************************/
#include <stdio.h>   // printf
#include <stdlib.h>  // calloc
#include <string.h>  // memcpy
#include <time.h>    // random seed initialization
#define ELEMENT_AT(arr, i, w) (((char*)arr) + ((i)*(w)))
#define BUF_SIZE  (20)


/*******************************************************************************
 * Function Prototypes
 ******************************************************************************/
typedef struct cricket_s {
   char pname[BUF_SIZE];
   char tname[BUF_SIZE];
   int avg;
} cricket_t;


/*******************************************************************************
 * Function Prototypes
 ******************************************************************************/
/* @functionName: bubbleSort
 * @brief:        Performs a bubble sort on an input array, using a user-
 *                provided function pointer for comparing data types so that
 *                the function can be as generic as possible.
 * @param:        arr: The array to search.
 * @param:        compareFcn: The comparison function to use.
 * @param:        sizeOfElement: The size of a single element in arr
 * @param:        numElements: The number of elements in arr
 */
void* bubbleSort(void* arr, int (*compareFcn)(void*, void*), size_t sizeOfElement, size_t numElements);

void rand_str(char *dest, size_t length);
int compareCricketAvg(void *a, void *b);
int compareCricketPname(void *a, void *b);

/*******************************************************************************
 * Function Definitions
 ******************************************************************************/
/*----------------------------------------------------------------------------*/
void* bubbleSort(void* arr, int (*compareFcn)(void*, void*), size_t sizeOfElement, size_t numElements) {
   if (!arr || !compareFcn || !numElements || !sizeOfElement) {
      return NULL;
   }
   int i, j;
   void* tempBuf;
   /* Create a swap buffer */
   if ((tempBuf = calloc(1, sizeOfElement)) == NULL) {
      return NULL;
   }
   /* Sort the list via bubble sort (stable) */
   for (i=0; i<(numElements-1); i++) {
      for (j=0; j<(numElements - i -1); j++) {
         if (compareFcn(ELEMENT_AT(arr, j, sizeOfElement), ELEMENT_AT(arr, j+1, sizeOfElement)) == (-1)) {
            memcpy(tempBuf, ELEMENT_AT(arr, j, sizeOfElement), sizeOfElement);
            memcpy(ELEMENT_AT(arr, j, sizeOfElement), ELEMENT_AT(arr, j+1, sizeOfElement), sizeOfElement);
            memcpy(ELEMENT_AT(arr, j+1, sizeOfElement), tempBuf, sizeOfElement);
         }
      }
   }
   /* Clean up and exit */
   free(tempBuf);
   return arr;
}

/*******************************************************************************
 * Comparson function s.
 * Returns (-1) if a<b, +1 if a>b, 0 if a==b
 */
/*----------------------------------------------------------------------------*/
int compareCricketAvg(void *a, void *b) {
   if (!a || !b) {
      /* Treat bad input as equality */
      return 0;
   }
   int ret;
   if (((cricket_t*)a)->avg < ((cricket_t*)b)->avg) {
      ret = (-1);
   } else if (((cricket_t*)a)->avg > ((cricket_t*)b)->avg) {
      ret = 1;
   } else
      ret = 0;
   return ret;
}


/*----------------------------------------------------------------------------*/
int compareCricketPname(void *a, void *b) {
   if (!a || !b) {
      /* Treat bad input as equality */
      return 0;
   }
   int ret;
   char *s1, *s2;
   s1 = ((cricket_t*)a)->pname;
   s2 = ((cricket_t*)b)->pname;
   ret = strncmp(s1, s2, BUF_SIZE);
   if (ret > 0) {
      ret = 1;
   } else if (ret < 0) {
      ret = (-1);
   } else {
      ret = 0;
   }

   return ret;
}


/*----------------------------------------------------------------------------*/
void rand_str(char *dest, size_t length) {
    char charset[] = "0123456789"
                     "abcdefghijklmnopqrstuvwxyz"
                     "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    while (length-- > 0) {
        size_t index = (double) rand() / RAND_MAX * (sizeof charset - 1);
        *dest++ = charset[index];
    }
    *dest = '\0';
}

/*******************************************************************************
 * Main Entry Point
 ******************************************************************************/
/*----------------------------------------------------------------------------*/
int main(void) {
   srand(time(NULL));   // init random seed
   int numPlayers = 10;
   int i;

   /* Dynamically allocate memory for a few teams */
   cricket_t* team;
   if ((team = calloc(numPlayers, sizeof(cricket_t))) == NULL) {
      printf("Memory error\n");
      return (-1);
   }

   /* Populate struct values */
   for (i=0; i<numPlayers; i++) {
      team[i].avg = rand() % 1000;
      rand_str(team[i].pname, BUF_SIZE);
      printf("Team %d - Pname:%s - Average:%d\n", i, team[i].pname, team[i].avg);
   }
   printf("\n");

   /* Sort the list according to AVG value */
   bubbleSort((void*)team, compareCricketAvg, sizeof(cricket_t), numPlayers);

   /* Print sorted team */
   for (i=0; i<numPlayers; i++) {
      printf("Team %d - Pname:%s - Average:%d\n", i, team[i].pname, team[i].avg);
   }
   printf("\n");

   /* Sort again, now by pname */
   bubbleSort((void*)team, compareCricketPname, sizeof(cricket_t), numPlayers);

   /* Print sorted team */
   for (i=0; i<numPlayers; i++) {
      printf("Team %d - Pname:%s - Average:%d\n", i, team[i].pname, team[i].avg);
   }
   printf("\n");

   free(team);
   return 0;
}

样例运行

Team 0 - Pname:YY7plBOnjIi7YQTKjgqB - Average:605
Team 1 - Pname:sKGbl8pIAjHzq6U2UimD - Average:439
Team 2 - Pname:tBrmmKDNmvf6crrlQaWa - Average:226
Team 3 - Pname:vBXqESI0vju7KRuvvhS1 - Average:117
Team 4 - Pname:YdYqzPBv0s0Bqqgi9hNs - Average:209
Team 5 - Pname:VdDpJ8GB9dAnb0W1Bs14 - Average:633
Team 6 - Pname:DuUTM3bAvXvJAVsJB3TP - Average:212
Team 7 - Pname:h1Fd2hF3l8GQ2AD6LdBI - Average:237
Team 8 - Pname:kjEN3gRX5ve6ar8r7cMg - Average:467
Team 9 - Pname:Djtgpet1XdmhSal81iew - Average:473

Team 0 - Pname:VdDpJ8GB9dAnb0W1Bs14 - Average:633
Team 1 - Pname:YY7plBOnjIi7YQTKjgqB - Average:605
Team 2 - Pname:Djtgpet1XdmhSal81iew - Average:473
Team 3 - Pname:kjEN3gRX5ve6ar8r7cMg - Average:467
Team 4 - Pname:sKGbl8pIAjHzq6U2UimD - Average:439
Team 5 - Pname:h1Fd2hF3l8GQ2AD6LdBI - Average:237
Team 6 - Pname:tBrmmKDNmvf6crrlQaWa - Average:226
Team 7 - Pname:DuUTM3bAvXvJAVsJB3TP - Average:212
Team 8 - Pname:YdYqzPBv0s0Bqqgi9hNs - Average:209
Team 9 - Pname:vBXqESI0vju7KRuvvhS1 - Average:117

Team 0 - Pname:vBXqESI0vju7KRuvvhS1 - Average:117
Team 1 - Pname:tBrmmKDNmvf6crrlQaWa - Average:226
Team 2 - Pname:sKGbl8pIAjHzq6U2UimD - Average:439
Team 3 - Pname:kjEN3gRX5ve6ar8r7cMg - Average:467
Team 4 - Pname:h1Fd2hF3l8GQ2AD6LdBI - Average:237
Team 5 - Pname:YdYqzPBv0s0Bqqgi9hNs - Average:209
Team 6 - Pname:YY7plBOnjIi7YQTKjgqB - Average:605
Team 7 - Pname:VdDpJ8GB9dAnb0W1Bs14 - Average:633
Team 8 - Pname:DuUTM3bAvXvJAVsJB3TP - Average:212
Team 9 - Pname:Djtgpet1XdmhSal81iew - Average:473
函数名称：binarySearch：复制粘贴错误？ - anatolyg
@anatolyg 哈哈，是的。谢谢！ - Cloud
2
您可以通过使用typedef定义新类型来避免非符号类型（如char *或struct point）的问题。更好的方法可能是将新函数的名称作为附加参数传递给宏。
比较的问题可以通过传递比较标准来解决，就像其他人指出的qsort的回调函数一样。由于该函数实际上并没有被调用，而是在编译时被替换为宏，因此它可以是一个宏。
下面是扩展后的宏：
#define GENERIC_SORT(NAME, TYPE, LT)            \
    void NAME(TYPE a[], int n)                  \
    {                                           \
        int i, j;                               \
                                                \
        for (i = 1; i < n; i++) {               \
            for (j = n - 1; j >= i; j--) {      \
                if (LT(a[j], a[j - 1])) {       \
                    TYPE aux = a[j];            \
                    a[j] = a[j - 1];            \
                    a[j - 1] = aux;             \
                }                               \
            }                                   \
        }                                       \
    }

你的整数排序如下：

然后：

#define LESS(a, b) ((a) < (b))

GENERIC_SORT(int_sort, int, LESS);

int main(void)
{
    int array[] = {
        6, 3, 9, 2, 7, 10, 5, 1
    };
    int n = sizeof(array) / sizeof(*array);
    int i;

    int_sort(array, n);
    for (i = 0; i < n; i++) {
        printf("%d\n", array[i]);
    }

    return 0;
}

使用比较函数对字符串进行排序：

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

#include "gen.h"   /* your macro */

int str_less(const char *a, const char *b)
{
    return strcmp(a, b) < 0;
}

GENERIC_SORT(str_sort, const char *, str_less);

int main(void)
{
    const char *array[] = {
        "apricot", "orange", "banana", "apple", "papaya", "kiwi"
    };
    int n = sizeof(array) / sizeof(*array);
    int i;

    str_sort(array, n);
    for (i = 0; i < n; i++) {
        printf("%s\n", array[i]);
    }

    return 0;
}
0
如果您已经有了“GENERIC_MAX”代码（如评论中所述），则可以使用它来代替比较和交换。要做到这一点，请定义“GENERIC_MIN”（应该很容易 - 非常类似于通用最大值）。然后：
#define GENERIC_SORT(TYPE) \
TYPE ##_SORT(TYPE a[],int n) \
{  \
int i,j; \
TYPE aux_min, aux_max; \
for(i=1;i<n;i++) \
    for(j=n-1;j>=i;j--) \
{ \
    aux_min=GENERIC_MIN(a[j], a[j-1]); \
    aux_max=GENERIC_MAX(a[j], a[j-1]); \
    a[j-1]=aux_min; \
    a[j]=aux_max; \
} \
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接