数据结构与算法学习—数据结构篇（线性表）（默然回首，夯实基础）

昨晚看了某B站主播的讲解，原来数据结构与算法才是校招面试的重点；在目前比较迷茫的准备中，也算是一盏明灯告诉我以后的这段时间该怎么准备了；接下来就是，重点复习一下数据结构与算法的基础知识，做一下leetcode上的题，希望在找工作之前能做完一半的题吧。

数据结构比较常问的就是：二叉树、红黑树、二叉查找树（BST）、平衡二叉树（Self-balancing binary search tree）、B-树，B+树与B*树的优缺点比较、 LSM 树这些知识点。
那接下来就一个骨头一个骨头的啃吧…

1.数据结构和算法概述

1.1什么是数据结构？

官方解释：
数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科。
大白话：
数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据；
**

1.2数据结构分类

**
传统上，我们可以把数据结构分为逻辑结构和物理结构两大类。

逻辑结构分类：
逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类，也是后面课题中需要关注和讨论的问题。
a.集合结构：集合结构中数据元素除了属于同一个集合外，他们之间没有任何其他的关系。

b.线性结构：线性结构中的数据元素之间存在一对一的关系。

c.树形结构：树形结构中的数据元素之间存在一对多的层次关系

d.图形结构：图形结构的数据元素是多对多的关系

物理结构分类：
逻辑结构在计算机中真正的表示方式（又称为映像）称为物理结构，也可以叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构。
顺序存储结构：
把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的，比如我们常用的数组就是顺序存储结构。

顺序存储结构存在一定的弊端，就像生活中排时也会有人插队也可能有人有特殊情况突然离开，这时候整个结构都处于变化中，此时就需要链式存储结构。
链式存储结构：
是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此在链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置

2、线性表

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。

前驱元素：
若A元素在B元素的前面，则称A为B的前驱元素
后继元素：
若B元素在A元素的后面，则称B为A的后继元素
线性表的特征：
数据元素之间具有一种“一对一”的逻辑关系。

1. 第一个数据元素没有前驱，这个数据元素被称为头结点；
2. 最后一个数据元素没有后继，这个数据元素被称为尾结点；
3. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
   如果把线性表用数学语言来定义，则可以表示为(a1,…ai-1,ai,ai+1,…an)，ai-1领先于ai,ai领先于ai+1，称ai-1是ai的前驱元素，ai+1是ai的后继元素；
   线性表的分类：
   线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。
   2.1 顺序表
   顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上响应的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系
   
   2.1.1 顺序表的实现
   顺序表API设计：
   
   顺序表的代码实现：

//顺序表代码
package Array;

public class List<T>{
    //存储元素的数组
    private T[] eles;
    //记录当前的元素的个数
    private int size;
    public List(){
    	
    }
    //构造方法
    public List(int capacity){
        eles = (T[])new Object[capacity];
        size = 0;
    }
    //将一个线性表设置为空表
    public void clear(){
        size = 0;
    }
    //判断当前线性表是否为空表
    public boolean isEmpty(){
        return size == 0;
    }
    //获取线性表的长度
    public int getSize(){
        return size;
    }
    //获取指定位置的元素
    public T get(int i){
        if (i < 0 || i>=size)
            throw new RuntimeException("当前元素不存在");
        return eles[i];

    }
    //向线性表中添加数据
    public void insert(T t){
        if(size == eles.length)
            throw new RuntimeException("当前表已经满了");
        eles[size] = t;
        size++;
    }
    //在i元素处插入元素t
    public void insert(int i,T t){
        if (i == eles.length){
            throw new RuntimeException("当前表已满");
        }
        if(i<0 || i>=size)
            throw new RuntimeException("插入的位置不合法");
        //把i位置的元素腾出来，i位置及后面的元素依次向后移动一位
        for(int j = size;j>i;j--){
            eles[j] = eles[j-1];
        }
        eles[i] = t;
        size++;
    }
    //删除指定位置i处的元素，并返回该元素
    public T remove(int i){
        if (i < 0|| i>size){
            throw new RuntimeException("当前删除的元素不存在");
        }
        T res = eles[i];
        //把i位置后面的元素都向前移动一位
        for(int j = i;j<size-1;j++){
            eles[j] = eles[j+1];
        }
        size--;
        return res;
    }
    //查找t元素第一次出现的位置
    public int find(T t){
        if (t == null)
            throw new RuntimeException("删除的元素不合法");
        for (int i = 0;i<eles.length;i++){
                if (eles[i] == t){
                    return i;
                }
            }
        
        return -1;
    }
    }

//测试program
package Array;

public class ListTest {

	public static void main(String[] args) {
		List<String> list = new List<String>(10);
		list.insert("lisi");
		list.insert("zhangsan");
		int i = list.getSize();
		System.out.println(list);
		System.out.println(i);
	}

}

2.1.2 顺序表的遍历
一般作为容器存储数据，都需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。
在java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们SequenceList也能支持foreach循环，则需要做如下操作：
1.让SequenceList实现Iterable接口，重写iterator方法；
2.在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法；
代码：

//顺序表代码
import java.util.Iterator;
 
public class SequenceList<T> implements Iterable<T>{
    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;
 
    //构造方法
    public SequenceList(int capacity){
        eles = (T[])new Object[capacity];
        N=0;
    }
 
    //将一个线性表置为空表
    public void clear(){
        N=0;
    }
 
    //判断当前线性表是否为空表
    public boolean isEmpty(){
        return N==0;
    }
 
