第四十二天学习记录：C语言进阶：笔试题整理Ⅲ

问：解释一下int(*a[20])(int)是什么？
ChatAI答：
int (*a[20])(int) 是一个数组，该数组中每个元素都是一个指向函数的指针，该函数具有一个int类型的参数，并返回一个int类型的值。

具体来说，a是一个数组，包含20个函数指针元素。每个函数指针指向的函数都具有一个int类型的参数，并返回一个int类型的值。可以使用下标访问数组中的任何函数指针元素，并将其赋值为指向满足该条件的函数的指针。

以下是一些使用该数组类型的示例：

#include <stdio.h>int add(int n) {return n + 1;
}int sub(int n) {return n - 1;
}int main() {int (*a[20])(int);a[0] = add;   // 将a[0]指向add函数a[1] = sub;   // 将a[1]指向sub函数int x = 10;x = a[0](x);  // 调用add函数，将a[0]作为函数指针传递x = a[1](x);  // 调用sub函数，将a[1]作为函数指针传递printf("%d\n", x);return 0;
}

在这个示例中，我们声明了一个包含20个函数指针元素的数组a，并将其第一个元素指向add函数，第二个元素指向sub函数。我们还定义了一个变量x并将其初始化为10。然后，我们通过调用a[0]和a[1]中的函数指针来操作x的值，并在最后打印出x的值。

请注意，在声明函数指针时，需要使用一对括号将函数名括起来，这是因为()的优先级高于*，否则会被解释为函数原型。

单选题：
题目名称：
关于回调函数描述错误的是（D）
题目内容：
A、回调函数就是一个通过函数指针调用的函数。
B、回调函数一般通过函数指针实现。
C、回调函数一般不是函数的实现方调用，而是在特定的场景下，由另一方调用。
D、回调函数是调用函数指针指向函数的函数。
（回调函数是调用函数指针指向的那个函数，而不是指向函数的函数。）

求下列程序输出结果：

#define _CRT_SECURE_NO_WARNINGS 1#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;//4,1
}

输出：4，1

求下列程序输出结果：

#define _CRT_SECURE_NO_WARNINGS 1#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;//1,6
}

输出：1，6

题目名称：

字符串左旋
题目内容：
实现一个函数，可以左旋字符串中的k个字符。
例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB
第一种写法：暴力求解法

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <string.h>
#include <assert.h>//暴力求解法
void left_move(char arr[], int k)
{assert(arr != NULL);int i = 0;int len = strlen(arr);for (i = 0; i < k; i++){char tmp = *arr;int j = 0;for (j = 0; j <len-1 ; j++){*(arr + j) = *(arr + j + 1);}*(arr + len - 1) = tmp;}
}int main()
{char arr[] = "abcdef";left_move(arr, 2);printf("%s\n", arr);return 0;
}

第二种写法：三部翻转法

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <string.h>
#include <assert.h>//三部翻转法
void reverse(char* left, char* right)
{assert(left != NULL);assert(right != NULL);while (left<right){char tmp = *left;*left = *right;*right = tmp;left++;right--;}
}void left_move(char arr[], int k)
{assert(arr);int len = strlen(arr);assert(k <= len);reverse(arr,arr+k-1);//逆序左边reverse(arr+k,arr+len-1);//逆序右边reverse(arr,arr+len-1);//逆序整体
}int main()
{char arr[] = "abcdef";left_move(arr, 2);printf("%s\n", arr);return 0;
}

题目名称：

字符串旋转结果
题目内容：
写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
例如：给定s1=AABCD和s2=BCDAA，返回1，给定s1=ABCD和s2=ACBD,返回0.
AABCD左旋一个字符得到ABCDA
AABCD左旋两个字符得到BCDAA
AABCD右旋一个字符得到DAABC

方法一：穷举法

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <string.h>
#include <assert.h>//三部翻转法
void reverse(char* left, char* right)
{assert(left != NULL);assert(right != NULL);while (left<right){char tmp = *left;*left = *right;*right = tmp;left++;right--;}
}void left_move(char arr[], int k)
{assert(arr);int len = strlen(arr);assert(k <= len);reverse(arr, arr + k - 1);//逆序左边reverse(arr + k, arr + len - 1);//逆序右边reverse(arr, arr + len - 1);//逆序整体
}int is_left_move(char* s1, char* s2)
{int len = strlen(s1);int i = 0;for (i = 0; i < len; i++){left_move(s1, 1);int ret=strcmp(s1, s2);if (ret == 0){return 1;}}return 0;
}int main()
{char arr1[] = "abcdef";char arr2[] = "cdefab";int ret = is_left_move(arr1, arr2);if (ret == 1){printf("Yes\n");}else{printf("No\n");}return 0;
}

