[数据结构与算法]Java数据结构

Java数据结构

一、数组

? 数组是一个可以存放多个数据的容器。

• 数据是同一类型

• 所有的数据都是线性规则排列

• 可通过位置索引来快速定位访问数据

• 需明确容器的长度

1.Java数组的定义和初始化

/*注意声明变量的时候没有分配内存，不需要指定大小*/
int[] a = new int[2];//定义一个数据类型为整数型长度为2的数组
a[0] = 1; a[1] = 2;//逐个初始化数组

int[] b = new int[]{0,2,4}//定义数组的同时初始化
int[] c = {1,3,5}//同时定义和初始化

2.数组的索引

• 数组的length属性标识数组的长度

• 从0开始，到length-1

• int[] a = new int[5]//a[0]~a[4] a.length = 5
  

• 数组不能越界访问，否则会有ArrayIndexOutOfBoundsException异常

3.数组的遍历

3.1控制索引位置

for(int i = 0;i<a.length;i++){
    System.out.println(d[i]);
}

3.2无需控制索引位置

for(int e:d){//e为每一个元素，d为数组
    System.out.println(e)
}

? 第二种for语句又称为for-each语句。不存在也不会出现越界访问异常。

二、多维数组

• 数组的数组
• 存储是按照行存储原则

1.规则数组

int[] a = new int[2][3]//定义一个两行三列的二维数组

2.不规则数组

int[][] b = new int[3][];
b[0] = new int[3];
b[1] = new int[4];
b[2] = new int[5];

?

3.二维数组的遍历

3.1通过位置索引

int k = 0;
for(int i = 0;i<a.length;i++){
    for(int j = 0;j<a[i].length;j++){
        a[i][j] = ++k;
    }
}

3.2无需索引

for(int[] arr:a){
    for(int[] arr1:arr){
        System.out.println(arr +",");
    }
    System.out.println();
}

三、JCF(Java Collection Framework)

• 容器：能够存放数据的空间结构

  • 数组、多维数组，只能线性存储
  • 列表、散列集、树集。。。

• 容器框架：表示和操作容器的一种标准体系结构

  • 对外的接口：容器中所能存放的抽象数据类型
  • 接口的实现：可复用的数据结构
  • 算法：对数据的查找和排序

• 容器框架的优点：提高数据存取效率，避免程序员重复劳动

1.早期接口：Enumeration

2.JCF的集合接口

• Collection
  • add（增加）,contains（包含）,remove（删除）,size（数据元素个数）
  • iterator（迭代器）

3.JCF的迭代器接口

• Iterator
  • hasNext（判断是否有下一个元素）
  • next（获取下一个元素）
  • remove（删除某一个元素）

4.JCF主要的数据结构实现类

• 列表（List，ArrayList，LinkedList）
• 集合（Set，HashSet，TreeSet，LinkedHashSet）
• 映射（Map，HashMap，TreeMap，LinkedHashMap）

5.JCF主要的算法类（工具类）

• Arrays:对数组进行查找和排序等操作。
• Collections：对Collection及其子类进行查找和排序等操作。

四、列表List

• List：列表

  • 有序的Collection
  • 允许重复元素
  • 允许嵌套 {1,2,4,{5,2},1,3}

• List主要实现

  • ArrayList（非同步）
  • LinkedList（非同步）
  • Vector（同步）

1.ArrayList

• 以数组实现的列表，不支持同步
• 利用索引位置可快速定位
• 不适合指定位置的插入、删除操作
• 适用于变动不大，主要用于查询的数据
• 其容量可动态调整
• 在元素填满容器时会自动扩充容器大小的50%

import java.util.ArrayList;
import java.util.Arrays;

public class ArrayListTest {
    public static void main(String[] args) {
        //创建一个空的数组链表对象list，list用来存放String类型的数据
        ArrayList<String> list=new ArrayList<String>();
        //增加元素到list对象中
        list.add("Item1");
        list.add("Item2");
        list.add(2,"Item3");//此条语句会把“Item3”字符串增加到list的第三个位置。
        list.add("Item4");
        //显示数组链表中的内容
        System.out.println("list链表包含以下元素："+list);
        //检查元素的位置
        int pos = list.indexOf("Item2");
        System.out.println("Item2的下标识："+pos);
        //检查数组链表是否为空
        boolean check = list.isEmpty();
        System.out.println("检查list是否为空："+check);
        //获取链表的大小
        int size = list.size();
        //检查数组链表中是否包含某元素
        boolean element = list.contains("Item5");
        System.out.println("检查数组链表是否包含Item5："+element);
        //获取指定位置上的元素
        String item = list.get(0);
        System.out.println("链表下标0的位置是："+item);
        //遍历arraylist中的元素
        //第1种方法：循环使用元素的索引和链表的大小
        System.out.println("使用下标从小到大循环遍历每个元素");
        for (int i = 0; i<list.size(); i++){
            System.out.println("元素："+i+"的内容是："+list.get(i));
        }//替换元素
        list.set(1,"NewItem");
        System.out.println("替换后的元素是："+list);
        //移除元素
        //移除第0个位置上的元素
        list.remove(0);
        //移除第一次找到的“item3”的元素
        list.remove("Item3");
        System.out.println("删除后的元素是："+list);
        //转换ArrayList为Array
        String[] simpleArray = list.toArray(new String[list.size()]);
        System.out.println("链表转换成数组后的内容是："+ Arrays.toString(simpleArray));
    }
}

