天天看點
傳回

java資料結構連結清單，堆棧，隊列相關專題分析與扯談-連結清單

這一篇開始我就講java資料結構連結清單相關，在這上兩個連結清單相關的demo（線性表(順序結構)和連結清單(離散結構)）

線性表

主要包括兩個方面：既資料集和該資料集上的操作集合（功能接口）。

一、實作操作功能類

操作集合包括如下：

1.求元素個數

2.插入

3.删除

4.查找

5.判斷是否為空

綜上所述寫個功能接口List_,該功能接口在鍊式表那裡還要用到

public interface List_ {

    int size();

    boolean isEmpty();

    void insert(int index,Object object)throws Exception;

    void delete(int index)throws Exception;

    Object get(int index)throws Exception;

}

接着實作線性表邏輯,功能邏輯類SequenceList_ 和 測試類Test

為了友善我在code裡面添加注釋,我就不在文章添加太多文字了

/**
 * 順序表
 * 
 * @author robert
 *
 */
public class SequenceList_ implements List_ {

    private static final int DEFAULT_SIZE = ;//表預設長度
    public int mSize;//目前長度
    private int mMaxSize;//最大長度
    private Object[] mArraylists;//數組

    public SequenceList_() {
        init(DEFAULT_SIZE);//new 該對象的時候不指派,預設長度
    }

    public SequenceList_(int size) {
        init(size);//new 該對象的時候手動指派長度
    }

    //初始化順序表(數組)
    public void init(int size) {
        this.mMaxSize = size;
        this.mSize = ;
        mArraylists = new Object[size];
    }

    @Override
    public int size() {
        return mSize;//傳回長度
    }

    @Override
    public boolean isEmpty() {
        return mSize == ;//判斷是否為空
    }

    @Override
    public void insert(int index, Object object) throws Exception {
        if (index <  || index > mSize) {
            throw new Exception("越界");
        }
        if (mSize == mMaxSize) {
            throw new Exception("順序表已滿");
        }
        //反向周遊至插入位置,元素全部前移
        for (int i = mSize; i > index; i--) {
            mArraylists[i] = mArraylists[i + ];
        }
        mArraylists[index] = object;
        mSize++;
    }

    @Override
    public void delete(int index) throws Exception {
        if(isEmpty()){
            throw new Exception("順序表為空");//判斷是否為空
        }
        if(index<||index>mSize){
            throw new Exception("越界");
        }
        //正向周遊至删除元素指針處
        for (int i = index; i < mSize - ; i++) {
            mArraylists[index] = mArraylists[index - ];
        }
        mSize--;
    }

    //該處是擷取具體指針的指向位置的值
    @Override
    public Object get(int index) throws Exception {
        if (index <  || index > mSize - ) {
            throw new Exception("越界");
        }
        return mArraylists[index];
    }
}

最後是Test_

