笔记首发于：lengyueling.cnPDF版本附在 lengyueling.cn 对应文章结尾，欢迎下载访问交流绪论数据结构在学什么如何用程序代码把现实世界的问题信息化如何用计算机高效地处理这些信息从而创造价值数据结构的基本概念什么是数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。现代计算机处理的数据：现代计算机——经常处理非数值型问题对于非数值型的问题：我们关心每个个体的具体信息我们还关心个体之间的关系数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。数据项：一个数据元素可由若干

知识回顾    通过前文，我们了解到线性表是具有相同数据类型的有限个数据元素序列；并且，线性表只是一种逻辑结构，其不同存储形式所展现出的也略有不同，那么今天我们来了解一下线性表的顺序存储——顺序表。顺序表的定义    顺序表指的是将逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。所以顺序表的特点就是其逻辑顺序与其物理顺序相同。    我们不妨将设线性表L存储的起始位置为LOC（A），那么其顺序表L相对应的顺序存储如图所示：（这里sizeof是计算括号内数据元素所占用存储空间的大小）    通过图我们也不难观察出其顺序表的特点。这里每个数据元素的存储

24考研王道计算机408网盘链接：https://pan.baidu.com/s/152XLyH64TlcLXwmU-zlAsQ?pwd=r7zf 提取码：r7zf 接下来，这部分是我对于四零八考试中红黑树考察方向的一个预测。希望大家对这部分内容能够有自己的大胆想法。红黑树暂时还没有考过，但是它所有可能考察的基本上就是这五个部分。其中代码。不可能考察。基础考点是最重要的，也就是定义以及与平衡。二叉树的比较。想考110分或以上的同学，这部分一定要认真复习。而如果老师想把难度增加一点，可以考察一个不平衡状态是如何旋转得到一个平衡状态的。如果你想考120分，需要复习一下这个部分。而如果老师想考的更难

知识回顾    到这里我们已经了解到线性表是具有相同数据类型的有限个数据元素序列，而线性表的顺序存储也就是顺序表，顺序表的存储形式十分直观，我们在实现时使用数组进行实现，但顺序表在插入或者删除元素时需要移动大量元素，那么怎么样才能在插入删除元素时不需要大费周章的移动如此之多的元素呢？为了解决这个问题，今天我们就来继续了解一下线性表的链式存储——链表。单链表定义    线性表的链式存储又叫单链表，既然是属于线性表的一种存储方式，那么其应该满足线性表的特征（具有相同数据类型的有限个数据元素序列）。        那么什么是链式存储呢？我们不难想象，就像链条一样，我们存在很多个相同的结点，这些结点之

考点剖析        线性表是算法题命题的重点，该类题目实现相对容易且代码量不高，但需要最优的性能（也就是其时间复杂度以及空间复杂度最优），这样才可以获得满分。所以在考研复习中，我们需要掌握线性表的基本操作，在平时多进行代码练习。当然在考场上，我们并不一定要求代码具有实际的可执行性，但我们需要去清晰的表达出算法的思路步骤，且算法题目只允许使用C/C++语言进行实现。线性表知识点    关于线性表这章内容其实并不多，我们将其分为两大部分：顺序存储（也就是我们常说的顺序表）和链式存储（链表），其中对于链表部分我们需要掌握其中的单链表、双链表、循环链表、静态链表等部分链表。    关于线性表的内容

错误现象：Usingdefaulttag:latestErrorresponsefromdaemon:errorparsingHTTP408responsebody:invalidcharacter'408RequestTime-out\nYourbrowserdidn'tsendacompleterequestintime.\n\n\n"解决办法：此时需要修改当前网卡的MTU为900#临时修改：ifconfigeth0mtu900#永久修改(尝试设置，但是失败了...)：#vi/etc/network/interfaces#【在最后增加内容:mtu900】...【然后重启网卡】/etc/in

该套代码，大学期间跟着网课一遍一遍打下来的，408大概就这些了，别的杂七杂八其实还有很多，遗憾的是，一直没有整理和归纳。导致一遍遍地学一遍遍地忘记。大四就快毕业了，研也考了。这里做个整理，算是给408一个小小的胶带吧。后续如果有缺漏还会弥补。目录：线性表链表栈队列链栈链队二叉树线索二叉树堆堆排序并查集（quickfind、quickunion、w-qickunion、路径压缩）AVL树红黑树B树拓扑排序排序（插入、冒泡、归并、选择、快排、快排优化）希尔排序dijsktra算法-单源最短路kruskal算法-最小生成树Prim算法-最小生成树字符串匹配算法汇总（朴素、哈希匹配、kmp、kmp优化

前面几篇文章介绍的是排序算法，现在让我们开始排序算法的专项练习。目录判断题选择题填空题1.插入排序2.另类选择排序3.冒泡排序4.快速查找第K大元判断题1.希尔排序是稳定的算法。（错）解析：稳定性是指如果两个元素在排序前后的相对顺序保持不变，那么这个排序算法就是稳定的。对于具有相同关键字的元素，排序后它们的相对位置应该保持不变。2.仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。（对）3.对N个记录进行归并排序，归并趟数的数量级是O(NlogN)。（错）答案：O(logN)4.对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。（错）解析：

目录1.解题思路2.生产者-消费者3.理发师4.读者-写者问题5.哲学家进餐6.读者-写者（写优先）7.读者-写者（读写公平）1.解题思路1.确定函数的个数：梳理题目中有几个进程，一个进程对应一个函数（根据动作是否一致区分是否为统一进程）2.确定函数的动作：①动作是什么：在函数内部，用中文描述动作（允许用中文的伪代码形式答题）②动作的次数：只做一次（不加while）还是重复进行（while循环）3.确定函数是否在每个动作之前需要进行P操作：如果需要进行P操作，则一定有与之对应的V操作；需要思考这个V操作应该被放在哪进行①消耗资源型的P操作：题目一般会显性给出，例如每次动作需要消耗一个缓冲区空间

一.图的相关定义（1）图的定义：    图由顶点集V和边集E组成，记为G=（V，E），使用V（G）表示所有顶点的集合（不能为空）；使用E（G）表示各个顶点之间的关系（可以为空）。若用V={v1,v2,v3,....,vn}来表示图，则使用|V|表示图中顶点的个数，使用E={（vi，vj）|vi∈V，vj∈V}，用|E|表示图中边的条数。（2）有向图的定义：        若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为,其中v、w均为顶点，v成为弧尾，w称为弧头（分不清的话可以记想象一下拉弓的场景，如下图，顶点4的左半边可以看作弓，右边箭头可以想象成箭矢，头是我们，做