- 博客(50)
- 收藏
- 关注
RSS订阅原创 （数据结构）两个有序表合并的最大比较次数：m+n-1
分析过程：设置两个指针分别指向两个表（A,B）当前要比较的结点；不妨设：p为A的工作指针，q为B的工作指针初始时，两个指针都指向各自的首结点。开始比较：p和q比（A_1和B_1比）,假设A_1小，则p后移一位指向A_2;再让A_2和B_1比，此时B_1小，q后移指向B_2；此时A_2和B_2比，此时A_2小，p后移指向A_3；此时A_3和B_2比，此时B_2小，q后移指向B_3;……发现，q和p两个工作指针，依次后移，你走一个，我走一个，两个表全部都走一遍是最坏的情况！都走一遍那不是
2021-12-12 22:03:35
5545
2
原创 考研算法（线性表）
首先两个基础操作，查找和插入//链表按位查找Node GetElem(LinkList L,int i){ Node *p=L; int j=0; while(p&&j<i){ j++; p=p->next; } return p;}void Insert(LinkList &L,int i,ElemType e){//在某一点插入e Node *p=GetElem(L,i); Node *s=(Node*)malloc(sizeof(
2021-11-26 22:15:08
776
1
原创 算法笔记（树）
树的算法1.基于后序遍历1.求i,j最近的公共祖先结点（顺序存储）2.树的后序遍历（非递归算法）3.求i,j最近的公共祖先结点（链式存储）13.求值为x的结点的所有祖先2.基于层次遍历4.求树的高度（非递归+递归），求某节点所在层次也用这个非递归就行5.求树的宽度6.判断是否是完全二叉树3.基于递归构建二叉链表7.给先序和中序（数组），构建二叉链表8.给满二叉树的先序，求后序4.前、中、后根遍历都可的算法9.求双分支节点个数，叶子节点个数，单分支节点个数10.交换所有结点的左右
2021-11-21 21:50:46
1052
原创 考研算法笔记（排序）
考纲（只考虑内部排序）1插入排序（直插(稳)，希尔）2交换排序（冒泡(稳)，快排）3选择排序（简选，堆排）4归并排序（稳）5基数排序（稳）算法笔记1.插入排序1.1.直接插入排序（稳定）适合顺序表，也可适用于链表，所以两个都需实现（用折半查找优化时，只能用顺序表！！！）1.查找插入位置（外部大循环）//第一个元素总是有序的，从第二个开始比较2.后移（内部小循环）void InsertSort(ElemType A[],int n){ //顺序表实现直接插入排序//1.第一步找
2021-11-14 14:55:36
1470
原创 考研数据结构_图
考纲1.图的基本概念（什么是图，图的术语）2.图的存储和基本操作（邻接矩阵，邻接表，十字链表（有向图），临界多重表（无向图））3.图的遍历（深搜 Depth First Search–DFS， 广搜 Breadt First Search–BFS）4.图的应用（最小生成树，最短路径，拓扑排序–AOV图，求关键路径–AOE）大体的知识点都概括在这了，以下根据1.是什么（知识点定义），2.为什么（这是知识点为了解决什么问题），3.怎么用（知识点是怎么运作的）来展开知识点并且用伪代码实
2021-11-08 20:02:35
1645
1
原创 ＜?xml version=“1.0“ encoding=“UTF-8“?＞报错，是啥原因？
<?xml version="1.0" encoding="UTF-8"?>报错，是啥原因？代码是没错的，就是eclipse不识别，或者说解析错误。解决方法：全选代码剪切，再粘贴回去就解决了。或者手敲也行啊，你不嫌累的话
2021-06-04 11:10:05
15270
原创 编译原理中的短语、直接短语、句柄，怎么找呀！个人理解，看完细品
首先要知道，他们仨是有包含关系的，（因为条件限制越来越高）句柄范围最小， 句柄 < 直接短语 < 短语一、先找句柄！分析一波先，这是课本上给予的偏理解性的定义，（1）首先要找到最左边的子树（2）这个子树有多少代（层），（缩小范围->） 只看最下面的两代，下面两代作为要寻找的子树。（3）这棵子树的叶子的从左到右排列就是句柄。怎么找句柄呢？上图实操！这是一个句型的语法分析树：1.找到最左边的子树 ，如图2.这个子树正好就两层，它本身就作为要找的目标子树句柄则为目
2021-05-15 18:19:14
7941
2
转载 安装npm报错，安装淘宝镜像cnpm时出现问题及解决方案
https://www.jianshu.com/p/3fd7d90db01a感谢大佬，看了直接秒解决！！！
2020-10-29 23:50:38
8080
2
原创 贪心算法
什么是贪心算法？在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。贪心算法不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解贪心算法的理论基础这种策略是一种很简洁的方法，对许多问题它能产生整体最优解，但不能保证总是有效，因为它不是对所有问题都能得到整体最优解。利用...
2020-05-03 23:20:23
388
原创 算法笔记动态规划
一、动态规划的基本思想1、动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。2、基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算...
2020-05-03 13:32:45
261
原创 分治算法——半数集问题
半数集问题什么是半数集？给定一个自然数n，在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半。举个例子：若n=6，求6的半数集。{6，16，26，126，36，136}6半数集肯定包含他本身；1不大于的一半 所以16；2不大于6的一半，26；1又不大于2，所以126；3不大于6的一半，36；1又不大于3，所以136；解题思路由图可知，12的半数集依赖于1至6的半数...
2020-04-29 13:52:38
4670
原创 选择问题——找出第k小的数
找出第k小的数首先来说这个问题很简单，直接先把集合排好序，然后输出第k个即可。但是时间复杂度高，不妨写出一个算法来解决这个问题。首先了解快速排序首先选第一个数作为分界，将比它小的数存储在它的左边，比它大的数据存储在他的右边，它在两个子集之间。这样左右两个子集就是原问题分解后的独立子问题——分治算法。（再用相同的方法，继续来对这两个子问题进行同样的操作，直到每个子集只有一个数，就完成了全部...
2020-04-27 16:33:12
946
原创 分治策略
分治策略简介分治策略是对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。基本步骤1、分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；2、解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；...
2020-04-22 14:12:08
205
原创 算法递归——整数划分问题
整数划分问题把一个正整数n表示成一系列正整数之和：n=n1+n2+…+nk; ( 其中n1>=n2>=n3>=…>=nk>=1;)示例若要求正整数6的划分，以下是他的划分：算法分析来设一个函数 f(n,m)，n代表所要划分的数，m代表划分中最大的加数。例如 f(6,6)即为划分问题的答案，f(6,4)是4+2，4+1+1,…,1+1+1+1+1+1。...
2020-04-16 14:27:35
483
原创 算法递归——集合的全排列问题
集合全排列问题设集合 R={ r1,r2,r3 … r n}，显然全排列的数目为 n！。那么如何显示集合的所有全排列呢？可以用递归的方式实现。解题思路如果集合有n个元素，那么就可以看作 n-1个元素全排列之后再加上 剩下的那个元素，因为是全排列，所以每一个元素都会剩下一次。（例如：R={1,2,3}的全排列。若 1 剩下，则 {2，3} 先进行排列，再与1结合，结果是 1 23，1 ...
2020-04-16 12:47:33
2110
原创 递推与递归-Fibonacci数列
Fibonacci数列有许多以Fibonacci数列为原型的题目，比如：楼梯有n个台阶，上楼可以一步上一阶，也可以一步上两阶。一共有多少种上楼的方法？尽管增加了环境渲染，题目的本质还是Fibonacci数列，找出规律即可。关于Fibonacci数列的解题可以用递推或者递归两种方法技巧；1.递推递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值...
2020-04-15 15:47:36
242
原创 快速排序（交换）
基本思想首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。关键问题⑴如何选择轴值？⑵如何实现分割（称一次划分）？⑶如何处理分割得到的两个待排序子序列？⑷如何判别快速排序的结束？（1）解决方法：轴值可以取记录中的任意值，一般取...
2019-12-25 21:24:12
434
原创 冒泡排序
基本思想两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。关键问题⑴ 在一趟起泡排序中，若有多个记录位于最终位置，应如何记载？⑵ 如何确定起泡排序的范围，使得已经位于最终位置的记录不参与下一趟排序？⑶ 如何判别起泡排序的结束？（1）解决方法：设变量exchange记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，且从此...
2019-12-25 21:03:09
154
原创 希尔排序
基本思想1、将整个待排序记录分割成若干个子序列，2、在子序列内分别进行直接插入排序，3、待整个序列中的记录基本有序时，对全体记录进行直接插入排序。关键问题1、分割待排序记录的目的是：1、减少待排序记录数目。2、使序列向基本有序发展。2、如何分割? 子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。（1）分割解决方法：将相隔某个“增量”的记录组成一个子...
2019-12-25 20:35:52
111
原创 直接插入排序
基本思想在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。直接插入排序算法是一种稳定的排序算法。需要解决的问题？（1）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置?（1）如何构造初始的有序序列？解决方法：将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。算法描述：for (i=2; i<=n; i++...
2019-12-23 22:05:37
177
原创 平衡二叉树
定义平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树：⑴ 根结点的左子树和右子树的深度最多相差1;⑵ 根结点的左子树和右子树也都是平衡二叉树。平衡因子： 结点的平衡因子是该结点的左子树的深度与右子树的深度之差。结点的平衡因子＝HL-HR在平衡树中，结点的平衡因子可以是1，0，-1。最小不平衡子树： 在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子的绝对值...
2019-12-16 20:17:08
86
原创 二叉排序树
定义二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：⑴若它的左子树不空，则左子树上所有结点的值均小于根结点的值；⑵若它的右子树不空，则右子树上所有结点的值均大于根结点的值；⑶ 它的左右子树也都是二叉排序树。中序遍历二叉排序树可以得到一个按关键码有序的序列二叉排序树的插入分析：若二叉排序树为空树，则新插入的结点为新的根结点；否则，如果插入的值比根节点值...
2019-12-16 19:52:13
282
原创 折半查找（二分查找）
1.适用条件线性表中的记录必须按关键码有序；必须采用顺序存储。2.折半查找（二分查找）具体实现基本思想：在有序的线性表中，取中间位置的数作为比较对象。若给定值与中间记录的值相等，则查找成功；若给定值小于中间记录的值，则在中间记录的左边继续查找；若给定值大于中间记录的值，则在中间记录的右边继续查找；不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。int Searc...
2019-12-16 19:27:00
1178
原创 顺序查找
1.顺序查找优缺点优点：算法简单而且使用面广。对表中记录的存储结构没有任何要求，顺序存储和链式存储均可；对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。缺点：平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。2.顺序查找具体实现基本思想：用线性表来存储数据，从线性表的一端到另一端进行逐个比较，若找到要求值，查找成功，给出该记录在表中的位置。若始终无相等的...
2019-12-16 18:57:55
2920
原创 关键路径和AOE网
AOE网的定义在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。AOE网的性质⑴ 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；⑵ 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。A...
2019-12-09 20:24:39
656
原创 图的最短路径（Dijkstra方法和Floyed方法）
什么是最短路径？1、在非网图中，两顶点之间经过顶点最少的路径，就是最短路径。2、在网图中，两点之间经过的权值之和最小的路经。最短路径问题的解决方法Dijkstra方法（单源点到其他顶点的最短路径）Floyed方法 （任意两点之间的最短路径）1.Dijkstra方法算法思想：1.设置一个集合S存放已经找到最短路径的顶点，初始值为单源点（起始点）。2.以后每求得一条最短路径v, …...
2019-12-02 19:53:58
415
原创 最小生成树（Prim算法和Kruskal算法）
什么是最小生成树？生成树的代价： 设G=（V，E）是一个无向连通网，生成树上各边的权值之和叫做该生成树的代价。最小生成树： 图G的所有生成树中，代价最小的生成树，叫做最小生成树。构造最小生成树的算法1.Prim算法（加点法）2.Kruskal算法（加边法）1.Prim算法基本思想：1、创建一个顶点集合U，和一个边集合TE。2、若从u开始，则将u放入U中，V总顶点集合则少一个u，...
2019-12-01 20:56:40
698
原创 图的遍历——深度和广度
深度优先遍历深度优先遍历就是从一个顶点开始，顺着一条边，依次访问连接着的顶点。直到顶点全部访问完毕结束。操作思路：1、用一个一维数组表示该点是否被访问（存储0和1，0代表没访问，1代表访问完了）。2、利用递归的方法，输出该节点数据，修改一维数组（0变成1），for循环，进行下一个节点，一直到全部访问完成（测试有没有访问的数组里都是1）；上代码这是用邻接矩阵（静态存储）存的图的深度遍历...
2019-12-01 19:26:13
176
原创 图的存储方法——邻接表（动态存储）
基本思想：1.每一个顶点都可以引出一条单链表。（对于每一个顶点vi，将所有邻接于vi的顶点连接成为一个单链表，称为顶点vi的边表。）用来存储边的2.所有边表的头指针和存储顶点信息的一维数组，构成了顶点表两种节点结构vertex：数据域，储存顶点信息。firstedge：指针域，指向下一个邻接的顶点。adjvex：邻接点域，边的终点再顶点表中的下标。next：指针域，边表的下一个节点...
2019-12-01 14:47:48
342
原创 图的存储方法——邻接矩阵
基本思想：图由顶点和边构成，则需要分别存储顶点和边，边又依附于点，还需存储点与边的逻辑关系。用一个一维数组来存储图中的所有顶点。再用一个二维数组来存储图的邻接矩阵，（邻接矩阵行列分别为第1个到第n个顶点），若两个顶点有边，则邻接矩阵 该行列 的值为1，无边则为0；具体代码体现：const int maxsize=10;template<class T>class Gra...
2019-11-21 17:58:52
506
原创 图的定义和基本术语
1、图的定义1.1、图的结构是由顶点和边构成。规范定义为 图是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为： G =（ V , E ）V是顶点集合，E是边的集合。（注意：线性表中无元素，则为空表，树中无节点，则为空树，但在图中，顶点数不能为0，边数可以为0。）1.2、有向边和无向边、有向图与无向图两个顶点之间的边的有无方向，判定它为有向无向，任意两个顶点的边是有向边的图为...
2019-11-21 17:28:02
2494
原创 纯CSS写出下拉菜单
网页的下拉菜单是，当鼠标移入到指定元素上时i，会出现下拉菜单。dropdown 是 dropdown-content的父元素。 鼠标移动到我这！ 我会显示出来 www.runoob.com 指定样式：.dropdown {position: relative;display: inline-block;}给鼠标移入的元...
2019-11-21 16:52:32
125
原创 AJAX读取Json文件
Ajax是对接后端的工具，向服务器发送请求并且接收响应。使用ajax读取文件需要以下基础的几步：1.获取需要添加事件的节点（或者叫元素），给予onclik或者其他事件。2.创建一个XMLHttpRequest对象。3.调用所创建对象的open方法，选定open方法的method和url。4.调用对象的send方法。5.为对象添加onreadystatechange响应函数。6.判断相...
2019-11-21 16:51:01
688
原创 树和二叉树
主要内容1、树的逻辑结构和存储结构2、二叉树的逻辑结构和存储结构3、树和二叉树的转换4、哈夫曼树1.1、树的逻辑结构1.树的定义：树是n（n>=0）个节点的有限集合。当n=0时，则为空树。2.树的基本术语：度： 节点的度是拥有子树的个数。树的度是节点度的最大值。叶子节点： 度为0的节点。也称终端节点。分支节点： 度不为0；也称非终端节点。有序树、无序树： 一棵树的各子...
2019-11-14 19:15:28
82
原创 数组与字符串
1、数组的定义数组是由一组类型相同的数据元素构成的有序集合，每个元素受n（n>=1）个线性关系的约束，并称该数组为n维数组。2、数组的特点1.元素本身可以具有某种结构描述与同一数据类型。2.数组是一个具有固定格式和数量的数据集合。3、数组的基本操作1.存取：给定一组下标，独处对应的数组元素；2。修改，给定一组下表，存储或修改与其相对应的数组元素。存取和修改操作本质上值对应一种...
2019-11-03 14:29:31
191
原创 栈与队列
栈与队列是特殊的线性表，它们属于线性表，与普通线性表的区别是，站和队列规定了插入和删除的位置。1.栈1.逻辑结构：栈的插入和删除位置规定在表尾操作，允许删除和插入的一端叫做栈顶，另一端叫做栈底。元素先入后出。2.存储结构：顺序存储const int maxsize=100;template<class T>class SeqStack{private: T da...
2019-10-27 16:24:43
195
原创 数据结构之线性表
线性表的主要内容线性表的逻辑结构线性表的顺序结构线性表的链式存储顺序表和单链表的比较线性表的定义零个或多个具有相同类型的数据元素的有限序列。元素的个数就是表的长度。长度为0就是空表。顺序存储结构及实现用一段连续的地址来存储数据。每个元素在存储空间的相邻关系和物理相邻关系相同，可通过下表实现随机访问。顺序存储通过一维数组实现它。const int maxsize=100;...
2019-09-29 12:50:36
84
原创 学懂模板
1.模板的概述模板事对具有相同特性的函数或类的再抽象，实现参数多态性（对象类型作为参数，使用时实例化，可以使一段代码适用于多类问题）。2.模板的分类1.函数模板2.类模板3.模板的实例化模板只有通过实例化，才能发挥他的作用，就像带参函数需要赋予实参才能运行一样，模板的参数就是对象类型，赋予一个模板以具体的类型就叫做实例化。4.模板的好处？1.当所需要的函数或者类的类型不确定时，只能...
2019-09-28 20:30:43
74
原创 系统开发入门心得
学了面向对象的程序设计，我已经写了ATM，图书管理系统。初次写系统，代码思路紊乱，写得一团糟，但是经过老师的讲解，课本的介绍，同学的帮助后，我写的简易系统慢慢符合面向对象程序设计系统的模样，渐渐成了一个像样的系统。功能从不全到完备，代码从错误百出到零错零警告，这一夜夜的心酸只有自己知道，调程序的乐趣也只有自己明白。1、老师说写程序要有宏观思想，当写系统是也是这样，不能只着眼与一个功能，要放观全局...
2019-06-22 23:17:46
404
原创 C++学习总结
一、对象的初始化、复制和销毁1.1 对象的初始化对象的初始化需要构造函数来实现，初始化是在创建一个对象时赋予其一个初始值，C++有不同的初始化形式，要调用不同的构造函数。1）默认初始化定义对象时没有指定初值，对象默认初始化，调用类内默认构造函数。2）直接初始化初始值写在对象后的（）中，例如： X a（…），调用类内相对应的构造函数。3）拷贝初始化用等号“=”初始化一个对象时，执行拷...
2019-06-22 22:54:48
817
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人