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

数据结构核心知识点精要

news 2026/4/26 2:07:48

数据结构是计算机科学中研究数据组织、存储和操作方法的学科。其核心是设计高效的数据组织和算法，以优化程序的执行效率与资源消耗。以下从核心概念、数据结构分类、关键知识点及应用场景等方面进行总结。

一、数据结构三要素

数据结构由以下三个要素构成：

要素	说明	示例
逻辑结构	数据元素之间的逻辑关系，与存储无关。	集合、线性结构、树形结构、图状结构（网状结构）。
物理结构（存储结构）	数据在计算机中的存储方式。	顺序存储、链式存储、索引存储、散列存储。
数据的运算	施加在数据上的操作，如插入、删除、查找、排序等。	在顺序表上实现插入元素。

逻辑结构是独立于存储的抽象模型，而存储结构是其物理实现。例如，线性表（逻辑结构）既可以用数组（顺序存储）实现，也可以用链表（链式存储）实现。

二、算法与复杂度分析

算法是对特定问题求解步骤的描述，其优劣通过时间复杂度和空间复杂度来衡量。

时间复杂度：关注算法执行时间随数据规模增长的趋势。常用大O记法表示，如 O(1), O(log n), O(n), O(n log n), O(n²) 等。
空间复杂度：关注算法运行所需额外内存空间随数据规模增长的趋势。

三、核心数据结构详解

1. 线性结构

数据元素之间存在“一对一”的线性关系。

线性表

概念：具有相同数据类型的 n 个数据元素的有限序列。

实现方式：

顺序表（数组）：元素在内存中连续存放。支持随机访问，但插入删除需移动大量元素。

// C语言顺序表插入操作示例（在位置i插入元素e） #define MaxSize 50 typedef struct { int data[MaxSize]; int length; } SqList; bool ListInsert(SqList *L, int i, int e) { if (i < 1 || i > L->length + 1) return false; // 判断i范围是否有效 if (L->length >= MaxSize) return false; // 存储空间已满 for (int j = L->length; j >= i; j--) { L->data[j] = L->data[j - 1]; // 将第i个及之后的元素后移 } L->data[i - 1] = e; // 插入新元素 L->length++; return true; }

链表：元素通过指针链接，在内存中非连续存放。插入删除高效，但失去了随机访问能力。主要有单链表、双链表、循环链表等变体。

栈

概念：后进先出（LIFO）的线性表。只允许在表尾（栈顶）进行插入（入栈）和删除（出栈）操作。
应用：函数调用栈、表达式求值、括号匹配、递归实现。

队列

概念：先进先出（FIFO）的线性表。插入在队尾，删除在队头。
变体：
- 循环队列：解决顺序队列假溢出的问题。
- 双端队列：两端都允许插入和删除。
应用：任务调度、消息队列、广度优先搜索（BFS）的辅助数据结构。

2. 树形结构

数据元素之间存在“一对多”的层次关系。

二叉树

性质：第 i 层至多有 2^(i-1) 个节点；深度为 k 的二叉树至多有 2^k - 1 个节点。

遍历：先序、中序、后序（递归或非递归实现）、层次遍历。

// 二叉树先序遍历递归算法（C语言） typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void PreOrder(BiTree T) { if (T != NULL) { visit(T); // 访问根节点 PreOrder(T->lchild); // 递归遍历左子树 PreOrder(T->rchild); // 递归遍历右子树 } }

特殊二叉树：
- 满二叉树：所有分支节点都有左右子树，且叶子都在同一层。
- 完全二叉树：除最后一层外，其余层都是满的，且最后一层叶子节点从左向右连续排列。此性质使其适合用数组高效存储。
二叉排序树（BST）：左子树上所有节点值均小于根节点值，右子树上所有节点值均大于根节点值。其中序遍历序列是递增有序的。
平衡二叉树（AVL树）：BST的一种，且任何节点的左右子树高度差绝对值不超过1，通过旋转操作保持平衡，保证查找效率为 O(log n) 。
哈夫曼树（最优二叉树）：带权路径长度最短的二叉树，用于数据压缩（哈夫曼编码）。

3. 图状结构

数据元素之间存在“多对多”的复杂关系。

基本概念

由顶点集 V 和边集 E 组成，记为 G=(V, E)。
分类：有向图 vs 无向图；加权图 vs 无权图。

存储方式

邻接矩阵：二维数组存储顶点间关系。适合稠密图，可快速判断两顶点是否邻接。
邻接表：数组+链表存储。适合稀疏图，节省空间，便于找任一顶点的所有邻接点。

遍历算法

深度优先搜索（DFS）：类似树的先序遍历，使用栈（递归）实现。
广度优先搜索（BFS）：类似树的层次遍历，使用队列实现。

重要算法

最小生成树：在加权无向图中找一棵边权值和最小的生成树。算法：Prim算法（适合稠密图）、Kruskal算法（适合稀疏图）。
最短路径：
- Dijkstra算法：求单源最短路径（权值非负）。
- Floyd算法：求所有顶点对之间的最短路径。
拓扑排序：针对有向无环图（DAG），得到一个顶点的线性序列，满足若存在路径从 A 到 B，则序列中 A 在 B 之前。用于任务调度、课程安排。

4. 查找结构

基本查找

顺序查找：O(n)。
二分查找：要求有序顺序表，O(log n)。

树形查找

二叉排序树（BST）：查找、插入、删除平均 O(log n)，最差 O(n)。
平衡二叉树（AVL）：查找稳定在 O(log n)，但维护平衡开销大。
B树与B+树：多路平衡查找树，大幅减少磁盘I/O次数，广泛应用于数据库和文件系统索引。

散列查找（哈希表）

核心：通过哈希函数将关键字映射到存储地址。
关键问题：
- 哈希函数构造：直接定址、除留余数、平方取中等。
- 冲突处理：开放定址法（线性探测、平方探测）、链地址法（拉链法）。
特点：理想情况下查找、插入、删除时间复杂度可达 O(1)。

5. 排序算法

排序是数据运算的重要部分，算法性能是考查重点。

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定	说明
冒泡排序	O(n²)	O(n²)	O(1)	稳定	相邻元素比较交换。
直接插入排序	O(n²)	O(n²)	O(1)	稳定	将元素插入已排序序列。
简单选择排序	O(n²)	O(n²)	O(1)	不稳定	每次选最小元素交换到前面。
希尔排序	O(n^1.3)	O(n²)	O(1)	不稳定	分组插入排序，是插入排序的改进。
快速排序	O(n log n)	O(n²)	O(log n)	不稳定	分治思想，选定枢轴划分。
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	利用堆这种数据结构。
归并排序	O(n log n)	O(n log n)	O(n)	稳定	分治思想，先分后合。
基数排序	O(d(n+r))	O(d(n+r))	O(n+r)	稳定	按位分配收集，d为位数，r为基数。

// 快速排序分区操作示例（C语言） int Partition(int A[], int low, int high) { int pivot = A[low]; // 选取第一个元素作为枢轴 while (low < high) { while (low < high && A[high] >= pivot) --high; A[low] = A[high]; // 将比枢轴小的移到左端 while (low < high && A[low] <= pivot) ++low; A[high] = A[low]; // 将比枢轴大的移到右端 } A[low] = pivot; // 枢轴存放到最终位置 return low; // 返回枢轴位置 }