線性表

線性表

1.線性表抽象數(shù)據(jù)類型

線性表是其組成元素間具有線性關系的一種線性結構，對線性表的基本操作主要有獲取元素值、遍歷、插入、刪除、查找、替代和排序等，插入和刪除可以在線性表的任意位置進行。線性表可以采用順序存儲和鏈式存儲結構表示。

線性表的特點：
1.有且僅有1個開始結點，沒有直接前驅，有1個直接后繼；
2.有且僅有1個結束結點，沒有直接后繼，有1個直接前驅；
3.其它結點均有1個直接前驅和1個直接后繼。

線性表(linear list) 是由 n(n>=0) 個類型相同的元素組成的有限序列。
(其實這個接口就是List，為什么重寫一遍呢而不是直接貼上jdk源碼？是我在參加阿里的面試時，阿里的面試官問我：有沒有自己去重寫jdk的一些源碼？重寫這些源碼去學習這些底層的實現(xiàn)方式)

創(chuàng)建一個線性表接口LList.java,信息如下：

public interface LList<T> {
    /**空判斷方法*/
    boolean isEmpty();
    /**線性表長度*/
    int size();
    /**返回第i個元素*/
    T get(int index);
    /**設置第i個元素為t*/
    void set(int index,T t);
    /**插入t作為第i個元素*/
    void insert(int index,T t);
    /**在線性表最后插入t*/
    void add(T t);
    /**刪除第i個元素*/
    T remove(int i);
    /**刪除全部元素*/
    void removeAll();
    /**查找*/
    T search(T key);
}

由于線性表可以采用順序存儲和鏈式存儲結構表示，在創(chuàng)建兩個實現(xiàn)類：

//順序存儲
public class SequenceList<T> implements LList<T>

//鏈式存儲結構
public class SinglyLinkedList<T> implements LList<T>

2.線性表的順序表示和實現(xiàn)

2.1 線性表的順序存儲結構

線性表的順序存儲是用一組連續(xù)的內存單元依次存放線性表的數(shù)據(jù)元素，元素在內存的物理存儲次序與它們在線性表中的邏輯相同，這種方式被稱為順序表(sequence list)。

線性表的數(shù)據(jù)元素a_i的存儲地址是它在線性表中位置i的線性函數(shù)。如圖所示：

線性表存儲結構.PNG

順序表通常采用數(shù)組存儲數(shù)據(jù)元素。將線性表的數(shù)據(jù)元素順序存放在數(shù)組中，數(shù)組元素在數(shù)組總的物理順序與線性表中元素的順序關系相同。
數(shù)組是順序存儲隨機存取結構，占用一組連續(xù)的存儲單元，通過下標(序號)識別元素，元素地址是下標的線性函數(shù)。一個下標能夠唯一確定一個元素，存取任何一個元素所花費的時間是O(1)。

2.2順序表

類SequenceList<T>實現(xiàn)了接口LList<T>

public class SequentialList<T> implements LList<T> {
    
    private Object[] element;
    private int len;
    
    public SequentialList(int size){
        //如果size<0,會拋出負數(shù)組長度異常
        this.element = new Object[size];
        this.len = 0;
    }

    /**
     * 創(chuàng)建容器的默認長度
     */
    public SequentialList() {
        this(64);
    }

    //時間復雜度為O(1)
    @Override
    public boolean isEmpty() {
        return this.len == 0;
    }

    //時間復雜度為O(1)
    @Override
    public int size() {
        return this.len;
    }
    
    //時間復雜度為O(1)
    @Override
    public T get(int index) {
        if (index >= 0 && index < this.len){
            return (T) this.element[index];
        }
        return null;
    }

    //時間復雜度為O(1)
    @Override
    public void set(int index, T t) {
        if (t == null){
            return;
        }
        if (index >= 0 && index < this.len){
            this.element[index] = t;
        }else {
            throw new IndexOutOfBoundsException(index+"");
        }
    }
    
}

2.3 順序表的插入與刪除

順序表的插入和刪除操作要移動數(shù)據(jù)元素。

插入元素時如果數(shù)組已滿，則不能插入，會報數(shù)據(jù)溢出異常(IndexOutOfBoundsException)。解決數(shù)據(jù)溢出的辦法是，將這個數(shù)組擴容。
而jdk實現(xiàn)的方式是申請一個更大的數(shù)組并復制全部數(shù)組元素，這樣就擴充了順序表的容量。

