线性表
基本概念线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。这些元素也可称为结点或表目. 在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。 逻辑结构用二元组(K,R)来表示线性表,则有: 123K={k0,k1,k2,...,kn-1}R={r}r={<ki,ki+1> |...
荷兰国旗
题目描述拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。 该问题本身是关于三色球排序和分类的，由荷兰科学家Dijkstra提出。由于问题中的三色小球有序排列后正好分为三类，Dijkstra就想象成他母国的国旗，于是问题也就被命名为荷兰旗问题（Dutch National Flag...
跳台阶问题
题目描述一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。 求总共有多少总跳法，并分析算法的时间复杂度。 分析与解法解法一首先考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。 现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。 当n>2时，第一次跳的时候就有两种不同的选择： 一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)； 另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。 因此n级台阶时的不同跳法的总数f(n)=f(n-1)+f(n-2)。 我们把上面的分析用一个公式总结如下： 123 / 1 n = 1f(n)= 2 n = 2 \ f(n-1) + f(n-2) ...
逆置顺序表
设顺序表a中数据元素递增有序,试着设计一个算法将x插入到顺序表的适当位置,以保持该表的有序性. 逐个遍历以为顺序表递增有序,从头开始找到第一个不小于它的元素,放在该元素前面. 二分查找步骤1:取顺序表中间元素的值与插入元素比较,步骤2:相等则放在该元素前面;插入元素小于中间元素,将列表分割为两部分对前面的部分进行步骤1;如果大于,对后面部分进行步骤1结束条件:比较结果相等,或者分割后顺序表元素个数为1
链表
链表简介链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构在插入的时候可以达到O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间.同时失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。 链表有很多种不同的类型：单向链表，双向链表以及循环链表。 单链表单链表中每个结点只包含一个数据域和一个指针. 单链表声明 123456789101112131415161718192021222324252627typedef int T;//元素类型typedef struct link{ T data; struct link *next;}SingleLinkList, *PSingleLinkList;PSingleLinkList Init();int...
附近地点搜索
附近地点搜索题目详情找一个点集中与给定点距离最近的点，同时，给定的二维点集都是固定的，查询可能有很多次，时间复杂度O(n)无法接受，请设计数据结构和相应的算法。 分析与解法此题是去年微软的三面题，类似于一朋友@陈利人出的这题：附近地点搜索，就是搜索用户附近有哪些地点。随着GPS和带有GPS功能的移动设备的普及，附近地点搜索也变得炙手可热。在庞大的地理数据库中搜索地点，索引是很重要的。但是，我们的需求是搜索附近地点，例如，坐标(39.91, 116.37)附近500米内有什么餐馆，那么让你来设计，该怎么做？ 解法一：R树二维搜索假定只允许你初中数学知识，那么你可能建一个X-Y坐标系，即以坐标(39.91,...
随机取出其中之一元素
随机取出其中之一元素题目描述一个文件中含有n个元素（n未知），要求在只能遍历一遍这n个元素的情况下，等概率随机的取出其中之一个元素。 分析与解法假设5个人轮流抽签，只有其中某一个人能中签，那么，这5个人每个人中签的概率是相等的。不信的话，咱们可以具体计算下。 首先，第一个人中签的概率是1/5，第二个人中签的情况只能在第一个人未中时才有可能，所以第二个人中签的概率是4/5 X 1/4 = 1/5（4/5表示第一个人未中，1/4表示第二个人在剩下的4个签里中签的概率），所以，第二个人最终的中签概率也是1/5， 同理，第三个人中签的概率为：第一个人未中的概率 * 第二个人未中的概率 * 第三个人中的概率，即为：4/5 * 3/4 * 1/3 =...
顺序表
定义顺序表(array-based list)又称为向量(vector)是在计算机内存中以数组的形式保存的线性表. 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。 顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 顺序表的基本操作顺序表的声明array_based_list.h 1234567891011121314151617181920212223242526272829#define ListSize 100 //线性表的最大长度typedef int DataType;// 顺序表内元素类型/**** 顺序表**///定义typedef struct{ DataType data[ListSize]; //用数组存储线性表中的元素 int length; ...
JVM
Java虚拟机（JVM, Java Virtual Machine）是Java语言的核心组件，它是一个抽象的计算机，专门为执行Java字节码而设计。Java源代码经过Java编译器编译后生成与平台无关的字节码文件（.class文件），这些字节码可以在任何安装了Java运行环境（JRE）的设备上运行，这是因为不同的平台上都有对应的JVM实现来解释或即时编译这些字节码。 JVM的主要作用和特征包括： 跨平台性： JVM为Java程序提供了跨平台的能力。开发者只需要编写一次Java代码，就可以在任何支持Java的系统上运行，这得益于JVM对不同操作系统和硬件架构的支持以及统一的字节码格式。 类加载机制： JVM通过类加载器（ClassLoader）将.class文件从硬盘加载到内存中，进行验证、准备、解析和初始化等步骤，使得类可以被JVM识别并使用。 内存管理： JVM内部有自己的一套内存模型，包含方法区、堆、栈、程序计数器和本地方法栈等多个区域。JVM负责自动管理内存分配与回收，尤其是垃圾收集机制（Garbage...
JVM学习指南
...