一、栈Stack栈是一种特殊的线性数据结构它就像我们平时叠盘子一样只能从最上面放盘子入栈或取盘子出栈。栈的特点只能从一端进行插入和删除操作这一端叫做栈顶另一端叫做栈底插入数据叫做入栈或压栈删除数据叫做出栈或弹栈栈的核心特性先进后出FILO就像叠盘子一样最先放进去的盘子会被压在最下面最后才能取出来。栈的实际应用解决回溯问题比如走迷宫时记录路径软件的撤销功能CtrlZ浏览器的前进后退功能判断回文字符串检查代码中的括号是否匹配顺序栈用数组实现的栈根据栈顶指针的移动方向分为满栈栈顶指针指向最后一个有效元素空栈栈顶指针指向第一个空位置增栈入栈时栈顶向内存高地址移动减栈入栈时栈顶向内存低地址移动链式栈用链表实现的栈更加灵活不需要预先分配固定大小的空间。栈的基本操作API创建栈入栈push出栈pop判断栈是否为空获取栈顶元素peek清空栈销毁栈二、二叉树一对多结构树就像现实中的家族树由一个根节点和若干个子节点组成每个节点可以有多个子节点。空树一个节点都没有的树。树的常用术语根节点最顶层的节点没有父节点叶子节点没有子节点的节点就像树的叶子分支节点有子节点的节点度一个节点拥有的子节点个数树的深度树有多少层树的度树中所有节点最大的度二叉树每个节点最多只能有两个子节点左孩子和右孩子而且左右孩子不能随意交换位置。满二叉树在不增加层数的前提下无法再增加任何一个节点的二叉树。每一层都填满了节点。完全二叉树在满二叉树的基础上按照从左到右、从上到下的顺序添加节点或者从下到上、从右到左的顺序删除节点得到的树。满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树。K层满二叉树的计算第K层的节点个数2^(K-1)K层总共节点个数2^K - 1二叉树的遍历深度优先遍历像走迷宫一样深入到底再返回前序遍历根节点 → 左子树 → 右子树ABFGCDHIE中序遍历左子树 → 根节点 → 右子树FBCGAHIDE后序遍历左子树 → 右子树 → 根节点FCGBIHEDA广度优先遍历像水波纹一样一层层扩散层序遍历从上到下、从左到右逐层遍历ABDFGHECI重要特性已知前序遍历和中序遍历结果可以唯一还原一棵二叉树已知后序遍历和中序遍历结果也可以唯一还原一棵二叉树三、哈希表Hash Table哈希表是一种非常高效的数据结构它就像一个大仓库每个物品都有自己专属的储物柜编号。核心思想通过一个哈希函数把数据的关键字比如名字、学号转换成一个数字这个数字就是数据在表中的存储位置。哈希表的优点查找速度快理想情况下查找数据的时间复杂度是O(1)也就是一次就能找到插入和删除也很快同样接近O(1)的时间复杂度哈希表的关键概念哈希函数把任意长度的输入转换成固定长度的输出哈希值哈希冲突不同的数据经过哈希函数计算后得到了相同的哈希值解决冲突的方法链地址法每个位置放一个链表冲突的数据都放在同一个链表中开放地址法冲突时找下一个空位置存放线性探测依次往后找空位二次探测按平方数跳跃查找双重哈希用第二个哈希函数计算步长哈希表的应用场景数据库索引缓存系统如Redis字典、集合的实现文件校验MD5、SHA等哈希算法密码存储存储密码的哈希值而非明文简单示例// C语言哈希表示例 - 使用链地址法解决冲突 #include stdio.h #include stdlib.h #include string.h #define TABLE_SIZE 10 // 哈希表节点结构 typedef struct HashNode { char key[20]; int value; struct HashNode* next; } HashNode; // 哈希表结构 typedef struct { HashNode* buckets[TABLE_SIZE]; } HashTable; // 哈希函数简单取模法 int hashFunction(const char* key) { int sum 0; for (int i 0; key[i] ! \0; i) { sum key[i]; } return sum % TABLE_SIZE; } // 创建哈希表 HashTable* createHashTable() { HashTable* table (HashTable*)malloc(sizeof(HashTable)); for (int i 0; i TABLE_SIZE; i) { table-buckets[i] NULL; } return table; } // 插入键值对 void insert(HashTable* table, const char* key, int value) { int index hashFunction(key); HashNode* newNode (HashNode*)malloc(sizeof(HashNode)); strcpy(newNode-key, key); newNode-value value; newNode-next table-buckets[index]; table-buckets[index] newNode; printf(插入: %s %d (哈希值: %d)\n, key, value, index); } // 查找键对应的值 int search(HashTable* table, const char* key) { int index hashFunction(key); HashNode* current table-buckets[index]; while (current ! NULL) { if (strcmp(current-key, key) 0) { return current-value; } current current-next; } return -1; // 未找到 } // 删除键值对 void delete(HashTable* table, const char* key) { int index hashFunction(key); HashNode* current table-buckets[index]; HashNode* prev NULL; while (current ! NULL) { if (strcmp(current-key, key) 0) { if (prev NULL) { table-buckets[index] current-next; } else { prev-next current-next; } free(current); printf(删除: %s\n, key); return; } prev current; current current-next; } printf(未找到要删除的键: %s\n, key); } // 打印哈希表 void printHashTable(HashTable* table) { printf(\n哈希表内容:\n); for (int i 0; i TABLE_SIZE; i) { printf(桶[%d]: , i); HashNode* current table-buckets[i]; while (current ! NULL) { printf(%s:%d - , current-key, current-value); current current-next; } printf(NULL\n); } } // 主函数演示 int main() { // 创建哈希表 HashTable* studentScores createHashTable(); // 插入学生成绩 insert(studentScores, 张三, 85); insert(studentScores, 李四, 92); insert(studentScores, 王五, 78); // 查找成绩 - 非常快 printf(\n查找成绩:\n); int score search(studentScores, 李四); if (score ! -1) { printf(李四的成绩是: %d\n, score); // 输出: 92 } // 添加新学生 insert(studentScores, 赵六, 88); // 删除学生 delete(studentScores, 王五); // 打印哈希表结构 printHashTable(studentScores); // 清理内存实际应用中需要更完整的释放 free(studentScores); return 0; }四、算法基础程序设计 数据结构 算法算法就是解决问题的具体步骤和方法就像做菜的食谱一样。好的算法应该具备正确性语法要正确合法的输入能得到合理的结果对非法输入要有处理机制经过各种测试都能正常运行可读性代码要容易看懂、容易交流健壮性输入非法数据时能妥善处理不会崩溃高效率执行时间要短时间复杂度低低存储占用内存要少空间复杂度低空间复杂度算法执行过程中额外开辟的空间随数据量n的变化关系。O(1)常数空间不随数据量变化O(n)线性空间随数据量线性增长时间复杂度算法执行所需时间的度量描述随着数据量n增加执行时间如何增长。一般用大O表示法比如O(n)表示时间复杂度与数据量n成正比。时间复杂度计算规则用常数1取代运行时间中的所有加法常数只保留最高阶项如果最高阶存在且系数不是1则去除系数常见时间复杂度示例// O(1) - 常数时间复杂度 void swap(int a, int b) { int tmp a; // 执行1次 a b; // 执行1次 b tmp; // 执行1次 // 总共执行3次与n无关 }// O(n) - 线性时间复杂度 for(int i 0; i n; i 2) { // 循环n/2次 int tmp a; a b; b tmp; // 总共执行约n次操作 }// O(log n) - 对数时间复杂度 for(int i 1; i n; i * 2) { // 每次i翻倍 // 循环次数log₂n // 比如n8时i1,2,4,8循环3次 }// O(n log n) - 线性对数时间复杂度 for(int i 0; i n; i) { // 外层循环n次 for(int j 0; j n; j * 2) { // 内层循环log n次 // 总共执行n * log n次 } }// O(n²) - 平方时间复杂度 for(int i 0; i n; i) { // 外层循环n次 for(int j i; j n; j) { // 内层循环(n-i)次 int tmp a; a b; b tmp; // 总共执行约n²/2次 } }时间复杂度比较从快到慢O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!) O(nⁿ)简单理解O(1)无论数据多少执行时间都一样O(log n)数据翻倍时间只增加一点点O(n)数据翻倍时间也翻倍O(n²)数据翻倍时间变成4倍O(2ⁿ)数据稍微增加时间就爆炸式增长常用排序和查找算法下面介绍几种常见的排序和查找算法用通俗易懂的方式解释它们的思想并提供代码示例。1. 选择排序思想就像在一堆牌中找最小的牌找到后放到最前面然后从剩下的牌中继续找最小的依次类推。时间复杂度O(n²)空间复杂度O(1)稳定性不稳定// 选择排序示例 void selection_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int min_index i; // 在未排序部分找到最小元素 for (int j i 1; j n; j) { if (arr[j] arr[min_index]) { min_index j; } } // 将最小元素交换到已排序部分的末尾 int temp arr[i]; arr[i] arr[min_index]; arr[min_index] temp; } }2. 冒泡排序思想就像水中的气泡往上冒相邻元素两两比较如果顺序不对就交换这样每一轮都会把最大的元素冒到最后面。时间复杂度O(n²)空间复杂度O(1)稳定性稳定// 冒泡排序示例 void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { // 优化如果某轮没有发生交换说明已经有序 int swapped 0; for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { // 交换相邻元素 int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; } } if (!swapped) break; // 提前结束 } }3. 插入排序思想就像打扑克牌时整理手牌每次拿到一张新牌就把它插入到已经排好序的牌中的正确位置。时间复杂度O(n²)空间复杂度O(1)稳定性稳定// 插入排序示例 void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; // 当前要插入的元素 int j i - 1; // 将比key大的元素向后移动 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; // 插入到正确位置 } }4. 希尔排序思想插入排序的改进版。先将整个序列分成若干个子序列对每个子序列进行插入排序然后逐渐缩小子序列的间隔最后对整个序列进行一次插入排序。时间复杂度O(n log n) ~ O(n²)空间复杂度O(1)稳定性不稳定// 希尔排序示例 void shell_sort(int arr[], int n) { // 使用希尔增量序列 for (int gap n / 2; gap 0; gap / 2) { // 对每个子序列进行插入排序 for (int i gap; i n; i) { int temp arr[i]; int j; // 插入排序逻辑 for (j i; j gap arr[j - gap] temp; j - gap) { arr[j] arr[j - gap]; } arr[j] temp; } } }5. 快速排序思想采用分治策略。选择一个基准元素将序列分成两部分比基准小的放在左边比基准大的放在右边。然后对左右两部分递归地进行快速排序。时间复杂度平均O(n log n)最坏O(n²)空间复杂度O(log n)递归栈空间稳定性不稳定// 快速排序示例 void quick_sort(int arr[], int low, int high) { if (low high) { // 分区操作返回基准元素的正确位置 int pivot_index partition(arr, low, high); // 递归排序左右两部分 quick_sort(arr, low, pivot_index - 1); quick_sort(arr, pivot_index 1, high); } } // 分区函数 int partition(int arr[], int low, int high) { int pivot arr[high]; // 选择最后一个元素作为基准 int i low - 1; // 小于基准的元素的边界 for (int j low; j high; j) { if (arr[j] pivot) { i; // 交换arr[i]和arr[j] int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } // 将基准元素放到正确位置 int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1; }查找算法二分查找前提条件序列必须是有序的思想就像查字典每次都从中间翻开根据中间值与目标值的大小关系决定在前半部分还是后半部分继续查找这样每次都能排除一半的数据。时间复杂度O(log n)空间复杂度O(1)迭代版本// 二分查找示例迭代版本 int binary_search(int arr[], int n, int target) { int left 0; int right n - 1; while (left right) { int mid left (right - left) / 2; // 防止溢出 if (arr[mid] target) { return mid; // 找到目标返回索引 } else if (arr[mid] target) { left mid 1; // 目标在右半部分 } else { right mid - 1; // 目标在左半部分 } } return -1; // 未找到 } // 二分查找示例递归版本 int binary_search_recursive(int arr[], int left, int right, int target) { if (left right) { return -1; // 未找到 } int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { return binary_search_recursive(arr, mid 1, right, target); } else { return binary_search_recursive(arr, left, mid - 1, target); } }算法性能对比下面是各种排序算法的性能对比算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景选择排序O(n²)O(n²)O(1)不稳定数据量小对稳定性无要求冒泡排序O(n²)O(n²)O(1)稳定教学演示数据基本有序插入排序O(n²)O(n²)O(1)稳定数据量小或基本有序希尔排序O(n log n) ~ O(n²)O(n²)O(1)不稳定中等规模数据快速排序O(n log n)O(n²)O(log n)不稳定大规模数据通用场景二分查找O(log n)O(log n)O(1)-有序数组查找简单总结选择排序简单但效率低适合教学冒泡排序最容易理解但实际很少用插入排序对小规模或基本有序数据很高效希尔排序插入排序的改进适合中等规模数据快速排序最常用的排序算法平均性能最好二分查找查找有序数据的利器效率极高在实际开发中C语言标准库提供了qsort()函数快速排序实现和bsearch()函数二分查找实现可以直接使用。