數(shù)據(jù)結(jié)構(gòu)于算法—線性表詳解

Freelander 發(fā)布于2019-08-19 10:29 / 2041人閱讀

摘要：前言通過前面數(shù)據(jù)結(jié)構(gòu)與算法前導(dǎo)我么知道了數(shù)據(jù)結(jié)構(gòu)的一些概念和重要性，那么我們今天總結(jié)下線性表相關(guān)的內(nèi)容。基本結(jié)構(gòu)對(duì)于線性表，我們只需要一個(gè)數(shù)組和就能表示基本信息。

前言

通過前面數(shù)據(jù)結(jié)構(gòu)與算法前導(dǎo)我么知道了數(shù)據(jù)結(jié)構(gòu)的一些概念和重要性，那么我們今天總結(jié)下線性表相關(guān)的內(nèi)容。當(dāng)然，我用自己的理解解分享給大家。

其實(shí)說實(shí)話，可能很多人依然分不清線性表，順序表，和鏈表之間的區(qū)別和聯(lián)系！

線性表：邏輯結(jié)構(gòu)，就是對(duì)外暴露數(shù)據(jù)之間的關(guān)系，不關(guān)心底層如何實(shí)現(xiàn)。

順序表、鏈表：物理結(jié)構(gòu)，他是實(shí)現(xiàn)一個(gè)結(jié)構(gòu)實(shí)際物理地址上的結(jié)構(gòu)。比如順序表就是用數(shù)組實(shí)現(xiàn)。而鏈表用指針完成主要工作。不同的結(jié)構(gòu)在不同的場(chǎng)景有不同的區(qū)別。

對(duì)于java來說，大家都知道List接口類型，這就是邏輯結(jié)構(gòu)，因?yàn)樗褪欠庋b了一個(gè)線性關(guān)系的一系列方法和數(shù)據(jù)。而具體的實(shí)現(xiàn)其實(shí)就是跟物理結(jié)構(gòu)相關(guān)的內(nèi)容。比如順序表的內(nèi)容存儲(chǔ)使用數(shù)組的，然后一個(gè)get，set，add方法都要基于數(shù)組來完成,而鏈表是基于指針的。當(dāng)我們考慮對(duì)象中的數(shù)據(jù)關(guān)系就要考慮指針的屬性。指針的指向和value。

下面用一個(gè)圖來淺析線性表的關(guān)系。可能有些不太確切，但是其中可以參考，并且后面也會(huì)根據(jù)這個(gè)圖舉例。
在這里插入圖片描述

線性表基本架構(gòu)

對(duì)于一個(gè)線性表來說。不管它的具體實(shí)現(xiàn)方法如何，我們應(yīng)該有的函數(shù)名稱和實(shí)現(xiàn)效果應(yīng)該一致。你也可以感覺的到在一些結(jié)構(gòu)的設(shè)計(jì)。比如List的Arraylist和LinkedList。Map的HashMap和currentHashMap他們的接口api都是相同的，但是底層設(shè)計(jì)實(shí)現(xiàn)肯定是有區(qū)別的。

所以，基于面向?qū)ο蟮木幊趟季S，我們可以將線性表寫成一個(gè)接口，而具體實(shí)現(xiàn)的順序表和鏈表可以繼承這個(gè)接口的方法，提高程序的可讀性。

還有一點(diǎn)比較重要的，記得初學(xué)數(shù)據(jù)結(jié)構(gòu)與算法時(shí)候?qū)崿F(xiàn)的線性表都是固定類型(int),隨著知識(shí)的進(jìn)步，我們應(yīng)當(dāng)采用泛型來實(shí)現(xiàn)更合理。至于接口的具體設(shè)計(jì)如下：

package LinerList;
public interface ListInterface {    
    void Init(int initsize);//初始化表
    int length();
    boolean isEmpty();//是否為空
    int ElemIndex(T t);//找到編號(hào)
    T getElem(int index) throws Exception;//根據(jù)index獲取數(shù)據(jù)
    void add(int index,T t) throws Exception;//根據(jù)index插入數(shù)據(jù)
    void delete(int index) throws Exception;
    void add(T t) throws Exception;//尾部插入
    void set(int index,T t) throws Exception;
    String toString();//轉(zhuǎn)成String輸出    
}

順序表

順序表是基于數(shù)組實(shí)現(xiàn)的，所以一些方法要基于數(shù)組的特性。對(duì)于順序表應(yīng)該有的基礎(chǔ)屬性為一個(gè)數(shù)組data和一個(gè)length.

還有需要注意的是初始化數(shù)組的大小，你可以固定大小，但是筆者為了可用性如果內(nèi)存不夠?qū)?b>擴(kuò)大二倍。當(dāng)然這樣很可能因?yàn)榭臻g使用問題造成很大的浪費(fèi)。

