介绍
1、数据结构分类
数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据。
把数据结构分为逻辑结构和物理结构两大类。
逻辑结构分类：集合结构、线性结构、树形结构、图形结构。
物理结构：顺序存储结构、链式存储结构。
顺序存储结构：把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的 ，比如我们常用的数组就是顺序存储结构。查找快、插入删除慢。
链式存储结构：是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此在链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。查找慢，增删快。
2、算法介绍
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。根据一定的条件，对一些数据进行计算，得到需要的结果。
一个优秀的算法追求以下两个目标：1.花最少的时间完成需求；2.占用最少的内存空间完成需求。
3、算法的时间复杂度
算法的时间复杂度分析
事后分析估算方法：计算方法执行时间System.currentTimeMillis()。
事前分析估算方法：算法采用的策略和方案；问题的输入规模(所谓的问题输入规模就是输入量的多少)。最重要的就是把核心操作的次数和输入规模关联起来。
总结：随着输入规模的增大，算法的常数操作可以忽略不计。随着输入规模的增大，与最高次项相乘的常数可以忽略。最高次项的指数大的，随着n的增长，结果也会变得增长特别快。算法函数中n最高次幂越小，算法效率越高。
4、时间复杂度大O记法
执行次数=执行时间。用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。
大O阶的表示法有以下几个规则可以使用：
1.用常数1取代运行时间中的所有加法常数；
2.在修改后的运行次数中，只保留高阶项；
3.如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数。
复杂程度从低到高依次为：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)。
5、算法的空间复杂度
数据类型 内存占用字节数：byte 1、short 2、int 4、long 8、float 4、double 8、boolean 1、char 2。
计算机访问内存的方式都是一次一个字节。
一个引用（机器地址）需要8个字节表示：
Date date = new Date()；//则date这个变量需要占用8个字节来表示
创建一个对象，比如new Date()，除了Date对象内部存储的数据(例如年月日等信息)占用的内存，该对象本身也有内存开销，每个对象的自身开销是16个字节，用来保存对象的头信息。
一般内存的使用，如果不够8个字节，都会被自动填充为8字节。
java中数组被被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销，4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。
int[] temp=new int[n];//申请n*4个字节+数组自身头信息开销24个字节
排序
1、Comparable接口
public class Student implements Comparable<Student>{
private String username;
private int age;
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"username='" + username + '\'' +
", age=" + age +
'}';
}
@Override
public int compareTo(Student o) {
return this.getAge()-o.getAge();
}
}
public class TestComparable {
public static void main(String[] args) {
//创建两个Student对象，并调用getMax方法，完成测试
Student s1 = new Student();
s1.setUsername("张三");
s1.setAge(18);
Student s2 = new Student();
s2.setUsername("李四");
s2.setAge(20);
Comparable max = getMax(s1, s2);
System.out.println(max);
}
public static Comparable getMax(Comparable c1,Comparable c2){
int result = c1.compareTo(c2);
//如果result<0,则c1比c2小；
//如果result>0，则c1比c2大；
//如果result==0,则c1和c2一样大；
if (result>=0){
return c1;
}else{
return c2;
}
}
}
2、冒泡排序
比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。最终最后位置的元素就是最大值。
public class Bubble {
/*
* 对数组的元素进行排序
*/
public static void sort(Comparable[] a){
for(int i=a.length-1;i>0;i--){
for(int j=0;j<i;j++){
//比较索引j和索引j+1处的值
if (greater(a[j],a[j+1])){
exch(a,j,j+1);
}
}
}
}
/*
* 比较v元素是否大于w元素
*/
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
}
public class BubbleTest {
public static void main(String[] args) {
Integer[] arr = {4,5,6,3,2,1};
Bubble.sort(arr);
System.out.println(Arrays.toString(arr));//{1,2,3,4,5,6}
}
}
冒泡排序的时间复杂度为O(N^2)。
3、选择排序
每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引。然后交换第一个索引处和最小值所在的索引处的值。
public class Selection {
/*
对数组中的元素进行排序
*/
public static void sort(Comparable[] a){
for(int i=0;i<=a.length-2;i++){
//定义一个变量，记录最小元素所在的索引，默认为参与选择排序的第一个元素所在的位置
int minIndex = i;
for(int j=i+1;j<a.length;j++){
//需要比较最小索引minIndex处的值和j索引处的值；
if (greater(a[minIndex],a[j])){
minIndex=j;
}
}
//交换最小元素所在索引minIndex处的值和索引i处的值
exch(a,i,minIndex);
}
}
/*
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
}
public class SelectionTest {
public static void main(String[] args) {
//原始数据
Integer[] a = {4,6,8,7,9,2,10,1};
Selection.sort(a);
System.out.println(Arrays.toString(a));//{1,2,4,5,7,8,9,10}
}
}
时间复杂度为O(N^2)。
4、插入排序
把所有的元素分为两组，已经排序的和未排序的；找到未排序的组中的第一个元素，向已经排序的组中进行插入；倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位。类似打扑克牌时，新牌往手里牌的排序。
public class Insertion {
/*
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a){
for(int i=1;i<a.length;i++){
for(int j=i;j>0;j--){
//比较索引j处的值和索引j-1处的值，如果索引j-1处的值比索引j处的值大，则交换数据，如果不大，那么就找到合适的位置了，退出循环即可；
if (greater(a[j-1],a[j])){
exch(a,j-1,j);
}else{
break;
}
}
}
}
/*
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
}
public class InsertionTest {
public static void main(String[] args) {
Integer[] a = {4,3,2,10,12,1,5,6};
Insertion.sort(a);
System.out.println(Arrays.toString(a));//{1,2,3,4,5,6,10,12}
}
}
时间复杂度为O(N^2)。
5、希尔排序
选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；对分好组的每一组数据完成插入排序；减小增长量，最小减为1，重复第二步操作。
增长量h的确定：
int h=1
while(h<(数组长度/2)){
h=2h+1
}
//循环结束后我们就可以确定h的最大值
//h的减小规则为：
h=h/2
代码
public class Shell {
/*
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a){
//1.根据数组a的长度，确定增长量h的初始值；
int h = 1;
while(h<a.length/2){
h=2*h+1;
}
//2.希尔排序
while(h>=1){
//排序
//2.1.找到待插入的元素
for (int i=h;i<a.length;i++){
//2.2把待插入的元素插入到有序数列中
for (int j=i;j>=h;j-=h){
//待插入的元素是a[j],比较a[j]和a[j-h]
if (greater(a[j-h],a[j])){
//交换元素
exch(a,j-h,j);
}else{
//待插入元素已经找到了合适的位置，结束循环；
break;
}
}
}
//减小h的值
h= h/2;
}
}
/*
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a,int i,int j){
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
}
public class ShellTest {
public static void main(String[] args) {
Integer[] a = {9,1,2,5,7,4,8,6,3,5};
Shell.sort(a);
System.out.println(Arrays.toString(a));//{1,2,3,4,5,5,6,7,8,9}
}
}
6、归并排序
尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。将相邻的两个子组进行合并成一个有序的大组；不断的重复步骤2，直到最终只有一个组为止。
public class Merge {
//归并所需要的辅助数组
private static Comparable[] assist;
/*
比较v元素是否小于w元素
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w)<0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
/*
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a) {
//1.初始化辅助数组assist；
assist = new Comparable[a.length];
//2.定义一个lo变量，和hi变量，分别记录数组中最小的索引和最大的索引；
int lo=0;
int hi=a.length-1;
//3.调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序
sort(a,lo,hi);
}
/*
对数组a中从lo到hi的元素进行排序
*/
private static void sort(Comparable[] a, int lo, int hi) {
//做安全性校验；
if (hi<=lo){
return;
}
//对lo到hi之间的数据进行分为两个组
int mid = lo+(hi-lo)/2;// 5,9 mid=7
//分别对每一组数据进行排序
sort(a,lo,mid);
sort(a,mid+1,hi);
//再把两个组中的数据进行归并
merge(a,lo,mid,hi);
}
/*
对数组中，从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并
*/
private static void merge(Comparable[] a, int lo, int mid, int hi) {
//定义三个指针
int i=lo;
int p1=lo;
int p2=mid+1;
//遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处
while(p1<=mid && p2<=hi){
//比较对应索引处的值
if (less(a[p1],a[p2])){
assist[i++] = a[p1++];
}else{
assist[i++]=a[p2++];
}
}
//遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
while(p1<=mid){
assist[i++]=a[p1++];
}
//遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
while(p2<=hi){
assist[i++]=a[p2++];
}
//把辅助数组中的元素拷贝到原数组中
for(int index=lo;index<=hi;index++){
a[index]=assist[index];
}
}
}
public class MergeTest {
public static void main(String[] args) {
Integer[] a = {8,4,5,7,1,3,6,2};
Merge.sort(a);
System.out.println(Arrays.toString(a));//{1,2,3,4,5,6,7,8}
}
}
归并排序的时间复杂度为O(nlogn)。归并排序的缺点：需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。
7、快速排序
首先设定一个分界值，通过该分界值将数组分成左右两部分；将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
切分原理：把一个数组切分成两个子数组的基本思想：
1.找一个基准值，用两个指针分别指向数组的头部和尾部；
2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4.交换当前左边指针位置和右边指针位置的元素；
5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
public class Quick {
/*
比较v元素是否小于w元素
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
//对数组内的元素进行排序
public static void sort(Comparable[] a) {
int lo = 0;
int hi = a.length-1;
sort(a,lo,hi);
}
//对数组a中从索引lo到索引hi之间的元素进行排序
private static void sort(Comparable[] a, int lo, int hi) {
//安全性校验
if (hi<=lo){
return;
}
//需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）；
int partition = partition(a, lo, hi);//返回的是分组的分界值所在的索引，分界值位置变换后的索引
//让左子组有序
sort(a,lo,partition-1);
//让右子组有序
sort(a,partition+1,hi);
}
//对数组a中，从索引 lo到索引 hi之间的元素进行分组，并返回分组界限对应的索引
public static int partition(Comparable[] a, int lo, int hi) {
//确定分界值
Comparable key = a[lo];
//定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
int left=lo;
int right=hi+1;
//切分
while(true){
//先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止
while(less(key,a[--right])){
if (right==lo){
break;
}
}
//再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止
while(less(a[++left],key)){
if (left==hi){
break;
}
}
//判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
if (left>=right){
break;
}else{
exch(a,left,right);
}
}
//交换分界值
exch(a,lo,right);
return right;
}
}
public class QuickTest {
public static void main(String[] args) {
Integer[] a= {6, 1, 2, 7, 9, 3, 4, 5, 8};
Quick.sort(a);
System.out.println(Arrays.toString(a));//{1, 2, 3, 4, 5, 6, 7, 8, 9}
}
}
快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的方式则是当两个数组都有序时，整个数组自然就有序了。在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。
快速排序的时间复杂度为O(nlogn)。
8、排序的稳定性
数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保证A元素依然在B元素的前面，可以说这个该算法是稳定的。
如果一组数据只需要一次排序，则稳定性一般是没有意义的，如果一组数据需要多次排序，稳定性是有意义的。例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序按照销量由高到低排序，如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。
稳定排序算法：冒泡排序、插入排序、归并排序。
不稳定的排序算法：选择排序、希尔排序、快速排序。
线性表
若A元素在B元素的前面，则称A为B的前驱元素。若B元素在A元素的后面，则称B为A的后继元素。
第一个数据元素没有前驱，这个数据元素被称为头结点；最后一个数据元素没有后继，这个数据元素被称为尾结点；除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。
顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
基本API、扩容、缩容、SequenceList能支持foreach循环，则需要做如下操作：让SequenceList实现Iterable接口，重写iterator方法；在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法。
public class SequenceList<T> implements Iterable<T>{
//存储元素的数组
private T[] eles;
//记录当前顺序表中的元素个数
private int N;
//构造方法
public SequenceList(int capacity){
//初始化数组
this.eles=(T[])new Object[capacity];
//初始化长度
this.N=0;
}
//将一个线性表置为空表
public void clear(){
this.N=0;
}
//判断当前线性表是否为空表
public boolean isEmpty(){
return N==0;
}
//获取线性表的长度
public int length(){
return N;
}
//获取指定位置的元素
public T get(int i){
return eles[i];
}
//向线型表中添加元素t
public void insert(T t){
if (N==eles.length){
resize(2*eles.length);
}
eles[N++]=t;
}
//在i元素处插入元素t
public void insert(int i,T t){
if (N==eles.length){
resize(2*eles.length);
}
//先把i索引处的元素及其后面的元素依次向后移动一位
for(int index=N;index>i;index--){
eles[index]=eles[index-1];
}
//再把t元素放到i索引处即可
eles[i]=t;
//元素个数+1
N++;
}
//删除指定位置i处的元素，并返回该元素
public T remove(int i){
//记录索引i处的值
T current = eles[i];
//索引i后面元素依次向前移动一位即可
for(int index=i;index<N-1;index++){
eles[index]=eles[index+1];
}
//元素个数-1
N--;
if (N<eles.length/4){
resize(eles.length/2);
}
return current;
}
//查找t元素第一次出现的位置
public int indexOf(T t){
for(int i=0;i<N;i++){
if (eles[i].equals(t)){
return i;
}
}
return -1;
}
//根据参数newSize，重置eles的大小
public void resize(int newSize){
//定义一个临时数组，指向原数组
T[] temp=eles;
//创建新数组
eles=(T[])new Object[newSize];
//把原数组的数据拷贝到新数组即可
for(int i=0;i<N;i++){
eles[i]=temp[i];
}
}
@Override
public Iterator<T> iterator() {
return new SIterator();
}
private class SIterator implements Iterator{
private int cusor;
public SIterator(){
this.cusor=0;
}
@Override
public boolean hasNext() {
return cusor<N;
}
@Override
public Object next() {
return eles[cusor++];
}
}
}
测试
public class SequenceListTest {
public static void main(String[] args) {
//创建顺序表对象
SequenceList<String> sl = new SequenceList<>(10);
//测试插入
sl.insert("姚明");
sl.insert("科比");
sl.insert("麦迪");
sl.insert(1,"詹姆斯");
for (String s : sl) {
System.out.println(s);
}
System.out.println("------------------------------------------");
//测试获取
String getResult = sl.get(1);
System.out.println("获取索引1处的结果为："+getResult);
//测试删除
String removeResult = sl.remove(0);
System.out.println("删除的元素是："+removeResult);
//测试清空
sl.clear();
System.out.println("清空后的线性表中的元素个数为:"+sl.length());
}
}
由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显。
java中ArrayList集合的底层也是一种顺序表，使用数组实现，同样提供了增删改查、扩容、遍历等功能。
链表
链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。
public class Node<T> {
//存储元素
public T item;
//指向下一个结点
public Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
public static void main(String[] args) throws Exception {
//构建结点
Node<Integer> first = new Node<Integer>(11, null);
Node<Integer> second = new Node<Integer>(13, null);
Node<Integer> third = new Node<Integer>(12, null);
Node<Integer> fourth = new Node<Integer>(8, null);
Node<Integer> fifth = new Node<Integer>(9, null);
//生成链表
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
}
单向链表
单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
实现基本API、遍历、链表的反转。
public class LinkList<T> implements Iterable<T>{
//记录头结点
private Node head;
//记录链表的长度
private int N;
//结点类
private class Node {
//存储数据
T item;
//下一个结点
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
public LinkList() {
//初始化头结点、
this.head = new Node(null,null);
//初始化元素个数
this.N=0;
}
//清空链表
public void clear() {
head.next=null;
this.N=0;
}
//获取链表的长度
public int length() {
return N;
}
//判断链表是否为空
public boolean isEmpty() {
return N==0;
}
//获取指定位置i出的元素
public T get(int i) {
//通过循环,从头结点开始往后找，依次找i次，就可以找到对应的元素
Node n = head.next;
for(int index=0;index<i;index++){
n=n.next;
}
return n.item;
}
//向链表中添加元素t
public void insert(T t) {
//找到当前最后一个结点
Node n = head;
while(n.next!=null){
n=n.next;
}
//创建新结点，保存元素t
Node newNode = new Node(t, null);
//让当前最后一个结点指向新结点
n.next=newNode;
//元素的个数+1
N++;
}
//向指定位置i出，添加元素t
public void insert(int i, T t) {
//找到i位置前一个结点
Node pre = head;
for(int index=0;index<=i-1;index++){
pre=pre.next;
}
//找到i位置的结点
Node curr = pre.next;
//创建新结点，并且新结点需要指向原来i位置的结点
Node newNode = new Node(t, curr);
//原来i位置的前一个节点指向新结点即可
pre.next=newNode;
//元素的个数+1
N++;
}
//删除指定位置i处的元素，并返回被删除的元素
public T remove(int i) {
//找到i位置的前一个节点
Node pre = head;
for(int index=0;index<=i-1;i++){
pre=pre.next;
}
//要找到i位置的结点
Node curr = pre.next;
//找到i位置的下一个结点
Node nextNode = curr.next;
//前一个结点指向下一个结点
pre.next=nextNode;
//元素个数-1
N--;
return curr.item;
}
//查找元素t在链表中第一次出现的位置
public int indexOf(T t) {
//从头结点开始，依次找到每一个结点，取出item，和t比较，如果相同，就找到了
Node n = head;
for(int i=0;n.next!=null;i++){
n=n.next;
if (n.item.equals(t)){
return i;
}
}
return -1;
}
@Override
public Iterator<T> iterator() {
return new LIterator();
}
private class LIterator implements Iterator{
private Node n;
public LIterator(){
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n = n.next;
return n.item;
}
}
//用来反转整个链表
public void reverse(){
//判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转
if (isEmpty()){
return;
}
reverse(head.next);
}
//反转指定的结点curr，并把反转后的结点返回
public Node reverse(Node curr){
if (curr.next==null){
head.next=curr;
return curr;
}
//递归的反转当前结点curr的下一个结点；返回值就是链表反转后，当前结点的上一个结点
Node pre = reverse(curr.next);
//让返回的结点的下一个结点变为当前结点curr；
pre.next=curr;
//把当前结点的下一个结点变为null
curr.next=null;
return curr;
}
}
测试
public class LinkListTest {
public static void main(String[] args) {
//创建顺序表对象
LinkList<String> sl = new LinkList<>();
//测试插入
sl.insert("姚明");
sl.insert("科比");
sl.insert("麦迪");
sl.insert(1,"詹姆斯");
for (String s : sl) {
System.out.println(s);
}
System.out.println("------------------------------------------");
//测试获取
String getResult = sl.get(1);
System.out.println("获取索引1处的结果为："+getResult);
//测试删除
String removeResult = sl.remove(0);
System.out.println("删除的元素是："+removeResult);
//测试清空
sl.clear();
System.out.println("清空后的线性表中的元素个数为:"+sl.length());
}
}
双向链表
双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。
实现基本API、遍历。
public class TowWayLinkList<T> implements Iterable<T> {
//首结点
private Node head;
//最后一个结点
private Node last;
//链表的长度
private int N;
//结点类
private class Node{
public Node(T item, Node pre, Node next) {
this.item = item;
this.pre = pre;
this.next = next;
}
//存储数据
public T item;
//指向上一个结点
public Node pre;
//指向下一个结点
public Node next;
}
public TowWayLinkList() {
//初始化头结点和尾结点
this.head = new Node(null,null,null);
this.last=null;
//初始化元素个数
this.N=0;
}
//清空链表
public void clear(){
this.head.next=null;
this.head.pre=null;
this.head.item=null;
this.last=null;
this.N=0;
}
//获取链表长度
public int length(){
return N;
}
//判断链表是否为空
public boolean isEmpty(){
return N==0;
}
//获取第一个元素
public T getFirst(){
if (isEmpty()){
return null;
}
return head.next.item;
}
//获取最后一个元素
public T getLast(){
if (isEmpty()){
return null;
}
return last.item;
}
//插入元素t
public void insert(T t){
if (isEmpty()){
//如果链表为空：
//创建新的结点
Node newNode = new Node(t,head, null);
//让新结点称为尾结点
last=newNode;
//让头结点指向尾结点
head.next=last;
}else {
//如果链表不为空
Node oldLast = last;
//创建新的结点
Node newNode = new Node(t, oldLast, null);
//让当前的尾结点指向新结点
oldLast.next=newNode;
//让新结点称为尾结点
last = newNode;
}
//元素个数+1
N++;
}
//向指定位置i处插入元素t
public void insert(int i,T t){
//找到i位置的前一个结点
Node pre = head;
for(int index=0;index<i;index++){
pre=pre.next;
}
//找到i位置的结点
Node curr = pre.next;
//创建新结点
Node newNode = new Node(t, pre, curr);
//让i位置的前一个结点的下一个结点变为新结点
pre.next=newNode;
//让i位置的前一个结点变为新结点
curr.pre=newNode;
//元素个数+1
N++;
}
//获取指定位置i处的元素
public T get(int i){
Node n = head.next;
for(int index=0;index<i;index++){
n=n.next;
}
return n.item;
}
//找到元素t在链表中第一次出现的位置
public int indexOf(T t){
Node n = head;
for(int i=0;n.next!=null;i++){
n=n.next;
if (n.next.equals(t)){
return i;
}
}
return -1;
}
//删除位置i处的元素，并返回该元素
public T remove(int i){
//找到i位置的前一个结点
Node pre = head;
for(int index=0;index<i;index++){
pre=pre.next;
}
//找到i位置的结点
Node curr = pre.next;
//找到i位置的下一个结点
Node nextNode= curr.next;
//让i位置的前一个结点的下一个结点变为i位置的下一个结点
pre.next=nextNode;
//让i位置的下一个结点的上一个结点变为i位置的前一个结点
nextNode.pre=pre;
//元素的个数-1
N--;
return curr.item;
}
@Override
public Iterator<T> iterator() {
return new TIterator();
}
private class TIterator implements Iterator{
private Node n;
public TIterator(){
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n=n.next;
return n.item;
}
}
}
测试
public class TowWayLinkListTest {
public static void main(String[] args) {
//创建双向链表对象
TowWayLinkList<String> sl = new TowWayLinkList<>();
//测试插入
sl.insert("姚明");
sl.insert("科比");
sl.insert("麦迪");
sl.insert(1,"詹姆斯");
for (String s : sl) {
System.out.println(s);
}
System.out.println("--------------------------------------");
System.out.println("第一个元素是："+sl.getFirst());
System.out.println("最后一个元素是："+sl.getLast());
System.out.println("------------------------------------------");
//测试获取
String getResult = sl.get(1);
System.out.println("获取索引1处的结果为："+getResult);
//测试删除
String removeResult = sl.remove(0);
System.out.println("删除的元素是："+removeResult);
//测试清空
sl.clear();
System.out.println("清空后的线性表中的元素个数为:"+sl.length());
}
}
java中LinkedList集合也是使用双向链表实现，结点类有三个域，并提供了增删改查等相关方法。
链表的物理地址是不连续的，它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作,同时它并没有涉及的元素的交换。
相比较顺序表，链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。
快慢指针
快慢指针获取中间值。slow与fast指针都指向链表第一个节点，然后slow每次移动一个指针，fast每次移动两个指针。
public class FastSlowTest {
public static void main(String[] args) throws Exception {
//创建结点
Node<String> first = new Node<String>("aa", null);
Node<String> second = new Node<String>("bb", null);
Node<String> third = new Node<String>("cc", null);
Node<String> fourth = new Node<String>("dd", null);
Node<String> fifth = new Node<String>("ee", null);
Node<String> six = new Node<String>("ff", null);
Node<String> seven = new Node<String>("gg", null);
//完成结点之间的指向
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
fifth.next = six;
six.next = seven;
//查找中间值
String mid = getMid(first);
System.out.println("中间值为："+mid);
}
/**
* @param first 链表的首结点
* @return 链表的中间结点的值
*/
public static String getMid(Node<String> first) {
//定义两个指针
Node<String> fast = first;
Node<String> slow = first;
//使用两个指针遍历链表，当快指针指向的结点没有下一个结点了，就可以结束了，结束之后，慢指针指向的结点就是中间值
while(fast!=null &&fast.next!=null){
//变化fast的值和slow的值
fast = fast.next.next;
slow=slow.next;
}
return slow.item;
}
//结点类
private static class Node<T> {
//存储数据
T item;
//下一个结点
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
}
快慢指针检查是否有环。两个指针有速度差，那么迟早两个指针会相遇，只要相遇那么就说明有环。
public class CircleListCheckTest {
public static void main(String[] args) throws Exception {
//创建结点
Node<String> first = new Node<String>("aa", null);
Node<String> second = new Node<String>("bb", null);
Node<String> third = new Node<String>("cc", null);
Node<String> fourth = new Node<String>("dd", null);
Node<String> fifth = new Node<String>("ee", null);
Node<String> six = new Node<String>("ff", null);
Node<String> seven = new Node<String>("gg", null);
//完成结点之间的指向
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
fifth.next = six;
six.next = seven;
// //产生环
// seven.next = third;
//判断链表是否有环
boolean circle = isCircle(first);
System.out.println("first链表中是否有环："+circle);
}
/**
* 判断链表中是否有环
* @param first 链表首结点
* @return ture为有环，false为无环
*/
public static boolean isCircle(Node<String> first) {
//定义快慢指针
Node<String> fast = first;
Node<String> slow = first;
//遍历链表，如果快慢指针指向了同一个结点，那么证明有环
while(fast!=null && fast.next!=null){
//变换fast和slow
fast = fast.next.next;
slow = slow.next;
if (fast.equals(slow)){
return true;
}
}
return false;
}
//结点类
private static class Node<T> {
//存储数据
T item;
//下一个结点
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
}
快慢指针查找有环链表入口。当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新”指针相遇的地方就是环的入口。
public class CircleListInTest {
public static void main(String[] args) throws Exception {
Node<String> first = new Node<String>("aa", null);
Node<String> second = new Node<String>("bb", null);
Node<String> third = new Node<String>("cc", null);
Node<String> fourth = new Node<String>("dd", null);
Node<String> fifth = new Node<String>("ee", null);
Node<String> six = new Node<String>("ff", null);
Node<String> seven = new Node<String>("gg", null);
//完成结点之间的指向
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
fifth.next = six;
six.next = seven;
//产生环
seven.next = third;
//查找环的入口结点
Node<String> entrance = getEntrance(first);
System.out.println("first链表中环的入口结点元素为："+entrance.item);
}
/**
* 查找有环链表中环的入口结点
* @param first 链表首结点
* @return 环的入口结点
*/
public static Node getEntrance(Node<String> first) {
//定义快慢指针
Node<String> fast = first;
Node<String> slow = first;
Node<String> temp = null;
//遍历链表，先找到环(快慢指针相遇),准备一个临时指针，指向链表的首结点，继续遍历，直到慢指针和临时指针相遇，那么相遇时所指向的结点就是环的入口
while(fast!=null && fast.next!=null){
//变换快慢指针
fast = fast.next.next;
slow = slow.next;
//判断快慢指针是否相遇
if (fast.equals(slow)){
temp = first;
continue;
}
//让临时结点变换
if (temp!=null){
temp = temp.next;
//判断临时指针是否和慢指针相遇
if (temp.equals(slow)){
break;
}
}
}
return temp;
}
//结点类
private static class Node<T> {
//存储数据
T item;
//下一个结点
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
}
循环链表
在单向链表中，最后一个节点的指针为null，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。
约瑟夫问题
构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；使用计数器count，记录当前报数的值；遍历链表，每循环一次，count++；判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0。
public class JosephTest {
public static void main(String[] args) {
//解决约瑟夫问题
//1.构建循环链表，包含41个结点，分别存储1~41之间的值
//用来就首结点
Node<Integer> first = null;
//用来记录前一个结点
Node<Integer> pre = null;
for(int i = 1;i<=41;i++){
//如果是第一个结点
if (i==1){
first = new Node<>(i,null);
pre = first;
continue;
}
//如果不是第一个结点
Node<Integer> newNode = new Node<>(i, null);
pre.next=newNode;
pre=newNode;
//如果是最后一个结点，那么需要让最后一个结点的下一个结点变为first,变为循环链表了
if (i==41){
pre.next=first;
}
}
//2.需要count计数器，模拟报数
int count=0;
//3.遍历循环链表
//记录每次遍历拿到的结点，默认从首结点开始
Node<Integer> n = first;
//记录当前结点的上一个结点
Node<Integer> before = null;
while(n!=n.next){
//模拟报数
count++;
//判断当前报数是不是为3
if (count==3){
//如果是3，则把当前结点删除调用，打印当前结点，重置count=0，让当前结点n后移
before.next=n.next;
System.out.print(n.item+",");
count=0;
n=n.next;
}else{
//如果不是3，让before变为当前结点，让当前结点后移；
before=n;
n=n.next;
}
}
//打印最后一个元素
System.out.println(n.item);
}
//结点类
private static class Node<T> {
//存储数据
T item;
//下一个结点
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
}
栈
栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。
代码实现
压栈、弹栈、遍历。
public class Stack<T> implements Iterable<T>{
//记录首结点
private Node head;
//栈中元素的个数
private int N;
private class Node{
public T item;
public Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
public Stack() {
this.head = new Node(null,null);
this.N=0;
}
//判断当前栈中元素个数是否为0
public boolean isEmpty(){
return N==0;
}
//获取栈中元素的个数
public int size(){
return N;
}
//把t元素压入栈
public void push(T t){
//找到首结点指向的第一个结点
Node oldFirst = head.next;
//创建新结点
Node newNode = new Node(t, null);
//让首结点指向新结点
head.next = newNode;
//让新结点指向原来的第一个结点
newNode.next=oldFirst;
//元素个数+1；
N++;
}
//弹出栈顶元素
public T pop(){
//找到首结点指向的第一个结点
Node oldFirst = head.next;
if (oldFirst==null){
return null;
}
//让首结点指向原来第一个结点的下一个结点
head.next=oldFirst.next;
//元素个数-1；
N--;
return oldFirst.item;
}
@Override
public Iterator<T> iterator() {
return new SIterator();
}
private class SIterator implements Iterator{
private Node n;
public SIterator(){
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n = n.next;
return n.item;
}
}
}-
测试
public class StackTest {
public static void main(String[] args) {
//创建栈对象
Stack<String> stack = new Stack<>();
//测试压栈
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
for (String item : stack) {
System.out.println(item);
}
System.out.println("------------------------------");
//测试弹栈
String result = stack.pop();
System.out.println("弹出的元素是："+result);
System.out.println("剩余的元素个数："+stack.size());
}
}
括号匹配问题
给定一个字符串，里边可能包含”()”小括号和其他字符，请编写程序检查该字符串的中的小括号是否成对出现。
创建一个栈用来存储左括号；从左往右遍历字符串，拿到每一个字符；判断该字符是不是左括号，如果是，放入栈中存储；判断该字符是不是右括号，如果不是，继续下一次循环；如果该字符是右括号，则从栈中弹出一个元素t；判断元素t是否为null，如果不是，则证明有对应的左括号，如果不是，则证明没有对应的左括号；循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配。
public class BracketsMatchTest {
public static void main(String[] args) {
String str = "上海(长安)())";
boolean match = isMatch(str);
System.out.println(str+"中的括号是否匹配："+match);
}
/**
* 判断str中的括号是否匹配
* @param str 括号组成的字符串
* @return 如果匹配，返回true，如果不匹配，返回false
*/
public static boolean isMatch(String str){
//1.创建栈对象，用来存储左括号
Stack<String> chars = new Stack<>();
//2.从左往右遍历字符串
for (int i = 0; i < str.length(); i++) {
String currChar = str.charAt(i)+ "";
//3.判断当前字符是否为左括号，如果是，则把字符放入到栈中
if (currChar.equals("(")){
chars.push(currChar);
}else if(currChar.equals(")")){
//4.继续判断当前字符是否是有括号，如果是，则从栈中弹出一个左括号，并判断弹出的结果是否为null,如果为null证明没有匹配的左括号，如果不为null，则证明有匹配的左括号
String pop = chars.pop();
if (pop==null){
return false;
}
}
}
//5.判断栈中还有没有剩余的左括号，如果有，则证明括号不匹配
if (chars.size()==0){
return true;
}else{
return false;
}
}
}
逆波兰表达式求值
创建一个栈对象oprands存储操作数；从左往右遍历逆波兰表达式，得到每一个字符串；判断该字符串是不是运算符，如果不是，把该该操作数压入oprands栈中；如果是运算符，则从oprands栈中弹出两个操作数o1,o2；使用该运算符计算o1和o2，得到结果result；把该结果压入oprands栈中 ；遍历结束后，拿出栈中最终的结果返回。
public class ReversePolishNotationTest {
public static void main(String[] args) {
//中缀表达式 3*（17-15）+18/6 的逆波兰表达式如下 6+3=9
String[] notation = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};
int result = caculate(notation);
System.out.println("逆波兰表达式的结果为：" + result);
}
/**
* @param notaion 逆波兰表达式的数组表示方式
* @return 逆波兰表达式的计算结果
*/
public static int caculate(String[] notaion) {
//1.定义一个栈，用来存储操作数
Stack<Integer> oprands = new Stack<>();
//2.从左往右遍历逆波兰表达式，得到每一个元素
for (int i = 0; i < notaion.length; i++) {
String curr = notaion[i];
//3.判断当前元素是运算符还是操作数
Integer o1;
Integer o2;
Integer result;
switch (curr) {
case "+":
//4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中
o1 = oprands.pop();
o2 = oprands.pop();
result = o2 + o1;
oprands.push(result);
break;
case "-":
//4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中
o1 = oprands.pop();
o2 = oprands.pop();
result = o2 - o1;
oprands.push(result);
break;
case "*":
//4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中
o1 = oprands.pop();
o2 = oprands.pop();
result = o2 * o1;
oprands.push(result);
break;
case "/":
//4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中
o1 = oprands.pop();
o2 = oprands.pop();
result = o2 / o1;
oprands.push(result);
break;
default:
//5.操作数，把该操作数放入到栈中；
oprands.push(Integer.parseInt(curr));
break;
}
}
//6.得到栈中最后一个元素，就是逆波兰表达式的结果
int result = oprands.pop();
return result;
}
}
队列
队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来。
实现
插入、删除、遍历。
public class Queue<T> implements Iterable<T>{
//记录首结点
private Node head;
//记录最后一个结点
private Node last;
//记录队列中元素的个数
private int N;
private class Node{
public T item;
public Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
public Queue() {
this.head = new Node(null,null);
this.last=null;
this.N=0;
}
//判断队列是否为空
public boolean isEmpty(){
return N==0;
}
//返回队列中元素的个数
public int size(){
return N;
}
//向队列中插入元素t
public void enqueue(T t){
if (last==null){
//当前尾结点last为null
last= new Node(t,null);
head.next=last;
} else {
//当前尾结点last不为null
Node oldLast = last;
last = new Node(t, null);
oldLast.next=last;
}
//元素个数+1
N++;
}
//从队列中拿出一个元素
public T dequeue(){
if (isEmpty()){
return null;
}
Node oldFirst = head.next;
head.next = oldFirst.next;
N--;
//因为出队列其实是在删除元素，因此如果队列中的元素被删除完了，需要重置last=null;
if (isEmpty()){
last=null;
}
return oldFirst.item;
}
@Override
public Iterator<T> iterator() {
return new QIterator();
}
private class QIterator implements Iterator{
private Node n;
public QIterator(){
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n = n.next;
return n.item;
}
}
}
测试
public class QueueTest {
public static void main(String[] args) {
//创建队列对象
Queue<String> q = new Queue<>();
//测试队列的enqueue方法
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
q.enqueue("d");
for (String str : q) {
System.out.println(str);
}
System.out.println("-------------------------------");
//测试队列的dequeue方法
String result = q.dequeue();
System.out.println("出队列的元素是："+result);
System.out.println("剩余的元素个数："+q.size());
}
}
符号表
符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值。符号表中，键具有唯一性。
实现
public class SymbolTable<Key,Value> {
//记录首结点
private Node head;
//记录符号表中元素的个数
private int N;
private class Node{
//键
public Key key;
//值
public Value value;
//下一个结点
public Node next;
public Node(Key key, Value value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
public SymbolTable() {
this.head = new Node(null,null,null);
this.N=0;
}
//获取符号表中键值对的个数
public int size(){
return N;
}
//往符号表中插入键值对
public void put(Key key,Value value){
//符号表中已经存在了键为key的键值对，那么只需要找到该结点，替换值为value即可
Node n = head;
while(n.next!=null){
//变换n
n = n.next;
//判断n结点存储的键是否为key，如果是，则替换n结点的值
if (n.key.equals(key)){
n.value = value;
return;
}
}
//如果符号表中不存在键为key的键值对，只需要创建新的结点，保存要插入的键值对，把新结点插入到链表的头部 head.next=新结点即可
Node newNode = new Node(key, value, null);
Node oldFirst = head.next;
newNode.next = oldFirst;
head.next = newNode;
//元素个数+1；
N++;
}
//删除符号表中键为key的键值对
public void delete(Key key){
//找到键为key的结点，把该结点从链表中删除
Node n = head;
while(n.next!=null){
//判断n结点的下一个结点的键是否为key，如果是，就删除该结点
if (n.next.key.equals(key)){
n.next = n.next.next;
N--;
return;
}
//变换n
n = n.next;
}
}
//从符号表中获取key对应的值
public Value get(Key key){
//找到键为key的结点
Node n = head;
while(n.next!=null){
//变换n
n = n.next;
if (n.key.equals(key)){
return n.value;
}
}
return null;
}
}
测试
public class SymbolTableTest {
public static void main(String[] args) {
//创建符号表对象
SymbolTable<Integer, String> symbolTable = new SymbolTable<>();
//测试put方法（插入,替换）
symbolTable.put(1,"乔峰");
symbolTable.put(2,"虚竹");
symbolTable.put(3,"段誉");
System.out.println("插入完毕后，元素的个数为:"+symbolTable.size());
symbolTable.put(2, "慕容复");
System.out.println("替换完毕后的元素的个数为:"+symbolTable.size());
//测试get方法
System.out.println("替换完毕后，键2对应的值为:"+symbolTable.get(2));
//测试删除方法
symbolTable.delete(2);
System.out.println("删除完毕后，元素的个数:"+symbolTable.size());
}
}
有序符号表
要根据键的大小进行排序，插入数据时要考虑顺序。
public class OrderSymbolTable<Key extends Comparable<Key>,Value> {
//记录首结点
private Node head;
//记录符号表中元素的个数
private int N;
private class Node{
//键
public Key key;
//值
public Value value;
//下一个结点
public Node next;
public Node(Key key, Value value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
public OrderSymbolTable() {
this.head = new Node(null,null,null);
this.N=0;
}
//获取符号表中键值对的个数
public int size(){
return N;
}
//往符号表中插入键值对
public void put(Key key,Value value){
//定义两个Node变量，分别记录当前结点和当前结点的上一个结点
Node curr = head.next;
Node pre = head;
while(curr!=null && key.compareTo(curr.key)>0){
//变换当前结点和前一个结点即可
pre = curr;
curr = curr.next;
}
//如果当前结点curr的键和要插入的key一样，则替换
if (curr!=null && key.compareTo(curr.key)==0){
curr.value = value;
return;
}
//如果当前结点curr的键和要插入的key不一样，把新的结点插入到curr之前
Node newNode = new Node(key, value, curr);
pre.next = newNode;
//元素的个数+1；
N++;
}
//删除符号表中键为key的键值对
public void delete(Key key){
//找到键为key的结点，把该结点从链表中删除
Node n = head;
while(n.next!=null){
//判断n结点的下一个结点的键是否为key，如果是，就删除该结点
if (n.next.key.equals(key)){
n.next = n.next.next;
N--;
return;
}
//变换n
n = n.next;
}
}
//从符号表中获取key对应的值
public Value get(Key key){
//找到键为key的结点
Node n = head;
while(n.next!=null){
//变换n
n = n.next;
if (n.key.equals(key)){
return n.value;
}
}
return null;
}
}
测试
public class OrderSymbolTableTest {
public static void main(String[] args) {
//创建有序符号表对象
OrderSymbolTable<Integer, String> table = new OrderSymbolTable<>();
table.put(1,"张三");
table.put(2,"李四");
table.put(4,"赵六");
table.put(7,"田七");
table.put(3,"王五");
}
}
二叉树
定义
树是由n（n>=1）个有限结点组成一个具有层次关系的集合。树具有以下特点：每个结点有零个或多个子结点；没有父结点的结点为根结点；每一个非根结点只有一个父结点；每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树。
结点的度：一个结点含有的子树的个数称为该结点的度。
叶结点：度为0的结点称为叶结点，也可以叫做终端结点。
分支结点：度不为0的结点称为分支结点，也可以叫做非终端结点。
结点的层次：从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推。
结点的层序编号：将树中的结点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数。
树的度：树中所有结点的度的最大值。
树的高度(深度)：树中结点的最大层次。
森林：m（m>=0）个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根结点，森林就变成一棵树。
孩子结点：一个结点的直接后继结点称为该结点的孩子结点。
双亲结点(父结点)：一个结点的直接前驱称为该结点的双亲结点。
兄弟结点：同一双亲结点的孩子结点间互称兄弟结点。
二叉树就是度不超过2的树(每个结点最多有两个子结点)。
一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
二叉查找树基于链表的实现
插入方法put实现思想：如果当前树中没有任何一个结点，则直接把新结点当做根结点使用。如果当前树不为空，则从根结点开始：如果新结点的key小于当前结点的key，则继续找当前结点的左子结点；如果新结点的key大于当前结点的key，则继续找当前结点的右子结点；如果新结点的key等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值即可。
查询方法get实现思想：从根节点开始：如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；如果要查询的key等于当前结点的key，则树中返回当前结点的value。
删除方法delete实现思想：找到被删除结点；找到被删除结点右子树中的最小结点minNode；删除右子树中的最小结点；让被删除结点的左子树称为最小结点minNode的左子树，让被删除结点的右子树称为最小结点minNode的右子树；让被删除结点的父节点指向最小结点minNode。
查找最小键、查找最大键。
把树由一个根节点、一个左子树、一个右子树组成，那么按照根节点什么时候被访问，我们可以把二叉树的遍历分为以下三种方式：
前序遍历：先访问根结点，然后再访问左子树，最后访问右子树。中序遍历：先访问左子树，中间访问根节点，最后访问右子树。后序遍历：先访问左子树，再访问右子树，最后访问根节点。
前序遍历步骤：把当前结点的key放入到队列中;找到当前结点的左子树，如果不为空，递归遍历左子树；找到当前结点的右子树，如果不为空，递归遍历右子树。
中序遍历实现步骤：找到当前结点的左子树，如果不为空，递归遍历左子树；把当前结点的key放入到队列中;找到当前结点的右子树，如果不为空，递归遍历右子树。
后序遍历实现步骤：找到当前结点的左子树，如果不为空，递归遍历左子树；找到当前结点的右子树，如果不为空，递归遍历右子树；把当前结点的key放入到队列中。
层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值。实现步骤：创建队列，存储每一层的结点；使用循环从队列中弹出一个结点：获取当前结点的key；如果当前结点的左子结点不为空，则把左子结点放入到队列中；如果当前结点的右子结点不为空，则把右子结点放入到队列中。
最大深度：如果根结点为空，则最大深度为0；计算左子树的最大深度；计算右子树的最大深度；当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1。
public class BinaryTree<Key extends Comparable<Key>, Value> {
//记录根结点
private Node root;
//记录树中元素的个数
private int N;
private class Node {
//存储键
public Key key;
//存储值
private Value value;
//记录左子结点
public Node left;
//记录右子结点
public Node right;
public Node(Key key, Value value, Node left, Node right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
//获取树中元素的个数
public int size() {
return N;
}
//向树中添加元素key-value
public void put(Key key, Value value) {
root = put(root, key, value);
}
//向指定的树x中添加key-value,并返回添加元素后新的树
private Node put(Node x, Key key, Value value) {
//如果x子树为空，
if (x==null){
N++;
return new Node(key,value, null,null);
}
//如果x子树不为空
//比较x结点的键和key的大小：
int cmp = key.compareTo(x.key);
if (cmp>0){
//如果key大于x结点的键，则继续找x结点的右子树
x.right = put(x.right,key,value);
}else if(cmp<0){
//如果key小于x结点的键，则继续找x结点的左子树
x.left = put(x.left,key,value);
}else{
//如果key等于x结点的键，则替换x结点的值为value即可
x.value = value;
}
return x;
}
//查询树中指定key对应的value
public Value get(Key key) {
return get(root,key);
}
//从指定的树x中，查找key对应的值
public Value get(Node x, Key key) {
//x树为null
if (x==null){
return null;
}
//x树不为null
//比较key和x结点的键的大小
int cmp = key.compareTo(x.key);
if (cmp>0){
//如果key大于x结点的键，则继续找x结点的右子树
return get(x.right,key);
}else if(cmp<0){
//如果key小于x结点的键，则继续找x结点的左子树
return get(x.left,key);
}else{
//如果key等于x结点的键，就找到了键为key的结点，只需要返回x结点的值即可
return x.value;
}
}
//删除树中key对应的value
public void delete(Key key) {
delete(root, key);
}
//删除指定树x中的key对应的value，并返回删除后的新树
public Node delete(Node x, Key key) {
//x树为null
if (x==null){
return null;
}
//x树不为null
int cmp = key.compareTo(x.key);
if (cmp>0){
//如果key大于x结点的键，则继续找x结点的右子树
x.right = delete(x.right,key);
}else if(cmp<0){
//如果key小于x结点的键，则继续找x结点的左子树
x.left = delete(x.left,key);
}else{
//如果key等于x结点的键，完成真正的删除结点动作，要删除的结点就是x；
//让元素个数-1
N--;
//得找到右子树中最小的结点
if (x.right==null){
return x.left;
}
if (x.left==null){
return x.right;
}
Node minNode = x.right;
while(minNode.left!=null){
minNode = minNode.left;
}
//删除右子树中最小的结点
Node n = x.right;
while(n.left!=null){
if (n.left.left==null){
n.left=null;
}else{
//变换n结点即可
n = n.left;
}
}
//让x结点的左子树成为minNode的左子树
minNode.left = x.left;
//让x结点的右子树成为minNode的右子树
minNode.right = x.right;
//让x结点的父结点指向minNode
x = minNode;
}
return x;
}
//查找整个树中最小的键
public Key min(){
return min(root).key;
}
//在指定树x中找出最小键所在的结点
private Node min(Node x){
//需要判断x还有没有左子结点，如果有，则继续向左找，如果没有，则x就是最小键所在的结点
if (x.left!=null){
return min(x.left);
}else{
return x;
}
}
//在整个树中找到最大的键
public Key max(){
return max(root).key;
}
//在指定的树x中，找到最大的键所在的结点
public Node max(Node x){
//判断x还有没有右子结点，如果有，则继续向右查找，如果没有，则x就是最大键所在的结点
if (x.right!=null){
return max(x.right);
}else{
return x;
}
}
//获取整个树中所有的键
public Queue<Key> preErgodic(){
Queue<Key> keys = new Queue<>();
preErgodic(root, keys);
return keys;
}
//获取指定树x的所有键，并放到keys队列中
private void preErgodic(Node x,Queue<Key> keys){
if (x==null){
return;
}
//把x结点的key放入到keys中
keys.enqueue(x.key);
//递归遍历x结点的左子树
if (x.left!=null){
preErgodic(x.left,keys);
}
//递归遍历x结点的右子树
if (x.right!=null){
preErgodic(x.right,keys);
}
}
//使用中序遍历获取树中所有的键
public Queue<Key> midErgodic(){
Queue<Key> keys = new Queue<>();
midErgodic(root,keys);
return keys;
}
//使用中序遍历，获取指定树x中所有的键，并存放到key中
private void midErgodic(Node x,Queue<Key> keys){
if (x==null){
return;
}
//先递归，把左子树中的键放到keys中
if (x.left!=null){
midErgodic(x.left,keys);
}
//把当前结点x的键放到keys中
keys.enqueue(x.key);
//在递归，把右子树中的键放到keys中
if(x.right!=null){
midErgodic(x.right,keys);
}
}
//使用后序遍历，把整个树中所有的键返回
public Queue<Key> afterErgodic(){
Queue<Key> keys = new Queue<>();
afterErgodic(root,keys);
return keys;
}
//使用后序遍历，把指定树x中所有的键放入到keys中
private void afterErgodic(Node x,Queue<Key> keys){
if (x==null){
return ;
}
//通过递归把左子树中所有的键放入到keys中
if (x.left!=null){
afterErgodic(x.left,keys);
}
//通过递归把右子树中所有的键放入到keys中
if (x.right!=null){
afterErgodic(x.right,keys);
}
//把x结点的键放入到keys中
keys.enqueue(x.key);
}
//使用层序遍历，获取整个树中所有的键
public Queue<Key> layerErgodic(){
//定义两个队列，分别存储树中的键和树中的结点
Queue<Key> keys = new Queue<>();
Queue<Node> nodes = new Queue<>();
//默认，往队列中放入根结点
nodes.enqueue(root);
while(!nodes.isEmpty()){
//从队列中弹出一个结点，把key放入到keys中
Node n = nodes.dequeue();
keys.enqueue(n.key);
//判断当前结点还有没有左子结点，如果有，则放入到nodes中
if (n.left!=null){
nodes.enqueue(n.left);
}
//判断当前结点还有没有右子结点，如果有，则放入到nodes中
if (n.right!=null){
nodes.enqueue(n.right);
}
}
return keys;
}
//获取整个树的最大深度
public int maxDepth(){
return maxDepth(root);
}
//获取指定树x的最大深度
private int maxDepth(Node x){
if (x==null){
return 0;
}
//x的最大深度
int max=0;
//左子树的最大深度
int maxL=0;
//右子树的最大深度
int maxR=0;
//计算x结点左子树的最大深度
if (x.left!=null){
maxL = maxDepth(x.left);
}
//计算x结点右子树的最大深度
if (x.right!=null){
maxR = maxDepth(x.right);
}
//比较左子树最大深度和右子树最大深度，取较大值+1即可
max = maxL>maxR?maxL+1:maxR+1;
return max;
}
}
代码测试
public class BinaryTreeTest {
public static void main(String[] args) {
//创建二叉查找树对象
BinaryTree<Integer, String> tree = new BinaryTree<>();
//测试插入
tree.put(1,"张三");
tree.put(2,"李四");
tree.put(3,"王五");
System.out.println("插入完毕后元素的个数："+tree.size());
//测试获取
System.out.println("键2对应的元素是："+tree.get(2));
//测试删除
tree.delete(3);
System.out.println("删除后的元素个数："+tree.size());
System.out.println("删除后键3对应的元素:"+tree.get(3));
}
}
遍历测试
public class BinaryTreeErgodicTest {
/*//测试前序遍历
public static void main(String[] args) {
//创建树对象
BinaryTree<String, String> tree = new BinaryTree<>();
//往树中添加数据
tree.put("E", "5");
tree.put("B", "2");
tree.put("G", "7");
tree.put("A", "1");
tree.put("D", "4");
tree.put("F", "6");
tree.put("H", "8");
tree.put("C", "3");
//遍历
Queue<String> keys = tree.preErgodic();
for (String key : keys) {
String value = tree.get(key);
System.out.println(key+"----"+value);
}
}*/
//测试中序遍历
/* public static void main(String[] args) {
//创建树对象
BinaryTree<String, String> tree = new BinaryTree<>();
//往树中添加数据
tree.put("E", "5");
tree.put("B", "2");
tree.put("G", "7");
tree.put("A", "1");
tree.put("D", "4");
tree.put("F", "6");
tree.put("H", "8");
tree.put("C", "3");
//遍历
Queue<String> keys = tree.midErgodic();
for (String key : keys) {
String value = tree.get(key);
System.out.println(key+"----"+value);
}
}*/
//测试后序遍历
/*public static void main(String[] args) {
//创建树对象
BinaryTree<String, String> tree = new BinaryTree<>();
//往树中添加数据
tree.put("E", "5");
tree.put("B", "2");
tree.put("G", "7");
tree.put("A", "1");
tree.put("D", "4");
tree.put("F", "6");
tree.put("H", "8");
tree.put("C", "3");
//遍历
Queue<String> keys = tree.afterErgodic();
for (String key : keys) {
String value = tree.get(key);
System.out.println(key+"----"+value);
}
}*/
//测试层序遍历
public static void main(String[] args) {
//创建树对象
BinaryTree<String, String> tree = new BinaryTree<>();
//往树中添加数据
tree.put("E", "5");
tree.put("B", "2");
tree.put("G", "7");
tree.put("A", "1");
tree.put("D", "4");
tree.put("F", "6");
tree.put("H", "8");
tree.put("C", "3");
//遍历
Queue<String> keys = tree.layerErgodic();
for (String key : keys) {
String value = tree.get(key);
System.out.println(key+"----"+value);
}
}
}
最大深度测试
public class BinaryTreeMaxDepthTest {
public static void main(String[] args) {
//创建树对象
BinaryTree<String, String> tree = new BinaryTree<>();
//往树中添加数据
tree.put("E", "5");
tree.put("B", "2");
tree.put("G", "7");
tree.put("A", "1");
tree.put("D", "4");
tree.put("F", "6");
tree.put("H", "8");
tree.put("C", "3");
int maxDepth = tree.maxDepth();
System.out.println(maxDepth);
}
}
折纸问题
纸条对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。连续对折N次，请从上到下打印所有折痕的方向 例如：N=1时，打印： down；N=2时，打印： down down up。
根结点为下折痕；每一个结点的左子结点为下折痕；每一个结点的右子结点为上折痕。
public class PagerFoldingTest {
public static void main(String[] args) {
//模拟这只过程，产生树
Node<String> tree = createTree(2);
//遍历树，打印每个结点
printTree(tree);
}
//通过模拟对折N次纸，产生树
public static Node<String> createTree(int N){
//定义根结点
Node<String> root=null;
for (int i = 0; i < N; i++) {
//1.当前是第一次对折
if (i==0){
root = new Node<>("down",null,null);
continue;
}
//2.当前不是第一次对折
//定义一个辅助队列，通过层序遍历的思想，找到叶子结点，叶子结点添加子节点
Queue<Node> queue = new Queue<>();
queue.enqueue(root);
//循环遍历队列
while(!queue.isEmpty()){
//从队列中弹出一个结点
Node<String> tmp = queue.dequeue();
//如果有左子结点，则把左子结点放入到队列中
if (tmp.left!=null){
queue.enqueue(tmp.left);
}
//如果有右子结点，则把右子结点放入到队列中
if (tmp.right!=null){
queue.enqueue(tmp.right);
}
//如果同时没有左子结点和右子结点，那么证明该节点是叶子结点，只需要给该节点添加左子结点和右子结点即可
if (tmp.left==null && tmp.right==null){
tmp.left = new Node<String>("down", null,null);
tmp.right = new Node<String>("up",null,null);
}
}
}
return root;
}
//打印树中每个结点到控制台
public static void printTree(Node<String> root){
//需要使用中序遍历完成
if (root==null){
return;
}
//打印左子树的每个结点
if (root.left!=null){
printTree(root.left);
}
//打印当前结点
System.out.print(root.item+" ");
//打印右子树的每个结点
if (root.right!=null){
printTree(root.right);
}
}
//结点类
private static class Node<T>{
public T item;//存储元素
public Node left;
public Node right;
public Node(T item, Node left, Node right) {
this.item = item;
this.left = left;
this.right = right;
}
}
}
堆
堆通常可以被看做是一棵完全二叉树的数组对象。
完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。
二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子结点则分别在位置4,5,6和7，以此类推。
如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。
每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟之前的二叉查找树是有区别的。
API实现
如果往堆中新插入元素，我们只需要不断的比较新结点a[k]和它的父结点a[k/2]的大小，然后根据结果完成数据元素的交换，就可以完成堆的有序调整。
当删除掉最大元素后，只需要将最后一个元素放到索引1处，并不断的拿着当前结点a[k]与它的子结点a[2k]和a[2k+1]中的较大者交换位置，即可完成堆的有序调整。
public class Heap<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//记录堆中元素的个数
private int N;
public Heap(int capacity) {
this.items= (T[]) new Comparable[capacity+1];
this.N=0;
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i,int j){
return items[i].compareTo(items[j])<0;
}
//交换堆中i索引和j索引处的值
private void exch(int i,int j){
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
//往堆中插入一个元素
public void insert(T t){
items[++N]=t;
swim(N);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k){
//通过循环，不断的比较当前结点的值和其父结点的值，如果发现父结点的值比当前结点的值小，则交换位置
while(k>1){
//比较当前结点和其父结点
if (less(k/2,k)){
exch(k/2,k);
}
k = k/2;
}
}
//删除堆中最大的元素,并返回这个最大元素
public T delMax(){
T max = items[1];
//交换索引1处的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根结点
exch(1,N);
//最大索引处的元素删除掉
items[N]=null;
//元素个数-1
N--;
//通过下沉调整堆，让堆重新有序
sink(1);
return max;
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k){
//通过循环不断的对比当前k结点和其左子结点2*k以及右子结点2k+1处中的较大值的元素大小，如果当前结点小，则需要交换位置
while(2*k<=N){
//获取当前结点的子结点中的较大结点
int max;//记录较大结点所在的索引
if (2*k+1<=N){
if (less(2*k,2*k+1)){
max=2*k+1;
}else{
max=2*k;
}
}else {
max = 2*k;
}
//比较当前结点和较大结点的值
if (!less(k,max)){
break;
}
//交换k索引处的值和max索引处的值
exch(k,max);
//变换k的值
k = max;
}
}
public static void main(String[] args) {
Heap<String> heap = new Heap<String>(20);
heap.insert("A");
heap.insert("B");
heap.insert("C");
heap.insert("D");
heap.insert("E");
heap.insert("F");
heap.insert("G");
String del;
while((del=heap.delMax())!=null){
System.out.print(del+",");
}
}
}
测试
public class HeapTest {
public static void main(String[] args) {
//创建堆对象
Heap<String> heap = new Heap<>(10);
//往堆中存入字符串数据
heap.insert("A");
heap.insert("B");
heap.insert("C");
heap.insert("D");
heap.insert("E");
heap.insert("F");
heap.insert("G");
//通过循环从堆中删除数据
String result = null;
while((result = heap.delMax())!=null){
System.out.print(result+" ");
}
}
}
利用堆进行排序
构造堆；得到堆顶元素，这个值就是最大值；交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；重复上述步骤，直到堆中剩一个元素为止。
堆构造过程：创建一个新数组，把原数组0length-1的数据拷贝到新数组的1length处，再从新数组长度的一半处开始往1索引处扫描（从右往左），然后对扫描到的每一个元素做下沉调整即可。
堆排序过程：对构造好的堆，我们只需要做类似于堆的删除操作，就可以完成排序。将堆顶元素和堆中最后一个元素交换位置；通过对堆顶元素下沉调整堆，把最大的元素放到堆顶(此时最后一个元素不参与堆的调整，因为最大的数据已经到了数组的最右边)；重复上面步骤，直到堆中剩最后一个元素。
实现：
public class HeapSort {
//判断heap堆中索引i处的元素是否小于索引j处的元素
private static boolean less(Comparable[] heap, int i, int j) {
return heap[i].compareTo(heap[j])<0;
}
//交换heap堆中i索引和j索引处的值
private static void exch(Comparable[] heap, int i, int j) {
Comparable tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
//根据原数组source，构造出堆heap
private static void createHeap(Comparable[] source, Comparable[] heap) {
//把source中的元素拷贝到heap中，heap中的元素就形成一个无序的堆
System.arraycopy(source,0,heap,1,source.length);
//对堆中的元素做下沉调整(从长度的一半处开始，往索引1处扫描)
for (int i = (heap.length)/2;i>0;i--){
sink(heap,i,heap.length-1);
}
}
//对source数组中的数据从小到大排序
public static void sort(Comparable[] source) {
//构建堆
Comparable[] heap = new Comparable[source.length+1];
createHeap(source,heap);
//定义一个变量，记录未排序的元素中最大的索引
int N = heap.length-1;
//通过循环，交换1索引处的元素和排序的元素中最大的索引处的元素
while(N!=1){
//交换元素
exch(heap,1,N);
//排序交换后最大元素所在的索引，让它不要参与堆的下沉调整
N--;
//需要对索引1处的元素进行对的下沉调整
sink(heap,1, N);
}
//把heap中的数据复制到原数组source中
System.arraycopy(heap,1,source,0,source.length);
}
//在heap堆中，对target处的元素做下沉，范围是0~range
private static void sink(Comparable[] heap, int target, int range){
while(2*target<=range){
//1.找出当前结点的较大的子结点
int max;
if (2*target+1<=range){
if (less(heap,2*target,2*target+1)){
max = 2*target+1;
}else{
max = 2*target;
}
}else{
max = 2*target;
}
//2.比较当前结点的值和较大子结点的值
if (!less(heap,target,max)){
break;
}
exch(heap,target,max);
target = max;
}
}
}
测试
public class HeapSortTest {
public static void main(String[] args) {
//待排序数组
String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"};
//通过HeapSort对数组中的元素进行排序
HeapSort.sort(arr);
//打印排序后数组中的元素
System.out.println(Arrays.toString(arr));
}
}
优先队列
最大优先队列
可以获取并删除队列中最大的值。基于堆区实现最大优先队列。
public class MaxPriorityQueue<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//记录堆中元素的个数
private int N;
public MaxPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity+1];
this.N= 0;
}
//获取队列中元素的个数
public int size() {
return N;
}
//判断队列是否为空
public boolean isEmpty() {
return N==0;
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i, int j) {
return items[i].compareTo(items[j])<0;
}
//交换堆中i索引和j索引处的值
private void exch(int i, int j) {
T tmp = items[i];
items[i] = items[j];
items[j] = tmp;
}
//往堆中插入一个元素
public void insert(T t) {
items[++N] = t;
swim(N);
}
//删除堆中最大的元素,并返回这个最大元素
public T delMax() {
T max = items[1];
exch(1,N);
N--;
sink(1);
return max;
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k) {
while(k>1){
if (less(k/2,k)){
exch(k/2,k);
}
k = k/2;
}
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
while(2*k<=N){
int max;
if (2*k+1<=N){
if (less(2*k,2*k+1)){
max=2*k+1;
}else{
max = 2*k;
}
}else {
max = 2*k;
}
if (!less(k,max)){
break;
}
exch(k,max);
k = max;
}
}
}
测试
public class MaxPriorityQueueTest {
public static void main(String[] args) {
//创建优先队列
MaxPriorityQueue<String> queue = new MaxPriorityQueue<>(10);
//往队列中存储元素
queue.insert("A");
queue.insert("B");
queue.insert("C");
queue.insert("D");
queue.insert("E");
queue.insert("F");
queue.insert("G");
//通过循环从队列中获取最大的元素
while(!queue.isEmpty()){
String max = queue.delMax();
System.out.print(max+" ");
}
}
}
最小优先队列
可以获取并删除队列中最小的值。基于堆来完成最小优先队列：最小的元素放在数组的索引1处；每个结点的数据总是小于等于它的两个子结点的数据。
public class MinPriorityQueue<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//记录堆中元素的个数
private int N;
public MinPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity+1];
this.N=0;
}
//获取队列中元素的个数
public int size() {
return N;
}
//判断队列是否为空
public boolean isEmpty() {
return N==0;
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i, int j) {
return items[i].compareTo(items[j])<0;
}
//交换堆中i索引和j索引处的值
private void exch(int i, int j) {
T tmp = items[i];
items[i] = items[j];
items[j] = tmp;
}
//往堆中插入一个元素
public void insert(T t) {
items[++N] = t;
swim(N);
}
//删除堆中最小的元素,并返回这个最小元素
public T delMin() {
T min = items[1];
exch(1,N);
N--;
sink(1);
return min;
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k) {
//通过循环比较当前结点和其父结点的大小
while(k>1){
if (less(k,k/2)){
exch(k,k/2);
}
k = k/2;
}
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
//通过循环比较当前结点和其子结点中的较小值
while(2*k<=N){
//1.找到子结点中的较小值
int min;
if (2*k+1<=N){
if (less(2*k, 2*k+1)){
min = 2*k;
}else{
min = 2*k+1;
}
}else{
min = 2*k;
}
//2.判断当前结点和较小值的大小
if (less(k,min)){
break;
}
exch(k,min);
k = min;
}
}
}
测试
public class MinPriorityQueueTest {
public static void main(String[] args) {
//创建最小优先队列对象
MinPriorityQueue<String> queue = new MinPriorityQueue<String>(10);
//往队列中存数据
queue.insert("G");
queue.insert("F");
queue.insert("E");
queue.insert("D");
queue.insert("C");
queue.insert("B");
queue.insert("A");
//通过循环获取最小优先队列中的元素
while(!queue.isEmpty()){
String min = queue.delMin();
System.out.print(min+" ");
}
}
}
索引优先队列
存储数据时，给每一个数据元素关联一个整数，例如insert(int k,T t),我们可以看做k是t关联的整数，那么我们的实现需要通过k这个值，快速获取到队列中t这个元素，此时有个k这个值需要具有唯一性。
用一个T[] items数组来保存数据元素，在insert(int k,T t)完成插入时，可以把k看做是items数组的索引，把t元素放到items数组的索引k处，这样我们再根据k获取元素t时就很方便了，直接就可以拿到items[k]即可。
数组int[]pq,来保存每个元素在items数组中的索引，pq数组需要堆有序，也就是说，pq[1]对应的数据元素items[pq[1]]要小于等于pq[2]和pq[3]对应的数据元素items[pq[2]]和items[pq[3]]。
数组int[] qp,用来存储pq的逆序。例如：在pq数组中：pq[1]=6;那么在qp数组中，把6作为索引，1作为值，结果是：qp[6]=1。
代码实现
public class IndexMinPriorityQueue<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//保存每个元素在items数组中的索引，pq数组需要堆有序
private int[] pq;
//保存qp的逆序，pq的值作为索引，pq的索引作为值
private int[] qp;
//记录堆中元素的个数
private int N;
public IndexMinPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity+1];
this.pq = new int[capacity+1];
this.qp= new int[capacity+1];
this.N = 0;
//默认情况下，队列中没有存储任何数据，让qp中的元素都为-1；
for (int i = 0; i < qp.length; i++) {
qp[i]=-1;
}
}
//获取队列中元素的个数
public int size() {
return N;
}
//判断队列是否为空
public boolean isEmpty() {
return N==0;
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i, int j) {
return items[pq[i]].compareTo(items[pq[j]])<0;
}
//交换堆中i索引和j索引处的值
private void exch(int i, int j) {
//交换pq中的数据
int tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
//更新qp中的数据
qp[pq[i]]=i;
qp[pq[j]] =j;
}
//判断k对应的元素是否存在
public boolean contains(int k) {
return qp[k] !=-1;
}
//最小元素关联的索引
public int minIndex() {
return pq[1];
}
//往队列中插入一个元素,并关联索引i
public void insert(int i, T t) {
//判断i是否已经被关联，如果已经被关联，则不让插入
if (contains(i)){
return;
}
//元素个数+1
N++;
//把数据存储到items对应的i位置处
items[i] = t;
//把i存储到pq中
pq[N] = i;
//通过qp来记录pq中的i
qp[i]=N;
//通过堆上浮完成堆的调整
swim(N);
}
//删除队列中最小的元素,并返回该元素关联的索引
public int delMin() {
//获取最小元素关联的索引
int minIndex = pq[1];
//交换pq中索引1处和最大索引处的元素
exch(1,N);
//删除qp中对应的内容
qp[pq[N]] = -1;
//删除pq最大索引处的内容
pq[N]=-1;
//删除items中对应的内容
items[minIndex] = null;
//元素个数-1
N--;
//下沉调整
sink(1);
return minIndex;
}
//删除索引i关联的元素
public void delete(int i) {
//找到i在pq中的索引
int k = qp[i];
//交换pq中索引k处的值和索引N处的值
exch(k,N);
//删除qp中的内容
qp[pq[N]] = -1;
//删除pq中的内容
pq[N]=-1;
//删除items中的内容
items[k]=null;
//元素的数量-1
N--;
//堆的调整
sink(k);
swim(k);
}
//把与索引i关联的元素修改为为t
public void changeItem(int i, T t) {
//修改items数组中i位置的元素为t
items[i] = t;
//找到i在pq中出现的位置
int k = qp[i];
//堆调整
sink(k);
swim(k);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k) {
while(k>1){
if (less(k,k/2)){
exch(k,k/2);
}
k = k/2;
}
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
while(2*k<=N){
//找到子结点中的较小值
int min;
if (2*k+1<=N){
if (less(2*k,2*k+1)){
min = 2*k;
}else{
min = 2*k+1;
}
}else{
min = 2*k;
}
//比较当前结点和较小值
if (less(k,min)){
break;
}
exch(k,min);
k = min;
}
}
}
测试代码
public class IndexMinPriorityQueueTest {
public static void main(String[] args) {
//创建索引最小优先队列对象
IndexMinPriorityQueue<String> queue = new IndexMinPriorityQueue<>(10);
//往队列中添加元素
queue.insert(0,"A");
queue.insert(1,"C");
queue.insert(2,"F");
//测试修改
queue.changeItem(2,"B");
//测试删除
while(!queue.isEmpty()){
int index = queue.delMin();
System.out.print(index+" ");
}
}
}
平衡树
2-3查找树
2-结点：含有一个键(及其对应的值)和两条链，左链接指向2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
3-结点：含有两个键(及其对应的值)和三条链，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
查找：要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到指向相应区间的连接，并在其指向的子树中递归地继续查找。如果这个是空链接，查找未命中。
向2-结点中插入新键：查找后未找到的节点是一个2-结点，我们只需要将新的元素放到这个2-结点里面使其变成一个3-结点即可。
一棵完全平衡的2-3树具有以下性质：任意空链接到根结点的路径长度都是相等的。4-结点变换为3-结点时，树的高度不会发生变化，只有当根结点是临时的4-结点，分解根结点时，树高+1。2-3树与普通二叉查找树最大的区别在于，普通的二叉查找树是自顶向下生长，而2-3树是自底向上生长。
直接实现2-3树比较复杂，但是2-3查找树作为一种比较重要的概念和思路对于红黑树、B树和B+树非常重要。
红黑树
红黑树主要是对2-3树进行编码，红黑树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。
我们将树中的链接分为两种类型：红链接：将两个2-结点连接起来构成一个3-结点。黑链接：则是2-3树中的普通链接。
确切的说，我们将3-结点表示为由一条左斜的红色链接(两个2-结点其中之一是另一个的左子结点)相连的两个2-结点。这种表示法的一个优点是，我们无需修改就可以直接使用标准的二叉查找树的get方法。
红黑树是含有红黑链接并满足下列条件的二叉查找树：红链接均为左链接；没有任何一个结点同时和两条红链接相连；该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
在对红黑树进行一些增删改查的操作后，很有可能会出现红色的右链接或者两条连续红色的链接，而这些都不满足红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。
左旋：当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。前提：当前结点为h，它的右子结点为x。左旋过程：让x的左子结点变为h的右子结点：h.right=x.left;让h成为x的左子结点：x.left=h;让h的color属性变为x的color属性值：x.color=h.color;让h的color属性变为RED：h.color=true。
右旋：当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋。前提：当前结点为h，它的左子结点为x。右旋过程：让x的右子结点成为h的左子结点：h.left = x.right;让h成为x的右子结点：x.right=h;让x的color变为h的color属性值：x.color = h.color;让h的color为RED。
颜色反转：当一个结点的左子结点和右子结点的color都为RED时，也就是出现了临时的4-结点，此时只需要把左子结点和右子结点的颜色变为BLACK，同时让当前结点的颜色变为RED即可。
由于根结点不存在父结点，所以每次插入操作后，我们都需要把根结点的颜色设置为黑色。
代码实现
public class RedBlackTree<Key extends Comparable<Key>, Value> {
//根节点
private Node root;
//记录树中元素的个数
private int N;
//红色链接
private static final boolean RED = true;
//黑色链接
private static final boolean BLACK = false;
//结点类
private class Node {
//存储键
public Key key;
//存储值
private Value value;
//记录左子结点
public Node left;
//记录右子结点
public Node right;
//由其父结点指向它的链接的颜色
public boolean color;
public Node(Key key, Value value, Node left, Node right, boolean color) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.color = color;
}
}
//获取树中元素的个数
public int size() {
return N;
}
/**
* 判断当前节点的父指向链接是否为红色
*
* @param x
* @return
*/
private boolean isRed(Node x) {
if (x==null){
return false;
}
return x.color==RED;
}
/**
* 左旋转
*
* @param h
* @return
*/
private Node rotateLeft(Node h) {
//找到h结点的右子结点x
Node x = h.right;
//找到x结点的左子结点，让x结点的左子结点称为h结点的右子结点
h.right = x.left;
//让h结点称为x结点的左子结点
x.left = h;
//让x结点的color属性变为h结点的color属性
x.color = h.color;
//让h结点的color属性变为RED
h.color = RED;
return x;
}
/**
* 右旋
*
* @param h
* @return
*/
private Node rotateRight(Node h) {
//找到h结点的左子结点 x
Node x = h.left;
//让x结点的右子结点成为h结点的左子结点
h.left = x.right;
//让h结点成为x结点的右子结点
x.right = h;
//让x结点的color属性变为h结点的color属性
x.color = h.color;
//让h结点的color属性为RED
h.color = RED;
return x;
}
/**
* 颜色反转,相当于完成拆分4-节点
*
* @param h
*/
private void flipColors(Node h) {
//当前结点变为红色
h.color = RED;
//左子结点和右子结点变为黑色
h.left.color=BLACK;
h.right.color = BLACK;
}
/**
* 在整个树上完成插入操作
*
* @param key
* @param val
*/
public void put(Key key, Value val) {
root = put(root,key,val);
//根结点的颜色总是黑色
root.color = BLACK;
}
/**
* 在指定树中，完成插入操作,并返回添加元素后新的树
*
* @param h
* @param key
* @param val
*/
private Node put(Node h, Key key, Value val) {
//判断h是否为空，如果为空则直接返回一个红色的结点就可以了
if (h == null){
//数量+1
N++;
return new Node(key,val,null,null,BLACK);
}
//比较h结点的键和key的大小
int cmp = key.compareTo(h.key);
if (cmp<0){
//继续往左
h.left = put(h.left,key,val);
}else if (cmp>0){
//继续往右
h.right = put(h.right,key,val);
}else{
//发生值的替换
h.value = val;
}
//进行左旋:当当前结点h的左子结点为黑色，右子结点为红色，需要左旋
if (isRed(h.right) && !isRed(h.left)){
h = rotateLeft(h);
}
//进行右旋：当当前结点h的左子结点和左子结点的左子结点都为红色，需要右旋
if (isRed(h.left) && isRed(h.left.left)){
rotateRight(h);
}
//颜色反转：当前结点的左子结点和右子结点都为红色时，需要颜色反转
if (isRed(h.left) && isRed(h.right)){
flipColors(h);
}
return h;
}
//根据key，从树中找出对应的值
public Value get(Key key) {
return get(root,key);
}
//从指定的树x中，查找key对应的值
public Value get(Node x, Key key) {
if (x == null){
return null;
}
//比较x结点的键和key的大小
int cmp = key.compareTo(x.key);
if (cmp<0){
return get(x.left,key);
}else if (cmp>0){
return get(x.right,key);
}else{
return x.value;
}
}
}
测试
public class RedBlackTreeTest {
public static void main(String[] args) {
//创建红黑树
RedBlackTree<String, String> tree = new RedBlackTree<>();
//往树中插入元素
tree.put("1","张三");
tree.put("2","李四");
tree.put("3","王五");
//从树中获取元素
String r1 = tree.get("1");
System.out.println(r1);
String r2 = tree.get("2");
System.out.println(r2);
String r3 = tree.get("3");
System.out.println(r3);
}
}
B树和B+树
B树
B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在我们选择一个参数M，来构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点：每个结点最多有M-1个key，并且以升序排列；每个结点最多能有M个子结点；根结点至少有两个子结点。
在实际应用中B树的阶数一般都比较大（通常大于100），所以，即使存储大量的数据，B树的高度仍然比较小，这样在某些应用场景下，就可以体现出它的优势。
在我们的程序中，不可避免的需要通过IO操作文件，而我们的文件是存储在磁盘上的。计算机操作磁盘上的文件是通过文件系统进行操作的，在文件系统中就使用到了B树这种数据结构。
B+树
B+树是对B树的一种变形树，它与B树的差异在于：非叶结点仅具有索引作用，也就是说，非叶子结点只存储key，不存储value；树的所有叶结点构成一个有序链表，可以按照key排序的次序遍历全部数据。
B+ 树的优点在于：由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key。B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。
B树的优点在于：由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的位置，就能找到value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶子结点的深度，才能找到value。
在数据库的操作中，查询操作可以说是最频繁的一种操作，因此在设计数据库时，必须要考虑到查询的效率问题，在很多数据库中，都是用到了B+树来提高查询的效率；在操作数据库时，我们为了提高查询效率，可以基于某张表的某个字段建立索引，就可以提高查询效率，那其实这个索引就是B+树这种数据结构实现的。
并查集
并查集也是一种树型结构，跟二叉树、红黑树、B树等都不一样，这种树的要求比较简单：每个元素都唯一的对应一个结点；每一组数据中的多个元素都在同一颗树中；一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系；元素在树中并没有子父级关系的硬性要求。
实现
初始情况下，并查集中的数据默认分为N个组；初始化数组eleAndGroup；把eleAndGroup数组的索引看做是每个结点存储的元素，把eleAndGroup数组每个索引处的值看做是该结点所在的分组，那么初始化情况下，i索引处存储的值就是i。
如果p和q已经在同一个分组中，则无需合并；如果p和q不在同一个分组，则只需要将p元素所在组的所有的元素的组标识符修改为q元素所在组的标识符即可；分组数量-1。
public class UF {
//记录结点元素和该元素所在分组的标识
private int[] eleAndGroup;
//记录并查集中数据的分组个数
private int count;
//初始化并查集
public UF(int N){
//初始化分组的数量,默认情况下，有N个分组
this.count = N;
//初始化eleAndGroup数组
this.eleAndGroup = new int[N];
//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素，并且让每个索引处的值(该元素所在的组的标识符)就是该索引
for (int i = 0; i < eleAndGroup.length; i++) {
eleAndGroup[i] = i;
}
}
//获取当前并查集中的数据有多少个分组
public int count(){
return count;
}
//元素p所在分组的标识符
public int find(int p){
return eleAndGroup[p];
}
//判断并查集中元素p和元素q是否在同一分组中
public boolean connected(int p,int q){
return find(p) == find(q);
}
//把p元素所在分组和q元素所在分组合并
public void union(int p,int q){
//判断元素q和p是否已经在同一分组中，如果已经在同一分组中，则结束方法就可以了
if (connected(p,q)){
return;
}
//找到p所在分组的标识符
int pGroup = find(p);
//找到q所在分组的标识符
int qGroup = find(q);
//合并组：让p所在组的所有元素的组标识符变为q所在分组的标识符
for (int i = 0; i < eleAndGroup.length; i++) {
if (eleAndGroup[i]==pGroup){
eleAndGroup[i] = qGroup;
}
}
//分组个数-1
this.count--;
}
}
测试
public class UFTest {
public static void main(String[] args) {
//创建并查集对象
UF uf = new UF(5);
System.out.println("默认情况下，并查集中有："+uf.count()+"个分组");
//从控制台录入两个要合并的元素，调用union方法合并，观察合并后并查集中的分组是否减少
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("请输入第一个要合并的元素：");
int p = sc.nextInt();
System.out.println("请输入第二个要合并的元素：");
int q = sc.nextInt();
//判断这两个元素是否已经在同一组了
if (uf.connected(p,q)){
System.out.println(p+"元素和"+q+"元素已经在同一个组中了");
continue;
}
uf.union(p,q);
System.out.println("当前并查集中还有："+uf.count()+"个分组");
}
}
}
UF_Tree算法优化
我们仍然让eleAndGroup数组的索引作为某个结点的元素；eleAndGroup[i]的值不再是当前结点所在的分组标识，而是该结点的父结点。
public class UF_Tree {
//记录结点元素和该元素所在分组的标识
private int[] eleAndGroup;
//记录并查集中数据的分组个数
private int count;
//初始化并查集
public UF_Tree(int N){
//初始化分组的数量,默认情况下，有N个分组
this.count = N;
//初始化eleAndGroup数组
this.eleAndGroup = new int[N];
//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素，并且让每个索引处的值(该元素所在的组的标识符)就是该索引
for (int i = 0; i < eleAndGroup.length; i++) {
eleAndGroup[i] = i;
}
}
//获取当前并查集中的数据有多少个分组
public int count(){
return count;
}
//判断并查集中元素p和元素q是否在同一分组中
public boolean connected(int p,int q){
return find(p) == find(q);
}
//元素p所在分组的标识符
public int find(int p){
while(true){
if (p == eleAndGroup[p]){
return p;
}
p = eleAndGroup[p];
}
}
//把p元素所在分组和q元素所在分组合并
public void union(int p,int q){
//找到p元素和q元素所在组对应的树的根结点
int pRoot = find(p);
int qRoot = find(q);
//如果p和q已经在同一分组，则不需要合并了
if (pRoot==qRoot){
return;
}
//让p所在的树的根结点的父结点为q所在树的根结点即可
eleAndGroup[pRoot] = qRoot;
//组的数量-1
this.count--;
}
}
测试
public class UFTeeTest {
public static void main(String[] args) {
//创建并查集对象
UF_Tree uf = new UF_Tree(5);
System.out.println("默认情况下，并查集中有："+uf.count()+"个分组");
//从控制台录入两个要合并的元素，调用union方法合并，观察合并后并查集中的分组是否减少
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("请输入第一个要合并的元素：");
int p = sc.nextInt();
System.out.println("请输入第二个要合并的元素：");
int q = sc.nextInt();
//判断这两个元素是否已经在同一组了
if (uf.connected(p,q)){
System.out.println(p+"元素和"+q+"元素已经在同一个组中了");
continue;
}
uf.union(p,q);
System.out.println("当前并查集中还有："+uf.count()+"个分组");
}
}
}
路径压缩优化
在每次合并树的时候，把较小的树连接到较大的树上，就可以减小树的深度。
public class UF_Tree_Weighted {
//记录结点元素和该元素所在分组的标识
private int[] eleAndGroup;
//记录并查集中数据的分组个数
private int count;
//用来存储每一个根结点对应的树中保存的结点的个数
private int[] sz;
//初始化并查集
public UF_Tree_Weighted(int N){
//初始化分组的数量,默认情况下，有N个分组
this.count = N;
//初始化eleAndGroup数组
this.eleAndGroup = new int[N];
//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素，并且让每个索引处的值(该元素所在的组的标识符)就是该索引
for (int i = 0; i < eleAndGroup.length; i++) {
eleAndGroup[i] = i;
}
this.sz = new int[N];
//默认情况下，sz中每个索引处的值都是1
for (int i = 0; i < sz.length; i++) {
sz[i] = 1;
}
}
//获取当前并查集中的数据有多少个分组
public int count(){
return count;
}
//判断并查集中元素p和元素q是否在同一分组中
public boolean connected(int p,int q){
return find(p) == find(q);
}
//元素p所在分组的标识符
public int find(int p){
while(true){
if (p == eleAndGroup[p]){
return p;
}
p = eleAndGroup[p];
}
}
//把p元素所在分组和q元素所在分组合并
public void union(int p,int q){
//找到p元素和q元素所在组对应的树的根结点
int pRoot = find(p);
int qRoot = find(q);
//如果p和q已经在同一分组，则不需要合并了
if (pRoot==qRoot){
return;
}
//判断proot对应的树大还是qroot对应的树大，最终需要把较小的树合并到较大的树中
if (sz[pRoot]<sz[qRoot]){
eleAndGroup[pRoot] = qRoot;
sz[qRoot]+=sz[pRoot];
}else{
eleAndGroup[qRoot] = pRoot;
sz[pRoot]+= sz[qRoot];
}
//组的数量-1
this.count--;
}
}
测试
public class UFTeeWeightedTest {
public static void main(String[] args) {
//创建并查集对象
UF_Tree_Weighted uf = new UF_Tree_Weighted(5);
System.out.println("默认情况下，并查集中有："+uf.count()+"个分组");
//从控制台录入两个要合并的元素，调用union方法合并，观察合并后并查集中的分组是否减少
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("请输入第一个要合并的元素：");
int p = sc.nextInt();
System.out.println("请输入第二个要合并的元素：");
int q = sc.nextInt();
//判断这两个元素是否已经在同一组了
if (uf.connected(p,q)){
System.out.println(p+"元素和"+q+"元素已经在同一个组中了");
continue;
}
uf.union(p,q);
System.out.println("当前并查集中还有："+uf.count()+"个分组");
}
}
}
案例
public class Traffic_Project_Test {
public static void main(String[] args) throws Exception{
//构建一个缓冲读取流BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(Traffic_Project_Test.class.getClassLoader().getResourceAsStream("traffic_project.txt")));
//读取第一行数据20
int totalNumber = Integer.parseInt(br.readLine());
//构建一个并查集对象
UF_Tree_Weighted uf = new UF_Tree_Weighted(totalNumber);
//读取第二行数据7
int roadNumber = Integer.parseInt(br.readLine());
//循环读取7条道路
for (int i=1;i<=roadNumber;i++){
String line = br.readLine();//0 1
String[] str = line.split(" ");
int p = Integer.parseInt(str[0]);
int q = Integer.parseInt(str[1]);
//调用并查集对象的union方法让两个城市相通
uf.union(p,q);
}
//获取当前并查集中分组的数量-1就可以得到还需要修建的道路的数目
int roads = uf.count()-1;
System.out.println("还需要修建"+roads+"条道路，才能实现畅通工程");
}
}
图
概念
图是由一组顶点和一组能够将两个顶点相连的边组成的。按照连接两个顶点的边的不同，可以把图分为以下两种：无向图：边仅仅连接两个顶点，没有其他含义；有向图：边不仅连接两个顶点，并且具有方向。
相邻顶点：当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。
度：某个顶点的度就是依附于该顶点的边的个数。
子图：是一幅图的所有边的子集(包含这些边依附的顶点)组成的图。
路径：是由边顺序连接的一系列的顶点组成。
环：是一条至少含有一条边且终点和起点相同的路径。
连通图：如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图。
连通子图：一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图。
图的存储结构
只需要表示清楚以下两部分内容即可：图中所有的顶点；所有连接顶点的边。
常见的图的存储结构有两种：邻接矩阵和邻接表
邻接矩阵：使用一个 V*V 的二维数组int[V][V] adj,把索引的值看做是顶点；如果顶点v和顶点w相连，我们只需要将adj[v][w]和adj[w][v]的值设置为1,否则设置为0即可。邻接矩阵这种存储方式的空间复杂度是V^2的。
邻接表：使用一个大小为V的数组 Queue[V] adj，把索引看做是顶点；每个索引处adj[v]存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点。
代码实现
public class Graph {
//顶点数目
private final int V;
//边的数目
private int E;
//邻接表
private Queue<Integer>[] adj;
public Graph(int V){
//初始化顶点数量
this.V = V;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new Queue[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new Queue<Integer>();
}
}
//获取顶点数目
public int V(){
return V;
}
//获取边的数目
public int E(){
return E;
}
//向图中添加一条边 v-w
public void addEdge(int v, int w) {
//在无向图中，边是没有方向的，所以该边既可以说是从v到w的边，又可以说是从w到v的边，因此，需要让w出现在v的邻接表中，并且还要让v出现在w的邻接表中
adj[v].enqueue(w);
adj[w].enqueue(v);
//边的数量+1
E++;
}
//获取和顶点v相邻的所有顶点
public Queue<Integer> adj(int v){
return adj[v];
}
}
图的搜索
深度优先搜索：在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。
public class DepthFirstSearch {
//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//记录有多少个顶点与s顶点相通
private int count;
//构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相邻顶点
public DepthFirstSearch(Graph G,int s){
//初始化marked数组
this.marked = new boolean[G.V()];
//初始化跟顶点s相通的顶点的数量
this.count=0;
dfs(G,s);
}
//使用深度优先搜索找出G图中v顶点的所有相通顶点
private void dfs(Graph G, int v){
//把v顶点标识为已搜索
marked[v] = true;
for (Integer w : G.adj(v)) {
//判断当前w顶点有没有被搜索过，如果没有被搜索过，则递归调用dfs方法进行深度搜索
if (!marked[w]){
dfs(G,w);
}
}
//相通顶点数量+1
count++;
}
//判断w顶点与s顶点是否相通
public boolean marked(int w){
return marked[w];
}
//获取与顶点s相通的所有顶点的总数
public int count(){
return count;
}
}
测试深度优先搜索
public class DepthFirstSearchTest {
public static void main(String[] args) {
//准备Graph对象
Graph G = new Graph(13);
G.addEdge(0,5);
G.addEdge(0,1);
G.addEdge(0,2);
G.addEdge(0,6);
G.addEdge(5,3);
G.addEdge(5,4);
G.addEdge(3,4);
G.addEdge(4,6);
G.addEdge(7,8);
G.addEdge(9,11);
G.addEdge(9,10);
G.addEdge(9,12);
G.addEdge(11,12);
//准备深度优先搜索对象
DepthFirstSearch search = new DepthFirstSearch(G, 0);
//测试与某个顶点相通的顶点数量
int count = search.count();
System.out.println("与起点0相通的顶点的数量为:"+count);
//测试某个顶点与起点是否相同
boolean marked1 = search.marked(5);
System.out.println("顶点5和顶点0是否相通："+marked1);
boolean marked2 = search.marked(7);
System.out.println("顶点7和顶点0是否相通："+marked2);
}
}
广度优先搜索:在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点。
实现代码
public class BreadthFirstSearch {
//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//记录有多少个顶点与s顶点相通
private int count;
//用来存储待搜索邻接表的点
private Queue<Integer> waitSearch;
//构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相邻顶点
public BreadthFirstSearch(Graph G, int s) {
this.marked = new boolean[G.V()];
this.count=0;
this.waitSearch = new Queue<Integer>();
bfs(G,s);
}
//使用广度优先搜索找出G图中v顶点的所有相邻顶点
private void bfs(Graph G, int v) {
//把当前顶点v标识为已搜索
marked[v] = true;
//让顶点v进入队列，待搜索
waitSearch.enqueue(v);
//通过循环，如果队列不为空，则从队列中弹出一个待搜索的顶点进行搜索
while(!waitSearch.isEmpty()){
//弹出一个待搜索的顶点
Integer wait = waitSearch.dequeue();
//遍历wait顶点的邻接表
for (Integer w : G.adj(wait)) {
if (!marked[w]){
bfs(G,w);
}
}
}
//让相通的顶点+1；
count++;
}
//判断w顶点与s顶点是否相通
public boolean marked(int w) {
return marked[w];
}
//获取与顶点s相通的所有顶点的总数
public int count() {
return count;
}
}
测试
public class BreadthFirstSearchTest {
public static void main(String[] args) {
//准备Graph对象
Graph G = new Graph(13);
G.addEdge(0,5);
G.addEdge(0,1);
G.addEdge(0,2);
G.addEdge(0,6);
G.addEdge(5,3);
G.addEdge(5,4);
G.addEdge(3,4);
G.addEdge(4,6);
G.addEdge(7,8);
G.addEdge(9,11);
G.addEdge(9,10);
G.addEdge(9,12);
G.addEdge(11,12);
//准备广度优先搜索对象
BreadthFirstSearch search = new BreadthFirstSearch(G, 0);
//测试与某个顶点相通的顶点数量
int count = search.count();
System.out.println("与起点0相通的顶点的数量为:"+count);
//测试某个顶点与起点是否相同
boolean marked1 = search.marked(5);
System.out.println("顶点5和顶点0是否相通："+marked1);
boolean marked2 = search.marked(7);
System.out.println("顶点7和顶点0是否相通："+marked2);
}
}
案例
public class Traffic_Project_Test2 {
public static void main(String[] args) throws Exception{
//构建一个缓冲读取流BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(Traffic_Project_Test2.class.getClassLoader().getResourceAsStream("traffic_project.txt")));
//读取第一行数据20
int totalNumber = Integer.parseInt(br.readLine());
//构建一个Graph对象
Graph G = new Graph(totalNumber);
//读取第二行数据7
int roadNumber = Integer.parseInt(br.readLine());
//循环读取有限次(7)，读取已经修建好的道路
for (int i = 1;i<=roadNumber;i++){
String road = br.readLine();//"0 1"
String[] str = road.split(" ");
int v = Integer.parseInt(str[0]);
int w = Integer.parseInt(str[1]);
//调用图的addEdge方法，把边添加到图中，表示已经修建好的道路
G.addEdge(v,w);
}
//构建一个深度优先搜索对象，起点设置为顶点9
DepthFirstSearch search = new DepthFirstSearch(G, 9);
//调用marked方法，判断8顶点和10顶点是否与起点9相通
System.out.println("顶点8和顶点9是否相通："+search.marked(8));
System.out.println("顶点10和顶点9是否相通："+search.marked(10));
}
}
路径查找
public class DepthFirstPaths {
//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//起点
private int s;
//索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
private int[] edgeTo;
//构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径
public DepthFirstPaths(Graph G, int s){
//初始化marked数组
this.marked = new boolean[G.V()];
//初始化起点
this.s = s;
//初始化edgeTo数组
this.edgeTo = new int[G.V()];
dfs(G,s);
}
//使用深度优先搜索找出G图中v顶点的所有相邻顶点
private void dfs(Graph G, int v){
//把v表示为已搜索
marked[v] = true;
//遍历顶点v的邻接表，拿到每一个相邻的顶点，继续递归搜索
for (Integer w : G.adj(v)) {
//如果顶点w没有被搜索，则继续递归搜索
if (!marked[w]){
edgeTo[w] = v;//到达顶点w的路径上的最后一个顶点是v
dfs(G,w);
}
}
}
//判断w顶点与s顶点是否存在路径
public boolean hasPathTo(int v){
return marked[v];
}
//找出从起点s到顶点v的路径(就是该路径经过的顶点)
public Stack<Integer> pathTo(int v){
if (!hasPathTo(v)){
return null;
}
//创建栈对象，保存路径中的所有顶点
Stack<Integer> path = new Stack<>();
//通过循环，从顶点v开始，一直往前找，到找到起点为止
for (int x = v; x!=s;x = edgeTo[x]){
path.push(x);
}
//把起点s放到栈中
path.push(s);
return path;
}
}
测试
public class DepthFirstPathsTest {
public static void main(String[] args) throws Exception{
//构建缓冲读取流BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(DepthFirstPathsTest.class.getClassLoader().getResourceAsStream("road_find.txt")));
//读取第一行数据6
int total = Integer.parseInt(br.readLine());
//根据第一行数据构建一副图Graph
Graph G = new Graph(total);
//读取第二行数据8
int edgeNumbers = Integer.parseInt(br.readLine());
//继续通过循环读取每一条边关联的两个顶点，调用addEdge方法，添加边
for (int i = 1;i<=edgeNumbers;i++){
String edge = br.readLine();//0 1
String[] str = edge.split(" ");
int v = Integer.parseInt(str[0]);
int w = Integer.parseInt(str[1]);
G.addEdge(v,w);
}
//构建路径查找对象，并设置起点为0
DepthFirstPaths paths = new DepthFirstPaths(G, 0);
//调用 pathTo(4)，找到从起点0到终点4的路径，返回Stack
Stack<Integer> path = paths.pathTo(4);
StringBuilder sb = new StringBuilder();
//遍历栈对象
for (Integer v : path) {
sb.append(v+"-");
}
sb.deleteCharAt(sb.length()-1);
System.out.println(sb);
}
}
有向图定义
有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成的，每条方向的边都连着一对有序的顶点。
出度：由某个顶点指出的边的个数称为该顶点的出度。
入度：指向某个顶点的边的个数称为该顶点的入度。
有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点。
有向环：一条至少含有一条边，且起点和终点相同的有向路径。
一副有向图中两个顶点v和w可能存在以下四种关系：没有边相连；存在从v到w的边v—>w;存在从w到v的边w—>v;既存在w到v的边，也存在v到w的边，即双向连接。
有向图实现
public class Digraph {
//顶点数目
private final int V;
//边的数目
private int E;
//邻接表
private Queue<Integer>[] adj;
public Digraph(int V){
//初始化顶点数量
this.V = V;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new Queue[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new Queue<Integer>();
}
}
//获取顶点数目
public int V(){
return V;
}
//获取边的数目
public int E(){
return E;
}
//向有向图中添加一条边 v->w
public void addEdge(int v, int w) {
//只需要让顶点w出现在顶点v的邻接表中，因为边是有方向的，最终，顶点v的邻接表中存储的相邻顶点的含义是： v->其他顶点
adj[v].enqueue(w);
E++;
}
//获取由v指出的边所连接的所有顶点
public Queue<Integer> adj(int v){
return adj[v];
}
//该图的反向图
private Digraph reverse(){
//创建有向图对象
Digraph r = new Digraph(V);
for (int v = 0;v<V;v++){
//获取由该顶点v指出的所有边
for (Integer w : adj[v]) {//原图中表示的是由顶点v->w的边
r.addEdge(w,v);//w->v
}
}
return r;
}
}
拓扑排序-检测有向图中的环
拓扑排序：给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级。
如果我们要使用拓扑排序解决优先级问题，首先得保证图中没有环的存在。
onStack[] 布尔数组，索引为图的顶点，当我们深度搜索时：在如果当前顶点正在搜索，则把对应的onStack数组中的值改为true，标识进栈；如果当前顶点搜索完毕，则把对应的onStack数组中的值改为false，标识出栈；如果即将要搜索某个顶点，但该顶点已经在栈中，则图中有环。
代码实现
public class DirectedCycle {
//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//记录图中是否有环
private boolean hasCycle;
//索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
private boolean[] onStack;
//创建一个检测环对象，检测图G中是否有环
public DirectedCycle(Digraph G){
//初始化marked数组
this.marked = new boolean[G.V()];
//初始化hasCycle
this.hasCycle = false;
//初始化onStack数组
this.onStack = new boolean[G.V()];
//找到图中每一个顶点，让每一个顶点作为入口，调用一次dfs进行搜索
for (int v =0; v<G.V();v++){
//判断如果当前顶点还没有搜索过，则调用dfs进行搜索
if (!marked[v]){
dfs(G,v);
}
}
}
//基于深度优先搜索，检测图G中是否有环
private void dfs(Digraph G, int v){
//把顶点v表示为已搜索
marked[v] = true;
//把当前顶点进栈
onStack[v] = true;
//进行深度搜索
for (Integer w : G.adj(v)) {
//判断如果当前顶点w没有被搜索过，则继续递归调用dfs方法完成深度优先搜索
if (!marked[w]){
dfs(G,w);
}
//判断当前顶点w是否已经在栈中，如果已经在栈中，证明当前顶点之前处于正在搜索的状态，那么现在又要搜索一次，证明检测到环了
if (onStack[w]){
hasCycle = true;
return;
}
}
//把当前顶点出栈
onStack[v] = false;
}
//判断当前有向图G中是否有环
public boolean hasCycle(){
return hasCycle;
}
}
拓扑排序-基于深度优先的顶点排序
栈reversePost用来存储顶点，当我们深度搜索图时，每搜索完毕一个顶点，把该顶点放入到reversePost中，这样就可以实现顶点排序。
代码实现：
public class DepthFirstOrder {
//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//使用栈，存储顶点序列
private Stack<Integer> reversePost;
//创建一个检测环对象，检测图G中是否有环
public DepthFirstOrder(Digraph G){
//初始化marked数组
this.marked = new boolean[G.V()];
//初始化reversePost栈
this.reversePost = new Stack<Integer>();
//遍历图中的每一个顶点，让每个顶点作为入口，完成一次深度优先搜索
for (int v = 0;v<G.V();v++){
if (!marked[v]){
dfs(G,v);
}
}
}
//基于深度优先搜索，把顶点排序
private void dfs(Digraph G, int v){
//标记当前v已经被搜索
marked[v] = true;
//通过循环深度搜索顶点v
for (Integer w : G.adj(v)) {
//如果当前顶点w没有搜索，则递归调用dfs进行搜索
if (!marked[w]){
dfs(G,w);
}
}
//让顶点v进栈
reversePost.push(v);
}
//获取顶点线性序列
public Stack<Integer> reversePost(){
return reversePost;
}
}
拓扑排序实现
public class TopoLogical {
//顶点的拓扑排序
private Stack<Integer> order;
//构造拓扑排序对象
public TopoLogical(Digraph G) {
//创建一个检测有向环的对象
DirectedCycle cycle = new DirectedCycle(G);
//判断G图中有没有环，如果没有环，则进行顶点排序：创建一个顶点排序对象
if (!cycle.hasCycle()){
DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
order = depthFirstOrder.reversePost();
}
}
//判断图G是否有环
private boolean isCycle(){
return order==null;
}
//获取拓扑排序的所有顶点
public Stack<Integer> order(){
return order;
}
}
测试
public class TopoLogicalTest {
public static void main(String[] args) {
//准备有向图
Digraph digraph = new Digraph(6);
digraph.addEdge(0,2);
digraph.addEdge(0,3);
digraph.addEdge(2,4);
digraph.addEdge(3,4);
digraph.addEdge(4,5);
digraph.addEdge(1,3);
//通过TopoLogical对象堆有向图中的顶点进行排序
TopoLogical topoLogical = new TopoLogical(digraph);
//获取顶点的线性序列进行打印
Stack<Integer> order = topoLogical.order();
StringBuilder sb = new StringBuilder();
for (Integer w : order) {
sb.append(w+"->");
}
String str = sb.toString();
int index = str.lastIndexOf("->");
str = str.substring(0,index);
System.out.println(str);
}
}
加权无向图
加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。
边的实现：
public class Edge implements Comparable<Edge> {
private final int v;//顶点一
private final int w;//顶点二
private final double weight;//当前边的权重
//通过顶点v和w，以及权重weight值构造一个边对象
public Edge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
//获取边的权重值
public double weight(){
return weight;
}
//获取边上的一个点
public int either(){
return v;
}
//获取边上除了顶点vertex外的另外一个顶点
public int other(int vertex){
if (vertex==v){
return w;
}else{
return v;
}
}
@Override
public int compareTo(Edge that) {
//使用一个遍历记录比较的结果
int cmp;
if (this.weight()>that.weight()){
//如果当前边的权重值大，则让cmp=1；
cmp = 1;
}else if (this.weight()<that.weight()){
//如果当前边的权重值小，则让cmp=-1；
cmp=-1;
}else{
//如果当前边的权重值和that边的权重值一样大，则让cmp=0
cmp = 0;
}
return cmp;
}
}
加权无向图的实现
public class EdgeWeightedGraph {
//顶点总数
private final int V;
//边的总数
private int E;
//邻接表
private Queue<Edge>[] adj;
//创建一个含有V个顶点的空加权无向图
public EdgeWeightedGraph(int V) {
//初始化顶点数量
this.V = V;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new Queue[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new Queue<Edge>();
}
}
//获取图中顶点的数量
public int V() {
return V;
}
//获取图中边的数量
public int E() {
return E;
}
//向加权无向图中添加一条边e
public void addEdge(Edge e) {
//需要让边e同时出现在e这个边的两个顶点的邻接表中
int v = e.either();
int w = e.other(v);
adj[v].enqueue(e);
adj[w].enqueue(e);
//边的数量+1
E++;
}
//获取和顶点v关联的所有边
public Queue<Edge> adj(int v) {
return adj[v];
}
//获取加权无向图的所有边
public Queue<Edge> edges() {
//创建一个队列对象，存储所有的边
Queue<Edge> allEdges = new Queue<>();
//遍历图中的每一个顶点，找到该顶点的邻接表，邻接表中存储了该顶点关联的每一条边
//因为这是无向图，所以同一条边同时出现在了它关联的两个顶点的邻接表中，需要让一条边只记录一次；
for(int v =0;v<V;v++){
//遍历v顶点的邻接表，找到每一条和v关联的边
for (Edge e : adj(v)) {
if (e.other(v)<v){
allEdges.enqueue(e);
}
}
}
return allEdges;
}
}
最小生成树
图的生成树是它的一棵含有其所有顶点的无环连通子图，一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树。
树的性质：用一条边接树中的任意两个顶点都会产生一个新的环；从树中删除任意一条边，将会得到两棵独立的树。
切分：将图的所有顶点按照某些规则分为两个非空且没有交集的集合。
横切边：连接两个属于不同集合的顶点的边称之为横切边。
切分定理：在一副加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图中的最小生成树。注意:一次切分产生的多个横切边中，权重最小的边不一定是所有横切边中唯一属于图的最小生成树的边。
贪心算法是计算图的最小生成树的基础算法，它的基本原理就是切分定理，使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边。如果图有V个顶点，那么需要找到V-1条边，就可以表示该图的最小生成树。
最小生成树Prim算法
Prim算法的切分规则：把最小生成树中的顶点看做是一个集合，把不在最小生成树中的顶点看做是另外一个集合。实现：
public class PrimMST {
//索引代表顶点，值表示当前顶点和最小生成树之间的最短边
private Edge[] edgeTo;
//索引代表顶点，值表示当前顶点和最小生成树之间的最短边的权重
private double[] distTo;
//索引代表顶点，如果当前顶点已经在树中，则值为true，否则为false
private boolean[] marked;
//存放树中顶点与非树中顶点之间的有效横切边
private IndexMinPriorityQueue<Double> pq;
//根据一副加权无向图，创建最小生成树计算对象
public PrimMST(EdgeWeightedGraph G) {
//初始化edgeTo
this.edgeTo = new Edge[G.V()];
//初始化distTo
this.distTo = new double[G.V()];
for (int i = 0; i < distTo.length; i++) {
distTo[i] = Double.POSITIVE_INFINITY;
}
//初始化marked
this.marked = new boolean[G.V()];
//初始化pq
pq = new IndexMinPriorityQueue<Double>(G.V());
//默认让顶点0进入到树中，但是树中只有一个顶点0，因此，0顶点默认没有和其他的顶点相连，所以让distTo对应位置处的值存储0.0
distTo[0] = 0.0;
pq.insert(0,0.0);
//遍历索引最小优先队列，拿到最小和N切边对应的顶点，把该顶点加入到最小生成树中
while (!pq.isEmpty()){
visit(G,pq.delMin());
}
}
//将顶点v添加到最小生成树中，并且更新数据
private void visit(EdgeWeightedGraph G, int v) {
//把顶点v添加到最小生成树中
marked[v] = true;
//更新数据
for (Edge e : G.adj(v)) {
//获取e边的另外一个顶点(当前顶点是v)
int w = e.other(v);
//判断另外一个顶点是不是已经在树中，如果在树中，则不做任何处理，如果不再树中，更新数据
if (marked[w]){
continue;
}
//判断边e的权重是否小于从w顶点到树中已经存在的最小边的权重；
if (e.weight()<distTo[w]){
//更新数据
edgeTo[w] = e;
distTo[w] = e.weight();
if (pq.contains(w)){
pq.changeItem(w,e.weight());
}else{
pq.insert(w,e.weight());
}
}
}
}
//获取最小生成树的所有边
public Queue<Edge> edges() {
//创建队列对象
Queue<Edge> allEdges = new Queue<>();
//遍历edgeTo数组，拿到每一条边，如果不为null，则添加到队列中
for (int i = 0; i < edgeTo.length; i++) {
if (edgeTo[i]!=null){
allEdges.enqueue(edgeTo[i]);
}
}
return allEdges;
}
}
测试
public class PrimMSTTest {
public static void main(String[] args) throws Exception{
//准备一副加权无向图
BufferedReader br = new BufferedReader(new InputStreamReader(PrimMSTTest.class.getClassLoader().getResourceAsStream("min_create_tree_test.txt")));
int total = Integer.parseInt(br.readLine());
EdgeWeightedGraph G = new EdgeWeightedGraph(total);
int edgeNumbers = Integer.parseInt(br.readLine());
for (int e = 1;e<=edgeNumbers;e++){
String line = br.readLine();//4 5 0.35
String[] strs = line.split(" ");
int v = Integer.parseInt(strs[0]);
int w = Integer.parseInt(strs[1]);
double weight = Double.parseDouble(strs[2]);
//构建加权无向边
Edge edge = new Edge(v, w, weight);
G.addEdge(edge);
}
//创建一个PrimMST对象，计算加权无向图中的最小生成树
PrimMST primMST = new PrimMST(G);
//获取最小生成树中的所有边
Queue<Edge> edges = primMST.edges();
//遍历打印所有的边
for (Edge e : edges) {
int v = e.either();
int w = e.other(v);
double weight = e.weight();
System.out.println(v+"-"+w+" :: "+weight);
}
}
}
最小生成树kruskal算法
kruskal算法是按照边的权重(从小到大)处理它们，将边加入最小生成树中，加入的边不会与已经加入最小生成树的边构成环，直到树中含有V-1条边为止。
kruskal算法和prim算法的区别：Prim算法是一条边一条边的构造最小生成树，每一步都为一棵树添加一条边。kruskal算法构造最小生成树的时候
也是一条边一条边地构造，但它的切分规则是不一样的。它每一次寻找的边会连接一片森林中的两棵树。如果一副加权无向图由V个顶点组成，初始化情况下每个顶点都构成一棵独立的树，则V个顶点对应V棵树，组成一片森林，kruskal算法每一次处理都会将两棵树合并为一棵树，直到整个森林中只剩一棵树为止。
取出权重最小的边，并得到该边关联的两个顶点v和w，通过uf.connect(v,w)判断v和w是否已经连通，如果连通，则证明这两个顶点在同一棵树中，那么就不能再把这条边添加到最小生成树中，因为在一棵树的任意两个顶点上添加一条边，都会形成环，而最小生成树不能有环的存在，如果不连通，则通过uf.connect(v,w)把顶点v所在的树和顶点w所在的树合并成一棵树，并把这条边加入到mst队列中，这样如果把所有的边处理完，最终mst中存储的就是最小生树的所有边。
kruskal算法实现:
public class KruskalMST {
//保存最小生成树的所有边
private Queue<Edge> mst;
//索引代表顶点，使用uf.connect(v,w)可以判断顶点v和顶点w是否在同一颗树中，使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并
private UF_Tree_Weighted uf;
//存储图中所有的边，使用最小优先队列，对边按照权重进行排序
private MinPriorityQueue<Edge> pq;
//根据一副加权无向图，创建最小生成树计算对象
public KruskalMST(EdgeWeightedGraph G) {
//初始化mst
this.mst = new Queue<Edge>();
//初始化uf
this.uf = new UF_Tree_Weighted(G.V());
//初始化pq
this.pq = new MinPriorityQueue<>(G.E()+1);
//把图中所有的边存储到pq中
for (Edge e : G.edges()) {
pq.insert(e);
}
//遍历pq队列，拿到最小权重的边，进行处理
while(!pq.isEmpty() && mst.size()<G.V()-1){
//找到权重最小的边
Edge e = pq.delMin();
//找到该边的两个顶点
int v = e.either();
int w = e.other(v);
//判断这两个顶点是否已经在同一颗树中，如果在同一颗树中，则不对该边做处理，如果不在一棵树中，则让这两个顶点属于的两棵树合并成一棵树
if (uf.connected(v,w)){
continue;
}
uf.union(v,w);
//让边e进入到mst队列中
mst.enqueue(e);
}
}
//获取最小生成树的所有边
public Queue<Edge> edges() {
return mst;
}
}
测试
public class KruskalMSTTest {
public static void main(String[] args) throws Exception{
//准备一副加权无向图
BufferedReader br = new BufferedReader(new InputStreamReader(KruskalMSTTest.class.getClassLoader().getResourceAsStream("min_create_tree_test.txt")));
int total = Integer.parseInt(br.readLine());
EdgeWeightedGraph G = new EdgeWeightedGraph(total);
int edgeNumbers = Integer.parseInt(br.readLine());
for (int e = 1;e<=edgeNumbers;e++){
String line = br.readLine();//4 5 0.35
String[] strs = line.split(" ");
int v = Integer.parseInt(strs[0]);
int w = Integer.parseInt(strs[1]);
double weight = Double.parseDouble(strs[2]);
//构建加权无向边
Edge edge = new Edge(v, w, weight);
G.addEdge(edge);
}
//创建一个KruskalMST对象，计算加权无向图中的最小生成树
KruskalMST primMST = new KruskalMST(G);
//获取最小生成树中的所有边
Queue<Edge> edges = primMST.edges();
//遍历打印所有的边
for (Edge e : edges) {
int v = e.either();
int w = e.other(v);
double weight = e.weight();
System.out.println(v+"-"+w+" :: "+weight);
}
}
}
加权有向图
有向图边的表示：
public class DirectedEdge {
private final int v;//起点
private final int w;//终点
private final double weight;//当前边的权重
//通过顶点v和w，以及权重weight值构造一个边对象
public DirectedEdge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
//获取边的权重值
public double weight(){
return weight;
}
//获取有向边的起点
public int from(){
return v;
}
//获取有向边的终点
public int to(){
return w;
}
}
有向图的实现：
public class EdgeWeightedDigraph {
//顶点总数
private final int V;
//边的总数
private int E;
//邻接表
private Queue<DirectedEdge>[] adj;
//创建一个含有V个顶点的空加权有向图
public EdgeWeightedDigraph(int V) {
//初始化顶点数量
this.V = V;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new Queue[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new Queue<DirectedEdge>();
}
}
//获取图中顶点的数量
public int V() {
return V;
}
//获取图中边的数量
public int E() {
return E;
}
//向加权有向图中添加一条边e
public void addEdge(DirectedEdge e) {
//边e是有方向的，所以只需要让e出现在起点的邻接表中即可
int v = e.from();
adj[v].enqueue(e);
E++;
}
//获取由顶点v指出的所有的边
public Queue<DirectedEdge> adj(int v) {
return adj[v];
}
//获取加权有向图的所有边
public Queue<DirectedEdge> edges() {
//遍历图中的每一个顶点，得到该顶点的邻接表，遍历得到每一条边，添加到队列中返回即可
Queue<DirectedEdge> allEdges = new Queue<>();
for (int v = 0;v<V;v++){
for (DirectedEdge edge : adj[v]) {
allEdges.enqueue(edge);
}
}
return allEdges;
}
}
最短路径
最短路径定义及性质定义：在一副加权有向图中，从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。
最短路径树：给定一副加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一副子图，它包含顶点s以及从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径。
边的松弛：放松边v->w意味着检查从s到w的最短路径是否先从s到v，然后再从v到w。
顶点的松弛：顶点的松弛是基于边的松弛完成的，只需要把某个顶点指出的所有边松弛，那么该顶点就松弛完毕。例如要松弛顶点v，只需要遍历v的邻接表，把每一条边都松弛，那么顶点v就松弛了。
Disjstra算法的实现和Prim算法很类似，构造最短路径树的每一步都是向这棵树中添加一条新的边，而这条新的边是有效横切边pq队列中的权重最小的边。
public class DijkstraSP {
//索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
private DirectedEdge[] edgeTo;
//索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
private double[] distTo;
//存放树中顶点与非树中顶点之间的有效横切边
private IndexMinPriorityQueue<Double> pq;
//根据一副加权有向图G和顶点s，创建一个计算顶点为s的最短路径树对象
public DijkstraSP(EdgeWeightedDigraph G, int s){
//初始化edgeTo
this.edgeTo = new DirectedEdge[G.V()];
//初始化distTo
this.distTo = new double[G.V()];
for (int i = 0; i < distTo.length; i++) {
distTo[i] = Double.POSITIVE_INFINITY;
}
//初始化pq
this.pq = new IndexMinPriorityQueue<>(G.V());
//找到图G中以顶点s为起点的最短路径树
//默认让顶点s进入到最短路径树中
distTo[s] = 0.0;
pq.insert(s,0.0);
//遍历pq
while(!pq.isEmpty()){
relax(G,pq.delMin());
}
}
//松弛图G中的顶点v
private void relax(EdgeWeightedDigraph G, int v){
for (DirectedEdge edge : G.adj(v)) {
//获取到该边的终点w
int w = edge.to();
//通过松弛技术，判断从起点s到顶点w的最短路径是否需要先从顶点s到顶点v，然后再由顶点v到顶点w
if (distTo(v)+edge.weight()<distTo(w)){
distTo[w] = distTo[v]+edge.weight();
edgeTo[w] = edge;
//判断pq中是否已经存在顶点w，如果存在，则更新权重，如果不存在，则直接添加
if (pq.contains(w)){
pq.changeItem(w,distTo(w));
}else{
pq.insert(w,distTo(w));
}
}
}
}
//获取从顶点s到顶点v的最短路径的总权重
public double distTo(int v){
return distTo[v];
}
//判断从顶点s到顶点v是否可达
public boolean hasPathTo(int v){
return distTo[v]<Double.POSITIVE_INFINITY;
}
//查询从起点s到顶点v的最短路径中所有的边
public Queue<DirectedEdge> pathTo(int v){
//判断从顶点s到顶点v是否可达，如果不可达，直接返回null
if (!hasPathTo(v)){
return null;
}
//创建队列对象
Queue<DirectedEdge> allEdges = new Queue<>();
while (true){
DirectedEdge e = edgeTo[v];
if (e==null){
break;
}
allEdges.enqueue(e);
v = e.from();
}
return allEdges;
}
}
测试
public class DijkstraSPTest {
public static void main(String[] args) throws Exception{
//创建一副加权有向图
BufferedReader br = new BufferedReader(new InputStreamReader(DijkstraSPTest.class.getClassLoader().getResourceAsStream("min_route_test.txt")));
int total = Integer.parseInt(br.readLine());
EdgeWeightedDigraph G = new EdgeWeightedDigraph(total);
int edgeNumbers = Integer.parseInt(br.readLine());
for(int i=1;i<=edgeNumbers;i++){
String line = br.readLine();//4 5 0.35
String[] strs = line.split(" ");
int v = Integer.parseInt(strs[0]);
int w = Integer.parseInt(strs[1]);
double weight = Double.parseDouble(strs[2]);
DirectedEdge e = new DirectedEdge(v, w, weight);
G.addEdge(e);
}
//创建DijkstraSP对象，查找最短路径树
DijkstraSP dijkstraSP = new DijkstraSP(G, 0);
//查找最短路径,0->6的最短路径
Queue<DirectedEdge> edges = dijkstraSP.pathTo(6);
//遍历打印
for (DirectedEdge edge : edges) {
System.out.println(edge.from()+"->"+edge.to()+" ：： "+edge.weight());
}
}
}
