原文出自：http://www.reibang.com/p/94fc4be7d61e

你還在為開發(fā)中頻繁切換環(huán)境打包而煩惱嗎箫攀？快來試試 Environment Switcher 吧兔簇！使用它可以在app運行時一鍵切換環(huán)境险毁，而且還支持其他貼心小功能允趟，有了它媽媽再也不用擔心頻繁環(huán)境切換了指攒。https://github.com/CodeXiaoMai/EnvironmentSwitcher

上一章：程序猿必修課之數據結構（三）線性表1

上篇我們復習的線性表的順序存儲結構足删，它的最大缺點就是：插入和刪除是需要移動大量元素掖看，造成時間的浪費眨层。

導致這個問題的原因是庙楚，相鄰兩個元素的存儲位置也具有鄰居關系，也就是說它們在內存中是挨著的趴樱，中間沒有空隙馒闷，當然就無法快速插入，而刪除后叁征，當中就會留出空隙窜司，自然需要彌補。鏈式存儲就是為了解決這個問題而產生的航揉。

線性表鏈式存儲結構定義

線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素塞祈，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的帅涂。這就意味著议薪，這些元素可以存在內存未被占用的任意位置。

在順序結構中媳友，每個數據元素只需要存儲數據元素信息就可以了∷挂椋現(xiàn)在鏈式結構中，除了要存數據元素信息外醇锚，還要存儲它的后繼元素的存儲地址哼御。

為了表示每個元素 Ai 與其直接后繼元素 A(i+1) 之間的邏輯關系，對數據元素 Ai 來說焊唬，除了存儲其本身的信息外恋昼，還需要存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。我們把存儲數據元素信息的域稱為數據域赶促，把存儲直接后繼位置的域稱為指針域液肌。指針域中存儲的信息叫做指針或鏈。這兩部分信息組成數據元素 Ai 的存儲映像鸥滨，稱為結點（Node)嗦哆。

n 個結點鏈接成一個鏈表谤祖，即為線性表的鏈式存儲結構，因為此鏈表的每個結點中只包含一個指針域老速，所以叫做單鏈表粥喜。

鏈表中第一個結點的存儲位置叫做頭指針。

為了方便對鏈表進行操作橘券，會在單鏈表的第一個結點前附加一個結點额湘，稱為頭結點。頭結點的數據域可以不存儲任何信息约郁，也可以存儲線性表的長度等附加信息，頭結點的指針域存儲指向第一個結點的指針但两。

頭指針與頭結點的異同

頭指針：

• 頭指針是指鏈表指向第一個結點的指針鬓梅，若鏈表有頭結點，則是指向頭結點的指針谨湘。
• 頭指針具有標識作用绽快，所以常用頭指針冠以鏈表的名字。
• 無論鏈表是否為空紧阔，頭指針均不為空坊罢。頭指針是鏈表的必要元素。

頭結點：

• 頭結點是為了操作的統(tǒng)一和方便而設立的擅耽，放在第一個元素的結點之前活孩，其數據域一般無意義（也可存放鏈表的長度）。
• 有了頭結點乖仇，對在第一個元素結點前插入結點或刪除第一個結點憾儒，其操作與其它結點的操作就統(tǒng)一了。
• 頭結點不一定是鏈表必須元素乃沙。

線性表鏈式存儲結構代碼描述

typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *LinkList;

單鏈表的讀取

在線性表的順序儲存結構中起趾，我們要計算任意一個元素的存儲位置是很容易的。但是在單鏈表中警儒，由于第 i 個元素到底在哪训裆，一開始不知道，必須從頭開始找蜀铲。

獲取單鏈表第 i 個數據的算法步驟

1. 聲明一個結點 p 指向鏈表第一個結點边琉，初始化 j 從 1 開始；
2. 當 j < i 時记劝，就遍歷鏈表艺骂，讓 p 的指針向后移動，不斷指向下一結點隆夯， j 累加 1钳恕；
3. 若到鏈表末尾 p 為空别伏，則說明第 i 個元素不存在；
4. 否則查找成功忧额，返回結點 p 的數據厘肮。

代碼如下：

ElemType GetElem (LinkList L, int i) {
    int j;
    LinkList p;
    p = L->next;
    j = 1;
    while (NULL != p && j < i) {
        p = p->next;
        ++j;
    }
    if (!p || j > i)
        return Error;
    return p->data;
}

由于這個算法的時間復雜度取決于 i 的位置，當 i = 1 時睦番，則不需遍歷类茂，而當 i = n 時則遍歷 n - 1次才可以，因此最壞情況的復雜度為O(n)托嚣。

單鏈表的插入

單鏈表第 i 個位置插入結點的算法步驟：

1. 聲明一個結點 p 指向鏈表第一個結點巩检，初始化 j 從 1 開始；
2. 當 j < i 時示启，就遍歷鏈表兢哭，讓 p 的指針向后移動，不斷指向下一個結點夫嗓， j 累加 1迟螺；
3. 若到鏈表末尾 p 為空，則說明第 i 個位置不存在舍咖；
4. 否則查找成功矩父，創(chuàng)建一個空結點 s；
5. 將數據元素賦值給 s->data;
6. 單鏈表的插入標準語句 s->next = p->next; p->next = s;
7. 返回成功排霉。

