本文主要內(nèi)容：線性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)以及相應(yīng)算法疗锐；

1. 定義和特點(diǎn)

1. 定義：

由N（N>=0）個(gè)數(shù)據(jù)特性相同的元素構(gòu)成的有限序列稱為線性表。N為線性表長(zhǎng)度滚停，當(dāng)N為0時(shí)就是空表霉囚。

非空線性表或是線性結(jié)構(gòu)橡卤，其的特點(diǎn)是：

線性表的順序表示和實(shí)現(xiàn)
線性表的順序表：指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素碧库。（這種表示又叫線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像）Sequential List

2. 特點(diǎn)**：

邏輯上相鄰的元素，物理上也相鄰 巧勤；

公式：Loc（ai）=Loc(a0）+（i-1）x L
所以只要確定了一個(gè)元素的位置嵌灰，表中任意元素都可以隨機(jī)存取，因此線性表是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)颅悉。
存取的時(shí)間復(fù)雜度為O(1).

缺點(diǎn)：插入和刪除費(fèi)時(shí)沽瞭，需要移動(dòng)大量的元素，長(zhǎng)度固定剩瓶。

3. 線性表的算法時(shí)間復(fù)雜度

4. 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)：
用一組任意的存儲(chǔ)單元（可連續(xù)可不連續(xù)）存儲(chǔ)線性表的數(shù)據(jù)元素傍药，存儲(chǔ)時(shí)需要額外的存儲(chǔ)單元存儲(chǔ)后繼元素的信息。

每個(gè)存儲(chǔ)的元素稱為節(jié)點(diǎn)（Node）魂仍，它由兩部分組成：

• 數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素信息的區(qū)域拐辽；
• 指針域：存儲(chǔ)直接后繼元素的位置；（稱為：指針或鏈）

由n個(gè)節(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表擦酌，即為鏈?zhǔn)降木€性表俱诸。

根據(jù)鏈表所含的指針個(gè)數(shù)，指針指向赊舶，指針連接方式睁搭，將鏈表分為：

其中單鏈表笼平、循環(huán)鏈表园骆、雙向鏈表用于實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其他鏈表多用于實(shí)現(xiàn)樹和圖等非線性結(jié)構(gòu)寓调。

4.1 單鏈表
單鏈表的存取必須從頭指針開(kāi)始進(jìn)行锌唾，頭指針指示鏈表的第一個(gè)節(jié)點(diǎn)，最后一個(gè)元素的指針為空NULL。
特點(diǎn)：

• 元素之間的關(guān)系有指針域指示晌涕；
• 邏輯上相鄰元素滋捶，物理上不一定相鄰；
• 存儲(chǔ)結(jié)構(gòu)為非順序印象余黎，是鏈?zhǔn)接诚瘢?/li>

一般為了處理方便重窟，會(huì)在單鏈表的第一個(gè)節(jié)點(diǎn)之前設(shè)置一個(gè)頭結(jié)點(diǎn)，該頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息惧财，也可以存儲(chǔ)線性表的長(zhǎng)度信息或其它附加信息亲族，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)節(jié)點(diǎn)的指針。

示例：
指針頭: H –>31可缚，如果H指向null表示為空表霎迫；

要取得第i個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)順鏈進(jìn)行尋找,所以單鏈表是順序存取的存取結(jié)構(gòu)。

查找算法：

• 按序號(hào)查找第i個(gè)元素帘靡，時(shí)間復(fù)雜度為O(n);
• 按值查找值為e的元素知给，時(shí)間復(fù)雜度為O(n);

插入算法：
將值為e的節(jié)點(diǎn)插入到第一個(gè)節(jié)點(diǎn)的位置上即ai-1和ai之間 - 找到ai-1節(jié)點(diǎn)，并有指針p指向該節(jié)點(diǎn)描姚；

• 生成新節(jié)點(diǎn)s涩赢；
• 設(shè)置新節(jié)點(diǎn)s的數(shù)據(jù)域設(shè)置為e，指針域設(shè)置為ai轩勘；
• 設(shè)置ai-1的指針域指向新節(jié)點(diǎn)s筒扒；
  時(shí)間復(fù)雜度為O（n），主要時(shí)間是查找ai-1

刪除算法： 時(shí)間復(fù)雜度為O（n）绊寻，主要時(shí)間在查找ai-1

單鏈表的創(chuàng)建：
鏈表從一個(gè)空表開(kāi)始花墩，動(dòng)態(tài)的不斷插入數(shù)據(jù)，形成鏈表澄步；

此時(shí)的根據(jù)節(jié)點(diǎn)的插入位置不同分為：前插法和后插法冰蘑；

