第一讲：数据结构与函数基础
本笔记基于课程第一讲内容整理，涉及数据结构的基本概念、软件逻辑与函数基础。
一、数据存储基础
1.1 数据的存放位置
-
内存：用于存储当前正在运行和处理的数据，访问速度快，但断电后数据丢失。
-
硬盘：用于持久化存储数据，速度较慢，但数据可以长期保存。
1.2 云计算简介
-
云：指将大量服务器资源汇集起来形成的资源池。
-
计算：通过合理分配与捆绑资源，提供高效的计算服务。
二、数据结构与算法
2.1 数据结构的定义
数据结构是计算机中组织、管理和存储数据的方式，它使得数据可以高效地被访问和修改。
2.2 算法的定义
算法是解决特定问题的一系列清晰指令，是程序执行的逻辑描述。数据结构与算法的结合，构成了程序设计的核心。
Donald Knuth 的名言（1984 年图灵奖获得者）：
“程序 = 数据结构 + 算法”
三、软件逻辑与业务实现
在网页或 App 业务中，数据结构主要体现在如何将业务数据以特定的形式组织和存储在数据库中。
四、后续学习内容概览
课程将逐步涵盖以下内容，构建完整的知识体系：
五、前置知识要求
学习本课程前，建议掌握以下基础知识：
六、函数基础
6.1 函数的作用
函数是一段可重复调用的代码块，用于实现特定功能，提高代码的复用性与可读性。
6.2 函数的设计原则
函数是否需要参数、是否需要返回值，取决于具体的功能需求。设计时应遵循“单一职责”原则，确保每个函数只完成一件明确的任务。
笔记整理说明：
对原文进行了结构化排版，统一了标题层级；
优化了部分语句的表达，使其更通顺易懂；
保留了所有原图链接，并为其添加了简短的描述性文字；
对技术术语与名人引言做了突出与保留，确保准确性。
第二讲：字符串、内存与数组
一、回车与换行的区别
-
回车（
\r）：将光标移动到当前行的行首 -
换行（
\n）：将光标移动到下一行的相同列位置
注：虽然现代系统中通常使用
\n表示换行，但了解两者的历史区别有助于理解不同系统的文本处理差异。
二、字符串基础
2.1 C语言中的字符串表示
C语言没有内置的string类型，而是使用字符数组来表示字符串。
字符与字符串的区别：
-
'a'：字符（单引号） -
"a"：字符串（双引号，实际包含字符’a’和结束符’\0’）
存储特点： char类型占用1字节，这种设计在资源受限的环境中很有优势。
2.2 字符编码
不同的字符编码方式：
-
ASCII编码：基础英文字符
-
UTF-8：变长Unicode编码
-
UTF-32：定长Unicode编码
-
GBK：中文编码标准
2.3 字符串初始化
错误示范：
char str[10];
str = "Hello"; // 错误：数组名不能直接赋值
正确方法：
#include <stdio.h>
#include <string.h>
int main()
{
// 方法1：声明时初始化
char str1[] = "HelloWorld";
printf("%s\n", str1);
// 方法2：使用strcpy函数
char str2[11]; // 包含'\0'结束符
strcpy(str2, "HelloWorld");
printf("%s\n", str2);
// sizeof vs strlen
printf("sizeof(str2) = %zu\n", sizeof(str2)); // 数组总大小：11
printf("strlen(str2) = %zu\n", strlen(str2)); // 字符串长度：10（不含'\0'）
return 0;
}
三、内存管理
3.1 冯·诺依曼体系结构
计算机的基本组成包括运算器、控制器、存储器、输入设备和输出设备。
3.2 虚拟内存地址
操作系统将物理内存抽象为连续的虚拟地址空间，就像一个巨大的一维数组。
地址空间大小：
-
32位系统：最多寻址 2³² ≈ 4GB 内存
-
64位系统：最多寻址 2⁶⁴ ≈ 16EB 内存
3.3 栈内存（Stack）
栈内存用于存储局部变量和函数调用信息，遵循"后进先出"原则。
重要概念：
int a = 5, b = 10;
-
字面量
5和10也有临时内存空间 -
赋值是将值复制到变量
a和b的空间 -
字面量的无名空间在语句结束后立即释放
-
局部变量在函数结束后释放
四、数组
4.1 数组基础
数组是相同类型元素的集合，具有以下特点：
-
长度在定义后不可改变
-
元素通过下标访问（从0开始）
-
内存地址连续
4.2 数组的地址连续性
数组元素在内存中是连续存储的：
int main()
{
int a[10];
printf("a[0]地址: %p\n", &a[0]);
printf("a[1]地址: %p\n", &a[1]);
printf("a[2]地址: %p\n", &a[2]);
printf("a[3]地址: %p\n", &a[3]);
// 地址依次相差sizeof(int)字节
return 0;
}
传参原理：数组作为参数传递时，实际传递的是数组首元素的地址。
4.3 获取数组长度
由于数组名在大多数情况下会退化为指针，需要用特殊方法获取数组长度：
int a[10];
size_t length = sizeof(a) / sizeof(a[0]);
-
sizeof(a)：获取数组总字节数 -
sizeof(a[0])：获取单个元素字节数 -
注意：
sizeof返回类型为size_t，应使用%zu格式化输出
五、补充说明
-
Linux系统底层：主要使用C89/C90标准编写
-
C语言特点：允许直接操作内存，提供底层控制能力
-
数据类型对齐：不同系统可能有不同的内存对齐要求
第三讲：指针与结构体详解
一、指针基础
1.1 指针的概念
指针是存储内存地址的变量，通过指针可以间接访问和操作内存中的数据。
1.2 指针的基本操作
声明与初始化指针：
int a = 10; // 普通整型变量
int *p = &a; // 指针变量，存储a的地址
关键图示：
1.3 解引用操作符（*）
解引用操作用于通过指针访问或修改其指向内存中的数据。
代码示例：
int a = 10;
int *p = &a;
*p = 20; // 通过指针修改变量a的值
printf("%d", a); // 输出：20
解引用过程：
二、指针与数组
2.1 指针与数组的紧密关系
在C语言中，数组名在大多数情况下会退化为指向数组首元素的指针。
2.2 指针算术运算
指针的加减运算不是简单的数值加减，而是根据指针类型的大小进行调整：
int arr[5];
int *p = arr; // p指向arr[0]
p++; // p现在指向arr[1]，实际地址增加sizeof(int)字节
2.3 常见数据类型的大小
三、指针与函数
3.1 通过指针实现函数间数据交换
#include <stdio.h>
// 错误示例：传值调用
void swap(int a, int b) {
int temp = a;
a = b;
b = temp;
// 只交换了局部副本，不影响原变量
}
// 正确示例：传指针调用
void swap_point(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
// 直接操作原内存位置
}
int main() {
int m = 5, n = 10;
// swap(m, n); // 无效
swap_point(&m, &n); // 有效
printf("m = %d, n = %d\n", m, n); // 输出：m = 10, n = 5
return 0;
}
重要结论：
-
传递变量值：创建副本，不影响原变量
-
传递指针：直接操作原变量内存位置
四、结构体（struct）
4.1 结构体的定义与使用
结构体允许将不同类型的数据组合成一个整体。
#include <stdio.h>
#include <string.h>
// 定义结构体类型
struct hero {
char heroName[30];
double red;
double blue;
double attack;
double attackSpeed;
};
int main() {
// 创建结构体变量
struct hero h1;
strcpy(h1.heroName, "liubei");
h1.red = 100.0;
h1.blue = 100.0;
h1.attack = 60.0;
h1.attackSpeed = 10.0;
// 结构体数组
struct hero hs[4];
hs[0] = h1; // 结构体支持直接赋值
return 0;
}
4.2 类型定义（typedef）
使用typedef为类型创建别名，提高代码可读性。
#include <stdio.h>
// 为结构体创建别名
typedef struct student {
char stuID[15];
char stuName[10];
int age;
} student_t; // 别名
int main() {
student_t s; // 使用别名声明变量
return 0;
}
五、函数传递指针的优势
5.1 传指针 vs 传值
// 传值：复制整个结构体（低效）
void initStu(student_t s) {
// 操作副本，不影响原变量
}
// 传指针：仅传递地址（高效）
void initStuPtr(student_t *p) {
strcpy(p->stuID, "190818115");
strcpy(p->stuName, "xiaoming");
p->age = 18;
}
int main() {
student_t s;
initStuPtr(&s); // 传递指针
return 0;
}
5.2 传指针的优势分析
1. 避免数据复制，提升性能
typedef struct {
char name[2000]; // 大字符串
int score;
} Student;
void update(Student s) { // A方式：传值
// 复制2000+字节，低效
s.score = 100;
}
void update_ptr(Student *ps) { // B方式：传指针
// 仅复制8字节地址，高效
ps->score = 100;
}
物理层面分析（电子系视角）：
-
B方式（传指针）：CPU只需移动8字节地址数据，约1个时钟周期
-
A方式（传值）：需要搬运2000字节数据，消耗数百个时钟周期，占用数据总线，增加功耗
2. 允许修改原数据
-
传值：只能操作副本
-
传指针：可直接修改原内存
3. 节省栈内存
-
任何指针（64位系统）都是8字节
-
大型结构体可能占用数百至数千字节
六、内存管理深度解析
6.1 内存区域划分
| 区域名称 | 物理位置 | 存储内容 | 特点 | 生命周期 |
|---|---|---|---|---|
| 栈区 (Stack) | RAM | 局部变量、函数参数、返回地址 | 自动分配/释放，速度快，空间小 | 函数调用期间 |
| 堆区 (Heap) | RAM | malloc申请的内存 |
手动分配/释放，空间大，速度较慢 | 直到free()调用 |
| 静态/全局区 | RAM | 全局变量、静态变量 | 程序启动即存在 | 整个程序运行期间 |
| 代码区 (Text) | RAM/Flash | 程序指令 | 只读，防止运行时修改 | 程序加载到卸载 |
6.2 动态内存分配
malloc函数原型：
void* malloc(size_t size); // size_t为无符号整数，表示字节数
使用示例：
int *p = (int*)malloc(sizeof(int)); // 分配一个整型空间
int *arr = (int*)malloc(10 * sizeof(int)); // 分配10个整型数组
6.3 栈内存 vs 堆内存
void example() {
int a; // 栈内存，自动分配
int *p = &a; // 指针p也在栈中
int *b = (int*)malloc(sizeof(int)); // 堆内存，手动分配
// 使用b...
free(b); // 必须手动释放
}
七、数组、字符串与指针的关系
7.1 数组名作为指针
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 传递数组实际上传递的是首地址
void print_array(int *a, int size) {
for(int i = 0; i < size; i++) {
printf("%d ", a[i]);
}
}
// 字符串也是字符数组
void print_string(char *s) {
for(int i = 0; s[i] != '\0'; i++) {
printf("%c", s[i]);
}
}
int main() {
// 动态分配字符串
char *s = (char*)malloc(10);
strcpy(s, "Hello");
// 静态数组
int arr[] = {21, 31, 315, 5};
print_array(arr, 4); // 数组名即首地址
print_string(s);
free(s); // 释放堆内存
return 0;
}
核心理解：数组名在大多数上下文中会退化为指向其首元素的指针。
八、电子系特别视角：嵌入式系统中的内存管理
8.1 各内存区域的硬件对应
| 区域名称 | 物理位置 | 存什么？ | 特点 |
|---|---|---|---|
| 栈区 | RAM | 局部变量、函数参数 | 自动分配，依赖SP寄存器，速度极快 |
| 堆区 | RAM | malloc申请的空间 |
手动管理，可能产生内存碎片 |
| 数据区 | RAM | 全局/静态变量 | 编译时确定，程序启动即存在 |
| 代码区 | Flash/RAM | 程序指令 | 通常存储在Flash，运行时加载到RAM |
8.2 嵌入式开发中的注意事项
1. 栈溢出（Stack Overflow）
-
现象：单片机突然复位
-
原因：局部变量（特别是大数组）超出栈空间
-
硬件表现：SP指针越界，触发HardFault异常
void dangerous_function() {
int huge_array[10000]; // 可能超出单片机栈空间！
// 运行到此函数时可能触发复位
}
2. 堆内存的尴尬
-
内存碎片问题：频繁
malloc/free导致内存碎片 -
实时性问题：
malloc执行时间不确定 -
行业实践：高可靠性系统（汽车电子、飞控）常禁止动态内存分配
3. 虚拟内存的真相
-
物理现实：硬盘作为持久化存储，断电不丢失
-
虚拟内存：操作系统用硬盘模拟内存（交换分区）
-
嵌入式限制：大多数单片机无虚拟内存机制
8.3 实战练习：传感器数据采集器
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 1. 定义结构体
typedef struct {
int sensor_id;
float temperature;
float humidity;
} SensorData_t;
// 4. 初始化函数（传指针）
void init_sensor(SensorData_t *sensor, int id, float temp, float hum) {
sensor->sensor_id = id;
sensor->temperature = temp;
sensor->humidity = hum;
}
int main() {
// 3. 在堆区申请内存
SensorData_t *data = (SensorData_t*)malloc(sizeof(SensorData_t));
if (data == NULL) {
printf("内存分配失败！\n");
return -1;
}
// 4. 初始化结构体
init_sensor(data, 1, 25.5, 60.2);
// 打印数据
printf("传感器ID: %d\n", data->sensor_id);
printf("温度: %.1f°C\n", data->temperature);
printf("湿度: %.1f%%\n", data->humidity);
// 5. 释放内存
free(data);
return 0;
}
8.4 避坑指南：常见错误分析
场景A：返回局部变量地址
int* get_data() {
int temp = 36; // 栈内存变量
return &temp; // 错误：函数结束temp被释放
}
int main() {
int *p = get_data();
printf("%d", *p); // 未定义行为！可能崩溃或输出随机值
return 0;
}
场景B：内存泄漏
void create_node() {
int *ptr = (int*)malloc(sizeof(int) * 100);
// 使用ptr...
// 忘记free(ptr)!
return; // 函数结束，ptr丢失，100*sizeof(int)字节永远泄漏
}
后果：如果create_node在循环中频繁调用，堆内存逐渐耗尽，最终导致：
-
malloc返回NULL -
程序崩溃
-
在嵌入式系统中，设备可能死机或复位
九、总结与最佳实践
9.1 指针使用要点
-
始终初始化指针：避免野指针
-
检查
malloc返回值：防止分配失败 -
配对使用
malloc/free：防止内存泄漏 -
避免返回局部变量地址：函数结束栈内存被回收
9.2 结构体设计建议
-
使用
typedef创建类型别名：提高可读性 -
按数据类型对齐：提高访问效率
-
考虑内存占用：嵌入式系统中特别重要
-
传指针而不是传值：提高性能，节省内存
9.3 嵌入式开发特别提示
-
慎用动态内存：优先使用静态分配
-
监控栈使用：避免栈溢出
-
理解硬件限制：不同MCU内存布局不同
-
性能与可靠性平衡：有时需要牺牲灵活性保证稳定性
优化说明：
-
结构化重组，逻辑更清晰
-
代码示例添加详细注释
-
针对电子系背景深化硬件相关知识
-
补充实际工程中的注意事项
-
添加实战练习和常见错误分析
-
强调嵌入式开发中的特殊考量
第四讲：数组指针和二级指针
一、字符串和数组的联系
基本概念
在C语言中，字符串本质上是以'\0'结尾的字符数组。数组名在大多数情况下会退化为指向数组首元素的指针。
代码示例与分析
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 传递整型数组参数的方式
// 参数1：数组首地址，参数2：数组元素个数
void fun(int *a, int n)
{
for(int i = 0; i < n; i++)
{
// 两种等价的访问方式
printf("%d ", *(a+i)); // 指针算术运算
// printf("%d ", a[i]); // 数组下标访问
}
printf("\n");
}
// 传递字符数组（字符串）参数
void fun2(char *s)
{
for(int i = 0; i < 6; i++)
{
printf("%c ", s[i]); // 通过下标访问字符
}
printf("\n");
}
int main()
{
// 1. 动态分配字符串（堆内存）
char *s = (char *)malloc(6 * sizeof(char)); // 分配6个字符空间
strcpy(s, "Hello");
printf("动态字符串: %s\n", s);
// 2. 栈上整型数组
int arr[] = {324, 78, 45, 98, 5};
printf("整型数组元素: ");
fun(arr, sizeof(arr) / sizeof(arr[0])); // 计算数组元素个数
// 3. 栈上字符数组
char s1[6] = "Hello"; // 自动包含'\0'结束符
printf("栈字符数组: ");
fun2(s1);
printf("堆字符数组: ");
fun2(s); // 堆内存同样可以像数组一样访问
free(s); // 释放动态分配的内存
return 0;
}
关键要点
-
数组名作为指针：数组名在函数调用时会退化为指向首元素的指针
-
数组传递的本质：传递的是数组首地址，不是整个数组
-
sizeof操作符：在函数内部无法通过
sizeof获取数组大小，需要额外传递大小参数 -
栈数组 vs 堆数组：两者在函数参数传递时用法相同
二、动态内存分配数组
动态内存的重要性
在软件开发中，动态内存分配允许：
-
在运行时确定数组大小
-
更灵活的内存管理
-
避免栈溢出问题
代码示例与分析
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 传递整型数组（已知道大小）
void fun(int *a)
{
for(int i = 0; i < 4; i++)
{
printf("%d ", a[i]); // 数组下标表示法
}
printf("\n");
}
// 传递字符串
void fun_str(char *s)
{
// 安全地遍历字符串（避免越界）
for(int i = 0; i < strlen(s); i++) // 使用strlen获取实际长度
{
printf("%c ", s[i]);
}
printf("\n");
// 或者使用指针遍历
// while(*s != '\0') {
// printf("%c ", *s);
// s++;
// }
}
int main()
{
// 动态分配字符串
char *s = (char*)malloc(10 * sizeof(char)); // 分配10个字符空间
if(s == NULL) {
printf("内存分配失败!\n");
return 1;
}
strcpy(s, "Hello");
printf("动态字符串: %s\n", s);
// 栈上整型数组
int arr[] = {21, 31, 315, 5};
printf("整型数组: ");
fun(arr); // 数组名退化为指针
printf("字符串遍历: ");
fun_str(s);
free(s); // 必须释放动态分配的内存
s = NULL; // 避免野指针
return 0;
}
注意事项
-
内存分配检查：
malloc可能返回NULL，需要检查分配是否成功 -
内存释放：动态分配的内存必须手动释放
-
内存泄漏：忘记释放内存会导致内存泄漏
-
野指针：释放后应将指针置为
NULL
三、二级指针
问题的引出：为什么需要二级指针？
#include <stdio.h>
#include <stdlib.h>
// 错误示例：无法修改调用者的指针
void fun(int *temp)
{
temp = (int*)malloc(sizeof(int)); // 这里的temp是局部变量
*temp = 100; // 修改的是局部指针指向的内容
}
int main()
{
int *p = NULL;
fun(p); // p本身的值没有被改变
printf("%d\n", *p); // 运行时错误：访问NULL指针
return 0;
}
解决方案：使用二级指针
#include <stdio.h>
#include <stdlib.h>
// 正确示例：使用二级指针修改调用者的指针
void fun(int** temp) // 参数是二级指针
{
// *temp 解引用一次，得到main函数中的p指针
*temp = (int*)malloc(sizeof(int));
if(*temp != NULL) {
**temp = 100; // 解引用两次，修改实际的内存值
}
}
int main()
{
int *p = NULL;
fun(&p); // 传递指针的地址
if(p != NULL) {
printf("值: %d\n", *p);
free(p);
p = NULL; // 避免野指针
}
return 0;
}
二级指针的图示
二级指针的核心概念
-
指针的指针：二级指针存储的是指针变量的地址
-
解引用层级：
-
temp：二级指针变量 -
*temp：一级指针（例如main函数中的p） -
**temp：实际的数据值
-
实际应用场景
-
在函数内部分配内存并返回给调用者
-
修改指针数组的内容
-
动态创建二维数组
-
函数返回多个指针结果
扩展示例：动态创建字符串数组
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 创建字符串数组
void create_string_array(char ***arr, int n) {
*arr = (char**)malloc(n * sizeof(char*));
for(int i = 0; i < n; i++) {
(*arr)[i] = (char*)malloc(20 * sizeof(char));
sprintf((*arr)[i], "String%d", i+1);
}
}
// 释放字符串数组
void free_string_array(char ***arr, int n) {
for(int i = 0; i < n; i++) {
free((*arr)[i]);
}
free(*arr);
*arr = NULL;
}
int main() {
char **strings = NULL;
int count = 3;
create_string_array(&strings, count);
for(int i = 0; i < count; i++) {
printf("%s\n", strings[i]);
}
free_string_array(&strings, count);
return 0;
}
四、总结与最佳实践
关键要点总结
-
数组与指针的关系：数组名在多数情况下退化为指针
-
函数参数传递：数组通过传递首地址实现
-
动态内存管理：
malloc/free必须成对使用 -
二级指针用途：用于在函数内修改调用者的指针变量
编程建议
-
使用
sizeof计算数组大小时要小心 -
动态分配内存后总是检查返回值
-
释放内存后将指针置为
NULL -
考虑使用
const修饰符保护不应修改的数据 -
对于字符串操作，优先使用安全函数（如
strncpy代替strcpy）
练习建议
-
实现一个函数，使用二级指针动态创建二维数组
-
编写一个字符串处理函数集，包含动态字符串的创建、修改和释放
-
理解并实现一个简单的内存池管理器
通过深入理解数组指针和二级指针，你将能够更好地管理内存、编写更灵活的C程序，并为学习更复杂的数据结构打下坚实基础。
第五讲：算法分析
本讲学习内容
时间复杂度
空间复杂度
抽线数据类型ADT(Abstract Data Type)
算法的执行效率
计算机性能 和 算法效率 都很重要
这就是个很好的例子
科普： bench marksort， 是个有名的世界排序比赛
时间复杂度
要理解：时间和算法复杂度是成正比的，时间越长，算法越复杂