考研数据结构：山东大学自命题与C语言代码复习攻略

简介：《数据结构》是计算机科学的核心课程，这份由山东大学课堂内容整理而成的PDF讲义，面向计算机专业学生、考研复习者及自学数据结构的学习者，重点解决对基本概念、逻辑结构与存储结构、算法分析等基础知识的系统梳理。资源为1个PDF文件，压缩包仅324KB，内容精炼，便于随时查阅与打印。文件围绕绪论与线性表两大部分展开，绪论部分系统讲解数据、数据元素、数据项、数据对象等基本术语，集合/线性/树形/网状四种逻辑结构，顺序、链式、散列、索引四种存储方式，并详细说明算法的五个重要特性、描述方式以及时间复杂度和空间复杂度的分析方法；线性表部分则覆盖其定义、基本操作，着重对比顺序存储与链式存储的实现原理、插入删除等操作的平均效率差异，帮助读者建立从逻辑设计到物理实现再到算法评估的完整认知。目前已有113人学习下载，适合作为课堂笔记补充、考前速记或第一轮入门复习的手册型资料。

1. 山东大学-数据结构.pdf：一份PDF背后的复习路线之争

不少考研党的网盘里都躺着一份“山东大学-数据结构.pdf”，它是考研数据结构这一科的高频复习资料，把线性表、栈与队列、树与二叉树、图、排序查找这些核心考点收拢成一条主线。它能解决的核心问题就一个：让目标明确的人——考山东大学计算机相关专业，或者想用山大自命题风格练手的人——把有限的复习时间花在真正会考的地方。但这里有个反直觉的结论：光靠把这本PDF从头翻到尾、在上面划重点，是考不过的。山大自命题数据结构最拉分的是算法设计题，要求手写完整且能运行的C代码，PDF里大量类C伪代码如果不亲手调通，上了考场连链表反转这样基础的操作都可能写岔。这份资料真正有用的打开方式，是带着“能不能跑起来”的标准把它读薄。

2. 先把“数据结构”的范围圈死：山大考点与408考纲的差异

拿到PDF先别急着顺着章节目录往下读。数据结构这门课内容看着就八章，但不同考试对深度的要求差别非常大。山大计算机相关专业的考研专业课，常见路线是自命题数据结构，不考操作系统、计算机组成原理和网络；这跟统考408的思路完全不同。408的数据结构只是四科之一，考查范围广但单点深度有限；山大自命题把数据结构单独拎出来考，意味着可以在这一门上砸更多时间，也意味着算法题考查得更细、更偏代码实现。

这会导致一个很现实的问题：如果你前期是照着408的思路复习数据结构的，比如花大量时间刷选择题技巧、背时间复杂度结论，转到山大风格时就会明显不适应。山大的大题经常要求你直接写一个完整的函数，包括结构体定义、参数设计、边界条件处理，而不是选一个正确选项。我见过不少同学做408真题时选择题正确率很高，一上来自命题的算法设计题就卡壳，根因就是复习重心放错了。

2.1 山大自命题与408的差异：复习深度的风向标

先把两类考试的差异摆成一张对比表，方便你定位自己的复习坐标系。

这张表不是我编出来的应试玄学，而是两类考试近几年出题风格的共性总结。408的选择题占比高，很多知识点靠“认得”就能拿分；自命题学校则更愿意在算法设计题上拉开区分度，因为代码题无法蒙，会写就是会写，不会写就是空白。结论很简单：如果你目标是山大，复习重心必须从“看懂”转向“能默写”。

从时间分配上看，我一般会建议把一半以上的复习时间压在线性表、栈与队列、二叉树、图这四块上，因为它们的代码题密度最高。排序和查找作为第二梯队，要熟练掌握每一趟的过程和代码框架；串、数组与广义表放到最后，理解核心概念、会做选择题即可。

2.2 用大纲倒推PDF重点：哪些章节精读、哪些只做选择题

拿到PDF后第一件事，是动手把目录抄到一张A4纸上，然后对照一轮真题把考察频率标注出来。这个过程花不了一下午，但它会直接决定你后面几个月的节奏，避免在低频章节上浪费大力气。

