
目錄
- 前言
- 冒泡排序
- 了解qsort
- c語言庫qsort的使用
- qsort模擬實作
- 指標和陣列筆試題決議
- 一維陣列
- 字符陣列
- 二維陣列
- 總結: 陣列名的意義
前言
qsort(quicksort)根據你給的比較函式給一個陣列快速排序,是通過指標移動實作排序功能,關于qsort的模擬實作,本次在底層的使用的排序演算法是使用的冒泡排序,那么就先來了解一下冒泡排序吧,另外作為C/C++程式員我們更應該透徹地去理解指標和陣列,這里我準備了幾道大題,內容會很精彩,期待你的點贊
冒泡排序
1、比較相鄰的元素,如果第一個比第二個大,就交換他們兩個,
2、對每一對相鄰元素做同樣的作業,從開始第一對到結尾的最后一對,在這一點,最后的元素應該會是最大的數,
3、針對所有的元素重復以上的步驟,除了最后一個,
4、持續每次對越來越少的元素重復上面的步驟,直到沒有任何一對數字需要比較,

/* 列印 */
void print(int arr[],int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
/* 交換 */
void Swap(int *n1,int *n2)
{
int tmp = *n1;
*n1 = *n2;
*n2 = tmp;
}
/* 冒泡演算法 */
void bubble_sort(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])
{
Swap(&arr[j],&arr[j + 1]);
}
}
}
}
int main()
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr,sz);
print(arr,sz);
return 0;
}
以上的講解大家對冒泡排序應該有了一個清晰的認知了,接下來進入我們的主題
了解qsort

compare使用檔案

void qsort(void *base, //待排序的物件,寫成void*的形式便于排序任意型別的資料
size_t num, //待排序的元素個數
size_t width,//一個元素的大小,單位是位元組
int(__cdecl *compare)
(const void *elem1, const void *elem2))
{
}
>compare指向排序時用來比較兩個元素的函式
> void *無具體型別的指標,能夠接受任意型別的地址
> 缺點:不能進行運算,不能解參考
> 舉例:void *p3;
> p3++ //err
報錯資訊

