黑马程序员技术交流社区

标题: 【石家庄校区】数据结构 [打印本页]

作者: 1597854328 时间: 2019-3-7 19:39
标题: 【石家庄校区】数据结构
一  数据结构
      数据结构就是数据的存储方式；       容器可能有不同数据结构  如： Arraylist集合、 arr[]  数据结构是数组、HashSets集合的数据结构是数组+单链表。
      不同的数据结构，决定了存储方式不同
1 栈
特点：
      先进后出(FILO,First In Last Out)
      入口和出口在同一侧
适用场景：
      JVM中栈中程序运行机制
      反转内容（车尾变车头，进出在出来就反转了）
2 队列
特点：
      先进先出（FIFO，first in first out）
      出口入口在两侧
适用场景：
      处理高并发场景
      秒杀，抢购
      在线售票
3 数组
特点：
      查询快：地址连续，有索引（第一个元素地址值+索引）可以快速计算出该索引元素的地址值
      增删慢：长度固定，增删需要新建数组并复制数据
适用场景：
      查询多，增删少
4 链表
链表: 链表由多个节点(Node / Entry) 组成
      特点：
            查询慢：地址不连续，每次查询从头开始
            增删快：增删元素对链表整体机构无影响,只需要修改保存的下一个节点的地址值
适用场景：
      查询少，增删多
补充
参考Map中Entry节点
5 红黑树
特点:       元素存储过程中就完成了大小排序       查询比链表快, 增删比数组快 (数组和链表的折中)
适用场景:       查询和增删都有, 需要元素自动排序的场景
二  集合

1 Collection
1.1List集合
特点：       （数组结构决定）
      1. 元素存取有序 (存入和取出元素的顺序一致)
      2. 元素可以重复
      3.有索引
特有方法：
[Java] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important]

[color=white !important]?

[AppleScript] 纯文本查看 复制代码

void add(int index,E element)

E get(int index)

E remove(int index)

E set(int index,E element)

1.1 ArrayList集合
ArrayList底层的数据结构:       数组ArrayList的特点:       查询快       增删慢       线程不安全, 效率高       不使用锁对象
ArrayList适用场景:       存储的数据查询多, 增删少的场景
1.2 LinkedList集合
LinkedList底层的数据结构:       链表LinkedList的特点:       查询慢       增删快       线程不安全, 效率高不使用锁对象LinkedList适用场景:       存储的数据查询少, 增删多的场景
特有方法：
[Java] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important]

[color=white !important]?

void addFirst(E e)
void addLast(E e)
E getFirst(E e)
E getLast(E e)
E removeFirst()
E Pop()
void push(E e)

1.3 Vector集合
目前几乎无人使用
2.1 Set集合
特点：
      元素不能重复重写了hashCode()和equals()方法
      应用：对集合重复元素去重
      无索引       哈希表结构（数组+链表结构/红黑树）
      无序（TreeSet例外）       哈希表结构
2.2 HashSet集合
常用方法：
      boolean add(E e)
自定义的JavaBean对象去重：
      重写hashCode()和equals()方法  Alt+Ins
补充：
HashSet集合保证添加元素不重复的原理:
      调用 add(E e) 添加元素时, 先调用 hashCode() 获取哈希值, 和当前HashSet集合中的元素比较
      如果哈希值不同, 则认为元素不重复, 添加, 并返回true
      如果哈希值相同, 则有可能是哈希冲突, 所以继续调用元素的 equals() 方法和所有哈希值相同的元素比较
      如果 equals() 比较所有元素都没有相同的, 则认为元素不重复, 添加, 并返回true
      如果 equals() 比较出有相同的元素, 则认为元素重复, 不添加, 并返回false
2.3 LinkedHashSet集合
特有特点：
      存取有序  哈希表+链表（数组+链表/红黑树+链表）
2.4 可变参数
格式: 用在方法的参数中
      修饰符返回值类型方法名(参数类型... 变量名) {
         // 可以直接将变量名当作数组名使用
      }
注意事项:
      1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个
      2. 一个方法的参数列表中, 只能有一个可变参数
      3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后
举例:
[Java] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important]

[color=white !important]?

public static void main(String[] args) {
      int sum2 = getSum(6, 7, 2, 12, 2121);
      System.out.println(sum2);
}
//可变参数写法
public static int getSum(int... arr) {
      int sum = 0;
      for (int a : arr) {
         sum += a;
      }
      return sum;
}
}

2 Map
1  概述：
      Java中提供的专门的集合类用来存放对应关系（映射）的对象，即java.util.Map接口。
      Map接口下的集合与Collection接口下的集合，他们存储数据的形式不同，如图：

      Collection中的集合，元素是孤立存在的
      Map中的集合，元素是成对存在的。每个元素由键和值两部分组成，通过键可以找到对应的值。
      Collection中的集合叫单列集合，Map中的集合叫双列集合。
