代码收藏家 【嵌入式C语言：面试与工作必备知识】
嵌入式C语言必备知识（面试和工作都用得到）
一、基础部分
1、数组与链表的区别？
（1）数组的元素个数在定义时就必须确定，且元素的类型必须一致；而链表的元素个数自由，且元素内可以有不同类型的数据。
（2）数组的元素在内存中是按顺序存储的，而链表的元素是随机存储的。
（3）要访问数组的元素可以按下标索引来访问，速度比较快；如果对它进行插入/删除操作的话，就得移动很多元素，所以对数组进行插入/删除操作效率很低。由于链表是随机存储的，如果要访问链表中的某个元素的话，那就得从链表的头逐个遍历，直到找到所需要的元素为止，所以链表的随机访问的效率就比数组要低；链表在插入/删除操作上有很高的效率（相对数组）。一句话总结就是：数组的访问效率高，而链表的插入/删除效率高。
2、C语言程序代码优化方法
（1）选择合适的数据结构与算法；
（2）使用尽量小的数据类型；
（3）使用自加、自减指令；
（4）用移位实现乘除法运算；
（5）求余运算用&（如a=a%8改为a=a&7）；
（6）平方运算用*（如a=pow(a,2.0)改为a=a*a）；
（7）延时函数的自加改为自减；
（8）switch语句中根据发生频率来进行case排序；
（9）减少运算的强度。
3、堆和栈的的区别？
| C语言内存分配的堆和栈 | 栈是向下生长的，栈中分配函数参数和局部变量，其分配方式类似于数据结构中的栈。堆是向上生长的，堆中分配程序员申请的内存空间（一旦忘记释放会造成内存泄漏），其分配方式类似于数据结构中的链表 |
|---|---|
| 数据结构的堆和栈 | 栈是一种先进后出的数据结构。堆是一种经过排序的树形数据结构（通常是二叉堆），每个结点都有一个值，根结点的值最小或最大，常用来实现优先队列，堆的存储是随意的 |
4、内联函数的优缺点和适用场景是什么？
（1）优点：内联函数与宏定义一样会在原地展开，省去了函数调用开销，同时又能做类型检查。
（2）缺点：它会使程序的代码量增大，消耗更多内存空间。
（3）适用场景：函数体内没有循环（执行时间短）且代码简短（占用内存空间小）
4、下面代码输出是什么？
#include<stdio.h>
void main()
{
int a[5] = {1, 2, 3, 4, 5};
int *ptr = (int *)(&a + 1);
printf("%d, %d", *(a + 1), *(ptr - 1));
}
答案：输出为2, 5
解读： a是数组首元素地址，所以*(a + 1)就是第二个元素a[1]。&a是数组地址，所以&a +1是整个数组结尾的下一个地址，*(ptr – 1)就是a[4]。
5、结构体struct和联合体union的区别？
（1）两者最大的区别在于内存的使用。
（2）结构体各成员拥有自己的内存，各自使用且互不干涉，遵循内存对齐原则。
（3）联合体所有成员共用一块内存空间，并且同时只有一个成员可以得到这块内存的使用权。一个联合体变量的总长度应至少能容纳最大的成员变量，且需要进行内存补齐。
6、函数参数的传递方式有几种？
（1）两种：值传递、指针传递。
（2）严格来看，只有一种传递，值传递，指针传递也是按值传递的，复制的是地址。
7、堆和栈的的区别？
| C语言内存分配的堆和栈 | 栈是向下生长的，栈中分配函数参数和局部变量，其分配方式类似于数据结构中的栈。堆是向上生长的，堆中分配程序员申请的内存空间（一旦忘记释放会造成内存泄漏），其分配方式类似于数据结构中的链表 |
|---|---|
| 数据结构的堆和栈 | 栈是一种先进后出的数据结构。堆是一种经过排序的树形数据结构（通常是二叉堆），每个结点都有一个值，根结点的值最小或最大，常用来实现优先队列，堆的存储是随意的。 |
8、在c语言中，一个函数不写返回值类型，默认的返回类型是（）
- 一个函数没有返回值时，是void型，此时的void关键字不能省略（不写）；
- 一个函数省略（不写）返回值类型时，默认是int型；
9、预处理功能主要包括:宏定义、文件包含、条件编译
10、%取余运算符只能用于整形
void main (void) {
double x=28;
int r;
r= x%5;
printf ("r=%d\n", r);
}
程序的输出是（） 编译错误
11、数组名是一个常量指针a
void main (``void``) {
char a[] = “SF-TECH” ;
a++;
printf (“%s”, a);
}
数组名是一个常量指针，所以不能对数组名直接进行++操作。可以重新定义指针，指向数组首地址，对其进行++操作。
12、进制转换
void main ( void )
{
int i ;
i = 0x10 + 010+ 10;
printf ("x = %x", i);
}
ox10是16进制，换成十进制是16；010是八进制，换成十进制是8；16+8+10＝34；％x是以16进制输出，34换成16进制就是22
13、printf ( “” )的返回值
void main (void)
{
int x;
x = printf("I See, Sea in C");
printf("x=%d", x);
}
int printf ( const char * format, … );返回值：
正确返回输出的字符总数，错误返回负值，与此同时，输入输出流错误标志将被置值，可由指示器ferror来检查输入输出流的错误标志。
14、下面是C语言的操作符的是（1）
- .
- $
- @
- 都不是
. 为访问结构体成员的操作符
15、 arm压栈过程
16、在ARM cortex M系列中， 哪些寄存器是分组寄存器？（）
17、代码中使用const定义的变量，存放在哪个段中？
18、支持时间片轮转调度的实时操作系统中，下面哪些情况会发生任务切换？（1、2、3、4）
- 进程使用互斥锁，互斥锁不可用时
- 进程主动休眠
- 进程被撤销
- 进程当前时间片使用完
19、应用的C函数main函数原型定义是下（4）
- void main(void)
- int main(void *arg)
- void main(void *arg)
- int main(int argc, const char *argv[])
二、算法部分
1、如何判读一个系统的大小端存储模式？
(1) 方法一：int 强制类型转换为char ，用“[]”解引用
void checkCpuMode(void)
{
int c = 0x12345678;
char *p = (char *)&c;
if(p[0] == 0x12)
printf("Big endian.\n");
else if(p[0] == 0x78)
printf("Little endian.\n");
else
printf("Uncertain.\n");
}
（2）方法二：int *强制类型转换为char ，用“”解引用
void checkCpuMode(void)
{
int c = 0x12345678;
char *p = (char *)&c;
if(*p == 0x12)
printf("Big endian.\n");
else if(*p == 0x78)
printf("Little endian.\n");
else
printf("Uncertain.\n");
}
（3）方法三：包含short跟char的共用体
void checkCpuMode(void)
{
union Data
{
short a;
char b[sizeof(short)];
}data;
data.a = 0x1234;
if(data.b[0] == 0x12)
printf("Big endian.\n");
else if(data.b[0] == 0x34)
printf("Little endian.\n");
else
printf("uncertain.\n");
}
大端小端模式：
大端模式：是指一个数据的低位字节序的内容放在高地址处，高位字节序存的内容放在低地址处。
小端模式：是指一个数据的低位字节序内容存放在低地址处，高位字节序的内容存放在高地址处。
如：一个数0x12345678存放在一个4字节空间里
0x12345678中，1234属于高位，如果低地址的第一个字节存的0x12 则 是高位字节 存储在了低地址，是大端模式。
低地址 ——————–> 高地址
0x12 | 0x34 | 0x56 | 0x78
如：一个数0x12345678存放在一个4字节空间里
0x12345678中，1234属于高位，如果低地址的第一个字节存的0x12 则是高位字节 存储在了 高地址，是小端模式。
低地址 ——————–> 高地址
0x78 | 0x56 | 0x34 | 0x12
原文链接：https://blog.csdn.net/ALakers/article/details/116225089
2、验证回文串：给定一个字符串，验证它是否是回文串，只考虑字符和数字字符，可以忽略字母的大小写
（回文串即左右对称的字符串，如"A man, a plan, a canal: Panama"）
思路：双指针法，一个指针指向字符串开头，另一个指向字符串结尾，两个指针都往中间
移动并寻找字符和数字，并将字母统一转为小写，然后比较是否相同，若不相同则返回false，若相同则继续寻找……如此循环，若直到两指针相遇都没返回false，则返回true。
bool isPalindrome(char * s)
{
char *left = s, *right = s + strlen(s) - 1;
if(strlen(s) == 0) return true;
while(left < right)
{
while(!((*left >= 'a' && *left <= 'z') || (*left >= 'A' && *left <= 'Z') || (*left >= '0' && *left <= '9')) && left < right) // 找到字母或数字
left++;
while(!((*right >= 'a' && *right <= 'z') || (*right >= 'A' && *right <= 'Z') || (*right >= '0' && *right <= '9')) && right > left) // 找到字母或数字
right--;
if(left < right)
{
if((*left >= 'A' && *left <= 'Z')) // 若为大写，则转为小写
*left = *left + 32;
if((*right >= 'A' && *right <= 'Z')) // 若为大写，则转为小写
*right = *right + 32;
if(*left == *right) // 比较
{
left++;
right--;
}
else
return false;
}
else
return true;
}
return true;
}
3、写一个程序, 要求功能：求出用1，2，5这三个数不同个数组合的和为100的组合个数。 如：100个1是一个组合，5个1加19个5是一个组合。
（1）最容易想到的算法是暴力解法 思路：设x是1的个数，y是2的个数，z是5的个数，number是组合数，注意到0 <= x <=> 100，0 <= y <= 50，0 <= z <= 20。
void count(void)
{
int x, y, z, number;
number = 0;
for (x = 0; x <= 100 / 1; x++)
{
for (y = 0; y <= 100 / 2; y++)
{
for (z = 0; z <= 100 / 5; z++)
{
if (x + 2 * y + 5 * z == 100)
number++;
}
}
}
printf("%d\t", number);
}
（2）上述暴力解法的时间复杂度为O(n³)，程序有些冗余，对其进行优化如下
思路：注意到上面代码的第三个for循环其实不是必要的，因为当1和2的数目确定了之后，加上一定数目的5能不能组成100也就确定了，没必要用for循环一个个去尝试，直接计算即可，优化后时间复杂度变为O(n2)。
void count(void)
{
int x, y, z, number;
number = 0;
for (x = 0; x <= 100 / 1; x++)
{
for (y = 0; y <= 100 / 2; y++)
{
if (100 - x - y * 2 >= 0 && (100 - x - y * 2) % 5 == 0) // 判断能否5整除
number++;
}
}
printf("%d\t", number);
}
4、判断链表是否有环。
思路：双指针法，定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（fast> == NULL）都没有追上第一个指针，那么链表就不是环形链表。
bool IsLoop(NODE *head)
{
if (head == NULL)
return false;
NODE *slow = head -> next; // 初始时，慢指针从第一个节点开始走1步
if (slow == NULL)
return false;
NODE *fast = slow -> next; // 初始时，快指针从第一个节点开始走2步
while (fast != NULL && slow != NULL) // 当单链表没有环时，循环到链表末尾结束
{
if (fast == slow) // 快指针追上慢指针
return true;
slow = slow -> next; // 慢指针走一步
fast = fast -> next; // 快指针走两步
if (fast != NULL)
fast = fast -> next;
}
return false;
} 
5、位翻转
翻转前：
| 数 | V8 | V7 | V6 | V5 | V4 | V3 | V2 | V1 |
|---|---|---|---|---|---|---|---|---|
| 位 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
翻转后：
| 数 | V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 |
|---|---|---|---|---|---|---|---|---|
| 位 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
思路：目标数初始化为0，用&0x01的方式获得原始数的第1位，然后左移7位再与目标数按位或，接着原始数右移一位；再用&0x01的方式获得原始数的第2位，然后左移6位……如此循环8次即可。最后返回目标数。
代码：
unsigned char bit_reverse(unsigned char input)
{
unsigned char result = 0;
int bit = 8;
while(bit--)
{
result |= ((input & 0x01) << bit);
input >>= 1;
}
return result;
}
6、字符串倒序：将一个字符串的字符顺序进行前后颠倒。
思路：双指针法，两个指针，一个指向字符串开头，另一个指向字符串结尾，相互交换指向的内容，接着头指针前进，尾指针后退，交换内容……直到两指针相遇。
#include<string.h>
void inverted_order(char *p)
{
char *s1, *s2, tem;
s1 = p;
s2 = s1 + strlen(p) - 1;
while(s1 < s2)
{
tem = *s1;
*s1 = *s2;
*s2 = tem;
s1++;
s2--;
}
}
7、找出一个字符串中一个最长的连续数字，并标注出位置和长度。
思路：指针法，指针从字符串开头开始寻找数字，若找到数字，则暂时记下位置，接着不断指向下一个字符，看连续的数字有多长，直到遇到非数字字符，然后比较长度是否比上一个连续数字长，若是则记录位置跟长度，接着寻找下一个数字，直到字符串结尾。最后返回最长的连续数字的位置和长度。
char *find(char *a, int *size)
{
char *in = a, *temp,*pos;
int count = 0, max = 0;
while(*in != '\0')
{
if(*in >= '0' && *in <= '9') // 寻找数字
{
temp = in;
while(*in >= '0' && *in <= '9') // 判断长度
{
count += 1;
in++;
}
if(count > max) // 记录最长连续数字的位置跟长度
{
pos = temp;
max = count;
}
count = 0;
}
in++;
}
*size = max;
return pos;
}
8、写一个函数，判断输入参数是不是质数（素数）。
思路：
（1）质数是指大于1的自然数中，除了1和它本身不再有其他因数的自然 数。一个大于1的自然数不是质数就是合数，因此可以将问题转换为判断合数。
（2）合数一定可以由两个自然数相乘得到，一个小于或等于它的平方根（大于1），另一个大于或等于它的平方根。因此可以判断“2 ~ 输入参数的平方根”中是否有能被输入参数整除的数，若有则该数是合数，若没有则该数是质数。
int IsPrime (unsigned int p)
{
unsigned int i;
if(p <= 1)
{
printf("请输入大于1的自然数。\n");
return -1;
}
for(i = 2; i <= sqrt(p); i++)
{
if(p % i == 0)
{
printf("该数不是质数。\n"); // 是合数
return 0;
}
}
printf("该数是质数。\n");
return 0;
}
9、大小端转化：对一个输入的整型数进行大小端存储模式转化
思路：大小端转化就是将一个整型数的低字节放到高字节，高字节放到低字节，跟前面的位翻转类似，只不过这里的单位是字节，因此需要将位翻转中的&0x01改为&0xFF，<< bit改为size * 8，>>= 1改为 >> 8。
int endian_convert(int input)
{
int result = 0;
int size = sizeof(input);
while(size--)
{
result |= ((input & 0xFF) << (size * 8));
input >>= 8;
}
return result;
}
10、已知两个已经从小到大排列的数组，将它们中所有的数组合成一个新的数组，要求新的数组也是按照从小到大排列的。
思路：原来的两个数组已经是顺序排列好的，那么为了减小时间复杂度，我们只需要新建一个数组，接着从后往前比较两个数组的元素的大小，并从后往前填充到新数组即可。时间复杂度为O(n)
代码：
int merge(int *array1, int len1, int *array2, int len2, int *array3)
{
int len3 = len1 + len2;
while(len1 > 0 && len2 > 0)
{
array3[len3-- - 1] = array1[len1 -1] > array2[len2 - 1] ? array1[len1-- - 1] : array2[len2-- -1]; // 比较数组元素大小并填充到新数组
}
while(len1 > 0) // 若数组1还有元素则依次填充
{
array3[len3-- - 1] = array1[len1-- - 1];
}
while(len2 > 0) // 若数组2还有元素则依次填充
{
array3[len3-- - 1] = array2[len2-- - 1];
}
return 0;
}
11、字符串排序问题，时间复杂度O(n)，任意字符串的排序并统计重复的个数，例如输入：$-%-#aeartvDEtGD%!%
输出：!1#1$1%3-2D2E1G1a2e1r1t2v1
思路：字符的ASCII码总共只有128个（0~127），那么我们是不是可以建立一个长度为128的数组并初始化为0，然后遍历每个字符，并以字符的ASCII为下标将该元素+1。这样一来，只需要遍历一遍字符串，就可以将字符串排好序并统计好个数。接下来在遍历一遍这个数组，将对应的字符和个数打印出来即可。（哈希表思维，将元素的值与其存储位置关联起来）
#include <stdio.h>
#include <string.h>
void sort(char a[], int len)
{
int i;
char b[128] = {0}, key;
for(i = 0; i < len; i++)
{
key = a[i]; // 将字符对应的ASCII码作为下标
b[key]++; // 对应元素+1
}
for(i = 0; i < 128; i++)
{
if(b[i] != 0)
printf("%c%d", i, b[i]); // 按顺序打印出字符跟个数
}
printf("\n");
}
12、写出二分查找的代码。
思路：二分查找是对有序数组而言的，那么我们只需要拿中间的元素来跟目标数值比较，如果相等则查找完成；如果中间的元素小于目标数值，那么说明目标元素在右边；如果中间的元素大于目标数值，那么说明目标元素在左边。接着再拿右边或左边的中间元素来比较……如此循环直到找到目标元素/找不到退出循环。时间复杂度为O(nlog2n)（二分思维）
int binary_search(int array[], int value, int size)
{
int low = 0;
int high = size -1;
int mid;
while(low <= high)
{
mid = (low + high) / 2; // 二分
if(array[mid] == value) // 中间数据是目标数据
return mid;
else if(array[mid] < value) // 中间数据比目标数据小
low = mid + 1;
else // 中间数据比目标数据大
high = mid - 1;
}
return -1;
}
13、写出快速排序的代码。
思路：数组一开始是乱序的，以第一个元素为基准，先将其保存；指针1从后往前寻<=基准的元素，插在基准元素的位置，接着指针2从前往后寻找>基准的元素，插在指针1的位置上；指针1继续往前寻找<=基准的元素，插在指针2的位置上，接着指针2继续往后寻找>基准的元素，插在指针1的位置上；如此循环直到两指针相遇，将基准元素插在相遇的位置，至此，<=基准的元素都在基准元素左边，>基准的元素都在基准元素右边，再递归地对左边的元素进行相同的操作，然后递归地对右边的元素进行相同的操作，即可完成排序，时间复杂度为O(nlog2n)。（二分思维、递归思维）
void quick_sort(int *num, int start_num, int end_num)
{
if(start_num < end_num)
{
int i = start_num;
int j = end_num;
int temp = num[start_num]; // 以第一个元素为基准
while(i < j)
{
while(i < j && num[j] > temp) // 从后往前寻找比基准小的元素
j--;
if(i < j)
num[i++] = num[j]; // 插在基准元素前面的空位上
while(i < j && num[i] <= temp) // 从前往后找比基准大的元素
i++;
if(i < j)
num[j--] = num[i]; // 插在基准元素后面的空位上
}
num[i] = temp; // 基准元素归位
quick_sort(num, start_num, i - 1); //递归地对基准元素左边的数据排序
quick_sort(num, i + 1, end_num); //递归地对基准元素右边的数据排序
}
}
14、数组a[N]，存放了数字1 ~ N-1，其中某个数重复一次。写一个函数，找出被重复的数字，时间复杂度必须为O(N)。
思路：数组有N个元素，刚好存放了数字1 ~ N –
1，那么是不是可以将数字与数组的下标对应起来存储，而重复的数字则刚好放在下标为0的位置。一开始假设a[0]是重复的数字，若不是则放到它该放的位置上，换另一个数字作为a[0]，若是则程序结束。如此循环，定能在N次循环内找到重复的数字。（哈希表思维，将元素的值与其存储位置关联起来）
int do_dup(int a[], int N)
{
int temp;
// a[0]为监视哨
while (a[0] != a[a[0]]) // 若两者相等，则说明该数字是重复数字
{
temp = a[0]; // 若不相等，则将该数放到以该数为下标的位置上
a[0] = a[temp]; // 该位置原来的数则放到0为下标的位置上
a[temp] = temp;
}
return a[0]; // 返回重复数字
}