我自己的分法是三层。第一层精读精练：线性表、栈与队列、树与二叉树、图。这四个章节不能只做题，必须做到能独立写出完整代码、能默写核心算法、能答出边界条件。第二层会做题：查找，重点是折半查找、二叉排序树、哈希表构造与冲突处理；排序，重点是快排、归并、堆排的实现和每趟过程，稳定性与复杂度要张口就来。第三层扫读：串、数组与广义表。这两章考察重心在概念题，比如KMP的next数组计算、特殊矩阵的压缩存储推导，不值得花大量时间写完整串匹配代码。

为什么这样分？拿串举例。算法设计题里几乎不会让你单独写一个KMP匹配函数，它最多作为一道选择题或简答题出现，让你手工算next数组。数组与广义表和它类似，重点在地址计算和压缩映射，你花一晚上把稀疏矩阵三元组表完整实现一遍，考试用到的概率很低。图却完全相反，邻接矩阵和邻接表的建图代码、DFS、BFS、拓扑排序、最小生成树、最短路径，每一个都可能被改编成大题。

还有个更实操的验证方法：面对PDF里每一章的章末习题，只看“算法设计题”一栏。如果一道题你拿起笔10分钟内写不出完整函数框架，说明这一章的代码能力没过关，回头练到能默写为止。这个标准比“我好像看懂了”靠谱得多，因为考场上你只有一支笔和一张答题卡。

3. 按“代码优先”的顺序过一遍：C语言版数据结构的最小可运行方案

判断数据结构复习是否到位的唯一标准，是你能不能在编译器里把代码跑通，而不是能不能看懂书上的伪代码。考研手写代码最稳妥的载体是C语言，王道、严蔚敏《数据结构（C语言版）》以及大话数据结构里的代码框架基本都是C或类C。用Python、Java刷题手感虽然好，但手写代码上考场时，C的指针操作和结构体定义才是阅卷老师最熟悉的答案形态。

所以这一章，我按数据结构考研最常见的顺序，给你一套从环境到核心数据结构的“最小可运行方案”。每个代码块都直接复制就能编译，关键函数后我会解释设计原因和参数含义。

3.1 环境准备：Win/Mac 上用 GCC 跑通第一个 C 程序

不管是Windows、Mac还是Linux，第一步都是在命令行里确认C编译器可用。Windows装MinGW-w64，或者装Visual Studio时勾选“使用C++的桌面开发”里的MSVC都行；Mac自带clang；Linux自带gcc。装好后先跑一个最小程序：

# 把下面三行存成 hello.c，然后依次执行 gcc -g -Wall -o hello hello.c ./hello # 程序里只需要一个 main 函数：printf("hello\n"); return 0;

这里几个参数说明一下。-g是把调试信息写进可执行文件，后续用gdb或printf定位段错误、野指针时，断点信息才能对上行号；-Wall把常见警告全部打开，比如变量未使用、隐式类型转换，这些警告能帮你在早期拦住很多隐蔽问题。我一般调试数据结构代码不依赖复杂IDE，而是直接在代码里插入printf打印关键变量，配合编译器警告逐个击破，所以环境越轻越好。

3.2 带头结点的单链表：从初始化到删除结点的全套代码

链表是所有代码题的基础，也是翻车重灾区。下面的代码把带头结点单链表从初始化到按值删除完整实现一遍。

#include <stdio.h> #include <stdlib.h> typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域，指向下一个结点 } LNode, *LinkList; // 初始化：建立头结点，next 置空 void initList(LinkList *L) { *L = (LNode *)malloc(sizeof(LNode)); if (*L == NULL) exit(1); // 分配失败直接退出 (*L)->next = NULL; } // 头插法：新结点插到头结点之后 void insertHead(LinkList L, int x) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = L->next; // 顺序一：先让新结点指向旧首元结点 L->next = s; // 顺序二：再让头结点指向新结点 } // 按值删除第一个出现的结点，删除成功返回 1 int deleteByValue(LinkList L, int x) { LNode *pre = L, *p = L->next; while (p != NULL && p->data != x) { pre = p; p = p->next; } if (p == NULL) return 0; // 没找到 pre->next = p->next; // 先接：前驱跳到后继 free(p); // 后断：释放被删结点 return 1; } void printList(LinkList L) { LNode *p = L->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } int main() { LinkList L; initList(&L); insertHead(L, 3); insertHead(L, 2); insertHead(L, 1); printList(L); // 输出：1 2 3 deleteByValue(L, 2); printList(L); // 输出：1 3 return 0; }