c語言庫qsort的使用
整形型別資料的排序
void print(int arr[],int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
int compare_int(const void *elem1, const void *elem2)
{
/* 升序 */
return *(int*)elem1 - *(int*)elem2;
/* 降序 */
//return *(int*)elem2 - *(int*)elem1;
}
int main()
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int n = sizeof(arr) / sizeof(arr[0]);
/* 排序 */
qsort(arr,n,sizeof(arr[0]), compare_int);
/* 列印 */
print(arr, n);
return 0;
}
浮點型型資料的排序
這里要提一句,浮點型資料型別會有精度的丟失,不能直接通過兩個形參值相減后直接回傳結果,通過關系比較回傳合適的整形
int cmp_double(const void* elem1, const void* elem2)
{
return ((*(double*)elem1- *(double*)elem2) > 0)? 1:-1;
}
int main()
{
double a[] = { 1.2,56.4,0.56,456.89,32.4 };
int sz = sizeof(a) / sizeof(a[0]);
qsort(a, sz, sizeof(a[0]), cmp_double);
for (int i = 0; i < sz; i++)
{
printf("%.2f ", a[i]);
}
return 0;
}
結構體型別資料的排序
typedef struct Student
{
int age;
char name[20];
float score;
}Stu;
void print(Stu arr[], int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%.1f ", arr[i].score);
}
printf("\n");
}
int compare_name(const void *elem1, const void *elem2)
{
/* 升序,這里比較的是字串的長度*/
return strcmp(((Stu*)elem1)->name, ((Stu*)elem2)->name);
}
int compare_age(const void *elem1, const void *elem2)
{
/* 升序 */
return ((Stu*)elem1)->age - ((Stu*)elem2)->age;
}
float compare_score(const void *elem1, const void *elem2)
{
/* 升序 */
return ((Stu*)elem1)->score - ((Stu*)elem2)->score;
}
int main()
{
Stu s[3] = { {18,"zhangsan",99.5},{20,"lisi",66.5},{21,"wangwu",76} };
int n = sizeof(s) / sizeof(s[0]);
qsort(s,n,sizeof(s[0]), compare_score);
print(s, n);
return 0;
}
qsort模擬實作
typedef struct Student
{
int age;
char name[20];
float score;
}Stu;
int compare_name(const void *elem1, const void *elem2)
{
/* 升序,這里比較的是字串的長度*/
return strcmp(((Stu*)elem1)->name, ((Stu*)elem2)->name);
}
/* 輸出整形資料 */
void print1(int arr[], int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
/* 輸出結構體成員資料 */
void print2(Stu arr[], int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%s ", arr[i].name);
}
printf("\n");
}
void Swap(char *buf1,char *buf2, size_t width)
{
size_t i = 0;
/* 交換寬度次 */
for (i = 0; i < width; i++)
{
int tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
/* 指標往后迭代 */
buf1++;
buf2++;
}
}
int BubbleSrot_cmp(const void *elem1, const void *elem2)
{
return *(char*)elem1 - *(char*)elem2;
}
/* 使用回呼函式實作一個通用的冒泡排序函式 */
void BubbleSrot(void *base, size_t num, size_t width, int (*BubbleSrot_cmp)(const void *elem1, const void *elem2))
{
//趟數
size_t i = 0;
for (i = 0; i < num - 1; i++)
{
//比較的對數
size_t j = 0;
for (j = 0; j < num - 1 - i; j++)
{
//判斷
if (BubbleSrot_cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//交換
Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
}
}
}
}
/* 整形資料排序*/
void test3()
{
int arr[10] = { 9,8,66,47,65,77,2,1,0 ,4};
int n = sizeof(arr) / sizeof(arr[0]);
BubbleSrot(arr, n, sizeof(arr[0]), BubbleSrot_cmp);
print1(arr, n);
}
/* 結構體型別資料排序 */
void test4()
{
Stu s[3] = { {18,"zhangsan",99.5},{20,"lisi",66.5},{21,"wangwu",76} };
int n = sizeof(s) / sizeof(s[0]);
qsort(s, n, sizeof(s[0]), compare_name);
print2(s, n);
}
int main()
{
test3();
test4();
return 0;
}
int BubbleSrot_cmp(const void elem1, const void elem2)
{
return * (char * )elem1 - * (char * )elem2;
}
BubbleSrot_cmp是比較函式,這次的模擬實作是基于對compar函式的理解和運用,所以功能在本質上是一樣的
指向比較兩個元素的函式的指標,
qsort會反復呼叫這個函式來比較兩個元素,它將遵循以下原型:
接受兩個指標作為實參(都轉換為const void),該函式通過回傳(以穩定和可傳遞的方式)來定義元素的順序:
(char * )base寫成這種形式主要是因為最合適,粒度更細,指標的步長跟型別是有關的,char的指標步長是1,p + 1跳過的是一個位元組長度根據,這樣一來(char * )base參與加減運算的時候步長就是1了,再通過(j * width)和(j + 1 ) * width 拿到相鄰的 兩個元素的地址,傳遞過去的實參大小取決于width的寬度,傳遞過去的指標比較指標所指向地址標識的那塊空間存盤資料的大小,確定是否執行交換,這里的排序是一個升序
void Swap(char *buf1,char *buf2, size_t width)
{
size_t i = 0;
/* 交換寬度次 */
for (i = 0; i < width; i++)
{
int tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
/* 指標往后迭代 */
buf1++;
buf2++;
}
}
Swap函式交換的是指標指向的地址的寬度個位元組
此時我們可以看到e1指向了陣列的首地址,而這3個元素的值都是9、8、66,
執行第一次回圈8和9換了,執行次數的條件限制是 i < width,也就是會回圈 width - 1 次,而恰好int型別的資料占4位元組,所以回圈結束了這兩個值也交換完了
指標和陣列筆試題決議
一維陣列
了解sizeof和strlen
sizeof是一個運算子,求的是變數所占空間的大小,求型別創建的變數所占空間的大小,單位是位元組
strlen是一個庫函式,功能是求字串長度,從起始位置開始向后計數直到遇見‘\0’結束標記,中間統計的字符個數就是字串的長度

