简介这份《西安电子科技大学-数据结构与算法-期末知识点总结》面向高校计算机相关专业学生尤其是备考数据结构与算法期末考试的西电学子也可供考研复习或自学该课程的同学参考。资源以PDF形式呈现共1个文件压缩包约2.09MB内容按基本概念、线性表、栈与队列、树与二叉树、图、查找算法、排序算法等模块系统梳理涵盖数据元素与数据项、逻辑结构与物理结构、算法五大特性、顺序表与单链表的对比、循环队列判空判满条件、二叉树性质与遍历方式等高频考点。已有1230人学习下载说明其在校内具有一定认可度。读者可借助这份总结快速建立知识框架对照课堂笔记查漏补缺在考前集中回顾易混淆概念与典型结论提升复习效率。1. 一份期末知识点总结PDF为什么值得当成工程手册来读西安电子科技大学-数据结构与算法-期末知识点总结.pdf这个标题看起来像是一份普通的课程复习资料但如果你正在准备408统考、正在带数据结构实验课、或者刚转行需要把链表和排序算法重新捡起来这份总结类PDF的价值远不止“应付考试”。它本质上是一张被压缩过的知识地图线性表、栈与队列、树与二叉树、图、查找、排序每一块都对应着真实工程里反复出现的结构选型和复杂度取舍。问题在于大部分人在搜索引擎里敲下“数据结构期末复习”或“数据结构知识点总结”之后拿到的是散落在各处的碎片——王道408的笔记、严蔚敏教材的课后答案、CSDN上格式混乱的代码片段。真正能让人从“知道这是什么”走到“能自己写出来、能判断该用哪个”的材料少之又少。这篇不是PDF内容的转述而是把这份总结背后最常被考、也最常被用到的几个硬核模块拆成可以动手复现的路径。适合谁看正在啃数据结构与算法C语言版的在校生、准备考研408数据结构代码必背的备考者、以及需要快速回顾排序算法和KMP算法实现细节的开发者。2. 从PDF目录到代码线性表与链表的落地拆解2.1 顺序表与链表的选型判断不是“哪个更好”而是“哪个更不坏”任何一份数据结构知识点总结都会在开头讲线性表但考试资料通常只告诉你顺序表随机访问O(1)、链表插入删除O(1)却不告诉你实际写代码时该怎么选。我一般会先看三个指标数据量是否可预估、操作以读为主还是以写为主、内存是否连续可用。如果数据量在编译期或启动期就能确定上限且查询远多于增删顺序表几乎总是更优——缓存友好没有指针跳转的开销。反过来如果元素数量动态变化剧烈或者需要在中间频繁插入删除链表的结构优势才会体现出来。但这里有一个容易被忽略的边界链表的O(1)插入删除是有前提的——你已经持有了目标节点的前驱指针。如果每次都要从头遍历找位置那实际复杂度是O(n)和顺序表比并没有优势。很多数据结构实验报告里写“链表插入更快”但代码里却在循环里做get(i)这就是典型的翻车现场。下面是一个单链表的核心操作实现用C语言写因为数据结构与算法C语言版和严蔚敏数据结构c语言版pdf是搜索量最大的教材版本考试和实验也基本以C为准。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 头插法建表时间复杂度O(n)但生成的链表是逆序的 Node* createListHeadInsert(int arr[], int n) { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; for (int i 0; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-data arr[i]; p-next head-next; // 新节点指向原首节点 head-next p; // 头节点指向新节点 } return head; } // 尾插法建表需要维护尾指针否则每次插入都是O(n) Node* createListTailInsert(int arr[], int n) { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; Node *tail head; // tail始终指向最后一个节点 for (int i 0; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-data arr[i]; p-next NULL; tail-next p; tail p; // 更新尾指针 } return head; } // 在第pos个位置插入pos从1开始需要先找到第pos-1个节点 int insertAt(Node *head, int pos, int value) { Node *p head; int j 0; while (p ! NULL j pos - 1) { // 找前驱 p p-next; j; } if (p NULL) return 0; // pos越界 Node *newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next p-next; p-next newNode; return 1; }头插法和尾插法的区别不只是顺序问题。头插法每次操作只涉及头节点代码简单但生成的链表与输入顺序相反尾插法需要额外维护tail指针但保持了输入顺序。考试里经常考“给定序列用头插法建表后的输出顺序”这就是送分题但实验里如果搞混了调试时会发现遍历结果莫名其妙反了。insertAt函数里那个while循环是链表操作的核心模式找前驱。参数pos从1开始计数循环条件是j pos - 1循环结束后p指向第pos-1个节点。如果p变成NULL说明pos超出了链表长度。这个边界判断在考试代码题里经常被扣分因为很多人只写循环不写越界检查。2.2 从链表到栈和队列用结构体封装而不是裸指针数据结构期末复习里栈和队列通常紧跟着线性表出现。考试要求你手写push、pop、enqueue、dequeue但实验报告里如果直接用裸指针操作代码会变得难以维护。我一般会用结构体把栈顶指针和容量封装在一起这样在传参时只需要传一个结构体指针而不是二级指针。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; // 栈顶下标空栈时为-1 } SeqStack; void initStack(SeqStack *s) { s-top -1; } int push(SeqStack *s, int value) { if (s-top MAXSIZE - 1) return 0; // 栈满 s-data[(s-top)] value; // 先加再存 return 1; } int pop(SeqStack *s, int *value) { if (s-top -1) return 0; // 栈空 *value s-data[(s-top)--]; // 先取再减 return 1; }这里有两个参数细节值得注意。push里用的是(s-top)先自增再赋值因为top初始为-1第一个元素应该存在data[0]。pop里用的是(s-top)--先取值再自减。这两个顺序如果写反栈的操作就会整体偏移一位考试时这种错误直接导致后续所有操作全错。队列的循环队列版本更考验边界处理。判空条件是front rear判满条件通常用(rear 1) % MAXSIZE front牺牲一个存储单元来区分空和满。这个“牺牲一个单元”的做法在王道数据结构里讲得很清楚但自己写代码时容易忘记取模导致数组越界。3. 树与图从遍历序列反推结构的实操方法3.1 二叉树遍历的递归与非递归实现考试写递归工程用非递归数据结构知识点总结里二叉树的遍历是必考内容。前序、中序、后序的递归写法三行就能搞定但考试经常要求写非递归版本因为非递归才能体现你对栈的理解。更重要的是在实际工程里递归深度受限于调用栈大小一棵退化成链表的二叉树递归遍历会直接栈溢出。先看递归版本这是理解遍历顺序的基础typedef struct TreeNode { int val; struct TreeNode *left, *right; } TreeNode; void inorderRecursive(TreeNode *root) { if (root NULL) return; inorderRecursive(root-left); printf(%d , root-val); inorderRecursive(root-right); }非递归中序遍历需要用栈模拟递归的调用过程。核心逻辑是一路向左把节点压栈直到没有左孩子然后弹出栈顶访问再转向右孩子。void inorderIterative(TreeNode *root) { TreeNode *stack[100]; int top -1; TreeNode *p root; while (p ! NULL || top ! -1) { while (p ! NULL) { // 一路向左 stack[top] p; p p-left; } if (top ! -1) { p stack[top--]; // 弹出栈顶 printf(%d , p-val); // 访问 p p-right; // 转向右子树 } } }这段代码里外层while的条件是p ! NULL || top ! -1两个条件缺一不可。如果只写p ! NULL当p变成NULL但栈里还有节点时循环会提前结束如果只写top ! -1根节点还没入栈时循环根本不会开始。这个细节在408数据结构代码必背里是高频考点。前序和后序的非递归实现略有不同。前序是入栈前访问后序需要额外记录上一个访问的节点来判断是从左子树返回还是从右子树返回。考试里后序非递归出现的频率稍低但一旦出现就是拉分题。3.2 由遍历序列重建二叉树前序中序的递归划分“给定前序和中序序列画出二叉树”是数据结构期末复习的经典题型。这个问题的本质是递归划分前序的第一个元素是根在中序里找到这个根的位置左边就是左子树的中序序列右边就是右子树的中序序列然后根据长度在前序里切分出左右子树的前序序列。TreeNode* buildTree(int *preorder, int preStart, int preEnd, int *inorder, int inStart, int inEnd) { if (preStart preEnd) return NULL; int rootVal preorder[preStart]; TreeNode *root (TreeNode*)malloc(sizeof(TreeNode)); root-val rootVal; root-left root-right NULL; int rootIndex inStart; while (inorder[rootIndex] ! rootVal) rootIndex; // 在中序中找根 int leftLen rootIndex - inStart; // 左子树节点数 root-left buildTree(preorder, preStart 1, preStart leftLen, inorder, inStart, rootIndex - 1); root-right buildTree(preorder, preStart leftLen 1, preEnd, inorder, rootIndex 1, inEnd); return root; }参数说明preStart和preEnd是前序序列的起止下标inStart和inEnd是中序序列的起止下标。左子树在前序中的范围是preStart1到preStartleftLen右子树是preStartleftLen1到preEnd。这个划分逻辑如果写错一个下标整棵树就建歪了。我一般会先用一个简单例子手算一遍前序ABDEC中序DBEAC根是A左子树中序是DBE长度3右子树中序是C长度1对应前序左子树是BDE右子树是C。注意前序中序可以唯一确定一棵二叉树后序中序也可以但前序后序不行。这个结论在选择题里反复出现原因是前序和后序只能确定根的位置无法区分只有一个孩子的情况。3.3 图的存储与遍历邻接矩阵和邻接表的代码切换图这一块考试重点在邻接矩阵和邻接表的相互转换以及DFS和BFS的遍历序列。邻接矩阵适合稠密图判断两点之间是否有边是O(1)邻接表适合稀疏图遍历某个节点的所有邻居更高效。实际写代码时我一般先用邻接矩阵快速验证逻辑再根据数据规模决定是否换成邻接表。#define MAXV 100 typedef struct { int edges[MAXV][MAXV]; int n, e; // 顶点数和边数 } MGraph; void initMGraph(MGraph *g, int n) { g-n n; g-e 0; for (int i 0; i n; i) for (int j 0; j n; j) g-edges[i][j] 0; } void addEdge(MGraph *g, int u, int v) { g-edges[u][v] 1; g-edges[v][u] 1; // 无向图对称赋值 g-e; } int visited[MAXV]; void DFS(MGraph *g, int v) { visited[v] 1; printf(%d , v); for (int i 0; i g-n; i) { if (g-edges[v][i] 1 !visited[i]) DFS(g, i); } }addEdge里对称赋值是无向图的关键如果只写g-edges[u][v] 1那就变成了有向图。DFS的递归写法依赖visited数组防止重复访问这个数组必须在遍历前清零。BFS则需要一个队列来辅助遍历顺序是按层扩展考试里经常要求写出从某个顶点出发的BFS序列。4. 排序与查找KMP和归并排序的手写细节4.1 KMP算法的next数组从暴力匹配到O(nm)KMP算法是数据结构期末复习里最容易翻车的考点之一。暴力匹配的时间复杂度是O(n*m)KMP通过预处理模式串的next数组把匹配过程优化到O(nm)。next数组的含义是当模式串的第j个字符与主串不匹配时模式串应该回退到next[j]的位置继续比较。void getNext(char *pattern, int *next) { int len strlen(pattern); next[0] -1; int i 0, j -1; while (i len - 1) { if (j -1 || pattern[i] pattern[j]) { i; j; next[i] j; } else { j next[j]; } } } int KMP(char *text, char *pattern) { int next[100]; getNext(pattern, next); int i 0, j 0; int tLen strlen(text), pLen strlen(pattern); while (i tLen j pLen) { if (j -1 || text[i] pattern[j]) { i; j; } else { j next[j]; } } if (j pLen) return i - pLen; // 匹配成功返回起始下标 return -1; }getNext里next[0] -1是人为规定的哨兵值表示模式串第一个字符就不匹配时主串指针i需要后移模式串指针j回到-1后下一轮变成0。j next[j]是回退操作也是KMP的核心。很多人在考试时把next[i] j写成next[i] j 1这取决于next数组的定义方式——有的教材next[0]0有的next[0]-1。严蔚敏数据结构c语言版pdf用的是-1起始的版本王道数据结构也是。如果考试时不确定先看题目给的示例。4.2 归并排序与堆排序两种O(n log n)的取舍排序算法是数据结构排序算法里内容最多的一章。冒泡排序算法c和堆排序算法是搜索热词但考试里归并排序的出现频率同样很高尤其是要求手写merge过程。void merge(int *arr, int left, int mid, int right, int *temp) { int i left, j mid 1, k left; while (i mid j right) { if (arr[i] arr[j]) temp[k] arr[i]; else temp[k] arr[j]; } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (int p left; p right; p) arr[p] temp[p]; } void mergeSort(int *arr, int left, int right, int *temp) { if (left right) { int mid left (right - left) / 2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); } }merge函数里三个while循环的顺序不能乱第一个循环同时遍历左右两段谁小取谁后面两个循环处理剩余元素。temp数组是辅助空间归并排序的空间复杂度是O(n)这是它和堆排序最大的区别。堆排序是原地排序空间O(1)但常数因子比归并排序大且不稳定。考试里如果问“哪个排序算法稳定”归并排序是稳定的堆排序和快速排序都不稳定。堆排序的核心是建堆和调整堆。建堆从最后一个非叶子节点开始依次向下调整。调整的过程是比较当前节点和左右孩子如果孩子更大就交换然后继续向下调整被交换的孩子节点。void heapify(int *arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { int temp arr[i]; arr[i] arr[largest]; arr[largest] temp; heapify(arr, n, largest); } } void heapSort(int *arr, int n) { for (int i n / 2 - 1; i 0; i--) // 建堆 heapify(arr, n, i); for (int i n - 1; i 0; i--) { int temp arr[0]; arr[0] arr[i]; arr[i] temp; heapify(arr, i, 0); // 调整剩余元素 } }heapify里left 2*i1和right 2*i2是0-based数组的公式如果考试用的是1-based数组公式变成2*i和2*i1。这个下标差异是堆排序代码题最常见的错误来源。5. 避坑与排查期末复习和实验里最容易翻车的五个点5.1 链表操作中的野指针与内存泄漏现象程序在遍历链表时随机崩溃或者运行结束后内存占用持续升高。原因删除节点时只写了p p-next没有先free掉被删除的节点或者插入节点时没有给newNode-next赋初值导致next指向随机地址。解决删除操作的标准写法是先用一个临时指针保存要删除的节点调整前驱的next指针后再free。插入操作里malloc之后立刻设置data和next不要留任何未初始化字段。5.2 循环队列的判空判满条件写反现象队列操作在运行一段时间后突然报“队列已满”但实际元素个数远小于容量。原因判满条件写成了front rear判空条件写成了(rear1)%MAXSIZE front两者刚好写反。解决记住“牺牲一个单元”的约定——空队列是front rear满队列是(rear1)%MAXSIZE front。如果不想牺牲单元可以额外维护一个size变量但考试里默认用牺牲单元法。5.3 KMP的next数组下标越界现象KMP匹配时程序在next[j]处崩溃j变成负数后没有正确处理。原因getNext里next[0] -1但在匹配循环里没有判断j -1的情况直接访问pattern[j]导致越界。解决匹配循环的条件里必须包含j -1当j为-1时直接执行i; j;相当于主串后移一位、模式串从头开始。5.4 二叉树非递归遍历的栈溢出现象用数组模拟栈时遍历一棵深度较大的二叉树导致数组下标越界。原因栈数组的大小按节点总数分配但非递归遍历的栈深度最大等于树的高度最坏情况下单支树高度等于节点数。解决栈数组的大小至少设为节点总数或者用动态分配的链栈。考试里如果题目没有限制直接开一个和节点数一样大的数组最保险。5.5 排序算法稳定性判断错误现象选择题问“下列排序算法中稳定的是”选了快速排序或堆排序。原因没有记住稳定性的本质——相等元素在排序后是否保持原来的相对顺序。解决稳定的排序有冒泡、插入、归并、基数不稳定的有快速、堆、选择、希尔。快速排序不稳定的经典例子是[2a, 2b, 1]第一趟划分后两个2的相对顺序可能改变。6. 把PDF知识点变成可运行的验证脚本期末复习最怕的是“看懂了但写不出来”。我的习惯是每复习完一个模块就写一个最小验证脚本用随机数据跑一遍和标准库的结果对比。比如排序算法可以用C标准库的qsort作为参照生成1000个随机整数分别用自己写的归并排序和qsort排序然后逐元素比较。如果结果不一致就打印出原始数组和两个排序结果定位到第一个不同的位置。#include stdio.h #include stdlib.h #include string.h #include time.h int cmp(const void *a, const void *b) { return (*(int*)a - *(int*)b); } int main() { srand(time(NULL)); int n 1000; int *arr1 (int*)malloc(n * sizeof(int)); int *arr2 (int*)malloc(n * sizeof(int)); int *temp (int*)malloc(n * sizeof(int)); for (int i 0; i n; i) { arr1[i] rand() % 10000; arr2[i] arr1[i]; } mergeSort(arr1, 0, n - 1, temp); qsort(arr2, n, sizeof(int), cmp); int ok 1; for (int i 0; i n; i) { if (arr1[i] ! arr2[i]) { printf(Mismatch at index %d: %d vs %d\n, i, arr1[i], arr2[i]); ok 0; break; } } if (ok) printf(All %d elements sorted correctly.\n, n); free(arr1); free(arr2); free(temp); return 0; }这个脚本的价值在于它把“我觉得我写对了”变成“数据证明我写对了”。参数n可以调整从10到100000观察不同规模下的运行时间。如果归并排序在n100000时明显慢于qsort检查merge里是否频繁malloc——正确的做法是只分配一次temp数组在所有递归调用中复用。对于KMP算法验证方法是生成一个随机文本和一个随机模式串分别用暴力匹配和KMP匹配比较返回的下标是否一致。如果暴力匹配返回-1而KMP返回了非负值说明next数组计算有误。对于二叉树重建可以先生成一棵随机二叉树输出它的前序和中序序列然后用重建函数还原再输出还原后的前序序列和原始前序对比。如果一致说明重建逻辑正确。这种“生成-变换-还原-对比”的验证模式比单纯看代码或背知识点有效得多。我当年复习数据结构期末的时候就是靠这个方法把KMP的next数组彻底搞明白的——手算十遍不如让程序跑一遍报错。希望帮到你。本文还有配套的精品资源点击获取