逻辑说明：为什么坚持带头结点？因为空表和非空表的插入删除操作能统一，不用在main里写一堆if判断“是不是空表”。头结点的data域闲置，只当作哨兵用，换来的是代码逻辑大幅简化。删除函数里必须维护一个pre前驱指针，因为单链表只有后继指针，要删p就得先拿到它的前驱，再把pre->next指向p->next，最后free(p)，这个“先接后断”的顺序不能反。

参数说明：initList需要传LinkList*，也就是指针的指针，因为malloc出来的头结点地址要写回到调用者的L变量里；insertHead和deleteByValue直接传头指针就行，因为它们只修改结点内部的next指向，不修改头指针本身。main函数里测试的输出顺序验证了头插法的特性：后插入的元素排在前面。

3.3 栈与队列：数组实现与链表实现各写一遍

栈和队列是后续二叉树层序遍历、表达式求值、图遍历的基础，建议数组实现和链表实现都亲手写一遍。先看顺序栈：

#define MaxSize 100 typedef struct { int data[MaxSize]; int top; // 栈顶下标，空栈时为 -1 } SqStack; // 入栈：栈满返回 0，成功返回 1 int push(SqStack *s, int x) { if (s->top == MaxSize - 1) return 0; s->data[++s->top] = x; // 先移动 top，再存数据 return 1; } // 出栈：栈空返回 0，成功返回 1 int pop(SqStack *s, int *x) { if (s->top == -1) return 0; *x = s->data[s->top--]; // 先取数据，再减小 top return 1; }

参数说明：top初始为-1，表示栈里没有元素；入栈执行++top，出栈执行top--，top始终指向栈顶元素的位置。仔细对比push和pop里top移动的先后，一个先加后存，一个先取后减，这个细节是后续手写代码最常见的丢分点。

再看循环队列，它比栈多一个“牺牲一个存储单元”的经典设计：

#define MaxSize 10 typedef struct { int data[MaxSize]; int front, rear; // front 指向队头，rear 指向队尾的下一个位置 } SqQueue; // 入队：队满返回 0，成功返回 1 int enQueue(SqQueue *q, int x) { if ((q->rear + 1) % MaxSize == q->front) return 0; // 队满判断 q->data[q->rear] = x; q->rear = (q->rear + 1) % MaxSize; // 尾巴循环后移 return 1; } // 出队：队空返回 0，成功返回 1 int deQueue(SqQueue *q, int *x) { if (q->front == q->rear) return 0; // 队空判断 *x = q->data[q->front]; q->front = (q->front + 1) % MaxSize; return 1; }

为什么循环队列必须空一个位置？因为队空和队满都可能是front==rear，如果不空一个位置，就无法区分这两种状态。队空条件是front==rear，队满条件是(rear+1)%MaxSize==front，这个取模操作保证了front和rear在数组范围内环形移动。后期做二叉树层序遍历时，辅助队列用的就是这个结构，所以现在把它调通，后面直接复用。

4. 排序算法与树的实现：把PDF里的伪代码变成能跑的C代码

排序和树是算法大题的高发区，也是PDF里伪代码密度最高的地方。伪代码不是不能跑，而是省略了大量实现细节——递归边界、指针判空、返回值处理、中间变量初始化。这一章把快排和二叉树的核心代码补齐到可直接运行的程度。

4.1 快速排序的基准选取：为什么PDF版本会栈溢出

很多PDF版本里的快排，基准直接取a[low]。这个写法简洁，但有个致命问题：对已经有序的数组，每次划分只移除一个元素，递归深度达到n，栈直接溢出。用“三数取中”可以缓解退化成O(n²)的情况。