public class Test_list {
    public static void main(String[] args) {
        SequenceList_ list_ = new SequenceList_();
        try {
            list_.insert(list_.mSize, new Student("asd11", "tom11", "1231", "12233234456"));
            list_.insert(list_.mSize, new Student("asd12", "tom12", "1232", "12233234456"));
            list_.insert(list_.mSize, new Student("asd13", "tom13", "1233", "12233234456"));
            list_.insert(list_.mSize, new Student("asd14", "tom14", "1234", "12233234456"));
            list_.insert(list_.mSize, new Student("asd15", "tom14", "1234", "12233234456"));
            for (int i = ; i < list_.size(); i++) {
                System.out.println(list_.get(i));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

補上bean類，即上面提到的資料集

public class Student {

    private String nicename;
    private String username;
    private String password;
    private String telephone;

    public Student() {
        super();
        // TODO Auto-generated constructor stub
    }

    public Student(String nicename, String username, String password, String telephone) {
        super();
        this.nicename = nicename;
        this.username = username;
        this.password = password;
        this.telephone = telephone;
    }

    public String getNicename() {
        return nicename;
    }

    public void setNicename(String nicename) {
        this.nicename = nicename;
    }

    public String getUsername() {
        return username;
    }

    public void setUsername(String username) {
        this.username = username;
    }

    public String getPassword() {
        return password;
    }

    public void setPassword(String password) {
        this.password = password;
    }

    public String getTelephone() {
        return telephone;
    }

    public void setTelephone(String telephone) {
        this.telephone = telephone;
    }

    @Override
    public String toString() {
        return "Student [nicename=" + nicename + ", username=" + username + ", password=" + password + ", telephone="
                + telephone + "]";
    }

}

輸出結果:

java資料結構連結清單，堆棧，隊列相關專題分析與扯談-連結清單

連結清單

然後是離散類型的表,即連結清單

單連結清單是由一個一個結點組成的，是以，要設計單連結清單類，必須先設計結點類。結點類的成員變量有兩個：一個是資料元素，另一個是表示下一個結點的對象引用（即指針）。

設計操作：

1.頭結點的初始化

2.非頭結點的構造

3.擷取該結點指向的下個結點

4.設定該結點指向的下個結點

5.設定該結點的資料

6.擷取該結點的資料

這裡同樣使用上面定義的List_接口功能類，此處就不貼了

抽象資料類型結點類

/**
 * 節點類
 * 
 * @author robert
 *
 */
public class ListNode_ {

    public Object elenment;//資料域
    public ListNode_ next;//指針域

    public ListNode_(ListNode_ next) {
        super();
        this.next = next;
    }

    public ListNode_(Object elenment, ListNode_ next) {
        super();
        this.elenment = elenment;
        this.next = next;
    }

    public Object getElenment() {
        return elenment;
    }

    public void setElenment(Object elenment) {
        this.elenment = elenment;
    }

    public ListNode_ getNext() {
        return next;
    }

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

    @Override
    public String toString() {
        return "ListNode_ [elenment=" + elenment + ", next=" + next + "]";
    }

}

處理邏輯類的部分

public class LinkedList_ implements List_ {

    ListNode_ mConnert;//目前節點對象
    ListNode_ mHead;//頭結點對象
    public int mSize;

    public LinkedList_() {
        this.mConnert = this.mHead = new ListNode_(null);
        this.mSize = ;
    }

    //操作指針的方法
    private void index(int index) throws Exception {
        if (index < - || index > mSize - ) {
            throw new Exception("越界");
        }
        if (index == -) {
            return;
        }
        this.mConnert = mHead.next;
        int count = ;
        while (index>count&&mConnert != null) {
            this.mConnert = this.mConnert.next;
            count++;
        }
    }

    @Override
    public int size() {
        return mSize;
    }

    @Override
    public boolean isEmpty() {
        return mSize == ;
    }

    @Override
    public void insert(int index, Object object) throws Exception {
        if(index<||index>mSize){
            throw new Exception("越界");
        }
        index(index-);//操作指針
        mConnert.setNext(new ListNode_(object, mConnert.next));//添加資料
        mSize++;//長度增加
    }

    @Override
    public void delete(int index) throws Exception {
        // TODO Auto-generated method stub
        if(index<||index>mSize){
            throw new Exception("越界");
        }
        if(isEmpty()){
            throw new Exception("為空");
        }
        index(index-);
        mConnert.setNext(mConnert.next.next);
        mSize--;
    }

    @Override
    public Object get(int index) throws Exception {
        if (index < - || index > mSize - ) {
            throw new Exception("越界");
        }
        index(index);
        return mConnert.getElenment();
    }
}

測試類Test

public class Test_Link {
    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        LinkedList_ list = new LinkedList_();
        for (int i = ; i < ; i++) {
            int temp = ((int) (Math.random() * )) % ;
            list.insert(i, temp);
            System.out.print(temp + " ");
        }
        list.delete();
        System.out.println("\n------删除第五個元素之後-------");
        for (int i = ; i < list.mSize; i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

結果

java資料結構連結清單，堆棧，隊列相關專題分析與扯談-連結清單

單向循環清單

單向循環連結清單和單連結清單類各部分都相似，不同的是，最後一個結點的指針域不指向null，而是指向head頭結點，和上述一樣，99%的地方都不用改，隻需改動兩處即可

在功能邏輯類裡面改動構造方法和index方法

public LinkList_() {
        this.head = corrend = new ListNode_(null);
        this.size = ;
        this.head.next = head;//1
    }

    public void index(int index) throws Exception {
        if (index < - || index > size - ) {
            throw new Exception("參數錯誤");
        }
        if (index == -) {
            return;
        }
        corrend = this.head.next;
        int j = ;
        while (j < index && corrend != head) {//2，null改為head
            corrend = this.corrend.next;
            j++;
        }
    }

雙向循環連結清單

雙向連結清單是每個結點除後繼指針外還有一個前驅指針。

實作方式和單連結清單略有不同

接口功能類一樣使用List_

抽象資料類型結點類

public class DoubleNode_ {

    public Object elenment;
    public DoubleNode_ tail;
    public DoubleNode_ next;

    public DoubleNode_(DoubleNode_ next) {
        this.next = next;
    }

    public DoubleNode_(Object elenment, DoubleNode_ next) {
        this.elenment = elenment;
        this.next = next;
    }

    public Object getElenment() {
        return this.elenment;
    }
    public void setElenment(Object elenment) {
        this.elenment = elenment;
    }
    public DoubleNode_ getTail() {
        return this.tail;
    }
    public void setTail(DoubleNode_ tail) {
        this.tail = tail;
    }
    public DoubleNode_ getNext() {
        return this.next;
    }
    public void setNext(DoubleNode_ next) {
        this.next = next;
    }
}

功能邏輯實作

/**
 * 雙向循環連結清單
 * 
 * @author robert
 *
 */
public class CycleLinkList_ implements List_ {

    DoubleNode_ head;
    DoubleNode_ corrend;
    public int size;

    public CycleLinkList_() {
        this.head = corrend = new DoubleNode_(null);
        this.size = ;
        this.head.next = head;
        this.head.tail = head;
    }

    public void index(int index) throws Exception {
        if (index < - || index > size - ) {
            throw new Exception("參數錯誤");
        }
        if (index == -) {
            return;
        }
        corrend = this.head.next;
        int j = ;
        while (j < index && corrend != head) {
            corrend = this.corrend.next;
            j++;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == ;
    }

    @Override
    public Object get(int index) throws Exception {
        if (index < - || index > size - ) {
            throw new Exception("參數錯誤");
        }
        index(index);
        return corrend.getElenment();
    }

    @Override
    public void insert(int index, Object object) throws Exception {
        if(index<||index>size){
            throw new Exception("參數錯誤");
        }
        index(index-);
        corrend.setNext(new DoubleNode_(object, corrend.next));
        corrend.next.setTail(corrend);
        corrend.next.next.setTail(corrend.next);
        size++;
    }

    @Override
    public void delete(int index) throws Exception {
        if(index<||index>size){
            throw new Exception("參數錯誤");
        }
        if(isEmpty()){
            throw new Exception("連結清單為空");
        }
        index(index-);
        corrend.setNext(corrend.next.next);
        corrend.setTail(corrend);
        size--;
    }
}

測試類Test

public class Test_Double {
    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        CycleLinkList_ list = new CycleLinkList_();
        for (int i = ; i < ; i++) {
            int temp = ((int) (Math.random() * )) % ;
            list.insert(i, temp);
            System.out.print(temp + " ");
        }
        list.delete();
        System.out.println("\n------删除第三個元素之後-------");
        for (int i = ; i < list.size; i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

結果：

java資料結構連結清單，堆棧，隊列相關專題分析與扯談-連結清單

下篇開始講java資料結構堆棧相關

Java資料結構 java 資料結構 連結清單 棧 線性表
上一篇: java資料結構連結清單，堆棧，隊列等相關專題分析與扯談-隊列
下一篇: java資料結構連結清單，堆棧，隊列，串相關專題分析與扯談-概述

繼續閱讀