数据结构入门指南

Ne0inhk

— 10 min read

数据结构入门指南：线性结构核心知识点与C语言实现

数据结构是程序设计的基石，直接决定代码的效率与可扩展性，尤其在Linux内核开发、嵌入式设备资源管理等场景中，合理运用数据结构能显著优化程序性能。本文聚焦入门必学的线性结构（数组、链表、栈、队列），通过精简概念+规范C语言代码，带初学者快速掌握核心用法，为后续复杂结构（树、图）打下基础。

一、数据结构的核心价值与应用场景

数据结构的本质是“组织与存储数据的方式”，其选择直接影响程序的时间复杂度与空间复杂度，核心应用场景如下：

  • 底层开发：Linux内核用链表管理进程、栈保存函数调用上下文，嵌入式设备用队列缓冲外设数据。
  • 算法优化：任何算法都依赖数据结构承载数据，如排序算法基于数组/链表，搜索算法基于树结构。
  • 工程实践：数据库索引用B+树，消息队列用队列结构，缓存机制用哈希表（后续进阶）。

入门阶段重点攻克线性结构——即数据元素按线性顺序排列的结构，是最基础且高频使用的类型。

二、预备知识：环境与核心概念

2.1 开发环境

沿用C语言入门环境（Windows Dev-C++/Linux GCC），无需额外配置，代码兼容双平台，编译运行方式与C语言程序一致。

2.2 核心概念

  • 逻辑结构：数据元素间的关联关系（线性结构为“一对一”，如数组元素、链表节点）。
  • 物理结构：数据在内存中的存储方式，分为“顺序存储”（如数组，连续内存）和“链式存储”（如链表，离散内存）。
  • 时间复杂度：衡量操作（增删查改）的效率，常用O(1)（常数级）、O(n)（线性级）表示，越低效率越高。

三、线性结构核心知识点与C语言实现

以下按“数组→链表→栈→队列”的顺序讲解，每个结构聚焦核心特性、实现代码与适用场景，代码遵循变量名规范，仅保留核心功能。

3.1 数组（顺序存储线性结构）

3.1.1 核心特性

连续内存存储，支持随机访问（通过下标快速定位），但插入/删除元素需移动后续元素，效率较低（时间复杂度O(n)），适合元素数量固定、查询频繁的场景。

3.1.2 C语言实现（动态数组）

静态数组大小固定，实际开发中常用动态数组（基于malloc分配内存），实现元素的增删查改：

#include<stdio.h>#include<stdlib.h>// 动态数组结构体typedefstruct{int* array_data;// 存储数据的指针int array_size;// 数组容量int element_count;// 实际元素个数} DynamicArray;// 初始化动态数组voidinit_dynamic_array(DynamicArray* dynamic_array,int initial_size){ dynamic_array->array_data =(int*)malloc(initial_size *sizeof(int)); dynamic_array->array_size = initial_size; dynamic_array->element_count =0;}// 插入元素（尾部插入，效率O(1)）voidinsert_element(DynamicArray* dynamic_array,int element_value){// 容量不足时扩容（翻倍扩容，减少扩容次数）if(dynamic_array->element_count == dynamic_array->array_size){ dynamic_array->array_size *=2; dynamic_array->array_data =(int*)realloc(dynamic_array->array_data, dynamic_array->array_size *sizeof(int));} dynamic_array->array_data[dynamic_array->element_count++]= element_value;}// 查找元素（按值查找，效率O(n)）intfind_element(DynamicArray* dynamic_array,int target_value){for(int i =0; i < dynamic_array->element_count; i++){if(dynamic_array->array_data[i]== target_value){return i;// 返回下标，未找到返回-1}}return-1;}// 释放内存voidfree_dynamic_array(DynamicArray* dynamic_array){free(dynamic_array->array_data); dynamic_array->array_data =NULL; dynamic_array->array_size =0; dynamic_array->element_count =0;}intmain(){ DynamicArray dynamic_array;init_dynamic_array(&dynamic_array,2);// 初始容量为2insert_element(&dynamic_array,10);insert_element(&dynamic_array,20);insert_element(&dynamic_array,30);// 触发扩容，容量变为4int target_index =find_element(&dynamic_array,20);printf("元素20的下标：%d\n", target_index);free_dynamic_array(&dynamic_array);return0;}

3.2 链表（链式存储线性结构）

3.2.1 核心特性

离散内存存储，通过指针连接节点，插入/删除元素无需移动数据（仅修改指针），效率O(1)，但不支持随机访问（需从头遍历，效率O(n)），适合元素数量动态变化、插入删除频繁的场景（如Linux进程链表）。