输出：Yes

方法二：

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <string.h>int is_left_move(char* str1, char* str2)
{int len1 = strlen(str1);int len2 = strlen(str2);if (len1 != len2){return 0;}//1.在str1字符串中追加一个str1字符串//strcat(str1,str1)//err不能自己给自己追加strncat(str1,str2,6);//2.判断str2指向的字符串是否是str1指向的字符串的子串char* ret=strstr(str1, str2);if (ret == NULL){return 0;}else{return 1;}
}int main()
{char arr1[30] = "abcdef";char arr2[] = "cdefab";int ret = is_left_move(arr1, arr2);if (ret == 1){printf("Yes\n");}else{printf("No\n");}return 0;
}

推荐：《程序员编程艺术》

题目名称：
杨氏矩阵
题目内容：
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于0（N）。

问：时间复杂度如何理解？
ChatAI答：
时间复杂度通常用来表示一个算法的执行效率，是指通过分析算法的执行次数与输入规模之间的关系，来描述算法的时间性能。时间复杂度常见的表示方法有大O符号表示法。

大O符号表示法是一种常用的描述算法时间复杂度的方法，它描述的是算法复杂度的一个上界，可以用来衡量算法的时间性能。

具体来说，时间复杂度有三种情况，分别是最坏时间复杂度、最好时间复杂度和平均时间复杂度。最坏时间复杂度表示在最差情况下的执行次数，最好时间复杂度表示在最优情况下的执行次数，平均时间复杂度则是考虑所有输入情况下的执行次数的期望值。在实际应用中，我们常常关注最坏时间复杂度，因为它是通常情况下最能反映算法时间性能的指标。

时间复杂度可以表示为 T(n) = O(f(n))，其中 n 表示问题规模，f(n) 表示每次运行算法所需的基本操作数，O 表示“不超过”的关系。大O记号表示的是一个函数的渐进上界，即随着输入规模 n 的增大，函数 f(n) 的增长速度不超过某个常量乘以 g(n)。其中 g(n) 是已知的一个非负函数，常用的有 O(1)、O(log n)、O(n)、O(nlog n)、O(n²)、O(n³) 等复杂度级别，其中 O(1) 表示常数复杂度，O(n) 表示线性复杂度，O(n²) 表示平方复杂度，O(log n) 表示对数复杂度，O(nlog n) 表示几乎线性的复杂度。

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>int FindNum(int arr[3][3], int k, int *px, int *py)
{int x = 0;int y = *py - 1;while (x<=*px-1&&y>=0){if (arr[x][y] > k){y--;}else if (arr[x][y] < k){x++;}else{*px = x;*py = y;return 1;}}//找不到return 0;
}int main()
{int arr[3][3] = { {1,2,3},{4,5,6},{7,8,9} };int k = 7;int x = 3;int y = 3;int ret = FindNum(arr, k, &x, &y);if (ret == 1){printf("找到了\n");printf("下标是：%d %d\n", x, y);}else{printf("找不到\n");}return 0;
}

问：C语言函数能返回一个数组吗？

ChatAI答：
在 C 语言中，函数不能直接返回一个数组，但可以通过以下几种方式来返回数组：

1. 返回指针

函数可以返回一个指向数组首元素的指针。这种方式效率高，也比较常用。需要注意的是函数返回的指针变量不能指向一个局部数组或变量，因为函数调用结束后，局部数组或变量的内存会被释放，指向它们的指针变量也就失效了。下面是一个返回动态分配数组的例子：

int* allocate_array(int n) {int* array = malloc(n * sizeof(int));/* 为数组赋初值 */for (int i = 0; i < n; i++) {array[i] = i + 1;}return array;
}

2. 传入参数

函数通过传入数组的方式，将结果保存在数组中。这种方式可以兼容局部数组和动态分配的数组。下面是一个接收参数并修改数组的例子：

void modify_array(int* array, int n) {/* 修改数组的元素 */for (int i = 0; i < n; i++) {array[i] += 1;}
}int main() {int a[5] = {1, 2, 3, 4, 5};modify_array(a, 5);/* 输出修改后的数组 */for (int i = 0; i < 5; i++) {printf("%d ", a[i]);}return 0;
}

3. 结构体返回

函数可以返回一个包含数组的结构体，但这种方式适用于较小的数组，否则会导致栈溢出的风险。下面是一个结构体返回数组的例子：

struct Array {int data[5];
};struct Array get_array() {struct Array arr = {.data = {1, 2, 3, 4, 5}};return arr;
}int main() {struct Array arr = get_array();/* 输出获取的数组 */for (int i = 0; i < 5; i++) {printf("%d ", arr.data[i]);} return 0;
}