C语言与数据结构

使用C语言实现读写寄存器变量

#define rBANKCON0 *((volatile unsigned long *)0x48000004)

rBANKCON0 = 0x12;

在C语言中，凡是以#开头的都是预处理命令，同时预处理命令都是以#开头

预处理标识#error在编译程序时，只要遇到#error就会跳出一个编译错误

static关键字

修饰局部变量

修饰全局变量

修饰函数

typedef关键字

#define dPS struct s*

dPS p1,p2;

typedef struct s * dPS

dPS p1,p2;

前者定义了一个结构体指针和一个结构体，后者定义了两个结构体指针。

sizeof和strlen

sizeof用于计算变量所占的字节数,包含字符串的’\0’;

strlen用于计算字符串所占的字节数，但不包好’\0’;

extern关键字

跨文件引用全局变量

extern “C”

在C++中调用C函数

register关键字

被该关键字修饰的变量尽量存入寄存器中

const和#define的区别

const有数据类型，编译器可以对其做类型检查

define没有类型，只是在预处理阶段进行替换

定义一个有10个指针的数组，10个指针均指向函数，并且参数为int，返回值为int

int(*a[10])(int);

类型转换

无符号数和有符号数进行运算时，有符号数会被强制转换为无符号数。

指针题

1
2
int *a = (int *)2;
printf("%d", a+3);

输出14；

int为4字节，a每＋1等于＋4；

数组首元素地址和数组首地址

1
2
3
int a[10];
&a[10];//a+1为第二个元素的地址
&a;//a+1为向后移动40个字节

给定一个地址a，强制转换为函数指针

1
(int (*)(int))a;

赋值规则

长赋值给短：截取低位，按短整数的数据类型解析

短赋值给长：无符号数高位补零或有符号数高位补符号位

浮点转整形：截取整数部分

整形转浮点：小数部分为0

float和double之间；前者向后者转不会丢失精度，后者向前者转会丢失精度

整数在内存中以补码形式存储

C语言内存

栈区

存放函数的参数，局部变量

堆区

可动态申请的内存

数据段

全局变量和静态局部变量

bss段

未初始化或初始化为0的全局变量或静态局部变量

代码段

存放二进制代码或者字符串常量

大小端

大端

权重值大的放在低地址

优点

符号位在低地址的第一个字节中，便于快速判断数据的正负和大小

小端

权重值小的放在低地址。

优点

CPU做数值运算时依次从内存的低位到高位进行运算，这样效率更高。

判断大小端

1
2
3
4
5
6
7
8
9
void check()
{
    int a = 0x12345678;
    char *c = (char *)&a;
    if(*c == 0x12)
        printf("big endian");
    else if(*c == 0x78)
        printf("little endian");
}

全局变量和局部变量的区别

全局变量存放在数据段，生命周期为进程级

局部变量存放在栈区，生命周期只在函数内，退出函数时销毁

malloc底层实现

在操作系统中有一个可用内存块连接成的空闲链表，调用malloc时，函数遍历该链表寻找足够大的内存空间，将该空间一分为二，一块用户使用，一块返回链表，调用free函数时，内存重新连接回链表。

若内存块过于琐碎无法满足申请需求，操作系统会合并相邻内存块

在1G内存中可以通过malloc申请大于1G内存

malloc函数是在程序的虚拟地址空间申请的内存，操作系统可以通过虚拟内存技术扩大内存

内存泄漏

使用malloc申请的内存没有使用free函数进行回收

堆溢出和栈溢出

堆溢出

堆的尺寸设置的过小或者动态申请的内存没有释放

栈溢出

递归层次太深或者分配了过大的内存

位翻转

1
2
3
4
5
6
7
8
9
10
11
unsigned char bit_reverse(unsigned char num)
{
    unsigned char result = 0;
    int bit = 8;
    while(bit--)
    {
        result |= ((num&0x01)<<bit);
        num >>= 1;
    }
    return result;
}

memmove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void *memmove(void *dst, const void *src, size_t count)
{
    if(dst == NULL || src == NULL || count == 0)
        return NULL;
    if(dst < src)
    {
        char *d = (char *)dst;
        char *s = (char *)src;
        while(count--)
        {
            *d++ = *s++;
        }
    }
    else
    {
    	char *d = (char *)dst + count;
        char *s = (char *)src + count;
        while(count--)
        {
            *--d = *--s;
        }
    }
    return dst;
}

查找最长连续数字，并标出位置和长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;  
}

大小端转换

