【C語言】指針進階終點站，回調函數和qsort

文章目錄

• ​​1.回調函數​​
• ​​2.qsort函數​​

• ​​2.1void*指針​​
• ​​2.2qsort函數定義​​
• ​​2.3利用qsort函數來排序int/char​​
• ​​2.4用qsort排序結構體​​

• ​​3.模拟實作qsort函數​​
• ​​結語​​

嘟嘟嘟，指針進階的公共汽車到終點站????啦！

這一站我們将學習回調函數、qsort的使用以及模拟實作

1.回調函數

定義：

回調函數就是一個通過函數指針調用的函數。如果你把函數的指針（位址）作為參數傳遞給另一 個函數，當這個指針被用來調用其所指向的函數時，我們就說這是回調函數。回調函數不是由該 函數的實作方直接調用，而是在特定的事件或條件發生時由另外的一方調用的，用于對該事件或 條件進行響應。

在上篇部落格函數指針數組裡，提到了一個電腦的代碼

在這裡就能用到我們的回調函數，通過一個新的calc函數來調用計算函數，同樣達到了避免switch/case語句重複的目的

不過今天我們的學習重點的内容不在這裡，而是一個全新的函數：​

​qsort​

​

2.qsort函數

qsort函數又稱 快速排序函數

2.1void*指針

void* p = &a;      

• void* 是一種無類型的指針，無具體類型的指針
• void* 的指針變量可以存放任意類型的位址
• void* 的指針不能直接進行解引用操作
• void* 的指針不能直接進行加減整數

了解了這個之後，我們再來看看​​qsort函數​​的定義

2.2qsort函數定義

void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));      

這些參數分别代表什麼意義呢？

• void*base 是待排序資料的起始位址
• size_t num 是待排序資料的個數
• size_t size 是待排序資料中每個資料的大小

siez_t是專為sizeof函數的傳回值設計的

它是一個無符号整型

• ​

  ​int (*compar)(const void*,const void*)​

  ​是一個函數指針

  該函數的參數為​

  ​(const void*,const void*)​

  ​，傳回值為int

在qsort的應用中，需要我們自己來編寫這樣一個compar函數，來判斷待排序資料誰大誰小

qsort庫函數對compar函數做出了如下規定：

• p1>p2時 傳回>0的數
• p1=p2時 傳回0
• p1<p2時 傳回<0的數

為什麼比較函數用的void*類型的指針?

因為qsort函數并不知道你需要排序什麼類型的資料，但是作為使用者，我們知道待排序的資料類型以及如何比較待排序的資料，這時候就可以将void*指針強制類型轉換，變為所需要的指針！

2.3利用qsort函數來排序int/char

首先我們建立一個待排序的整型數組，依照qsort函數的定義，将參數填入該函數

