C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)（中）：https://developer.aliyun.com/article/1513063
3笔试题二
3.1指向函数指针数组的指针
声明一个指向含有10个元素的数组的指针，其中每个元素是一个函数指针，该函数的返回值是int，
参数是int*，正确的是（ ）
A.(int *p[10])(int*)
B.int [10]*p(int *)
C.int (*(*p)[10])(int *)
D.int ((int *)[10])*p
解析：
A选项，第一个括号里是一个完整定义，第二个括号里是个类型，四不像。BD选项，[]只能在标识符右边，双双排除。只有C是能编过的。
3.2函数指针
定义一个函数指针，指向的函数有两个int形参并且返回一个函数指针，返回的指针指向一个有一个
int形参且返回int的函数。下面哪个是正确的？（ ）
A.int (*(*F)(int, int))(int)
B.int (*F)(int, int)
C.int (*(*F)(int, int))
D.*(*F)(int, int)(int)
解析：
D类型不完整先排除，然后看返回值，B的返回值是int，C的返回值是int *，故选A。判断返回值类型只需要删掉函数名/函数指针和参数列表再看就行了。int (*(*F)(int, int))(int)删掉(*F)(int, int)后剩下int (*)(int)，符合题意。
3.3函数指针
设有以下函数void fun(int n,char *s){……},则下面对函数指针的定义和赋值均是正确的是：（ ）
A.void (*pf)(int，char); pf=&fun;
B.void (*pf)(int n，char *s); pf=fun;
C.void *pf(); *pf=fun;
D.void *pf(); pf=fun;
解析：
CD前半句压根就不是定义而是声明，A选项参数列表的第二个参数错了。应为char *，B选项正确。需要说明的是，对于函数名来说，前面的&和*都会被忽略，所以fun前面加不加取地址都没区别。只有定义出的函数指针变量（如题面中的pf）加上&后才会变成二级函数指针。
3.4指针+-
#include <stdio.h> int main() { int aa[2][5] = { 10,9,8,7,6,5,4,3,2,1 }; int* ptr1 = (int*)(&aa + 1); int* ptr2 = (int*)(*(aa + 1)); printf("%d,%d", *(ptr1 - 1), *(ptr2 - 1)); return 0; }
A.1, 6
B.10, 5
C.10, 1
D.1, 5
解析：
&aa的类型是int (*)[2][5]，加一操作会导致跳转一个int [2][5]的长度，直接跑到刚好越界的位置。减一以后回到最后一个位置1处。*(aa + 1)相当于aa[1]，也就是第二行的首地址，自然是5的位置。减一以后由于多维数组空间的连续性，会回到上一行末尾的6处。故选A。
3.5数组指针
#include <stdio.h> int main() { int a[5] = { 5, 4, 3, 2, 1 }; int* ptr = (int*)(&a + 1); printf("%d,%d", *(a + 1), *(ptr - 1)); return 0; }
A.5, 1
B.4, 1
C.4, 2
D.5, 2
解析：
*(a + 1)等同于a[1]，第一个是4，a的类型是int [5]，&a的类型就是int(*)[5]，是个数组指针。所以给int(*)[5]类型加一，相当于加了一个int [5]的长度。也就是这个指针直接跳过了a全部的元素，直接指在了刚好越界的位置上，然后转换成了int *后再减一，相当于从那个位置向前走了一个int，从刚好越觉得位置回到了1的地址处，所以第二个是1，故选B。
3.6函数参数设计
下面代码中print_arr函数参数设计哪个是正确的？（ ）
int arr[3][5] = {1,2,3,4,5,6,7,8,9,10}; print_arr(arr, 3, 5);
A.void print_arr(int arr[ ][ ],int row, int col);
B.void print_arr(int* arr, int row, int col);
C.void print_arr(int (*arr)[5], int row, int col);
D.void print_arr(int (*arr)[3], int row, int col);
解析：
二维数组相当于数组的数组，传到子函数变成数组的指针。int arr[3][5]相当于是3个元素的arr，每个元素是int [5]，所以int [5]是类型说明不能省略。丢失的信息只有数组的元素个数，也就是3。A丢了类型中的5，B选项arr是首元素地址，首元素是第一行数组，指针层次错了。D选项5写成了3，
3.7函数设计
下面test函数设计正确的是：（ ）
char* arr[5] = {"hello", "bit"}; test(arr);
A.void test(char* arr);
B.void test(char** arr);
C.void test(char arr[5]);
D.void test(char* arr[5]);
解析：
指针的数组传递给子函数变为指针的指针，也就是二级指针。但是允许中括号写法，
写成char **arr、char *arr[]、char * arr[5]都可。所以BD正确。
3.8（编程）杨氏矩阵
杨氏矩阵
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，
请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N);
解题：
如杨氏矩阵：
1 2 3
4 5 6
7 8 9
再如：
1 2 3
2 3 4
3 4 5
查找某个元素——若遍历二维数组，若数组有n个元素，
则最坏情况下找n次，即时间复杂度为O(N)，（时间复杂度是数据结构的内容，现在不懂可以略过）
而题目要求时间复杂度小于n。时间复杂度小于O(N)的算法:
#include<stdio.h> int find_arr(int arr[3][3], int row, int col, int k) { int x = 0, y = col - 1;//从右上角开始找 while (x < row && y >= 0) { if (arr[x][y] > k) { y--; } else if (arr[x][y] < k) { x++; } else { printf("%d %d\n", x, y); return 1; } } return 0; } int main() { int arr[3][3] = { 1,2,3,4,5,6,7,8,9 }; // 1 2 3 // 4 5 6 // 7 8 9 //若要找的元素是k＝2，比右上角的3小，因为3是一列中最小的元素，所以去掉一列； // 若要找的元素是k＝7，比右上角的3大，因为3是一行中最大的元素， // 所以去掉一行；7比在剩下的元素中右上角的6还要大，则又去掉一行； // 7与剩下元素中右上角的9小，则在这一行中查找7， // （因为9已经是剩下元素所在列中最小的元素）去掉一列； // 8比7大说明还在8的左边，去掉一列；7与7相等则找到； // 如果7还找不到则结果就是找不到。 int k = 0; scanf("%d", &k); //找到返回1 找不到返回0 //传arr和行、列、要找的元素 if (find_arr(arr, 3, 3, k)) { printf("找到了\n"); } else { printf("找不到\n"); } return 0; }
虽然封装了函数，但是找到的下标是自己打印的，这不是好的解决办法。
解决办法：用函数查找，用函数带回或返回找不到。
而且return不能直接带回两个值。
更好的代码实现：
#include<stdio.h> int find_arr(int arr[3][3], int* row, int* col, int k) { int x = 0, y = *col - 1;//从右上角开始找 while (x < *row && y >= 0) { if (arr[x][y] > k) { y--; } else if (arr[x][y] < k) { x++; } else { *row = x; *col = y; return 1; } } return 0; } int main() { int arr[3][3] = { 1,2,3,4,5,6,7,8,9 }; int k = 0, x = 3, y = 3; scanf("%d", &k); //找到返回1 找不到返回0 //传arr和行、列、要找的元素 //传行和列的地址，则在函数中所求的下标就可以通过这两个地址放到x、y中 if (find_arr(arr, &x, &y, k)) { printf("找到了,下标是%d,%d\n",x,y); } else { printf("找不到\n"); } return 0; } //这里传& x和& y的好处： //既可以带进函数两个值：3和3，在函数中使用； //又可以在函数结束的时候带回值——这种设计是返回型参数（输出型参数）， //用指针修改，把数值带回去。
3.9（编程）模拟实现qsort
自己敲出一个模拟的qsort并应用
