網(wǎng)站首頁404淘寶新店怎么快速做起來
目錄
1、模擬實現(xiàn)qsort函數(shù)
1.1、qsort函數(shù)的回顧
1.2、模擬實現(xiàn)qsort函數(shù)?
2、指針和數(shù)組筆試題解析
2.1、一維數(shù)組
2.2、字符數(shù)組
1、模擬實現(xiàn)qsort函數(shù)
1.1、qsort函數(shù)的回顧
要模擬實現(xiàn)qsort函數(shù)，就要了解清楚qsort函數(shù)的參數(shù)以及使用方式。
我們先回顧一下qsort函數(shù)：
qsort是一個庫函數(shù)，底層使用的是快速排序的方式對數(shù)據(jù)進行排序。頭文件：<stdlib.h>
這個函數(shù)可以直接使用用來排序任意類型的數(shù)據(jù)。
qsort函數(shù)定義原型：?
void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));
- void* base：待排序數(shù)組的第一個元素的地址
- size_t num：待排序數(shù)組的元素個數(shù)
- size_t size：以字節(jié)為單位，待排序數(shù)組中一個元素的大小。
- int (*compar)(const void*,const void*)：函數(shù)指針，指向一個比較函數(shù)，用來比較兩個元素，由用戶自行創(chuàng)建并封裝。
形參中為什么用的是void*：
void* 是無具體類型的指針，不能進行解引用操作符，也不能進行+-整數(shù)的操作，它是用來存放任意類型數(shù)據(jù)的地址（可以理解為垃圾桶，什么都能裝，當需要用時再強制類型轉換為需要的類型）。只有void*被允許存放任意類型數(shù)據(jù)的地址，如果是其他類型的指針編譯器會報錯。正是因為定義qsort函數(shù)時用的是void*，qsort函數(shù)才可以排序任意類型的數(shù)據(jù)。
1.2、模擬實現(xiàn)qsort函數(shù)?
使用【冒泡排序】的算法，模擬實現(xiàn)一個排序函數(shù)?bsort?，可以用來排序任意類型的數(shù)據(jù)。
首先，先用冒泡排序?qū)崿F(xiàn)排序整型數(shù)據(jù)：
void bsort(int arr[], int sz)
{int i = 0;for ( i = 0; i < sz - 1; 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 main()
{int arr[] = { 10,9,8,7,6,5,4,3,2,1 };int sz = sizeof(arr) / sizeof(arr[0]);bsort(arr, sz);int i = 0;for ( i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}????????在這個冒泡排序排序整型數(shù)據(jù)的代碼的基礎上進行改造。
????????首先改造的第一部分就是函數(shù)參數(shù)，這里的函數(shù)參數(shù)被寫死了只能進行int類型的排序，因此為了讓其他類型的數(shù)據(jù)也能夠傳入到bsort函數(shù)中進行排序，我們這里需要使用指針來接收傳入?yún)?shù)。
? ? ? ? 參數(shù)一：而指針的選擇上又只有?void*?最為符合，因為它是用來存放任意類型數(shù)據(jù)的地址（可以理解為垃圾桶，什么都能裝，當需要用時再強制類型轉換為需要的類型）。
? ? ? ? 參數(shù)二：對照庫函數(shù)qsort的定義中，第二個參數(shù)為待排序數(shù)組的元素個數(shù)，因此我們也用個 size_t?num?存放待排序數(shù)組的元素個數(shù)。
當前，我們可以通過參數(shù)一和參數(shù)二知道起始位置地址（void* base）和元素個數(shù)（num），但是僅僅知道起始地址和元素個數(shù)是不夠的，因為不知道一個元素有多大的，一次需要跳過多少個字節(jié)，5個？10個？
????????參數(shù)三：因此還需要一個參數(shù)記錄一個元素的大小 size_t size。
到此，我們先把注意里放在函數(shù)內(nèi)部，函數(shù)內(nèi)部循環(huán)的趟數(shù)和一趟的次數(shù)是不需要改造的，只有紅色框框內(nèi)的交換區(qū)域需要改造，因為整數(shù)的大小可以用><=號比較，但是結構體數(shù)據(jù)是不能直接使用><=號來比較的。排序一個整型需要整型的方法，排序一個結構體需要結構體的方法，因此如果需要排序各種各樣的類型時，不能固定寫死交換區(qū)域的比較方式，這就需要用戶自行創(chuàng)建比較函數(shù)來實現(xiàn)。
? ? ? ? 參數(shù)四：而我們這里只需要使用函數(shù)指針 int (*cmp)(const void* e1,const void* e2)? 接收用戶傳遞的比較函數(shù)即可。e1和 e2都是指針，分別存放著一個要比較的元素的地址。
?對紅框區(qū)域進行修改：
注意，在cmp函數(shù)中傳入base參數(shù)時，需要對base強制類型轉換char*，因為只有char的步長最短，可以滿足所有類型的交換。假設是int類型的話，+1直接跳過4個字節(jié)，那么如果要交換一個char類型或者short類型的數(shù)據(jù)，那就無法做到交換了。
?【交換int類型數(shù)據(jù)的完整代碼】
swap(char* buf1, char* buf2, size_t size)
{一個字節(jié)一個字節(jié)地交換int i = 0;for ( i = 0; i < size; i++){char tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}//模擬庫函數(shù)qsort
void bsort(void* base, size_t num, size_t size, int (*cmp)(const void* e1, const void* e2))
{int i = 0;for ( i = 0; i < num - 1; i++){int j = 0;for ( j = 0; j < num - 1 - i; j++){//if(arr[j]>arr[j+1])if (cmp((char*)base + size * j, (char*)base + size * (j + 1)) > 0) //大于0時，證明j的元素大于j+1的元素，所以要交換位置{//交換swap((char*)base + size * j, (char*)base + size * (j + 1), size);}}}
}//用戶自行創(chuàng)建
int cmp_in(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}int main()
{int arr[] = { 10,9,8,7,6,5,4,3,2,1 };int sz = sizeof(arr) / sizeof(arr[0]);bsort(arr, sz,sizeof(arr[0]),cmp_in);int i = 0;for ( i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}【圖解】
同理，結構體類型數(shù)據(jù)也能交換。?
?【交換結構體類型數(shù)據(jù)的完整代碼】
swap(char* buf1, char* buf2, size_t size)
{//一個字節(jié)一個字節(jié)地交換int i = 0;for ( i = 0; i < size; i++){char tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}void bsort(void* base, size_t num, size_t size, int (*cmp)(const void* e1, const void* e2))
{int i = 0;for ( i = 0; i < num - 1; i++){int j = 0;for ( j = 0; j < num - 1 - i; j++){//if(arr[j]>arr[j+1])if (cmp((char*)base + size * j, (char*)base + size * (j + 1)) > 0) //大于0時，證明j的元素大于j+1的元素，所以要交換位置{//交換swap((char*)base + size * j, (char*)base + size * (j + 1), size);}}}
}struct Stu
{char name[20];int age;
};int cmp_stu_age(const void* e1, const void* e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}int main()
{struct Stu arr[] = { {"zhangsan",22},{"lisi",26},{"wangwu",20} };int sz = sizeof(arr) / sizeof(arr[0]);bsort(arr, sz,sizeof(arr[0]),cmp_stu_age);printf("\n");return 0;
}例子中是按照年齡排序。使用調(diào)試檢查一下，確實完成了交換：
如果想要進行降序排序的話，只需要將用戶自行創(chuàng)建并封裝的?cmp函數(shù)?中return的e1和e2交換即可，下面以cmp_int為例：
swap(char* buf1, char* buf2, size_t size)
{//一個字節(jié)一個字節(jié)地交換int i = 0;for ( i = 0; i < size; i++){char tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}void bsort(void* base, size_t num, size_t size, int (*cmp)(const void* e1, const void* e2))
{int i = 0;for ( i = 0; i < num - 1; i++){int j = 0;for ( j = 0; j < num - 1 - i; j++){//if(arr[j]>arr[j+1])if (cmp((char*)base + size * j, (char*)base + size * (j + 1)) > 0) //大于0時，證明j的元素大于j+1的元素，所以要交換位置{//交換swap((char*)base + size * j, (char*)base + size * (j + 1), size);}}}
}int cmp_in(const void* e1, const void* e2)
{return *(int*)e2 - *(int*)e1; //進行【降序】排序
}int main()
{int arr[] = {1,2,3,4,5,6,7,8,9,10};int sz = sizeof(arr) / sizeof(arr[0]);bsort(arr, sz,sizeof(arr[0]),cmp_in);return 0;
}2、指針和數(shù)組筆試題解析
計算下面運算輸出的值
2.1、一維數(shù)組
int a[] = { 1,2,3,4 };
printf("%d\n", sizeof(a));
printf("%d\n", sizeof(a + 0));
printf("%d\n", sizeof(*a));
printf("%d\n", sizeof(a + 1));
printf("%d\n", sizeof(a[1]));
printf("%d\n", sizeof(&a));
printf("%d\n", sizeof(*&a));
printf("%d\n", sizeof(&a + 1));
printf("%d\n", sizeof(&a[0]));
printf("%d\n", sizeof(&a[0] + 1));
【答案】32位環(huán)境下運行的結果
【解析】
printf("%d\n", sizeof(a));sizeof(數(shù)組名)，這里的數(shù)組名表示整個數(shù)組，所以計算的是整個數(shù)組的大小，4(int字節(jié)數(shù))*4=16。
printf("%d\n", sizeof(a + 0));a并非單獨放在sizeof內(nèi)部，也沒有&，所以數(shù)組名a是數(shù)組首元素的地址，a+0還是首元素的地址，32位環(huán)境下，地址大小就是4。
printf("%d\n", sizeof(*a));?a并非單獨放在sizeof內(nèi)部，也沒有&,所以數(shù)組名a是數(shù)組首元素的地址。*a 就是 首元素，大小就是4 ，特別的：*a == *(a+0) == a[0]
printf("%d\n", sizeof(a + 1));?a并非單獨放在sizeof內(nèi)部，也沒有&，所以數(shù)組名a是數(shù)組首元素的地址,a+1就是第2個元素的地址，32位環(huán)境下，地址大小就是4。
printf("%d\n", sizeof(a[1]));?a[1]就是數(shù)組的第二個元素，這里計算的就是第二個元素的大小，int就是4。
printf("%d\n", sizeof(&a));?&a - 是取出數(shù)組的地址，但是數(shù)組的地址也是地址，32位環(huán)境下，是地址就是4。數(shù)組的地址 和 數(shù)組首元素的地址 的本質(zhì)區(qū)別是類型的區(qū)別，并非大小的區(qū)別。
printf("%d\n", sizeof(*&a));?對數(shù)組指針解引用訪問一個數(shù)組的大小，單位是字節(jié)，也可以理解成?*&相互抵消，即sizeof(*&a) =? sizeof(a)，sizeof(數(shù)組名)，這里的數(shù)組名表示整個數(shù)組，所以計算的是整個數(shù)組的大小。
printf("%d\n", sizeof(&a + 1));?&a數(shù)組的地址，&a+1還是地址，是地址就是4。
printf("%d\n", sizeof(&a[0]));?&a[0]是首元素的地址，計算的是地址的大小4。
printf("%d\n", sizeof(&a[0] + 1));?&a[0]是首元素的地址，&a[0]+1就是第二個元素的地址，大小4。
2.2、字符數(shù)組
char arr[] = {'a','b','c','d','e','f'};
printf("%d\n", sizeof(arr));
printf("%d\n", sizeof(arr+0));
printf("%d\n", sizeof(*arr));
printf("%d\n", sizeof(arr[1]));
printf("%d\n", sizeof(&arr));
printf("%d\n", sizeof(&arr+1));
printf("%d\n", sizeof(&arr[0]+1));【答案】?32位環(huán)境下運行的結果
【解析】
printf("%d\n", sizeof(arr));?數(shù)組名arr單獨放在sizeof內(nèi)部，計算的是整個數(shù)組的大小6。
printf("%d\n", sizeof(arr + 0));arr是首元素的地址==&arr[0]，是地址就是4。
- 指針變量的大小和類型無關，不管什么類型的指針變量，大小都是4/8個字節(jié)
- 指針變量是用來存放地址的，地址存放需要多大空間，指針變量的大小就是幾個字節(jié)
- 32位環(huán)境下，地址是32個二進制位，需要4個字節(jié)，所以指針變量的大小就是4個字節(jié)
- 64位環(huán)境下，地址是64個二進制位，需要8個字節(jié)，所以指針變量的大小就是8個字節(jié)
printf("%d\n", sizeof(*arr));?arr是首元素的地址，*arr就是首元素，大小就是1。
printf("%d\n", sizeof(arr[1]));?arr[1]就是第2個元素，大小就是1。
printf("%d\n", sizeof(&arr));?&arr是數(shù)組的地址，sizeof(&arr)就是4
printf("%d\n", sizeof(&arr + 1));&arr+1 是跳過數(shù)組后的地址，?是地址就是4。
printf("%d\n", sizeof(&arr[0] + 1));?第二個元素的地址，是地址就是4。
看完sizeof了，再來看一組strlen
printf("%d\n", strlen(arr));
printf("%d\n", strlen(arr+0));
printf("%d\n", strlen(*arr));
printf("%d\n", strlen(arr[1]));
printf("%d\n", strlen(&arr));
printf("%d\n", strlen(&arr+1));
printf("%d\n", strlen(&arr[0]+1));?【答案】32位環(huán)境下運行的結果
1、隨機值
2、隨機值
3、err
4、err
5、隨機值
6、隨機值-6
7、隨機值-1
【解析】
注意：題目中使用的是char arr[] = {'a','b','c','d','e','f'};的創(chuàng)建方式，該方式不會自動在末尾添加\0，而strlen只有遇到\0才會停下
printf("%d\n", strlen(arr));arr是首元素的地址，就是從arr第一個元素開始，找\0，由于不知道后面\0在哪個位置，因此是隨機值。
printf("%d\n", strlen(arr + 0));?arr是首元素的地址, arr+0還是首元素的地址，與上一題同理，是隨機值。
printf("%d\n", strlen(*arr));?arr是首元素的地址, *arr就是首元素，srtlen需要接收一個地址，而這里傳遞的是一個字符，站在strlen的角度，認為傳參進去的'a'-97就是地址，97作為地址，直接進行訪問，就是非法訪問，因此程序會報錯。
printf("%d\n", strlen(arr[1]));?arr第二個元素地址'b'，與上一題同理，非法訪問程序報錯。
printf("%d\n", strlen(&arr));?&arr表示整個數(shù)組的地址，向后查找\0，因此是隨機值。
printf("%d\n", strlen(&arr + 1));??&arr表示整個數(shù)組的地址，&arr + 1表示跳過整個數(shù)組（6個字節(jié)）向后查找\0，因此是隨機值-6。
printf("%d\n", strlen(&arr[0] + 1));?&arr[0]表示首元素地址，&arr[0] + 1跳過一個元素，向后查找\0，因此是隨機值-1。
下面換成char arr[] = "abcdef";再來看看
char arr[] = "abcdef";
printf("%d\n", sizeof(arr));
printf("%d\n", sizeof(arr+0));
printf("%d\n", sizeof(*arr));
printf("%d\n", sizeof(arr[1]));
printf("%d\n", sizeof(&arr));
printf("%d\n", sizeof(&arr+1));
printf("%d\n", sizeof(&arr[0]+1));【答案】32位環(huán)境下運行的結果
?
【解析】
printf("%d\n", sizeof(arr));?sizeof(數(shù)組名)表示整個數(shù)組，sizeof是會把\0也計入在內(nèi)的，因此是7。
printf("%d\n", sizeof(arr + 0));?arr+0表示首元素地址，是地址就是4。
printf("%d\n", sizeof(*arr));?*arr表示首元素，首元素是char類型，所以就是1。
printf("%d\n", sizeof(arr[1]));?第二個元素，所以就是1。
printf("%d\n", sizeof(&arr));&arr表示整個數(shù)組的地址，?是地址就是4
printf("%d\n", sizeof(&arr + 1));?&arr表示整個數(shù)組的地址， &arr + 1表示跳過整個數(shù)組，是地址就是4。
printf("%d\n", sizeof(&arr[0] + 1));?第一個元素的地址，是地址就是4。
換成srtlen
printf("%d\n", strlen(arr));
printf("%d\n", strlen(arr+0));
printf("%d\n", strlen(*arr));
printf("%d\n", strlen(arr[1]));
printf("%d\n", strlen(&arr));
printf("%d\n", strlen(&arr+1));
printf("%d\n", strlen(&arr[0]+1));【答案】
1、6
2、6
3、err
4、err
5、6
6、隨機值
7、5
【解析】
printf("%d\n", strlen(arr));?統(tǒng)計\0前有多少個元素，就是6。
printf("%d\n", strlen(arr + 0));?arr+0等于首元素地址，統(tǒng)計\0前有多少個元素，就是6。
printf("%d\n", strlen(*arr));?*arr表示首元素，把元素作為地址直接進行訪問，就是非法訪問，因此程序會報錯。
printf("%d\n", strlen(arr[1]));?與上一題同理，非法訪問程序報錯。
printf("%d\n", strlen(&arr));?&arr表示整個數(shù)組的地址，向后找\0所以是6。
printf("%d\n", strlen(&arr + 1));??&arr表示整個數(shù)組的地址，&arr + 1表示跳過了一整個數(shù)組，跑到了\0之后，無法知道下一個\0在哪里，所以是隨機值。
printf("%d\n", strlen(&arr[0] + 1));?&arr[0] + 1 表示第二個元素的地址，向后找\0等于5。
如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！
如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！
如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！