克鲁斯卡尔算法(Kruskal)详解
应用场景-公交站问题
看一个应用场景和问题:
某城市新增 7 个站点 (A, B, C, D, E, F, G) ,现在需要修路把 7 个站点连通
各个站点的距离用边线表示 ( 权 ) ,比如 A – B 距离 12 公里
问:如何修路保证各个站点都能连通,并且总的修建公路总里程最短 ?
克鲁斯卡尔算法介绍
克鲁斯卡尔 (Kruskal) 算法,是用来求加权连通图的最小生成树的算法 。
基本思想 :按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路
具体做法 :首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止
克鲁斯卡尔算法图解说明
以城市公交站问题来图解说明 克鲁斯卡尔算法的原理和步骤:
在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到最小,则称其为连通网的最小生成树。
例如,对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。
克鲁斯卡尔算法图解
以上图G4为例,来对克鲁斯卡尔进行演示(假设,用数组R保存 ...
int p[4];int (*p)[4];和int *p[4];三种数组定义详解
初学C语言时,很难分清楚到底三者有何区别,尤其还涉及c语言的灵魂——C指针,下面,我将详细介绍一下三种定义方式,希望对正困惑的你有所帮助。
1.分析第一种方式——int p[4];
我相信接触过数组的,不管是任何所学的编程语言,这种定义应该最常见也最方便理解的吧。
1.1定义解释
int p[4];表示定义了一个整型数组,数组名为p(数组名表示该数组在内存存放的首地址,故p为数组的首地址),此数组有4个元素,并且每个元素也都是int类型,定义该数组会开辟sizeof(int) * 4个字节的连续存储空间。
1.2数组在内存中的存放形式:
2.分析第二种方式——int (*p)[4];
这种定义方式经常与二维数组联用
2.1解释定义
int (*p)[4];表示p是一个指针变量,指向一个存放4个整型元素的一维数组,且p+1(或p-1)是向前(或向后)移动数组长度个字节的大小。其中,指针变量指向一维数组的指针变量,指向二维数组中的某一行。
而第一种方式的p+1(或p-1)是向前(或向后)移动int个字节的大小。
2.2该方式在与二维数组的联用
设有如下二维数组:
int (*p)[4] ...
KMP算法详解
KMP 解法
KMP 算法是一个快速查找匹配串的算法,它的作用其实就是本题问题:如何快速在「原字符串」中找到「匹配字符串」。
在朴素解法中,不考虑剪枝的话复杂度是 O(m∗n) 的,而 KMP 算法的复杂度为 O(m+n)。
KMP 之所以能够在O(m+n) 复杂度内完成查找,是因为其能在「非完全匹配」的过程中提取到有效信息进行复用,以减少「重复匹配」的消耗。
你可能不太理解,没关系,我们可以通过举个例子来理解 KMP。
1. 匹配过程
在模拟 KMP 匹配过程之前,我们先建立两个概念:
前缀:对于字符串 abcxxxxefg,我们称 abc 属于 abcxxxxefg 的某个前缀。
后缀:对于字符串 abcxxxxefg,我们称 efg 属于 abcxxxxefg 的某个后缀。
然后我们假设原串为 abeababeabf,匹配串为 abeabf:
我们可以先看看如果不使用 KMP,会如何进行匹配(不使用 substring 函数的情况下)。
首先在「原串」和「匹配串」分别各自有一个指针指向当前匹配的位置。
首次匹配的「发起点」是第一个字符 a。显然,后面的 abeab 都是匹配的 ...
c++运算符优先级归纳
C++一共有 18个优先级,运算中按优先级进行性计算,当优先级相同时,根据结合性规则来决定。
结合性:
1.从左到右(L-R):操作数和操作符结合的顺序大部分是从左到右结合性的,例如()、单独的算术运算符
2.从右到左(R-L):最典型的是赋值运算符,当赋值符号与算术运算符结合后 ,整体也是R-L。另一个最常用的就是逻辑非运算符 “!”。
在使用的时候,如果不确定,或者运算符太多,就按照自己的思路用括号隔开。
因为在程序中,正确性>可读性>简洁性,万万不可本末倒置
优先级1
优先级2
平时常用的最高优先级操作符是从左向右结合的一批操作符,操作数和操作符结合的顺序是从左到右。包括:函数调用、数组下标、取成员、类型转换、后置运算符等。
优先级3
此优先级都是一元运算符(单目运算符),从右向做结合。
优先级4
类成员指针运算符
优先级5
算术运算符中的乘(*)、除(/)、取余(%)
优先级6
算术运算符中的加、减
优先级7
移位运算符
优先级8
比较运算符
优先级9
比较运算符
优先级10、11、12
按位运算符
优先级13、14
逻辑运算符
优先级15
...
指向常量的指针和常量指针
指向常量的指针
指向常量的指针,即 pointer to const,即指针指向的是一个常量,你应该把这个词(指向常量的指针)当做一个整体来理解,而不是分开。(当然也有翻译成指针常量的,但我并不喜欢这种翻译方式)
通常也将指针本身是一个常量称为顶层 const,将指针所指的对象是个常量称为底层 const
它的语法格式是 const 在 * 左边,这一点很重要,因为后面要讲的常量指针是 const 在 * 的右边。下面是它的基本语法格式
const double pi = 3.14; // pi 是一个常量const double *cptr = π // cptr 是一个指向常量的指针// 或者,它的另一种写法是交换一下 const 和 double 的位置顺序double const *cptr = π // cptr 是一个指向常量的指针
下面我们举一个例子来进行具体的讲解
#include <iostream>using namespace std;int main(){ const double pi = 3.14; ...
c++ switch case详解
当程序的一部分导致另一部分执行时,会发生分支。if-else if 语句允许程序分支到几个可能的路径之一,当这些测试之一成立时,它执行一系列测试(通常是关系)和分支。
switch 语句是一个类似的机制,但是它测试的是整数表达式的值,然后使用该值来确定要分支到哪一组语句,以下是 switch 语句的格式:
switch (IntegerExpression){ case ConstantExpression: //在这里放置一个或多个语句 case ConstantExpression: //在这里放置一个或多个语句 //case可被重复多次 default: //在这里放置一个或多个语句}
此类语句的第一行以单词 switch 开始,后面是括号内的整数表达式 Integer Expression。 这可以是以下两种之一:
任何一个整型数据类型的变量(包括 char)。
其值为任何整型数据类型的表达式。
在下一行是包含几个 case 语句的块的开头,每个 case 语句格式如下:
case Cons ...
一些学计算机可能会用到的网站
最近对原学院的学习氛围感到厌倦,想要称大一加权还不错的情况下转专业。在以前同学的帮助下,收集到了一些用于自学的比较好的网站
1.cpp参考手册:https://zh.cppreference.com
2.OI Wiki(偏向与信息学竞赛的一个网站,不过对于系统自学cpp也有很大的帮助):https://oiwiki.org/
3.CS自学指南(这个可以说比较硬核了):https://csdiy.wiki/
4.Leetcode(经典的刷题面试网站,曾经因为没有接触过容器和类对这个网站很反感,建议在学完容器和类之后去刷题):https://leetcode.cn/
5.Luogu(可以说是很经典的刷题网站了,主要面向NOIP和NOI,但是刷题还是不错的):https://www.luogu.com.cn/
留园现场课笔记
因为本来就是苏州人,暑假有时间可再次造访留园,所以这次没有去留园,听直播课讲解以后的一些心得体会。
园林的空间体验,不会一下看清空间是什么,在第一次空间体验中无法感受到空间的全貌。需要通过两次甚至三次的重复体验才能够感受到完整的空间。
在感受空间的过程中,设计者往往会给出一些线索,比如露出影子的树,去引导你的游览路线。墙上的窗形成的孔隙也是一种线索,通过孔隙将园林中的景观和空间相互联系,同时孔隙之间还会产生联系,在极小的空间内营造出极为丰富的空间体验。
z字型转折,廊道,在功能上毫无用处。但是,这种“无用”的转折可以营丰富且拥有深度的空间。有的转折会漏出两个孔洞,空洞之间会有一个对话的关系。园林有很多曲折的廊道,求曲而不求直,曲折的意义,通过一个转折漏出了空间空隙,并且在孔隙中形成了空间景观。
廊道与柱子构成了虚的空间划分,将廊道和转折所构成的景观分割成了对立空间,从而产生了一种距离感,景不是让你游的,而是让人远离景观去远观画的。同时,空间光线的巧妙安排使得景物一边有自然光线渗入,而人所在的廊道较暗,形成了景物在舞台上,人在观众席上的感觉,进而形成人与景的对话关系。
古木交柯,在空间 ...
对于中国古典园林,在阅读中国古典园林分析的基础上的一些个人见解与看法
中国古典园林的发展经历了漫长的时光。周、汉时期,古典园林主要是皇家苑囿,规模很大,但是属于圈地性质。秦汉时期出现过人工开池、堆山活动,但是造园的主旨、意趣依然很淡薄。到了魏晋南北朝时期,初步确立了再现自然山水的基本原则,把园林主要作为观赏艺术来对待。隋唐五代,由于文人直接参与造园活动,从而将造园艺术与诗画相联系,有助于在园林中创造出诗情画意的境界。宋代,对自然美的认识更加深刻,出现了山水画的理论著作,进一步推动园林的发展。
从园林的分布来看,造园活动的选址大多都在经济比较繁荣的地区或者是郊外安静的地区,这些地区都有山或者水或者二者兼有。文人工匠利用自然界的山水,在市井中营造一个小自然。
西方的古典园林设计受到一定程度上当时对于比例尺度的推崇,这种理性主义反映在园林中则是利用几何图形进行园林的规划设计。而中国的古典园林,从发展历程不难看出,很大程度上受到了当时文人墨客的影响,他们将书画诗等高雅艺术形式融入造园活动中,反映的是人的趣味,气质。
与其他中国古典建筑不同的是,古典园林在构图上取消了中轴线,在中国古典园林中很难看到左右对称的布局形式。其次,古典园林对待周围环境的态度不同,我认为这 ...
Economist以及其他一些英文外刊免费下载
Magazinelib
Magazinelib,一个全球免费英文杂志下载网站,主要是PDF 和交互式,上面收录了全球各个国家关于动物、艺术、商业、时尚、科学、科技等等方面的杂志,可以按照国家、年份和类型查看下载,而且英文杂志不断在更新,杂志下载无跳转,无需注册登录,直接下载PDF格式的杂志。但是需要右键点击文件复制链接地址用迅雷下载。
Magazinelib:https://magazinelib.com/
freemagazinepdf
电子杂志以 pdf 格式免费下载
freemagazinepdf:https://freemagazinepdf.com/
freemagazines.top
最好的在线杂志免费全部集中在一个地方。pdf可供下载,无需订阅即可随意选择大量类型。
freemagazines.top:https://freemagazines.top/
杂志之家
免费杂志下载,您可以找到您想要下载的免费杂志。来在线享受免费杂志
杂志之家::https://magazinebis.com/
PDF之家
PDF之家,一个专门分享PDF杂志、PDF图书、PDF漫画,并且提供免 ...