1
2
3
4
5
6
7
8
9
10
11
int endian_reverse(int num)
{
    int result = 0;
    int size = sizeof(num);
    while(size--)
    {
        result |= ((num&0xFF) << (size * 8));
        num >>= 8;
    }
    return result;
}

new和malloc的区别

new和delete是c++的操作符，malloc和free是c的标准库函数

c++允许重载这两个操作符，C不允许重载函数

new返回的是对象类型的指针，严格与对象匹配，malloc返回的是void *类型的指针，需要进行强制转换

new可以自动计算所申请的内存大小，malloc需要显式地给出内存大小

new操作符从自由存储区上动态分配内存，malloc从堆区分配内存

new分配失败会抛出异常，malloc分配失败会返回NULL

new/delete会调用对象的构造/析构函数，已完成对对象的构造/析构，而malloc不会

C语言代码优化

选择合适的数据结构与算法

使用尽可能小的数据类型

使用自加、自减指令

使用移位运算来实现乘除法运算

求余使用&

平方使用*

延时函数地自加改为自减

switch根据发生的频率来进行case排序

完全二叉树

当一个数除了最后一层外其他每一层的节点数都达到最大，且最后一层的叶子节点靠左排列时，即为完全二叉树。

平衡二叉树

当且仅当一个树两个子树高度相差不超过1时，即为平衡二叉树。

堆和栈的区别

栈是一种先进后出的数据结构，向下生长，栈中分配函数参数和局部变量

堆是一种经过排序的树形数据结构，向上生长，堆中动态分配内存空间

快慢指针的应用

判断链表是否有环

找出链表中的中间节点

数组a[N]，存放了数字1 ~ N-1，其中某个数重复一次。写一个函数，找出被重复的数字，时间复杂度必须为O(N)

1
2
3
4
5
6
7
8
9
10
11
int do_dup(int *a, int N)
{
    int tmp;
    while(a[0] != a[a[0]])
    {
        tmp = a[0];
        a[0] = a[tmp];
        a[tmp] = tmp;
    }
    return a[0];
}

ARM裸机开发

CPU内部结构

控制单元

运算单元

存储单元

时钟

虚拟内存

当系统需要的内存空间大于实际的物理空间时，就需要用到虚拟内存，虚拟内存可以将部分硬盘空间模拟成内存空间，将暂时不运行的程序和不使用的数据存储在硬盘上，需要时再将其存储到内存。

嵌入式微处理器和DSP的区别

微处理器偏控制，DSP偏运算，能进行大量数据的快速运算，适用于音视频处理等领域

ARM指令的状态

ARM状态：所有指令均为32位

Thunmb状态：所有指令均为16位

Thunmb-2状态：兼容16和32位指令

调试状态：处理机停机调试

RISC（精简指令集计算机）

CISC（复杂指令集计算机）

ARM总线

AHB

高速总线，用于连接高速外设

APB

低速总线，用于连接低速外设

中断

中断函数不能有参数和返回值

中断处理过程

中断请求

中断响应

保护现场

中断服务

恢复现场

中断返回

复位中断和其他中断的不同

复位中断产生后，系统自动从0地址重新开始执行程序，无需中断返回

中断向量

中断服务子程序的入口地址

中断嵌套

在中断服务函数中产生更高优先级的中断时，暂停当前中断服务程序，转去执行更高优先级的中断服务子程序，处理完成后再来处理当前的中断服务子程序。

中断优点

实现CPU和IO设备的并行工作，提高CPU的利用率

中断缺点

中断处理过程需要保护现场、恢复现场，整个过程需要一定的时间和空间开销。如果中断的频率太高，会降低系统的性能。

寄存器与存储器

通用寄存器

R0~R15,堆栈指针寄存器SP为R13,程序链接寄存器LR为R14，程序计数器PC为R15.

NOR FLASH

NAND FLASH

RAM

随机存储器，掉电丢失

SRAM

静态的随机存储器，加电情况下不需要刷新，数据不会丢失，一般用作CPU缓存

DRAM

动态的随机存储器，加电情况下需要不断刷新才能保存数据，一般用作系统内存

SDRAM

同步动态随机存储器，

CPU对cache读取DMA数据

CPU要先对cache做一个invalidate（作废）操作，再从内存中读取数据到缓存，保证缓存和内存中数据的一致性，才能读取DMA数据。

缓冲技术的作用

改善CPU与IO设备之间速度不匹配的矛盾呢

提高CPU和IO设备的并行性，提高系统的吞吐量和设备的利用率

减少CPU中断的频率，放宽对中断响应时间的限制

缓冲技术的种类

单缓冲，双缓冲，多缓冲，缓冲池

I/O接口

