Java数据结构与基本算法之线性表

1 数组

1.1 基本类型数组

例如:向一维数组做,插入,更新,替换,删除操作时:


// 声明一个数组
int[] scores = {1, 2, 3, 4, 5, 6};

// 1. 在数据尾部位置插入一个数字
scores = add(scores, 7);
public static int[] add(int[] array, int score) {
        int[] tempArray = new int[array.length + 1];
        for (int i = 0; i < array.length; i++) {
            tempArray[i] = array[i];
        }
        tempArray[array.length] = score;
        return tempArray;
    }
    
// 2. 向一维数组任意位置(指定位置)修改一个数据,真实位置=要求位置-1
scores = update(scores, 7, 2);
public static int[] update(int[] arrary, int score, int index) {
        arrary[index] = score;
        return arrary;
}

// 3. 替换一个数字到指定位置
scores = insert(scores, 7, 2);//将75插入到索引为2的位置
public static int[] insert(int[] array, int score, int index) {
        int[] tempArray = new int[array.length + 1];
        for (int i = 0; i < array.length; i++) {
            if (i < index) {
                tempArray[i] = array[i];
            } else {
                tempArray[i + 1] = array[i];
            }
        }
        tempArray[index] = score;
        return tempArray;
    }

// 4. 删除指定位置的数字
scores = delete(scores, 3);
public static int[] delete(int[] array, int index) {
        int[] tempArray = new int[array.length - 1];
        for (int i = 0; i < array.length; i++) {
            if (i <= index) {
                tempArray[i] = array[i];
            } else {
                tempArray[i - 1] = array[i];
            }
        }
        return tempArray;
    }

1.2 封装类型ArrayList数组

    //声明初始接口方法
    public interface List {
        public void add(Object element);//添加元素
        public Object get(int index);//获得元素
        public Object set(int index,Object element);//修改元素
        public Object remove(int index);//删除元素
        public int size();//集合大小
    }
    //实现声明接口的数组
    public class ArrayList implements List {
        private int initCapacit = 20;//初始数组大小
        private int size;//元素个数
        private Object[] elementData;//数据数组对象
    
        public ArrayList() {
            elementData = new Object[initCapacit];
        }
    
        public ArrayList(int initCapacit) {
            elementData = new Object[initCapacit];
            this.initCapacit = initCapacit;
        }
    
        //添加元素
        @Override
        public void add(Object element) {
            if (size < initCapacit) {
                elementData[size] = element;
                size++;
            } else {
                elementData = expandArray(elementData);
                elementData[size] = element;
                size++;
            }
        }
    
        //扩充List对象数组大小
        public Object[] expandArray(Object[] elementData) {
            Object[] tempArray = new Object[elementData.length * 2];//每次扩充为原来的2倍大小
            for (int i = 0; i < elementData.length; i++) {
                tempArray[i] = elementData[i];
            }
            return tempArray;
        }
    
        //获得元素
        @Override
        public Object get(int index) {
            return elementData[index];
        }
    
        //集合大小
        @Override
        public int size() {
            return size;
        }
    
        //删除元素
        @Override
        public Object remove(int index) {
            Object removeObj = elementData[index];
            //删除元素后面的元素前移
            for (int i = index; i < size; i++) {
                elementData[i] = elementData[i + 1];
            }
            size--;
            return removeObj;
        }
        
        //修改元素
        @Override
        public Object set(int index, Object element) {
            elementData[index] = element;
            return element;
        }
    

        Node p=head;
        int i=0;
        while (p.getNext()!=null && i<index){
            p=p.getNext();
            i++;
        }
        p.setData(element);
        return element;
    }

    @Override
    public Object remove(int index) {
        Node p=head;
        int i=0;
        while (p.getNext()!=null && i<index){
            p=p.getNext();
            i++;
        }
        Node temp=p;//保存要删除的节点
        p.getPrev().setNext(p.getNext());
        p.getNext().setPrev(p.getPrev());
        temp.setNext(null);
        temp.setPrev(null);
        size--;
        return temp.getData();
    }
}


2 链表

2.1 单链表

//单链表的结构,Node的自引用,next代表指针变量指向下一个节点
public class Node {
    private String data;//节点数据
    private Node next;//下一个节点

    public Node(String data, Node next) {
        this.data = data;
        this.next = next;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

2.2 单循环链表

 // 核心在于打印两次,头开始到尾,再从尾到头循环打印
 public static void print(Node node) {
        Node p = node;
        Node startNode = node;
        int circleCount = 0;//循环打印次数
        while (circleCount < 2) {
            //从头开始到尾,再从尾到头循环打印
            String data = p.getData();
            System.out.print(data + "→");
            p = p.getNext();
            if (p.getNext() == startNode) {
                circleCount++;
            }
        }
        String data = p.getData();
        System.out.print(data + "\n\n");
    }

2.3 双链表

// 双链表,prev和next两个指针变量  prev-data-next
class Node {
    private String data;//结点数据
    private Node prev;//上一个结点
    private Node next;//下一个结点

    public Node(String data, Node prev, Node next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node getPrev() {
        return prev;
    }

    public void setPrev(Node prev) {
        this.prev = prev;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

2.4 双向循环链表

       nt circleCount = 0;//循环打印次数
        while (circleCount < 2) {
            //从头开始直到尾结束,再从尾到头循环打印
            String data = p.getData();
            System.out.print(data + "->");
            p = p.getNext();
            if (p.getNext()==startNode){
                circleCount++;
            }
        }

评论

暂无评论