資料結構（java）-1.1-線性表（理論知識）

目錄

線性表

線性順序表

線性連結清單

單連結清單

靜态連結清單

循環連結清單

雙向連結清單

線性表_順序表的基本實作

線性表

線性表概述

線性表是最基本、最簡單、也是最常用的一種資料結構。一個線性表是n個具有相同特征的資料元素的有限序列。

前驅元素：若A在B元素的前面，則稱A為B的前驅元素。

後繼元素：若B在A元素的後面，則稱B為A的後繼元素。

線性表的特征：

1、第一個元素沒有前驅，這個資料元素被稱為頭結點。

2、最後一個元素沒有後繼，這個元素被稱為尾結點。

3.除了第一個和最後一個資料元素外，其他資料元素有且僅有一個前驅和一個後繼。

線性表的分類：

線性表中資料存儲的方式可以是順序存儲，也可以是鍊式存儲，按照資料的存儲方式不同，可以把線性表分為順序表和連結清單。（順序存儲的存儲位址是連續的，鍊式存儲存儲位址不一定連續）

線性順序表

在計算機内以數組的形式儲存的線性表，通過資料元素實體存儲的相鄰關系來反映資料元素之間邏輯上的相鄰關系。

性表的順序存儲結構：把線性表的結點按邏輯順序依次存放在一組位址連續的存儲單元裡。用這種方法存儲的線性表簡稱順序表。是一種随機存取的存儲結構。順序存儲指記憶體位址是一塊的，随機存取指通路時可以按下标随機通路，存儲和存取是不一樣的。如果是存儲，則是指按順序的，如果是存取，則是可以随機的，可以利用元素下标進行。數組比線性表速度更快的是：原地逆序、傳回中間節點、選擇随機節點。

1.便于線性表的構造和任意元素的通路

2.插入：插入新結點，之後結點後移。

3.删除：删除節點，之後結點前移。

線性連結清單

用一組任意的存儲單元來依次存放線性表的結點，這組存儲單元即可以是連續的，也可以是不連續的，甚至是零散分布在記憶體中的任意位置上的。

連結清單中結點的邏輯次序和實體次序不一定相同。為了能正确表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲訓示其後繼結點的位址。data域是資料域，用來存放結點的值。next是指針域（亦稱鍊域），用來存放結點的直接後繼的位址（或位置）。不需要事先估計存儲空間大小。

單連結清單

單連結清單中每個結點的存儲位址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。同時，由于最後一個結點無後繼，故結點的指針域為空，即NULL。頭插法建表(逆序)、尾插法建表(順序)。增加頭結點的目的是算法實作上的友善，但增大了記憶體開銷。

1.查找：隻能從連結清單的頭指針出發，順鍊域next逐個結點往下搜尋，直到搜尋到第i個結點為止。是以，連結清單不是随機存取結構。

2.插入：先找到表的第i-1的存儲位置，然後插入。新結點先連後繼，再連前驅。

3.删除：首先找到ai-1的存儲位置p。然後令p–>next指向ai的直接後繼結點，即把ai從鍊上摘下。最後釋放結點ai的空間.r=p->next;p->next=r->next;delete r。

4.判斷一個單向連結清單中是否存在環的最佳方法是快慢指針。

靜态連結清單

靜态連結清單：用一維數組來實作線性連結清單，這種用一維數組表示的線性連結清單，稱為靜态連結清單。靜态：展現在表的容量是一定的。（數組的大小）；連結清單：插入與删除同前面所述的動态連結清單方法相同。靜态連結清單中指針表示的是下一進制素在數組中的位置。

靜态連結清單是用數組實作的，是順序的存儲結構，在實體位址上是連續的，而且需要預先配置設定大小。動态連結清單是用申請記憶體函數（C是malloc,C++是new）動态申請記憶體的，是以在連結清單的長度上沒有限制。動态連結清單因為是動态申請記憶體的，是以每個節點的實體位址不連續，要通過指針來順序通路。靜态連結清單在插入、删除時也是通過修改指針域來實作的，與動态連結清單沒有什麼分别。

