java之集合-ag真人游戏

数据结构

含义：就是在计算机的缓存，内存，硬盘如何组织管理数据的；重点是在结构上，是按照什么结构来管理我们的数据的

数据结构分类：

• 逻辑结构：思想上的结构->线性表(数组、链表)、图、树、栈、队列
• 物理结构：逻辑上的结构->紧密结构(顺序结构)、跳转结构(链式结构)

逻辑结构和物理结构关系

• 线性表的逻辑结构，对应的真实结构如果是紧密结构，那么典型例子就是数组
• 线性表的逻辑结构，对应的真实结构如果是跳转结构，那么典型例子就是链表 

紧密结构优缺点

• 优点：寻址快（查找元素快）
• 缺点：增删慢

跳转结构优缺点

• 优点：增删快
• 缺点：查询慢

含义：线性表是n个类型相同数据元素的有限序列。

线性表的逻辑结构

线性表的特点

• 相同数据类型：线性表的每个数据元素是具有相同的属性的元素
• 序列(顺序性)：除了表头和表尾之间的所有元素都有且仅有一个直接前驱和直接后继
• 有限：线性表中数据元素的个数n是一个有限值

含义：链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表分类

• 单向链表：链表中的每个数据都保存着数据与下一个元素的地址
• 双向链表：链表中的每个元素都保存着数据与上一个元素地址以及下一个元素的地址，首元素的上一个地址为null，尾地址的下一个地址为null
• 循环链表：链表中的每个元素都保存着数据与上一个元素地址以及下一个元素的地址，首元素上一个元素地址为尾元素地址，尾元素的下一个地址为首元素地址

单向链表

双向链表

循环链表

含义：树是(n>=0)个节点的有限集合，n=0时称为空树

任何一个非空树的满足条件

1. 有且仅有一个特定的称为根的节点
2. 当n>1时，其余节点可分为m(m>0)个互不相交的有限集合，t1，t2，t3……tm，其中，每个集合本身又是一棵树，称为根节点的子树 

注意：

• 树是一种递归的数据结构
• 除了根节点以外的所有节点，有且仅有1个前驱节点
• 树中的所有节点可以有0或多个后继节点 

树的分析

根节点：a

祖先节点：a，b，d都为i的祖先节点

子孙节点：b，d，i，k为a的子孙节点

双亲节点：a为b的双亲节点，也为c的双亲节点

孙子节点：b为a的孙子节点

兄弟节点：有相同双亲的节点（如b和c）

树中的基本概念

节点的度：树中的1个节点的子节点个数（如a的度为2，b的度为3）

树的度：树中节点的最大度（如上面树的度为3）

分支节点：度大于0的节点

叶子节点：度为0的节点

节点的层次：从根节点开始定义，根节点为第一次，他的子节点为第二层，以此类推

节点的深度：从根节点开始，自顶向下逐层累加

节点的高度：从叶子节点开始从底向上逐层累加

树的高度：树中节点的最大层数

有序树：树中节点的子树从左到右是有次序的

无序树：树中节点的子树从左到右没有次序，可以交换

路径：树中两个节点的路径是由这两个节点之间所经过的节点序列构成

路径的长度：路径上所经过边的个数

二叉树

含义：二叉树又称二叉查找树，亦称二叉搜索树，二叉树（binary tree）是指树中结点的度不大于2的有序树，它是一种最简单且最重要的树。

二叉树的特性：任意一个左子树的节点值都比当前节点的值小，任意一个右子树的节点值都比当前节点值大

二叉树的遍历

• 先序遍历：根节点——>左子树——>右子树（a,b,d,c,e,g,f）
• 中序遍历：左子树——>根节点——>右子树（b,d,a,e,g,c,f）
• 后序遍历：左子树——>右子树——>根节点（d,b,g,e,f,c,a）

注意：数组和集合都是对数据进行存储操作的，简称容器，但这里的存储指的是内存层面的存储，而不是持久化的存储

数组特点：

• 数组一旦创建，长度不可改变
• 数组中可以存放引用数据类型与基本数据类型
• 一旦声明了类型以后，数组中只能存放这个类型的数据。数组中只能存放同一种类型的数据
• 删除，增加元素效率低
• 数组只能获取数组整个长度，实际元素数量没有办法获取，没有提供对应的方法或者属性来获取
• 数组储存：有序、可重复，对于无序，不可重复的数据，数组不能满足要求

集合特点：

• 只能存放引用类型数据，不能存放基本数据类型数据
• 集合的长度是可变的
• 集合可以存放不同数据类型

集合结构图

继承结构特点

list接口：数据有下标，有序，可重复

• arraylist类：底层维护的是数组——紧密结构
• linkedlist类：底层维护的是链表——跳转结构（虚拟下标）

set接口：数据无下标，无序，不可重复

• hashset类：底层hashmap
• treeset类：底层treemap

map接口：键值对的方式存数据

• hashmap类：底层数组 链表（哈希表）
• treemap类：底层二叉树

常用方法

clear()：移除此集合中的所有元素，没有返回值

equals(object o)：判断此集合对象与指定对象是否相等，相等返回true，否则为false

        collection c = new arraylist<>();
        c.add(18);
        c.add(34);
        c.add(18);
        list list = arrays.aslist(new integer[]{1,4,9});
        c.addall(list);//将另一个集合加入该集合中
        c.remove(18);
        system.out.println(c);
        system.out.println("集合是否包含18这个元素" c.contains(18));
        system.out.println("集合的长度为" c.size());
        c.clear();//清空集合所有元素
        system.out.println("集合是否为空" c.isempty());
        system.out.println(c.tostring());
        collection c1=new arraylist<>();
        system.out.println("c和c1集合内容是否一样" c.equals(c1));//判断集合是否一样

集合的遍历

        collection collection = new arraylist<>();
        collection.add(18);
        collection.add(34);
        collection.add("18");
       //对集合进行遍历
        //增强for循环
        for(object o:collection){
            system.out.println(o);
        }
        //迭代器遍历
        iterator iterator = collection.iterator();
        //如果有下一个元素就返回true，否则返回false
        while (iterator.hasnext()){
            //打印该（下一个）元素，并且指针下移一位
            system.out.println(iterator.next());
        }

list接口：数据有下标，有序，可重复

常用方法

remove(int index)：根据下标移除列表中指定位置的元素， 返回值为移除的元素

注意：可以看到list扩展的方法都和索引相关 

        //集合下标从0开始
        list list=new arraylist();
        list.add(13);
        list.add(17);
        list.add(true);
        list.add(2);
        list.add(1,89);//在下标为1的位置增加89
        list.set(3, 66);//将下标为3位置的元素改为66
        //注意：list的remove有2个方法，分别传入索引与object类型
        list.remove(2);//索引的优先级高，如果索引和元素恰好一样，那么会把索引下的元素删除。
        list.remove((object)2);//删除为2的元素
        system.out.println(list);
        system.out.println("下标为0的元素" list.get(0));

list集合的遍历

        //list集合的遍历
        //for循环
        for (int i=0;i