//一維陣列
1、int a[4] = {1,2,3,4};
//這是一個一維陣列,陣列的長度是4、陣列的每個元素型別是int,陣列的大小是16
2、printf("%d\n",sizeof(a));
//sizeof運算子與陣列名單獨放在一起,計算的是陣列的大小,16
3、printf("%d\n",sizeof(a+0));
//a是陣列首元素的地址,a + 0依舊是首元素的地址,計算地址的大小具體跟作業系統相關,4/8
4、printf("%d\n",sizeof(*a));
//a是首元素的地址,對地址解參考找到的是陣列下標為0的整形元素,int占4個位元組,4
5、printf("%d\n",sizeof(a+1));
//a是首元素的地址,a + 1跳過一個整形,但他還是一個地址,計算地址的大小具體跟作業系統相關,4/8
6、printf("%d\n",sizeof(a[1]));
//下標為1的整形元素,型別是int占4個位元組
7、printf("%d\n",sizeof(&a));
//&a取出整個陣列的地址,地址 + 1跳過一個陣列的大小,但是a還是一個地址,計算地址的大小具體跟作業系統相關,4/8
8、printf("%d\n",sizeof(*&a));
//&a取出整個陣列的地址(int(*)[4]),整個陣列的大小是16,對陣列的地址解參考,計算的是陣列的大小,16
9、printf("%d\n",sizeof(&a+1));
//&a是陣列的地址,&a + 1跳過整個陣列,但是此時的&a + 1還是一個地址,計算地址的大小具體跟作業系統相關,4/8
10、printf("%d\n",sizeof(&a[0]));
//首元素的地址 int*, 4/8
11、printf("%d\n",sizeof(&a[0]+1));
//首元素的地址 int*, 首元素的地址+ 1 得到的是下標為1的元素地址,地址的大小跟作業系統相關,4/8
字符陣列

//字符陣列
char arr[] = {'a','b','c','d','e','f'};
printf("%d\n", sizeof(arr));
//sizeof(陣列名)計算的是整個陣列的大小,陣列的大小跟元素型別和元素個數有關,6
printf("%d\n", sizeof(arr+0));
//sizeof并未與陣列名單獨放在一起,所以陣列名表示的是陣列首元素的地址,陣列首地址+1跳過一個整形,可是他還是一個地址,地址的大小就是4/8
printf("%d\n", sizeof(*arr));
//sizeof并未與陣列名單獨放在一起,那他表示的就是陣列首元素的地址,元素型別是char,首元素的地址就是char*,對char*指標解參考訪問一個位元組,1
printf("%d\n", sizeof(arr[1]));
//陣列的元素型別是char,char型別所占用的空間是1個位元組
.
printf("%d\n", sizeof(&arr));
//&陣列名是取出整個陣列的地址,陣列的地址是型別是char(*)[6],是一個陣列指標,既然是指標那么指標大小就跟作業系統有關,4/8
printf("%d\n", sizeof(&arr+1));
//&arr取出的是陣列的地址,型別是 char(*)[6],陣列的地址+1跳過的就是一個陣列,即使是這樣,但他還是一個地址,地址就是4/8
printf("%d\n", sizeof(&arr[0]+1));
//arr[0]表示的是陣列首元素,&arr[0]取出陣列首元素的地址,char*,字符指標 + 1 還是一個指標,4/8,但是此時的指標指向的是陣列的第二個元素,因為char*的步長是1個位元組