GPIO接口的寄存器

控制寄存器

数据寄存器

上拉寄存器

GPIO的输入输出模式

输入模式

浮空输入

带上拉输入

带下拉输入

模拟输入

输出模式

开漏输出

推挽输出

开漏复用输出

推挽复用输出

总线接口

UART

串行异步通信，全双工，小端模式

三根线：RX，TX，GND

USB

串行同步通信，半双工，小端模式

四根线：Vbus，GND，D+，D-

传输距离短

SPI

串行同步通信，全双工，大端模式

四根线：SCLK，SIMO，SOMI，SS（片选），大端模式

时钟相位CPOL

为0时空闲时SCLK为低电平，为1时SCLK为高电平

时钟极性CPHA

为0时在第一个边沿开始采样，为1时第二个边沿开始采样

IIC

串行同步通信，半双工，大端模式

两根线：SCL，SDA

传输距离短

空闲状态

SCL与SDA均为高电平，接上拉电阻

启动信号

SCL为高电平期间，SDA产生一个下降沿

数据位发送

SCL为高电平期间，SDA上电平保持稳定，高电平为数据1，低电平为数据0。

应答信号

SCL保持高电平期间，SDA保持低电平，iic总线上所有数据都是以8位一个字节传送，每发送一个字节，就在第九个时钟脉冲周期释放SDA，由接收器反馈一个ACK

非应答信号

SCL保持高电平期间，SDA保持高电平，接收到最后一个字节后，发送一个NACK

停止信号

SCL保持高电平期间，SDA产生一个上升沿

写数据步骤

发出启动信号（START）

主机发送7位从机地址＋一位读写位，1表示读，0表示写（0）

从机产生应答信号（ACK）

主机发送寄存器地址

从机产生应答信号（ACK）

主机发送一字节数据

从机发出应答信号（ACK）

发送完数据后主机产生停止信号（STOP）

读数据步骤

发出启动信号（START）

主机发送7位从机地址+一位读写位，1读，0写（0）

从机产生应答信号（ACK）

主机发送寄存器地址

从机应答（ACK）

发出启动信号（START）

再次发出7位从机地址+一位读写位，1读，0写（1）

从机应答（ACK）

读取一字节数据

主机产生一个非应答信号（NACK）

读取完成后发出停止信号（STOP）

异步串行

以字符为单位传送信息，字符内部各位同步，字符间异步，发送时钟和接收时钟相近即可

同步串行

以数据块为单位传送信息，在字符块内，字符之间无间隔，字符内部同步，字符间也同步，接收时钟和发送时钟需要严格同步

串口发送浮点数据

使用共用体发送

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
union  
{  
    float f;  
    unsigned long l;  
}data_TX;  
data_TX.f = 123.456;  
TX = (unsigned char)data_TX.l;       // 低8位  
TX = (unsigned char)(data_TX.l >> 8);  
TX = (unsigned char)(data_TX.l >> 16);  
TX = (unsigned char)(data_TX.l >> 24);  // 高8位 
union  
{  
    float f;  
    unsigned long l;  
}data_RX;  
data_RX.l = RX;      // 低8位  
data_RX.l |= RX << 8;  
data_RX.l |= RX << 16;  
data_RX.l |= RX << 24; // 高8位  
data_RX.f == data_TX.f;

UART和TTL、RS-232、RS-485的关系

UART是一种具有特征协议的收发器，一个按照特定协议来收发数据的硬件。

其余三者为三种不同的电气协议，UART可以使用这三种电平

TTL

+5V或>=2.4V为逻辑1

0V或<=0.4V为逻辑0

RS232

-5V~-15V为逻辑1

5V~15V为逻辑0

RS485

A线比B线电平高200mV为逻辑1

A线比B线电平低200mV为逻辑0

UART如何保证数据传输的正确性

在数据的两端添加起始位，奇偶校验位，停止位用于数据的同步和纠错

MSB

最高有效位，是指二进制中最高值的比特

LSB

最低有效位，是指二进制中最低值的比特

UART一帧可以传5/6/7/8位，IIC必须是8位，SPI可以8/16位

两种串行通信方式

异步

UART

同步

SPI，IIC，USB

串行通信占用资源少，线间干扰小，并行速度快但占用资源多，线间干扰大

应用编程与网络编程

进程&线程

同步IO与异步IO

同步IO

当一个IO操作执行时，应用程序必须等待IO执行完

异步IO

IO操作和应用程序可以同时运行，提高系统性能

进程间通信方式

管道

半双工通信，数据只能单向流通，通常只能在父子进程之间使用

有名管道

