• 【C语言】指针的进阶（三）—— 模拟实现qsort函数以及指针和数组的笔试题解析

    目录

    1、模拟实现qsort函数

    1.1、qsort函数的回顾

    1.2、模拟实现qsort函数 

    2、指针和数组笔试题解析

    2.1、一维数组

    2.2、字符数组

    1、模拟实现qsort函数

    1.1、qsort函数的回顾

    要模拟实现qsort函数，就要了解清楚qsort函数的参数以及使用方式。

    我们先回顾一下qsort函数：

    qsort是一个库函数，底层使用的是快速排序的方式对数据进行排序。头文件：

    这个函数可以直接使用用来排序任意类型的数据。

    qsort函数定义原型： 

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

    • void* base：待排序数组的第一个元素的地址
    • size_t num：待排序数组的元素个数
    • size_t size：以字节为单位，待排序数组中一个元素的大小。
    • int (*compar)(const void*,const void*)：函数指针，指向一个比较函数，用来比较两个元素，由用户自行创建并封装。

    形参中为什么用的是void*：

    void* 是无具体类型的指针，不能进行解引用操作符，也不能进行+-整数的操作，它是用来存放任意类型数据的地址（可以理解为垃圾桶，什么都能装，当需要用时再强制类型转换为需要的类型）。只有void*被允许存放任意类型数据的地址，如果是其他类型的指针编译器会报错。正是因为定义qsort函数时用的是void*，qsort函数才可以排序任意类型的数据。

    1.2、模拟实现qsort函数 

    使用【冒泡排序】的算法，模拟实现一个排序函数 bsort ，可以用来排序任意类型的数据。

    首先，先用冒泡排序实现排序整型数据：

    1. void bsort(int arr[], int sz)
    2. {
    3. 	int i = 0;
    4. 	for ( i = 0; i < sz - 1; i++)
    5. 	{
    6. 		int j = 0;
    7. 		for ( j = 0; j < sz - 1 - i; j++)
    8. 		{
    9. 			if (arr[j] > arr[j + 1])
    10. 			{
    11. 				int tmp = arr[j];
    12. 				arr[j] = arr[j + 1];
    13. 				arr[j + 1] = tmp;
    14. 			}
    15. 		}
    16. 	}
    17. }
    18.  
    19. int main()
    20. {
    21. 	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
    22. 	int sz = sizeof(arr) / sizeof(arr[0]);
    23. 	bsort(arr, sz);
    24.  
    25. 	int i = 0;
    26. 	for ( i = 0; i < sz; i++)
    27. 	{
    28. 		printf("%d ", arr[i]);
    29.  
    30. 	}
    31. 	printf("\n");
    32. 	return 0;
    33. }

            在这个冒泡排序排序整型数据的代码的基础上进行改造。

            首先改造的第一部分就是函数参数，这里的函数参数被写死了只能进行int类型的排序，因此为了让其他类型的数据也能够传入到bsort函数中进行排序，我们这里需要使用指针来接收传入参数。

            参数一：而指针的选择上又只有 void* 最为符合，因为它是用来存放任意类型数据的地址（可以理解为垃圾桶，什么都能装，当需要用时再强制类型转换为需要的类型）。

            参数二：对照库函数qsort的定义中，第二个参数为待排序数组的元素个数，因此我们也用个 size_t num 存放待排序数组的元素个数。

    当前，我们可以通过参数一和参数二知道起始位置地址（void* base）和元素个数（num），但是仅仅知道起始地址和元素个数是不够的，因为不知道一个元素有多大的，一次需要跳过多少个字节，5个？10个？

            参数三：因此还需要一个参数记录一个元素的大小 size_t size。

    到此，我们先把注意里放在函数内部，函数内部循环的趟数和一趟的次数是不需要改造的，只有红色框框内的交换区域需要改造，因为整数的大小可以用><=号比较，但是结构体数据是不能直接使用><=号来比较的。排序一个整型需要整型的方法，排序一个结构体需要结构体的方法，因此如果需要排序各种各样的类型时，不能固定写死交换区域的比较方式，这就需要用户自行创建比较函数来实现。

            参数四：而我们这里只需要使用函数指针 int (*cmp)(const void* e1,const void* e2)  接收用户传递的比较函数即可。e1和 e2都是指针，分别存放着一个要比较的元素的地址。

     对红框区域进行修改：

    注意，在cmp函数中传入base参数时，需要对base强制类型转换char*，因为只有char的步长最短，可以满足所有类型的交换。假设是int类型的话，+1直接跳过4个字节，那么如果要交换一个char类型或者short类型的数据，那就无法做到交换了。

     【交换int类型数据的完整代码】

    1. swap(char* buf1, char* buf2, size_t size)
    2. {
    3.     一个字节一个字节地交换
    4. 	int i = 0;
    5. 	for ( i = 0; i < size; i++)
    6. 	{
    7. 		char tmp = *buf1;
    8. 		*buf1 = *buf2;
    9. 		*buf2 = tmp;
    10. 		buf1++;
    11. 		buf2++;
    12. 	}
    13. }
    14.  
    15.  
    16. //模拟库函数qsort
    17. void bsort(void* base, size_t num, size_t size, int (*cmp)(const void* e1, const void* e2))
    18. {
    19. 	int i = 0;
    20. 	for ( i = 0; i < num - 1; i++)
    21. 	{
    22. 		int j = 0;
    23. 		for ( j = 0; j < num - 1 - i; j++)
    24. 		{
    25. 			//if(arr[j]>arr[j+1])
    26. 			if (cmp((char*)base + size * j, (char*)base + size * (j + 1)) > 0) //大于0时，证明j的元素大于j+1的元素，所以要交换位置
    27. 			{
    28. 				//交换
    29. 				swap((char*)base + size * j, (char*)base + size * (j + 1), size);
    30. 			}
    31. 		}
    32. 	}
    33. }
    34.  
    35.  
    36. //用户自行创建
    37. int cmp_in(const void* e1, const void* e2)
    38. {
    39. 	return *(int*)e1 - *(int*)e2;
    40. }
    41.  
    42. int main()
    43. {
    44. 	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
    45. 	int sz = sizeof(arr) / sizeof(arr[0]);
    46. 	bsort(arr, sz,sizeof(arr[0]),cmp_in);
    47.  
    48. 	int i = 0;
    49. 	for ( i = 0; i < sz; i++)
    50. 	{
    51. 		printf("%d ", arr[i]);
    52.  
    53. 	}
    54. 	printf("\n");
    55. 	return 0;
    56. }

    【图解】

    同理，结构体类型数据也能交换。 

     【交换结构体类型数据的完整代码】

    1. swap(char* buf1, char* buf2, size_t size)
    2. {
    3. 	//一个字节一个字节地交换
    4. 	int i = 0;
    5. 	for ( i = 0; i < size; i++)
    6. 	{
    7. 		char tmp = *buf1;
    8. 		*buf1 = *buf2;
    9. 		*buf2 = tmp;
    10. 		buf1++;
    11. 		buf2++;
    12. 	}
    13. }
    14.  
    15. void bsort(void* base, size_t num, size_t size, int (*cmp)(const void* e1, const void* e2))
    16. {
    17. 	int i = 0;
    18. 	for ( i = 0; i < num - 1; i++)
    19. 	{
    20. 		int j = 0;
    21. 		for ( j = 0; j < num - 1 - i; j++)
    22. 		{
    23. 			//if(arr[j]>arr[j+1])
    24. 			if (cmp((char*)base + size * j, (char*)base + size * (j + 1)) > 0) //大于0时，证明j的元素大于j+1的元素，所以要交换位置
    25. 			{
    26. 				//交换
    27. 				swap((char*)base + size * j, (char*)base + size * (j + 1), size);
    28. 			}
    29. 		}
    30. 	}
    31. }
    32.  
    33.  
    34. struct Stu
    35. {
    36. 	char name[20];
    37. 	int age;
    38. };
    39.  
    40. int cmp_stu_age(const void* e1, const void* e2)
    41. {
    42. 	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
    43. }
    44.  
    45. int main()
    46. {
    47. 	struct Stu arr[] = { {"zhangsan",22},{"lisi",26},{"wangwu",20} };
    48.  
    49. 	int sz = sizeof(arr) / sizeof(arr[0]);
    50. 	bsort(arr, sz,sizeof(arr[0]),cmp_stu_age);
    51.  
    52.  
    53. 	printf("\n");
    54. 	return 0;
    55. }

    例子中是按照年龄排序。使用调试检查一下，确实完成了交换：

    如果想要进行降序排序的话，只需要将用户自行创建并封装的 cmp函数 中return的e1和e2交换即可，下面以cmp_int为例：

    1. swap(char* buf1, char* buf2, size_t size)
    2. {
    3. 	//一个字节一个字节地交换
    4. 	int i = 0;
    5. 	for ( i = 0; i < size; i++)
    6. 	{
    7. 		char tmp = *buf1;
    8. 		*buf1 = *buf2;
    9. 		*buf2 = tmp;
    10. 		buf1++;
    11. 		buf2++;
    12. 	}
    13. }
    14.  
    15. void bsort(void* base, size_t num, size_t size, int (*cmp)(const void* e1, const void* e2))
    16. {
    17. 	int i = 0;
    18. 	for ( i = 0; i < num - 1; i++)
    19. 	{
    20. 		int j = 0;
    21. 		for ( j = 0; j < num - 1 - i; j++)
    22. 		{
    23. 			//if(arr[j]>arr[j+1])
    24. 			if (cmp((char*)base + size * j, (char*)base + size * (j + 1)) > 0) //大于0时，证明j的元素大于j+1的元素，所以要交换位置
    25. 			{
    26. 				//交换
    27. 				swap((char*)base + size * j, (char*)base + size * (j + 1), size);
    28. 			}
    29. 		}
    30. 	}
    31. }
    32.  
    33. int cmp_in(const void* e1, const void* e2)
    34. {
    35. 	return *(int*)e2 - *(int*)e1;  //进行【降序】排序
    36. }
    37.  
    38. int main()
    39. {
    40. 	int arr[] = {1,2,3,4,5,6,7,8,9,10};
    41. 	int sz = sizeof(arr) / sizeof(arr[0]);
    42. 	bsort(arr, sz,sizeof(arr[0]),cmp_in);
    43.  
    44.  
    45. 	return 0;
    46. }

    2、指针和数组笔试题解析

    计算下面运算输出的值

    2.1、一维数组

    1. int a[] = { 1,2,3,4 };
    2. printf("%d\n", sizeof(a));
    3. printf("%d\n", sizeof(a + 0));
    4. printf("%d\n", sizeof(*a));
    5. printf("%d\n", sizeof(a + 1));
    6. printf("%d\n", sizeof(a[1]));
    7. printf("%d\n", sizeof(&a));
    8. printf("%d\n", sizeof(*&a));
    9. printf("%d\n", sizeof(&a + 1));
    10. printf("%d\n", sizeof(&a[0]));
    11. printf("%d\n", sizeof(&a[0] + 1));

    【答案】32位环境下运行的结果

    【解析】

    printf("%d\n", sizeof(a));

    sizeof(数组名)，这里的数组名表示整个数组，所以计算的是整个数组的大小，4(int字节数)*4=16。

    printf("%d\n", sizeof(a + 0));

    a并非单独放在sizeof内部，也没有&，所以数组名a是数组首元素的地址，a+0还是首元素的地址，32位环境下，地址大小就是4。

    printf("%d\n", sizeof(*a));

     a并非单独放在sizeof内部，也没有&,所以数组名a是数组首元素的地址。*a 就是 首元素，大小就是4 ，特别的：*a == *(a+0) == a[0]

    printf("%d\n", sizeof(a + 1));

     a并非单独放在sizeof内部，也没有&，所以数组名a是数组首元素的地址,a+1就是第2个元素的地址，32位环境下，地址大小就是4。

    printf("%d\n", sizeof(a[1]));

     a[1]就是数组的第二个元素，这里计算的就是第二个元素的大小，int就是4。

    printf("%d\n", sizeof(&a));

     &a - 是取出数组的地址，但是数组的地址也是地址，32位环境下，是地址就是4。数组的地址 和 数组首元素的地址 的本质区别是类型的区别，并非大小的区别。

    printf("%d\n", sizeof(*&a));

     对数组指针解引用访问一个数组的大小，单位是字节，也可以理解成 *&相互抵消，即sizeof(*&a) =  sizeof(a)，sizeof(数组名)，这里的数组名表示整个数组，所以计算的是整个数组的大小。

    printf("%d\n", sizeof(&a + 1));

     &a数组的地址，&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、字符数组

    1. char arr[] = {'a','b','c','d','e','f'};
    2. printf("%d\n", sizeof(arr));
    3. printf("%d\n", sizeof(arr+0));
    4. printf("%d\n", sizeof(*arr));
    5. printf("%d\n", sizeof(arr[1]));
    6. printf("%d\n", sizeof(&arr));
    7. printf("%d\n", sizeof(&arr+1));
    8. printf("%d\n", sizeof(&arr[0]+1));

    【答案】 32位环境下运行的结果

    【解析】

    printf("%d\n", sizeof(arr));

     数组名arr单独放在sizeof内部，计算的是整个数组的大小6。

    printf("%d\n", sizeof(arr + 0));

    arr是首元素的地址==&arr[0]，是地址就是4。

    • 指针变量的大小和类型无关，不管什么类型的指针变量，大小都是4/8个字节
    • 指针变量是用来存放地址的，地址存放需要多大空间，指针变量的大小就是几个字节
    • 32位环境下，地址是32个二进制位，需要4个字节，所以指针变量的大小就是4个字节
    • 64位环境下，地址是64个二进制位，需要8个字节，所以指针变量的大小就是8个字节
    printf("%d\n", sizeof(*arr));

     arr是首元素的地址，*arr就是首元素，大小就是1。

    printf("%d\n", sizeof(arr[1]));

     arr[1]就是第2个元素，大小就是1。

    printf("%d\n", sizeof(&arr));

     &arr是数组的地址，sizeof(&arr)就是4

    printf("%d\n", sizeof(&arr + 1));

    &arr+1 是跳过数组后的地址， 是地址就是4。

    printf("%d\n", sizeof(&arr[0] + 1));

     第二个元素的地址，是地址就是4。

    看完sizeof了，再来看一组strlen

    1. printf("%d\n", strlen(arr));
    2. printf("%d\n", strlen(arr+0));
    3. printf("%d\n", strlen(*arr));
    4. printf("%d\n", strlen(arr[1]));
    5. printf("%d\n", strlen(&arr));
    6. printf("%d\n", strlen(&arr+1));
    7. printf("%d\n", strlen(&arr[0]+1));

     【答案】32位环境下运行的结果

    1、随机值

    2、随机值

    3、err

    4、err

    5、随机值

    6、随机值-6

    7、随机值-1

    【解析】

    注意：题目中使用的是char arr[] = {'a','b','c','d','e','f'};的创建方式，该方式不会自动在末尾添加\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表示整个数组的地址，向后查找\0，因此是随机值。

    printf("%d\n", strlen(&arr + 1));

      &arr表示整个数组的地址，&arr + 1表示跳过整个数组（6个字节）向后查找\0，因此是随机值-6。

    printf("%d\n", strlen(&arr[0] + 1));

     &arr[0]表示首元素地址，&arr[0] + 1跳过一个元素，向后查找\0，因此是随机值-1。

    下面换成char arr[] = "abcdef";再来看看

    1. char arr[] = "abcdef";
    2. printf("%d\n", sizeof(arr));
    3. printf("%d\n", sizeof(arr+0));
    4. printf("%d\n", sizeof(*arr));
    5. printf("%d\n", sizeof(arr[1]));
    6. printf("%d\n", sizeof(&arr));
    7. printf("%d\n", sizeof(&arr+1));
    8. printf("%d\n", sizeof(&arr[0]+1));

    【答案】32位环境下运行的结果

     

    【解析】

    printf("%d\n", sizeof(arr));

     sizeof(数组名)表示整个数组，sizeof是会把\0也计入在内的，因此是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表示整个数组的地址， 是地址就是4

    printf("%d\n", sizeof(&arr + 1));

     &arr表示整个数组的地址， &arr + 1表示跳过整个数组，是地址就是4。

    printf("%d\n", sizeof(&arr[0] + 1));

     第一个元素的地址，是地址就是4。

    换成srtlen

    1. printf("%d\n", strlen(arr));
    2. printf("%d\n", strlen(arr+0));
    3. printf("%d\n", strlen(*arr));
    4. printf("%d\n", strlen(arr[1]));
    5. printf("%d\n", strlen(&arr));
    6. printf("%d\n", strlen(&arr+1));
    7. 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));

     统计\0前有多少个元素，就是6。

    printf("%d\n", strlen(arr + 0));

     arr+0等于首元素地址，统计\0前有多少个元素，就是6。

    printf("%d\n", strlen(*arr));

     *arr表示首元素，把元素作为地址直接进行访问，就是非法访问，因此程序会报错。

    printf("%d\n", strlen(arr[1]));

     与上一题同理，非法访问程序报错。

    printf("%d\n", strlen(&arr));

     &arr表示整个数组的地址，向后找\0所以是6。

    printf("%d\n", strlen(&arr + 1));

      &arr表示整个数组的地址，&arr + 1表示跳过了一整个数组，跑到了\0之后，无法知道下一个\0在哪里，所以是随机值。

    printf("%d\n", strlen(&arr[0] + 1));

     &arr[0] + 1 表示第二个元素的地址，向后找\0等于5。

    如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！

    如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！

    如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！

  • 相关阅读:
    TheadLocal：当前线程的全局变量
    【计算机毕设选题推荐】产品管理系统SpringBoot+SSM+Vue
    日料西餐厅餐品预约小程序的作用是什么
    2022 年杭电多校第八场补题记录
    前端开发中的 TypeScript 泛型：深入解析
    【kafka】kafka常见的面试题总结及对应答案
    基于springboot+vue开发的教师工作量管理系
    Java参数校验详解：使用@Valid注解和自定义注解进行参数验证
    [PAT练级笔记] 13 Basic Level 1015
    linux_进程周边知识——理解冯诺依曼体系结构
  • 原文地址：https://blog.csdn.net/zzzzzhxxx/article/details/133023732