假設這是字串在記憶體中存盤時的記憶體布局,arr這個陣列名是一個地址arr[ ]并不是給電腦看的,而是給程式員看的,在編譯的時候就已經將機器指令轉化為二進制指令了,而機器能看懂的只是指令,arr只是語法上方便程式員理解
而當這個陣列被創建了伴隨著這塊這塊空間被分配了,但是字串前面的這一段空間和后面的這一段空間都是不確定的
char arr[] = {'a','b','c','d','e','f'};
printf("%d\n", strlen(arr));
//arr陣列首地址會作為引數傳遞給strlen,strlen會從陣列首地址開始往后找,直到運到‘\0’,而中間的字符計數就是字符
//串的長度,但是這個陣列中并未包含‘\0’,strlen還會繼續往后查找,至于‘\0’的出現時機決定了strlen求出字串的長度,而這個‘\0’的出現時機又是不確定的,通過前面的畫圖我們知道這塊空間僅僅我們知道的只,有'a','b','c','d','e','f',這里值得注意的是strlen往后訪問的時候其實他已經越界了
printf("%d\n", strlen(arr+0));
//隨機值,本質同上
printf("%d\n", strlen(*arr));
// arr是首元素的地址,*arr是對首元素的
//地址解參考,取出來的值是‘a’,'a'的ascii碼值就是97,那么strlen就會將'a'的ascii碼值是97看成是一個地址,他是一個非法的地址,野指標,那么程式就會崩潰
printf("%d\n", strlen(arr[1]));
//arr[1]取出的值是‘b’,'b'的ascii碼是98,將b'的ascii碼值98看成一個地址,也會引發程式錯誤 err
printf("%d\n", strlen(&arr));
//&arr 的型別是char(*)[6],strlen這個庫函式的引數型別是 char *,當&arr作為實參傳遞過去,指向的還是陣列首地址,strlen的功能實作是從起始地址向后查找直到遇見‘\0’終止,所以最后的結果也是隨機值,因為‘\0’的出現時機不確定嘛
printf("%d\n", strlen(&arr+1));
//&arr取出的是整個陣列的地址,&arr + 1跳過一個陣列,從之后的地址開始往后查找直到遇見‘\0’結束,但是‘\0’的出現時機并不確定,所以還是一個隨機值
printf("%d\n", strlen(&arr[0]+1));
//&arr[0] + 1跳過一個字符,來到第二個值的地址處,接著往后查找直到遇到‘\0’,而‘\0’的出現時機又不確定,所以還是一個隨機值,只不過他的計數比從strlen從首元素地址往后查找計數少一個

字串的末尾會自動增加一個‘\0’
char arr[] = "abcdef";
printf("%d\n", sizeof(arr));
//sizeof(陣列名)計算整個陣列的大小,7
printf("%d\n", sizeof(arr+0));
//arr并未單獨放在sizeof中,所以計算的是陣列首元素的地址,地址的大小就是4/8
printf("%d\n", sizeof(*arr));
//arr是陣列首元素的地址,對陣列首元素的地址解參考訪問的就是首字符,char型別所占大小就是1,*arr是1
printf("%d\n", sizeof(arr[1]));
//通過下標訪問陣列的第二個元素,char型別的字符所占空間還是1
printf("%d\n", sizeof(&arr));
//&arr取出整個陣列的地址,陣列的地址還是4/8
printf("%d\n", sizeof(&arr+1));
//&arr取出整個陣列的地址,&arr + 1跳過整個陣列,但他還是一個地址,地址還是4/8
printf("%d\n", sizeof(&arr[0]+1));
//&arr[0]取出的是陣列首元素地址,陣列首元素地址 + 1,訪問第二個字符地址,但是還是一個地址,地址大小就是4/8