允许除父子进程之间的进程使用

信号量

用于进程之间的同步

消息队列

共享内存

一段能够被多个进程共同访问的内存，由一个进程创建。是最快的进程间通信方式，通常配合信号量来使用

套接字

用于不同主机间的通信

信号

用于通知接收进程某个事件已经发送

进程的地址空间模型

代码段

用于存储代码和字符串常量

数据段

存储初始化不为0的全局变量和静态局部变量、const型常量

bss段

存储未初始化或初始化为0的全局变量和静态局部变量

堆区

用于动态申请的内存

栈区

存储函数参数，局部变量

进程的五种状态

就绪态

所有运行条件已经就绪，只要得到cpu就可运行

运行态

得到CPU并正在运行

僵尸态

进程已经结束但父进程没有来得及回收其资源

暂停态

暂时停止参与CPU的调度

子进程可以从父进程继承的资源

堆栈，内存，用户号，组号，打开的文件描述符，当前工作目录、根目录

进程上下文

上文

进程由用户态切换到内核态时需要保存用户态时CPU寄存器中的值，进程状态以及堆栈上的内容，即保存当前进程的状态，以便再次执行该进程时，能够恢复到切换时的状态，继续执行

下文

切换到内核态后执行的程序

中断上下文

上文

和进程相似

下文

执行在内核空间的中断服务程序

进程和线程的区别

进程是系统中程序执行和资源分配的基本单位，线程是CPU调度的基本单位

一个进程可以拥有多个线程，线程可以访问其所属进程的地址空间和系统资源，同时也可以拥有自己的堆栈

同一个进程内的多个线程可以共享同一地址空间，因此通信实现比较简单，而且切换开销小，创建和消亡的开销也小

多进程和多线程的应用场景

当程序的安全性、稳定性要求较高时使用多进程

需要频繁通信/切换/创建和销毁时使用多线程

线程属于进程，运行需要依赖进程的地址空间和系统资源，线程崩溃的本质是内存出错，若出错的内存没有被其他进程访问，则不会导致其他内存出错，也就不会导致进程崩溃。

线程间的通信方式

信号、信号量、互斥锁、条件变量、自旋锁、读写锁

如何防止同时产生大量的线程

使用线程池

互斥锁与信号量的区别

信号量用于线程间的同步，互斥锁用于线程互斥

信号量可以为非负整数，可以实现多个同类资源的多线程同步，互斥锁只能为0/1，只能用于一个资源的互斥访问

信号量可以由一个线程释放，另一个线程得到。互斥锁的加锁和解锁必须由同一线程分别对应使用，且多个线程使用多个互斥锁必须统一顺序，否则可能造成死锁。

孤儿进程

父进程先于子进程结束，此时子进程成为一个孤儿进程

网络编程

OSI协议分层

七层

应用层，表示层，会话层，传输层，网络层，数据链路层，物理层

五层

应用层，传输层，网络层，数据链路层，物理层

四层

应用层，传输层，网络层，网络接口层

TCP/IP协议

应用层，传输层、网络层、网络接口层

建立和释放

建立

三次握手

释放

四次挥手

IP地址转换成物理地址

ARP地址解析协议

IP地址的编码

分为网络号和主机号

ping发出的报文

ICMP请求报文

SOCKET编程流程

服务端

创建套接字，绑定本地IP地址和端口号，设置监听队列长度，等待连接，接收消息，关闭套接字

客户端

创建套接字，发送请求连接，发送信息，关闭套接字

TCP/UDP的区别

TCP是面向连接的，UDP是面向无连接的

TCP是面向字节流的，UDP是基于数据报的

TCP提供可靠服务，UDP提供不可靠服务

TCP程序结构复杂，占用资源多，UDP程序结构简单，占用资源少

TCP拥有阻塞控制，UDP没有阻塞控制，因此网络出现阻塞不会使源主机发送速率降低，适用于实时应用，如IP电话，实时视频会议

TCP只支持一对一，UDP支持一对一、一对多、多对一、多对多

TCP，UDP各自的优缺点

TCP

优点：稳定可靠

缺点：效率低，占用资源高。

UDP

优点：效率高，占用资源少，传输速度快

缺点：不稳定，不可靠，网络不好时容易丢包

各自适用场景

TCP

对数据传输质量要求高，对实时性要求不高，如HTTP、FTP等传输协议

UDP

对实时性要求高，数据质量要求不高，如在线视频电话

socket网络编程五元组

客户端端口，客户端IP，服务端端口，服务端IP，传输协议

操作系统

MMU的作用

地址映射

内存分配和回收

内存保护

内存扩充