1、顺序表

1.1 顺序表实现

 

 

package com.haifei.demo02linear;

import java.util.Iterator;

public class SequenceList <T>{

    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;

    //构造方法
    public SequenceList(int capacity){
        //初始化数组
        this.eles = (T[])new Object[capacity];
        this.N = 0;
    }

    //将线性表置空
    public void clear(){
        this.N = 0;
    }

    //判断当前线性表是否为空表
    public boolean isEmpty(){
        return N == 0;
    }

    //获取线性表长度
    public int length(){
        return N;
    }

    //获取线性表指定位置的元素
    public T get(int i){
        return eles[i];
    }

    //向线性表中追加元素t
    public void insert(T t){
        eles[N++] = t;
    }

    //在线性表索引i处插入元素t
    public void insert(int i, T t){
        //先把i索引处及其后面的元素依次向后移动一位
        for (int index=N-1; index>i; index--){
            eles[index] = eles[index-1];
        }
        //再将t元素添加到i索引处
        eles[i] = t;
    }

    //删除线性表索引i处的元素，并返回该元素
    public T remove(int i){
        //记录索引i处的元素
        T current = eles[i];
        //索引i处后面的元素依次向前移动一位
        for (int index=i; index<N-1; index++){
            eles[index] = eles[index+1];
        }
        //元素个数-1
        N--;
        //返回已删除元素
        return current;
    }

    //查照线性表中t元素第一次出现的位置
    public int indexOf(T t){
        for (int i=0; i<N; i++){
            if (eles[i].equals(t)){
                return i;
            }
        }
        return -1; //线性表当前不存在t元素
    }

}

View Code

package com.haifei.demo02linear.test;

import com.haifei.demo02linear.SequenceList;

public class Test01SequenceList {

    public static void main(String[] args) {
        //创建顺序表对象
        SequenceList<String> sl = new SequenceList<>(10);

        //测试插入
        sl.insert("姚明");
        sl.insert("科比");
        sl.insert("麦迪");
        sl.insert(1,"詹姆斯");
        //测试获取
        String getResult = sl.get(1);
        System.out.println("获取索引1处的结果为："+getResult); //詹姆斯
        //测试删除
        String removeResult = sl.remove(0);
        System.out.println("删除的元素是："+removeResult); //姚明
        //测试清空
        sl.clear();
        System.out.println("清空后的线性表中的元素个数为:"+sl.length()); //0
    }

}

View Code

 

1.2 顺序表遍历

 

 

 

 

package com.haifei.demo02linear;

import java.util.Iterator;

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

    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;

    //构造方法
    public SequenceList(int capacity){
        //初始化数组
        this.eles = (T[])new Object[capacity];
        this.N = 0;
    }

    //将线性表置空
    public void clear(){
        this.N = 0;
    }

    //判断当前线性表是否为空表
    public boolean isEmpty(){
        return N == 0;
    }

    //获取线性表长度
    public int length(){
        return N;
    }

    //获取线性表指定位置的元素
    public T get(int i){
        return eles[i];
    }

    //向线性表中追加元素t
    public void insert(T t){
        eles[N++] = t;
    }

    //在线性表索引i处插入元素t
    public void insert(int i, T t){
        //先把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){
        //记录索引i处的元素
        T current = eles[i];
        //索引i处后面的元素依次向前移动一位
        for (int index=i; index<N-1; index++){
            eles[index] = eles[index+1];
        }
        //元素个数-1
        N--;
        //返回已删除元素
        return current;
    }

    //查照线性表中t元素第一次出现的位置
    public int indexOf(T t){
        for (int i=0; i<N; i++){
            if (eles[i].equals(t)){
                return i;
            }
        }
        return -1; //线性表当前不存在t元素
    }


    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }
    private class SIterator implements Iterator{//内部类
        private int cusor;
        public SIterator(){
            this.cusor = 0;
        }
        @Override
        public boolean hasNext() {
            return cusor<N;
        }
        @Override
        public Object next() {
            return eles[cusor++];
        }
    }


}

View Code

package com.haifei.demo02linear.test;

import com.haifei.demo02linear.SequenceList;

public class Test01SequenceList {

    public static void main(String[] args) {
        //创建顺序表对象
        SequenceList<String> sl = new SequenceList<>(10);

        //测试插入
        sl.insert("姚明");
        sl.insert("科比");
        sl.insert("麦迪");
        sl.insert(1,"詹姆斯");
        //测试遍历
        for (String s : sl) {
            System.out.println(s);
        }
        /*
        姚明
        詹姆斯
        科比
        麦迪
         */
        System.out.println("========================");
        //测试获取
        String getResult = sl.get(1);
        System.out.println("获取索引1处的结果为："+getResult); //詹姆斯
        //测试删除
        String removeResult = sl.remove(0);
        System.out.println("删除的元素是："+removeResult); //姚明
        //测试清空
        sl.clear();
        System.out.println("清空后的线性表中的元素个数为:"+sl.length()); //0
    }

}

