数据结构基础

2019-02-17 01:49:00来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

1.1 数据结构介绍

数据结构:数据用什么样的方式组合在一起。

1.2 常见的数据结构

数据存储的常用结构有:栈、队列、数组、链表和红黑树。

栈:

  • 栈:stack,又称为堆栈,它是运算受限的线性表,其限制是仅允许在标的一端进行插入和删除操作,不允许在其他任何位置进行添加、查找、删除等操作。

  简单来说:采用该结构的集合,对元素的存取有如下的特点。

  • 先进后出(即,存进去的元素,要在它后面的元素依次取出后,才能取出该元素)。例如,子弹压进弹夹,先压进去的子弹在下面,后压进去的子弹在上面,

当开枪的时候,先弹出上面的子弹,然后才弹出下面的子弹。

  • 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为压栈(PUSH),删除则称为弹栈(POP)

这里需要理解两个名词:

  • 压栈:就是存元素。即,把元素存储到栈的顶端位置,栈中已有元素依次向栈底方向移动一个位置。
  • 弹栈:就是取元素。即,把栈的顶端位置元素取出,栈中已有元素依次向栈顶方向移动一个位置。

代码:

public class MyStack {
    private int[] array;
    private int size;
    private int top;
     
    public MyStack(int size){
        this.size = size;
        array = new int[size];
        top = -1;
    }
     
    //压栈
    public void push(int value){
        if(top < size-1){
            array[++top] = value;
        }
    }
     
    //弹栈
    public int pop(){
        return array[top--];
    }
     
    //获取栈顶数据
    public int getTop(){
        return array[top];
    }
     
    //判断栈是否为空
    public boolean isEmpty(){
        return (top == -1);
    }
     
    //判断栈是否满了
    public boolean isFull(){
        return (top == size-1);
    }
     
 
}

  代码测试:

public class Test {
    public static void main(String[] args) {
        MyStack stack = new MyStack(3);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        System.out.println(stack.getTop());
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
         
    }
 
}

  结果:

队列

  • 队列:queue,简称队,它同堆栈一样,也是一种运算受限的线性表,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。

简单的说,采用该结构的集合,对元素的存取有如下的特点:

  • 先进先出(即,存进去的元素,要在后它前面的元素依次取出后,才能取出该元素)。例如,小火车过山洞,车头先进去,车尾后进去;车头先出来,车尾后出来。
  • 队列的入口、出口各占一侧。例如,下图中的左侧为入口,右侧为出口。

数组

  • 数组:Array,是有序的元素序列,数组是在内存中开辟一段连续的空间,并在此空间存放元素。就像是一排出租屋,有100个房间,从001到100每个房间都有固定编号,通过编号就可以快速找到租房子的人。

简单来说,采用该结构的集合,对元素的存取有以下特点:

  • 查找元素快:通过索引,可以快速访问指定位置的元素

  • 增删元素慢:指定索引增加元素:需要创建一个新的数组,将指定新元素存储在指定索引位置,再将原数组元素根据索引,复制到新数组对应索引的位置上

  • 指定索引位置删除元素:需要创建一个新数组,把原数组元素根据索引,复制到新数组对应的索引位置,原数组中指定索引位置元素不复制到新数组中。

链表

  • 链表:linked list,由一系列结点node(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。我们常说的链表结构有单向链表与双向链表,那么这里给大家介绍的是单向链表多个接地

简单来说,采用该结构的集合,对元素的存取有以下的特点:

  • 多个结点之间,通过地址进行连接。例如,多个人手拉手,每个人使用自己的右手拉住下个人的左手,依次类推,这样多个人就连在一起了。
  • 查找元素慢:想查找某个元素,需要通过连接的节点,依次向后查找指定元素。
  • 增删元素快:

红黑树

  • 二叉树:binary tree ,是每个结点不超过2的有序树(tree)。

简单的理解,就是一种类似于我们生活中树的结构,只不过每个结点上都最多只能有两个子结点。

二叉树是每个结点最多有两个子树的树结构。顶上的叫根结点,两边被称作“左子树”和“右子树”。

 

 

我们要说的是二叉树的一种比较有意思的叫做红黑树,红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。如图:

红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡,从而来提高效率。

2.1 HashSet集合存储数据的结构(哈希表)

  什么是哈希表?

  在JDK1.8之前,哈希表底层采用数组+链表实现,即使用数组处理冲突,同意hash值的链表都存储在一个数组内。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,哈希表存储采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

  简单的来说,哈希表是由数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,如下图所示。

 

 

为了方便理解可以结合一个存储流程图来说明一下:

总而言之,JDK1.8引入红黑树大程度优化了HashMap的性能,那么对于实际应用来讲保证HashSet集合元素的唯一,其实就是根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象,那么保证其唯一,就必须复写hashCode和equals方法建立属于当前对象的比较方式。

 

2.1 HashSet 存储自定义类型元素

  给HashSet中存放自定义类型元素时,需要重写对象中的hashCode和equals方法,建立自己的比较方式,才能保证HashSet集合中的对象唯一.

代码:

// 创建自定义学生类

public class Student {
    private int age;
    private String name;
    private double score;

    public Student() {
    }

    public Student(int age, String name, double score) {
        this.age = age;
        this.name = name;
        this.score = score;
    }


// 重写equal和hashCode方法,
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Student)) return false;
        Student student = (Student) o;
        return getAge() == student.getAge() &&
                Double.compare(student.getScore(), getScore()) == 0 &&
                Objects.equals(getName(), student.getName());
    }

    @Override
    public int hashCode() {
        return Objects.hash(getAge(), getName(), getScore());
    }

// 重写toString方法
@Override
  public String toString() {
        return "Student{" +
              "age=" + age +
              ", name='" + name + '\'' +
              ", score=" + score +
              '}'+"\n";
  }
// get, set 方法省略。

  

  创建测试类:

public class Demo15 {
    public static void main(String[] args) {
        // 创建HashSet集合,接收自定义类型数据。
        HashSet<Student> hs = new HashSet<>();
        Student s1 = new Student(19,"王小石",99.2);
        Student s2 = new Student(20,"雷纯",99.4);
        Student s6 = new Student(23,"戚少商",99.8);
        Student s3 = new Student(21,"温柔",99.6);
        Student s4 = new Student(22,"白愁飞",99.1);
        Student s5 = new Student(23,"戚少商",99.8);
       

     // 将数据添加到HashSet集合当中。
        hs.add(s1);
        hs.add(s2);
        hs.add(s3);
        hs.add(s4);
        hs.add(s5);
        hs.add(s6);

        System.out.println(hs);        

  结果:


原文链接:https://www.cnblogs.com/XJP-now/p/10367622.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Android中handler倒计时

下一篇:springBoot2 基础语法