3.2.2 C语言实现（单链表）

单链表是最基础的链表类型，每个节点包含数据域和指向下一节点的指针：

#include<stdio.h>#include<stdlib.h>// 链表节点结构体typedefstructLinkNode{int node_data;// 数据域structLinkNode* next;// 指针域，指向后续节点} LinkNode;// 创建新节点 LinkNode*create_link_node(int data_value){ LinkNode* new_node =(LinkNode*)malloc(sizeof(LinkNode)); new_node->node_data = data_value; new_node->next =NULL;return new_node;}// 头部插入节点（效率O(1)）voidinsert_node_head(LinkNode** head_node,int data_value){ LinkNode* new_node =create_link_node(data_value); new_node->next =*head_node;*head_node = new_node;}// 遍历链表voidtraverse_link_list(LinkNode* head_node){ LinkNode* current_node = head_node;while(current_node !=NULL){printf("%d ", current_node->node_data); current_node = current_node->next;}printf("\n");}// 释放链表内存voidfree_link_list(LinkNode* head_node){ LinkNode* temp_node;while(head_node !=NULL){ temp_node = head_node; head_node = head_node->next;free(temp_node);}}intmain(){ LinkNode* head_node =NULL;// 链表头节点初始化insert_node_head(&head_node,30);insert_node_head(&head_node,20);insert_node_head(&head_node,10);printf("链表遍历结果：");traverse_link_list(head_node);// 输出：10 20 30free_link_list(head_node);return0;}

3.3 栈（先进后出LIFO结构）

3.3.1 核心特性

受限线性结构，仅允许在一端（栈顶）插入/删除元素，另一端（栈底）固定，符合“先进后出”规则，常用顺序存储（数组）实现，效率O(1)，应用场景如函数调用栈、括号匹配、表达式求值。

3.3.2 C语言实现（顺序栈）
#include<stdio.h>#include<stdlib.h>#defineMAX_STACK_SIZE100// 栈最大容量// 顺序栈结构体typedefstruct{int stack_data[MAX_STACK_SIZE];// 存储栈元素int stack_top;// 栈顶指针（-1表示空栈）} SequenceStack;// 初始化栈voidinit_sequence_stack(SequenceStack* sequence_stack){ sequence_stack->stack_top =-1;}// 判断栈空intis_stack_empty(SequenceStack* sequence_stack){return sequence_stack->stack_top ==-1;}// 入栈voidpush_stack_element(SequenceStack* sequence_stack,int element_value){if(sequence_stack->stack_top == MAX_STACK_SIZE -1){printf("栈满，无法入栈\n");return;} sequence_stack->stack_data[++sequence_stack->stack_top]= element_value;}// 出栈intpop_stack_element(SequenceStack* sequence_stack){if(is_stack_empty(sequence_stack)){printf("栈空，无法出栈\n");exit(1);// 异常退出}return sequence_stack->stack_data[sequence_stack->stack_top--];}intmain(){ SequenceStack sequence_stack;init_sequence_stack(&sequence_stack);push_stack_element(&sequence_stack,10);push_stack_element(&sequence_stack,20);push_stack_element(&sequence_stack,30);printf("出栈元素：%d\n",pop_stack_element(&sequence_stack));// 30printf("出栈元素：%d\n",pop_stack_element(&sequence_stack));// 20return0;}

3.4 队列（先进先出FIFO结构）

3.4.1 核心特性

受限线性结构，允许在一端（队尾）插入元素，另一端（队头）删除元素，符合“先进先出”规则，常用链式存储实现（避免顺序存储的假溢出），应用场景如任务调度、外设数据缓冲、消息队列。