一些基本的額方法就不說了，下面著重講解一些初學(xué)者容易混淆的概念和方法實(shí)現(xiàn)。這里把順序表比作一隊(duì)坐在板凳上的人。

插入

add(int index,T t)

其中index為插入的編號(hào)位置，t為插入的數(shù)據(jù)

根據(jù)圖片你就很好理解插入操作。當(dāng)插入一個(gè)index時(shí)候，他的后面所有元素都要后移一位。你可以看的出插入時(shí)候整個(gè)操作的臃腫性。所以這也是順序表性能表現(xiàn)最差的地方,頻繁的插入，刪除。

刪除

同理，刪除也是非常占用資源的。原理和插入類似，不過人走了，空一個(gè)小板凳后面的人需要往前挪。

其他操作

其他操作就很簡(jiǎn)單了。比如如果按照編號(hào)獲取數(shù)據(jù)getElem(int index)，你可以直接根據(jù)數(shù)據(jù)坐標(biāo)返回。a[index]，而其他操作，可以通過遍歷直接操作數(shù)組即可。

鏈表

我想，表應(yīng)該是很多人感覺很繞的東西，這個(gè)很大原因可能因?yàn)?b>指針。很多人說java沒指針，其實(shí)java他也有隱形指針。只不過不能直接用罷了。

指針建立的數(shù)據(jù)關(guān)系往往比數(shù)組這些要抽象的多。對(duì)于指針域，你把他當(dāng)成一個(gè)對(duì)象就好了，不過這個(gè)對(duì)象指向的是另一個(gè)同等級(jí)對(duì)象。對(duì)于這個(gè)關(guān)系，你可以比作每個(gè)person類。每個(gè)person類都有老公(老婆),而這個(gè)老公老婆也是一個(gè)實(shí)際對(duì)象，可以理解這更像一種邏輯約定關(guān)系，而不是硬生生的關(guān)系吧。

指針你可以考慮成腦子記憶。上面的順序表我們說它有序因?yàn)槊總€(gè)小板凳(數(shù)組)有編號(hào)，我們可以根據(jù)這個(gè)來確定位置。而對(duì)于鏈表來說，你可以看作成一個(gè)站在操場(chǎng)上的一隊(duì)人。而他的操作也略有不同，下面針對(duì)一些比較特殊和重要的進(jìn)行歸納。

基本結(jié)構(gòu)

對(duì)于線性表，我們只需要一個(gè)data數(shù)組和length就能表示基本信息。而對(duì)于鏈表，我們需要一個(gè)node(head頭節(jié)點(diǎn))，和length,當(dāng)然，這個(gè)node也是一個(gè)結(jié)構(gòu)體。

class node{
    T data;//節(jié)點(diǎn)的結(jié)果
    node next;//下一個(gè)連接的節(jié)點(diǎn)
    public node(){}
    public node(T data)
    {
        this.data=data;
    }
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    } 
}

當(dāng)然，這個(gè)節(jié)點(diǎn)有數(shù)據(jù)域和指針域。數(shù)據(jù)域就是存放真實(shí)的數(shù)據(jù)，而指針域就是存放下一個(gè)node的指針。所以相比順序表，如果用滿數(shù)組情況下，鏈表占用更多的資源，因?yàn)樗娣胖羔樥加觅Y源。

插入

add(int index,T t)
其中index為插入的編號(hào)位置，t為插入的數(shù)據(jù)
加入插入一個(gè)節(jié)點(diǎn)node，根據(jù)index找到插入的前一個(gè)節(jié)點(diǎn)叫pre。那么操作流程為

node.next=pre.next如下1的操作，將插入節(jié)點(diǎn)后面聯(lián)系起來。此時(shí)node.next和pre.next一致。

pre.next=node因?yàn)槲覀円迦雗ode，而node鏈可以替代pre自身的next。那么直接將pre指向node。那么就相當(dāng)于原始鏈表插入了一個(gè)node。

帶頭節(jié)點(diǎn)與不帶頭節(jié)點(diǎn)

很多人搞不清什么是帶頭節(jié)點(diǎn)和不帶頭節(jié)點(diǎn)。帶頭節(jié)點(diǎn)就是head節(jié)點(diǎn)不放數(shù)據(jù)，第0項(xiàng)從head后面那個(gè)開始數(shù)。而不帶頭節(jié)點(diǎn)的鏈表head放數(shù)據(jù)，head節(jié)點(diǎn)就是第0位。
主要區(qū)別：

