菜单

线性表

duckflew
发布于 2020-10-20 / 195 阅读
0
0

线性表

线性表

public class SqList<T> {
    static int LIST_INIT_SIZE;
    static int LIST_INCREMENT_SIZE;
    private Object[] elements;
    private int length;     //当前有多少数据
    private int listSize;  //数组当前的大小

    static //静态代码块初始化
    {
        LIST_INIT_SIZE = 100;
        LIST_INCREMENT_SIZE = 10;
    }

    private void init() {
        elements = null;
        length = 0;
        elements = new Object[LIST_INIT_SIZE];
        listSize = 0;
    }

    public SqList() {
        init();
    }

    public boolean add(T t) {
        if (length >= listSize) {
            /**
             * 空间不足 扩大数组的容量
             */
            listSize += LIST_INCREMENT_SIZE;//更新容量信息
            Object[] newBase = new Object[listSize];
            for (int i = 0; i < length; i++) {
                newBase[i] = elements[i];
            }
            /**
             * 更新信息
             */
            newBase[length] = t;
            length++;
            elements = newBase;
        } else {
            elements[length++] = t;
        }
        System.out.println("添加一个数据");
        return true;
    }

    public T get(int index) {
        T wantToGet = null;
        try {
            wantToGet = (T) elements[index];
        } catch (ArrayIndexOutOfBoundsException e) {
            System.out.println("输入的位置不合法!");
        }
        return wantToGet;
    }

    public int size() {
        return length;
    }

    public boolean set(int index, T t) {
        T wantToGet = null;
        try {
            wantToGet = (T) elements[index];
        } catch (ArrayIndexOutOfBoundsException e) {
            System.out.println("输入的位置不合法!");
            return false;
        }
        this.elements[index] = t;
        return true;
    }

    public boolean insert(int index, T t) {
        try {
            T wantToGet = (T) elements[index];
        } catch (ArrayIndexOutOfBoundsException e) {
            System.out.println("输入的位置不合法!");
            return false;
        }
        Object[] tem = new Object[length + 1];// 用一个临时数组作为备份
        //开始备份数组
        for (int i = 0; i < length + 1; i++) {
            if (i < index) {
                tem[i] = this.elements[i];
            } else if (i == index) {
                tem[i] = t;
            } else if (i > index) {
                tem[i] = this.elements[i - 1];
            }
        }
        this.elements = tem;
        length++;
        return true;
    }

    public boolean remove(int index) {
        try
        {
            T wantToGet = (T) elements[index];
        } catch (ArrayIndexOutOfBoundsException e)
        {
            System.out.println("输入的位置不合法!");
            return false;
        }
        Object[] tem = new Object[length - 1];// 用一个临时数组作为备份
        //开始备份数组
        for (int i = 0; i < length - 1; i++)
        {
            if (i < index)
            {
                tem[i] = this.elements[i];
            }
            else
            {
                tem[i] = this.elements[i + 1];
            }
        }
        this.elements=tem;
        length--;
        return true;
    }
}

有序线性表的归并

public class ListMethods
{
    public static void mergeList(SequenceList<Integer> listA,SequenceList<Integer> listB,SequenceList<Integer>listC)
    {
        //线性表的归并  ,假设lista listb都是有序的   归并得到listC也是有序排列
         int laLength=listA.size();
         int lbLength=listB.size();
         int lcLength=listC.size();
         int i=0,j=0;
         while (i<laLength&&j<lbLength)
         {
             if(listA.get(i)<listB.get(j))
             {
                 listC.add(listA.get(i));
                         i++;
             }
             else
             {
                 listC.add(listB.get(j));
                 j++;
             }
         }
         while (i<laLength)listC.add(listA.get(i++));
         while (j<lbLength)listC.add(listB.get(j++));
    }
}


链表

public class LinkListPractice<E>
{
    private class Node
    {
        E data;
        Node next;

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

        @Override
        public String toString()
        {
            return data.toString();
        }
    }
    private Node head;
    private int size;

    public LinkListPractice()
    {
        head= new Node(null,null);
        size=0;
    }
    public int length(){return size;}
    public boolean isEmpty(){return size==0;}

    /**
     * 向指定位置添加元素
     * @param index
     * @param data
     */
    public void add(int index,E data)
    {
        if (index<0||index>size)throw new IllegalArgumentException("illegal index!");
        Node pre=head;
        for (int i=0;i<size;i++)
        {
            pre=pre.next;
        }
        pre.next=new Node(data,pre.next);
        size++;
    }
    public void addFirst(E data)
    {
        add(0,data);
    }
    public void addLast(E data)
    {
        add(size,data);
    }

    @Override
    public String toString()
    {
        StringBuilder builder=new StringBuilder();
        builder.append("length:"+length()+"\n");
        builder.append("head");
        Node cur=head.next;
        while (cur!=null)
        {
            builder.append("->"+cur.data);
            cur=cur.next;
        }
        builder.append("->null");
        return builder.toString();
    }

    /**
     * 获取指定位置的元素
     * @param index
     * @return
     */
    public E get(int index)
    {
        if (index<0||index>=size)throw new IllegalArgumentException("illegal index!");
        Node cur =head.next;
        for (int i=0;i<size;i++)
        {
            cur=cur.next;
        }
        return cur.data;
    }

    public E getFirst()
    {
        return get(0);
    }
    public E getLast()
    {
        return get(size-1);
    }

    /**
     * 删除指定位置的元素
     * @param index
     * @return
     */
    public E remove(int index)
    {
        if (index<0||index>=size)throw new IllegalArgumentException("illegal index!");
        Node pre =head;
        for (int i=0;i<index;i++)
        {
            pre=pre.next;
        }
        Node toDeleteNode=pre.next;
        pre.next=toDeleteNode.next;
        toDeleteNode.next=null;
        size--;
        return toDeleteNode.data;
    }

    /**
     * 删除第一个出现的data元素
     * @param data
     */
    public void removeData(E data)
    {
        Node pre =head;
        while (pre.next!=null)
        {
            if (pre.next.data.equals(data))
            {
                Node toDeleteNode = pre.next;
                pre.next = toDeleteNode.next;
                size--;
                toDeleteNode.next = null;
                break;
            }
            else
            {
                pre=pre.next;
            }
        }
    }
    public E removeFirst(){return remove(0);}
    public E removeLast(){return remove(size-1);}

    /**
     * 删除所有出现的data
     * @param data
     */
    public void removeAll(E data)
    {
        Node pre =head;
        while (pre.next!=null)
        {
            if (pre.next.data.equals(data))
            {
                Node toDeleteNode = pre.next;
                pre.next = toDeleteNode.next;
                size--;
                toDeleteNode.next = null;
            }
            else
            {
                pre=pre.next;
            }
        }
    }
    public boolean contains(E data)
    {
        Node cur =head.next;
        while (cur.next!=null)
        {
            if (cur.next.data.equals(data))
                return true;
                cur=cur.next;
        }
        return false;
    }
}


评论