3.4.2 C语言实现（链式队列）
#include<stdio.h>#include<stdlib.h>// 队列节点结构体typedefstructQueueNode{int node_data;structQueueNode* next;} QueueNode;// 队列结构体（记录队头和队尾）typedefstruct{ QueueNode* queue_front;// 队头 QueueNode* queue_rear;// 队尾} LinkQueue;// 初始化队列voidinit_link_queue(LinkQueue* link_queue){ link_queue->queue_front = link_queue->queue_rear =(QueueNode*)malloc(sizeof(QueueNode)); link_queue->queue_front->next =NULL;}// 判断队列空intis_queue_empty(LinkQueue* link_queue){return link_queue->queue_front == link_queue->queue_rear;}// 入队voidenqueue_element(LinkQueue* link_queue,int element_value){ QueueNode* new_node =(QueueNode*)malloc(sizeof(QueueNode)); new_node->node_data = element_value; new_node->next =NULL; link_queue->queue_rear->next = new_node; link_queue->queue_rear = new_node;}// 出队intdequeue_element(LinkQueue* link_queue){if(is_queue_empty(link_queue)){printf("队列空，无法出队\n");exit(1);} QueueNode* temp_node = link_queue->queue_front->next;int element_value = temp_node->node_data; link_queue->queue_front->next = temp_node->next;// 队尾与队头重合时，更新队尾if(link_queue->queue_rear == temp_node){ link_queue->queue_rear = link_queue->queue_front;}free(temp_node);return element_value;}intmain(){ LinkQueue link_queue;init_link_queue(&link_queue);enqueue_element(&link_queue,10);enqueue_element(&link_queue,20);enqueue_element(&link_queue,30);printf("出队元素：%d\n",dequeue_element(&link_queue));// 10printf("出队元素：%d\n",dequeue_element(&link_queue));// 20return0;}

四、经典实战案例：括号匹配（栈的应用）

以面试高频题“括号匹配”为例，演示栈的实际应用，判断输入字符串中的括号（()、[]、{}）是否成对闭合：

#include<stdio.h>#include<string.h>#defineMAX_STACK_SIZE100typedefstruct{char stack_data[MAX_STACK_SIZE];int stack_top;} BracketStack;voidinit_bracket_stack(BracketStack* bracket_stack){ bracket_stack->stack_top =-1;}voidpush_bracket(BracketStack* bracket_stack,char bracket_char){ bracket_stack->stack_data[++bracket_stack->stack_top]= bracket_char;}charpop_bracket(BracketStack* bracket_stack){return bracket_stack->stack_data[bracket_stack->stack_top--];}// 判断括号匹配intis_bracket_matched(char* input_string){ BracketStack bracket_stack;init_bracket_stack(&bracket_stack);int string_length =strlen(input_string);for(int i =0; i < string_length; i++){char current_char = input_string[i];// 左括号入栈if(current_char =='('|| current_char =='['|| current_char =='{'){push_bracket(&bracket_stack, current_char);}else{// 右括号无对应左括号，匹配失败if(bracket_stack.stack_top ==-1)return0;char top_bracket =pop_bracket(&bracket_stack);// 检查括号是否成对if((current_char ==')'&& top_bracket !='(')||(current_char ==']'&& top_bracket !='[')||(current_char =='}'&& top_bracket !='{')){return0;}}}// 栈空说明所有括号都匹配return bracket_stack.stack_top ==-1;}intmain(){char input_string[100];printf("请输入包含括号的字符串：");scanf("%s", input_string);if(is_bracket_matched(input_string)){printf("括号匹配成功\n");}else{printf("括号匹配失败\n");}return0;}

五、入门常见问题与避坑指南

  • 链表空指针问题：遍历或操作链表时，需先判断节点指针是否为NULL，避免野指针访问（如链表尾节点next必须置空）。
  • 栈/队列边界判断：入栈前检查栈满，出栈前检查栈空；队列同理，避免越界访问或空操作。
  • 内存泄漏：链式结构（链表、链式队列）的节点需手动free，避免长期运行导致内存耗尽，建议封装专门的释放函数。
  • 顺序存储假溢出：顺序队列若仅移动指针，会出现“队尾满但队头有空余”的假溢出，可通过循环队列优化。

六、进阶学习路线（贴合底层开发）

掌握线性结构后，可按以下路线深化，适配Linux系统编程与嵌入式开发需求：

  1. 复杂线性结构：双向链表、循环链表（Linux内核常用）、循环队列、优先级队列（堆实现）。
  2. 非线性结构：树（二叉树、红黑树）、图，重点掌握二叉树的遍历（前中后序）与红黑树在Linux内核中的应用。
  3. 算法结合：学习基于数据结构的排序（链表排序、堆排序）、搜索（二叉树查找）算法，优化时间复杂度。
  4. 实战落地：在嵌入式开发中用队列缓冲串口数据，用链表管理传感器节点，复刻Linux内核简单链表逻辑。

总结

数据结构入门的关键是“理解特性+多实战”，线性结构虽简单，但需明确不同结构的适用场景——数组适合查询，链表适合增删，栈/队列适合特定顺序需求。本文实现的代码均为核心逻辑，可直接用于课程作业或小型项目，建议手动敲写并调试，理解指针操作与内存管理的细节。

后续学习中，需结合Linux内核源码、嵌入式项目案例，体会数据结构在底层开发中的优化作用，逐步建立“数据结构决定程序性能”的思维，为复杂项目开发筑牢基础。