View Code

 

1.3 顺序表的容量可变

package com.haifei.demo02linear.test;

import com.haifei.demo02linear.SequenceList;

public class Test02SequenceList {

    public static void main(String[] args) {
        SequenceList<String> sl = new SequenceList<>(3);

        sl.insert("张三");
        sl.insert("李四");
        sl.insert("王五");
//        sl.insert("赵六"); //java.lang.ArrayIndexOutOfBoundsException: 3

    }

}

View Code

 

 

 

 

 

 

package com.haifei.demo02linear;

import java.util.Iterator;

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

    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中的元素个数
    private int N;

    //构造方法
    public SequenceList(int capacity){
        //初始化数组
        this.eles = (T[])new Object[capacity];
        this.N = 0;
    }

    //将线性表置空
    public void clear(){
        this.N = 0;
    }

    //判断当前线性表是否为空表
    public boolean isEmpty(){
        return N == 0;
    }

    //获取线性表长度
    public int length(){
        return N;
    }

    //获取线性表指定位置的元素
    public T get(int i){
        return eles[i];
    }

    //向线性表中追加元素t
    /*public void insert(T t){
        eles[N++] = t;
    }*/
    public void insert(T t){
        if (N == eles.length){ //扩容
            resize(2 * eles.length);
        }

        eles[N++] = t;
    }

    //在线性表索引i处插入元素t
    /*public void insert(int i, T t){
        //先把i索引处及其后面的元素依次向后移动一位
        for (int index=N-1; index>i; index--){
            eles[index] = eles[index-1];
        }
        //再将t元素添加到i索引处
        eles[i] = t;
    }*/
    /*public void insert(int i, T t){
        //先把i索引处及其后面的元素依次向后移动一位
        for (int index=N; index>i; index--){
            eles[index] = eles[index-1];
        }
        //再将t元素添加到i索引处
        eles[i] = t;
        //元素个数+1
        N++;
    }*/
    public void insert(int i, T t){
        if (N == eles.length){ //扩容
            resize(2 * eles.length);
        }

        //先把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){
        //记录索引i处的元素
        T current = eles[i];
        //索引i处后面的元素依次向前移动一位
        for (int index=i; index<N-1; index++){
            eles[index] = eles[index+1];
        }
        //元素个数-1
        N--;
        //返回已删除元素
        return current;
    }*/
    public T remove(int i){
        //记录索引i处的元素
        T current = eles[i];
        //索引i处后面的元素依次向前移动一位
        for (int index=i; index<N-1; index++){
            eles[index] = eles[index+1];
        }
        //元素个数-1
        N--;

        if (N < eles.length/4){ //缩容
            resize(eles.length / 2);
        }

        //返回已删除元素
        return current;
    }

    //查照线性表中t元素第一次出现的位置
    public int indexOf(T t){
        for (int i=0; i<N; i++){
            if (eles[i].equals(t)){
                return i;
            }
        }
        return -1; //线性表当前不存在t元素
    }

    //根据参数newSize，重置eles的大小
    public void resize(int newSize){
        //定义一个临时数组，指向原数组
        T[] temp=eles;
        //创建新数组
        eles=(T[])new Object[newSize];
        //把原数组的数据拷贝到新数组
        for(int i=0;i<N;i++){
            eles[i]=temp[i];
        }
    }


    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }
    private class SIterator implements Iterator{//内部类
        private int cusor;
        public SIterator(){
            this.cusor = 0;
        }
        @Override
        public boolean hasNext() {
            return cusor<N;
        }
        @Override
        public Object next() {
            return eles[cusor++];
        }
    }


}

View Code

package com.haifei.demo02linear.test;

import com.haifei.demo02linear.SequenceList;

public class Test02SequenceList {

    public static void main(String[] args) {
        /*SequenceList<String> sl = new SequenceList<>(3);
        sl.insert("张三");
        sl.insert("李四");
        sl.insert("王五");
//        sl.insert("赵六"); //java.lang.ArrayIndexOutOfBoundsException: 3*/


        //在SequenceList类中添加resize()以及对应插入删除配置后
        SequenceList<String> sl = new SequenceList<>(3);
        sl.insert("张三");
        sl.insert("李四");
        sl.insert("王五");
        sl.insert("赵六"); //ok
    }

}

View Code

 

1.4 顺序表的时间复杂度

 

 

1.5 Java中ArrayList实现

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2、链表

 

 

 

 

 

 

 

 

 

 

 

 

2.1 单向链表

2.2 双向链表

2.3 链表的时间复杂度

2.4 链表翻转

2.5 快慢指针

2.6 循环链表

2.7 约瑟夫问题

3、栈

3.1 栈概述

3.2 栈实现

3.3 栈案例

4、队列