char arr[] = "abcdef";
printf("%d\n", strlen(arr));
//strlen從起始位置開始往后查找,直到遇見‘\0’結束,而中間的字符計數都是字串的長度,6
printf("%d\n", strlen(arr+0));
//6,本質同上
printf("%d\n", strlen(*arr));
//將'a'的ascii碼值97看成一個地址,也會引發程式錯誤 err
printf("%d\n", strlen(arr[1]));
//將'b'的ascii碼值98看成一個地址,也會引發程式錯誤 err
printf("%d\n", strlen(&arr));
//&arr取出陣列的地址型別是char(*)[6],將陣列的地址傳遞給strlen會發生隱士型別轉換,此時的指著指向的還是陣列首元素的地址,從陣列首元素的地址查找遇到‘\0’終止,中間的字符計數就是陣列的大小
printf("%d\n", strlen(&arr+1));//隨機值
printf("%d\n", strlen(&arr[0]+1));
//從第二個元素開始向后數,遇到‘\0’停止5

const char *p = "abcdef";
printf("%d\n", sizeof(p));//p是指標變數,4/8
printf("%d\n", sizeof(p+1));
//p + 1是指標變數跳過一個字符指向后一個字符的地址,4/8
printf("%d\n", sizeof(*p));
//指標p指向的是字串的首地址,指標解參考訪問的是第一個字符,字符占用1位元組空間
printf("%d\n", sizeof(p[0]));
//等價于*(p + 0),還是首字符,1
printf("%d\n", sizeof(&p));
//指標變數所占用的大小就是 4/8
printf("%d\n", sizeof(&p+1));
// p是char *型別,&p是char**型別 ,
// &p + 1跳過的是4位元組因為char *型別所占空間是4位元組,指標變數所占用的空間就是 4/8
printf("%d\n", sizeof(&p[0]+1));
//指標跳過一個位元組指向后一個字符,但是它還是一個地址,地址就是4/8

const char *p = "abcdef";
printf("%d\n", strlen(p));//6
printf("%d\n", strlen(p+1));//5
printf("%d\n", strlen(*p));//*p取出來的字符是a,a的ascii碼值是97,將字符a,ascii值為97的字符放到strlen中會出錯,因為這是不合法的,err
printf("%d\n", strlen(p[0]));//,同上,err
printf("%d\n", strlen(&p));
//&p取出的是指標變數的地址,不是字串首元素的地址, strlen去求指標變數的地址什么時候遇到結束標記('\0')又是未知的,所以是隨機值
printf("%d\n", strlen(&p+1));
//隨機值,本質同上,但是&p + 1與 &p之間的差值卻并沒有關聯關系,因為strlen去求指標變數的地址什么時候遇到結束標記('\0')又是未知的
printf("%d\n", strlen(&p[0]+1));//5
二維陣列