Read more

【数据结构与算法】21.合并两个有序链表(LeetCode)

【数据结构与算法】21.合并两个有序链表(LeetCode)

文章目录 * 合并两个有序链表：高效算法解析与实现 * 问题描述 * 核心思路：双指针尾插法 * 完整代码实现 * 关键点解析 * 1. 边界条件处理 * 2. 头节点初始化 * 3. 节点比较与插入 * 4. 剩余节点处理 * 常见错误与修正 * 优化方案：哨兵节点 * 算法应用场景 * 总结 * 总结 合并两个有序链表：高效算法解析与实现 链表合并是数据结构中的经典问题，在算法面试和实际开发中经常出现。本文将深入解析如何高效合并两个有序链表，并展示C语言的实现方案。 问题描述 给定两个升序排列的链表list1和list2，要求将它们合并为一个新的升序链表并返回。新链表应该通过拼接给定链表的节点来完成。 示例： 输入：list1 = [1,2,4], list2 = [1,3,4] 输出：[1,1,2,3,4,4] 核心思路：

By Ne0inhk

【学习记录】使用 John the Ripper 和 Hashcat破解 RAR、ZIP 与 7z 文件密码（Windows教程）

文章目录 * 📌 引言 * 📦 支持类型 * 🛠️ 所需工具下载地址（Windows 官方编译版） * 额外工具 * 🔐 一、破解RAR 压缩文件密码 * 步骤 1：获取RAR 文件的加密哈希值 * 步骤 2：将正确的哈希值复制到 `hash.txt` 文件 * 步骤 3：在 Hashcat 官方 wiki 查找 `-m` 哈希模式 ID * 步骤 4: 使用 Hashcat 破解哈希值 * 📁 二、破解ZIP 压缩文件密码 * 步骤 1：提取 ZIP 文件的加密哈希值 * 步骤 2：将正确的哈希值复制到 `hash.txt` 文件 * 步骤

By Ne0inhk
Flutter 三方库 collection — 鸿蒙应用全方位集合操作与算法增强利器，实现鸿蒙深度适配下的高效容器过滤与优先级队列实战全解析（适配鸿蒙 HarmonyOS Next ohos）

Flutter 三方库 collection — 鸿蒙应用全方位集合操作与算法增强利器，实现鸿蒙深度适配下的高效容器过滤与优先级队列实战全解析（适配鸿蒙 HarmonyOS Next ohos）

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net。 Flutter 三方库 collection — 鸿蒙应用全方位集合操作与算法增强利器，实现鸿蒙深度适配下的高效容器过滤与优先级队列实战全解析 前言 在鸿蒙（OpenHarmony）应用开发中，数据结构的选择往往决定了逻辑的成败。当标准的 List、Set、Map 无法满足更高级的需求（例如：需要一个自动按优先级排序的任务队列，或者需要判断两个深度嵌套的 Map 是否完全一致）时，开发者就需要引入更强大的集合支持。 collection 是 Dart 官方维护的最核心基础库之一。它不仅补充了大量缺失的容器类型（如 PriorityQueue、Heap），还为原生集合提供了极其丰富的扩展工具类（如 ListEquality、CanonicalizedMap）。在 Flutter for OpenHarmony 的底层架构实践中，它是处理复杂业务逻辑、优化检索效率的必备“基石”。 一、原理解析 / 概念介绍

By Ne0inhk
【数据结构】常见时间复杂度以及空间复杂度

【数据结构】常见时间复杂度以及空间复杂度

时间复杂度与空间复杂度 * 一、复杂度的概念 * 二、时间复杂度 * 1、大O的渐进表示法 * 2、函数clock计算运算时间 * 3、常见复杂度对比 * 3.1常数项复杂度 * 3.2线性时间复杂度 * 案例1 * 案例2 * 3.3平方阶复杂度 * 3.4对数复杂度 * 3.5递归函数 * 单递归 * 双递归 * 三、空间复杂度 * 冒泡排序O(1) * 三个反置O(N) 一、复杂度的概念 * 一个算法的好坏，主要是对比两者的时间和空间两个维度，也就是时间和空间复杂度。 * 时间复杂度主要衡量一个算法运行的快慢，空间复杂度主要衡量一个算法运行需要的额外空间 二、时间复杂度 * 算法的时间复杂度是一个函数式T(N)，算法中的基本操作的执行次数，为算法的时间复杂度。 * 注：编译器的不同，编译所需要的时间也不同。越新的编译器，编译的时间往往比旧的编译器快 * 当一个算法函数式为T(

By Ne0inhk