当前位置： 首页 > news >正文

嵌入式Linux学习笔记 | 数据结构（Day02）顺序表核心功能实现 + 快速排序 + 折半查找 + 作业实战

news 2026/4/27 4:52:18

点赞+关注私信领取全部代码资料~

顺序表是数据结构中最基础的线性表存储结构，本质是用一段连续的物理地址存储数据元素，支持随机访问，是学习数据结构的入门核心。本文将完整实现顺序表的查找、修改、排序核心功能，详解快速排序、折半查找经典算法，并配套实战作业，代码可直接编译运行，适合学习和面试备考。

一、前置准备：顺序表结构体定义

为了让顺序表支持任意数据类型（int、char、自定义结构体等），采用泛型设计，核心包含：数据指针、元素大小、有效长度、最大容量。

#include <stdio.h> #include <stdlib.h> #include <string.h> // 函数指针类型：比较函数，适配任意数据类型 // 返回值：>0 前者大，=0 相等，<0 后者大 typedef int (*cmp_t)(const void *, const void *); // 顺序表结构体（泛型） typedef struct { void *data; // 存储数据的基地址（无类型指针，适配任意数据） int elem_size; // 单个元素的大小（字节） int length; // 当前有效元素个数 int capacity; // 最大容量 } seqlist_t;

通用工具函数

  1. 顺序表初始化
// 初始化顺序表：容量capacity，单个元素大小elem_size seqlist_t *seqlist_create(int capacity, int elem_size) { seqlist_t *s = (seqlist_t *)malloc(sizeof(seqlist_t)); s->data = malloc(elem_size * capacity); s->elem_size = elem_size; s->length = 0; s->capacity = capacity; return s; }
  1. 顺序表插入（尾部插入，辅助测试）
// 尾部插入元素 int seqlist_push_back(seqlist_t *s, const void *val) { if (s->length >= s->capacity) return -1; // 满了返回失败 // 计算插入位置：基地址 + 偏移量 char *pos = (char *)s->data + s->length * s->elem_size; memcpy(pos, val, s->elem_size); s->length++; return 0; }
  1. 顺序表遍历（辅助测试，以 int 类型为例）
// 遍历int类型顺序表 void seqlist_print_int(seqlist_t *s) { for (int i = 0; i < s->length; i++) { int *val = (int *)((char *)s->data + i * s->elem_size); printf("%d ", *val); } printf("\n"); }

二、顺序表核心功能补充实现

a. 查找功能

函数原型：void *seqlist_search(const seqlist_t *s, const void *key, cmp_t cmp);顺序表查找采用线性遍历思想，遍历顺序表中所有有效元素，借助自定义比较函数匹配目标关键字，若找到匹配元素则返回该元素内存地址，未找到则返回空值。该方法通用性极强，依托泛型设计，能够适配整数、字符串、自定义结构体等多种数据类型，是无序顺序表中最常用的查找方式。