注意：Map中的集合不能包含重复的键，值可以重复，每个键只能对应一个值。
2 Map常用子类
      HsahMap:存储元素采用的哈希表结构，元素的存取顺序不能保证一致。由于要保证键的唯一，不重复，需要重写键的hashCode()方法、equals()方法。
      LinkedHashMap:HashMap下的子类，存储数据采用哈希表结构（保证元素存取顺序一致）+链表结构（保证键值不重复，需重写hashCode()、equals()）。
3 Map接口中的常用方法
[Java] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important]

[color=white !important]?

public V put(K key, V value) : 把指定的键与指定的值添加到Map集合中。
public V remove(Object key) : 把指定的键所对应的键值对元素在Map集合中删除，返回被删除元素的值。
public V get(Object key) 根据指定的键，在Map集合中获取对应的值。
public Set<K> keySet() : 获取Map集合中所有的键，存储到Set集合中。
public Set<Map.Entry<K,V>> entrySet() : 获取到Map集合中所有的键值对对象的集合(Set集合)。

Map接口的方法演示
[Java] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important]

[color=white !important]?

public class MapDemo {
public static void main(String[] args) {
      HashMap<String, String>  map = new HashMap<String, String>();
      map.put("黄晓明", "杨颖");
      map.put("文章", "马伊琍");
      map.put("邓超", "孙俪");
      System.out.println(map);
      System.out.println(map.remove("邓超"));
      System.out.println(map);
      System.out.println(map.get("黄晓明"));
      System.out.println(map.get("邓超"));
}
}

4  Map集合遍历键找值方式
      获取Map中的所有键，由于键唯一，所以返回一个Set集合存储所有的键  Keyset()。
      遍历键的set集合，得到每一个键值。
      根据键，获取键对应的值。get(K key)。
代码演示：
[Java] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important]

[color=white !important]?

[AppleScript] 纯文本查看 复制代码

public class MapDemo01 {

    public static void main(String[] args) {

        HashMap<String, String> map = new HashMap<String,String>();

        map.put("胡歌", "霍建华");

        map.put("郭德纲", "于谦");

        map.put("薛之谦", "大张伟");

 Set<String> keys = map.keySet();

        for (String key : keys) {

            String value = map.get(key);

            System.out.println(key+"的CP是："+value);

        } 

    }

}

5 Entry键值对对象
Entry将键值对的对应关系封装成了对象，即键值对对象，这样我们可以在遍历Map集合时就可以从每一个键值对Entry对象中获取对应的键与对应的值。
Entry获取对应的键和对应的值方法：
      public K getKey() ：获取Entry对象中的键。
      public V getValue() ：获取Entry对象中的值。
6  Map集合遍历键值对方式

[AppleScript] 纯文本查看 复制代码

public class MapDemo02 {

    public static void main(String[] args) {

        HashMap<String, String> map = new HashMap<String,String>();

        map.put("胡歌", "霍建华");

        map.put("郭德纲", "于谦");

        map.put("薛之谦", "大张伟");

        Set<Entry<String,String>> entrySet = map.entrySet();

        for (Entry<String, String> entry : entrySet) {

            String key = entry.getKey();

            String value = entry.getValue(); 

            System.out.println(key+"的CP是:"+value);

        }

    }

}

[color=white !important]

[color=white !important]?

7 LinkedHashMap（元素唯一、存取有序、查询快）

public class LinkedHashMapDemo {
public static void main(String[] args) {
      LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();
      map.put("邓超", "孙俪");
      map.put("李晨", "范冰冰");
      map.put("刘德华", "朱丽倩");
      Set<Entry<String, String>> entrySet = map.entrySet();
      for (Entry<String, String> entry : entrySet) {
         System.out.println(entry.getKey() + "  " + entry.getValue());
      }
}
}

补充知识点
1、JDK9对集合添加的优化
Of（）方法

[color=white !important]

[color=white !important]?