帶頭節(jié)點(diǎn)和不帶頭節(jié)點(diǎn)的主要區(qū)別就在插入刪除首位，尤其是首位插入。帶頭節(jié)點(diǎn)找元素需要多遍歷一次因?yàn)樗牡谝粋€(gè)head節(jié)點(diǎn)是頭節(jié)點(diǎn)，不存數(shù)據(jù)(可看作一列火車的火車頭)。而方便的就是帶頭節(jié)點(diǎn)在首位插入更簡(jiǎn)單。因?yàn)椴迦?b>第0位也是在head的后面。

而不帶頭節(jié)點(diǎn)的鏈表就需要特殊考慮首位。因?yàn)椴迦氲?位其實(shí)是插入head的前面。假設(shè)有head，插入node。具體操作為：

node.next=head；(node指向head，node這條鏈成我們想要的鏈)

head=node；(很多人想不明白，其實(shí)這個(gè)時(shí)候node才是插入后最長(zhǎng)鏈的首位節(jié)點(diǎn)，head在他的后面，而在鏈表中head通常表示首位節(jié)點(diǎn)，所以head不表示第二個(gè)節(jié)點(diǎn)，直接"="node節(jié)點(diǎn)。這樣head和node都表示操作完成的鏈表。但是對(duì)外暴露的只有head。所以head只能指向第一個(gè)節(jié)點(diǎn)！)

插入尾

而在插入尾部的時(shí)候，需要注意尾部的next為null。不能和插入普通位置相比！

刪除

按照index移除：delete(int index)

找到該index的節(jié)點(diǎn)node。node.next=node.next.nex

按照尾部移除(拓展)：deleteEnd()

這個(gè)方法我沒有寫，但是我給大家講一下，按照尾部刪除的思想就是：

聲明一個(gè)node為head。

當(dāng)node.next！=null時(shí)node=node.next 指向下一個(gè)

當(dāng)node.next==null時(shí)候。說明這個(gè)節(jié)點(diǎn)時(shí)最后一個(gè)。你可以node=null。這個(gè)這個(gè)node的前驅(qū)pre的next就是null。這個(gè)節(jié)點(diǎn)就被刪除了。

頭部刪除(帶頭節(jié)點(diǎn))：

帶頭節(jié)點(diǎn)的刪除和普通刪除一直。直接head.next(第1個(gè)元素)=head.next.next(第二個(gè)元素)

這樣head.next就直接指向第二個(gè)元素了。第一個(gè)就被刪除了

頭部刪除(不帶頭節(jié)點(diǎn))

我們知道不帶頭節(jié)點(diǎn)的第一個(gè)就是存貨真價(jià)實(shí)的元素的。不帶頭節(jié)點(diǎn)刪除也很簡(jiǎn)單。直接將head移到第二位就行了。即：head=head.next

其他

對(duì)于其他操作，主要時(shí)結(jié)合查找。而單鏈表的查找時(shí)從head開始。然后另一個(gè)節(jié)點(diǎn)team=head或head.next。然后用這個(gè)節(jié)點(diǎn)不停的等于它指向的next去查找我們需要的內(nèi)容即while(循環(huán)條件){team=team.next}類似。

不同教程和人寫的線性表也不一致，這里只給出一個(gè)樣例學(xué)習(xí)使用而并不是標(biāo)準(zhǔn)，希望大家審視。

在實(shí)現(xiàn)上用了帶頭節(jié)點(diǎn)的鏈表實(shí)現(xiàn)，因?yàn)楸容^方便管理，不需要很多if else.

代碼實(shí)現(xiàn) 順序表

package LinerList;

public class seqlist implements ListInterface {
    private Object[] date;//數(shù)組存放數(shù)據(jù)
    private int lenth;
    public seqlist() {//初始大小默認(rèn)為10
        Init(10);
    }

    public void Init(int initsize) {//初始化
        this.date=new Object[initsize];
        lenth=0;        
    }
    public int length() {        
        return this.lenth;
    }

    public boolean isEmpty() {//是否為空
        if(this.lenth==0)
            return true;
        return false;
    }

    /*
     * * @param t    
     * 返回相等結(jié)果，為-1為false
     */
    public int ElemIndex(T t) {
        // TODO Auto-generated method stub
        for(int i=0;ilenth-1)
            throw new Exception("數(shù)值越界");
        return (T) date[index];
    }
    
    public void add(T t) throws Exception {//尾部插入
         add(lenth,t);
    }