public class SequentialList<T> implements LList<T> {
    //時間復雜度為O(n)
    public void insert(int index, T t) {
        if (t == null){
            return;
        }
        //如果數(shù)組滿了，則擴容順序表的容量
        if (this.len == element.length){
            Object[] tmp = this.element;
            this.element = new Object[tmp.length*2];
            for (int i = 0;i<tmp.length;i++){
                this.element[i] = tmp[i];
            }
        }

        //下標容錯
        if (index < 0){
            index = 0;
        }
        if (index > this.len){
            index = this.len;
        }

        //元素后移，平均移動len/2
        for (int i = this.len-1;i>=index;i--){
            this.element[i+1] = this.element[i];
        }

        this.element[index] = t;
        this.len++;
    }

    public void add(T t) {
        insert(this.len,t);
    }
}

public class SequentialList<T> implements LList<T> {

    public T remove(int i) {
        if (this.len == 0 || i<0 || i >= this.len){
            return null;
        }

        T old = (T) this.element[i];
        for (int j = i;j<this.len-1;j++){
            this.element[j] = this.element[j+1];
        }
        this.element[this.len-1] = null;
        this.len--;
        return old;
    }

    public void removeAll() {
        this.len = 0;
    }
}

2.5 順序表的淺拷貝與深拷貝

一個類的構造方法，如果其參數(shù)是該對象，則稱為拷貝構造方法。如：

public Student(Student student){ …… }

拷貝構造方法的功能是復制對象，以形式參數(shù)的實例值初始化當前新創(chuàng)建對象。

順序表的淺拷貝：如果一個類將拷貝構造方法實現(xiàn)為逐域拷貝，即將當前對象的各種成員變量值賦值為實際參數(shù)對應各成員變量值，稱為淺拷貝。
如SequentialList類的淺拷貝構造方法：

public class SequentialList<T> implements LList<T> {
    /**
     * 淺拷貝的構造方法
     */
    public SequentialList(SequentialList<T> list){
        this.element = list.element;
        this.len = list.len;
    }
}

在Java中數(shù)據(jù)類型是基本類型時，淺拷貝能夠實現(xiàn)對象復制功能，數(shù)組和類是引用類型，兩個數(shù)組/對象之間的賦值是引用賦值，數(shù)組賦值過程中沒有申請新的存儲空間，
對象賦值過程中沒有創(chuàng)建新的實例。因此當成員變量的數(shù)據(jù)類型是引用類型時，淺拷貝只復制了對象引用，并沒有真正實現(xiàn)對象復制功能。

順序表的深拷貝：一個類包含引用類型的成員變量時，該類聲明的拷貝構造函數(shù)，不僅復制對象的所有基本類型成員變量值，
還重新申請引用類型變量占用的動態(tài)存儲空間，并復制其中所有對象。
如SequentialList類的深拷貝構造方法：

public class SequentialList<T> implements LList<T> {
    /**
     * 深拷貝的構造方法
     */
    public SequentialList(SequentialList<T> list){
            this.len = list.len;
            this.element = new Object[list.element.length];
            for (int i = 0;i<list.element.length;i++){
                this.element[i] = list.element[i];
            }
    }
}

結合順序表的特點思考一下約瑟夫環(huán)的問題

有n個人，環(huán)成一圈開始報數(shù)，從s數(shù)起，數(shù)到m就槍斃一個，然后繼續(xù)從s數(shù)起，數(shù)到d就槍斃一個，直到所有槍斃。輸出所有人的死亡順序。

public class Josephus {

    /**
     * @param number 總數(shù)量
     * @param start 開始位置
     * @param distance 執(zhí)行位置
     */
    public Josephus(int number,int start,int distance){
        SequentialList<String> list = new SequentialList<>(number);
        for (int i= 0;i<number;i++){
            list.add((char)('A'+i)+"");
        }
        System.out.println("約瑟夫環(huán)("+number+","+start+","+distance+")");
        System.out.println(list.toString());

        int i = start;
        while (list.size() > 1){
            i = (i + distance-1)%list.size();
            System.out.println("刪除"+list.remove(i).toString());
            System.out.println(list.toString());
        }
        System.out.println("被赦免者是"+list.get(0).toString());
    }

    public static void main(String[] args) {
        new Josephus(5,0,2);

    }
}

3.線性表的鏈式表示和實現(xiàn)

線性表的鏈式存儲是用若干地址分散的存儲單元存儲數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素在物理位置不一定相鄰。
存儲一個數(shù)據(jù)元素的存儲單元至少包含兩個部分——數(shù)據(jù)域和地址域，數(shù)據(jù)域中存儲的是數(shù)據(jù)元素值，地址域存儲的是后繼元素的地址。

