數(shù)據(jù)結(jié)構(gòu)-線性表

@(數(shù)據(jù)結(jié)構(gòu))

線性表是數(shù)據(jù)結(jié)構(gòu)中的邏輯結(jié)構(gòu)?？梢源鎯υ跀?shù)組上，也可以存儲在鏈表上。

順序表（數(shù)組）

簡述

用數(shù)組來存儲的線性表就是順序表。

優(yōu)點(diǎn)

• 查找速度快，因為本身是數(shù)組的查找

缺點(diǎn)

• 插入和刪除都會伴隨著大量的元素操作和移動

Java代碼造輪子

• 基本方法架構(gòu)如圖:
• 這里我們實現(xiàn)的是大小固定的，當(dāng)然我們也可以去詳細(xì)寫一個大小根據(jù)插入而拓展的就像我們常使用的ArrayList一樣。

線性表 順序表（數(shù)組）
 * 
 * MyList(int size) 構(gòu)造函數(shù)指定大小 
 * void destory() 銷毀順序表對象 
 * void clear() 清空順序表內(nèi)元素
 * boolean isEmpty() 判空 
 * boolean isFull() 判滿 
 * int getLength() 獲取當(dāng)前順序表長度 
 * T get(intposition) 根據(jù)位置獲取順序表內(nèi)元素對象 
 * int getPosition(T t) 根據(jù) 元素對象獲取順序表位置 
 * T prior(T t)獲取對象前驅(qū) 
 * T next(T t) 獲取對象后繼
 * 
 * boolean insert(T t) / insert(int position, T t) 
 * 向順序表插入對象，不傳位置就默認(rèn)在最后插入，這里!不是!內(nèi)部調(diào)用insert(int position, T t)
 * 
 * boolean delete(T t) / delete(int position) 
 * 根據(jù)對象或者位置刪除順序表 內(nèi)元素
 * 
 * void traverse(int position) 
 * 遍歷順序表 
 * 
 * abstract void onTraverse()
 * 遍歷順序表得到對象的具體操作
 * @author Rayhahah
 *
 * @param <T> 當(dāng)前順序表中的元素對象類型

• 代碼實現(xiàn)部分

public abstract class MyList<T> {
    private int mCapacity;
    private Object[] mList;
    private int mLength;

    /**
     * 構(gòu)造函數(shù)
     * 
     * @param size
     *            指定順序表容量
     */
    public MyList(int size) {
        mCapacity = size;
        mList = new Object[mCapacity];
    }

    /**
     * 摧毀當(dāng)前順序表
     */
    public void destory() {
        clear();
        mCapacity = 0;
        mList = null;
        System.gc();
    }

    /**
     * 清空順序表 只需要將長度置為0就可以了
     *  因為獲取表中內(nèi)容的時候，都需要和length做判斷
     */
    public void clear() {
        mLength = 0;
    }

    /**
     * 判斷當(dāng)前順序表是否為空
     * 
     * @return 空：true， 非空：false
     */
    public boolean isEmpty() {
        return mLength == 0;
    }

    /**
     * 判斷當(dāng)前順序表是否為滿
     * 
     * @return 滿：true， 未滿：false
     */
    public boolean isFull() {
        return mLength == mCapacity;
    }

    /**
     * 獲取當(dāng)前 順序表的長度 注意不是容量
     * 
     * @return
     */
    public int getLength() {
        return mLength;
    }

    /**
     * 根據(jù)坐標(biāo)獲取順序表的元素
     * 
     * @param position
     *            坐標(biāo)
     * @return 順序表元素
     */
    public T get(int position) {
        // 不滿足都返回null
        if (position < 0 || position >= mLength || mList == null) {
            return null;
        }

        return (T) mList[position];
    }