int main()
{
    int arr[10] = { 3,4,7,9,0,1,2,5,8,6 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int* ptr = arr;//此處可以直接用arr來代替
    qsort(ptr, sz, sizeof(arr[0]), cmp_int);

    return 0;
}      

接着，我們需要來編寫這個cmp_int函數，用于判斷兩個整型的大小

然後把這個函數名寫入qsort

//編寫一個函數比較整型
int cmp_int(const void* e1, const void* e2)
{
  return *(int*)e1 - *(int*)e2;
}      

運作，可以看到資料已經按照升序重新排序了！

如果你想降序排序，隻需要将比較函數參數裡的e1和e2對調位置

再來試試排序char字元類型吧！

//比較字元
int cmp_char(const void* e1, const void* e2)
{
  char a = *(char*)e1;
  char b = *(char*)e2;
  if (a == b)
    return 0;
  else if (a > b)
    return 1;
  else
    return -1;
}

int main()
{
  char arr1[5] = { 'd','i','a','c','k'};
  int sz1 = sizeof(arr1) / sizeof(arr1[0]);
  int* pc = arr1;
  qsort(pc, sz1, sizeof(arr1[0]), cmp_char);

  for(int i = 0; i < sz1; i++)
  {
    printf("%c ", arr1[i]);
  }
  printf("\n");
  return 0;
}      

2.4用qsort排序結構體

定義一個結構體，内容分别代表姓名、年齡、成績

struct Stu
{
  char name[20];
  int age;
  float score;
};      

該結構體有char、int、float三種類型的資料，需要我們寫三種對應的排序函數

//排序成績
int cmp_stu_by_socre(const void* e1, const void* e2)
{
  if (((struct Stu*)e1)->score > ((struct Stu*)e2)->score)
  {
    return 1;
  }
  else if (((struct Stu*)e1)->score < ((struct Stu*)e2)->score)
  {
    return -1;
  }
  else
  {
    return 0;
  }
}
//按年齡排序
int cmp_stu_by_age(const void* e1, const void* e2)
{
  return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
//按名字排序
int cmp_stu_by_name(const void* e1, const void* e2)
{   //用strcmp函數比較字元串
  return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}      

再寫一個函數來列印結構體變量

void print_stu(struct Stu arr[], int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%s %d %.2f\n", arr[i].name, arr[i].age, arr[i].score);
  }
  printf("\n");
}      

最後在主函數裡定義結構體類型并寫入qsort函數

int main()
{
  struct Stu arr[] = { {"zhangsan",20,87.5f},{"lisi",22,99.0f},{"wangwu", 10, 68.5f},{"niuyeye",30,95.0f} };
  int sz = sizeof(arr) / sizeof(arr[0]);
  qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);

  print_stu(arr,sz);

  return 0;
}      

可以看到，我們的資料已經按照姓名排序了！

3.模拟實作qsort函數

那麼，qsort函數的原理是什麼呢？

之前我們寫過用于排序整型的冒泡排序

其原理是比較數組内的a元素以及a的下一位元素，如果a大于a+1的元素，則将它們互換位置

void bubble_sort(int arr[], int sz)//形參arr本質是指針
{
  //确定趟數
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    //一趟冒泡排序
    int j = 0;
    for (j = 0; j < sz - 1 - i; j++)
    {
      if (arr[j] > arr[j + 1] )
      {
        //交換
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
}      

有沒有辦法将冒泡排序給改寫成通用的排序函數呢？

思考：

• 冒泡排序的時候，使用是int類型，int類型是4個位元組，無法排序比4個位元組小的資料類型
• 結構體類型的大小不一定是4的整數倍，也無法用int來排序
• char類型是1個位元組，能否通過char類型來更改所有類型？

答案當然是肯定的！

在之前的指針學習裡，我們了解到，盡管​

​char*​

​​和​

​int*​

​類型的指針都占4個位元組，但是char*類型隻能通路1個位元組的資料。

我們可以利用​

​char*​

​​指針的這個特點，對資料進行一個位元組一個位元組的交換，交換4次不就能交換完一個int類型了嗎？同理也能通過​

​char*​

​的多次通路，交換其他類型的資料！

既然是模拟實作qsort函數，那函數的參數應該和qsort相同

直接把qsort函數改成my_qsort，開整！

利用冒泡排序的基本架構，我們可以寫出以下的代碼

//模拟實作qsort
void my_qsort(void* base, int sz,int width, int(*cmp)(const void* e1, const void* e2))
{
  for (int i = 0; i < sz - 1; i++)
  {
    for (int j = 0; j < sz - i - 1; j++)
    {
      if (cmp((char*)base + j * width , (char*)base + (j + 1) * width)>0)
      {
        my_swap((char*)base + j * width, (char*)base + (j+1) * width ,width);
      }
    }
  }
}      

你可能對if裡面的語句感到很懵，别急，看圖！

cmp就是一個回調函數，利用函數指針來調用比較函數

再來寫一個swap函數，實作位元組的交換

//用char類型的指針來一個一個地通路
void my_swap(char* e1, char* e2,int sz)
{    
    //sz是待排序資料的寬度:width
    for (int k = 0; k < sz; k++)
    {
        char tmp = *e1;
        *e1 = *e2;
        *e2 = tmp;
        e1++;
        e2++;
    }
}      

測試一下，成功按照成績來排序！

結語

指針進階的行程到這裡就圓滿結束啦！是不是感覺收獲滿滿呢？

學有餘力的朋友們可以看看這一類指針筆試題????