3.1 單鏈表

單鏈表是由一個個結點鏈接而成，如圖：

單鏈表結構圖.PNG

3.1.1 單鏈表的結點

單鏈表是由一個個結點鏈接而成，不同的鏈表之間的區(qū)別在與結點的不同。
聲明單鏈表的類Node，代碼如下：

public class Node<T> {
    /**數(shù)據(jù)域，保存數(shù)據(jù)元素*/
    public T data;
    /**地址域，引用后繼結點,通過next鏈將兩個結點鏈接起來*/
    public Node<T> next;

    public Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }

    public Node() {
        this(null,null);
    }
}

成員變量next的數(shù)據(jù)類型是Node類自己，這個類型稱為“自引用的類”。是指一個類聲明包含一個引用當前類的對象的成員變量。

3.1.2 單鏈表的遍歷操作

遍歷單鏈表是指從第一個結點開始，沿著結點的next鏈，依次訪問單鏈表中的每個結點，并且每個結點只訪問一次。

Node<T> node = head;
while(node != null){
    node = node.next;
}

語句node = node.next是node移動到后繼結點，此時結點間的鏈接關系沒有改變。如果寫為“node.next = node”，就變成node.next指向了自己，
改變了鏈接關系，并且丟失了后繼結點，遍歷就變成死循環(huán)

3.1.3 單鏈表的插入操作

對于單鏈表進行插入操作，只要改變結點間的鏈接關系，不需要移動數(shù)據(jù)元素。在單鏈表中插入一個結點，根據(jù)位置的不同分為：空表插入、頭插入、中間插入、尾插入
1.空表插入、頭插入

 head = new Node<T>(t,head);

空表插入也是頭插入,當然也可以拆開來寫：

if(head == null){
    //空表插入
    head = new Node<T>(t,null);
}else{
    //頭插入
    Node<T> node = new Node<T>(t,null);
    node.next = head;
}

2.中間插入、尾插入
假設node指向了非空單鏈表中的某個結點，在node之后的插入q結點

    Node<T> node = new Node<T>(t,null);
    q.next=node.next; //q的后繼結點是node的原后繼結點
    node.next = q;//q作為node的新后繼節(jié)點

若node指向最后一個結點，node.next == null,可以執(zhí)行上述代碼塊。上面代碼也可以精簡為一句話：

p.next = new Node<T>(t,p.next);

3.1.4 單鏈表的刪除操作

在單鏈表中刪除指定結點，只要改變結點的next域就可以改變結點間的鏈接關系，不需要移動元素。根據(jù)結點的位置分為頭刪除、中間刪除、尾刪除
1.頭刪除
刪除單鏈表第一個結點，只要使head指向其后繼結點即可

head = head.next;

若單鏈表只有一個結點，則刪除該結點后單鏈表為空表。

3.1.5 帶結點的單鏈表

帶頭結點的單鏈表是在單鏈表的第一個結點之前增加一個特殊結點，稱為頭結點。頭結點的作用是使所有鏈表（包括空表）的頭指針非空，
并使對單鏈表的插入、刪除操作不需要區(qū)分為空表或是否在第一個位置進行，從而與其他位置的插入、刪除操作一致。

public class SinglyLinkedList<T> implements LList<T> {

    //頭指針，指向單鏈表的頭結點
    public Node<T> head;

    /**
     * 重寫默認無參構造，構造一個單鏈表，并帶有頭結點，data和next都為null
     */
    public SinglyLinkedList() {
        head = new Node<T>();
    }

    /**
     * 淺拷貝構造函數(shù)
     * @param list
     */
    /*public SinglyLinkedList(SinglyLinkedList<T> list) {
        head = list.head;
    }*/

    /**
     * 深拷貝構造函數(shù)
     * @param list
     */
    public SinglyLinkedList(SinglyLinkedList<T> list) {
        this();
        Node<T> node = list.head.next;
        Node<T> rear = this.head;

        while (node != null){
            rear.next = new Node<T>(node.data,null);
            rear = rear.next;
            node = node.next;
        }
    }

    /**
     * 由指定數(shù)組中的多個對象構造單鏈表，采用尾插入構造單鏈表
     * @param element 數(shù)據(jù)元素
     */
    public SinglyLinkedList(T[] element) {
        this();
        Node<T> rear = head;
        for (int i = 0; i < element.length; i++) {
            rear.next = new Node<T>(element[i],null);
            rear = rear.next;
        }
    }