2.LinkedList

• 以双向链表实现的列表，不支持同步
• 可被当做堆栈、队列和双端队列进行操作
• 顺序访问高效，随机访问较差，中间插入和删除高效
• 使用于经常变化的数据

3.Vector

• 和ArrayList类似，由可变数组来实现的一种类别，但支持同步
• 适合在多线程下使用

五、集合Set

• 确定性：对任意对象都能判断是否属于某一个集合
• 互异性：集合内每个元素都不相同（内容互异）
• 无序性：与集合内的顺序无关

1.集合接口Set

• HashSet（基于散列函数的集合，无序，不支持同步）
• TreeSet（基于树结构的集合，可排序，不支持同步）
• LinkedHashSet（基于散列函数和双向链表的集合，可排序，不支持同步）

1.1HashSet

• 基于HashMap实现的，可容纳null元素，不支持同步。

  • 同步方法

    Set s = Collections.synchronizedSet(new HashSet(...));
    

• add 添加元素

• clear 清除整个HashSet

• contains 判定是否包含一个元素

• remove 删除一个元素

• size 大小

• retainAll 计算两个集合的交集

1.2LinkedHashSet

• 继承HashSet，基于HashMap实现，可容纳null元素，不支持同步

  • 同步方法

    Set s = Collections.synchronizedSet(new LinkedHashSet(...));
    

• 方法与HashSet基本一致

  • add,clear,contains,remove,size

• 通过一个双向链表维护插入顺序

  • LinkedHashSet是保留顺序的，其遍历顺序和插入顺序一致；而HashSet没有保留顺序，其遍历顺序无序

1.3TreeSet

• 基于TreeMap实现，不可以容纳null元素，不支持同步

  • SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
    

• add 添加一个元素

• clear 清除整个TreeSet

• contains 判断是否包含一个元素

• remove 删除一个元素

• size 大小

• 根据compareTo方法或指定Comparator排序

• TreeSet是按照所存储对象大小升序输出的

  • HashSet是无序输出的；LinkedHashSet是按照插入的顺序进行遍历输出的。

1.4Java中的四大接口

• Comparable：可比较的；
• Clonable：可克隆的；
• Runnable：可线程化的；
• Serializable：可序列化的

2.判定原则

• HashSet，LinkedHashSet，TreeSet的元素都只能是对象

• HashSet和LinkedHashSet判断元素重复原则：

  • 判断两个元素的hashCode返回值是否相同，若不同则返回false
  • 若两个元素的hashCode返回值相同，判定equals方法，若不同，返回false，否则返回true
  • HashSet的元素判定规则只和hashCode、equals两个方法有关，与compareTo方法无关。

• TreeSet判断元素重复的原则：

  • 需要元素继承自Comparable接口

  • 比较两个元素的CompareTo方法

    //compareTo具体方法规则
    int a = obj1.compareTo(obj2);
    /*
    	如果a>0,则obj1>obj2;
    	如果a=0,则obj1>obj2;
    	如果a<0,则obj1<obj2;
    */
    

六、映射Map

• Map映射
  • 数学定义：两个集合之间的元素对应关系
  • 一个输入对应一个输出
  • {1，张三}，{2，李四}，{Key，Value} => 键值对 <=> K-V对
• Java中的Map
  • Hashtable（同步，性能慢，适合数据量小的）
  • HashMap（不同步，性能快，适合数据量大的）
  • Properties（同步，使用文件形式存储，适合数据量小的）

1.Hashtable

• K-V对，K和V都是不允许为null的；
• 同步，多线程安全
• 无序的
• 适合小数据量
• 主要方法：
  • clear：清空数据；
  • contains：等同于containsValue；
  • containsValue：判定是否包含某一个值；
  • containsKey：判定是否包含某一个Key；
  • get：根据Key获取相应的值；
  • put：增加新的K-V对；
  • remove：删除某一个K-V对；
  • size：返回数据大小

public class HashtableTest{
    public static void main(String[] args){
        //定义一个泛型标识，表示只能接受数字（Key）-字符串（Value）的K-V对
        Hashtable<Integer,String> ht = new Hashtable<Integer,String>();
        
        //ht.put(1,null); 编译不报错，运行报错
        //ht.put(null,1); 编译报错
        
        ht.put(1000,"aaa");
        ht.put(2,"bbb");
        ht.put(30000,"ccc");
        
        System.out.println(ht.contains("aaa"));
        System.out.println(ht.containsValue("aaa"));
        System.out.println(ht.containsKey(30000));//通常通过Key进行操作
        System.out.println(ht.get(30000));
        
        ht.put(30000,"ddd");//覆盖ccc
        System.out.println(ht.get(30000));
        
        ht.remove(2);
        System.out.println("size:"+ht.size());
        
        ht.clear();
        System.out.println("size:"+ht.size());
    }
}