public class HelloJDK9 {
public static void main(String[] args) {
      Set<String> str1=Set.of("a","b","c");
      System.out.println(str1);
      Map<String,Integer> str2=Map.of("a",1,"b",2);
      System.out.println(str2);
      List<String> str3=List.of("a","b");
      System.out.println(str3);
}

2、Debug追踪
使用IDEA的断点调试功能，查看程序的运行过程
3 Collections集合工具类
1 常用方法：

[color=white !important]

[color=white !important]?

static <T> boolean addAll(Collection<T> c,T...elements)
static void shuffle(List<?> list)
static <T> void sort(List<T> list)：实现Comparable<E>接口，重写int CompareTo(T e)方法
static <T> void sort(List<T> list,Comparator<?super T>):比较器排序

2  Collections集合工具类：自定义JavaBean对象sort<List<T> list>排序
2.1 第一种：
需要实现 Comparable<E> 接口, 重写 int compareTo(E e) 方法
      大小的比较通过 compareTo() 方法的返回值确定:
      负数: 当前元素比被比较元素小
      0: 当前元素与被比较元素相等
      正数: 当前元素比被比较元素大
规则:
      this-参数: 升序
      参数-this: 降序
@Override
public int compareTo(Person o) {
      // 比较的规则:
      // this.属性值 - 参数o.属性值: 升序
      // 参数o.属性值 - this.属性值: 降序
      return this.age - o.age;  // 升序
//       return o.age - this.age;  // 升序
}
2.2 第二种：
Comparator使用方式:
定义类作为比较器, 实现Comparator接口, 重写int compare(E o1, E o2)方法, 泛型为要比较的元素的类型
在Collections.sort(List<T> list，Comparator<? super T>)方法中传入自定义比较器对象
规则:
      o1-o2: 升序
      o2-o1: 降序

[color=white !important]

[color=white !important]?

Collections.sort(list, new Comparator<Person>() {
         @Override
         public int compare(Person o1, Person o2) {
            // o1 - o2: 升序
            // o2 - o1: 降序
            return o1.getAge() - o2.getAge();
         } });

Comparable接口和Comparetor接口的区别：
Comparable: 让JavaBean自身具有可比较性 (自己和其他人比)
Comparator: 定义一个比较器类, 用比较器对象比 (让第三个人来帮两个人比较)
三  异常
Throwable;
Error ;
Exception----->runtime Exption
java .long Throwable 体系最顶层
      |__Error          不能处理的错误
      |__Erxception          可以处理的异常
      |__run time Expetion    异常的子类
Exception in thread()"main----主线程异常
数学计算异常,原因是除以0;
1  异常的分类
      1 Error;错误错误就相当于得了一个无法治愈得病,没法解决错误(Error): 不能捕获处理的严重问题. 绝症
必须将程序停下来, 修改代码才能解决错误的类名都是 "XxxError" 方式
   2 异常(Exception): 可以捕获处理的问题. 发烧感冒吃个药就好了程序执行起来后, 如果有合适的处理方式, 即使发生异常, 程序也能处理该异常并继续运行
异常的类名都是 "XxxException" 方式；
编译时异常:
   （1）编译时期就会发生的异常, 必须在编译时期处理
   （2）运行时异常:编译时正常, 运行时才会发生的异常

2 throw与throws
throw 关键字作用制造一个异常抛出一个异常必须写在方法内部
throw 创建便以异常必须处理要么throws要try catch
格式:
   throw new 异常类名("异常原因字符串");
举例
      throw new NullPointerException("要访问的arr数组不存在");
      throw new ArrayIndexOutOfBoundsException("该索引在数组中不存在，已超出范围");
throws 后面代码不会被执行 jvm中断处理
Throw和throws的区别

3 try catch执行流程
try下面抛完异常(只会捕捉一个异常)直接进行catch
继续执行catch下面的代码;
若catch没有解决异常那么交给虚拟机运行终止运行所以下面代码不会被执行
Throwable三种成员方法

[color=white !important]

[color=white !important]?

String getmessage();返回此throwble 的简短描述
String tostring();返回此throwable的详细字符串
void PrintStackTrace();jvm打印异常,默认此方法,打印的异常信息是最全的

4 finally代码块

[color=white !important]

[color=white !important]?

try {}
catch(){}
finally{
};

无论是否出现异常都会被执行
finally不能单独运行,必须和try 一块使用
一般用于资源释放(资源回收),无论是否出现异常,最后都要资源释放();
注意如果finally代码块中有return 语句,则永远返回fianlly中的return语句的值,所以应避免 finally中写return语句
5 子类集成父类重写方法时
可以有三种方式
1.抛出和父亲相同的异常
2.抛出父亲异常的子类
3.不抛出异常
父类方法没有抛出异常,子类重写父类方法时也不可声明抛出
只能直接在方法内 try catch
6 自定义异常
如果java提供给我们的不能满足我们需要自己定义异常类继承 Exception或者RuntimeException
我们需要生成一个有参构造
一个无参构造
7 异常的处理方式有两种

一种throws交给jvm虚拟机yunxing
另一种是try catch
8 异常的处理流程

<一>运行时异常
[Java] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important]

[color=white !important]?

ArrayIndexOutofboundsException 数组索引越界异常
NullpointerException;空指针异常
ClassCastException
IndexOutOfBoundsException 索引越界异常
ConcurrentModificationException
ArithmeticException 算术运算异常
NumberFormatException 数字格式化异常

<二>编译时异常

[AppleScript] 纯文本查看 复制代码

FileNotFoundException  文件地址异常

IOException     

ParseException 解析异常

[color=white !important]

[color=white !important]?

创建异常类对象时调用异常类的异常方法时必须声明异常或者解决异常

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2