本文通过阅读 Spark RPC 相关部分的代码，了解学习 spark RPC 的架构实现以及原理和细节。 参考的 spark 版本为 2.3.1. spark RPC 在实现上主要分为本地RPC与远程RPC通信。 本地 RPC 通信主要是以线程实现的异步通信方式，而远程RPC通信主要以netty实现的socket通信方式。 如下所示， NettyRpcEndpointRef 为R...

面向 TCP 的 socket 开发现在场景比较普及，我们常见的像 tomcat, jetty 之类的 web 服务， 还有linux 的 sshd 用户认证服务， mysql server 等等， 他们使用到的都是 tcp 通信技术。 在基于tcp的 socket 开发里面, 服务端开发是比较复杂的一点，主要是它不但要正确处理用户来的请求消息， 还要及时处理异常的用户访问状态，并且要保障...

协议 特性 应用数据被分割成TCP认为最适合发送的数据块。这和UDP完全不同，应用程序产生的数据报长度将保持不变。由TCP传递给IP的信息单位称为报文段或段（segment）。 当TCP发出一个段后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段。 当TCP收到发自TCP连接另一端的数据，它将发送一个确认。这个确认不是立即发送，通...

概要: 当我们发送消息之前，先问几个问题：每条消息都是很关键且不能容忍丢失么？偶尔重复消息可以么？我们关注的是消息延迟还是写入消息的吞吐量？ 举个例子，有一个信用卡交易处理系统，当交易发生时会发送一条消息到Kafka，另一个服务来读取消息并根据规则引擎来检查交易是否通过，将结果通过Kafka返回。 对于这样的业务，消息既不能丢失也不能重复，由于交易量大因此吞吐量需要尽可能大，延迟可以稍微...

应用从Kafka中读取数据需要使用KafkaConsumer订阅主题，然后接收这些主题的消息。在我们深入这些API之前，先来看下几个比较重要的概念。 Kafka消费者相关的概念 1.消费者与消费组: 假设这么个场景：我们从Kafka中读取消息，并且进行检查，最后产生结果数据。 我们可以创建一个消费者实例去做这件事情，但如果生产者写入消息的速度比消费者读取的速度快怎么办呢？ 这样随着时间...

基本架构 了解Kafka之前，您必须了解Topic，Brocker，Producer和 Consumer 等主要术语。 一个 Topic 对应一个消息队列。 Producer 主要负责将数据发送到 kafka 对应的 topic 中去。Consumer 主要负责从 Topic 中去接收消息。 Partition 概念 我们知道 Kafka 的目标是大数据，如果将消息存在一个...

UDP是一个简单的面向数据报的运输层协议：进程的每个输出操作都正好产生一个UDP数据报，并组装成一份待发送的IP数据报。 UDP数据报封装成一份IP数据报的格式如图所示。 UDP不提供可靠性：它把应用程序传给IP层的数据发送出去，但是并不保证它们能到达目的地。由于缺乏可靠性，我们似乎觉得要避免使用UDP而使用一种可靠协议如TCP。 应用程序必须关心IP数据报的长度。如果它超过网络的...

如果并发的线程数量很多，并且每个线程都是执行一个时间很短的任务就结束了，这样频繁创建线程就会大大降低系统的效率，因为频繁创建线程和销毁线程需要时间。 那么有没有一种办法使得线程可以复用，就是执行完一个任务，并不被销毁，而是可以继续执行其他的任务？ 在Java中可以通过线程池来达到这样的效果。今天我们就来详细讲解一下Java的线程池，首先我们从最核心的ThreadPoolExecutor类中的...

Java NIO是java 1.4之后新出的一套IO接口，这里的的新是相对于原有标准的Java IO和Java Networking接口。NIO提供了一种完全不同的操作方式。 NIO包含下面几个核心的组件： Channels : 主要负责对接数据源， 主要用于读取或写入数据到数据源。 Buffers : 主要用于存储来自 channel 拉取的数据或维护将要写入chann...

网络层是为传输层提供服务的，传送的协议数据单元称为数据包或分组。 该层的主要作用是解决如何使数据包通过各结点传送的问题，即通过路径选择算法（路由）将数据包送到目的地。 另外，为避免通信子网中出现过多的数据包而造成网络阻塞，需要对流入的数据包数量进行控制（拥塞控制）。 当数据包要跨越多个通信子网才能到达目的地时，还要解决网际互连的问题。 IP 协议 IP协议是TCP/IP协议的核心，所有的...