介于二維陣列會復雜一點,先來看二維陣列的記憶體布局再來做這道題吧,這樣一來也會有一個細致的印象
//二維陣列
int a[3][4] = {0};
printf("%d\n",sizeof(a));
//整個二維陣列的大小:3*4*int
printf("%d\n",sizeof(a[0][0]));
//通過下標訪問到首元素,int型別占4位元組
printf("%d\n",sizeof(a[0]));
//a[0]表示的是二維陣列的第0行的一維陣列,a[0]是一維陣列的陣列名,
//同樣也是一維陣列的首元素地址,這個一維陣列能能訪問的元素也就是a[0][j],sizeof(陣列名)計算的是整個陣列的大小,,16
printf("%d\n",sizeof(a[0]+1));
// a[0]并沒有單獨放在sizeof內部,所以它表示的是一個二維陣列第0行的一維
//陣列,他是一個陣列的首元素的地址a[0][0],型別是int *,a[0] + 1 跳過的是一個整形,現在指向的是第二個元素a[0][1],但是他還是一個地址,4/8
printf("%d\n",sizeof(*(a[0]+1)));
//a[0] + 1,是二維陣列的第0行的一維陣列的首元素地址,+ 1跳過的是一個整
//形,*(a[0] + 1)此時是訪問二維陣列的第0行的一維陣列的第二個元素,下標為a[0][1]
printf("%d\n",sizeof(a+1));
//陣列名并沒有單獨放在sizeof內部,也沒有&,所以a表示【首元素】(第一行)
//的地址,a + 1表示的就是第二行的地址,(可以理解為陣列名a表示的是二維
//陣列的第一行一維陣列的地址,他是一個陣列的地址,陣列的地址 + 1跳過的是一個一維陣列的大小),但是它還是一個地址,4/8
printf("%d\n",sizeof(*(a+1)));
//陣列名并沒有單獨放在sizeof內部,也沒有&,所以a表示【首元素】(第一行)
//的地址,a + 1表示的就是第二行的地址,*(a + 1)訪問的是二維陣列中第二
//行的地址,相當于訪問整個一維陣列,占16個位元組
printf("%d\n",sizeof(&a[0]+1));
//&a[0]取出的是二維陣列的第一行的地址,他是一個陣列的地址,
//陣列的地址 + 1跳過的是一個陣列的大小,現在表示的是二維陣列的第二行的地址,他是一個陣列的地址,地址還是4/8
printf("%d\n",sizeof(*(&a[0]+1)));
//&a[0]取出的是二維陣列的第一行的地址(陣列的地址),&a[0]+1跳過了一個一
//維陣列的大小,*(&a[0]+1)訪問的就是二維陣列中的第二行的地址,對陣列的
//地址解參考放到sizeof內部,計算的是整個陣列的大小,16
//*(&a[0] + 1) --> *(&a[1]) --> a[1],
printf("%d\n",sizeof(*a));
//a表示二維陣列首元素的地址,對首元素的地址解參考訪問的就是首元素,型別
//是int占4位元組
printf("%d\n",sizeof(a[3]));
//注意這里并不會越界,sizeof是一個計算型別大小的運算子,它并不會去檢查這塊空間存不存在,只
//是去計算這塊空間應該會占用多少位元組的大小,a[3]還是表示二維陣列第4行的陣列名,既然是
//陣列名單獨放在sizeof中計算的是陣列的大小,16
總結: 陣列名的意義
- sizeof(陣列名),這里的陣列名表示整個陣列,計算的是整個陣列的大小,
- &陣列名,這里的陣列名表示整個陣列,取出的是整個陣列的地址,
- 除此之外所有的陣列名都表示首元素的地址,

程式的結果是什么?
答案:2 5
分析:*(a + 1),a + 1是從陣列首地址偏移一個整形的大小,表示的是陣列第二個元素的地址 * (a + 1),訪問的是陣列第二個元素,再來
看 * (ptr - 1),ptr指標的初始化的時候是指向&a + 1的地址處,ptr - 1不就又回到了陣列的最后一個元素處的位置嗎

答案:00100014、00100001、00100004
分析:指標 + 1會偏移多少個位元組是取決于它自身的型別,已知結構體大小是20個位元組,那么指標 + 1就會偏移20個位元組,由于地址是以十六進制的形式表示的,十進制的20最侄訓變成十六進制的14,所以是0x100014,
(unsigned long)p + 0x1);會將指標變數強制型別轉換成無符號整形,他是一個整數,整數+ 1 得到的結果就是0x100001
(unsigned int*)p + 0x1);,將結構體指標強制型別轉換為無符號整形指標,指標的步長跟型別有關,那么 無符號整形指標 + 1就會跳過4位元組得到的結果就是0x100004,
后期還會繼續更新,謝謝大家

轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/297838.html
標籤:其他
上一篇:動態記憶體管理(上)
下一篇:wifi修復記錄(8個方法)


(char * )base寫成這種形式主要是因為最合適,粒度更細,指標的步長跟型別是有關的,char的指標步長是1,p + 1跳過的是一個位元組長度根據,這樣一來(char * )base參與加減運算的時候步長就是1了,再通過(j * width)和(j + 1 ) * width 拿到相鄰的 兩個元素的地址,傳遞過去的實參大小取決于width的寬度,傳遞過去的指標比較指標所指向地址標識的那塊空間存盤資料的大小,確定是否執行交換,這里的排序是一個升序