循環連結清單

循環連結清單：是一種頭尾相接的連結清單。其特點是無須增加存儲量，僅對表的連結方式稍作改變，即可使得表處理更加友善靈活。

在單連結清單中，将終端結點的指針域NULL改為指向表頭結點的或開始結點，就得到了單鍊形式的循環連結清單，并簡單稱為單循環連結清單。由于循環連結清單中沒有NULL指針，故涉及周遊操作時，其終止條件就不再像非循環連結清單那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指針或尾指針等。

雙向連結清單

雙向連結清單:在單連結清單的每個結點裡再增加一個指向其直接前趨的指針域prior。這樣就形成的連結清單中有兩個方向不同的鍊。雙連結清單一般由頭指針唯一确定的，将頭結點和尾結點連結起來構成循環連結清單，并稱之為雙向連結清單。設指針p指向某一結點，則雙向連結清單結構的對稱性可用下式描述：p—>prior—>next=p=p—>next—>prior。從兩個方向搜尋雙連結清單，比從一個方向搜尋雙連結清單的方差要小。

1.插入：先搞定插入節點的前驅和後繼，再搞定後結點的前驅，最後搞定前結點的後繼。

2.在有序雙向連結清單中定位删除一個元素的平均時間複雜度為O(n)

3.可以直接删除目前指針所指向的節點。而不需要像單向連結清單中，删除一個元素必須找到其前驅。是以在插入資料時，單向連結清單和雙向連結清單操作複雜度相同，而删除資料時，雙向連結清單的性能優于單向連結清單。

線性表_順序表的基本實作

代碼結構

源代碼

package linear;

import java.util.Objects;

public class SequenceList <T>{
    //存儲元素的數組
    private T[] eles;
    //記錄目前順序表中的元素個數

    private  int N;

    //構造方法
    public SequenceList(int capacity){
        //初始化數組
        this.eles=(T[])new Object[capacity];//強轉為T類型的數組
        //初始化長度
        this.N=0;

    }

    //将一個線性表值為空表
    public void clear(){
        this.N=0;
    }

    //判斷目前線性表是否為空表
    public boolean isEmpty(){
        return N==0;
    }

    //擷取線性表的長度
    public int length(){
        return N;
    }

    //擷取指定位置的元素
    public T get(int i){
        return eles[i];
    }

    //向線性表中添加元素t
    public void insert(T t){
        eles[N++]=t;
    }

    //在i元素處插入元素t
    public void insert(int i,T t){
       //先把i索引處的元素及其後面的元素依次向後移動一位
        for(int index=N-1;index>i;index--){
            eles[index]=eles[index-1];
        }
       // 再把t元素放到i元素處即可
        eles[i]=t;
    }

    //删除指定位置i處的元素，并傳回該元素
    public T remove(int i){
        //記錄索引i處的值
        T current=eles[i];
        //索引i後面的元素依次向前移動一位即可
        for (int index=i;index<N-1;index++){
            eles[index]=eles[index+1];
        }
        //元素個數減一
        N--;
        return current;
    }

    //查找t元素第一次出現的位置
    public  int indexOf(T t){
        for(int i=0;i<N;i++){
            if(eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
}
           

測試類

package linear;


import linear.SequenceList;

import java.sql.SQLOutput;

public class SequenceListTest {
    public static void main(String[] args) {
        //建立順序表對象
        SequenceList<String> sl = new SequenceList<>(10);

        //測試插入
        sl.insert("周自珩");
        sl.insert("夏習清");
        sl.insert(1,"盛放星雲");

        //測試擷取
        String getResult = sl.get(1);
        System.out.println("擷取索引1處的結果為："+getResult);

        //測試删除
        String removeResult = sl.remove(0);
        System.out.println("删除的元素是："+removeResult);

        //測試清空
        sl.clear();
        System.out.println("清空後的線性表中的元素個數為："+sl.length());

    }
}
           

測試結果