链路层设计的主要协议如下 : CSMA/CD 协议 最初的以太网是将所有的计算机连接到一根总线上。当一台计算机发送数据的时候，总线上的所有计算机都能检测到这个数据。 这就是广播通信方式。 当我们需要在总线上进行一对一通信的时候，就需要使每一台计算机的网卡拥有一个与其他网卡都不同的地址。这个时候，我们在发送数据帧时，就需要表明数据帧接收站的地址。只有网卡地址与其相同时，才接受数据帧，否...

TCP/IP 协议分层 物理层为数据链路层实现在物理链路的传输，在其上串行传送电气特征的比特流。所以，该层中比较密切的是电气特性和物理特性等功能。 数据链路层负责在网络节点间的线路上通过检测、流量控制和重发等手段，无差错地传送以帧为单位的数据。为做到这一点，在每一帧中必须同时带有同步、地址、差错控制及流量控制等控制信息。 网络层为了将数据分组从源(源端系统) 送到 目的地(目标端系...

Google Guice 框架是一个基于Java 6以上的轻量级依赖注入框架，由Google开发。它相比于Spring IOC 来说，如果你只需在应用程序中实现依赖注入，那么你无需使用Spring容器。 Spring不仅仅是一个依赖注入框架，二期大多数Spring应用都使用了XML作为依赖注入的方式。而Guice却是一个相对更轻量级的框架，它的集成更少，有Java实例配置和运行时绑定。 通过...

CMake 是一个跨平台的、开源的构建工具。cmake 是 makefile 的上层工具，它们的目的正是为了产生可移植的makefile，并简化自己动手写makefile时的巨大工作量. 目前很多开源的项目都可以通过CMake工具来轻松构建工程. 入门案例 项目部署 c/c++ 项目工程部署如上: src : 源码工程目录 ext : 第三方依赖库文件与头文件...

进程调度 首先，我们需要清楚，什么样的进程会进入调度器进行选择，就是处于TASK_RUNNING状态的进程，而其他状态下的进程都不会进入调度器进行调度。 系统发生调度的时机如下: 调用cond_resched()时 显式调用schedule()时 从系统调用或者异常中断返回用户空间时 从中断上下文返回用户空间时 当开启内核抢占(默认开启)时，会多出几个调度...

背景: 页框管理是Linux系统的基本功能,主要负责维护RAM资源，完成系统对RAM资源请求的分配。 Linux 把 RAM 每 4KB( $2^{12}$ )划分为一个页框,这样正好与页大小相等或为页框的整数倍，便于请求页框。 利用页框机制有助于灵活分配内存地址，因为分配时不必要求必须有大块的连续内存，系统可以离散寻找空闲页凑出所需要的内存供进程使用。 虽然如此，但是实际上系统使用内存...

前言 继内存寻址之后， 本篇开始介绍Linux内核地址空间初始化过程。 通过内存寻址篇我们知道， Linux 系统运行过程中位于保护模式,系统必须要是用MMU来完成地址寻址， 这就依赖于段表跟页表。 但是问题来了, 系统是如何将段表跟页表是如何装入的呢？ 本文通过 Linux 系统初始化过程，开始介绍内存管理的构建过程。 BIOS 时代: 当PC机加电的那一刻，主机开始获取操作指...

内存地址: 现代操作系统为了实现程序的运行时动态链接, 动态运行时的装入方式, 保护模式 和 虚拟内存 等技术, 在程序的内存寻址方面采用逻辑地址替代物理地址。 运行时动态链接 : 是指将程序运行时所需要的链接库暂时驻留在磁盘中， 当程序执行到需要的库函数时，才将库链接到内存中，加入程序的地址空间。 动态运行时的装入方式 : 是指装入程序在把装入模块装入内存后，并不立即把装入模...

转载自:Spring-MVC开发之全局异常捕获全面解读 - 牧码游子 - 博客园 欢迎阅读原作者。 在用Spring MVC开发WEB应用时捕获全局异常的方法基本有两种： WEB.XML : 就是指定error-code和page到指定地址，这也是最传统和常见的做法 用Spring的全局异常捕获功能，这种相对可操作性更强一些，可根据自己的需要做一后善后处理，比如日志记录等。 SO...

原文地址:http://www.cnblogs.com/xiaoxi/p/5695783.html 1、直接把表单的参数写在Controller相应的方法的形参中，适用于get方式提交，不适用于post方式提交。 /** * 1.直接把表单的参数写在Controller相应的方法的形参中 * @param username * @param password * @return...

原文地址:http://www.cnblogs.com/xiaoxi/p/5695783.html 1、直接把表单的参数写在Controller相应的方法的形参中，适用于get方式提交，不适用于post方式提交。 /** * 1.直接把表单的参数写在Controller相应的方法的形参中 * @param username * @param password * @return...

原文:https://blog.csdn.net/gfd54gd5f46/article/details/75022305 1. 过滤器Filter : 创建 ServletFilter.java 实现 Filter 方法 package com.example.filter; import java.io.IOException; import javax.servlet.Filt...

原文: Spring MVC 框架入门学习 - 简书 1.Spring web mvc 介绍: Spring web mvc和Struts2都属于表现层的框架,它是Spring框架的一部分,我们可以从Spring的整体结构中看得出来: 2.Web mvc 用户发出的请求通过 HadllerMapping 定位到指定的控制器(Controller) 控制器(Control...

1.Jetty简介 1.1 什么是Jetty Jetty是一个提供 HTP服务器、HTTP客户端和javax.servlet容器的开源项目。 Jetty9 是Jetty的最近一个版本且比之前的版本有很大的改进，其中一个改进是Jetty所有特性已经体现在Jetty9的文档里。 Jetty有一个口号：不要把应用部署到Jetty上，要把Jetty部署到你的应用里。这句话的意思是把应用打成一...

介绍 : AOP(Aspect Orient Programming) 既为面向切面编程。 它可以说是OOP编程的一种扩展与补充，可以较为友好的处理不同模块之间具有横向相关性质的一类问题，比如日志管理，安全机制等。 我们这里 AOP 技术用的 AspectJ 的注解形式处理的。 <dependency> <groupId>org.aspectj</...

介绍 Spring AOP 主要通过 动态代理 来实现的，所以我们需要在介绍 AOP 用法之前，先来介绍下动态代理的用法以及本质。 对于动态代理的理解可以借鉴普通代理模式。我们普通的Java代理需要为一个对象建立专门的代理对象，通过调用代理对象，来实现原对象的各种功能。 而动态代理区别于普通代理方式,动态代理是在运行时产生的代理类。 普通代理的实现方式： 接口 : pub...

1. log4j 使用介绍: Log4j有三个主要的组件：Logger(输出源) ，Appender (输出方式 ) 和 Layout(布局) 。 这里可简单理解为日志类别，日志要输出的地方和日志以何种形式输出。 综合使用这三个组件可以轻松地记录信息的类型和级别，并可以在运行时控制日志输出的样式和位置。 1.1 Logger (负责控制输出源) : Loggers组件在此系统中被分为五...

使用注解配置的形式来构造bean需要首先引入 context:component-scan 的配置。他指定了 spring ioc 需要扫描的包，包下面的类将通过注解配置，构造bean对象。 例如: <context:component-scan base-package="com.saligia.spring.bean.annotation"></context:co...

介绍: Spring Core 中有两大部分组成 : IOC, AOP.这里我们开始介绍IOC. IOC(控制反转) 本质上就是将对象的构造与依赖关系交给IOC框架去维护。 用户只需要配置构造成员参数跟对象依赖关系。 框架帮你自动构建初始化对象。我们只需要从容器中拿取即可，不必在显示的 new 对象。 又称为依赖注入技术(DI). 依赖: <dependency> &...

1. 背景 mybatis最初配置信息是基于 XML ,映射语句(SQL)也是定义在 XML 中的。而到了 MyBatis 3提供了新的基于注解的配置。 这里讲述 注解开发方式: 首先我们需要获取 SqlSession: SqlSession session = sqlSessionFactory.openSession(true); 参数设置为true表示开启自动提交模式。 ...

1. 说明： MyBatis 是一款优秀的持久层框架，它支持定制化 SQL、存储过程以及高级映射。MyBatis 避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集。 什么意思，看下例子,原生的jdbc案例: //STEP 1. Import required packages import java.sql.*; public class FirstExample { ...

转载自:[2. 中介者模式 — Graphic Design Patterns] 15.1 模式动机 在用户与用户直接聊天的设计方案中，用户对象之间存在很强的关联性，将导致系统出现如下问题： 系统结构复杂：对象之间存在大量的相互关联和调用，若有一个对象发生变化，则需要跟踪和该对象关联的其他所有对象，并进行适当处理。 对象可重用性差：由于一个对象和其他对象具有很强的关联，若没有其他对象...

转载自: [1. 命令模式 — Graphic Design Patterns] 14.1 模式动机 在软件设计中，我们经常需要向某些对象发送请求，但是并不知道请求的接收者是谁，也不知道被请求的操作是哪个，我们只需在程序运行时指定具体的请求接收者即可，此时，可以使用命令模式来进行设计，使得请求发送者与请求接收者消除彼此之间的耦合，让对象之间的调用关系更加灵活。 命令模式可以对发送者和接...

转载自:[3. 观察者模式 — Graphic Design Patterns] 1.模式动机 建立一种对象与对象之间的依赖关系，一个对象发生改变时将自动通知其他对象，其他对象将相应做出反应。在此，发生改变的对象称为观察目标，而被通知的对象称为观察者，一个观察目标可以对应多个观察者，而且这些观察者之间没有相互联系，可以根据需要增加和删除观察者，使得系统更易于扩展，这就是观察者模式的模式动...

转载自: [5. 策略模式 — Graphic Design Patterns] 1. 模式动机: 完成一项任务，往往可以有多种不同的方式，每一种方式称为一个策略，我们可以根据环境或者条件的不同选择不同的策略来完成该项任务。 在软件开发中也常常遇到类似的情况，实现某一个功能有多个途径，此时可以使用一种设计模式来使得系统可以灵活地选择解决途径，也能够方便地增加新的解决途径。 在软件系统...

转载自:[4. 状态模式 — Graphic Design Patterns] 1. 模式动机: 在很多情况下，一个对象的行为取决于一个或多个动态变化的属性，这样的属性叫做状态，这样的对象叫做有状态的(stateful)对象，这样的对象状态是从事先定义好的一系列值中取出的。当一个这样的对象与外部事件产生互动时，其内部状态就会改变，从而使得系统的行为也随之发生变化。 ...

转载自: [3. 装饰模式 — Graphic Design Patterns] 1.模式动机 一般有两种方式可以实现给一个类或对象增加行为： 继承机制 ：使用继承机制是给现有类添加功能的一种有效途径，通过继承一个现有类可以使得子类在拥有自身方法的同时还拥有父类的方法。但是这种方法是静态的，用户不能控制增加行为的方式和时机。 关联机制 : 即将一个类...

转载自 : [4. 外观模式 — Graphic Design Patterns] 1.模式定义 外观模式(Facade Pattern) ：外部与一个子系统的通信必须通过一个统一的外观对象进行，为子系统中的一组接口提供一个一致的界面，外观模式定义了一个高层接口，这个接口使得这一子系统更加容易使用。外观模式又称为门面模式，它是一种对象结构型模式。 2. 模式结构 外观模式包含如...

6.1 模式动机: 在某些情况下，一个客户不想或者不能直接引用一个对象，此时可以通过一个称之为“代理”的第三者来实现间接引用。 代理对象可以在客户端和目标对象之间起到中介的作用，并且可以通过代理对象去掉客户不能看到的内容和服务或者添加客户需要的额外服务。 通过引入一个新的对象（如小图片和远程代理对象）来实现对真实对象的操作或者将新的对象作为真实对象的一个替身，这种实现机制即 为代理模式...

转载自 : [5. 享元模式 — Graphic Design Patterns] 1. 模式动机: 面向对象技术可以很好地解决一些灵活性或可扩展性问题: 但在很多情况下需要在系统中增加类和对象的个数,当对象数量太多时，将导致运行代价过高，带来性能下降等问题。 享元模式正是为解决这一类问题而诞生的,享元模式通过共享技术实现相同或相似对象的重用。 在享元模式中可以共享的相同内容称为内部...

转载自:[1. 适配器模式 — Graphic Design Patterns] 1.模式动机 在软件开发中采用类似于电源适配器的设计和编码技巧被称为适配器模式。 通常情况下，客户端可以通过目标类的接口访问它所提供的服务。有时，现有的类可以满足客户类的功能需要，但是它所提供的接口不一定是客户类所期望的，这可能是因为现有类中方法名与目标类中定义的方法名不...

转载自 : [2. 桥接模式 — Graphic Design Patterns] 1. 模式动机: 设想如果要绘制矩形、圆形、椭圆、正方形，我们至少需要4个形状类，但是如果绘制的图形需要具有不同的颜色，如红色、绿色、蓝色等，此时至少有如下两种设计方案： 第一种设计方案是为每一种形状都提供一套各种颜色的版本。 第二种设计方案是根据实际需要对形状和颜色进行组合 对于有两个变...

转载自: [4. 建造者模式 — Graphic Design Patterns] 1. 模式动机 无论是在现实世界中还是在软件系统中，都存在一些复杂的对象，它们拥有多个组成部分，如汽车，它包括车轮、方向盘、发送机等各种部件。 而对于大多数用户而言，无须知道这些部件的装配细节，也几乎不会使用单独某个部件，而是使用一辆完整的汽车，可以通过建造者模式对其进行设计与描述，建造者模式可以将部件...

转载自:[5. 单例模式 — Graphic Design Patterns] 1. 模式动机 对于系统中的某些类来说，只有一个实例很重要，例如，一个系统中可以存在多个打印任务，但是只能有一个正在工作的任务；一个系统只能有一个窗口管理器或文件系统；一个系统只能有一个计时工具或ID（序号）生成器。 如何保证一个类只有一个实例并且这个实例易于被访问呢？定义一个全局变量可以确保对象随时都可以...

转载自:[3. 抽象工厂模式 1.模式动机 在工厂方法模式中具体工厂负责生产具体的产品，每一个具体工厂对应一种具体产品，工厂方法也具有唯一性，一般情况下，一个具体工厂中只有一个工厂方法或者一组重载的工厂方法。 但是有时候我们需要一个工厂可以提供多个产品对象，而不是单一的产品对象。 为了更清晰地理解工厂方法模式，需要先引入两个概念： 产品等级结构 ：产品等级结...

转载自：[2. 工厂方法模式 1. 模式动机 现在对该系统进行修改，不再设计一个按钮工厂类来统一负责所有产品的创建，而是将具体按钮的创建过程交给专门的工厂子类去完成。 我们先定义一个抽象的按钮工厂类，再定义具体的工厂类来生成圆形按钮、矩形按钮、菱形按钮等，它们实现在抽象按钮工厂类中定义的方法。 这种抽象化的结果使这种结构可以在不修改具体工厂类的情况下引进新的产品，如果出现新的按钮类...

转载自:[1. 简单工厂模式 1. 模式动机 考虑一个简单的软件应用场景，一个软件系统可以提供多个外观不同的按钮（如圆形按钮、矩形按钮、菱形按钮等）， 这些按钮都源自同一个基类. 不过在继承基类后不同的子类修改了部分属性从而使得它们可以呈现不同的外观，如果我们希望在使用这些按钮时，不需要知道这些具体按钮类的名字. 只需要知道表示该按钮类的一个参数并提供一个调用方便的方法，把该参数传入...

转载自 : 设计模式之六大原则（转载） - 海 子 - 博客园 前言： 设计模式（Design pattern） 是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。 使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。 设计模式使代码编制真正工程化，设计模式是软件工程的基石，如同大厦的一块块砖石一样。 只有精通了设计模式，才敢说真正理解了软件工程。 ...

转载自:[看懂UML类图和时序图 — Graphic Design Patterns] 1-从一个示例开始: 请看以下这个类图，类之间的关系是我们需要关注的： 车的类图结构为<<abstract>>，表示车是一个抽象类； 它有两个继承类：小汽车和自行车；它们之间的关系为实现关系，使用带空心箭头的虚线表示； 小汽车为与SUV之间也是继承关系，它们...

转载自 UML建模中的时序图详解 - CSDN博客 1.时序图简介（Brief introduction） 时序图（Sequence Diagram） 是显示对象之间交互的图，这些对象是按时间顺序排列的。顺序图中显示的是参与交互的对象及其对象之间消息交互的顺序。时序图中包括的建模元素主要有：对象（Actor）、生命线（Lifeline）、控制焦点（Focus of control）、消息...

转载自:[深入理解JVM(5)——虚拟机类加载机制 - 王泽远的博客 Crow’s Blog](https://crowhawk.github.io/2017/08/21/jvm_5/) 虚拟机描述类的数据从 Class 文件加载到内存，并对数据进行校验,转换解析和初始化,最终形成可以被虚拟机直接使用的java类型。这就是虚拟机的类加载机制。 在上图中，...

1.概述: 我们都知道，在当前的Java中（1.0）之后，编译器讲源代码转成字节码，那么字节码如何被执行的呢？ 这就涉及到了JVM的字节码执行引擎，执行引擎负责具体的代码调用及执行过程。就目前而言，所有的执行引擎的基本一致： 输入：字节码文件 处理：字节码解析 输出：执行结果。 物理机的执行引擎是由硬件实现的，和物理机的执行过程不同的是虚拟机的执行引擎由于自己实现的。 ...

1. 首先需要解决的问题:哪些对象已经死亡 1.1 引用计数算法 引用分析算法是这样的: 给每一个对象添加一个引用计数器， 每当有一个地方使用，计数器就加一; 任何时刻计数器为0的对象就是 不可能再被使用的。 缺点:难以解决对象之间的循环引用问题 1.2 可达性分析算法(商用程序语言的主流实现): 这个算法的基本思想就是通过一系列的”GC ROOTS”的对象作为起始点...

程序计数器 作用: 程序计数器是较小的内存空间，它可以当做是当前线程所执行的字节码的行号指示器。 字节码解释器工作时就是通过改变这个计数器的值来选取下一条需要执行的字节码指令，分支，循环，跳转，异常处理，线程恢复等基础功能都需要依赖这个程序计数器来完成。 程序计数器的线程隔离性 java 虚拟机的多线程都是通过线程轮流切换并分配处理器执行时间的方式来实现的，在任...

转载自图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园 归并排序是利用归并的思想实现的排序方式，该算法采用经典的分治策略。(分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。 分而治之 可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭...

1. 简单选择排序 选择排序（Selection Sort）是一种简单直观的排序算法。 它的工作原理如下: 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均排序完毕。 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。 选择排序...

思想: “快速排序”的思想很简单，整个排序过程只需要三步： （1）在数据集之中，选择一个元素作为"基准"（`pivot`）。 （2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。 （3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。 举例来说，现在有一个数据集${85, 24, 63, 45,...

1. 直接插入排序: 每次从无序表中取出最后一个元素，把它插入到有序表的合适位置，使有序表仍然有序。 1. 详解： 从数组的第二个元素开始,将数组中的每一个元素按照（升序或者降序）规则插入到已排好序的数组中以达到排序的目的. 一般情况下将数组的第一个元素作为起始元素,从第二个元素开始依次插入。 由于要插入到的数组是已经排好序的,所以只要从右向左（或者从后向前）找到排序插入点插入元素...

1. 迪杰斯特拉(Dijkstra)算法: 1. 定义概览 Dijkstra(迪杰斯特拉) 算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。 主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 问题描...

拓扑排序 1. 什么是拓扑排序: 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件： 每个顶点出现且只出现一次。 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（DAG）才有拓扑排序，非DAG图没有...

转载自: [勿在浮沙筑高台] 连通图：在无向图中，若任意两个顶点$v_{i}$与$v_{j}$都有路径相通，则称该无向图为连通图。 强连通图：在有向图中，若任意两个顶点$v_{i}$与$v_{j}都有路径相通，则称该有向图为强连通图。 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。 生成树：一个连通图的生成树...

图的深度优先遍历(DFS) 深度优先搜索（depth-first search）是对先序遍历（preorder traversal）的推广。我们从某个顶点 v 开始处理 v，然后递归地遍历所有与 v 邻接的顶点。 实现思想： 在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去，当节点 v 的所有边都已被探寻过，探索将回溯到发现节点 v...

概念: 图是由顶点的有穷非空集合和顶点之间边的集合组成，通过表示为G(V,E)，其中，G标示一个图，V是图G中顶点的集合，E是图G中边的集合。 无边图：若顶点$V_{i}$到$V_{j}$之间的边没有方向，则称这条边为无项边(Edge), 用序偶对$(V_{i},V_{j})$标示。 对于下图无向图G1来说，G1=(V1, {E1})，其中顶点集合V1={A,B,C,D}; 边...

介绍: 红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束，但是这样在动态插入中保持树的完美平衡代价太高，所以，我们稍微放松逛一下限制，希望找到一个能在对数时间内完成查找的数据结构。这个时候，红黑树站了出来。 红黑树是在普通二叉树上，对每个节点添加一个颜色属性形成的，同时整个红黑二叉树需要同时满足一下五条性质: 每个节点或者是...

转载自:B-树的详解 - CSDN博客 B 树: 1.背景 磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候...

背景: AVL(Adelson-Velskii和Landis发明者的首字母)树 是带有平衡条件的二叉查找树。 二叉查找树的性能分析： 在一颗左右子树高度平衡情况下，最优的时间复杂度为$O(log_{2}{n})$，这与这半查找相同； 在一个只有右子树的二叉树中，最差的时间复杂度会脱变为线性查找$O(n)$。 由于二叉查找树存在以上问题，所以AVL树通过旋转使自身始...

二叉查找树(Binary Search Tree)，又被称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为 $key[x]$。 如果y是x的左子树中的一个结点，则 $key[y] <= key[x]$; 如果y是x的右子树的一个结点，则 $key[y] >= key[x]$。 说明: 若任意节点的左子树不空，则左子树上所有结点...

概念： 二叉树的遍历分为以下三种: 先序遍历：遍历顺序规则为【根左右】 中序遍历：遍历顺序规则为【左根右】 后序遍历：遍历顺序规则为【左右根】 举个例子，看下图: 先序遍历：ABCDEFGHK 中序遍历：BDCAEHGKF 后序遍历：DCBHKGFEA 编程实现方式: 三种方法中，递归最为简单，栈次之，循环最为麻烦。递归的深度如果太大则会导致栈溢出；栈的方式需要额外的...

定义: 1. 节点的类型: 在非空二叉树中，第i层的结点总数最大为$2^{i}-1,i\ge1$（满树情况） 深度为h的二叉树最多有 $2^h-1, h\ge1$ 个结点，最少有$h$个结点 对于任意一棵二叉树，设其总结点数为$N$，如果其叶结点(度为0的结点）数为$N_0$，而度数为2的结点总数为$N_2$，则$N_0=N_2+1$，度为1的结点数$N_1=N-N_0-N...

转载自 : 树的三种存储结构 - CSDN博客 定义 树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。 在任意一棵非空树中: 有且仅有一个特定的称为根(Root)的结点; 当n>1时，其余结点可分为m(m>O)个互不相交的有限集$T_1,T2,…,T_m$，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)，如图...

线性表是一种典型的线性结构。 线性表的顺序实现 顺序表是线性表的顺序存储结构，指的是用一组地址连续的存储单元依次存储线性表的数据元素. 顺序表具备如下两个基本特征： 顺序表中的所有元素所占的存储空间是连续的； 顺序表中各数据元素在存储空间中是按逻辑顺序依次存放的。 假设顺序表的每个元素需占用$K$个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则顺...

栈: 栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶(TOP)，另一端为栈底(BOTTOM)。 当表中没有元素时称为栈空。 栈顶元素总是后被插入(入栈)的元素，从而也是最先被移除(出栈)的元素；栈底元素总是最先被插入的元素，从而也是最后才能被移除的元素。所以栈是个 后进先出(LIFO) 的数据结构 栈的基本运算有三种：入栈、出栈与读栈顶，时间复杂度都是O(...

串的存储表示和实现: 串是一种特殊的线性表,其存储表示和线性表类似但又不完全相同。串的存储方式取决于将要对串所进行的操作. 串在计算机中有3种表示方式: 定长顺序存储方式: 将串定义成字符数组,利用串名可以直接访问串值。用这种表示方式,串的存 储空间在编译时确定,其大小不能改变。 堆分配存储方式: 仍然用一组地址连续的存储单 元来依次存储串中的字符序列...

简要