C语言内功修炼：打通语法、内存、数据结构，制胜牛客&大厂面试：征服字节腾讯面试完整指南 牛客热题101 + 腾讯字节核心考点精讲 C语言核心知识点与实战精讲
这篇C语言教程涵盖了从基础语法到高级特性的全面内容，分为两个部分： 第一部分重点讲解了C语言基础语法、内存管理（指针和动态内存分配）、数组与字符串、结构体与联合体、预处理指令以及链表和二叉树等基本数据结构。 第二部分深入探讨了高级指针应用（函数指针和多级指针）、栈/队列/哈希表等高级数据结构、排序与查找算法、文件I/O操作、错误处理与调试技巧，并针对牛客网热门面试题和大厂面试常见问题进行了详细解析
小引子——为什么是C语言？
在编程语言的百花园中，C语言无疑是那块坚实而永恒的基石。它诞生于20世纪70年代，以其高效、灵活、贴近硬件的特性，深刻影响了后世几乎所有主流编程语言的设计。
从操作系统内核（如Linux）、嵌入式系统、游戏引擎，到高性能计算和底层驱动开发，C语言的身影无处不在。
你或许会问，在Python、Java、Go等高级语言大行其道的今天，学习C语言还有必要吗？
答案是：绝对必要，尤其对于志在进入大厂、深耕计算机领域的你！
掌握C语言，意味着你拥有：
-
直击底层： 理解计算机内存管理、指针操作的本质，这是理解高级语言内部机制的关键。
-
性能优势： 编写高性能代码的能力，这是许多对速度有极致要求的场景不可或缺的。
-
算法与数据结构基石： C语言是学习和实现各种复杂算法与数据结构最纯粹的载体，帮助你构建扎实的编程内功。
-
面试利器： 无论是牛客热题101必刷榜，还是大厂面试，C语言（或C++）的考察都是衡量一个程序员基础功底的重要标准。对指针、内存、数据结构的理解，往往是区分高手的关键。
本教程将以“牛客热题面试101必刷榜”和“大厂C语言面试”为导向，带你全面深入C语言的核心知识点，并提供大量实战代码示例和解析。在第一部分，我们将聚焦于C语言的语法基础、内存管理、指针的精髓以及经典数据结构的实现！！！
当然了有本作者两个月手敲的八万行代码带你彻头彻尾的把C给玩透吃透，永远都不怕面试的拷打！！！
到时候如果大家反应不错我将会把我自己的这些核心源码全部开源！
一、C语言基础：构建你的代码骨架
学习任何一门语言，都始于其基本语法。C语言的语法相对简洁，但其对底层的抽象能力使其功能强大。
1.1 第一个C程序：Hello World
让我们从经典的“Hello World”开始，这是所有编程语言的起点。
// 文件名: hello_world.c
// 目的: 演示最简单的C语言程序结构
#include <stdio.h> // 包含标准输入输出库，提供了printf函数
int main() { // main函数是程序的入口点
// printf是一个库函数，用于向标准输出（通常是屏幕）打印格式化的文本
printf("Hello, World!\n"); // 打印字符串，\n表示换行
return 0; // main函数返回0表示程序成功执行
}
代码解析：
-
#include <stdio.h>：这是一个预处理指令。#include告诉编译器在编译前把stdio.h文件的内容包含进来。stdio.h（standard input-output header）是C标准库中用于处理输入和输出的头文件，其中包含了printf函数的声明。 -
int main()：这是C程序的主函数。所有C程序都从main函数开始执行。int表示main函数返回一个整数类型的值，通常用来表示程序的退出状态（0表示成功，非0表示错误）。括号()表示main函数不接受任何参数。 -
{ }：花括号定义了函数体，其中包含程序的执行语句。 -
printf("Hello, World!\n");：这条语句调用了printf函数，将字符串 "Hello, World!" 打印到屏幕上。\n是一个转义序列，表示换行符。 -
return 0;：这表示main函数执行完毕，并返回整数值0。
编译与运行：
你需要一个C编译器（如GCC）来编译C代码： gcc hello_world.c -o hello_world 然后运行生成的可执行文件： ./hello_world
1.2 基本数据类型、变量与常量
C语言是静态强类型语言，这意味着在使用变量之前必须声明其类型，并且类型一旦确定就不能改变。
A. 基本数据类型：
|
类型 |
描述 |
常见占用字节数（取决于编译器和系统） |
取值范围示例（32位系统） |
|---|---|---|---|
|
|
字符类型，通常用于存储单个字符或小整数 |
1字节 |
-128 到 127 或 0 到 255 |
|
|
短整型 |
2字节 |
-32768 到 32767 |
|
|
整型，最常用的整数类型 |
4字节 |
±2×109 左右 |
|
|
长整型 |
4或8字节 |
±2×109 或 ±9×1018 |
|
|
更长的整型（C99标准引入） |
8字节 |
±9×1018 左右 |
|
|
单精度浮点型 |
4字节 |
1.2E−38 到 3.4E+38 |
|
|
双精度浮点型，常用 |
8字节 |
2.3E−308 到 1.7E+308 |
|
|
布尔类型（C99标准引入，头文件 |
1字节 |
0（false）或 1（true） |
修饰符：
-
signed/unsigned：用于修饰整数类型，表示是否有符号。unsigned类型只能表示非负数，但可以扩大正数范围。 -
const：定义常量。 -
static：定义静态变量。 -
extern：声明外部变量。 -
volatile：告知编译器变量可能被意外修改。
B. 变量的定义与初始化：
变量是程序中用来存储数据的命名存储区域。
// 变量的定义和初始化
int age; // 定义一个整型变量age，未初始化，其值是不确定的（垃圾值）
float price = 19.99f; // 定义并初始化一个单精度浮点型变量price，注意f后缀
double pi = 3.1415926535; // 定义并初始化一个双精度浮点型变量pi
char grade = 'A'; // 定义并初始化一个字符变量grade
int count = 0; // 定义并初始化一个整型变量count
// 使用printf格式化输出
printf("Age: %d\n", age); // %d 用于输出整型
printf("Price: %.2f\n", price); // %.2f 表示输出浮点数并保留两位小数
printf("PI: %lf\n", pi); // %lf 用于输出双精度浮点型
printf("Grade: %c\n", grade); // %c 用于输出字符
printf("Count: %d\n", count);
C. 常量：
常量是程序执行过程中其值不能被改变的量。
// 宏常量：在预处理阶段进行文本替换，没有类型检查
#define MAX_USERS 100
#define PI_VALUE 3.14159
// const关键字定义的常量：在编译阶段进行类型检查，更安全
const int MIN_VALUE = 0;
const double EULER_NUM = 2.71828;
// 枚举常量：定义一组整数常量，提高代码可读性
enum Weekday {
MONDAY = 1, // 默认从0开始，也可指定值
TUESDAY, // 自动递增为2
WEDNESDAY,
THURSDAY,
FRIDAY,
SATURDAY,
SUNDAY
};
printf("Max Users: %d\n", MAX_USERS);
printf("Min Value: %d\n", MIN_VALUE);
printf("First day of week: %d\n", MONDAY);
面试考点： 掌握C语言基本数据类型及其典型占用字节数和取值范围。理解 char, int, float, double 的区别与使用场景。掌握 const 关键字的用法和宏定义 #define 的区别。
1.3 运算符与表达式
C语言提供了丰富的运算符来执行各种操作。
A. 算术运算符： +, -, *, /, % (取模) B. 关系运算符： == (等于), != (不等于), >, <, >=, <= C. 逻辑运算符： && (逻辑与), || (逻辑或), ! (逻辑非) D. 位运算符： & (按位与), | (按位或), ^ (按位异或), ~ (按位取反), << (左移), >> (右移) E. 赋值运算符： =, +=, -=, *=, /=, %=, &=, |=, ^=, <<=, >>= F. 增量/减量运算符： ++ (自增), -- (自减) G. 其他运算符： sizeof (计算类型或变量大小), ? : (三目运算符), () (函数调用/优先级), [] (数组下标), . (成员访问), -> (指针成员访问), & (取地址), * (解引用/指针声明)
#include <stdio.h>
int main() {
int a = 10, b = 3;
printf("a + b = %d\n", a + b); // 13
printf("a / b = %d\n", a / b); // 3 (整数除法)
printf("a %% b = %d\n", a % b); // 1
printf("a > b is %d\n", a > b); // 1 (true)
printf("a == b is %d\n", a == b); // 0 (false)
int x = 5;
printf("x++ is %d, then x is %d\n", x++, x); // x++先使用后自增，输出5，x变为6
printf("++x is %d, then x is %d\n", ++x, x); // ++x先自增后使用，x变为7，输出7
int flags = 0b0101; // 二进制表示 (C99支持)
printf("flags & 0b0011 = %d\n", flags & 0b0011); // 0b0001 (1)
printf("flags | 0b1000 = %d\n", flags | 0b1000); // 0b1101 (13)
printf("flags << 1 = %d\n", flags << 1); // 0b1010 (10)
int max = (a > b) ? a : b; // 三目运算符
printf("Max of a and b is %d\n", max); // 10
return 0;
}
面试考点： 熟练掌握所有运算符的优先级和结合性，尤其是自增/自减的前缀和后缀形式。理解整数除法和取模运算。了解位运算符在嵌入式和网络编程中的应用。
1.4 控制流语句：程序的“决策”与“循环”
控制流语句决定了程序执行的顺序。
A. 条件语句： if, else if, else, switch
#include <stdio.h>
int main() {
int score = 85;
// if-else if-else
if (score >= 90) {
printf("Excellent!\n");
} else if (score >= 80) {
printf("Very Good!\n");
} else if (score >= 60) {
printf("Pass.\n");
} else {
printf("Fail.\n");
}
// switch语句
char grade_char = 'B';
switch (grade_char) {
case 'A':
printf("Grade is A.\n");
break; // break很重要，防止“穿透”
case 'B':
printf("Grade is B.\n");
break;
case 'C':
printf("Grade is C.\n");
break;
default:
printf("Invalid grade.\n");
break;
}
return 0;
}
B. 循环语句： for, while, do-while
#include <stdio.h>
int main() {
// for循环
printf("For loop from 1 to 5:\n");
for (int i = 1; i <= 5; i++) {
printf("%d ", i);
}
printf("\n");
// while循环
printf("While loop from 5 to 1:\n");
int j = 5;
while (j >= 1) {
printf("%d ", j);
j--;
}
printf("\n");
// do-while循环 (至少执行一次循环体)
printf("Do-while loop (will execute at least once even if condition is false initially):\n");
int k = 10;
do {
printf("k is %d\n", k);
k++;
} while (k < 5); // 条件为假，但循环体仍执行了一次
printf("\n");
// break 和 continue
printf("Demonstrating break and continue:\n");
for (int i = 0; i < 10; i++) {
if (i == 3) {
continue; // 跳过当前循环的剩余部分，进入下一次迭代
}
if (i == 7) {
break; // 终止整个循环
}
printf("%d ", i);
}
printf("\n"); // 输出: 0 1 2 4 5 6
return 0;
}
面试考点： 掌握 if-else if-else 和 switch 的使用场景。特别注意 switch 语句中 break 的作用。熟练使用 for, while, do-while 循环，理解它们的区别。掌握 break 和 continue 在循环中的控制作用。
1.5 函数：模块化你的代码
函数是C语言中组织代码的基本单元，它将一段完成特定任务的代码封装起来，实现代码的重用和模块化。
#include <stdio.h> // 包含标准输入输出库
#include <stdlib.h> // 包含标准库，用于exit()函数
// 函数声明 (Function Declaration / Prototype)
// 告诉编译器函数的名称、参数类型和返回类型
// 建议在main函数之前声明，或者放在头文件中
int add(int a, int b);
void greet(char* name); // 没有返回值的函数使用void
void exit_program();
// 函数定义 (Function Definition)
// 实现了函数的具体功能
int add(int a, int b) {
return a + b; // 返回两个整数的和
}
void greet(char* name) {
printf("Hello, %s!\n", name);
}
void exit_program() {
printf("Exiting program...\n");
exit(0); // 终止程序执行，参数0表示正常退出
}
int main() {
int num1 = 10;
int num2 = 20;
// 函数调用 (Function Call)
int sum = add(num1, num2); // 调用add函数
printf("Sum: %d\n", sum);
greet("Alice"); // 调用greet函数
greet("Bob");
// 匿名函数 (Lambda) - C语言本身不支持，C++11及以后支持
// 在C语言中，通常通过函数指针模拟类似行为，但不是真正的匿名函数
// 例如： qsort 函数接受一个比较函数指针作为参数。
// exit_program(); // 如果取消注释，程序会在此处终止
printf("This line will not be executed if exit_program is called.\n");
return 0;
}
面试考点： 理解函数声明、定义和调用的区别。掌握 void 关键字在函数参数和返回值中的含义。了解 return 语句的作用。
二、内存管理：直击C语言的灵魂
内存管理是C语言的核心和难点，也是区分C语言程序员水平的关键。理解内存的分配、使用和释放是编写高效、安全代码的基础。
2.1 内存分区：程序的“家”
在程序运行时，内存通常被划分为以下几个区域：
-
栈区（Stack）：
-
特点： 由编译器自动分配和释放。存放局部变量、函数参数、函数返回地址等。
-
生长方向： 从高地址向低地址生长。
-
速度： 速度快。
-
限制： 空间有限，通常几十MB到几GB，当栈溢出（Stack Overflow）时程序崩溃。
-
示例： 函数内部定义的
int a;。
-
-
堆区（Heap）：
-
特点： 由程序员手动分配和释放（使用
malloc,calloc,realloc,free等函数）。 -
生长方向： 从低地址向高地址生长。
-
速度： 相对栈区慢，但比静态存储区快。
-
限制： 理论上空间较大，受限于系统内存。
-
示例：
int* ptr = (int*)malloc(sizeof(int));。
-
-
全局/静态区（Global/Static Storage Area）：
-
特点： 存放全局变量和静态变量（包括静态局部变量和静态全局变量）。在程序编译时分配，在程序结束时由系统自动释放。
-
初始化： 未初始化的全局变量和静态变量会被系统自动初始化为0。
-
示例：
int global_var; static int static_var;。
-
-
常量区（Constant Data Area）：
-
特点： 存放常量字符串、
const修饰的全局变量（在某些系统上，局部const变量可能在栈上）。只读，不允许修改。 -
示例：
const char* str = "Hello";中的"Hello"。
-
-
代码区（Text Segment）：
-
特点： 存放可执行的机器指令（程序的代码）。只读。
-
示例：
main函数编译后的机器指令。
-
[Image: A simplified diagram showing common memory segments: Stack, Heap, Global/Static, Constant, Code, with their typical growth directions.]
面试考点： 能够清晰地描述栈区和堆区的区别，包括分配方式、生命周期、生长方向、速度和大小限制。理解全局变量和静态变量的存储位置及初始化规则。
2.2 指针：C语言的精髓
指针是C语言的灵魂，也是其强大和危险并存的根源。理解指针是掌握C语言的关键。
A. 指针的定义与使用：
指针是一个变量，其值是另一个变量的内存地址。
#include <stdio.h>
int main() {
int num = 10; // 定义一个整型变量
int* ptr; // 定义一个指向整型变量的指针变量ptr
ptr = # // 使用取地址运算符 '&' 获取num的内存地址，并赋给ptr
// 此时，ptr中存储的就是num的地址
printf("num 的值: %d\n", num); // 输出 10
printf("num 的地址: %p\n", (void*)&num); // 输出 num 的内存地址 (使用 %p 格式符)
printf("ptr 中存储的地址: %p\n", (void*)ptr); // 输出 ptr 中存储的地址，即 num 的地址
printf("ptr 指向的值: %d\n", *ptr); // 使用解引用运算符 '*' 获取ptr指向地址的值，即num的值
*ptr = 20; // 通过指针修改num的值
printf("通过指针修改后，num 的值: %d\n", num); // 输出 20
// 注意：定义指针时 * 是类型声明的一部分，表示这是一个指针变量
// 使用指针时 * 是解引用运算符，表示访问指针指向的值
int* another_ptr = # // 定义并初始化
printf("another_ptr 指向的值: %d\n", *another_ptr);
// 指针的类型很重要，它决定了解引用时能访问多少字节
char c = 'X';
char* char_ptr = &c;
printf("char_ptr 指向的值: %c\n", *char_ptr);
return 0;
}
B. 空指针与野指针：
-
空指针（Null Pointer）： 不指向任何有效内存地址的指针。通常用
NULL(C语言宏定义) 或0来表示。在C99及以后，可以使用nullptr（C++11引入，但在C语言中，_Noreturn类型的__null关键字通常被定义为((void*)0)，宏NULL通常是(void*)0）。在C语言中，一般用NULL。-
作用： 用于标记指针未初始化或不再指向有效对象，避免访问非法内存。在访问指针前检查是否为
NULL是良好的编程习惯。
-
-
野指针（Wild Pointer）： 指向一个无效或未知内存地址的指针。
-
产生原因：
-
未初始化： 指针变量在定义时未初始化，其值是随机的，可能指向任意内存。
-
释放后未置空：
free或delete内存后，指针变量仍然存储着被释放内存的地址，但该地址可能已被系统回收并分配给其他用途。 -
超出作用域： 函数返回局部变量的地址，而局部变量在函数结束后被销毁。
-
-
危险性： 访问野指针会导致程序崩溃（段错误/内存访问冲突）或产生不可预测的行为。
-
#include <stdio.h>
#include <stdlib.h> // For malloc and free
int main() {
// 1. 空指针
int* null_ptr = NULL; // 声明并初始化为空指针
if (null_ptr == NULL) {
printf("null_ptr is a NULL pointer.\n");
}
// 尝试解引用空指针会导致运行时错误 (Segmentation fault)
// *null_ptr = 100; // 不要这样做！
// 2. 未初始化的野指针
int* wild_ptr1; // 未初始化，其值不确定，是一个野指针
// printf("wild_ptr1 指向的值: %d\n", *wild_ptr1); // 危险！可能崩溃
// 3. 释放后未置空的野指针
int* ptr_dynamic = (int*)malloc(sizeof(int));
if (ptr_dynamic != NULL) {
*ptr_dynamic = 50;
printf("动态分配内存，值: %d\n", *ptr_dynamic);
free(ptr_dynamic); // 释放内存
// 此时ptr_dynamic变成野指针，因为其指向的内存已不再属于程序
// printf("释放后: %d\n", *ptr_dynamic); // 危险！
ptr_dynamic = NULL; // 最佳实践：释放后将指针置为NULL
printf("释放后并置空，ptr_dynamic: %p\n", (void*)ptr_dynamic);
}
// 4. 超出作用域的野指针
// int* get_local_address() {
// int local_var = 123;
// return &local_var; // 错误！返回局部变量地址，函数结束后local_var被销毁
// }
// int* dangling_ptr = get_local_address();
// printf("dangling_ptr 指向的值: %d\n", *dangling_ptr); // 危险！
return 0;
}
面试考点： 解释空指针和野指针的区别、危害及避免方法。理解 NULL 的作用。能够识别常见的野指针产生场景。
2.3 动态内存分配：灵活运用堆空间
栈内存由编译器自动管理，大小有限。当需要处理大小不确定的数据，或分配在函数结束后仍然存在的内存时，就需要使用动态内存分配，即在堆区分配内存。
A. malloc 和 free：
-
malloc(size_t size)：在堆区分配size字节的内存。成功则返回一个void*类型的指针，指向分配的内存的起始地址；失败则返回NULL。 -
free(void* ptr)：释放之前由malloc、calloc或realloc分配的内存。-
注意： 只能释放动态分配的内存。释放后，应将指针置为
NULL，防止野指针。
-
#include <stdio.h>
#include <stdlib.h> // 包含malloc和free函数
int main() {
int *ptr_int;
int num_elements = 5;
// 1. 分配单个int的内存
ptr_int = (int*)malloc(sizeof(int)); // 分配足够存储一个int的内存
if (ptr_int == NULL) { // 检查是否分配成功
perror("Failed to allocate memory for single int"); // 打印错误信息
return 1; // 退出程序
}
*ptr_int = 100;
printf("单个int的值: %d\n", *ptr_int);
free(ptr_int); // 释放内存
ptr_int = NULL; // 养成好习惯，释放后置NULL
printf("\n");
// 2. 分配int数组的内存
int* arr;
arr = (int*)malloc(num_elements * sizeof(int)); // 分配5个int的内存
if (arr == NULL) {
perror("Failed to allocate memory for array");
return 1;
}
// 初始化并打印数组
printf("动态分配的int数组:\n");
for (int i = 0; i < num_elements; i++) {
arr[i] = (i + 1) * 10; // 数组元素赋值
printf("arr[%d] = %d\n", i, arr[i]);
}
printf("\n");
free(arr); // 释放数组内存
arr = NULL;
// 尝试再次释放已释放的内存 (双重释放) 是未定义行为，可能导致程序崩溃
// free(arr); // 不要这样做！
return 0;
}
B. calloc 和 realloc：
-
calloc(size_t num, size_t size)：分配num个size字节大小的内存块，并将所有字节初始化为零。 -
realloc(void* ptr, size_t new_size)：重新调整已分配内存块的大小。-
ptr：指向之前由malloc,calloc,realloc分配的内存块的指针。 -
new_size：新的内存块大小（以字节为单位）。 -
行为： 如果
new_size大于原大小，新分配的部分未初始化；如果小于原大小，数据可能被截断。realloc可能会返回新的内存地址，原内存块被释放。 -
注意： 如果
ptr是NULL，realloc行为与malloc相同。如果new_size为0，realloc行为与free相同。
-
#include <stdio.h>
#include <stdlib.h> // For malloc, calloc, realloc, free
int main() {
// 1. calloc 的使用
int* arr_calloc;
int num_elements_calloc = 3;
// 分配3个int的内存，并初始化为0
arr_calloc = (int*)calloc(num_elements_calloc, sizeof(int));
if (arr_calloc == NULL) {
perror("Failed to allocate memory with calloc");
return 1;
}
printf("使用 calloc 分配的数组 (初始值):\n");
for (int i = 0; i < num_elements_calloc; i++) {
printf("arr_calloc[%d] = %d\n", i, arr_calloc[i]); // 应该都是0
}
printf("\n");
// 2. realloc 的使用
int* arr_realloc;
int initial_size = 3;
int new_size = 5;
arr_realloc = (int*)malloc(initial_size * sizeof(int));
if (arr_realloc == NULL) {
perror("Failed to allocate memory with malloc for realloc demo");
return 1;
}
for (int i = 0; i < initial_size; i++) {
arr_realloc[i] = i + 1;
}
printf("realloc前数组:\n");
for (int i = 0; i < initial_size; i++) {
printf("arr_realloc[%d] = %d\n", i, arr_realloc[i]);
}
printf("arr_realloc地址 (realloc前): %p\n", (void*)arr_realloc);
printf("\n");
// 重新调整大小
int* temp_ptr = (int*)realloc(arr_realloc, new_size * sizeof(int));
if (temp_ptr == NULL) {
perror("Failed to reallocate memory");
free(arr_realloc); // 如果realloc失败，原内存块未释放，需要手动释放
return 1;
}
arr_realloc = temp_ptr; // 更新指针，因为realloc可能返回新地址
printf("realloc后数组 (新大小 %d):\n", new_size);
for (int i = 0; i < new_size; i++) {
// 新增部分未初始化，旧部分保持原值
printf("arr_realloc[%d] = %d\n", i, arr_realloc[i]);
}
printf("arr_realloc地址 (realloc后): %p\n", (void*)arr_realloc);
printf("\n");
free(arr_calloc);
free(arr_realloc);
return 0;
}
面试考点： 熟练掌握 malloc, calloc, realloc, free 四个函数的使用场景和区别（特别是 calloc 会初始化为零）。理解动态内存分配的原理以及内存泄漏（Memory Leak）的危害（忘记 free 动态分配的内存）。
三、数组与字符串：有序数据的管理
数组和字符串是C语言中最基本、最常用的复合数据类型。
3.1 数组：同类型元素的集合
数组是存储相同类型元素的连续内存区域。
A. 数组的定义与初始化：
#include <stdio.h>
int main() {
// 1. 定义时指定大小，不初始化
int numbers[5]; // 定义一个包含5个整数的数组，元素值不确定
// 2. 定义时指定大小并部分初始化
int scores[5] = {10, 20, 30}; // scores[0]=10, scores[1]=20, scores[2]=30, scores[3]=0, scores[4]=0 (其余元素自动初始化为0)
// 3. 定义时不指定大小，根据初始化列表推断大小
int ages[] = {25, 30, 22, 28}; // 数组大小为4
// 4. 访问数组元素：通过下标 (索引从0开始)
printf("scores[0] = %d\n", scores[0]); // 输出 10
scores[4] = 99; // 修改元素
printf("scores[4] = %d\n", scores[4]); // 输出 99
// 遍历数组
printf("Numbers array:\n");
for (int i = 0; i < 5; i++) {
// C语言不检查数组越界，访问 numbers[5] 或更大下标可能导致严重错误
numbers[i] = (i + 1) * 100;
printf("numbers[%d] = %d\n", i, numbers[i]);
}
printf("\n");
// 5. 二维数组 (多维数组)
int matrix[2][3] = { // 2行3列的矩阵
{1, 2, 3},
{4, 5, 6}
};
printf("Matrix elements:\n");
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
return 0;
}
B. 数组与指针：
在C语言中，数组名在大多数情况下可以被视为指向其第一个元素的常量指针。
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr) / sizeof(arr[0]); // 计算数组大小
// 数组名 arr 相当于指向 arr[0] 的指针
printf("arr 的地址: %p\n", (void*)arr);
printf("&arr[0] 的地址: %p\n", (void*)&arr[0]);
printf("arr[0] 的值: %d\n", *arr); // 等价于 arr[0]
// 指针算术
int* ptr = arr; // ptr 指向 arr[0]
printf("ptr 指向的值: %d\n", *ptr); // 输出 10
printf("(ptr + 1) 指向的值: %d\n", *(ptr + 1)); // 输出 20 (指针移动sizeof(int)个字节)
// 通过指针遍历数组
printf("通过指针遍历数组:\n");
for (int i = 0; i < size; i++) {
printf("%d ", *(ptr + i)); // *(ptr + i) 等价于 arr[i]
}
printf("\n");
// 也可以直接用数组名进行指针运算
printf("通过数组名进行指针遍历:\n");
for (int i = 0; i < size; i++) {
printf("%d ", *(arr + i));
}
printf("\n");
// 函数参数中的数组：数组作为参数传递时会退化为指针
// void print_array(int a[], int len) 等价于 void print_array(int* a, int len)
// 这意味着在函数内部，无法通过 sizeof(a) 获取原始数组的大小
return 0;
}
// 示例函数：数组作为参数退化为指针
void print_array_elements(int* arr_param, int len) {
printf("在函数内部，arr_param 的大小: %zu (实际上是指针的大小)\n", sizeof(arr_param));
printf("在函数内部，遍历数组:\n");
for (int i = 0; i < len; i++) {
printf("%d ", arr_param[i]);
}
printf("\n");
}
面试考点： 掌握数组的定义、初始化和元素访问。理解数组与指针的紧密关系，以及数组名作为指针的特殊性。明确数组作为函数参数时会退化为指针，以及这带来的影响。
3.2 字符串：字符数组的特殊应用
在C语言中，字符串是以空字符 \0 结尾的字符数组。
A. 字符串的定义与初始化：
#include <stdio.h>
#include <string.h> // 包含字符串处理函数 (strlen, strcpy, strcat, strcmp等)
int main() {
// 1. 作为字符数组定义和初始化
char str1[10] = {'H', 'e', 'l', 'l', 'o', '\0'}; // 显式添加空字符
char str2[10] = "World"; // 编译器会自动在末尾添加空字符
// 2. 作为字符指针定义 (字符串字面量存储在只读数据区)
const char* str3 = "C Language"; // 推荐使用const，因为字符串字面量是常量，不可修改
// char* str_bad = "Dangerous"; // 不推荐，修改str_bad指向的内容会是未定义行为
printf("str1: %s\n", str1); // %s 用于输出字符串
printf("str2: %s\n", str2);
printf("str3: %s\n", str3);
// 字符串的长度 (不包含空字符)
printf("Length of str1: %zu\n", strlen(str1)); // 输出 5
printf("Length of str2: %zu\n", strlen(str2)); // 输出 5
printf("Length of str3: %zu\n", strlen(str3)); // 输出 10
// 注意：sizeof 获取的是数组的总大小，而 strlen 获取的是字符串的实际长度
printf("Sizeof str1 array: %zu bytes\n", sizeof(str1)); // 输出 10
printf("Sizeof str2 array: %zu bytes\n", sizeof(str2)); // 输出 10
printf("Sizeof str3 pointer: %zu bytes (指针大小，而非字符串字面量大小)\n", sizeof(str3)); // 通常是4或8字节
return 0;
}
B. 常用字符串处理函数（来自 <string.h>）：
-
strlen(const char* s)：返回字符串的长度（不包括\0）。 -
strcpy(char* dest, const char* src)：将src字符串复制到dest。不检查dest缓冲区大小，可能导致缓冲区溢出。 -
strncpy(char* dest, const char* src, size_t n)：复制n个字符。如果src短于n，dest会用\0填充；如果src长于n，dest可能不会以\0结尾，需要手动添加。 -
strcat(char* dest, const char* src)：将src字符串连接到dest字符串的末尾。不检查缓冲区大小。 -
strncat(char* dest, const char* src, size_t n)：连接n个字符。 -
strcmp(const char* s1, const char* s2)：比较两个字符串。相等返回0，s1 > s2返回正值，s1 < s2返回负值。 -
strncmp(const char* s1, const char* s2, size_t n)：比较前n个字符。 -
sprintf(char* buffer, const char* format, ...)：将格式化的数据写入字符串buffer。
#include <stdio.h>
#include <string.h> // For string functions
int main() {
char source[] = "Hello";
char destination[20]; // 确保有足够大的缓冲区
// strcpy: 复制字符串
strcpy(destination, source);
printf("After strcpy: %s\n", destination); // Output: Hello
char str_long[] = "This is a very long string.";
char buffer_short[10];
// strncpy: 复制指定数量的字符
strncpy(buffer_short, str_long, sizeof(buffer_short) - 1); // 留一个位置给\0
buffer_short[sizeof(buffer_short) - 1] = '\0'; // 手动添加\0，确保字符串合法
printf("After strncpy (truncated): %s\n", buffer_short); // Output: This is a
char s1[30] = "C ";
char s2[] = "Programming";
// strcat: 连接字符串
strcat(s1, s2);
printf("After strcat: %s\n", s1); // Output: C Programming
// strcmp: 比较字符串
char str_a[] = "apple";
char str_b[] = "banana";
char str_c[] = "apple";
printf("strcmp(\"apple\", \"banana\"): %d\n", strcmp(str_a, str_b)); // < 0
printf("strcmp(\"banana\", \"apple\"): %d\n", strcmp(str_b, str_a)); // > 0
printf("strcmp(\"apple\", \"apple\"): %d\n", strcmp(str_a, str_c)); // == 0
// sprintf: 格式化输出到字符串
char info_buffer[50];
int year = 2024;
double version = 1.0;
sprintf(info_buffer, "Current year is %d, Version %.1f.", year, version);
printf("Formatted string: %s\n", info_buffer);
return 0;
}
面试考点： 理解C语言中字符串的本质是字符数组以 \0 结尾。掌握 strlen 和 sizeof 对字符串的异同。熟悉 strcpy, strcat, strcmp 等常用字符串函数的使用，并特别注意缓冲区溢出的风险，强调 strncpy 和 snprintf 的安全性。
四、结构体与联合体：自定义数据类型
C语言允许你定义自己的数据类型，将不同类型的数据组合在一起，形成更有意义的复合结构。
4.1 结构体（Structures）：打包不同类型数据
结构体（struct）允许你将不同数据类型（甚至其他结构体）的变量组合成一个单一的复合数据类型。
#include <stdio.h>
#include <string.h> // For strcpy
// 定义一个结构体
struct Student {
int id;
char name[50];
int age;
float score;
};
// 结构体嵌套
struct Date {
int year;
int month;
int day;
};
struct Course {
char course_name[100];
struct Date start_date; // 结构体嵌套
int credits;
};
int main() {
// 声明结构体变量
struct Student s1;
// 访问结构体成员：使用点运算符 (.)
s1.id = 101;
strcpy(s1.name, "Alice Smith"); // 字符串赋值需要使用strcpy
s1.age = 20;
s1.score = 95.5f;
printf("Student ID: %d\n", s1.id);
printf("Student Name: %s\n", s1.name);
printf("Student Age: %d\n", s1.age);
printf("Student Score: %.1f\n", s1.score);
printf("\n");
// 初始化结构体变量
struct Student s2 = {102, "Bob Johnson", 21, 88.0f}; // 按照成员声明顺序初始化
// 也可以使用指定初始化器 (C99及以后)
struct Student s3 = {.name = "Charlie Brown", .id = 103, .age = 19, .score = 78.5f};
printf("Student s2 Name: %s\n", s2.name);
printf("Student s3 Name: %s\n", s3.name);
printf("\n");
// 结构体数组
struct Student class_list[3];
class_list[0] = s1;
class_list[1] = s2;
class_list[2] = s3;
printf("Class List:\n");
for (int i = 0; i < 3; i++) {
printf("ID: %d, Name: %s, Age: %d, Score: %.1f\n",
class_list[i].id, class_list[i].name, class_list[i].age, class_list[i].score);
}
printf("\n");
// 结构体指针：使用箭头运算符 (->)
struct Student* ptr_s1 = &s1; // 定义并初始化一个指向s1的指针
printf("通过指针访问s1的姓名: %s\n", ptr_s1->name); // 等价于 (*ptr_s1).name
ptr_s1->age = 22; // 通过指针修改成员
printf("通过指针修改s1的年龄: %d\n", s1.age);
printf("\n");
// 嵌套结构体的访问
struct Course c1;
strcpy(c1.course_name, "Computer Science Basics");
c1.start_date.year = 2023;
c1.start_date.month = 9;
c1.start_date.day = 1;
c1.credits = 3;
printf("Course Name: %s\n", c1.course_name);
printf("Start Date: %d-%02d-%02d\n", c1.start_date.year, c1.start_date.month, c1.start_date.day);
printf("\n");
return 0;
}
B. 结构体与内存对齐：
结构体成员在内存中通常不会紧密排列，编译器为了提高访问效率（CPU通常按字长访问内存），会自动进行内存对齐。这可能导致结构体实际占用空间大于其成员变量大小之和。
#include <stdio.h>
// 结构体1：未考虑对齐
struct SimpleData1 {
char c1; // 1 byte
int i; // 4 bytes
char c2; // 1 byte
};
// 假设int按4字节对齐，char按1字节对齐
// c1 (1 byte) [padding 3 bytes] i (4 bytes) c2 (1 byte) [padding 3 bytes]
// 实际大小可能为 1 + 3 + 4 + 1 + 3 = 12 bytes
// 结构体2：考虑对齐，将大成员放在前面
struct SimpleData2 {
int i; // 4 bytes
char c1; // 1 byte
char c2; // 1 byte
};
// 假设int按4字节对齐，char按1字节对齐
// i (4 bytes) c1 (1 byte) c2 (1 byte) [padding 2 bytes]
// 实际大小可能为 4 + 1 + 1 + 2 = 8 bytes
// 结构体3：空结构体或只有一个成员
struct EmptyStruct {};
struct SingleMember {
int x;
};
int main() {
printf("Size of char: %zu\n", sizeof(char));
printf("Size of int: %zu\n", sizeof(int));
printf("\n");
printf("Size of SimpleData1: %zu bytes\n", sizeof(struct SimpleData1)); // 理论上6字节，实际可能是12字节
printf("Size of SimpleData2: %zu bytes\n", sizeof(struct SimpleData2)); // 理论上6字节，实际可能是8字节
printf("Size of EmptyStruct: %zu bytes\n", sizeof(struct EmptyStruct)); // 通常为1字节 (空结构体也占用1字节，确保实例拥有唯一地址)
printf("Size of SingleMember: %zu bytes\n", sizeof(struct SingleMember)); // 通常为4字节
return 0;
}
面试考点： 熟练掌握结构体的定义、成员访问（点运算符和箭头运算符）、初始化。理解结构体指针的使用。重点理解内存对齐的原理及其对结构体大小的影响，并能给出优化内存对齐的建议（大成员放前）。
4.2 联合体（Unions）：共享内存空间
联合体（union）是一种特殊的数据类型，它允许在同一块内存空间中存储不同的数据类型。在任何时候，联合体中只有一个成员是活跃的。联合体的大小取决于其最大成员的大小。
#include <stdio.h>
// 定义一个联合体
union Data {
int i; // 4 bytes
float f; // 4 bytes
char str[20]; // 20 bytes (最大成员)
};
int main() {
union Data data; // 声明一个联合体变量
printf("Size of union Data: %zu bytes\n", sizeof(union Data)); // 输出 20 (取决于最大成员str的大小)
printf("\n");
// 赋值给整型成员
data.i = 10;
printf("data.i: %d\n", data.i); // 输出 10
// 此时访问其他成员，会得到未定义的结果，因为它们共享同一内存，且当前存储的是整型数据
printf("data.f (after i): %f\n", data.f); // 可能输出垃圾值或0.0
printf("data.str (after i): %s\n", data.str); // 可能输出乱码或空字符串
printf("\n");
// 赋值给浮点型成员
data.f = 22.5f;
printf("data.f: %f\n", data.f); // 输出 22.500000
printf("data.i (after f): %d\n", data.i); // 可能输出一个与22.5浮点数二进制表示对应的整数值
printf("\n");
// 赋值给字符串成员
strcpy(data.str, "C Programming");
printf("data.str: %s\n", data.str); // 输出 C Programming
// 此时访问data.i或data.f会得到垃圾值
printf("data.i (after str): %d\n", data.i); // 乱码整数
printf("data.f (after str): %f\n", data.f); // 乱码浮点数
printf("\n");
return 0;
}
面试考点： 理解联合体和结构体的根本区别：联合体成员共享同一块内存空间，而结构体成员各自拥有独立内存。掌握联合体的大小计算方式（最大成员的大小）。明确联合体在任何时刻只有一个成员是活跃的。
4.3 枚举（Enumerations）：可读的整数常量
枚举（enum）允许你定义一组命名的整数常量，提高代码的可读性和可维护性。
#include <stdio.h>
// 定义一个简单的枚举
enum Day {
SUNDAY, // 默认值为 0
MONDAY, // 默认值为 1
TUESDAY, // 默认值为 2
WEDNESDAY,
THURSDAY,
FRIDAY,
SATURDAY
};
// 枚举可以指定值
enum Status {
SUCCESS = 0,
FAILURE = -1,
PENDING = 1
};
int main() {
enum Day today = WEDNESDAY;
enum Status current_status = SUCCESS;
printf("Today is day number: %d\n", today); // 输出 3
printf("Success status code: %d\n", current_status); // 输出 0
// 枚举变量可以隐式转换为int
int day_num = MONDAY;
printf("Monday is day number: %d\n", day_num); // 输出 1
// 也可以将整数转换为枚举类型（但要确保值在枚举范围内）
enum Day next_day = (enum Day)4; // 将4转换为枚举类型 (THURSDAY)
printf("Next day is day number: %d\n", next_day); // 输出 4
// 遍历枚举 (不是直接支持，需要转换为整数并检查范围)
printf("Days of the week:\n");
for (int i = SUNDAY; i <= SATURDAY; i++) {
printf("Day %d\n", i);
}
return 0;
}
面试考点： 掌握枚举的定义和使用，理解枚举成员默认从0开始递增，也可以显式指定值。理解枚举本质上是整数常量，可以与整数相互转换。
五、预处理指令：编译前的“魔法”
预处理指令在程序编译之前由预处理器处理，它们不是C语言本身的语句，而是给编译器提供指示。
5.1 宏定义：代码片段的替换
#define 用于定义宏，它在预处理阶段进行简单的文本替换。
#include <stdio.h>
// 1. 定义常量宏
#define MAX_SIZE 100
#define PI 3.14159265
// 2. 定义带参数的宏
#define SQUARE(x) (x * x) // 注意括号，避免运算符优先级问题
#define ADD_TWO(a, b) ((a) + (b)) // 同样注意括号
// 宏定义多行
#define PRINT_HELLO_WORLD \
printf("Hello, "); \
printf("World!\n");
int main() {
printf("Max size: %d\n", MAX_SIZE);
printf("PI: %f\n", PI);
int val = 5;
printf("SQUARE(val): %d\n", SQUARE(val)); // 替换为 (val * val) -> (5 * 5) = 25
printf("SQUARE(val + 1): %d\n", SQUARE(val + 1)); // 替换为 (val + 1 * val + 1) -> (5 + 1 * 5 + 1) = 5 + 5 + 1 = 11 (错误！)
// 应该写成 ((x) * (x)) -> ((val + 1) * (val + 1)) = (6 * 6) = 36
printf("Correct SQUARE(val + 1): %d\n", (val + 1) * (val + 1)); // 实际应这样使用或修改宏定义
printf("ADD_TWO(10, 20): %d\n", ADD_TWO(10, 20)); // 替换为 ((10) + (20)) = 30
PRINT_HELLO_WORLD; // 替换为 printf("Hello, "); printf("World!\n");
// 3. 宏的副作用问题
// int i = 1;
// int result = SQUARE(i++); // 替换为 (i++ * i++)，这会导致i被自增两次，结果不确定
// printf("Macro side effect: i=%d, result=%d\n", i, result); // 结果可能不符合预期
return 0;
}
面试考点： 掌握宏定义（#define）的基本用法。理解宏在预处理阶段进行文本替换的特性，强调使用括号来避免运算符优先级问题。了解宏的“副作用”问题以及与函数的区别（宏没有类型检查，可能产生意想不到的错误）。
5.2 条件编译：代码的“开关”
条件编译指令允许你根据特定的条件（如宏是否定义、表达式的值）来包含或排除部分源代码，常用于调试、平台兼容性、版本控制等。
#include <stdio.h>
// 定义宏用于条件编译
#define DEBUG_MODE
#define VERSION 200
int main() {
printf("This line is always compiled.\n");
// #ifdef: 如果宏被定义
#ifdef DEBUG_MODE
printf("DEBUG_MODE is defined. This is debug output.\n");
#endif
// #ifndef: 如果宏未被定义
#ifndef RELEASE_MODE
printf("RELEASE_MODE is NOT defined. This is likely a debug/development build.\n");
#endif
// #if: 根据表达式的值
#if VERSION >= 200
printf("Version is 2.0 or higher.\n");
#elif VERSION == 100
printf("Version is 1.0.\n");
#else
printf("Unknown version.\n");
#endif
// #undef: 取消宏定义
#undef DEBUG_MODE
#ifdef DEBUG_MODE
printf("DEBUG_MODE is still defined? No, it should not be.\n"); // 此行不会被编译
#else
printf("DEBUG_MODE has been undefined.\n"); // 此行会被编译
#endif
return 0;
}
面试考点： 掌握 ifdef, ifndef, if, elif, else, endif, undef 等条件编译指令的用法。理解条件编译在跨平台开发、调试和版本管理中的重要性。
5.3 文件包含：模块化项目的基石
#include 指令除了用于标准库，也用于包含自定义头文件，实现代码的模块化。
// math_utils.h (头文件示例)
#ifndef MATH_UTILS_H // 防止头文件被重复包含
#define MATH_UTILS_H
// 函数声明
int add_integers(int a, int b);
int subtract_integers(int a, int b);
#endif // MATH_UTILS_H
// math_utils.c (实现文件示例)
#include "math_utils.h" // 包含自定义头文件
int add_integers(int a, int b) {
return a + b;
}
int subtract_integers(int a, int b) {
return a - b;
}
// main.c (主程序文件示例)
#include <stdio.h>
#include "math_utils.h" // 包含自定义头文件
int main() {
int result_add = add_integers(5, 3);
printf("5 + 3 = %d\n", result_add);
int result_sub = subtract_integers(10, 4);
printf("10 - 4 = %d\n", result_sub);
return 0;
}
编译： gcc main.c math_utils.c -o my_program
面试考点： 理解 #include 的两种形式（<> 和 ""）的区别。理解头文件卫士（#ifndef/#define/#endif）的作用，避免重复包含导致编译错误。
六、C语言高级数据结构（上）：链表与树
掌握基本语法后，C语言在数据结构和算法方面的能力就真正展现出来。这些数据结构是解决复杂问题的基础，也是面试中的高频考点。
6.1 链表：动态的线性结构
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。它克服了数组大小固定、插入删除效率低的缺点。
A. 单向链表：
每个节点包含数据域和指向下一个节点的指针域。
#include <stdio.h>
#include <stdlib.h> // For malloc and free
// 定义链表节点结构体
struct Node {
int data; // 数据域
struct Node* next; // 指针域，指向下一个节点
};
// 函数：创建新节点
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(EXIT_FAILURE); // 退出程序
}
newNode->data = value;
newNode->next = NULL; // 新节点的next初始为NULL
return newNode;
}
// 函数：在链表头部插入节点
struct Node* insertAtBeginning(struct Node* head, int value) {
struct Node* newNode = createNode(value);
newNode->next = head; // 新节点的next指向原头节点
return newNode; // 返回新节点作为新的头节点
}
// 函数：在链表末尾插入节点
struct Node* insertAtEnd(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) { // 如果链表为空，新节点就是头节点
return newNode;
}
struct Node* current = head;
while (current->next != NULL) { // 遍历到链表尾部
current = current->next;
}
current->next = newNode; // 尾节点的next指向新节点
return head; // 返回原头节点
}
// 函数：在指定位置插入节点 (例如，在某个值之后插入)
struct Node* insertAfter(struct Node* head, int target_data, int value_to_insert) {
struct Node* current = head;
while (current != NULL && current->data != target_data) {
current = current->next;
}
if (current == NULL) {
printf("Target data %d not found in the list. Cannot insert.\n", target_data);
return head;
}
// 目标节点找到
struct Node* newNode = createNode(value_to_insert);
newNode->next = current->next;
current->next = newNode;
return head;
}
// 函数：删除链表中第一个匹配指定值的节点
struct Node* deleteNode(struct Node* head, int value) {
if (head == NULL) {
printf("List is empty. Cannot delete.\n");
return NULL;
}
struct Node* current = head;
struct Node* prev = NULL;
// 如果头节点就是要删除的节点
if (current != NULL && current->data == value) {
head = current->next; // 更新头节点
free(current); // 释放原头节点内存
return head;
}
// 遍历查找要删除的节点
while (current != NULL && current->data != value) {
prev = current;
current = current->next;
}
// 如果没有找到要删除的节点
if (current == NULL) {
printf("Value %d not found in the list. Cannot delete.\n", value);
return head;
}
// 找到了，删除它
prev->next = current->next; // 前一个节点指向当前节点的下一个节点
free(current); // 释放当前节点内存
return head;
}
// 函数：查找链表中的元素
struct Node* searchNode(struct Node* head, int value) {
struct Node* current = head;
while (current != NULL) {
if (current->data == value) {
return current; // 找到并返回该节点指针
}
current = current->next;
}
return NULL; // 未找到
}
// 函数：遍历并打印链表
void printList(struct Node* head) {
struct Node* current = head;
printf("List: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// 函数：释放链表所有节点内存
void freeList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
struct Node* temp = current; // 临时保存当前节点
current = current->next; // 移动到下一个节点
free(temp); // 释放当前节点内存
}
printf("List memory freed.\n");
}
int main() {
struct Node* head = NULL; // 初始化空链表
head = insertAtBeginning(head, 30);
head = insertAtBeginning(head, 20);
head = insertAtBeginning(head, 10); // List: 10 -> 20 -> 30 -> NULL
printList(head);
head = insertAtEnd(head, 40);
head = insertAtEnd(head, 50); // List: 10 -> 20 -> 30 -> 40 -> 50 -> NULL
printList(head);
head = insertAfter(head, 30, 35); // List: 10 -> 20 -> 30 -> 35 -> 40 -> 50 -> NULL
printList(head);
head = deleteNode(head, 20); // Delete 20: List: 10 -> 30 -> 35 -> 40 -> 50 -> NULL
printList(head);
head = deleteNode(head, 10); // Delete 10 (head): List: 30 -> 35 -> 40 -> 50 -> NULL
printList(head);
struct Node* found = searchNode(head, 40);
if (found) {
printf("Found 40 in the list.\n");
} else {
printf("40 not found.\n");
}
freeList(head); // 释放所有节点内存
head = NULL; // 释放后将头指针置空
return 0;
}
B. 双向链表 (Doubly Linked List)：
每个节点包含数据域、指向前一个节点的指针域和指向后一个节点的指针域。
#include <stdio.h>
#include <stdlib.h>
// 定义双向链表节点结构体
struct DNode {
int data;
struct DNode* prev; // 指向前一个节点
struct DNode* next; // 指向下一个节点
};
// 函数：创建新节点
struct DNode* createDNode(int value) {
struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(EXIT_FAILURE);
}
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// 函数：在双向链表头部插入节点
struct DNode* insertDAtBeginning(struct DNode* head, int value) {
struct DNode* newNode = createDNode(value);
if (head != NULL) {
newNode->next = head;
head->prev = newNode;
}
return newNode; // 返回新节点作为新的头节点
}
// 函数：在双向链表末尾插入节点
struct DNode* insertDAtEnd(struct DNode* head, int value) {
struct DNode* newNode = createDNode(value);
if (head == NULL) {
return newNode;
}
struct DNode* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
return head;
}
// 函数：删除双向链表中的节点
struct DNode* deleteDNode(struct DNode* head, int value) {
struct DNode* current = head;
while (current != NULL && current->data != value) {
current = current->next;
}
if (current == NULL) {
printf("Value %d not found. Cannot delete.\n", value);
return head;
}
if (current->prev != NULL) {
current->prev->next = current->next;
} else { // 删除的是头节点
head = current->next;
}
if (current->next != NULL) {
current->next->prev = current->prev;
}
free(current);
return head;
}
// 函数：正向遍历并打印双向链表
void printDListForward(struct DNode* head) {
struct DNode* current = head;
printf("List (Forward): ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// 函数：反向遍历并打印双向链表
void printDListBackward(struct DNode* head) {
struct DNode* current = head;
if (head == NULL) {
printf("List (Backward): NULL\n");
return;
}
// 找到尾节点
while (current->next != NULL) {
current = current->next;
}
printf("List (Backward): ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->prev;
}
printf("NULL\n");
}
// 函数：释放双向链表所有节点内存
void freeDList(struct DNode* head) {
struct DNode* current = head;
while (current != NULL) {
struct DNode* temp = current;
current = current->next;
free(temp);
}
printf("Doubly Linked List memory freed.\n");
}
int main() {
struct DNode* head = NULL;
head = insertDAtBeginning(head, 10);
head = insertDAtBeginning(head, 5);
printDListForward(head); // 5 <-> 10 <-> NULL
head = insertDAtEnd(head, 15);
head = insertDAtEnd(head, 20);
printDListForward(head); // 5 <-> 10 <-> 15 <-> 20 <-> NULL
printDListBackward(head); // 20 <-> 15 <-> 10 <-> 5 <-> NULL
head = deleteDNode(head, 10); // Delete 10
printDListForward(head); // 5 <-> 15 <-> 20 <-> NULL
head = deleteDNode(head, 5); // Delete head (5)
printDListForward(head); // 15 <-> 20 <-> NULL
head = deleteDNode(head, 20); // Delete last node (20)
printDListForward(head); // 15 <-> NULL
head = deleteDNode(head, 15); // Delete remaining (15)
printDListForward(head); // NULL
freeDList(head); // 实际head已经是NULL，这里是安全调用
return 0;
}
面试考点： 深刻理解链表（特别是单向链表）的节点结构、插入（头插、尾插、中间插）、删除、查找、遍历等基本操作的实现。能够手动编写链表操作函数。了解双向链表与单向链表的区别及各自的优缺点。链表操作是面试手写代码的重中之重。
6.2 树：非线性的层级结构
树是一种抽象数据类型，它模拟了具有父子关系的层级结构。在C语言中，通常通过结构体和指针来实现树。
A. 二叉树（Binary Tree）：
每个节点最多有两个子节点：左子节点和右子节点。
#include <stdio.h>
#include <stdlib.h> // For malloc and free
// 定义二叉树节点结构体
struct TreeNode {
int data;
struct TreeNode* left; // 指向左子节点
struct TreeNode* right; // 指向右子节点
};
// 函数：创建新节点
struct TreeNode* createTreeNode(int value) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(EXIT_FAILURE);
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 遍历：前序遍历 (Preorder Traversal: 根 -> 左 -> 右)
void preorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data); // 访问根节点
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
// 遍历：中序遍历 (Inorder Traversal: 左 -> 根 -> 右)
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left); // 遍历左子树
printf("%d ", root->data); // 访问根节点
inorderTraversal(root->right); // 遍历右子树
}
// 遍历：后序遍历 (Postorder Traversal: 左 -> 右 -> 根)
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left); // 遍历左子树
postorderTraversal(root->right); // 遍历右子树
printf("%d ", root->data); // 访问根节点
}
// 函数：层序遍历 (Level Order Traversal) - 需要队列
// 简单的队列实现（数组模拟，非线程安全，仅用于演示）
#define MAX_QUEUE_SIZE 100
struct TreeNode* queue[MAX_QUEUE_SIZE];
int front = -1, rear = -1;
void enqueue(struct TreeNode* node) {
if (rear == MAX_QUEUE_SIZE - 1) {
printf("Queue is full.\n");
return;
}
if (front == -1) {
front = 0;
}
queue[++rear] = node;
}
struct TreeNode* dequeue() {
if (front == -1 || front > rear) {
printf("Queue is empty.\n");
return NULL;
}
return queue[front++];
}
int is_queue_empty() {
return front == -1 || front > rear;
}
void levelOrderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
front = -1; // 重置队列
rear = -1;
enqueue(root);
printf("Level Order Traversal: ");
while (!is_queue_empty()) {
struct TreeNode* current = dequeue();
printf("%d ", current->data);
if (current->left != NULL) {
enqueue(current->left);
}
if (current->right != NULL) {
enqueue(current->right);
}
}
printf("\n");
}
// 函数：计算二叉树的最大深度
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0; // 空树深度为0
}
int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);
// 当前节点深度 = max(左子树深度, 右子树深度) + 1
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
// 函数：检查是否是平衡二叉树
// 平衡二叉树：任意节点的左右子树高度差不超过1
int getHeight(struct TreeNode* node) {
if (node == NULL) {
return 0;
}
int left_h = getHeight(node->left);
int right_h = getHeight(node->right);
return (left_h > right_h ? left_h : right_h) + 1;
}
// isBalancedHelper返回树高，如果发现不平衡则返回-1
int isBalancedHelper(struct TreeNode* node) {
if (node == NULL) {
return 0;
}
int left_height = isBalancedHelper(node->left);
if (left_height == -1) {
return -1; // 左子树不平衡
}
int right_height = isBalancedHelper(node->right);
if (right_height == -1) {
return -1; // 右子树不平衡
}
if (abs(left_height - right_height) > 1) { // 检查当前节点是否平衡
return -1;
}
return (left_height > right_height ? left_height : right_height) + 1;
}
// 函数：检查是否是平衡二叉树的入口
int isBalanced(struct TreeNode* root) {
return isBalancedHelper(root) != -1;
}
// 函数：释放二叉树所有节点内存
void freeTree(struct TreeNode* root) {
if (root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
// 构建一棵简单的二叉树
// 1
// / \
// 2 3
// / \
// 4 5
struct TreeNode* root = createTreeNode(1);
root->left = createTreeNode(2);
root->right = createTreeNode(3);
root->left->left = createTreeNode(4);
root->left->right = createTreeNode(5);
printf("Preorder Traversal: ");
preorderTraversal(root); // Output: 1 2 4 5 3
printf("\n");
printf("Inorder Traversal: ");
inorderTraversal(root); // Output: 4 2 5 1 3
printf("\n");
printf("Postorder Traversal: ");
postorderTraversal(root); // Output: 4 5 2 3 1
printf("\n");
levelOrderTraversal(root); // Output: 1 2 3 4 5
printf("Max depth of tree: %d\n", maxDepth(root)); // Output: 3
if (isBalanced(root)) { // Not balanced, because left subtree's depth is 2, right is 1. (abs(2-1)=1, still balanced in strict definition, but adding more nodes makes it unbalanced)
printf("The tree is balanced.\n"); // This specific tree (1-2-3-4-5) IS balanced.
} else {
printf("The tree is NOT balanced.\n");
}
// 尝试一个不平衡的树
struct TreeNode* unbalanced_root = createTreeNode(10);
unbalanced_root->left = createTreeNode(20);
unbalanced_root->left->left = createTreeNode(30);
unbalanced_root->left->left->left = createTreeNode(40); // 深度为4，右子树为0，高度差为4
printf("\nChecking unbalanced tree:\n");
if (isBalanced(unbalanced_root)) {
printf("The unbalanced tree IS balanced (ERROR in logic or definition for this example).\n");
} else {
printf("The unbalanced tree is NOT balanced.\n"); // Expected for this tree
}
freeTree(root);
freeTree(unbalanced_root);
return 0;
}
面试考点： 掌握二叉树的节点定义。熟练掌握二叉树的前序、中序、后序遍历（递归实现），这是高频考点。理解层序遍历的原理（需要队列）。能够手写计算树的深度和判断平衡二叉树的函数。
这是C语言完整教程的第一部分，涵盖了基础语法、内存管理和一些基本数据结构。后续部分将深入探讨更高级的主题，包括：
-
高级指针应用： 函数指针、多级指针、指针数组与数组指针
-
链表与树的更多操作： 环形链表、红黑树/B树概念
-
排序与查找算法： 冒泡、选择、插入、快速、归并、堆排序、二分查找
-
文件I/O： 文件的读写操作
-
错误处理与调试：
errno、perror、assert -
内存优化与常见陷阱
-
牛客热题101必刷榜真题解析
-
大厂C语言面试高频问题与解题策略
C语言完整教程：牛客热题与大厂面试通关秘籍（第二部分：高级特性、算法与面试实战）
引言：从语法到实战——构建你的C语言“内功”
在第一部分中，我们已经打下了坚实的C语言基础，掌握了其基本语法、变量、运算符、控制流以及内存管理的核心——指针，并初步了解了链表和二叉树的实现。这些知识构成了你C语言编程的“骨架”。
在本第二部分中，我们将进一步深入C语言的“血肉”和“神经系统”。我们将探索高级指针应用，这不仅是C语言的精髓，也是面试中考察你对内存理解深度和灵活性的试金石。我们还将详细讲解其他重要的数据结构，如栈、队列、哈希表等，并深入剖析经典的排序与查找算法。此外，文件I/O、错误处理和调试技巧也将是本部分的重点。最终，我们将把所学知识与牛客热题101必刷榜以及大厂C语言面试高频问题紧密结合，提供实战解析和解题策略，助你真正将C语言内化为解决实际问题的强大工具。
准备好了吗？让我们开启C语言的进阶之旅，为你的面试和职业发展添砖加瓦！
七、高级指针应用：驾驭C语言的“利剑”
指针是C语言的灵魂，也是它强大和复杂的源泉。掌握高级指针应用，意味着你能够更灵活、更高效地操作内存，实现复杂的数据结构和回调机制。
7.1 函数指针：函数作为参数与回调
在C语言中，函数也是有地址的。函数指针就是指向函数的指针，可以将其作为参数传递给其他函数，或者存储在变量中以备后用。这是实现回调（Callback）机制和多态性的基础。
A. 定义与使用：
函数指针的定义格式为：返回类型 (*指针变量名)(参数类型列表);
#include <stdio.h>
// 1. 定义两个普通函数
int add(int a, int b) {
return a + b;
}
int subtract(int a, int b) {
return a - b;
}
// 2. 定义一个接受函数指针作为参数的函数
// 它接受两个整数和一个函数指针，该函数指针指向一个接受两个int并返回int的函数
int calculate(int x, int y, int (*operation)(int, int)) {
return operation(x, y); // 调用传入的函数指针
}
int main() {
// 声明并初始化函数指针
int (*op_ptr)(int, int); // 声明一个函数指针 op_ptr
op_ptr = add; // 将add函数的地址赋给op_ptr
printf("使用函数指针执行加法: %d\n", op_ptr(10, 5)); // 通过函数指针调用add
op_ptr = subtract; // 将subtract函数的地址赋给op_ptr
printf("使用函数指针执行减法: %d\n", op_ptr(10, 5)); // 通过函数指针调用subtract
printf("\n");
// 使用calculate函数
printf("使用 calculate 函数执行加法: %d\n", calculate(20, 7, add));
printf("使用 calculate 函数执行减法: %d\n", calculate(20, 7, subtract));
// 函数指针数组 (不是非常常见，但了解概念)
int (*operations[])(int, int) = {add, subtract}; // 存储函数指针的数组
printf("使用函数指针数组执行加法: %d\n", operations[0](30, 8));
printf("使用函数指针数组执行减法: %d\n", operations[1](30, 8));
return 0;
}
B. 回调函数：
回调函数是一种通过函数指针实现的设计模式。你编写一个函数A，并将其作为参数传递给另一个函数B。函数B在执行其任务的某个点，会“回调”函数A来完成特定的操作。
场景： 排序函数（如 qsort）、事件处理、异步编程、自定义比较逻辑等。
#include <stdio.h>
#include <stdlib.h> // For qsort
#include <string.h> // For strcmp
// 比较函数：用于qsort，比较整数
// qsort要求比较函数接收两个const void*参数，并返回int
int compare_integers(const void* a, const void* b) {
return (*(int*)a - *(int*)b); // 将void*转换为int*，然后解引用进行比较
}
// 比较函数：用于qsort，比较字符串
int compare_strings(const void* a, const void* b) {
// a 和 b 是指向字符串指针的指针 (char**)
return strcmp(*(const char**)a, *(const char**)b);
}
int main() {
// 使用 qsort 排序整数数组
int numbers[] = {5, 2, 8, 1, 9, 4};
int n = sizeof(numbers) / sizeof(numbers[0]);
printf("原始整数数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
// 调用 qsort，传入 compare_integers 作为回调函数
qsort(numbers, n, sizeof(int), compare_integers);
printf("排序后整数数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", numbers[i]);
}
printf("\n\n");
// 使用 qsort 排序字符串数组
const char* names[] = {"Charlie", "Alice", "Bob", "David"};
int m = sizeof(names) / sizeof(names[0]);
printf("原始字符串数组: ");
for (int i = 0; i < m; i++) {
printf("%s ", names[i]);
}
printf("\n");
// 调用 qsort，传入 compare_strings 作为回调函数
qsort(names, m, sizeof(const char*), compare_strings);
printf("排序后字符串数组: ");
for (int i = 0; i < m; i++) {
printf("%s ", names[i]);
}
printf("\n");
return 0;
}
面试考点： 熟练掌握函数指针的定义、声明和赋值。理解函数指针作为参数的机制，特别是回调函数的概念和应用（如 qsort）。能够手写简单的函数指针使用示例。
7.2 多级指针：指向指针的指针
多级指针是指向指针的指针，即指针变量存储的地址是另一个指针变量的地址。最常见的是二级指针（指向指针的指针）。
A. 定义与使用：
-
类型 **指针变量名;：定义一个二级指针。 -
类型 ***指针变量名;：定义一个三级指针，以此类推。
#include <stdio.h>
#include <stdlib.h> // For malloc
int main() {
int value = 100;
int* ptr_to_value = &value; // 一级指针，指向value
int** ptr_to_ptr = &ptr_to_value; // 二级指针，指向ptr_to_value
// 访问原始变量的值：
printf("value: %d\n", value); // 直接访问
printf("*ptr_to_value: %d\n", *ptr_to_value); // 通过一级指针解引用
printf("**ptr_to_ptr: %d\n", **ptr_to_ptr); // 通过二级指针两次解引用
// 访问指针变量的地址：
printf("&value: %p\n", (void*)&value);
printf("ptr_to_value: %p\n", (void*)ptr_to_value); // 存储的是value的地址
printf("&ptr_to_value: %p\n", (void*)&ptr_to_value);
printf("ptr_to_ptr: %p\n", (void*)ptr_to_ptr); // 存储的是ptr_to_value的地址
// 通过多级指针修改值
**ptr_to_ptr = 200;
printf("修改后 value: %d\n", value); // value 变为 200
printf("\n");
// 经典应用：在函数内部修改指针所指向的内存（例如，为指针分配内存）
// 如果想要函数内部修改外部指针本身的值（即让外部指针指向新的地址），
// 必须传入该外部指针的地址，即二级指针。
int* dynamic_ptr = NULL; // 初始为空
// 错误示例：无法在函数内部修改外部指针本身（只会修改形参）
// void allocate_wrong(int* p) {
// p = (int*)malloc(sizeof(int));
// if (p) *p = 10;
// }
// allocate_wrong(dynamic_ptr); // dynamic_ptr 仍然是 NULL
// 正确示例：传入二级指针来修改外部指针本身
void allocate_correct(int** p) {
*p = (int*)malloc(sizeof(int)); // *p 解引用得到外部指针，然后给它赋值新地址
if (*p) {
**p = 10; // **p 解引用得到外部指针指向的内存，赋值
printf("在函数内部分配并赋值: **p = %d\n", **p);
}
}
printf("dynamic_ptr (分配前): %p\n", (void*)dynamic_ptr);
allocate_correct(&dynamic_ptr); // 传入 dynamic_ptr 的地址
printf("dynamic_ptr (分配后): %p\n", (void*)dynamic_ptr);
if (dynamic_ptr != NULL) {
printf("通过外部 dynamic_ptr 访问值: %d\n", *dynamic_ptr);
free(dynamic_ptr); // 释放内存
dynamic_ptr = NULL;
}
return 0;
}
面试考点： 理解多级指针的含义和分层关系。能够通过多级指针正确地访问和修改数据。重点理解为什么需要在函数中传入二级指针来修改一级指针所指向的地址，这是动态内存管理和链表操作（如删除头节点）中非常重要的概念。
7.3 指针数组与数组指针：形似神异
这两种概念的名称非常相似，但含义截然不同，是面试中常见的混淆点。
A. 指针数组（Array of Pointers）：
-
定义：
类型* 数组名[大小]; -
含义： 一个数组，其每个元素都是一个指针。
-
用途： 存储多个字符串（
char*[]），或者指向不同数据结构实例的指针。
#include <stdio.h>
int main() {
// 1. 指针数组：存储多个字符串（每个元素都是 char* 类型）
char* names[3]; // 一个包含3个 char* 指针的数组
names[0] = "Alice";
names[1] = "Bob";
names[2] = "Charlie";
printf("指针数组存储的字符串:\n");
for (int i = 0; i < 3; i++) {
printf("names[%d]: %s (地址: %p)\n", i, names[i], (void*)names[i]);
}
printf("\n");
// 2. 指针数组：存储指向整数的指针
int a = 10, b = 20, c = 30;
int* int_ptrs[3]; // 一个包含3个 int* 指针的数组
int_ptrs[0] = &a;
int_ptrs[1] = &b;
int_ptrs[2] = &c;
printf("指针数组存储的整数值:\n");
for (int i = 0; i < 3; i++) {
printf("*int_ptrs[%d]: %d (地址: %p)\n", i, *int_ptrs[i], (void*)int_ptrs[i]);
}
printf("\n");
return 0;
}
B. 数组指针（Pointer to Array）：
-
定义：
类型 (*指针变量名)[大小]; -
含义： 一个指针，它指向整个数组（而不是数组的第一个元素）。
-
用途： 访问多维数组。
#include <stdio.h>
int main() {
int arr[3] = {10, 20, 30};
// 1. 数组指针：指向一个包含3个int的数组
int (*ptr_to_arr)[3]; // 声明一个指针，它指向一个包含3个int的数组
ptr_to_arr = &arr; // 将整个数组arr的地址赋给ptr_to_arr
// 注意这里是 &arr，而不是 arr (arr会退化为指向第一个元素的指针)
printf("数组 arr 的地址: %p\n", (void*)arr);
printf("ptr_to_arr 存储的地址 (即数组起始地址): %p\n", (void*)ptr_to_arr);
printf("ptr_to_arr 自身的地址: %p\n", (void*)&ptr_to_arr);
printf("\n");
// 通过数组指针访问数组元素
printf("通过数组指针访问元素:\n");
printf("(*ptr_to_arr)[0]: %d\n", (*ptr_to_arr)[0]); // 解引用 ptr_to_arr 得到数组本身，再用下标访问
printf("(*ptr_to_arr)[1]: %d\n", (*ptr_to_arr)[1]);
printf("(*ptr_to_arr)[2]: %d\n", (*ptr_to_arr)[2]);
printf("\n");
// 数组指针与多维数组
int matrix[2][3] = {
{1, 2, 3},
{4, 5, 6}
};
// matrix 可以看作是一个指向 int[3] 数组的指针
// 定义一个数组指针，指向一个包含3个int的数组
int (*ptr_to_row)[3];
ptr_to_row = matrix; // matrix 隐式转换为指向第一行的指针
printf("通过数组指针遍历二维数组:\n");
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
printf("%d ", ptr_to_row[i][j]); // ptr_to_row[i] 相当于 *(ptr_to_row + i)，得到第i行数组
}
printf("\n");
}
// 也可以写成 *(*(ptr_to_row + i) + j)
// 甚至 *(*(matrix + i) + j)
return 0;
}
面试考点： 区分指针数组和数组指针的定义和含义，这是最常考的题目之一。能够手写它们的定义并解释各自的应用场景。理解数组名作为指针的退化特性与 &数组名 的区别。
八、高级数据结构：解决复杂问题的利器
除了链表和二叉树，还有许多其他重要的数据结构，它们在算法设计和面试中扮演着核心角色。
8.1 栈（Stack）：后进先出（LIFO）
栈是一种特殊的线性数据结构，只允许在表的一端（栈顶，Top）进行插入（Push）和删除（Pop）操作。其特点是后进先出（Last In, First Out, LIFO）。
实现方式：
-
数组实现： 简单，但需要预先确定大小，可能存在溢出。
-
链表实现： 灵活，动态大小，但每个元素占用更多内存（额外指针）。
A. 数组实现栈：
#include <stdio.h>
#include <stdbool.h> // For bool type
#define MAX_STACK_SIZE 10
int stack[MAX_STACK_SIZE];
int top = -1; // 栈顶指针，-1表示空栈
// 判断栈是否为空
bool is_stack_empty() {
return top == -1;
}
// 判断栈是否已满
bool is_stack_full() {
return top == MAX_STACK_SIZE - 1;
}
// 入栈操作
void push(int value) {
if (is_stack_full()) {
printf("Error: Stack is full. Cannot push %d\n", value);
return;
}
stack[++top] = value; // 栈顶指针先加1，再赋值
printf("Pushed: %d\n", value);
}
// 出栈操作
int pop() {
if (is_stack_empty()) {
printf("Error: Stack is empty. Cannot pop\n");
return -1; // 返回一个错误值
}
return stack[top--]; // 先返回栈顶元素，再将栈顶指针减1
}
// 查看栈顶元素 (不移除)
int peek() {
if (is_stack_empty()) {
printf("Error: Stack is empty. No top element\n");
return -1;
}
return stack[top];
}
void print_stack() {
printf("Stack (Top to Bottom): ");
if (is_stack_empty()) {
printf("Empty\n");
return;
}
for (int i = top; i >= 0; i--) {
printf("%d ", stack[i]);
}
printf("\n");
}
int main() {
print_stack(); // Empty
push(10);
push(20);
push(30);
print_stack(); // 30 20 10
printf("Peek: %d\n", peek()); // 30
printf("Popped: %d\n", pop()); // 30
print_stack(); // 20 10
push(40);
print_stack(); // 40 20 10
while (!is_stack_empty()) {
printf("Popped: %d\n", pop());
}
print_stack(); // Empty
pop(); // Error: Stack is empty.
return 0;
}
面试考点： 深刻理解栈的LIFO特性。掌握栈的基本操作（push, pop, peek, isEmpty, isFull）及其数组或链表实现。常见应用： 函数调用栈、表达式求值（中缀转后缀）、括号匹配、深度优先搜索（DFS）等。
8.2 队列（Queue）：先进先出（FIFO）
队列是一种特殊的线性数据结构，只允许在表的一端（队尾，Rear）进行插入（Enqueue），在另一端（队头，Front）进行删除（Dequeue）操作。其特点是先进先出（First In, First Out, FIFO）。
实现方式：
-
数组实现： 简单，但可能存在“假溢出”（数组前面有空闲空间，但队尾已到数组末尾），可通过循环队列解决。
-
链表实现： 灵活，动态大小，无“假溢出”问题。
A. 数组实现队列（循环队列）：
#include <stdio.h>
#include <stdbool.h>
#define MAX_QUEUE_SIZE 5 // 队列最大容量
int queue_arr[MAX_QUEUE_SIZE];
int front_q = -1; // 队头指针，-1表示空
int rear_q = -1; // 队尾指针，-1表示空
// 判断队列是否为空
bool is_queue_empty() {
return front_q == -1;
}
// 判断队列是否已满 (循环队列的判断条件)
bool is_queue_full() {
// (rear + 1) % MAX_QUEUE_SIZE == front
// 留一个空位，通常用于区分空和满，或者使用一个计数器
// 这里的实现是：当 rear 的下一个位置是 front 时，队列满
return (rear_q + 1) % MAX_QUEUE_SIZE == front_q;
}
// 入队操作
void enqueue(int value) {
if (is_queue_full()) {
printf("Error: Queue is full. Cannot enqueue %d\n", value);
return;
}
if (is_queue_empty()) { // 如果队列为空，则队头和队尾都指向第一个元素
front_q = 0;
}
rear_q = (rear_q + 1) % MAX_QUEUE_SIZE; // 队尾指针向后移动（循环）
queue_arr[rear_q] = value;
printf("Enqueued: %d\n", value);
}
// 出队操作
int dequeue() {
if (is_queue_empty()) {
printf("Error: Queue is empty. Cannot dequeue\n");
return -1;
}
int value = queue_arr[front_q];
if (front_q == rear_q) { // 如果队列中只有一个元素，出队后队列变空
front_q = -1;
rear_q = -1;
} else {
front_q = (front_q + 1) % MAX_QUEUE_SIZE; // 队头指针向后移动（循环）
}
return value;
}
// 查看队头元素 (不移除)
int front_element() {
if (is_queue_empty()) {
printf("Error: Queue is empty. No front element\n");
return -1;
}
return queue_arr[front_q];
}
void print_queue() {
printf("Queue (Front to Rear): ");
if (is_queue_empty()) {
printf("Empty\n");
return;
}
int i = front_q;
while (true) {
printf("%d ", queue_arr[i]);
if (i == rear_q) break;
i = (i + 1) % MAX_QUEUE_SIZE;
}
printf("\n");
}
int main() {
print_queue();
enqueue(10);
enqueue(20);
enqueue(30);
print_queue(); // 10 20 30
printf("Front element: %d\n", front_element()); // 10
printf("Dequeued: %d\n", dequeue()); // 10
print_queue(); // 20 30
enqueue(40);
enqueue(50);
enqueue(60); // 尝试入队，队列满
print_queue(); // 20 30 40 50
printf("Dequeued: %d\n", dequeue()); // 20
printf("Dequeued: %d\n", dequeue()); // 30
printf("Dequeued: %d\n", dequeue()); // 40
printf("Dequeued: %d\n", dequeue()); // 50
print_queue(); // Empty
dequeue(); // Error: Queue is empty.
return 0;
}
面试考点： 深刻理解队列的FIFO特性。掌握队列的基本操作（enqueue, dequeue, front, isEmpty, isFull）及其数组（循环队列）或链表实现。常见应用： 广度优先搜索（BFS）、任务调度、缓存队列、打印队列等。
8.3 哈希表（Hash Table）：快速查找
哈希表（或散列表）是一种根据键（Key）直接访问数据（Value）的数据结构。它通过哈希函数将键映射到数组中的一个索引，从而实现快速的查找、插入和删除操作。理想情况下，平均时间复杂度可达到 O(1)。
解决冲突： 不同的键可能通过哈希函数映射到同一个索引，这称为哈希冲突。常见的解决冲突方法有：
-
链地址法（Separate Chaining）： 数组的每个槽位都指向一个链表（或红黑树等），所有哈希到该槽位的键值对都存储在这个链表中。
-
开放地址法（Open Addressing）： 当发生冲突时，探测（Probe）下一个空槽位来存储数据。常见的探测方法有线性探测、二次探测、双重哈希等。
A. 链地址法实现哈希表：
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // For strcmp, strdup
// 定义哈希表节点结构体 (存储键值对，用于链表)
struct HashNode {
char* key;
int value;
struct HashNode* next;
};
// 定义哈希表结构体
struct HashTable {
struct HashNode** table; // 指向一个HashNode指针数组
int size; // 哈希表的大小（桶的数量）
};
// 哈希函数：将字符串键映射到索引
// 简单的DJB2哈希算法
unsigned int hash_function(const char* key, int table_size) {
unsigned int hash = 5381; // 这是一个魔术数
int c;
while ((c = *key++)) {
hash = ((hash << 5) + hash) + c; // hash * 33 + c
}
return hash % table_size;
}
// 初始化哈希表
struct HashTable* createHashTable(int size) {
struct HashTable* ht = (struct HashTable*)malloc(sizeof(struct HashTable));
if (ht == NULL) {
perror("Failed to allocate HashTable");
exit(EXIT_FAILURE);
}
ht->size = size;
ht->table = (struct HashNode**)calloc(size, sizeof(struct HashNode*)); // calloc自动初始化为NULL
if (ht->table == NULL) {
perror("Failed to allocate hash table array");
free(ht);
exit(EXIT_FAILURE);
}
printf("Hash Table created with size %d.\n", size);
return ht;
}
// 插入键值对
void ht_insert(struct HashTable* ht, const char* key, int value) {
unsigned int index = hash_function(key, ht->size);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
if (newNode == NULL) {
perror("Failed to allocate HashNode");
exit(EXIT_FAILURE);
}
newNode->key = strdup(key); // 复制键字符串，避免悬挂指针
if (newNode->key == NULL) {
perror("Failed to duplicate key string");
free(newNode);
exit(EXIT_FAILURE);
}
newNode->value = value;
newNode->next = ht->table[index]; // 新节点插入到链表头部
ht->table[index] = newNode;
printf("Inserted: Key='%s', Value=%d at index %u\n", key, value, index);
}
// 查找键对应的值
int* ht_search(struct HashTable* ht, const char* key) {
unsigned int index = hash_function(key, ht->size);
struct HashNode* current = ht->table[index];
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
return &(current->value); // 找到，返回指向值的指针
}
current = current->next;
}
return NULL; // 未找到
}
// 删除键值对
void ht_delete(struct HashTable* ht, const char* key) {
unsigned int index = hash_function(key, ht->size);
struct HashNode* current = ht->table[index];
struct HashNode* prev = NULL;
while (current != NULL && strcmp(current->key, key) != 0) {
prev = current;
current = current->next;
}
if (current == NULL) {
printf("Key '%s' not found. Cannot delete.\n", key);
return;
}
if (prev == NULL) { // 删除的是链表头节点
ht->table[index] = current->next;
} else {
prev->next = current->next;
}
printf("Deleted: Key='%s', Value=%d from index %u\n", current->key, current->value, index);
free(current->key); // 释放复制的键字符串
free(current); // 释放节点内存
}
// 打印哈希表内容 (用于调试)
void printHashTable(struct HashTable* ht) {
printf("\n--- Hash Table Contents ---\n");
for (int i = 0; i < ht->size; i++) {
struct HashNode* current = ht->table[i];
if (current != NULL) {
printf("Bucket %d: ", i);
while (current != NULL) {
printf("('%s':%d) -> ", current->key, current->value);
current = current->next;
}
printf("NULL\n");
}
}
printf("---------------------------\n\n");
}
// 释放哈希表所有内存
void freeHashTable(struct HashTable* ht) {
for (int i = 0; i < ht->size; i++) {
struct HashNode* current = ht->table[i];
while (current != NULL) {
struct HashNode* temp = current;
current = current->next;
free(temp->key); // 释放键字符串
free(temp); // 释放节点
}
}
free(ht->table); // 释放桶数组
free(ht); // 释放哈希表结构体
printf("Hash Table memory freed.\n");
}
int main() {
struct HashTable* my_ht = createHashTable(10); // 创建一个大小为10的哈希表
ht_insert(my_ht, "apple", 100);
ht_insert(my_ht, "banana", 200);
ht_insert(my_ht, "cherry", 300);
ht_insert(my_ht, "grape", 400); // 可能会与apple冲突，具体看哈希函数
ht_insert(my_ht, "apricot", 500); // 可能会与apple冲突
printHashTable(my_ht);
int* val;
val = ht_search(my_ht, "banana");
if (val) {
printf("Found 'banana': %d\n", *val); // Found 'banana': 200
} else {
printf("'banana' not found.\n");
}
val = ht_search(my_ht, "orange");
if (val) {
printf("Found 'orange': %d\n", *val);
} else {
printf("'orange' not found.\n"); // 'orange' not found.
}
ht_delete(my_ht, "cherry"); // Deleted: Key='cherry', Value=300 from index X
printHashTable(my_ht);
ht_delete(my_ht, "nonexistent"); // Key 'nonexistent' not found.
freeHashTable(my_ht);
return 0;
}
面试考点： 理解哈希表的原理、哈希函数的作用和哈希冲突的概念。掌握链地址法解决冲突的实现。能够手写哈希表的插入、查找、删除操作。深入考点： 开放地址法（线性探测、二次探测），加载因子，哈希表扩容。
8.4 二叉搜索树（Binary Search Tree, BST）：有序的非线性结构
二叉搜索树（BST）是一种特殊的二叉树，它满足以下条件：
-
左子树中所有节点的值都小于根节点的值。
-
右子树中所有节点的值都大于根节点的值。
-
左右子树也都是二叉搜索树。
BST 使得查找、插入和删除操作的平均时间复杂度为 O(logn)。
#include <stdio.h>
#include <stdlib.h>
// 定义二叉搜索树节点
struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
};
// 函数：创建新节点
struct BSTNode* createBSTNode(int value) {
struct BSTNode* newNode = (struct BSTNode*)malloc(sizeof(struct BSTNode));
if (newNode == NULL) {
perror("Failed to allocate BSTNode");
exit(EXIT_FAILURE);
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 函数：插入节点
struct BSTNode* insertBST(struct BSTNode* root, int value) {
if (root == NULL) { // 找到插入位置或树为空
return createBSTNode(value);
}
if (value < root->data) {
root->left = insertBST(root->left, value);
} else if (value > root->data) {
root->right = insertBST(root->right, value);
}
// 如果值等于root->data，通常不插入或更新，取决于具体需求
return root;
}
// 函数：查找节点
struct BSTNode* searchBST(struct BSTNode* root, int value) {
if (root == NULL || root->data == value) {
return root; // 树为空或找到目标
}
if (value < root->data) {
return searchBST(root->left, value);
} else {
return searchBST(root->right, value);
}
}
// 辅助函数：找到最小值的节点（用于删除操作）
struct BSTNode* findMinNode(struct BSTNode* node) {
struct BSTNode* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
// 函数：删除节点
struct BSTNode* deleteBST(struct BSTNode* root, int value) {
if (root == NULL) {
return root; // 树为空或未找到要删除的节点
}
if (value < root->data) {
root->left = deleteBST(root->left, value);
} else if (value > root->data) {
root->right = deleteBST(root->right, value);
} else { // 找到要删除的节点 (root->data == value)
// 情况1: 节点没有子节点或只有一个子节点
if (root->left == NULL) {
struct BSTNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct BSTNode* temp = root->left;
free(root);
return temp;
}
// 情况2: 节点有两个子节点
// 找到右子树中的最小节点（或左子树中的最大节点）
struct BSTNode* temp = findMinNode(root->right);
root->data = temp->data; // 将temp的数据复制到当前节点
// 递归删除右子树中的temp节点
root->right = deleteBST(root->right, temp->data);
}
return root;
}
// 中序遍历 (BST的中序遍历结果是排好序的)
void inorderTraversalBST(struct BSTNode* root) {
if (root == NULL) {
return;
}
inorderTraversalBST(root->left);
printf("%d ", root->data);
inorderTraversalBST(root->right);
}
// 函数：释放二叉搜索树所有节点内存
void freeBST(struct BSTNode* root) {
if (root == NULL) {
return;
}
freeBST(root->left);
freeBST(root->right);
free(root);
}
int main() {
struct BSTNode* root = NULL;
// 插入操作
root = insertBST(root, 50);
insertBST(root, 30);
insertBST(root, 70);
insertBST(root, 20);
insertBST(root, 40);
insertBST(root, 60);
insertBST(root, 80);
printf("BST Inorder Traversal (Sorted): ");
inorderTraversalBST(root); // Expected: 20 30 40 50 60 70 80
printf("\n");
// 查找操作
struct BSTNode* found_node = searchBST(root, 40);
if (found_node) {
printf("Found 40 in BST.\n");
} else {
printf("40 not found.\n");
}
found_node = searchBST(root, 90);
if (found_node) {
printf("Found 90 in BST.\n");
} else {
printf("90 not found.\n");
}
printf("\n");
// 删除操作
printf("Deleting 20...\n");
root = deleteBST(root, 20);
printf("Inorder Traversal after deleting 20: ");
inorderTraversalBST(root); // Expected: 30 40 50 60 70 80
printf("\n");
printf("Deleting 70...\n");
root = deleteBST(root, 70);
printf("Inorder Traversal after deleting 70: ");
inorderTraversalBST(root); // Expected: 30 40 50 60 80
printf("\n");
printf("Deleting 50 (root with two children)...\n");
root = deleteBST(root, 50);
printf("Inorder Traversal after deleting 50: ");
inorderTraversalBST(root); // Expected: 30 40 60 80 (new root could be 60)
printf("\n");
freeBST(root);
return 0;
}
面试考点： 深刻理解二叉搜索树的定义和特性。掌握BST的插入、查找、删除（尤其是有两个子节点的情况）操作。理解中序遍历在BST中的特殊意义（得到有序序列）。高级考点： 平衡二叉搜索树（AVL树、红黑树）的概念及其平衡调整原理（无需手写代码，但需理解）。
九、排序与查找算法：解决问题的核心策略
排序和查找是计算机科学中最基本、最重要的问题之一，也是算法面试的重中之重。
9.1 排序算法：数据的组织艺术
排序是将一组数据按照特定顺序（升序或降序）重新排列的过程。
A. 冒泡排序（Bubble Sort）：
-
原理： 重复遍历列表，比较相邻元素，如果顺序错误就交换它们，直到没有元素可以再交换。
-
特点： 简单直观，但效率低下。
-
时间复杂度： 最佳 O(n)，平均 O(n2)，最坏 O(n2)。
-
空间复杂度： O(1)（原地排序）。
-
稳定性： 稳定。
#include <stdio.h>
// 冒泡排序函数
void bubbleSort(int arr[], int n) {
int i, j;
bool swapped; // 标志位，用于优化，如果一趟扫描没有发生交换，则数组已排序
for (i = 0; i < n - 1; i++) {
swapped = false; // 假设本趟没有交换
// 每趟结束后，最大的元素会被“冒泡”到数组末尾已排序区域
for (j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // 发生交换
}
}
// 如果一趟没有发生交换，说明数组已经有序，提前结束
if (swapped == false) {
break;
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted array: ");
printArray(arr, n); // Output: 11 12 22 25 34 64 90
return 0;
}
B. 选择排序（Selection Sort）：
-
原理： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到所有元素排完。
-
特点： 简单，但性能比冒泡略好（交换次数少）。
-
时间复杂度： 始终 O(n2)。
-
空间复杂度： O(1)（原地排序）。
-
稳定性： 不稳定。
#include <stdio.h>
// 选择排序函数
void selectionSort(int arr[], int n) {
int i, j, min_idx;
// 遍历未排序部分
for (i = 0; i < n - 1; i++) {
min_idx = i; // 假设当前元素是最小的
// 在未排序部分中找到最小元素的索引
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 将找到的最小元素与当前位置 (arr[i]) 交换
// 如果 min_idx 不是 i，才进行交换
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}
// printArray 函数与冒泡排序示例相同
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n); // Output: 11 12 22 25 64
return 0;
}
C. 插入排序（Insertion Sort）：
-
原理： 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
-
特点： 对于部分有序的数组效率高，实现简单。
-
时间复杂度： 最佳 O(n)，平均 O(n2)，最坏 O(n2)。
-
空间复杂度： O(1)（原地排序）。
-
稳定性： 稳定。
#include <stdio.h>
// 插入排序函数
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) { // 从第二个元素开始遍历
key = arr[i]; // 当前要插入的元素
j = i - 1; // 已排序部分的最后一个元素的索引
// 将比key大的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // 插入key到正确位置
}
}
// printArray 函数与冒泡排序示例相同
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
insertionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n); // Output: 5 6 11 12 13
return 0;
}
D. 快速排序（Quick Sort）：
-
原理： 采用分治策略。选择一个“基准元素”（pivot），将数组分为两部分：小于基准的元素放在一边，大于基准的元素放在另一边。然后递归地对这两部分进行快速排序。
-
特点： 通常是实践中最快的通用排序算法。
-
时间复杂度： 最佳 O(nlogn)，平均 O(nlogn)，最坏 O(n2)（可以通过选择好的基准元素避免）。
-
空间复杂度： O(logn)（递归栈空间），最坏 O(n)。
-
稳定性： 不稳定。
#include <stdio.h>
// 交换函数
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 分区函数：返回基准元素的最终位置
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // 小于基准的元素的索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于等于基准
if (arr[j] <= pivot) {
i++; // 增加小于基准的元素的索引
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); // 将基准元素放到正确的位置
return (i + 1);
}
// 快速排序主函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi 是分区索引，arr[pi] 现在在正确的位置
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // 递归排序左子数组
quickSort(arr, pi + 1, high); // 递归排序右子数组
}
}
// printArray 函数与冒泡排序示例相同
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n); // Output: 1 5 7 8 9 10
return 0;
}
E. 归并排序（Merge Sort）：
-
原理： 采用分治策略。将数组递归地分成两半，直到只剩下单个元素。然后将这些已排序的子数组合并（Merge）起来，形成更大的有序数组。
-
特点： 稳定排序，时间复杂度始终为 O(nlogn)，适合处理大数据量。
-
时间复杂度： 始终 O(nlogn)。
-
空间复杂度： O(n)（需要额外的辅助空间）。
-
稳定性： 稳定。
#include <stdio.h>
#include <stdlib.h> // For malloc, free
// 合并两个有序子数组
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1; // 左子数组大小
int n2 = r - m; // 右子数组大小
// 创建临时数组
int* L = (int*)malloc(n1 * sizeof(int));
int* R = (int*)malloc(n2 * sizeof(int));
if (L == NULL || R == NULL) {
perror("Memory allocation failed in merge");
exit(EXIT_FAILURE);
}
// 复制数据到临时数组L[]和R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// 合并临时数组到 arr[l..r]
i = 0; // L 的初始索引
j = 0; // R 的初始索引
k = l; // 合并数组的初始索引
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制L[]中剩余的元素（如果有）
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 复制R[]中剩余的元素（如果有）
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
free(L); // 释放临时数组内存
free(R);
}
// 归并排序主函数
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; // 避免 l+r 溢出
// 递归地对两半进行排序
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// 合并已排序的两半
merge(arr, l, m, r);
}
}
// printArray 函数与冒泡排序示例相同
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n); // Output: 5 6 7 11 12 13
return 0;
}
F. 堆排序（Heap Sort）：
-
原理： 利用堆这种数据结构（通常是最大堆）。首先将待排序序列构建成一个最大堆，然后将堆顶元素（最大值）与最后一个元素交换，接着将剩余元素重新调整为最大堆，重复此过程直到所有元素有序。
-
特点： 原地排序，时间复杂度稳定。
-
时间复杂度： 始终 O(nlogn)。
-
空间复杂度： O(1)（原地排序）。
-
稳定性： 不稳定。
#include <stdio.h>
// 交换函数 (与快速排序相同)
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 堆化函数：维护最大堆的性质
// n 是堆的大小，i 是要堆化的子树的根节点索引
void heapify(int arr[], int n, int i) {
int largest = i; // 初始化最大元素为根
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比根大
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点比目前的最大值大
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大元素不是根
if (largest != i) {
swap(&arr[i], &arr[largest]);
// 递归地堆化受影响的子树
heapify(arr, n, largest);
}
}
// 堆排序主函数
void heapSort(int arr[], int n) {
// 1. 构建最大堆 (从最后一个非叶子节点开始向上堆化)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 2. 一个个地从堆中提取元素
for (int i = n - 1; i > 0; i--) {
// 将当前堆顶（最大值）与末尾元素交换
swap(&arr[0], &arr[i]);
// 对剩余的堆进行堆化 (范围减小)
heapify(arr, i, 0);
}
}
// printArray 函数与冒泡排序示例相同
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
heapSort(arr, n);
printf("Sorted array: ");
printArray(arr, n); // Output: 5 6 7 11 12 13
return 0;
}
面试考点： 掌握所有排序算法的原理、时间复杂度、空间复杂度、稳定性。能够手写冒泡、选择、插入、快速排序的实现（通常在白板上）。理解归并排序和堆排序的分治/堆化思想。重点关注快速排序的实现细节和最坏情况避免，以及归并排序的稳定性。
9.2 查找算法：数据的定位艺术
查找是在数据集合中寻找特定元素的过程。
A. 顺序查找（Sequential Search / Linear Search）：
-
原理： 从数据集合的第一个元素开始，逐个与目标值比较，直到找到或遍历完所有元素。
-
特点： 简单，适用于任何无序或有序的线性数据结构。
-
时间复杂度： 最佳 O(1)，平均 O(n)，最坏 O(n)。
#include <stdio.h>
#include <stdbool.h>
// 顺序查找函数
int sequentialSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // 找到目标，返回索引
}
}
return -1; // 未找到，返回-1
}
int main() {
int arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
int n = sizeof(arr) / sizeof(arr[0]);
int target1 = 30;
int target2 = 99;
int index1 = sequentialSearch(arr, n, target1);
if (index1 != -1) {
printf("Target %d found at index %d.\n", target1, index1); // Found 30 at index 3.
} else {
printf("Target %d not found.\n", target1);
}
int index2 = sequentialSearch(arr, n, target2);
if (index2 != -1) {
printf("Target %d found at index %d.\n", target2, index2);
} else {
printf("Target %d not found.\n", target2); // 99 not found.
}
return 0;
}
B. 二分查找（Binary Search）：
-
原理： 适用于有序数据集合。每次通过比较中间元素与目标值，将查找范围缩小一半。
-
特点： 效率高。
-
时间复杂度： 始终 O(logn)。
-
空间复杂度： O(1)（迭代实现）或 O(logn)（递归实现）。
#include <stdio.h>
// 二分查找函数 (迭代实现)
int binarySearch(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2; // 避免 (low + high) 溢出
// 目标值在中间
if (arr[mid] == target) {
return mid;
}
// 目标值在左半部分
if (arr[mid] > target) {
high = mid - 1;
}
// 目标值在右半部分
else {
low = mid + 1;
}
}
return -1; // 未找到
}
// 二分查找函数 (递归实现)
int binarySearchRecursive(int arr[], int low, int high, int target) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] > target) {
return binarySearchRecursive(arr, low, mid - 1, target);
}
return binarySearchRecursive(arr, mid + 1, high, target);
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int n = sizeof(arr) / sizeof(arr[0]);
int target1 = 30;
int target2 = 99;
int index1_iter = binarySearch(arr, 0, n - 1, target1);
if (index1_iter != -1) {
printf("Target %d (iterative) found at index %d.\n", target1, index1_iter); // Found 30 at index 2.
} else {
printf("Target %d (iterative) not found.\n", target1);
}
int index2_iter = binarySearch(arr, 0, n - 1, target2);
if (index2_iter != -1) {
printf("Target %d (iterative) found at index %d.\n", target2, index2_iter);
} else {
printf("Target %d (iterative) not found.\n", target2); // 99 not found.
}
int index1_rec = binarySearchRecursive(arr, 0, n - 1, target1);
if (index1_rec != -1) {
printf("Target %d (recursive) found at index %d.\n", target1, index1_rec);
} else {
printf("Target %d (recursive) not found.\n", target1);
}
return 0;
}
面试考点： 理解顺序查找和二分查找的原理和适用场景。重点掌握二分查找（迭代和递归实现），能够清晰地编写其代码，并解释其时间复杂度优势。
十、文件I/O：与外部数据交互
文件I/O（Input/Output）允许程序与磁盘上的文件进行交互，读取数据或将数据写入文件。这是持久化数据和处理大量数据的基本方式。
10.1 文件操作的基本流程
文件操作通常遵循以下步骤：
-
打开文件： 使用
fopen()函数。 -
读写文件： 使用
fgetc(),fputc(),fgets(),fputs(),fprintf(),fscanf(),fread(),fwrite()等函数。 -
关闭文件： 使用
fclose()函数。
10.2 文本文件读写
文本文件以人类可读的字符形式存储数据。
#include <stdio.h> // 包含文件操作函数
int main() {
FILE* fp; // 声明一个文件指针
// --- 1. 写入文本文件 ---
fp = fopen("example.txt", "w"); // "w" 模式：写入模式，如果文件不存在则创建，如果存在则清空
if (fp == NULL) {
perror("Error opening file for writing"); // 打印错误信息
return 1;
}
fprintf(fp, "Hello C Language!\n"); // 写入格式化字符串到文件
fputs("This is a new line.\n", fp); // 写入字符串到文件
fputc('A', fp); // 写入单个字符
fputc('\n', fp);
fclose(fp); // 关闭文件
printf("Data written to example.txt\n");
// --- 2. 读取文本文件 ---
fp = fopen("example.txt", "r"); // "r" 模式：读取模式
if (fp == NULL) {
perror("Error opening file for reading");
return 1;
}
char buffer[100]; // 缓冲区用于存储读取的行
printf("\nReading from example.txt:\n");
// fgets 逐行读取，包括换行符
while (fgets(buffer, sizeof(buffer), fp) != NULL) {
printf("%s", buffer); // 直接打印缓冲区内容
}
// 或者逐字符读取
// int ch;
// while ((ch = fgetc(fp)) != EOF) { // EOF (End Of File)
// putchar(ch); // 打印到控制台
// }
fclose(fp);
printf("Finished reading from example.txt\n");
// --- 3. 追加文本文件 ---
fp = fopen("example.txt", "a"); // "a" 模式：追加模式，在文件末尾添加内容
if (fp == NULL) {
perror("Error opening file for appending");
return 1;
}
fprintf(fp, "This line is appended.\n");
fclose(fp);
printf("\nData appended to example.txt\n");
return 0;
}
10.3 二进制文件读写
二进制文件以字节流的形式存储数据，不进行任何字符转换。适用于存储结构化数据（如结构体数组）或图像、音频等。
#include <stdio.h>
#include <stdlib.h>
// 定义一个简单的结构体
struct Record {
int id;
char name[20];
float value;
};
int main() {
FILE* fp;
struct Record rec1 = {1, "Alice", 10.5f};
struct Record rec2 = {2, "Bob", 20.0f};
struct Record read_rec;
// --- 1. 写入二进制文件 ---
fp = fopen("records.bin", "wb"); // "wb" 模式：写入二进制文件
if (fp == NULL) {
perror("Error opening binary file for writing");
return 1;
}
// fwrite(数据源, 元素大小, 元素数量, 文件指针)
fwrite(&rec1, sizeof(struct Record), 1, fp);
fwrite(&rec2, sizeof(struct Record), 1, fp);
fclose(fp);
printf("Records written to records.bin\n");
// --- 2. 读取二进制文件 ---
fp = fopen("records.bin", "rb"); // "rb" 模式：读取二进制文件
if (fp == NULL) {
perror("Error opening binary file for reading");
return 1;
}
printf("\nReading from records.bin:\n");
// fread(目标缓冲区, 元素大小, 元素数量, 文件指针)
while (fread(&read_rec, sizeof(struct Record), 1, fp) == 1) {
printf("ID: %d, Name: %s, Value: %.1f\n", read_rec.id, read_rec.name, read_rec.value);
}
fclose(fp);
// --- 3. 文件指针定位 ---
fp = fopen("records.bin", "rb+"); // "rb+" 模式：读写二进制文件
if (fp == NULL) {
perror("Error opening binary file for read/write");
return 1;
}
// 将文件指针定位到第二个记录 (rec2) 的开头
// SEEK_SET: 从文件开头算起
// SEEK_CUR: 从当前位置算起
// SEEK_END: 从文件末尾算起
fseek(fp, sizeof(struct Record), SEEK_SET);
// 读取第二个记录
if (fread(&read_rec, sizeof(struct Record), 1, fp) == 1) {
printf("\nRead second record after fseek: ID: %d, Name: %s, Value: %.1f\n", read_rec.id, read_rec.name, read_rec.value);
}
// 修改第二个记录的值
read_rec.value = 99.9f;
strcpy(read_rec.name, "EditedBob");
// 将文件指针再次定位到第二个记录的开头，然后写入
fseek(fp, -sizeof(struct Record), SEEK_CUR); // 从当前位置（第二个记录末尾）回退一个记录大小
fwrite(&read_rec, sizeof(struct Record), 1, fp);
printf("Second record updated.\n");
fclose(fp);
// 重新打开文件验证修改
fp = fopen("records.bin", "rb");
if (fp == NULL) {
perror("Error opening binary file for final verification");
return 1;
}
printf("\nVerifying updated records:\n");
while (fread(&read_rec, sizeof(struct Record), 1, fp) == 1) {
printf("ID: %d, Name: %s, Value: %.1f\n", read_rec.id, read_rec.name, read_rec.value);
}
fclose(fp);
return 0;
}
面试考点： 掌握 fopen, fclose 的使用和文件模式（r, w, a, rb, wb, ab, r+, w+, a+, rb+, wb+, ab+）。理解文本I/O（fprintf, fscanf, fgets, fputs）和二进制I/O（fread, fwrite）的区别。掌握 fseek, ftell, rewind 进行文件指针定位。
十一、错误处理与调试：保证程序健壮性
在C语言编程中，错误处理和调试是不可或缺的技能，它们能帮助你编写更健壮的程序并快速定位问题。
11.1 错误处理：errno, perror, strerror
C标准库提供了一套基本的错误报告机制。
-
errno：一个全局整型变量，当系统调用或库函数发生错误时，会设置这个变量为一个错误码。 -
perror(const char* s)：打印一个错误消息到标准错误输出（stderr）。消息通常是s字符串，后面跟着一个冒号，然后是errno对应的系统错误描述。 -
strerror(int errnum)：返回一个指向字符串的指针，该字符串是错误码errnum对应的系统错误描述。
#include <stdio.h>
#include <stdlib.h> // For exit()
#include <errno.h> // For errno
#include <string.h> // For strerror()
int main() {
FILE* fp;
// 尝试打开一个不存在的文件进行读取
fp = fopen("non_existent_file.txt", "r");
if (fp == NULL) {
// 打印错误信息的第一种方式：使用 perror
perror("Error opening non_existent_file.txt");
// Output example: Error opening non_existent_file.txt: No such file or directory
// 打印错误信息的第二种方式：手动组合
// printf("Error code: %d\n", errno); // errno 保存了具体的错误码
// printf("Error description: %s\n", strerror(errno)); // strerror 返回错误描述字符串
} else {
printf("Successfully opened non_existent_file.txt (unexpected).\n");
fclose(fp);
}
printf("\n");
// 模拟一个内存分配失败
int* large_array = (int*)malloc(1024 * 1024 * sizeof(int) * 1000); // 尝试分配一个巨大的内存块
if (large_array == NULL) {
perror("Error allocating large array");
} else {
printf("Successfully allocated large array.\n");
free(large_array);
}
return 0;
}
面试考点： 了解C语言中通过 errno、perror、strerror 进行错误处理的基本方法。理解这些机制在系统编程和底层开发中的重要性。
11.2 断言：assert
assert 宏（定义在 <assert.h> 中）用于在程序运行时检查某个条件是否为真。如果条件为假，程序会终止执行，并打印一条错误消息，指出失败的表达式、源文件和行号。
特点：
-
调试用途： 主要用于开发和调试阶段，帮助程序员快速发现逻辑错误或不应该发生的条件。
-
发布版本移除： 在编译发布版本时，可以通过定义
NDEBUG宏来禁用所有assert语句，从而避免其运行时开销和意外终止。-
gcc -D NDEBUG your_program.c -o your_program
-
#include <stdio.h>
#include <assert.h> // 包含assert宏
// 函数：计算两个数的商
double divide(int a, int b) {
// 使用assert确保除数不为零
// 如果 b 为 0，程序将终止并报告错误
assert(b != 0);
return (double)a / b;
}
int main() {
printf("Dividing 10 by 2: %.2f\n", divide(10, 2));
printf("Dividing 10 by 0...\n");
// 这将触发assert，如果NDEBUG未定义，程序会终止
printf("Result: %.2f\n", divide(10, 0));
printf("This line will not be executed if assert is triggered.\n");
return 0;
}
面试考点： 掌握 assert 的使用场景和目的。理解 assert 在调试和验证程序逻辑中的作用。知道如何通过 NDEBUG 宏在发布版本中禁用 assert。
11.3 调试工具（概念性：GDB）
虽然本教程不深入GDB的具体操作，但理解其作用对于C语言开发至关重要。
GDB (GNU Debugger) 是一款强大的命令行调试工具，用于在程序运行时检查其内部状态。
-
断点 (Breakpoints)： 在代码的特定行设置，程序执行到此处会暂停。
-
单步执行 (Step-by-step Execution)： 逐行执行代码，观察变量变化。
-
查看变量值 (Inspect Variables)： 随时查看任何变量的当前值。
-
栈回溯 (Stack Trace)： 查看函数调用链。
-
修改变量值 (Modify Variables)： 运行时修改变量值以测试不同情况。
编译时添加调试信息： gcc -g your_program.c -o your_program （-g 选项添加调试信息）
运行GDB： gdb ./your_program
面试考点： 了解GDB作为C/C++调试工具的基本概念和常用功能（断点、单步、查看变量、栈回溯）。
十二、内存优化与常见陷阱：C语言的“双刃剑”
C语言直接操作内存的能力赋予了它强大的性能，但也带来了内存管理上的挑战。
12.1 内存泄漏（Memory Leak）回顾
-
定义： 动态分配的内存（
malloc、calloc、realloc）在使用完毕后没有被free释放，导致这部分内存无法被程序再次使用，也无法被操作系统回收，直到程序结束。 -
危害： 长期运行的程序内存占用不断增长，最终可能导致系统内存耗尽，影响其他程序的运行甚至系统崩溃。
示例：
#include <stdio.h>
#include <stdlib.h>
void cause_memory_leak() {
int* ptr = (int*)malloc(100 * sizeof(int)); // 分配内存
if (ptr == NULL) {
perror("malloc failed");
return;
}
printf("Memory allocated at %p, but not freed (leak).\n", (void*)ptr);
// ptr 在函数结束时超出作用域，但其指向的内存没有被free，导致内存泄漏
}
int main() {
cause_memory_leak();
// 此时，之前分配的100个int的内存已经泄漏
printf("Program finished, but memory might have leaked.\n");
return 0;
}
避免： 遵循“谁分配谁释放”原则。每次 malloc 后，都应该有对应的 free。对于复杂的内存管理，可以考虑使用智能指针（C++）或引用计数/垃圾回收（其他语言），但在纯C中需要手动严谨管理。
面试考点： 深刻理解内存泄漏的定义、危害和产生场景。能够给出避免内存泄漏的策略。
12.2 段错误（Segmentation Fault）
-
定义： 当程序尝试访问其不应该访问的内存区域时（例如，访问受保护的内存、读写只读内存、访问野指针或空指针指向的内存），操作系统会发送一个信号给程序，通常导致程序终止，并报告“段错误”（Segment Fault）。
-
常见原因：
-
解引用空指针或野指针。
-
数组越界访问。
-
栈溢出。
-
修改字符串字面量（存储在只读数据区）。
-
对已释放的内存进行读写（Use-After-Free）。
-
双重释放（Double Free）。
-
示例： （部分在指针部分已演示，这里补充一个字符串字面量）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
// 1. 修改字符串字面量 (通常导致段错误)
// 字符串字面量 "Hello" 存储在只读数据区
char* str_literal = "Hello";
// str_literal[0] = 'J'; // 尝试修改只读内存，会导致段错误！
// 正确的做法：如果需要修改字符串内容，将其存储在可写数组中
char str_array[] = "Hello";
str_array[0] = 'J';
printf("Modified str_array: %s\n", str_array); // Jello
// 2. 数组越界访问 (可能导致段错误，也可能产生难以察觉的bug)
int arr[5];
// arr[5] = 100; // 访问越界，C语言不检查，可能覆盖其他数据或导致段错误
// 3. 对已释放内存的读写 (Use-After-Free)
int* ptr = (int*)malloc(sizeof(int));
if (ptr) {
*ptr = 10;
printf("Initial value: %d\n", *ptr);
free(ptr);
// ptr 此时是野指针
// *ptr = 20; // 危险！Use-After-Free，可能导致段错误
// printf("Value after use-after-free: %d\n", *ptr);
ptr = NULL; // 最佳实践
}
return 0;
}
面试考点： 解释段错误的定义和常见原因。能够识别代码中可能导致段错误的典型场景。
12.3 缓冲区的安全性：gets vs fgets，sprintf vs snprintf
在处理字符串和缓冲区时，C语言提供了不安全的函数和更安全的替代品。
-
gets()(不安全)： 从标准输入读取一行字符，直到遇到换行符或文件结束符。它不检查缓冲区大小，可能导致缓冲区溢出。 -
fgets(char* s, int size, FILE* stream)(安全)： 从stream读取最多size-1个字符到s，并在末尾添加\0。如果读取到换行符或文件结束符，也会停止。 -
sprintf()(不安全)： 将格式化的数据写入字符串。不检查目标缓冲区大小，可能导致缓冲区溢出。 -
snprintf(char* s, size_t n, const char* format, ...)(安全)： 将格式化的数据写入字符串s，最多写入n-1个字符，并在末尾添加\0。
#include <stdio.h>
#include <string.h>
int main() {
char buffer_unsafe[10]; // 缓冲区大小10
// --- gets() 的不安全性 ---
printf("Enter a string (gets is unsafe): ");
// gets(buffer_unsafe); // 极其不安全！如果输入超过9个字符，会溢出
// printf("You entered: %s\n", buffer_unsafe);
// --- fgets() 的安全性 ---
printf("Enter a string (fgets is safe): ");
if (fgets(buffer_unsafe, sizeof(buffer_unsafe), stdin) != NULL) {
// fgets 会读取换行符，如果不需要可以手动移除
buffer_unsafe[strcspn(buffer_unsafe, "\n")] = '\0'; // 移除末尾的换行符
printf("You entered (fgets): %s\n", buffer_unsafe);
}
printf("\n");
char dest_buffer_unsafe[20];
int num = 123456789;
// --- sprintf() 的不安全性 ---
// sprintf(dest_buffer_unsafe, "Number: %d, long string: %s", num, "This is a very very long string.");
// printf("Unsafe sprintf: %s\n", dest_buffer_unsafe); // 可能溢出
// --- snprintf() 的安全性 ---
char dest_buffer_safe[20]; // 缓冲区大小20
int bytes_written = snprintf(dest_buffer_safe, sizeof(dest_buffer_safe), "Number: %d, long string: %s", num, "This is a very very long string.");
printf("Safe snprintf (bytes written: %d): %s\n", bytes_written, dest_buffer_safe); // 会被截断，但不会溢出
// Output: Safe snprintf (bytes written: 46): Number: 123456789, long
// 注意：bytes_written 是如果缓冲区足够大时会写入的字符数，不代表实际写入数
return 0;
}
面试考点： 强调缓冲区溢出的危害。明确 gets 和 sprintf 的不安全性，并推荐使用 fgets 和 snprintf 作为更安全的替代方案。
12.4 栈溢出（Stack Overflow）
-
定义： 当程序使用的栈空间超过了系统或程序预设的栈大小限制时，就会发生栈溢出。通常由于无限递归或局部变量占用过大空间引起。
-
危害： 程序崩溃（段错误）。
示例：
#include <stdio.h>
// 无限递归导致栈溢出
void infinite_recursion() {
char buffer[1024]; // 每次调用都在栈上分配1KB
printf("Stack frames building up...\n");
infinite_recursion(); // 递归调用自身
}
int main() {
// 局部变量占用过大空间 (也可能导致栈溢出，但编译时通常会有警告或错误)
// char large_buffer[1024 * 1024 * 10]; // 10MB，可能直接编译不过或运行时溢出
printf("Starting infinite recursion...\n");
infinite_recursion(); // 调用函数，最终导致栈溢出
return 0;
}
面试考点： 解释栈溢出的原因（无限递归、大局部变量）。理解栈空间有限的特性。
十三、牛客热题101必刷榜真题解析（精选）
我们将挑选几道牛客网“面试必刷101”榜单中的经典C语言题目进行解析。这些题目旨在考察你对基础知识、数据结构和算法的综合运用能力。
由于篇幅限制，这里只提供题目类型和思路，具体代码实现和更详细的解析将在实战环节中进行。
13.1 BM23 二叉树的前序遍历
题目描述： 给定一个二叉树的根节点，返回其节点值的前序遍历。
考查点：
-
二叉树节点的定义（结构体和指针）。
-
递归的思想。
-
二叉树遍历（前序、中序、后序）的实现。
思路：
-
前序遍历顺序：根 -> 左子树 -> 右子树。
-
使用递归函数：
-
如果当前节点为空，返回。
-
访问当前节点（将其值加入结果列表）。
-
递归遍历左子树。
-
递归遍历右子树。
-
示例代码（核心逻辑，已在c_lang_tutorial_part1的“6.2 树”中给出）：
void preorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data); // 访问根节点
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
13.2 BM28 二叉树的最大深度
题目描述： 给定一个二叉树的根节点，返回其最大深度。
考查点：
-
递归的思想。
-
树的层级概念。
思路：
-
递归定义： 空树的深度为0。非空树的深度是其左右子树深度的最大值加1（加上根节点本身）。
-
使用递归函数：
-
如果节点为空，返回0。
-
递归计算左子树的最大深度
left_depth。 -
递归计算右子树的最大深度
right_depth。 -
返回
max(left_depth, right_depth) + 1。
-
示例代码（核心逻辑，已在c_lang_tutorial_part1的“6.2 树”中给出）：
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
13.3 BM30 二叉搜索树与双向链表
题目描述： 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点的指针指向。
考查点：
-
二叉搜索树（BST）的特性。
-
双向链表的结构与操作。
-
中序遍历的应用。
-
递归与指针的复杂操作。
思路：
-
BST的中序遍历特性： BST的中序遍历结果是升序的。因此，我们可以对二叉搜索树进行中序遍历，并在遍历过程中构建双向链表。
-
不创建新节点： 利用二叉树节点的
left和right指针来充当双向链表的prev和next指针。 -
递归实现：
-
定义一个全局或传递引用的
prev指针，用于记录中序遍历中的前一个节点。 -
doFunc(root):-
递归处理
root->left。 -
处理当前节点
root：-
root->left = prev;（将当前节点的左指针指向前一个节点，作为双向链表的prev） -
如果
prev不为空，prev->right = root;（将前一个节点的右指针指向当前节点，作为双向链表的next） -
更新
prev = root;（当前节点成为下一个递归调用的prev）
-
-
递归处理
root->right。
-
-
-
获取头节点： 转换完成后，链表的头节点是原二叉搜索树中值最小的节点，可以通过不断沿着
left指针（即新链表的prev指针）向前找到。
13.4 BM32 合并二叉树
题目描述： 假设两棵二叉树的某些节点重叠，当它们重叠时，它们的值相加作为新的节点值；否则，不重叠的节点将直接作为新树的节点。
考查点：
-
二叉树的递归操作。
-
处理空节点的情况。
思路：
-
递归实现：
-
基本情况：
-
如果
t1为空，返回t2。 -
如果
t2为空，返回t1。
-
-
递归处理：
-
t1->val += t2->val;（重叠节点值相加） -
t1->left = mergeTrees(t1->left, t2->left);（递归合并左子树） -
t1->right = mergeTrees(t1->right, t2->right);（递归合并右子树） -
返回
t1作为合并后的子树根节点。
-
-
示例代码（核心逻辑，已在文件 BM32合并二叉树.c 中给出，但原先代码有一些注释掉的旧逻辑，这里给出精简版）：
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode *mergeTrees(struct TreeNode *t1, struct TreeNode *t2)
{
// write code here
if (t1 == NULL) // 如果t1为空，直接返回t2（无论t2是否为空）
return t2;
if (t2 == NULL) // 如果t2为空，但t1不为空，直接返回t1
return t1;
// t1和t2均不为空，则重叠，值相加
t1->val += t2->val;
// 递归合并左右子树
t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
return t1; // 返回合并后的t1作为根节点
}
13.5 BM33 二叉树镜像
题目描述： 操作给定的二叉树，将其变换为源二叉树的镜像。
考查点：
-
二叉树的递归操作。
-
指针交换。
思路：
-
递归实现：
-
基本情况： 如果当前节点为空，返回。
-
交换子节点： 交换当前节点的左子树和右子树。
-
递归处理： 递归地对交换后的左子树和右子树进行镜像操作。
-
示例代码（核心逻辑，已在文件 BM33二叉树镜像.c 中给出，这里给出精简版）：
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode *Mirror(struct TreeNode *pRoot)
{
// write code here
if (pRoot == NULL) { // 边界条件：如果当前节点为空，则返回
return NULL; // 或者直接返回 pRoot;
}
// 交换当前节点的左右子树
struct TreeNode* temp = pRoot->right;
pRoot->right = pRoot->left;
pRoot->left = temp;
// 递归地对左右子树进行镜像操作
Mirror(pRoot->left);
Mirror(pRoot->right);
return pRoot; // 返回当前节点
}
13.6 BM34 判断是不是二叉搜索树
题目描述： 给定一个二叉树的根节点，判断它是不是一棵二叉搜索树。
考查点：
-
二叉搜索树（BST）的定义。
-
递归与范围限制。
思路：
-
BST的定义： 任何节点的左子树所有值都小于该节点，右子树所有值都大于该节点。更重要的是，对于任何节点，它的值必须在其祖先节点所定义的有效范围之内。
-
递归实现（带范围参数）：
-
定义一个递归辅助函数
bool doFunc(struct TreeNode *root, long minV, long maxV)。 -
基本情况： 如果
root为空，返回true。 -
检查当前节点： 如果
root->val小于minV或大于maxV，返回false。 -
递归检查左右子树：
-
递归检查左子树：
doFunc(root->left, minV, root->val)（左子树的值必须在minV到root->val之间） -
递归检查右子树：
doFunc(root->right, root->val, maxV)（右子树的值必须在root->val到maxV之间） -
只有当左右子树都满足条件时，才返回
true。
-
-
-
初始调用：
isValidBST(root)函数应该调用doFunc(root, LONG_MIN, LONG_MAX)，使用系统提供的最小值和最大值作为初始的无限范围。
示例代码（核心逻辑，已在文件 BM34是不是而搜索树.c 中给出，这里给出精简版）：
#include <limits.h> // For LONG_MIN, LONG_MAX
#include <stdbool.h> // For bool
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
// 递归辅助函数，检查节点值是否在指定范围内
bool doFunc(struct TreeNode *root, long minV, long maxV)
{
if(root == NULL) { // 空树是有效的BST
return true;
}
// 检查当前节点的值是否在有效范围内
if(root->val < minV || root->val > maxV) {
return false;
}
// 递归检查左子树和右子树
// 左子树的上限是当前根节点的值
// 右子树的下限是当前根节点的值
return doFunc(root->left, minV, root->val) && doFunc(root->right, root->val, maxV);
}
// 主函数入口
bool isValidBST(struct TreeNode *root)
{
// write code here
// 初始调用时，设定值的有效范围为整个long int的范围
return doFunc(root, LONG_MIN, LONG_MAX);
}
13.7 BM35 完全二叉树
题目描述： 判断给定的二叉树是否是完全二叉树。
考查点：
-
完全二叉树的定义。
-
层序遍历（BFS）的应用。
-
队列数据结构的使用。
思路：
-
完全二叉树定义：
-
除了最后一层，其他层的节点都是满的。
-
最后一层的节点都集中在左侧。
-
-
判断方法（使用层序遍历/BFS）：
-
使用队列进行层序遍历。
-
在遍历过程中，设置一个标志位
is_leaf_level，初始为false。 -
规则1： 如果遇到一个节点有右子节点而没有左子节点，则不是完全二叉树。
-
规则2： 如果遇到一个节点只有左子节点没有右子节点，或者没有子节点，则说明我们已经进入了树的“叶子层”（或即将进入）。此时，将
is_leaf_level设置为true。 -
规则3： 如果
is_leaf_level已经是true（意味着我们已进入叶子层），但之后又遇到了一个有子节点的节点（无论是左子还是右子），则不是完全二叉树。 -
所有节点遍历完后，如果一直满足上述规则，则是完全二叉树。
-
伪代码：
isCompleteTree(root):
if root is NULL: return true
queue = new Queue()
enqueue(root)
is_leaf_level = false
while queue is not empty:
current_node = dequeue()
// 规则3：如果已经进入叶子层，但当前节点还有子节点
if is_leaf_level and (current_node.left is not NULL or current_node.right is not NULL):
return false
// 规则1：右子节点存在但左子节点不存在
if current_node.right is not NULL and current_node.left is NULL:
return false
// 入队左子节点
if current_node.left is not NULL:
enqueue(current_node.left)
else: // 左子节点为空，进入叶子层状态
is_leaf_level = true
// 入队右子节点
if current_node.right is not NULL:
enqueue(current_node.right)
else: // 右子节点为空，进入叶子层状态（即使左子节点存在）
is_leaf_level = true
return true
示例代码（核心逻辑，基于队列的实现）：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
// 简单的队列实现 (与之前树遍历的队列类似，这里重新定义以保持独立性)
#define MAX_QUEUE_SIZE 1000
struct TreeNode* bfs_queue[MAX_QUEUE_SIZE];
int bfs_front = 0;
int bfs_rear = 0;
void bfs_enqueue(struct TreeNode* node) {
if (bfs_rear == MAX_QUEUE_SIZE) { // 队列满
// Error handling
return;
}
bfs_queue[bfs_rear++] = node;
}
struct TreeNode* bfs_dequeue() {
if (bfs_front == bfs_rear) { // 队列空
return NULL;
}
return bfs_queue[bfs_front++];
}
bool bfs_is_empty() {
return bfs_front == bfs_rear;
}
void bfs_reset_queue() {
bfs_front = 0;
bfs_rear = 0;
}
bool isCompleteTree(struct TreeNode* root) {
if (root == NULL) {
return true;
}
bfs_reset_queue(); // 重置队列状态
bfs_enqueue(root);
bool is_leaf_level = false; // 标记是否已经到达或进入了叶子层
while (!bfs_is_empty()) {
struct TreeNode* current = bfs_dequeue();
// 如果已经开始遇到空隙 (is_leaf_level为真)，但又遇到了非空子节点
if (is_leaf_level && (current->left != NULL || current->right != NULL)) {
return false;
}
// 检查左子节点
if (current->left != NULL) {
if (is_leaf_level) { // 如果在叶子层状态下，还遇到左子节点，则不是完全二叉树（因为前面应该都填满了）
return false;
}
bfs_enqueue(current->left);
} else {
// 左子节点为空，意味着从现在开始，后续节点都必须是叶子节点，或者只有右子节点的（但不应出现只有右没有左）
is_leaf_level = true;
}
// 检查右子节点
if (current->right != NULL) {
if (is_leaf_level) { // 如果已经进入叶子层状态，且当前节点还有右子节点（但左子节点已经为空），则不是完全二叉树
return false;
}
bfs_enqueue(current->right);
} else {
// 右子节点为空，从这里开始，后续节点都必须是叶子节点（如果左子节点也为空的话）
is_leaf_level = true;
}
}
return true;
}
13.8 BM36 判断是不是平衡二叉树
题目描述： 给定一个二叉树的根节点，判断它是不是平衡二叉树。
考查点：
-
平衡二叉树的定义。
-
递归计算树高度。
-
同时判断高度和平衡性。
思路：
-
平衡二叉树定义： 任意节点的左右子树高度差不超过1。
-
递归实现：
-
定义一个辅助函数
getHeightAndCheckBalance(node)，它返回以node为根的子树的高度。如果发现子树不平衡，则返回一个特殊值（如-1）。 -
getHeightAndCheckBalance(node)：-
如果
node为空，返回0（高度）。 -
递归调用
getHeightAndCheckBalance(node->left)得到left_height。 -
如果
left_height是-1，说明左子树不平衡，直接返回-1。 -
递归调用
getHeightAndCheckBalance(node->right)得到right_height。 -
如果
right_height是-1，说明右子树不平衡，直接返回-1。 -
如果
abs(left_height - right_height) > 1，说明当前节点不平衡，返回-1。 -
否则，返回
max(left_height, right_height) + 1。
-
-
-
主函数
IsBalanced_Solution(pRoot)调用辅助函数，如果返回不是-1，则是平衡的。
示例代码（核心逻辑，已在c_lang_tutorial_part1的“6.2 树”中给出）：
#include <stdbool.h> // For bool
#include <stdlib.h> // For abs (absolute value)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
// isBalancedHelper返回树高，如果发现不平衡则返回-1
int isBalancedHelper(struct TreeNode* node) {
if (node == NULL) {
return 0; // 空树高度为0
}
int left_height = isBalancedHelper(node->left);
if (left_height == -1) { // 左子树不平衡，则整个树不平衡
return -1;
}
int right_height = isBalancedHelper(node->right);
if (right_height == -1) { // 右子树不平衡，则整个树不平衡
return -1;
}
// 检查当前节点的左右子树高度差是否超过1
if (abs(left_height - right_height) > 1) {
return -1; // 不平衡
}
// 如果平衡，返回当前子树的高度
return (left_height > right_height ? left_height : right_height) + 1;
}
// 函数：检查是否是平衡二叉树的入口
bool IsBalanced_Solution(struct TreeNode* pRoot) {
// 调用辅助函数，如果返回值不是-1，则表示是平衡二叉树
return isBalancedHelper(pRoot) != -1;
}
13.9 BM37 最近公共祖先
题目描述： 给定一个二叉树（非二叉搜索树）和两个节点的值 p 和 q，找到这两个节点的最近公共祖先。
考查点：
-
二叉树的遍历和递归。
-
对节点存在性的判断和路径跟踪。
思路：
-
递归实现：
-
基本情况：
-
如果
root为空，返回NULL。 -
如果
root->val等于p或q，那么当前root就是一个潜在的最近公共祖先（或者就是p或q本身），返回root。
-
-
递归查找左右子树：
-
递归查找左子树：
left_lca = lowestCommonAncestor(root->left, p, q)。 -
递归查找右子树：
right_lca = lowestCommonAncestor(root->right, p, q)。
-
-
判断结果：
-
如果
left_lca和right_lca都不为空，说明p和q分别位于root的左右子树中，那么root就是它们的最近公共祖先，返回root。 -
如果
left_lca不为空，right_lca为空，说明p和q都在root的左子树中，返回left_lca。 -
如果
right_lca不为空，left_lca为空，说明p和q都在root的右子树中，返回right_lca。 -
如果
left_lca和right_lca都为空，说明p和q都不在以root为根的子树中，返回NULL。
-
-
示例代码（核心逻辑，已在文件 BM37最近公共祖先.c 中给出）：
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int lowestCommonAncestor(struct TreeNode *root, int p, int q)
{
// write code here
if (root == NULL || root->val == p || root->val == q) {
return root; // 如果根节点为空，或者找到了p或q，就返回根节点
}
// 递归查找左子树
struct TreeNode *left_lca = lowestCommonAncestor(root->left, p, q);
// 递归查找右子树
struct TreeNode *right_lca = lowestCommonAncestor(root->right, p, q);
// 如果左右子树都找到了结果（即p和q分别在左右子树），那么当前root就是LCA
if (left_lca != NULL && right_lca != NULL) {
return root;
}
// 如果只有左子树找到了结果，说明p和q都在左子树中，LCA在左子树中
else if (left_lca != NULL) {
return left_lca;
}
// 如果只有右子树找到了结果，说明p和q都在右子树中，LCA在右子树中
else {
return right_lca;
}
}
十四、大厂C语言面试高频问题与解题策略
大厂C语言面试通常不仅仅考察语法和算法，更注重你对底层原理的理解、解决实际问题的能力以及良好的编程习惯。
14.1 高频问题类型与应对策略
-
指针和内存管理：
-
问题： 空指针、野指针、内存泄漏、段错误、
malloc/free的实现和原理、动态内存分配的安全性。 -
策略： 结合代码示例，清晰解释概念和危害。强调内存管理规范（如配对使用
malloc和free，释放后置NULL）。对于malloc原理，可提及内核的brk/mmap系统调用和jemalloc/tcmalloc等用户态内存分配器。
-
-
数据结构与算法：
-
问题： 链表、树、图、哈希表的实现和应用；各种排序和查找算法的原理、复杂度、稳定性。
-
策略： 能够手写核心代码，分析时间/空间复杂度。对于复杂算法，理解其核心思想和适用场景。多做LeetCode/牛客刷题，并注意代码规范和边界条件。
-
-
预处理器和宏：
-
问题： 宏的副作用、
#define与const/enum的区别、条件编译的应用。 -
策略： 解释宏的文本替换原理，指出其优缺点和安全隐患。强调
const/enum在类型安全方面的优势。
-
-
C语言特性与陷阱：
-
问题：
static关键字的作用（局部、全局、函数）、const的用法（修饰变量、指针、函数参数）、volatile关键字、类型转换（隐式/显式）、函数传值与传址。 -
策略： 清晰区分概念。对于陷阱，如数组名作为函数参数的退化、
gets安全性等，能解释原因和提供替代方案。
-
-
系统编程基础（通常在高级岗位）：
-
问题： 多进程/多线程（
fork,pthread）、进程间通信（IPC，如管道、共享内存、消息队列）、网络编程（socket）。 -
策略： 了解基本概念和API。对于并发问题，理解互斥锁、信号量、死锁等概念。
-
14.2 提升C语言面试表现的通用技巧
-
代码规范： 保持代码风格一致（缩进、命名、注释）。良好的代码风格是专业性的体现。
-
边界条件和错误处理： 在编写代码时，始终考虑输入为空、数组为空、循环零次等边界条件。对可能失败的函数调用（如
malloc,fopen）进行错误检查。 -
时间与空间复杂度分析： 每次完成算法题后，都习惯性地分析其时间复杂度和空间复杂度。
-
提问与沟通： 面试中遇到不清楚的地方，积极向面试官提问以明确需求。在解题时，可以与面试官沟通思路，展示解决问题的过程。
-
内存思维： C语言的核心是内存。在遇到任何问题时，尝试从内存布局、指针操作的角度去思考。
-
善用工具： 熟悉使用GCC编译，GDB调试。
-
刷题： 牛客网、LeetCode上的C语言题目是检验和提升你能力的最好途径。对于必刷榜的题目，务必手写多次，直到熟练。
总结与展望
恭喜你完成了C语言完整教程的第二部分！至此，我们已经全面覆盖了C语言的核心语法、内存管理、高级指针应用、基本及高级数据结构、经典排序与查找算法，并探讨了文件I/O、错误处理以及面试中常见的问题类型和应对策略。
C语言是一门强大而基础的编程语言，它将带你深入计算机的底层，为你未来学习操作系统、网络、嵌入式开发、高性能计算等领域打下坚实的基础。掌握了C语言：
-
编写高效的程序： 精确控制内存，优化性能瓶颈。
-
理解底层机制： 深入了解数据如何在内存中存储和操作。
-
构建复杂系统： 利用C语言的灵活性实现各种系统级组件。
-
应对大厂面试： 扎实的C语言功底将是你通过技术面试的有力保障。
后续建议：
-
持续刷题： 针对牛客网“面试必刷101”以及LeetCode上的C语言题目，反复练习，特别是链表、树、排序、查找等数据结构和算法题。
-
深入源码： 尝试阅读一些开源C语言项目的源码，例如Linux内核、Redis等，学习大型项目的结构和内存管理技巧。
-
实践项目： 尝试用C语言实现一些小项目，如文件管理器、简易Shell、网络聊天程序等，将理论知识应用于实践。
-
学习C++： 如果目标是后端开发、游戏开发等领域，C++是C语言的超集，学习C++将帮助你更好地利用面向对象、模板编程等高级特性。
希望这份教程能成为你C语言学习和面试准备路上的灯塔。祝你学习顺利，在未来的技术道路上大放异彩！
欢迎加入我们的广州开发者社区，与优秀的开发者共同成长！
更多推荐
3
0- 0
已为社区贡献2条内容
所有评论(0)