/** * @brief 顺序表查找 * @param s 顺序表指针 * @param key 查找关键字 * @param cmp 比较函数指针 * @return 找到返回元素地址，未找到返回NULL */ void *seqlist_search(const seqlist_t *s, const void *key, cmp_t cmp) { // 遍历所有有效元素 for (int i = 0; i < s->length; i++) { // 计算当前元素地址 char *elem = (char *)s->data + i * s->elem_size; // 比较相等，返回地址 if (cmp(elem, key) == 0) { return elem; } } // 未找到 return NULL; }

b. 修改功能

功能描述：先根据关键字查找元素，找到后用new_data替换原数据，返回 0 成功，-1 失败。函数原型：int seqlist_modify(seqlist_t *s, const void *key, cmp_t cmp, const void *new_data);

注：原命名和查找函数冲突，修改为seqlist_modify，更符合语义。

/** * @brief 顺序表修改元素 * @param s 顺序表指针 * @param key 查找关键字 * @param cmp 比较函数指针 * @param new_data 新数据 * @return 0成功，-1未找到/失败 */ int seqlist_modify(seqlist_t *s, const void *key, cmp_t cmp, const void *new_data) { // 1. 查找元素 void *elem = seqlist_search(s, key, cmp); if (elem == NULL) return -1; // 未找到 // 2. 替换为新数据 memcpy(elem, new_data, s->elem_size); return 0; }

c. 插入排序

功能描述：对顺序表进行插入排序，支持任意数据类型，通过比较函数指定排序规则。函数原型：void seqlist_insert_sort(seqlist_t *s, cmp_t cmp);

/** * @brief 顺序表插入排序 * @param s 顺序表指针 * @param cmp 比较函数指针（决定升序/降序） */ void seqlist_insert_sort(seqlist_t *s, cmp_t cmp) { int i, j; // 临时变量：存储待插入元素 char *temp = (char *)malloc(s->elem_size); // 从第二个元素开始遍历 for (i = 1; i < s->length; i++) { // 待插入元素存入temp memcpy(temp, (char *)s->data + i * s->elem_size, s->elem_size); // 向前遍历，找到插入位置 for (j = i - 1; j >= 0; j--) { char *curr = (char *)s->data + j * s->elem_size; // 若当前元素 > temp（升序），后移 if (cmp(curr, temp) > 0) { memcpy(curr + s->elem_size, curr, s->elem_size); } else { break; } } // 插入temp到正确位置 memcpy((char *)s->data + (j + 1) * s->elem_size, temp, s->elem_size); } free(temp); }

三、快速排序（核心算法）

核心思想

  1. 选择基准元素（通常选第一个 / 最后一个 / 中间元素）；
  2. 一趟排序完成两件事：
    • 确定基准元素的最终位置；
    • 分区：基准左侧元素 ≤ 基准，基准右侧元素 ≥ 基准；
  3. 递归对左右子序列重复上述步骤，直到序列有序。

完整实现（适配顺序表）

// 快速排序：分区函数（找到基准位置并分区） static int _quick_partition(seqlist_t *s, int left, int right, cmp_t cmp) { // 选第一个元素为基准 char *pivot = (char *)s->data + left * s->elem_size; char *temp = (char *)malloc(s->elem_size); while (left < right) { // 从右往左找 ≤ 基准的元素 while (left < right && cmp((char *)s->data + right * s->elem_size, pivot) >= 0) { right--; } // 移到左边 memcpy(temp, (char *)s->data + right * s->elem_size, s->elem_size); memcpy((char *)s->data + left * s->elem_size, temp, s->elem_size); // 从左往右找 ≥ 基准的元素 while (left < right && cmp((char *)s->data + left * s->elem_size, pivot) <= 0) { left++; } // 移到右边 memcpy(temp, (char *)s->data + left * s->elem_size, s->elem_size); memcpy((char *)s->data + right * s->elem_size, temp, s->elem_size); } // 基准归位 memcpy((char *)s->data + left * s->elem_size, pivot, s->elem_size); free(temp); return left; // 返回基准下标 } // 快速排序递归函数 static void _quick_sort(seqlist_t *s, int left, int right, cmp_t cmp) { if (left < right) { // 找到基准位置 int pivot_pos = _quick_partition(s, left, right, cmp); // 递归左子序列 _quick_sort(s, left, pivot_pos - 1, cmp); // 递归右子序列 _quick_sort(s, pivot_pos + 1, right, cmp); } } // 对外接口：顺序表快速排序 void seqlist_quick_sort(seqlist_t *s, cmp_t cmp) { _quick_sort(s, 0, s->length - 1, cmp); }

四、折半查找（二分查找）

核心思想

  1. 前提：序列必须有序；
  2. 取有序序列中间元素与查找值比较：
    • 相等 → 找到；
    • 查找值 < 中间元素 → 去左半区间查找；
    • 查找值 > 中间元素 → 去右半区间查找；
  3. 重复直到找到元素或区间为空。

完整实现

/** * @brief 折半查找（仅适用于有序顺序表） * @param s 有序顺序表 * @param key 查找关键字 * @param cmp 比较函数 * @return 找到返回元素地址，未找到返回NULL */ void *seqlist_binary_search(const seqlist_t *s, const void *key, cmp_t cmp) { int left = 0, right = s->length - 1; while (left <= right) { // 计算中间下标（避免溢出） int mid = left + (right - left) / 2; char *mid_elem = (char *)s->data + mid * s->elem_size; int ret = cmp(mid_elem, key); if (ret == 0) { return mid_elem; // 找到 } else if (ret > 0) { right = mid - 1; // 左半区间 } else { left = mid + 1; // 右半区间 } } return NULL; // 未找到 }

五、实战作业（代码实现）

作业 1：将顺序表倒序

思路：双指针，首尾元素交换，直到指针相遇。

// 顺序表倒序 void seqlist_reverse(seqlist_t *s) { int left = 0, right = s->length - 1; char *temp = (char *)malloc(s->elem_size); while (left < right) { char *l_elem = (char *)s->data + left * s->elem_size; char *r_elem = (char *)s->data + right * s->elem_size; // 交换首尾元素 memcpy(temp, l_elem, s->elem_size); memcpy(l_elem, r_elem, s->elem_size); memcpy(r_elem, temp, s->elem_size); left++; right--; } free(temp); }

作业 2：求顺序表最大值、最小值（参数回填）

思路：遍历顺序表，通过指针参数将最大值、最小值回填给调用者。

/** * @brief 求顺序表最大/最小值（参数回填） * @param s 顺序表 * @param cmp 比较函数 * @param max_val 输出：最大值地址 * @param min_val 输出：最小值地址 */ void seqlist_get_max_min(seqlist_t *s, cmp_t cmp, void *max_val, void *min_val) { if (s->length == 0) return; // 初始化最大/最小值为第一个元素 memcpy(max_val, s->data, s->elem_size); memcpy(min_val, s->data, s->elem_size); // 遍历所有元素 for (int i = 1; i < s->length; i++) { char *elem = (char *)s->data + i * s->elem_size; // 更新最大值 if (cmp(elem, max_val) > 0) { memcpy(max_val, elem, s->elem_size); } // 更新最小值 if (cmp(elem, min_val) < 0) { memcpy(min_val, elem, s->elem_size); } } }

六、测试代码（可直接运行）

// int类型比较函数（升序） int int_cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } int main() { // 1. 创建int类型顺序表，容量10 seqlist_t *s = seqlist_create(10, sizeof(int)); // 2. 插入元素 int arr[] = {3, 1, 4, 2, 5}; for (int i = 0; i < 5; i++) { seqlist_push_back(s, &arr[i]); } printf("初始顺序表："); seqlist_print_int(s); // 3. 查找：查找元素2 int key = 2; int *find_val = seqlist_search(s, &key, int_cmp); printf("查找元素2：%s，值：%d\n", find_val ? "成功" : "失败", *find_val); // 4. 修改：将2修改为9 int new_val = 9; seqlist_modify(s, &key, int_cmp, &new_val); printf("修改后："); seqlist_print_int(s); // 5. 插入排序 seqlist_insert_sort(s, int_cmp); printf("插入排序后："); seqlist_print_int(s); // 6. 快速排序 seqlist_quick_sort(s, int_cmp); printf("快速排序后："); seqlist_print_int(s); // 7. 折半查找（有序表） find_val = seqlist_binary_search(s, &new_val, int_cmp); printf("折半查找9：%s，值：%d\n", find_val ? "成功" : "失败", *find_val); // 8. 作业1：倒序 seqlist_reverse(s); printf("倒序后："); seqlist_print_int(s); // 9. 作业2：获取最大/最小值 int max, min; seqlist_get_max_min(s, int_cmp, &max, &min); printf("最大值：%d，最小值：%d\n", max, min); return 0; }

七、运行结果

初始顺序表：3 1 4 2 5 查找元素2：成功，值：2 修改后：3 1 4 9 5 插入排序后：1 3 4 5 9 快速排序后：1 3 4 5 9 折半查找9：成功，值：9 倒序后：9 5 4 3 1 最大值：9，最小值：1

八、总结拓展

数据结构的学习是程序开发进阶的核心基石，而顺序表作为线性结构的入门模型，其设计思想贯穿后续链表、栈、队列等多种数据结构。本文完整落地了顺序表必备的查找、修改、排序功能，结合插入排序、快速排序、折半查找三大核心算法，将理论原理与代码实践相结合，同时搭配课后实操题目，全方位巩固知识点。

从实际应用角度分析，不同算法拥有各自的适用场景。线性查找无需数据有序，容错性强，但数据量大时效率低下；折半查找运算速度快，查询效率极高，却严格受制于有序条件；插入排序逻辑简单，代码易实现，适合小批量数据处理；快速排序凭借高效的分区递归机制，成为大数据排序的主流选择。理解不同算法的优劣与适用场景，是数据结构学习的关键，不仅能提升代码编写能力，更能培养算法思维。

同时，本文采用的泛型编程设计思路，是 C 语言进阶开发的重要技巧。利用void*无类型指针结合内存拷贝函数，打破数据类型限制，让同一套代码适配多种数据结构，极大提升了代码的复用性与拓展性，这一设计思路在后续结构体、自定义数据类型开发中具有极高的参考价值。

在日常学习与课程练习中，我们不能只局限于代码抄写，更要深入理解底层逻辑。比如顺序表依托连续内存带来的优势与弊端，动态扩容的实现思路，排序算法的时间复杂度变化，查找算法的优化方向等。扎实掌握顺序表相关知识，吃透排序与查找核心逻辑，能够为后续复杂数据结构、算法竞赛、项目开发打下坚实基础。日常可以多结合实际案例练习，尝试自主拓展功能，比如添加顺序表删除、扩容、清空等方法，循序渐进积累编程经验，真正做到学以致用。

http://www.jsqmd.com/news/706798/

相关文章：

  • 智能工具生成引擎ToolGen：用自然语言自动生成可执行代码
  • 小红书专业号主体变更流程
  • DaVinci平台Linux视频驱动架构与优化实践
  • 深度学习中评估指标计算库TorchMetrics的使用
  • AI代码审查实战：让CodeRabbit当你的第二双眼睛
  • 物理信息神经网络驱动的阻变存储器参数反演：从时序电压响应中精准提取二氧化钛ReRAM物理参数（Python）
  • 电脑软件《图片转PDF转换器》 - 新手入门指南
  • Unsloth Sglang Vllm核心区别和使用场景
  • Dubbo线程池策略详解：Fixed、Cached、Limited与Eager对比
  • 2026正规免费量化交易软件推荐榜：ea量化交易软件/什么是量化交易/手机量化交易软件/散户如何做量化交易/期货量化交易系统/选择指南 - 优质品牌商家
  • 循环优化设计
  • 从零开始学C语言：环境搭建与首个代码
  • 梯度下降算法详解：原理、实现与优化技巧
  • 零基础秒落地！魔珐星云打造专属法务数字人
  • 成都地区、H型钢、350X350X12X19、Q235B、包钢、现货批发供应 - 四川盛世钢联营销中心
  • 用户上周说有两个孩子，这周说有三个孩子，Agent 如何处理记忆冲突？
  • Weaviate向量数据库实战：从部署到多模态搜索与生产优化
  • PyTorch训练管理：检查点与早停技术详解
  • 成都地区、H型钢、700X300X13X14、Q235B、包钢、现货批发供应 - 四川盛世钢联营销中心
  • 成都地区、低合金H型钢、500X200X10X16、Q355B、包钢、现货批发供应 - 四川盛世钢联营销中心
  • 记录一次Jenkins构建任务的坑
  • HTML总结
  • 成都地区、H型钢、588X300X12X20、Q235B、包钢、现货批发供应 - 四川盛世钢联营销中心
  • 205套思维工具（转）
  • caj2pdf：3个技巧让知网CAJ文献在Linux上重获新生
  • 2026川渝地区耐火砖技术分享：耐火材料供应厂家/耐火材料厂商/耐火材料厂家/耐火材料哪家好/耐火材料批发/耐火材料报价/选择指南 - 优质品牌商家
  • 为什么你的Dev Container正在悄悄上传源码？揭秘.gitignore之外的5类敏感数据泄漏路径（企业级隔离方案已落地）
  • 共享记忆会毁掉系统 多智能体信息污染的五种典型路径
  • 贝叶斯信念网络：原理、构建与应用实践
  • Linearis：Rust高性能线性代数库的设计、应用与性能调优