1.1遍历方法

1.1.1根据Entry迭代器遍历

public static void traverseByEntry(Hashtable<Integer,String> ht){
    Integer Key;
    String Value;
    Iterator<Entry<Integer,String>> iter = ht.entrySet().iterator();
    
    while(iter.hasNext()){
        Map.Entry<Integer,String> entry = iter.next();
        //获取Key
        Key = entry.getKey();
        //获取Value
        Value = entry.getValue();
        
        System.out.println("Key:" + Key + ",Value:" + Value);
    }
}

1.1.2根据Key的Iterator遍历

public static void traverseByKeySet(Hashtable<Integer,String> ht){
    Integer Key;
    String Value;
    Iterator<Integer> iter = ht.KeySet().iterator();
    
    while(iter.hasNext()){
        Key = iter.next();
        //获取Value
        Value = ht.get(Key);
        
        System.out.println("Key:" + Key + ",Value:" + Value);
    }
}

1.1.3根据Key的Enumeration遍历

public static void traverseByKeyEnumeration(Hashtable<Integer,String> ht){
    Integer Key;
    String Value;
    Enumeration<Integer> keys = ht.keys();
    
    while(keys.hasMoreElements()){
        Key = keys.nextElement();
        //获取Value
        Value = keys.get(Key);
        
        System.out.println("Key:" + Key + ",Value:" + Value);
    }
}

2.HashMap

• K-V对，K和V都可以为null

• 不同步，多线程不安全

  • 同步操作：

    Map m = Collections.synchronizedMap(new HashMap(...));
    

• 无序的

• 主要方法：（与Hashtable一致）

  • clear：清空数据；
  • containsValue：判定是否包含某一个值；
  • containsKey：判定是否包含某一个Key；
  • get：根据Key获取相应的值；
  • put：增加新的K-V对；
  • remove：删除某一个K-V对；
  • size：返回数据大小

3.LinkedHashMap

• 基于双链表的维持插入顺序的HashMap
• LinkedHashMap遍历的顺序和插入的顺序保持一致

4.TreeMap

• 基于红黑树的Map，可以根据key的自然排序或者compareTo方法进行排序输出
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3ddiH6tP-1629125335351)(C:\Users\10637\AppData\Roaming\Typora\typora-user-images\image-20210805172609726.png)]

• TreeMap的遍历顺序是按照大小或者compareTo方法规定的

5.Properties

• 继承于Hashtable
• 可以将K-V对保存在文件中
• 适用于数据量少的配置文件
• 继承自Hashtable的方法：
  • clear：清空数据；
  • contains：等同于containsValue；
  • containsValue：判定是否包含某一个值；
  • containsKey：判定是否包含某一个Key；
  • get：根据Key获取相应的值；
  • put：增加新的K-V对；
  • remove：删除某一个K-V对；
  • size：返回数据大小
• 从文件加载的load方法，写入到文件中的store方法
  • load是加载源文件中所有的K-V对，store是将所有K-V对写入到文件中
• 获取属性getProperty，设置属性setProperty
  • getProperty是获取某一个key所对应的valu，setProperty是写入一个K-V对

七、工具类

1.JCF的工具类

• 不存储数据，而是在数据容器上实现高效操作
  • 排序
  • 搜索
• Arrays类
• Collections类

1.1Arrays：处理对象是数组

• 排序：对数组排序，sort/parallelSort

• 查找：从数组中查找一个元素，binarySearch（二分法查找）

• 批量拷贝：从源数组批量复制元素到目标数组，copyOf

• 批量赋值：对数组进行批量赋值，fill

  public static void fillTest(){
      int[] a = new int[10];
      Arrays.fill(a,100);//10个元素全部赋值100
      Arrays.fill(a,2,8,200);//第2个元素到第8个元素之间全部赋值200
  }
  

• 等价性比较：判定两个数组内容是否相同，equals

1.2包装器类

1.2.1Collections

• 处理对象是Collection及其子类

• 排序：对List进行排序，sort

• 搜索：从List中搜索元素，binarySearch

• 批量赋值：对List批量赋值，fill

• 最大、最小：查找集合中最大、最小值，max，min

  • 反序：将List反序排列，reverse

1.2.2对象比较

对象排序需要遵循一定的规则。Integer对象可以自然按照数值大小进行排序。而普通的自定义对象无法排序。因此，普通的自定义对象需要实现Comparable接口，按照compareTo方法所规定的原则进行排序。

• 对象实现Comparable接口（需要修改对象类）
  • compareTo方法
    • 大于号 > 返回1，==返回0，< 返回-1
  • Arrays和Collections在进行对象sort时，自动调用该方法
• 新建Comparator（适用于对象类不可更改的情况）
  • compare方法
    • 大于号 >返回1，==返回0，<返回-1
  • Comparator比较器将作为参数提交给工具类的sort方法