• 前插法：通過(guò)將新節(jié)點(diǎn)逐個(gè)插入鏈表的頭部（頭節(jié)點(diǎn)之后），來(lái)創(chuàng)建鏈表村缸；
• 后插法：為了使新節(jié)點(diǎn)能夠插入到尾部祠肥，需要增加一個(gè)指針r指向鏈表的未節(jié)點(diǎn)，初始時(shí)r也指向頭節(jié)點(diǎn)梯皿。

前插法創(chuàng)建鏈表：前插法創(chuàng)建一個(gè)N個(gè)元素的值的鏈表仇箱，時(shí)間復(fù)雜度為O(n);
后插法創(chuàng)建鏈表：時(shí)間復(fù)雜度為O(n)；

4.2 循環(huán)鏈表
另一種鏈?zhǔn)酱鎯?chǔ)东羹，特點(diǎn)是表中的最后一個(gè)節(jié)點(diǎn)的指針剂桥，指向頭節(jié)點(diǎn)，整個(gè)鏈表的形式形成一個(gè)環(huán)百姓。從表中任意節(jié)點(diǎn)出發(fā)都可以找到其他節(jié)點(diǎn)渊额。
合并兩個(gè)循環(huán)鏈表時(shí)，只需要表1的尾->表2的第一個(gè)節(jié)點(diǎn)（釋放表2的頭節(jié)點(diǎn)）垒拢，表2的尾指針->表1的頭節(jié)點(diǎn)旬迹。

4.3 雙向鏈表
修改節(jié)點(diǎn)的結(jié)構(gòu)，之前的節(jié)點(diǎn)只有后繼指針求类，現(xiàn)在給節(jié)點(diǎn)添加上前驅(qū)指針
雙向鏈表的節(jié)點(diǎn)結(jié)構(gòu)：

雙向鏈表也有循環(huán)鏈表叫雙向循環(huán)鏈表

5.線性表的應(yīng)用

兩個(gè)線性表La和Lb: La長(zhǎng)度為m,Lb 的長(zhǎng)度為n奔垦；

1. 合并兩個(gè)線性表：

for(int i=0;i<Lb.length;i++){
    GetElem(Lb,i,e);
    if(LocateElem(La,e)){
        ListInsert(La,++La_len,e);
    }
}

假設(shè)GetElem和ListInsert與表長(zhǎng)無(wú)關(guān)，LocateElem執(zhí)行的時(shí)間與表長(zhǎng)成正比尸疆，則時(shí)間復(fù)雜度為O（m*n）

2. 有序表的合并：

public class MergeOrderedList {

    String TAG = "MergeOrderedList";
    //順序存儲(chǔ)結(jié)構(gòu)的兩個(gè)有序線性表
    int[] LA = {3, 5, 8, 11, 23};
    int[] LB = {1, 2, 5, 7, 11, 15, 20, 28};


    int[] LC = new int[LA.length + LB.length];//new 空表
    int len = LA.length > LB.length ? LB.length : LA.length;


    public void megre() {

        if (len <= 0) {
            return;
        }

        int pa = 0, pb = 0;
        int pa_last = LA.length - 1, pb_last = LB.length - 1;
        int pc = 0;

        while (pa <= pa_last && pb <= pb_last) {

            //依次取LA和LB中小的值到LC表中椿猎，知道一中一個(gè)表到最后一個(gè)元素
            if (LA[pa] < LB[pb]) {
                LC[pc] = LA[pa];
                pa++;
            } else if (LA[pa] > LB[pb]) {
                LC[pc] = LB[pb];
                pb++;
            }else{
                LC[pc] = LA[pa];
                pa++;
                pb++;
            }

            pc++;

        }

        while (pa <= pa_last) {
            LC[pc] = LA[pa];
            pc++;
            pa++;
        }

        while (pb <= pb_last) {
            LC[pc] = LB[pb];
            pc++;
            pb++;
        }

    }

    public void printLC() {

        if (LC.length <= 0) {
            return;
        }


        for (int i : LC) {
            Log.e(TAG, "i>>>>" + i);
        }

    }


}

調(diào)用

MergeOrderedList m = new MergeOrderedList();
m.megre();
m.printLC();

結(jié)果

image.png

時(shí)間復(fù)雜度O(mn）；
需要開(kāi)辟新的輔助空間寿弱，所以空間復(fù)雜度也為O（mn）犯眠；

3. 鏈?zhǔn)接行虮淼暮喜?br> 時(shí)間復(fù)雜度為O(m*n)；
   空間復(fù)雜度為O（1）症革；