    /**
     * 根據(jù)傳入元素返回元素在順序表中的坐標(biāo) 
     * 判斷依據(jù)是 元素的地址
     * 
     * @param t
     * @return 元素所在坐標(biāo)
     */
    public int getPosition(T t) {
        if (isEmpty()) {
            return -1;
        }

        for (int i = 0; i < mLength; i++) {
            if (t == mList[i]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 獲取傳入元素的前驅(qū) 判斷依據(jù)元素的地址
     * 
     * @param t
     * @return
     */
    public T prior(T t) {
        if (isEmpty()) {
            return null;
        }
        for (int i = 1; i < mLength; i++) {
            if (t == mList[i]) {
                return (T) mList[i - 1];
            }
        }
        return null;
    }

    /**
     * 獲取傳入元素的后繼 判斷依據(jù) 元素的地址
     * 
     * @param t
     * @return
     */
    public T next(T t) {
        if (isEmpty()) {
            return null;
        }
        for (int i = 0; i < mLength; i++) {
            if (t == mList[i]) {
                return (T) mList[i + 1];
            }
        }
        return null;
    }

    /**
     * 插入元素，不指定位置默認(rèn)插入在順序表的最后 
     * 如果順序表已經(jīng)滿了，就返回false 插入成功返回true
     * 
     * @param t
     * @return
     */
    public boolean insert(T t) {
        if (isFull()) {
            return false;
        }
        mList[mLength] = t;
        mLength++;
        return true;
    }

    /**
     * 向指定位置插入元素，其他元素向后退一位
     * 
     * @param position
     * @param t
     * @return
     */
    public boolean insert(int position, T t) {
        T tar = t;
        T temp = null;
        // 滿了以后長度不再變化
        if (!isFull()) {
            mLength++;
        }
        for (int i = position; i < mLength; i++) {
            if (temp != null) {
                tar = temp;
            }
            temp = (T) mList[i];
            mList[i] = tar;
        }
        return true;
    }

    /**
     * 刪除順序表中的指定元素
     * 
     * @param t
     * @return
     */
    public boolean delete(T t) {
        if (isEmpty()) {
            return false;
        }
        T temp = null;
        boolean flag = false;
        for (int i = 0; i < mLength; i++) {
            //找到刪除元素以后就開始將后面元素前移
            if (t == mList[i]) {
                mLength--;
                if (i == mLength) {
                    return true;
                }
                flag = true;
            }
            if (i != mLength) {
                temp = (T) mList[i + 1];
            }
            if (flag) {
                mList[i] = temp;
                if (i == mLength) {
                    return true;
                }

            }
        }
        return false;
    }

    /**
     * 刪除順序表中的指定位置的元素
     * 
     * @param position
     * @return
     */
    public boolean delete(int position) {
        if (isEmpty() || position >= mLength || position < 0) {
            return false;
        }
        for (int i = position; i < mLength; i++) {
            System.out.println(i);
            if (i + 1 >= mLength) {
                mLength--;
                return true;
            }
            mList[i] = mList[i + 1];
            System.out.println(mList[i]);
        }
        return true;
    }

    /**
     * 默認(rèn)遍歷為遍歷整個順序表
     */
    public void traverse() {
        traverse(0);
    }

    /**
     * 指定開始遍歷的位置
     * 
     * @param position
     */
    public void traverse(int position) {
        for (int i = position; i < mLength; i++) {
            onTraverse((T) mList[i]);
        }
    }

    /**
     * 遍歷得到元素所需要的具體操作
     *  交回給用戶自己確定
     * 
     * @param t
     */
    public abstract void onTraverse(T t);

}

鏈表

單鏈表

• 單向性：鏈表中的節(jié)點(diǎn)只會指向另一個節(jié)點(diǎn)，最后的節(jié)點(diǎn)指向null

單鏈表.png

循環(huán)鏈表

• 形成回路：與單鏈表最大的區(qū)別就是尾節(jié)點(diǎn)指向頭結(jié)點(diǎn)

循環(huán)鏈表.png

雙向鏈表

• 每個節(jié)點(diǎn)都會指向它的"前節(jié)點(diǎn)"和"后節(jié)點(diǎn)"
• 頭結(jié)點(diǎn)的"前節(jié)點(diǎn)"指向為null，尾節(jié)點(diǎn)的"后節(jié)點(diǎn)"指向為null

雙向鏈表.png

靜態(tài)鏈表

• 對于沒有指針的語言，就要使用靜態(tài)鏈表
• 使用數(shù)組，每個節(jié)點(diǎn)的指向就是保存它指向節(jié)點(diǎn)的數(shù)組中的坐標(biāo)

靜態(tài)鏈表.png

代碼造輪子

• 在這里我只做了單鏈表的代碼實現(xiàn)，其他的鏈表其實也是觸類旁通
• 這里的功能我只做了基本的方法，想要深入研究的朋友可以參考一下Java源碼的LinkedList相信一定可以有所收獲
• 基本結(jié)構(gòu)：

 * MyLinkedList() 構(gòu)造函數(shù)
 * void clearList() 清空鏈表數(shù)據(jù)
 * 
 * boolean isEmpty() 鏈表判空
 * int getLength() 鏈表的當(dāng)前長度
 * 
 * T get(int position) 根據(jù)坐標(biāo)獲取鏈表中的元素
 * int getPosition(T t) 根據(jù)數(shù)據(jù)對象獲取在鏈表中的位置坐標(biāo)
 * 
 * boolean insert(T t) / insert(int position,T t) 
 * 向鏈表末尾插入數(shù)據(jù)對象 / 向指定位置插入數(shù)據(jù)對象
 * 
 * boolean delete(T t) / delete (int position) 
 * 刪除在鏈表中的傳入數(shù)據(jù)對象 / 刪除指定位置的節(jié)點(diǎn)
 * 
 * void traverse(int position) 
 * 啟動遍歷鏈表
 * abstract void onTraverse() 
 * 遍歷順序表得到對象的具體操作
 * 
 * @author Rayhahah
 *
 * @param <T>
 *            鏈表儲存的數(shù)據(jù)對象類型

• 具體代碼實現(xiàn)：

public abstract class MyLinkedList<T> {
    private MyNode<T> first;
    private int mLength;

    public MyLinkedList() {
        first = new MyNode<T>(null, null);
        mLength = 0;
    }

    /**
     * 判空
     * 
     * @return
     */
    public boolean isEmpty() {
        return mLength == 0;
    }

    /**
     * 清空鏈表
     */
    public void clear() {
        for (MyNode<T> temp = first; temp != null;) {
            MyNode<T> next = temp.next;
            temp.next = null;
            temp.t = null;
            temp = next;
        }
        mLength = 0;
    }

    /**
     * 節(jié)點(diǎn)是否為空
     * 
     * @param myNode
     * @return
     */
    private boolean isNodeNull(MyNode<T> myNode) {
        if (myNode.next == null && myNode.t == null) {
            return true;
        }
        return false;
    }

    /**
     * 向鏈表最后插入節(jié)點(diǎn)
     * 
     * @param t
     * @return
     */
    public boolean insert(T t) {
        return insert(mLength, t);
    }

    /**
     * 向指定位置插入及節(jié)點(diǎn)
     * 
     * @param position
     * @param t
     * @return
     */
    public boolean insert(int position, T t) {
        if (position < 0 || position > mLength) {
            return false;
        }
        mLength++;
        MyNode<T> currentNode = first;
        MyNode<T> currentNodeBefore = null;
        //插入位置是頭節(jié)點(diǎn)的情況
        if (position == 0) {
            MyNode<T> newNode = new MyNode<T>(t, first);
            first = newNode;
            return true;
        }
        for (int i = 0; i < position; i++) {
            currentNodeBefore = currentNode;
            currentNode = currentNode.next;
        }
        //指向后節(jié)點(diǎn)
        MyNode<T> newNode = new MyNode<>(t, currentNode);
        //前節(jié)點(diǎn)指向新節(jié)點(diǎn)就等于插入
        currentNodeBefore.next = newNode;
        return true;
    }

    /**
     * 根據(jù)坐標(biāo)刪除節(jié)點(diǎn)
     * 
     * @param position
     * @return
     */
    public boolean delete(int position) {
        if (position < 0 || position >= mLength) {
            return false;
        }
        mLength--;
        if (position == 0) {
            return deleteFirst(first.next);
        }
        MyNode<T> currentNode = first;
        MyNode<T> currentNodeBefore = null;
        for (int i = 0; i < position; i++) {
            currentNodeBefore = currentNode;
            currentNode = currentNode.next;
        }
        //將要刪除的節(jié)點(diǎn)的前節(jié)點(diǎn)指向  要刪除的節(jié)點(diǎn)的后節(jié)點(diǎn)
        //失去了聯(lián)系節(jié)點(diǎn)就等于被刪除了
        currentNodeBefore.next = currentNode.next;
        return true;
    }

    /**
     * 清楚頭節(jié)點(diǎn)數(shù)據(jù)
     * 
     * @param node
     * @return
     */
    private boolean deleteFirst(MyNode<T> node) {
        first = node;
        return true;
    }

    /**
     * 刪除包含有該數(shù)據(jù)對象的節(jié)點(diǎn)數(shù)據(jù)
     * 
     * @param t
     * @return
     */
    public boolean delete(T t) {
        if (isEmpty()) {
            return false;
        }

        mLength--;
        // 現(xiàn)在節(jié)點(diǎn)
        MyNode<T> currentNode = first;
        // 前節(jié)點(diǎn)
        MyNode<T> currentNodeBefore = null;
        while (currentNode.t != null) {
            if (currentNode.t == t) {
                // 頭節(jié)點(diǎn)
                if (currentNodeBefore == null) {
                    first = currentNode.next;
                } else {
                    currentNodeBefore.next = currentNode.next;
                }
                return false;
            }
            currentNodeBefore = currentNode;
            currentNode = currentNode.next;
        }
        return false;
    }

    /**
     * 根據(jù)坐標(biāo)返回數(shù)據(jù)對象
     * 
     * @param position
     *            坐標(biāo)
     * @return 數(shù)據(jù)對象
     */
    public T get(int position) {
        if (position < 0 || position >= mLength) {
            return null;
        }
        MyNode<T> currentNode = first;
        // 移動至position就可以找到需要的數(shù)據(jù)對象了
        for (int i = 0; i < position; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.t;
    }

    /**
     * 根據(jù)傳入元素獲取在鏈表中的坐標(biāo)
     * 
     * @param t
     *            需要查找坐標(biāo)的對象
     * @return 坐標(biāo)
     */
    public int getPosition(T t) {
        if (isEmpty()) {
            return -1;
        }
        int count = 0;// 獲取當(dāng)前查找到的坐標(biāo)
        MyNode<T> currentNode = first;
        while (currentNode != null) {
            // 找到元素就返回
            if (currentNode.t == t) {
                return count;
            }
            count++;
            currentNode = currentNode.next;
        }
        return -1;
    }

    /**
     * 遍歷整個鏈表
     */
    public void traverse() {
        MyNode<T> currentNode = first;
        while (currentNode.t != null) {
            onTraverse(currentNode.t);
            currentNode = currentNode.next;
        }
    }

    /**
     * 遍歷時對每個元素具體的操作
     * 
     * @param t
     */
    public abstract void onTraverse(T t);

}

最后

線性表是平常我們會用到非常多的一個數(shù)據(jù)結(jié)構(gòu)，雖然自己造輪子并沒有什么卵用
不過對于我們思維聯(lián)想的提升，我相信還是有點(diǎn)幫助的
附上 數(shù)據(jù)結(jié)構(gòu)項目的GitHub:
https://github.com/Rayhahah/DataStructure