代碼如下：

bool ListInsert (LinkList *L, int i, ElemType e) {
    int j;
    LinkList p, s;
    p = *L;
    j = 1;
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    if (!p || j > i)
        return false;
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

單鏈表刪除第 i 個結點的算法步驟：

1. 聲明一個結點 p 指向鏈表第一個結點窍株，初始化 j 從 1 開始；
2. 當 j < i 時攻柠，就遍歷鏈表夹姥，讓 p 的指針向后移動，不斷指向下一個結點辙诞， j 累加 1辙售；
3. 若到鏈表末尾 p 為空，則說明第 i 個結點不存在飞涂；
4. 否則查找成功旦部，將要刪除的結點 p->next 賦值給 q；
5. 單鏈表的刪除標準語句 p->next = q->next;
6. 將 q 結點的數據賦值給 e较店，作為返回士八；
7. 釋放 q 結點；
8. 返回成功梁呈。

代碼如下：

bool ListDelete (LinkList *L, int i, ElemType *e) {
    LinkedList p, q;
    int j;
    p = *L;
    j = 1;
    while (p->next && j < i) {
        p = p->next;
        j++;
    }
    if (!(p->next) || j > i)
        return false;
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return true;
}

對于插入或刪除數據越頻繁的操作婚度，單鏈表的效率比順序存儲結構要高。

單鏈表的創(chuàng)建

我們已經知道官卡，順序存儲結構的創(chuàng)建蝗茁，其實就是一個數組的初始化醋虏，即聲明一個類型和大小的數組并賦值的過程。而單鏈表和順序存儲結構不一樣哮翘，它不像順序存儲結構這么集中颈嚼，可以很散，是一種動態(tài)結構饭寺。對于每個鏈表來說阻课，它所占用空間的大小和位置是不需要預先分配劃定的，可以根據系統(tǒng)的情況和實際的需求即時生成艰匙。

所以創(chuàng)建單鏈表的過程就是一個動態(tài)生成鏈表的過程限煞，即從“空表”的初始狀態(tài)，依次建立各元素結點员凝，并逐個插入鏈表署驻。

創(chuàng)建單鏈表整表的步驟（頭插法）：

1. 聲明一個結點 p 和計數器變量 i；
2. 初始化一個空鏈表 L绊序；
3. 讓 L 的頭結點的指針指向 NULL硕舆，即建立一個帶頭結點的單鏈表秽荞；
4. 循環(huán)：
   1. 生成一個新結點賦值給 p骤公；
   2. 將值賦值給 p的數據域 p->data;
   3. 將 p 插入到頭結構與前一新結點之間。

代碼如下：

void createList(LinkList *L, int n) {
    LinkList p;
    int i;
    /* 初始化隨機數種子 */
    srand (time(0));
    *L = (LinkList)malloc(sizeof(Node));
    /* 創(chuàng)建一個帶頭結點的單鏈表 */
    (*L)->next = NULL;
    for (i = 0; i < n; i++) {
        p = (LinkList)malloc(sizeof(Node));
        /* 隨機生成100以內的數字 */
        p->data = rand() % 100 + 1;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

尾插法：

void createList(LinkList *L, int n) {
    LinkList p, r;
    int i;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    /* 指向尾結點的結點 */
    r = *L;
    for (i = 0; i < n; i++) {
        p = (Node *)malloc(sizeof(Node));
        p->data = rand() % 100 + 1;
        /* 將表尾結點的指針指向新結點 */
        r->next = p;
        /* 將當前的新結點定義為尾結點 */
        r = p;
    }
    r->next = NULL;
}

單鏈表的整表刪除

單鏈表整表刪除的步驟：

1. 聲明一個結點 p 和 q扬跋；
2. 將第一個結點賦值給 p阶捆；
3. 循環(huán)：
   1. 將下一個結點賦值給 q；
   2. 釋放 p钦听；
   3. 將 q 賦值給 p洒试。

代碼如下：

bool clearList(LinkList *L) {
    LinkList p, q;
    /* p指向第一個結點 */
    p = (*L)->next;
    while(p) {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return true;
}

單鏈表結構與順序存儲結構優(yōu)缺點

總結

• 若線性表需要頻繁查找叼架，很少進行插入和刪除操作時，宜采用順序存儲結構衣撬。若需要頻繁插入和刪除時乖订，宜采用單鏈表結構。
• 當線性表中的元素個數變化較大或者根本不知道有多大時具练，最好用單鏈表結構乍构，這樣可以不需要考慮存儲空間的大小問題。

總之扛点，線性表的順序存儲結構和單鏈表結構各有優(yōu)缺點哥遮，不能簡單的說哪個好岂丘，哪個不好，需要根據實際情況綜合平衡采用哪種數據結構更能滿足和達到需求昔善。

下一章：程序猿必修課之數據結構（五）線性表3