如何使用指向 NULL 的指针对指针数组进行排序？

Question

我尝试实现指针数组的冒泡排序，从它们指向的最大值到最小值，基本上我必须在元素（第二个单元格）的中间放置一个指向 NULL 的指针，当我尝试对它们进行排序，我希望将 NULL 指针放在单元格 (2) 的最后一个位置，而其他的则按顺序排列，除了这个放在最后一个位置的指针。但这给了我一个分段错误：

typedef struct example{
     int data;
}exp;

exp *arr[3];

static void sort_arr(exp *[]);

int main(){
 
 arr[0] = malloc(sizeof(*arr[0]));
 arr[0]->data = 1;

 arr[1] = NULL;

 arr[2] = malloc(sizeof(*arr[2]));
 arr[2]->data = 2;

 sort_arr(arr);

 return 0;
}

static void sort_arr(exp *pass_arr[]){
    for (int i = 0; i < 3; i++)
    {
        for (int j = i + 1; j < 3; ++j)
        {
            if (pass_arr[i]->data < pass_arr[j]->data)
            {
                exp *temp = pass_arr[i];
                pass_arr[i] = pass_arr[j];
                pass_arr[j] = temp;
            }
        }
    }
    return;
}

Answer 1

您需要检查一个数组元素是否为NULL，并将其视为低于另一个值。

            if (pass_arr[i] == NULL || 
                (pass_arr[j] != NULL && pass_arr[i]->data < pass_arr[j]->data))
            {
                exp *temp = pass_arr[i];
                pass_arr[i] = pass_arr[j];
                pass_arr[j] = temp;
            }

Answer 2

使用比较函数 pointer-aware，类似于

#define EQ  0
#define LT -1
#define GT +1

static int cmp( x *exp, y *exp )
{
  if ( x == NULL && y == NULL ) return EQ ; // Two NULLs compare equal
  if ( x == NULL && y != NULL ) return GT ; // NULL compares high with respect to non-NULL
  if ( x != NULL && y == NULL ) return GT ; // NULL compares high with respect to non-NULL

  // if we get here both X and Y are non-null,
  // and so can safely be de-referenced

  if ( x->data < y->data ) return LT ;
  if ( x->data > y->data ) return GT ;

  // must be equal

  return EQ; 
}

您的排序例程中的测试从

if ( pass_arr[i]->data < pass_arr[j]->data )
. . .

至

if ( cmp( pass_arr[i] , pass_arr[j] ) < 0 )
. . .

Answer 3

改变if语句就足够了，例如下面的方式

if ( pass_arr[j] != NULL && 
     ( pass_arr[i] == NULL || pass_arr[i]->data < pass_arr[j]->data ) )

这个比这个条件好

if (pass_arr[i] == NULL || 
    (pass_arr[j] != NULL && pass_arr[i]->data < pass_arr[j]->data))

因为在最后一种情况下，两个空指针可能存在冗余交换。

如何使用指向 NULL 的指针对指针数组进行排序？

How to sort an array of pointers with a pointer to NULL?

c

arrays

pointers