#include <stdio.h> // 三数取中：把 low、mid、high 三个位置的元素排好序，返回 mid 的下标 int medianOfThree(int a[], int low, int high) { int mid = low + (high - low) / 2; if (a[low] > a[mid]) { int t = a[low]; a[low] = a[mid]; a[mid] = t; } if (a[low] > a[high]) { int t = a[low]; a[low] = a[high]; a[high] = t; } if (a[mid] > a[high]) { int t = a[mid]; a[mid] = a[high]; a[high] = t; } return mid; } // 划分：挖坑填数法，返回基准元素的最终位置 int partition(int a[], int low, int high) { int idx = medianOfThree(a, low, high); int pivot = a[idx]; // 把基准换到 low 位置，腾出 a[low] 当坑 int t = a[low]; a[low] = a[idx]; a[idx] = t; while (low < high) { while (low < high && a[high] >= pivot) high--; a[low] = a[high]; // 右边小于 pivot 的填到左边坑 while (low < high && a[low] <= pivot) low++; a[high] = a[low]; // 左边大于 pivot 的填到右边坑 } a[low] = pivot; // 基准归位 return low; } // 递归边界必须写 low >= high，否则死循环或栈溢出 void quickSort(int a[], int low, int high) { if (low >= high) return; int pos = partition(a, low, high); quickSort(a, low, pos - 1); // 左半闭区间 quickSort(a, pos + 1, high); // 右半闭区间 }

逻辑说明：partition里内层的两个while都要带上low < high条件，否则high和low会互相穿过导致越界访问。基准先挖走，相当于数组里默认留下一个坑，先从右往左找小于pivot的值填坑，再从左往右找大于pivot的值填坑，最后把pivot放回low和high相遇的位置。参数说明：low和high是闭区间下标，递归边界low >= high表示当前区间没有元素或只有一个元素，必须放在函数第一行。

4.2 二叉树：层序遍历与递归非递归互换

二叉树这块，PDF里画图很清晰，但代码往往只给递归版本。考试要求你写非递归版本时，很多人就卡住了。这里用数组模拟栈和队列，避免手写链表结构引入额外变量。

#include <stdio.h> #include <stdlib.h> typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 用数组队列保存结点地址，容量 100 练习题足够 typedef struct { BiTree data[100]; int front, rear; } Queue; // 层序遍历：从上到下、从左到右 void levelOrder(BiTree root) { if (root == NULL) return; Queue q = { .front = 0, .rear = 0 }; q.data[q.rear++] = root; // 根结点先入队 while (q.front != q.rear) { BiTree cur = q.data[q.front++]; // 出队一个 printf("%d ", cur->data); if (cur->lchild) q.data[q.rear++] = cur->lchild; if (cur->rchild) q.data[q.rear++] = cur->rchild; } } // 非递归中序遍历：数组栈模拟系统调用栈 void inOrderNoRec(BiTree root) { BiTree stack[100]; int top = -1; BiTree p = root; while (p != NULL || top != -1) { while (p != NULL) { // 一路向左，全部压栈 stack[++top] = p; p = p->lchild; } if (top != -1) { p = stack[top--]; // 左走到底，出栈访问 printf("%d ", p->data); p = p->rchild; // 转向右子树 } } }

逻辑说明：层序遍历的核心是“出队一个、访问、左右孩子入队”，队列保证每一层从左到右，再逐层向下。这里用线性数组队列，front和rear直接后移，不需要循环取模，因为二叉树层序最多同时入队的结点数不会超出数组容量，练习题100个结点绰绰有余。非递归中序的外层循环条件“p != NULL || top != -1”覆盖了两种情况：要么当前结点不为空需要继续往左，要么栈里有等待访问的结点。参数说明：递归转非递归的通用思路是用栈保存“还没处理完的上下文”，每次把左链全部压栈，弹出一个访问，再转右子树，这个模式吃透后，前序、后序、DFS都能套。

5. 避坑：山大版数据结构复习中最常见的6个翻车点

这章写点血泪经验。数据结构复习的坑很集中，基本都是代码能力没跟上、边界条件没处理导致的。每条我按“现象→原因→解决”写，你对照自查，能省下大量无效调试时间。

5.1 现象：PDF里的代码抄下来编译报错，报错信息看不懂

