数据结构完整教程从基础到核心数据结构是计算机科学中研究数据组织、存储和管理方式的学科其核心目标是设计出能够高效支持数据访问和修改的存储方案。它不仅是算法设计与分析的基础更是构建高效、可靠软件系统的关键。一个精心选择的数据结构可以极大提升程序的性能反之则可能导致效率低下甚至无法工作。本教程将系统性地介绍数据结构的全部核心知识点。一、数据结构基础概念在深入具体结构之前必须明确其基本术语和评价体系。1. 基本术语数据对客观事物符号化的表示是计算机中可以操作的对象。数据元素组成数据的基本单位在计算机中通常作为一个整体进行考虑和处理例如一条学生记录。数据项构成数据元素的不可分割的最小单位例如学生记录中的学号、姓名。数据对象性质相同的数据元素的集合是数据的子集。数据类型一组性质相同的值的集合以及定义在这个集合上的一组操作的总称例如整型、浮点型。抽象数据类型一个数学模型以及定义在该模型上的一组操作。它仅取决于其逻辑特性而与在计算机内部如何表示和实现无关体现了封装和信息隐藏的思想。2. 数据结构的分类数据结构可以从两个维度进行分类逻辑结构和物理存储结构。逻辑结构描述数据元素之间的逻辑关系与数据的存储无关。线性结构数据元素之间存在一对一的线性关系。如线性表、栈、队列、串。非线性结构数据元素之间存在一对多或多对多的关系。如树、图、集合。物理结构又称存储结构是数据结构在计算机中的表示映像包括数据元素的表示和关系的表示。顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。其特点是逻辑上相邻的元素在物理位置上也相邻。链式存储结构借助指示元素存储地址的指针来表示数据元素间的逻辑关系。其特点是逻辑上相邻的元素在物理位置上不一定相邻。3. 算法与复杂度分析算法是为解决特定问题而规定的一系列有限的操作步骤。评价一个算法的优劣主要依靠复杂度分析。时间复杂度定性描述算法运行时间随问题规模增长的变化趋势。常用大O记法表示。例如O(1)表示常数时间复杂度O(n)表示线性时间复杂度O(n²)表示平方时间复杂度。空间复杂度定性描述算法在运行过程中临时占用存储空间大小随问题规模增长的变化趋势。二、 线性结构线性结构是最基本且应用最广泛的数据结构其特点是元素之间存在唯一的首尾关系。1. 线性表线性表是具有相同数据类型的n个数据元素的有限序列。其基本操作包括初始化、销毁、插入、删除、查找、遍历等。实现方式对比实现方式存储特点优点缺点核心操作时间复杂度顺序表使用一组地址连续的存储单元依次存放元素。随机访问快O(1)存储密度高。插入/删除需移动大量元素O(n)预分配空间不灵活。访问: O(1), 插入/删除: O(n)单链表节点包含数据域和指向后继节点的指针域通过指针链接成链。插入/删除灵活O(1)已知位置时无需预知规模。不支持随机访问访问需遍历O(n)指针域消耗额外空间。访问: O(n), 插入/删除: O(1)*// 顺序表结构定义 (C语言示例) #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; // 存储数据元素 int length; // 当前长度 } SqList; // 单链表节点定义 typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域指向下一个节点 } LNode, *LinkList; // 在单链表第i个位置插入元素eStatus ListInsert_L(LinkList *L, int i, int e) { LinkList p *L; int j 0; // 寻找第i-1个节点 while (p j i - 1) { p p-next; j; } if (!p || j i - 1) return ERROR; // i不合法 // 创建新节点 LinkList s (LinkList)malloc(sizeof(LNode)); s-data e; // 插入操作 s-next p-next; p-next s; return OK; }链表变体双向链表节点包含指向前驱和后继的指针支持双向遍历但维护成本更高。循环链表尾节点的指针指向头节点形成一个环便于从任意节点出发遍历整个链表。2. 栈栈是一种后进先出的线性表限定仅在表尾进行插入和删除操作。表尾称为栈顶表头称为栈底。基本操作入栈、出栈、获取栈顶元素、判断栈空。应用场景函数调用栈、表达式求值、括号匹配、浏览器的前进后退。// 顺序栈的实现 typedef struct { int data[MAXSIZE]; int top; // 栈顶指针 } SqStack; // 入栈操作 Status Push(SqStack *S, int e) { if (S-top MAXSIZE1) return ERROR; // 栈满 S-data[(S-top)] e; // 栈顶指针先加1再赋值 return OK; } // 出栈操作 Status Pop(SqStack *S, int *e) { if (S-top -1) return ERROR; // 栈空 *e S-data[(S-top)--]; // 先取值栈顶指针再减1 return OK; }3. 队列队列是一种先进先出的线性表限定在表的一端插入在另一端删除。插入端称为队尾删除端称为队头。基本操作入队、出队、获取队头元素、判断队空。应用场景任务调度、消息队列、广度优先搜索。// 循环队列的顺序实现解决“假溢出” typedef struct { int data[MAXSIZE]; int front; // 队头指针 int rear; // 队尾指针} SqQueue; // 初始化队列 Status InitQueue(SqQueue *Q) { Q-front 0; Q-rear 0; return OK; } // 入队操作 Status EnQueue(SqQueue *Q, int e) { if ((Q-rear 1) % MAXSIZE Q-front) return ERROR; // 队满判断 Q-data[Q-rear] e; Q-rear (Q-rear 1) % MAXSIZE; // 循环后移 return OK; }4. 串串是由零个或多个字符组成的有限序列是内容受限的线性表元素为字符。其基本操作包括求串长、连接、求子串、模式匹配等。模式匹配算法经典的KMP算法通过计算next数组在主串指针不回溯的情况下完成匹配将时间复杂度从O(m*n)优化至O(mn)。三、 非线性结构树与二叉树树形结构反映了数据元素之间的层次关系其中二叉树是最重要且研究最透彻的结构。1. 树的基本概念定义树是n个结点的有限集。n0时为空树。对于非空树有且仅有一个根结点其余结点可分为m个互不相交的有限集每个集合本身又是一棵树称为根的子树。术语结点、结点的度、叶子结点、分支结点、孩子、双亲、兄弟、层次、深度、高度、森林。2. 二叉树二叉树是每个结点最多有两棵子树且子树有左右之分的树形结构。性质第i层上至多有2^(i-1)个结点。深度为k的二叉树至多有2^k1个结点。对任何二叉树若叶子结点数为n0度为2的结点数为n2则n0 n2 1。存储结构顺序存储用一组连续的存储单元按照完全二叉树的编号顺序存放结点。适用于完全二叉树否则空间浪费严重。链式存储使用二叉链表结点包含数据域、左孩子指针、右孩子指针。遍历算法遍历是二叉树所有操作的基础有四种主要方式。// 二叉链表结点定义 typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 递归先序遍历根 - 左 - 右 void PreOrderTraverse(BiTree T) { if (T NULL) return; visit(T-data); // 访问根节点 PreOrderTraverse(T-lchild); // 遍历左子树 PreOrderTraverse(T-rchild); // 遍历右子树 } // 递归中序遍历左 - 根 - 右 void InOrderTraverse(BiTree T) { if (T NULL) return; InOrderTraverse(T-lchild); visit(T-data); InOrderTraverse(T-rchild); } // 递归后序遍历左 - 右 - 根 void PostOrderTraverse(BiTree T) { if (T NULL) return; PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); visit(T-data); } // 层次遍历需要借助队列实现3. 特殊二叉树及应用二叉排序树左子树上所有结点的值均小于根结点的值右子树上所有结点的值均大于根结点的值左右子树也分别是二叉排序树。用于动态查找其中序遍历序列是一个有序序列。平衡二叉树在BST的基础上要求任何结点的左右子树高度差绝对值不超过1。通过旋转操作LL, RR, LR, RL维持平衡保证查找、插入、删除的时间复杂度为O(log n)。哈夫曼树带权路径长度最小的二叉树用于数据压缩哈夫曼编码。构建方法是每次选择权值最小的两棵树合并。堆一种特殊的完全二叉树。大顶堆中每个结点的值都大于等于其孩子结点的值小顶堆则相反。堆常用于实现优先队列和堆排序。4. 树、森林与二叉树的转换树、森林和二叉树之间可以通过固定的规则进行相互转换这使得对树和森林的操作可以借助成熟的二叉树算法来实现。四、 非线性结构图图是比树更一般的非线性结构用于表示多对多的关系。图中顶点集合不能为空但边集可以为空。1. 图的基本概念定义图G由顶点集V和边集E组成记为G(V, E)。分类有向图/无向图、带权图/无权图、简单图/多重图。术语度、入度、出度、路径、回路、连通图、强连通图、生成树。2. 图的存储结构存储结构描述优点缺点适用场景邻接矩阵使用一个二维数组A[i][j]表示顶点i到j的边关系。直观便于判断顶点间是否有边方便计算度。空间复杂度O(n²)稀疏图浪费空间。稠密图。邻接表为每个顶点建立一个单链表链表中是与该顶点邻接的所有顶点。空间复杂度O(ne)适合稀疏图。判断两点间是否有边需遍历链表。稀疏图需频繁遍历邻接点。// 邻接矩阵表示法 #define MAX_VERTEX_NUM 100 typedef struct { int vexs[MAX_VERTEX_NUM]; // 顶点表 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum, arcnum; // 顶点数和边数 } MGraph; // 邻接表表示法 typedef struct ArcNode { // 边表结点 int adjvex; // 该边所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条边的指针 // InfoType info; // 网的权值 } ArcNode; typedef struct VNode { // 顶点表结点 int data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的边的指针 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph;3. 图的遍历从图中某一顶点出发访问图中所有顶点且每个顶点仅被访问一次。深度优先搜索类似于树的先序遍历。从起始点出发访问其第一个邻接点再以该邻接点为新起点递归进行直到“走不通”再回溯。// DFS递归算法邻接表存储 int visited[MAX_VERTEX_NUM]; // 访问标记数组 void DFS(ALGraph G, int v) { visited[v] 1; visit(v); // 访问顶点v ArcNode *p G.vertices[v].firstarc; while (p ! NULL) { int w p-adjvex; if (!visited[w]) DFS(G, w); p p-nextarc; } }广度优先搜索类似于树的层次遍历。使用队列从起始点开始依次访问其所有邻接点再按顺序访问这些邻接点的邻接点。4. 图的应用算法最小生成树在连通带权图中找到一棵权值总和最小的生成树。Prim算法从某个顶点开始每次选择连接已选顶点集和未选顶点集的最小权值边并将该边连接的顶点加入已选集。适用于稠密图。Kruskal算法将所有边按权值排序从小到大选择边若该边连接的两个顶点属于不同的连通分量则加入生成树。适用于稀疏图。最短路径Dijkstra算法求单源最短路径从某个源点到其余各顶点的最短路径要求边权非负。Floyd算法求所有顶点对之间的最短路径。拓扑排序针对有向无环图生成一个顶点序列使得对每条有向边(u, v)u在序列中都出现在v之前。用于判断工程能否顺利进行是否有环及确定活动顺序。关键路径在带权有向图中从源点到汇点的最长路径决定了整个工程的最短完成时间。用于项目管理。五、 查找技术查找是在大量数据中定位特定元素的过程。1. 静态查找表查找表的数据在查找过程中不发生变化。顺序查找从表的一端开始逐个比较。时间复杂度O(n)。折半查找要求查找表有序。每次与中间元素比较将查找范围缩小一半。时间复杂度O(log n)。分块查找将表分成若干块块内无序块间有序。先确定块再在块内查找。2. 动态查找表查找表的数据在查找过程中可以动态地插入或删除。二叉排序树如前所述插入、删除、查找的平均时间复杂度为O(log n)最坏情况退化成单支树为O(n)。平衡二叉树通过自平衡机制将最坏情况下的性能也维持在O(log n)。B树与B树一种平衡的多路查找树专为磁盘等外存设备设计能有效减少磁盘I/O次数广泛应用于数据库和文件系统索引。B树所有叶子节点在同一层每个节点包含多个关键字和子树指针。B树与B树的主要区别是非叶子节点仅起索引作用所有关键字记录都出现在叶子节点中且叶子节点间通过指针链接成有序链表便于范围查询。3. 哈希表哈希表通过一个哈希函数将关键字直接映射到存储地址从而在平均O(1)时间内完成查找。核心概念哈希函数将关键字映射为存储地址的函数。常见方法有直接定址法、除留余数法、平方取中法等。冲突处理不同关键字映射到同一地址的情况。开放定址法当发生冲突时寻找下一个空的哈希地址。包括线性探测法、平方探测法等。链地址法将所有哈希地址相同的记录链接在同一个单链表中。// 链地址法哈希表结构示例 typedef struct HashNode { int key; int value; struct HashNode *next; } HashNode; typedef struct { HashNode **table; // 指针数组每个元素是一个链表头指针 int size; } HashMap; // 插入操作使用除留余数法 void insert(HashMap *map, int key, int value) { int index key % map-size; // 哈希函数 HashNode *newNode (HashNode*)malloc(sizeof(HashNode)); newNode-key key; newNode-value value; // 头插法插入链表 newNode-next map-table[index]; map-table[index] newNode; }六、 排序技术排序是将一组无序的数据元素调整为有序序列的过程。以下是各类内部排序算法的总结与对比。类别算法名称平均时间复杂度最坏时间复杂度空间复杂度稳定性核心思想插入排序直接插入排序O(n²)O(n²)O(1)稳定将待排元素插入到前面已排序序列的合适位置。希尔排序O(n^1.3)O(n²)O(1)不稳定将序列按增量分组对每组进行插入排序增量逐渐减小至1。交换排序冒泡排序O(n²)O(n²)O(1)稳定相邻元素两两比较逆序则交换使最大/小元素“冒泡”到顶端。快速排序O(n log n)O(n²)O(log n)不稳定分治法。选取基准将序列分为小于基准和大于基准的两部分递归排序。选择排序简单选择排序O(n²)O(n²)O(1)不稳定每轮从未排序序列中选择最小大元素放到已排序序列末尾。堆排序O(n log n)O(n log n)O(1)不稳定将序列构建成大顶堆将堆顶元素最大与末尾交换调整堆重复。归并排序二路归并排序O(n log n)O(n log n)O(n)稳定分治法。将序列递归分成两半分别排序再将两个有序子序列合并。基数排序基数排序O(d(nr))O(d(nr))O(nr)稳定不基于比较。按关键字位个、十、百...依次进行稳定排序。// 快速排序示例递归版 void QuickSort(int arr[], int low, int high) { if (low high) { int pivotpos Partition(arr, low, high); // 划分获取基准位置 QuickSort(arr, low, pivotpos - 1); // 递归排序左子表 QuickSort(arr, pivotpos 1, high); // 递归排序右子表 } } int Partition(int arr[], int low, int high) { int pivot arr[low]; // 用第一个元素作为基准 while (low high) { while (low high arr[high] pivot) --high; arr[low] arr[high]; // 将比基准小的移到左端 while (low high arr[low] pivot) low; arr[high] arr[low]; // 将比基准大的移到右端 } arr[low] pivot; // 基准归位 return low; // 返回基准位置 } // 归并排序示例void Merge(int arr[], int low, int mid, int high) { int *temp (int*)malloc((high - low 1) * sizeof(int)); // 辅助数组 int i low, j mid 1, k 0; while (i mid j high) { if (arr[i] arr[j]) temp[k] arr[i]; else temp[k] arr[j]; } while (i mid) temp[k] arr[i]; while (j high) temp[k] arr[j]; for (i low, k 0; i high; i, k) arr[i] temp[k]; // 拷贝回原数组 free(temp); } void MergeSort(int arr[], int low, int high) { if (low high) { int mid (low high) / 2; MergeSort(arr, low, mid); MergeSort(arr, mid 1, high); Merge(arr, low, mid, high); } }七、 广义表与数组数组由相同类型的数据元素构成的有序序列是线性表的推广。存储时通常采用顺序存储结构可通过下标公式直接计算元素地址。特殊矩阵压缩存储对于对称矩阵、三角矩阵、稀疏矩阵等为节省空间只存储非零元素或特定区域元素。广义表线性表的推广其元素可以是原子也可以是另一个广义表。广义表具有共享和递归的特性。学习路径与建议系统学习数据结构应遵循“理解概念 - 掌握实现 - 分析复杂度 - 应用实践”的路径。夯实基础从线性表、栈、队列等线性结构开始理解其逻辑和物理结构。突破难点二叉树和图是非线性结构的核心务必掌握其遍历、存储和各种经典算法。掌握工具查找和排序是解决实际问题的利器不仅要会写代码更要理解其适用场景和优劣。动手实践对于每个数据结构亲手用代码实现其基本操作创建、插入、删除、查找、遍历。通过调试和可视化工具观察数据在内存中的动态变化过程。联系应用思考所学数据结构在操作系统、数据库、编译原理、网络等领域的应用例如B树用于数据库索引、栈用于函数调用、队列用于消息缓冲。数据结构的学习是一个从具体到抽象再从抽象到具体的过程。它培养的是一种用计算机高效描述和解决现实问题的思维模式这种能力是计算机专业人才的核心竞争力。参考来源数据结构知识点总结[可运行源码]资源-CSDN下载5208070-数据结构-教学大纲.docx“数据结构与算法”教学大纲清华大学数据结构讲义深度解析 - CSDN文库如何系统学习数据结构?