<small id="7ktuj"></small>
      <bdo id="7ktuj"></bdo>
        <mark id="7ktuj"></mark>

        <source id="7ktuj"></source>
        <small id="7ktuj"></small>

        ITPub博客

        首頁 > 應用開發 > Java > Java實現數據結構之線性結構

        Java實現數據結構之線性結構

        原創 Java 作者:蝴蝶飛啊飛 時間:2019-10-17 12:51:37 0 刪除 編輯

        一、順序表

        順序表本質是使用數組儲存數組的一種數據結構,在計算機的儲存中是連續的分配內存的。

        下面是我自己使用java 實現的簡單順序表結構

        package list;

        public class MyArrayList<E> {

            private Object[] data; // 數據

            private int length; // 目前長度

            private int size;  // 容量

            // 空構造器 默認容量 10

            public MyArrayList(){

                this(10);

            }

            /**

             * 初始化表自定義容量

             * @param size

             */

            public MyArrayList(int size){

                if(size<0){

                    throw new RuntimeException(" 定義表容量錯誤 :"+size);

                }else {

                    this.data = new Object[size];

                    this.size = size;

                    this.length = 0;

                }

            }

            /**

             * 判斷容量是否足夠,若不夠則擴充 10

             */

            public void SizeIsEnough(){

                if(this.length>=this.size){

                    Object[] newData = new Object[this.size+10];

                    this.size = size+10;

                }

            }

            /**

             * 向表末尾插入一個元素

             * @param e 插入的元素

             */

            public void add(E e){

                data[length++] = e;

            }

            /**

             *   向表的指定位置插入一個元素

             * @param e 插入元素的值

             * @param index 插入的位置

             */

            public void add(E e,int index){

                SizeIsEnough();

                if(index<0|| index>=length+1){

                    throw  new RuntimeException(" 插入元素位置錯誤 "+index);

                }

                for(int i=length++; i>=index; i--){

                    data[i] = data[i-1];

                }

                data[index] = e;

            }

            /**

             * 移除指定位置的元素

             * @param index 移除元素的位置

             */

            public E remove(int index){

                if(index<0||index>=length){

                    throw  new RuntimeException(" 刪除元素位置錯誤 "+index);

                }

                E e = Get(index);

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

                    data[i] = data[i+1];

                }

                return e;

            }

            /**

             *   移除最后一個元素

             * @return 返回被移除的元素

             */

            public E remove(){

                return remove(length-1);

            }

            /**

             *   獲取指定位置的元素

             * @param index 獲取元素的位置

             * @return 獲取的元素的值

             */

            public E Get(int index){

                if(index<0||index>=length){

                    throw  new RuntimeException(" 查找元素位置錯誤 "+index);

                }

                E e = (E) data[index];

                return e;

            }

            /**

             * 獲取指定值的元素的位置

             * @param e

             * @return

             */

            public int Get(E e){

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

                    if (data[i].equals(e)) {

                        return i;

                    }

                }

                return -1;

            }

            public int Length() {

                return length;

            }

            public static void main(String[] args) {

                MyArrayList<String> list = new MyArrayList<>();

                list.add("ming");

                list.add("king");

                list.add("ling");

                for(int i=0;i<list.Length();i++){

                    System.out.println(list.Get(i));

                }

                list.remove(2);

                list.add("ling",2);

                for(int i=0;i<list.Length();i++){

                    System.out.println(list.Get(i));

                }

            }

        }

        二、鏈表

        鏈表是本質上使用指針儲存下一個元素的地址,從而可以在外匯返傭http://www.fx61.com/內存中找到下一個元素,形成一個鏈式的結構。java 中沒有指針的概念,當時 java 面向對象的本質就是指針,所以可以使用類作為指針的替代。

        以下是我自己實現的簡單的單鏈表

        package list;

        public class MyLinkList<E> {

            private Node<E> head=null;

            private int size=0;

            /**

             * 添加元素

             */

            public void  add(E e){

                Node<E> node = new Node<>();

                node.setData(e);

                if(head == null){

                    head = node;

                    size++;

                    return;

                }

                assert false;

                Node<E> tmp = head;

                while (tmp.hasNext()){

                    tmp = tmp.getNext();

                }

                tmp.setNext(node);

                size++;

            }

            /**

             * 刪除指定位置的元素

             * @param index

             * @return

             */

            public E remove(int index){

                Node<E> tmp = head;

                Node<E> preNode;

                Node<E> currNode;

                int count=0;

                if(index < 0 || index >size-1){

                    throw  new RuntimeException(" 刪除位置錯誤 "+index);

                }

                while (tmp.hasNext()&&count != index-1){

                    tmp = tmp.getNext();

                    count++;

                }

                preNode = tmp;

                currNode = tmp.getNext();

                assert currNode != null;

                preNode.setNext(currNode.getNext());

                size--;

                return currNode.getData();

            }

            public int Size(){

                return size;

            }

            /**

             * 移除鏈表尾部元素

             * @return

             */

            public E remove(){

                return remove(size-1);

            }

            /**

             * 獲取指定位置的元素

             * @param index

             * @return

             */

            public E get(int index){

                Node<E> tmp = head;

                int count=0;

                if(index < 0 || index > size-1){

                    throw  new RuntimeException(" 查找位置錯誤 "+index);

                }

                while (tmp.hasNext() && count != index){

                    tmp = tmp.getNext();

                    count++;

                }

                return tmp.getData();

            }

            public static void main(String[] args) {

                MyLinkList<String> linked = new MyLinkList<>();

                linked.add("ming");

                linked.add("ling");

                linked.add("ping");

                linked.add("king");

                for (int i = 0; i < linked.size; i++) {

                    System.out.println(linked.get(i));

                }

                String s = linked.remove();

                for (int i = 0; i < linked.size; i++) {

                    System.out.println(linked.get(i));

                }

                System.out.println(s);

            }

        }

        class Node<E> {

            private E data;

            private Node<E> next = null;

            public E getData() {

                return data;

            }

            public void setData(E data) {

                this.data = data;

            }

            public Node<E> getNext() {

                return next;

            }

            public void setNext(Node<E> next) {

                this.next = next;

            }

            public boolean hasNext(){

                return next != null;

            }

        }

        實現線性表有兩種方式。第一種是使用數組存儲線性表的元素。數組是動態創建的。超過數組的容量時,創建一個新的更大的數組,并且將當前數組中的元素復制到新建的數組中。另一種方法是用鏈表結構實現。鏈表由節點組成,每個結點都是動態生成的,用來存儲一個元素。所有的結點連接成一個線性表。

        本文講述使用變長數組實現線性表

        實現代碼

        package com.billJiang.array;

        import java.util.Arrays;

        import java.util.Collection;

        /**

         * Created by billJiang on 2016/11/30.

         * 變長數組

         */

        public class ArrayList<T> {

            private static final int INITIAL_SIZE = 10;

            private int size = 0;

            private T[] array;

            public ArrayList(int initial) {

                if (initial <= 0)

                    initial = INITIAL_SIZE;

                array = (T[]) new Object[initial];

            }

            public void add(T item) {

                // 數組擴容

                if (size == array.length) {

                    array = Arrays.copyOf(array, size * 2);

                }

                array[size++] = item;

            }

            public T get(int index) {

                if (index >= size || index < 0) {

                    throw new IndexOutOfBoundsException(" 獲取的元素超出了數組的界限 ");

                }

                return array[index];

            }

            public T set(int index, T item) {

                T oldItem = this.get(index);

                array[index] = item;

                return oldItem;

            }

            public int size() {

                return this.size;

            }

        }

        測試代碼

        package com.billJiang.array;

        /**

         * Created by billJiang on 2016/11/30.

         */

        public class ArrayListTest {

            public static void main(String[] args) {

                ArrayList<Integer> arrayList=new ArrayList<Integer>(3);

                arrayList.add(new Integer(1));

                arrayList.add(new Integer(2));

                arrayList.add(new Integer(3));

                System.out.println(arrayList.size());

                arrayList.add(new Integer(4));

                arrayList.set(3,5);

                System.out.println(arrayList.size());

            }

        }


        來自 “ ITPUB博客 ” ,鏈接:http://www.ep4tq.com/69946279/viewspace-2660341/,如需轉載,請注明出處,否則將追究法律責任。

        請登錄后發表評論 登錄
        全部評論
        管他誰是誰非,做自己的主宰,我是這條街最亮的崽!

        注冊時間:2019-08-22

        • 博文量
          49
        • 訪問量
          21835
        妹子图每日分享