    @Override
    public boolean isEmpty() {
        return head.next == null;
    }

    @Override
    public int size() {
        int i = 0;
        Node<T> node = head.next;
        while (node != null){
            i++;
            node = node.next;
        }
        return i;
    }

    @Override
    public T get(int index) {
        if (index >= 0){
            Node<T> node = head.next;
            for (int i = 0; node != null && i<index; i++) {
                node = node.next;
            }
            if (node != null){
                return node.data;
            }
        }
        return null;
    }

    @Override
    public void set(int index, T t) {
        if (t == null){
            return;
        }
        if (index >= 0){
            Node<T> node = head.next;
            for (int i = 0; node != null && i<index; i++) {
                node = node.next;
            }
            if (node != null){
                node.data = t;
            }else{
                throw new IndexOutOfBoundsException(index+"");
            }
        }
    }

    @Override
    public void insert(int index, T t) {
        if (t == null){
            return;
        }
        Node<T> node = head;
        for (int i=0;node.next!=null&&index<i;i++){
            node = node.next;
        }
        node.next = new Node<T>(t,node.next);
    }

    @Override
    public void add(T t) {
        insert(Integer.MAX_VALUE,t);
    }

    @Override
    public T remove(int i) {
        if (i >= 0){
            Node<T> node = head;
            for (int j = 0; node.next != null && j<i ; j++) {
                node = node.next;
            }
            if (node.next != null){
                T old = node.data;
                node.next = node.next.next;
                return old;
            }
        }
        return null;
    }

    @Override
    public void removeAll() {
        head.next = null;
    }

    @Override
    public T search(T key) {
        ////在unit-10-search中實現(xiàn)
        return null;
    }

    @Override
    public String toString() {
        String string="(";
        Node<T> node = this.head.next;
        while (node != null) {
            string += node.data.toString();
            if (node.next != null){
                string += ",";
            }
            node = node.next;
        }

        return string+")";
    }
}

3.1.6 循環(huán)單鏈表

循環(huán)單鏈表就是鏈表最后的一個結點的next鏈保存單鏈表的頭指針head值，形成一個環(huán)形結構。

循環(huán)單鏈表.PNG

構造方法為：

public class CirSinglyLinkedList<T> {
    
    public Node<T> head;
    
    public CirSinglyLinkedList(){
        this.head = new Node<T>();
        this.head.next = this.head;
    }

    public boolean isEmpty() {
        return head.next == this.head;
    }

    @Override
    public String toString() {
        String string="(";
        Node<T> node = this.head.next;
        while (node != this.head) {
            string += node.data.toString();
            if (node.next != null){
                string += ",";
            }
            node = node.next;
        }

        return string+")";
    }
    
    //...其他方法參考同SinglyLinkedList.class
}

3.2雙鏈表

雙鏈表的每個結點有兩個地址域，分別指向它的前驅結點和后繼節(jié)點，結構如下：

循環(huán)雙鏈表.PNG

創(chuàng)建雙鏈表基類：

public class DLinkNode<T> {
    public T data;
    public DLinkNode<T> prev,next;

    public DLinkNode(T data, DLinkNode<T> prev, DLinkNode<T> next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }

    public DLinkNode() {
        this(null,null,null);
    }
}

雙鏈表的插入和刪除操作與單鏈表不同，其他均與單鏈表相似
1.雙鏈表的插入
在雙鏈表中插入一個結點，既可插入指定結點之前，也可以插入在指定結點之后。

//插入指定結點之前，假定在結點node之前插入值為x的q結點
q = new DLinkNode<T>(x,node.prev,node);
node.prev.next = q;
node.prev = q;

//插入指定結點之后，假定在結點node之后插入值為x的q結點
q = new DLinkNode<T>(x,node,node.next);
if(node.next != null){
    //中間插入時執(zhí)行
    node.prev.next = q;
}
node.prev = q;

2.雙鏈表的刪除
代碼如下：

node.prev.next = node.next;
if(node.next != null){
    node.next.prev = node.prev;
}

3.3循環(huán)雙鏈表

循環(huán)雙鏈表是最后一個結點的next指向頭結點，頭結點的prev鏈指向最后一個結點?？针p鏈表是后繼結點指向自己的開始結點，開始結點指向自己的后繼結點。

循環(huán)雙鏈表.PNG

代碼如下：

public class CirDoublyLinkedList<T> implements LList<T> {

    public DLinkNode<T> head;

