一、数组知识小结回顾在进入进阶内容之前先回顾数组的核心知识点1.1 为什么需要数组当需要处理大量同类型数据时如统计全班成绩逐个定义变量不现实数组提供了一种批量管理变量的方式。1.2 数组定义数据类型 数组名[数组长度]; int a[10]; // 定义了一个包含 10 个 int 型元素的数组1.3 数组的三大特点特点说明连续性数组元素在内存中占用一片连续的空间单一性数组中存放的是同一类型的数据有序性元素按下标顺序排列第一个后面就是第二个1.4 数组元素的引用通过下标访问数组中的具体元素a[0] 1; // 下标从 0 开始 a[1] 2;1.5 给值方式// 全部初始化 int a[10] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 部分初始化——前面的元素依次赋值后面默认为 0 int a[10] {1, 2, 3, 4, 5}; // 不初始化——数组中是随机值垃圾值 int a[10]; // 初始化成全 0 int a[10] {0}; int a[10] {}; // 初始化器默认给 0 // 初始化时省略长度由初始化值个数推算 int a[] {1, 2, 3, 4}; // 数组长度为 4注意数组不能整体赋值int a[10]; a {1, 2, 3, 4, 5}; // ❌ 错误必须逐个元素赋值 a[0] 2; // ✅ 正确二、排序算法2.1 选择排序核心思想给合适的位置选择合适的数。算法步骤外层循环控制位置内层循环从剩余元素中找到合适最小或最大的数放到当前位置。代码实现升序int i, j; for (i 0; i n - 1; i) // 外层控制位置 { for (j i 1; j n; j) // 内层从 i1 开始找数 { if (a[j] a[i]) // 如果找到更小的 { int t a[i]; // 交换 a[i] a[j]; a[j] t; } } }时间复杂度分析i 0 时内层循环 n-1 次 i 1 时内层循环 n-2 次 i 2 时内层循环 n-3 次 ... i n-2 时内层循环 1 次 总计1 2 3 ... (n-1) n(n-1)/2 n²/2 - n/2时间复杂度O(n²)用最高次项来反映增长趋势2.2 冒泡排序核心思想相邻两个元素两两比较小的往前放大的往后放像气泡一样浮到末尾。代码实现升序int i, j; for (i 1; i n; i) // 外层控制趟数 { for (j 0; j n - i; j) // 内层相邻比较 { if (a[j] a[j 1]) // 前面比后面大就交换 { int t a[j]; a[j] a[j 1]; a[j 1] t; } } }时间复杂度O(n²)2.3 插入排序核心思想将数据插入到已有的有序序列中通过和已排序的序列进行比较找到合适的位置插入。场景理解想象打扑克牌时每摸一张新牌就把它插入到手中已排好序的牌的正确位置。代码实现升序int i, j; for (i 1; i n; i) { int t a[i]; // 取出当前要插入的元素 j i; while (j 0 t a[j - 1]) // 在已排序序列中从后往前找位置 { a[j] a[j - 1]; // 比 t 大的元素往后挪 --j; } a[j] t; // 插入到正确位置 }时间复杂度分析i 1 时最多比较 1 次 i 2 时最多比较 2 次 i 3 时最多比较 3 次 ... i n-1 时最多比较 n-1 次时间复杂度O(n²)2.4 三种排序对比排序算法时间复杂度核心思想选择排序O(n²)给合适的位置选择合适的数冒泡排序O(n²)相邻元素两两比较大的往后冒泡插入排序O(n²)将元素插入到已排序序列的正确位置三、查找算法二分查找3.1 前提条件数据必须是有序的排好序的数组。3.2 核心思想每次找到中间位置将中间位置的值和要找的值比较中间值目标值 → 目标在左半部分中间值目标值 → 目标在右半部分中间值目标值 → 找到了3.3 过程图示以在有序数组中查找值1为例数组1 2 3 4 5 6 7 8 9 10 第 1 次中间值 55 1往左找 第 2 次中间值 22 1往左找 第 3 次中间值 11 1找到3.4 代码实现int begin 0, end n - 1, mid; int target; // 要查找的目标值 int found -1; // -1 表示未找到 while (begin end) { mid (begin end) / 2; // 中间位置 if (a[mid] target) { end mid - 1; // 目标在左半部分 } else if (a[mid] target) { begin mid 1; // 目标在右半部分 } else { found mid; // 找到了记录位置 break; } } if (begin end) { // 找到了 printf(找到了位置是 %d\n, found); } else { // 没找到 printf(没找到\n); }3.5 时间复杂度情况时间复杂度最好O(1)一次就找到最差O(logN)每次排除一半四、一维字符型数组与字符串4.1 字符数组的定义char s[10]; // 10 个 char 元素的数组大小 10 字节字符型数组和 int 型数组本质上没有太大区别主要是用来处理字符数据。4.2 字符串的存储方式C 语言中用双引号表示字符串常量hello字符串在内存中按字符数组方式存储char s[10] hello;下标0123456789值hello\0字符串结束标志\0。字符串的长度是\0前面有效字符的个数。4.3 字符数组的初始化// 用字符串常量初始化 char s[10] hello; // 用字符列表初始化部分初始化后面补 0 char s[10] {h, e, l, l, o}; // 等价于 h,e,l,l,o,\0,0,0,0,0 // 省略长度由初始化值推算自动包含 \0 char s[] hello; // 数组长度为 65个字符 1个\04.4 字符串与数组的关系字符数组是存放字符串的容器。处理字符串时更关心字符串什么时候结束\0而不是数组什么时候结束。因此数组长度显得不那么重要\0才是关键。4.5 获取字符串长度strlen#include string.h size_t strlen(const char *s);功能计算字符串长度\0前面有效字符的个数。注意strlen和sizeof不同——strlen不算\0sizeof算整个数组大小。char s[10] hello; strlen(s); // 返回 5h,e,l,l,o不算 \0 sizeof(s); // 返回 10整个数组的大小4.6 字符串复制strcpy#include string.h char *strcpy(char *dest, const char *src);功能将src中的字符串复制到dest中。参数src— 字符串源数组名或字符串常量。dest— 目标数组名或存放字符串的空间地址。返回值返回dest。char s1[10] hello; char s2[10] world; strcpy(s1, s2); // s1 变为 world4.7 字符串拼接strcat#include string.h char *strcat(char *dest, const char *src);功能将src中的字符串拼接到dest末尾。参数src— 字符串源数组名或字符串常量。dest— 目标数组名或存放字符串的空间地址。返回值返回dest。char s1[20] hello; char s2[10] world; strcat(s1, s2); // s1 变为 helloworld拼接思路1.定位到\0的位置。2.从\0位置开始依次复制src中的字符。3.最后补上\0。五、总结知识点核心要点选择排序给位置选数时间复杂度 O(n²)冒泡排序相邻两两比较大的往后冒时间复杂度 O(n²)插入排序将元素插入已排序序列的正确位置时间复杂度 O(n²)二分查找前提数据有序每次排除一半最好 O(1)最差 O(logN)字符数组用来存储字符串以\0作为结束标志strlen计算字符串长度不含\0strcpy字符串复制strcat字符串拼接
C语言基础篇（7）：数组进阶——排序、查找与字符数组
一、数组知识小结回顾在进入进阶内容之前先回顾数组的核心知识点1.1 为什么需要数组当需要处理大量同类型数据时如统计全班成绩逐个定义变量不现实数组提供了一种批量管理变量的方式。1.2 数组定义数据类型 数组名[数组长度]; int a[10]; // 定义了一个包含 10 个 int 型元素的数组1.3 数组的三大特点特点说明连续性数组元素在内存中占用一片连续的空间单一性数组中存放的是同一类型的数据有序性元素按下标顺序排列第一个后面就是第二个1.4 数组元素的引用通过下标访问数组中的具体元素a[0] 1; // 下标从 0 开始 a[1] 2;1.5 给值方式// 全部初始化 int a[10] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 部分初始化——前面的元素依次赋值后面默认为 0 int a[10] {1, 2, 3, 4, 5}; // 不初始化——数组中是随机值垃圾值 int a[10]; // 初始化成全 0 int a[10] {0}; int a[10] {}; // 初始化器默认给 0 // 初始化时省略长度由初始化值个数推算 int a[] {1, 2, 3, 4}; // 数组长度为 4注意数组不能整体赋值int a[10]; a {1, 2, 3, 4, 5}; // ❌ 错误必须逐个元素赋值 a[0] 2; // ✅ 正确二、排序算法2.1 选择排序核心思想给合适的位置选择合适的数。算法步骤外层循环控制位置内层循环从剩余元素中找到合适最小或最大的数放到当前位置。代码实现升序int i, j; for (i 0; i n - 1; i) // 外层控制位置 { for (j i 1; j n; j) // 内层从 i1 开始找数 { if (a[j] a[i]) // 如果找到更小的 { int t a[i]; // 交换 a[i] a[j]; a[j] t; } } }时间复杂度分析i 0 时内层循环 n-1 次 i 1 时内层循环 n-2 次 i 2 时内层循环 n-3 次 ... i n-2 时内层循环 1 次 总计1 2 3 ... (n-1) n(n-1)/2 n²/2 - n/2时间复杂度O(n²)用最高次项来反映增长趋势2.2 冒泡排序核心思想相邻两个元素两两比较小的往前放大的往后放像气泡一样浮到末尾。代码实现升序int i, j; for (i 1; i n; i) // 外层控制趟数 { for (j 0; j n - i; j) // 内层相邻比较 { if (a[j] a[j 1]) // 前面比后面大就交换 { int t a[j]; a[j] a[j 1]; a[j 1] t; } } }时间复杂度O(n²)2.3 插入排序核心思想将数据插入到已有的有序序列中通过和已排序的序列进行比较找到合适的位置插入。场景理解想象打扑克牌时每摸一张新牌就把它插入到手中已排好序的牌的正确位置。代码实现升序int i, j; for (i 1; i n; i) { int t a[i]; // 取出当前要插入的元素 j i; while (j 0 t a[j - 1]) // 在已排序序列中从后往前找位置 { a[j] a[j - 1]; // 比 t 大的元素往后挪 --j; } a[j] t; // 插入到正确位置 }时间复杂度分析i 1 时最多比较 1 次 i 2 时最多比较 2 次 i 3 时最多比较 3 次 ... i n-1 时最多比较 n-1 次时间复杂度O(n²)2.4 三种排序对比排序算法时间复杂度核心思想选择排序O(n²)给合适的位置选择合适的数冒泡排序O(n²)相邻元素两两比较大的往后冒泡插入排序O(n²)将元素插入到已排序序列的正确位置三、查找算法二分查找3.1 前提条件数据必须是有序的排好序的数组。3.2 核心思想每次找到中间位置将中间位置的值和要找的值比较中间值目标值 → 目标在左半部分中间值目标值 → 目标在右半部分中间值目标值 → 找到了3.3 过程图示以在有序数组中查找值1为例数组1 2 3 4 5 6 7 8 9 10 第 1 次中间值 55 1往左找 第 2 次中间值 22 1往左找 第 3 次中间值 11 1找到3.4 代码实现int begin 0, end n - 1, mid; int target; // 要查找的目标值 int found -1; // -1 表示未找到 while (begin end) { mid (begin end) / 2; // 中间位置 if (a[mid] target) { end mid - 1; // 目标在左半部分 } else if (a[mid] target) { begin mid 1; // 目标在右半部分 } else { found mid; // 找到了记录位置 break; } } if (begin end) { // 找到了 printf(找到了位置是 %d\n, found); } else { // 没找到 printf(没找到\n); }3.5 时间复杂度情况时间复杂度最好O(1)一次就找到最差O(logN)每次排除一半四、一维字符型数组与字符串4.1 字符数组的定义char s[10]; // 10 个 char 元素的数组大小 10 字节字符型数组和 int 型数组本质上没有太大区别主要是用来处理字符数据。4.2 字符串的存储方式C 语言中用双引号表示字符串常量hello字符串在内存中按字符数组方式存储char s[10] hello;下标0123456789值hello\0字符串结束标志\0。字符串的长度是\0前面有效字符的个数。4.3 字符数组的初始化// 用字符串常量初始化 char s[10] hello; // 用字符列表初始化部分初始化后面补 0 char s[10] {h, e, l, l, o}; // 等价于 h,e,l,l,o,\0,0,0,0,0 // 省略长度由初始化值推算自动包含 \0 char s[] hello; // 数组长度为 65个字符 1个\04.4 字符串与数组的关系字符数组是存放字符串的容器。处理字符串时更关心字符串什么时候结束\0而不是数组什么时候结束。因此数组长度显得不那么重要\0才是关键。4.5 获取字符串长度strlen#include string.h size_t strlen(const char *s);功能计算字符串长度\0前面有效字符的个数。注意strlen和sizeof不同——strlen不算\0sizeof算整个数组大小。char s[10] hello; strlen(s); // 返回 5h,e,l,l,o不算 \0 sizeof(s); // 返回 10整个数组的大小4.6 字符串复制strcpy#include string.h char *strcpy(char *dest, const char *src);功能将src中的字符串复制到dest中。参数src— 字符串源数组名或字符串常量。dest— 目标数组名或存放字符串的空间地址。返回值返回dest。char s1[10] hello; char s2[10] world; strcpy(s1, s2); // s1 变为 world4.7 字符串拼接strcat#include string.h char *strcat(char *dest, const char *src);功能将src中的字符串拼接到dest末尾。参数src— 字符串源数组名或字符串常量。dest— 目标数组名或存放字符串的空间地址。返回值返回dest。char s1[20] hello; char s2[10] world; strcat(s1, s2); // s1 变为 helloworld拼接思路1.定位到\0的位置。2.从\0位置开始依次复制src中的字符。3.最后补上\0。五、总结知识点核心要点选择排序给位置选数时间复杂度 O(n²)冒泡排序相邻两两比较大的往后冒时间复杂度 O(n²)插入排序将元素插入已排序序列的正确位置时间复杂度 O(n²)二分查找前提数据有序每次排除一半最好 O(1)最差 O(logN)字符数组用来存储字符串以\0作为结束标志strlen计算字符串长度不含\0strcpy字符串复制strcat字符串拼接