    /*
     *根據(jù)編號(hào)插入
     */
    public void add(int index, T t) throws Exception {
        if(index<0||index>lenth)
            throw new Exception("數(shù)值越界");
        if (lenth==date.length)//擴(kuò)容
        {
            Object newdate[]= new Object[lenth*2];
            for(int i=0;i=index;i--)//后面元素后移動(dòng)
        {
            date[i+1]=date[i];
        }
        date[index]=t;//插入元素
        lenth++;//順序表長(zhǎng)度+1
        
    }

    public void delete(int index) throws Exception {
        if(index<0||index>lenth-1)
            throw new Exception("數(shù)值越界");
        for(int i=index;ilenth-1)
            throw new Exception("數(shù)值越界");
        date[index]=t;
    }
    public String  toString() {
        String vaString="";
        for(int i=0;i
鏈表
package LinerList;

class node{
    T data;//節(jié)點(diǎn)的結(jié)果
    node next;//下一個(gè)連接的節(jié)點(diǎn)
    public node(){}
    public node(T data)
    {
        this.data=data;
    }
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    }
   
}
public class Linkedlist implements ListInterface{

    node head;
    private int length;
    public Linkedlist() {
        head=new node();
        length=0;
    }
    public void Init(int initsize) {
        head.next=null;
        
    }

    public int length() {
        return this.length;
    }

    
    public boolean isEmpty() {
        if(length==0)return true;
        else return false;
    }

    /*
     * 獲取元素編號(hào)
     */
    public int ElemIndex(T t) {
        node team=head.next;
        int index=0;
        while(team.next!=null)
        {
            if(team.data.equals(t))
            {
                return index;
            }
            index++;
            team=team.next;
        }
        return -1;//如果找不到
    }

    @Override
    public T getElem(int index) throws Exception {
        node team=head.next;
        if(index<0||index>length-1)
        {
            throw new Exception("數(shù)值越界");
        }
        for(int i=0;ilength)
        {
            throw new Exception("數(shù)值越界");
        }
        node team=head;//team 找到當(dāng)前位置node
        for(int i=0;inode =new node(value);//新建一個(gè)node
        node.next=team.next;//指向index前位置的下一個(gè)指針
        team.next=node;//自己變成index位置    
        length++;
    }
    

    @Override
    public void delete(int index) throws Exception {
        if(index<0||index>length-1)
        {
            throw new Exception("數(shù)值越界");
        }
        node team=head;//team 找到當(dāng)前位置node
        for(int i=0;ilength-1)
        {
            throw new Exception("數(shù)值越界");
        }
        node team=head;//team 找到當(dāng)前位置node
        for(int i=0;i
測(cè)試與結(jié)果
package LinerList;
public class test {
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        System.out.println("線性表測(cè)試：");
        ListInterfacelist=new seqlist();
        list.add(5);
        list.add(6);
        list.add(1,8);
        list.add(3,996);
        list.add(7);
        System.out.println(list.ElemIndex(8));
        System.out.println(list.toString());
        list.set(2, 222);
        System.out.println(list.toString());
        list.delete(4);
        System.out.println(list.toString());
        System.out.println(list.length());    
        
        System.out.println("鏈表測(cè)試：");
        list=new Linkedlist();
        list.add(5);
        list.add(6);
        list.add(1,8);
        list.add(3,996);
        list.add(7);
        System.out.println(list.ElemIndex(8));
        System.out.println(list.toString());
        list.set(2, 222);
        System.out.println(list.toString());
        list.delete(4);
        System.out.println(list.toString());
        System.out.println(list.length());    
    }
}

輸出:
線性表測(cè)試：
1
5 8 6 996 7 
5 8 222 996 7 
5 8 222 996 
4
鏈表測(cè)試：
1
5 8 6 996 7 
5 222 6 996 7 
5 222 6 996 
4
總結(jié)

這里的只是簡(jiǎn)單實(shí)現(xiàn)，實(shí)現(xiàn)基本方法。鏈表也只是單鏈表。完善程度還可以優(yōu)化。如果有錯(cuò)誤還請(qǐng)大佬指正。
單鏈表查詢速度較慢，因?yàn)樗枰獜念^遍歷。如果頻繁操作尾部，可以考慮鏈表中不僅有head在加尾tail節(jié)點(diǎn)。而順序表查詢速度雖然快但是插入很費(fèi)時(shí)費(fèi)力。實(shí)際應(yīng)用根據(jù)需求選擇！
java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優(yōu)化，并且jdk的api做了大量?jī)?yōu)化。所以大家不用造輪子，可以直接用，但是還是很有學(xué)習(xí)價(jià)值的。
如果有不理解或者不懂的可以聯(lián)系交流討論。筆者敞開自家公眾號(hào)的大門隨時(shí)歡迎受訪！下面還會(huì)持續(xù)出貨分享！，感覺不錯(cuò)的可以點(diǎn)個(gè)贊，關(guān)注一波公眾號(hào)(回復(fù)數(shù)據(jù)結(jié)構(gòu)有精心準(zhǔn)備資料一份)：bigsai