    public CirDoublyLinkedList(DLinkNode<T> head) {
        this.head = new DLinkNode<T>();
        this.head.prev = head;
        this.head.next = head;
    }

    @Override
    public boolean isEmpty() {
        return head.next == null;
    }

    @Override
    public int size() {
        int i = 0;
        DLinkNode<T> node = head.next;
        while (node != null){
            i++;
            node = node.next;
        }
        return i;
    }

    @Override
    public T get(int index) {
        if (index >= 0){
            DLinkNode<T> node = head.next;
            for (int i = 0; node != null && i<index; i++) {
                node = node.next;
            }
            if (node != null){
                return node.data;
            }
        }
        return null;
    }

    @Override
    public void set(int index, T t) {
        if (t == null){
            return;
        }
        if (index >= 0){
            DLinkNode<T> node = head.next;
            for (int i = 0; node != null && i<index; i++) {
                node = node.next;
            }
            if (node != null){
                node.data = t;
            }else{
                throw new IndexOutOfBoundsException(index+"");
            }
        }
    }

    /**
     * 將對象t插入在序號為index結點上
     * 時間復雜度為O(n)
     * @param index 結點
     * @param t 對象
     */
    @Override
    public void insert(int index, T t) {
        //不能插入空對象
        if (t == null){
            return;
        }
        //尋找插入位置，當循環(huán)停止時，node指向index-1結點上
        DLinkNode<T> node = this.head;
        for (int i = 0;node.next != this.head && i<index;i++){
            node = node.next;
        }
        //插入在node結點上
        DLinkNode<T> linkNode = new DLinkNode<T>(t,node,node.next);
        node.next.prev = linkNode;
        node.next = linkNode;
    }

    /**
     * 在循環(huán)雙鏈表最后添加結點
     * 時間復雜度為O(n)
     * @param t 對象
     */
    @Override
    public void add(T t) {
        if (t == null){
            return;
        }
        //使用尾插法，插入在頭結點之前
        DLinkNode<T> linkNode = new DLinkNode<T>(t,head.prev,head);
        head.next.prev = linkNode;
        head.next = linkNode;
    }

    /**
     * 刪除序號為i的結點
     * @param i
     * @return
     */
    @Override
    public T remove(int i) {
        if (i >= 0){
            DLinkNode<T> node = this.head.next;
            //定位到待刪除的結點
            for (int j = 0;node != head&&j<i;j++){
                node = node.next;
            }

            if (node != head){
                //獲得原對象
                T old = node.data;
                node.prev.next = node.next;
                //刪除序號為i的結點
                node.next.prev = node.prev;
                return old;
            }
        }
        return null;
    }

    @Override
    public void removeAll() {
        this.head.prev = head;
        this.head.next = head;
    }

    @Override
    public T search(T key) {
        //在unit-10-search中實現(xiàn)
        return null;
    }
}

鏈接：文檔地址源碼地址

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一起學數(shù)據(jù)結構：線性表

一起學數(shù)據(jù)結構：線性表

線性表

1.線性表抽象數(shù)據(jù)類型

2.線性表的順序表示和實現(xiàn)

2.1 線性表的順序存儲結構

2.2順序表

2.3 順序表的插入與刪除

2.5 順序表的淺拷貝與深拷貝

結合順序表的特點思考一下約瑟夫環(huán)的問題

3.線性表的鏈式表示和實現(xiàn)

3.1 單鏈表

3.1.1 單鏈表的結點

3.1.2 單鏈表的遍歷操作

3.1.3 單鏈表的插入操作

3.1.4 單鏈表的刪除操作

3.1.5 帶結點的單鏈表

3.1.6 循環(huán)單鏈表

3.2雙鏈表

3.3循環(huán)雙鏈表

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

一起學數(shù)據(jù)結構：線性表

線性表

1.線性表抽象數(shù)據(jù)類型

2.線性表的順序表示和實現(xiàn)

2.1 線性表的順序存儲結構

2.2順序表

2.3 順序表的插入與刪除

2.5 順序表的淺拷貝與深拷貝

結合順序表的特點思考一下約瑟夫環(huán)的問題

3.線性表的鏈式表示和實現(xiàn)

3.1 單鏈表

3.1.1 單鏈表的結點

3.1.2 單鏈表的遍歷操作

3.1.3 單鏈表的插入操作

3.1.4 單鏈表的刪除操作

3.1.5 帶結點的單鏈表

3.1.6 循環(huán)單鏈表

3.2雙鏈表

3.3循環(huán)雙鏈表

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av