简介山东大学《数据结构》课程PDF课件面向计算机专业本科生、考研复习者及自学数据结构的学习者。这份资料以精炼的课堂讲义形式系统梳理了绪论与线性表两大部分的核心知识从数据、数据元素、数据项、数据对象等基本概念出发解释了集合、线性、树形、网状四类逻辑结构以及顺序、链式、散列、索引四种存储结构同时对算法的有穷性、确定性、可行性等五大特性时间复杂度的O(1)、O(n)、O(n^2)、O(log n)等常见量级以及空间复杂度的评价方法均作了简明归纳。第二章线性表部分则重点剖析了顺序表和链式表的定义、存储特点与典型操作包括插入、删除、查找、合并等算法步骤及其时间复杂度分析并配有C语言类型描述示例便于读者理解理论并联系实际编码。包内共1个PDF文件约324KB体量小巧方便手机、平板随时翻阅也适合打印后对照教材复习。目前已有113人学习下载适合期末备考、考研专业课第一轮梳理或教学备课辅助。1. 拿到这份山东大学数据结构PDF先看绪论和线性表这两块考研和期末复习数据结构最怕的不是题难而是手头资料东一块西一块课件缺页、代码抄错、复杂度结论对不上。这份山东大学的数据结构PDF属于典型的课堂讲义型资源把绪论和线性表两大部分讲得很细顺序表和单链表的插入、删除、合并都给了完整C语言代码复杂度分析也逐条列了结论。它不是一本从头讲到尾的教材更像老师上课时沉淀下来的核心笔记适合拿来对着课本划重点、背概念、抄代码。如果你是冲着数据结构考研、期末突击或者补C语言版数据结构基础来的这份PDF的前两章基本覆盖了高频考点但里面有几处明显的排版笔误和结论偏差读的时候得带着批判眼光别直接照抄。这篇笔记就把这些地方逐条挑出来给你看。2. 绪论逻辑结构、存储结构与复杂度分析2.1 四类逻辑结构集合、线性、树形、网状怎么区分数据结构这门课的第一个核心概念是逻辑结构。PDF里给了一个二元组定义data_structure (D, S)D是数据元素的有限集S是D上关系的有限集。这个定义很多同学背得下来但做题时还是分不清四类结构。集合结构的特点是元素之间除了“同属于一个集合”之外没有其他关系线性结构是每个元素最多一个直接前驱和一个直接后继比如英文字母表、学生花名册树形结构是每个结点最多一个直接前驱但可以有多个直接后继典型的是目录树、家族谱网状结构则是前驱后继都不限制比如交通路线图、课程先修关系图。判断逻辑结构时有个容易混淆的点逻辑结构与数据元素本身的形式、内容无关与元素的相对位置无关与所含结点个数也无关。也就是说同样是20个整数可以组织成线性表也可以组织成完全二叉树全看你怎么定义它们之间的关系。考研选择题里经常给一组元素让你判断属于什么结构关键就是看关系描述的是一对一、一对多还是多对多。PDF里“一个结点代表一个元素结点之间的连线代表逻辑关系”这句话其实就是图论里图的直观表达建议动手画一下那四类结构的关系图比背十遍定义都管用。2.2 存储结构顺序、链式、散列、索引四种方式逻辑结构是抽象的数学模型存储结构才是数据在计算机里实际的表示方式。PDF把存储结构分成四类顺序存储、链式存储、散列存储、索引存储。顺序存储靠元素在内存中物理位置的相邻来表达逻辑相邻关系C语言里用数组描述链式存储靠指针显式地记录元素之间的关系C语言里用指针描述散列存储通过散列函数直接算出元素存放位置索引存储则是额外建一张索引表来定位元素。在C语言的数据结构实现里最常用的就是前两种。顺序存储的典型例子是顺序表它的特点是逻辑上相邻的结点在存储位置上仍然相邻因此可以随机存取想读第i个元素直接算地址就行缺点是插入和删除要大量移动元素而且表长一旦定下来就不好扩展。链式存储的典型例子是单链表它用指针把结点串起来插入删除只需要修改指针不需要搬动数据但查找某个位置的结点必须从头开始遍历不能随机存取。这里有一个重要的换算公式PDF里给了第i个元素在顺序表中的位置是LOC(ai) LOC(a1) (i-1) * L其中L是每个元素占用的存储单元数。这个公式考研小题经常考比如给了首地址和元素大小让你算第5个元素的地址直接用这个公式往里代数就行。注意i从1开始数组下标从0开始换算时不要混。2.3 时间复杂度的O记号与五个常见阶算法效率的度量PDF里明确分了事后统计和事前分析估算两种。事后统计受机器性能、编译器优化影响太大基本只能作为参考真正用于理论分析的是事前估算也就是时间复杂度。定义是算法中基本操作重复执行的次数是问题规模n的某个函数f(n)记作T(n) O(f(n))表示随问题规模增大算法执行时间的增长率和f(n)相同。PDF给出了五个常见复杂度阶常量阶O(1)、线性阶O(n)、平方阶O(n²)、对数阶O(log n)、指数阶O(2ⁿ)。做题时要把这些阶按增长速度排序O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)。判断时间复杂度时核心是找“基本操作”是什么以及它执行的次数。比如单层循环遍历n个元素是O(n)双重循环是O(n²)每次循环规模减半是O(log n)。这里最容易翻车的是把log n阶误判成O(1)或O(n)关键看循环变量是乘以2还是加1。提示PDF里把算法设计要求归纳为正确性、可读性、健壮性、高效性四条。考试简答题喜欢问“什么是健壮性”标准答法是当输入数据非法时算法也能做出适当处理而不产生莫名输出或崩溃。2.4 空间复杂度不只是数变量个数空间复杂度S(n) O(f(n))n表示问题规模。PDF里给出了两个评价角度数据占用的存储空间和算法运行所需的附加存储空间。有些算法原地工作只需要常数个额外变量就是O(1)空间有些算法需要开一个和输入规模相同的辅助数组就是O(n)空间。递归算法的空间复杂度尤其要注意——每次递归调用都会在栈上分配空间递归深度就是空间复杂度的量级。很多同学把时间复杂度和空间复杂度分开记但实际设计算法时两者经常要权衡比如用空间换时间典型的就是后面线性表章节的合并操作如果不开辅助空间就要反复移动元素。3. 顺序表实现类型定义、插入删除代码与下标边界3.1 顺序表类型定义与地址连续性顺序表是线性表顺序存储的具体实现PDF里给出的类型定义如下#define Max 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; /* 存储空间基址 */ int length; /* 当前表长 */ int listsize; /* 当前分配的存储容量 */ } sqlist;这段定义里ElemType是数据元素类型的占位符实际使用时可以typedef成int、char或者一个结构体。elem指向一块连续内存的首地址length记录当前有多少个有效元素listsize记录总共分配了多少容量。三个字段各司其职listsize和length的区别是考试常考的填空length是实际用了多少listsize是可以装多少。引用顺序表元素时有个关键习惯第i个元素对应L.elem[i-1]表长是L.length最后一个元素是L.elem[L.length-1]。数组下标从0开始但线性表位序从1开始这个错位是初学阶段最典型的翻车点。地址连续性带来的好处是随机存取读取任意位置元素的时间复杂度是O(1)这是链表做不到的代价是插入和删除要移动元素平均复杂度O(n)。3.2 插入操作后移、置入、表长加一顺序表插入的完整代码我按PDF伪代码整理成可运行的C版本void Insert_sq(sqlist *L, int i, ElemType e) { int j; if (L-length Max - 1) { printf(表满\n); return; } if (i 1 || i L-length 1) { printf(i不合法\n); return; } for (j L-length; j i; j--) { L-elem[j 1] L-elem[j]; /* 从最后一个元素开始依次后移 */ } L-elem[i] e; /* 新元素放入第i个位置 */ L-length; /* 表长加1 */ }插入逻辑分三步先判断表是否满、i是否合法再从表尾往前把元素逐个后移一位最后把e放入第i个位置并更新length。注意后移必须从最后一个元素开始如果从前往后移后面的元素会被覆盖掉。i的合法性判断是i 1 i length 1因为允许插入到表尾后面也就是第length1个位置但i不能小于1也不能大于length1否则会出现空洞或者越界。插入的平均移动次数是n/2时间复杂度O(n)。推导方式是等概率情况下在0到n这n1个可能插入位置中移动次数分别是n, n-1, ..., 0求平均值就是n/2。考试常问“在长度为n的顺序表中插入一个元素的平均移动次数”——答案是n/2不是(n1)/2看清楚题目说的是插入还是删除。3.3 删除操作前移、表长减一删除代码同样按PDF整理void Delete_sq(sqlist *L, int i) { int j; if (i 1 || i L-length) { printf(不存在第%d个元素\n, i); return; } for (j i 1; j L-length; j) { L-elem[j - 1] L-elem[j]; /* 从删除位置的下一个开始依次前移 */ } --L-length; /* 表长减1 */ }删除和插入对称但有两个不同合法性判断变成i 1 i length因为删除不存在的元素没意义元素移动方向是前移从删除位置的下一个元素开始逐个往前挪一位。平均移动次数是(n-1)/2时间复杂度同样是O(n)。注意删除操作是否需要把原来最后一个位置的数据清零不需要。只要length减1最后一个位置的元素就不再属于这个表下次插入时会被覆盖。这个“逻辑删除”思想和链表的free操作不同顺序表不需要释放空间。顺序表小结可以提炼成一张对比表操作时间复杂度特点随机读取O(1)地址连续直接计算位置插入O(n)平均移动n/2个元素删除O(n)平均移动(n-1)/2个元素按值查找O(n)需要逐个比较4. 单链表实现结点定义、指针操作与有序表合并4.1 单链表结点定义与指针引用单链表用一组任意的存储单元存放线性表元素这些存储单元在物理上可以不连续靠指针建立逻辑联系。每个结点只有一个指针域指向后继结点所以叫单链表。PDF里给出的类型定义typedef struct Lnode { ElemType data; /* 数据域 */ struct Lnode *next; /* 指针域指向后继结点 */ } Lnode, *Linklist;Lnode和Linklist实际上是同一个类型一个是结构体类型名一个是指向该结构体的指针类型。定义变量时Linklist L就声明了一个头指针。引用结点时设p指向第i个结点p-data是第i个结点的数据p-next是指向第i1个结点的指针p-next-data是第i1个结点的数据。这套引用关系是链表的“九九乘法表”不熟练的话后面插入删除全乱套。链表里还有几个术语要分清头指针指向链表第一个结点标志整个链表头结点是链表第一个结点之前的哨兵结点它的数据域可以不存东西作用是统一空表和非空表的操作逻辑首结点是第一个真正存数据的结点尾结点的指针域是NULL。带头结点的链表在插入和删除时不需要单独处理“在第一个位置插入”和“删除第一个结点”的边界情况所以考研和工程实现都推荐带头结点版本。4.2 查找与插入指针修改的先后顺序单链表读取第i个元素的算法ElemType GetElem_L(Linklist L, int i) { int j 1; Linklist p L-next; while (p j i) { p p-next; j; } if (!p || j i) { printf(该结点不存在\n); return ERROR; } return p-data; }注意循环条件是p j ip为空说明已经遍历到链表尾部还没找到第i个元素j大于i说明i不合法比如i为0。和顺序表O(1)的随机读取不同单链表查找第i个元素必须从头开始数等概率下平均时间复杂度O(n)。这个差距是线性表两种实现方式最本质的性能差异。插入操作的完整代码void Insert_L(Linklist L, int i, ElemType e) { int j 0; Linklist p L, s; while (p j i - 1) { /* 找到第i-1个结点 */ p p-next; j; } if (!p || j i - 1) { printf(该结点不存在\n); return; } s (Linklist)malloc(sizeof(Lnode)); s-data e; s-next p-next; /* 新结点先指向原第i个结点 */ p-next s; /* 第i-1个结点再指向新结点 */ }核心是最后两行指针操作先后顺序绝不能反先让s指向p的后继再让p指向s。如果反过来先把p的next改成s那原来第i个结点就丢了s-next指向的是已经被覆盖的旧值。生成新结点用malloc动态分配这个操作在顺序表里不存在。4.3 删除操作与有序表合并删除第i个结点void Delete_L(Linklist L, int i, ElemType *e) { int j 0; Linklist p L, q; while (p-next j i - 1) { /* 找到第i-1个结点 */ p p-next; j; } if (!p-next || j i - 1) { printf(第i个结点不存在\n); return; } q p-next; /* q指向待删除结点 */ p-next q-next; /* 跳过q */ *e q-data; free(q); /* 释放被删结点空间 */ }删除的关键是找到待删结点的前驱让前驱直接指向待删结点的后继然后free掉待删结点。注意这里要释放空间和顺序表删除的“逻辑删除”完全不同。查找前驱的循环条件是p-next j i - 1这里判断的是p-next不为空而不是p不为空因为我们要保证p-next是存在的结点。两个有序链表合并PDF里的代码整理后void Merge_L(Linklist La, Linklist Lb, Linklist *Lc) { Linklist pa, pb, pc; pa La-next; pb Lb-next; pc *Lc; while (pa pb) { if (pa-data pb-data) { pc-next pa; pc pa; pa pa-next; } else { pc-next pb; pc pb; pb pb-next; } } pc-next pa ? pa : pb; /* 把剩余结点一次性接到尾部 */ free(Lb); }合并的思路是用pa和pb分别遍历La和Lb每次取较小的结点接到结果链表的尾部一个表遍历完就把另一个表的剩余部分整个接上。这里有个细节pc pa之后pc指向的是刚接上的结点下次再接入新结点时直接操作pc-next即可。注意算法复杂度是O(n)n为两个链表长度之和。4.4 循环链表与双向链表的扩展循环链表和单链表的区别只有一个尾结点的next不指向NULL而是指向头结点所以从任意一个结点出发都能走回起点。判断是不是表尾条件是p-next L而不是p NULL。这个改动让某些操作变简单了比如合并两个循环链表不用遍历到表尾直接用尾指针操作即可但遍历时要小心循环条件否则死循环。双向链表的结点有两个指针域typedef struct DulNode { ElemType data; struct DulNode *prior; /* 指向前驱 */ struct DulNode *next; /* 指向后继 */ } DulNode;单链表的缺点是查找前驱必须从头遍历双向链表用prior和next两个指针解决了这个问题。插入和删除时要注意同时修改两个方向的指针操作步骤比单链表更多也更容易出错。考试里常考双向链表插入的指针修改顺序核心原则还是那句话先改新结点的两个指针再改它相邻结点的指针。5. 避坑清单线性表实现中五个一踩一个准的错误5.1 位序和数组下标混淆导致越界现象写顺序表插入删除代码时明明逻辑没问题一运行就数组越界或者插入到了错误的位置。排查发现是把第i个元素写成了L.elem[i]实际应该写L.elem[i-1]。原因线性表的位序从1开始C语言数组下标从0开始。第1个元素在elem[0]第i个元素在elem[i-1]。很多人推导公式LOC(ai)LOC(a1)(i-1)*L时用的是数学语言一到写代码就忘了把位序减一。解决在所有涉及“第i个元素”的代码里统一用注释标注位序和下标的关系。我自己的习惯是先在纸面上写出i1、ilength、ilength1三个边界分别算一遍对应下标再落到代码。插入时的合法范围是1到length1删除是1到length这两个边界的细节也最容易在这个位置出错。5.2 原PDF有两处代码笔误直接照抄会编译失败现象照着PDF抄单链表删除算法变量q的类型是结点指针但代码里写q p-data编译直接报错合并算法里pcpa papa-next;中间缺个分号语法错误。原因这是典型的讲义排版/OCR问题。删除算法里q应该是待删除结点的指针正确写法是q p-next用p-data去初始化一个指针变量类型都不匹配合并算法的语句缺少分号明显是录入时漏了。解决抄代码前先看类型。q声明为Linklist左值是地址右值就必须是地址。遇到指针变量的赋值优先怀疑是不是把data和next写混了。我拿到这类PDF资源后会先把所有代码在编译器里过一遍报错的地方对照算法逻辑手工修正而不是盲目信任印刷内容。5.3 合并两个有序链表的复杂度结论存疑现象背了PDF里“合并算法平均时间复杂度O(nlogn)”做题时选O(nlogn)结果答案是错的。原因merge操作对每个结点最多访问一次两个有序链表合并且不重复扫描已处理结点复杂度应该是O(n)n是两表长度之和。PDF这里写的O(nlogn)很可能把归并排序的复杂度错误迁移到了这么单一步操作上。解决分析复杂度时回到基本操作次数。合并过程里while循环每执行一次接走一个结点每个结点被处理一次就结束所以总操作次数约等于两表结点数之和。凡是复杂度结论和直观不符的一定要亲手数一遍。5.4 单链表插入时指针修改顺序反了现象插入后链表断成两截或者新结点数据丢失原第i个结点找不到了。检查发现p-next s写在了s-next p-next前面。原因p-next原本指向第i个结点先改p-next后原第i个结点和链表断开了s-next已经取不到正确的后继。指针操作的核心是“在断开连接前先记录后继”。解决记住两句话先让新结点指向后面再让前面指向新结点。双向链表同理先改新结点的prior和next再改相邻结点的指针。我在写这类代码时会在纸上画插入前后的指针状态图双线下划线标记会变的指针就不会搞反了。5.5 判断“表满”和“i不合法”的顺序影响健壮性现象顺序表插入时表满了但i不合法程序只提示表满不提示i的问题或者反过来用户输入的i超出范围却优先执行了别的分支。原因if-else结构只执行第一个满足条件的分支判断顺序决定了错误提示的优先级。表满和i不合法是两个独立错误理应先判断最根本的合法性。解决插入操作先检查i是否在[1, length1]区间再检查存储空间是否够用因为i都不合法的话后续移动元素寸步难行。删除操作同理先检查i是否在[1, length]再考虑表是否为空。这个顺序可以统一写成先参数合法性再容量/空表判断最后才执行操作。6. 一个验证习惯用边界条件和小规模数据跑通每个算法读这份PDF最有效的收获不是背下那些定义而是把每段代码都当作可以运行的程序去验证。我拿到有代码的讲义之后有一个固定的验收流程把每个算法抄进编译器构造三个用例——空表、单元素表、正常长度表分别跑一遍。空表用例暴露的是边界判断错误单元素表暴露的是指针初始化问题正常长度表暴露的是算法逻辑漏洞。顺序表插入我会特意试i1和ilength1这两个边界看元素是否正确落在elem[0]和elem[length]单链表删除我会试删除首结点和尾结点看头指针和尾结点的next是否处理正确。复杂度计算也有一个快速验证法把代码里的循环数出来。单层循环遍历n个元素是O(n)嵌套两层是O(n²)每轮规模减半是O(log n)。合并链表那道题我会数一遍while循环对每个结点的处理次数发现每个结点只被处理一次结论自然就是O(n)。复杂度结论不直观的时候先数循环再背公式就不会被讲义里的笔误带偏。从那以后我每次拿到新的数据结构讲义或代码包都强制走一遍这套流程先编译排查语法错误再跑边界用例验证逻辑最后回头对着复杂度定义核对结论。这份PDF虽然有几处笔误但把绪论和线性表的骨架搭得非常完整修正之后就是一套可以直接拿来复习和复试上机的笔记。希望帮到你。本文还有配套的精品资源点击获取