原因：资料里大量代码是类C伪代码，省略了#include、结构体定义、返回值类型，甚至省略了malloc的头文件stdlib.h。解决：抄代码时先把头文件和typedef补全，再逐个函数编译。如果报“未声明的标识符”，优先检查函数用到的结构体是否定义在前面；如果报“不可达代码”，多半是if或while后面直接跟了return，括号范围盖住了后续逻辑。

5.2 现象：链表题一写就断链，打印出来元素少一半

原因：指针修改顺序反了。典型错误是插入时先把前驱的next指向新结点，再让新结点的next指向原来的后继，结果原后继彻底丢失；或者删除时先free(p)，再想拿p->next，直接读到野指针。解决：画图。每个操作先画出“从哪个箭头断开、从哪个箭头接上”，再落代码。插入口诀是“先接后断”，删除口诀是“先跳过后继，再释放当前结点”。

5.3 现象：二叉树递归代码思路对，一运行栈溢出或空指针崩溃

原因：递归边界写错。常见坑是拿叶子结点当终止条件，写成if (p->lchild == NULL && p->rchild == NULL)就return，这会让空指针传进函数后继续访问p->lchild。解决：所有二叉树递归函数第一行固定写if (p == NULL) return;，先保证空指针安全，再写业务逻辑。这个习惯能挡住八成以上二叉树代码崩溃。

5.4 现象：图算法看得懂，真让写完整代码就懵，不知道从哪下手

原因：图的存储结构没单独练。邻接矩阵和邻接表的建图代码，PDF里通常只给示意片段，很多同学跳过建图直接看DFS、BFS，结果读懂了遍历过程但写不出函数签名。解决：先花一个下午把邻接矩阵的“建图+DFS+BFS”完整敲一遍，再换成邻接表敲一遍。注意函数签名要写全，比如void DFS(int v, int visited[])，把visited数组显式传进去，不要依赖全局变量。

5.5 现象：排序的稳定性、复杂度记混，代码和结论对不上号

原因：只看不跑，没有建立“代码过程”和“结论”的联系。快排为什么不稳定？因为partition里基准会和远处的元素交换，相同元素的相对顺序可能被打乱——这个结论不亲手跟踪一趟划分过程很难内化。解决：写一个随机数组生成器，把冒泡、快排、归并每趟排序后的数组print出来，观察相同值的相对位置变化。跑三次，稳定性结论自然就记住了，比死背口诀可靠。

5.6 现象：真题算法题看着会写，模拟考一紧张就写岔，指针满天飞

原因：平时用IDE写代码，自动补全和编译纠错把问题提前挡住了，手写代码的手感没建立起来。考场上是白纸黑字，没有编译器提示。解决：复习后期每天抽20分钟，在纸上默写一个核心算法，比如链表原地反转、快排、二叉树非递归中序遍历，默写完再对照PDF里的框架逐行核对。坚持两周，手写速度和心态都会明显变化。

6. 复习后期怎么把PDF用出“后悔药”效果：真题复盘与算法默写

前期按章节过代码，后期PDF的角色要变，它不再是一本从头读到尾的书，而是一本查漏字典。不用等学完所有章节再开始真题，我自己的节奏是第二轮复习就穿插真题，每做一套，都把涉及的知识点在PDF目录旁边做一个记号，练到后期一眼就能看出哪些章节是重灾区。

建议把下面几个高频算法整理成一张默写清单，每天挑一个，限时完成：

真题复盘时，不要只看对错。把错题映射到PDF里的具体知识点：一道拓扑排序大题做错了，回到图这一章，把入度表更新和队列结构的关系重新画一遍；一道链表逆置综合题卡住，回到线性表章节，把头插法代码再默写一遍。这样做两套真题，PDF的目录就会被你标出一张“高频考点热力图”，后续冲刺就只看这些地方。

我自己当年最亏的事，就是只顾着“看懂”。看视频、看资料都觉得简单，一合上书写链表反转，纸上画了三遍才把指针顺序理清。后来改成每天早饭后默写一个算法，坚持两周，手感和心态都稳了。数据结构这门课，别人讲一万遍不如自己跑通一遍，希望帮到你。

本文还有配套的精品资源，点击获取