    //获取线性表的长度
    public int length(){
        return N;
    }
 
    //获取指定位置的元素
    public T get(int i){
        if (i<0 || i>=N){
            throw new RuntimeException("当前元素不存在！");
        }
        return eles[i];
    }
    
    //向线型表中添加元素t
    public void insert(T t){
        if (N==eles.length){
            throw new RuntimeException("当前表已满");
        }
        eles[N++] = t;
    }
  //在i元素处插入元素t
    public void insert(int i,T t){
        if (i==eles.length){
            throw new RuntimeException("当前表已满");
        }
 
        if (i<0 || i>N){
            throw new RuntimeException("插入的位置不合法");
        }
 
        //把i位置空出来，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){
        if (i<0 || i>N-1){
            throw new RuntimeException("当前要删除的元素不存在");
        }
        //记录i位置处的元素
        T result = eles[i];
        //把i位置后面的元素都向前移动一位
        for (int index=i;index<N-1;index++){
            eles[index]=eles[index+1];
        }
 
        //当前元素数量-1
        N--;
        return result;
    }
    //查找t元素第一次出现的位置
    public int indexOf(T t){
        if(t==null){
            throw new RuntimeException("查找的元素不合法");
        }
 
        for (int i = 0; i < N; i++) {
            if (eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
 
    //打印当前线性表的元素
    public void showEles(){
        for (int i = 0; i < N; i++) {
            System.out.print(eles[i]+" ");
        }
        System.out.println();
    }
 
    
    @Override
    public Iterator iterator() {
        return new SIterator();
    }
 
    private class SIterator implements Iterator{
        private int cur;
        public SIterator(){
            this.cur=0;
        }
        @Override
        public boolean hasNext() {
            return cur<N;
        }
        
        @Override
        public T next() {
            return eles[cur++];
        }
    }
}
 
//测试代码
public class Test {
    public static void main(String[] args) throws Exception {
        SequenceList<String> squence = new SequenceList<>(5);
        //测试遍历
        squence.insert(0, "姚明");
        squence.insert(1, "科比");
        squence.insert(2, "麦迪");
        squence.insert(3, "艾佛森");
        squence.insert(4, "卡特");
 
        for (String s : squence) {
            System.out.println(s);
        }
    }
}

2.1.3 顺序表的容量可变
在之前的实现中，当我们使用SequenceList时，先new SequenceList(5)创建一个对象，创建对象时就需要指定容器的大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了5个元素，还要继续插入数据，则会报错，就不能插入了。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该考虑它的容量的伸缩性。考虑容器的容量伸缩性，其实就是改变存储数据元素的数组的大小，那我们需要考虑什么时候需要改变数组的大小？

1.添加元素时：
添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个是原数组两倍容量的新数组存储元素。

2.移除元素时
移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的1/2的新数组存储元素。

//顺序表代码

public class SequenceList<T> implements Iterable<T>{

    //存储元素的数组

   private T[] eles;

    //记录当前顺序表中的元素个数

    private int N;

    //构造方法

    public SequenceList(int capacity){

        eles = (T[])new Object[capacity];

        N=0;

    }
    //将一个线性表置为空表

    public void clear(){

        N=0;

    }
    //判断当前线性表是否为空表

    public boolean isEmpty(){

        return N==0;

    }
    //获取线性表的长度

    public int length(){

        return N;

    }
    //获取指定位置的元素

    public T get(int i){

        if (i<0 || i>=N){

            throw new RuntimeException("当前元素不存在！");

        }

        return eles[i];

    }
    //向线型表中添加元素t

    public void insert(T t){

        if (N==eles.length){

            resize(eles.length*2);

        }

        eles[N++] = t;

    }
    //在i元素处插入元素t

    public void insert(int i,T t){
        if (i<0 || i>N){

            throw new RuntimeException("插入的位置不合法");

        }

        //元素已经放满了数组，需要扩容

        if (N==eles.length){

            resize(eles.length*2);

        }
        //把i位置空出来，i位置及其后面的元素依次向后移动一位
        for (int index=N-1;index>i;index--){

            eles[index]=eles[index-1];

        }
        //把t放到i位置处

        eles[i]=t;

        //元素数量+1

        N++;

    }
    //删除指定位置i处的元素，并返回该元素

    public T remove(int i){

        if (i<0 || i>N-1){

            throw new RuntimeException("当前要删除的元素不存在");

        }
        //记录i位置处的元素

        T result = eles[i];

        //把i位置后面的元素都向前移动一位

        for (int index=i;index<N-1;index++){

            eles[index]=eles[index+1];

        }
        //当前元素数量-1

        N--;
        //当元素已经不足数组大小的1/4,则重置数组的大小

        if (N>0 && N<eles.length/4){

            resize(eles.length/2);

        }
        return result;

    }

    //查找t元素第一次出现的位置

    public int indexOf(T t){

        if(t==null){

            throw new RuntimeException("查找的元素不合法");

        }
        for (int i = 0; i < N; i++) {

            if (eles[i].equals(t)){

                return i;

            }

        }

        return -1;

    }
    //打印当前线性表的元素

    public void showEles(){

        for (int i = 0; i < N; i++) {

            System.out.print(eles[i]+" ");

        }

        System.out.println();

       }
    @Override

    public Iterator iterator() {

        return new SIterator();

    }
    private class SIterator implements Iterator{

        private int cur;

        public SIterator(){

            this.cur=0;

        }

        @Override

        public boolean hasNext() {

            return cur<N;

        }
        @Override

        public T next() {

            return eles[cur++