線性表--鏈式存儲結構--單鏈表

一、定義

1.特點：

• 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以存在內存中未被占用的任意位置。
• 比起順序存儲結構每個數(shù)據(jù)元素只需要存儲一個位置就可以了?，F(xiàn)在鏈式存儲結構中，除了要存儲數(shù)據(jù)元素信息外，還要存儲它的后繼元素的存儲地址（指針）。
• 也就是說除了存儲其本身的信息外，還需存儲一個指示其直接后繼的存儲位置的信息。

2.定義：

• 我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱為指針或鏈。這兩部分信息組成數(shù)據(jù)元素稱為存儲映像，稱為結點(Node)。
• n個結點鏈接成一個鏈表，即為線性表(a1, a2, a3, …, an)的鏈式存儲結構。
• 因為此鏈表的每個結點中只包含一個指針域，所以叫做單鏈表。

單鏈表.png

我們把鏈表中的第一個結點的存儲位置叫做頭指針，最后一個結點指針為空(NULL)。

單鏈表結構.png

頭結點的數(shù)據(jù)域一般不存儲任何信息

3.頭指針與頭結點的異同

頭指針

• 頭指針是指鏈表指向第一個結點的指針，若鏈表有頭結點，則是指向頭結點的指針。
• 頭指針具有標識作用，所以常用頭指針冠以鏈表的名字（指針變量的名字）。
• 無論鏈表是否為空，頭指針均不為空。
• 頭指針是鏈表的必要元素。

頭結點

• 頭結點是為了操作的統(tǒng)一和方便而設立的，放在第一個元素的結點之前，其數(shù)據(jù)域一般無意義（但也可以用來存放鏈表的長度）。
• 有了頭結點，對在第一元素結點前插入結點和刪除第一結點起操作與其它結點的操作就統(tǒng)一了。
• 頭結點不一定是鏈表的必須要素。

二、單鏈表存儲結構

單鏈表圖例.jpg

空鏈表圖例.jpg

C語言中可以用結構指針來描述單鏈表：

typedef struct Node
{
    ElemType data;      // 數(shù)據(jù)域
    struct Node* Next;  // 指針域
} Node;
    typedef struct Node* LinkList;

結點由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結點地址的指針域組成。

例1：假設p是指向線性表第i個元素的指針，則該結點ai的數(shù)據(jù)域我們可以用p->data的值是一個數(shù)據(jù)元素，結點ai的指針域可以用p->next來表示，p->next的值是一個指針。

那么p->next指向第i+1個元素。也就是指向ai+1的指針。

例2：如果p->data = ai，那么p->next->data = ?
p->next->data = ai+1。

三、單鏈表的操作--讀取、插入和刪除

1.讀取

對于單鏈表實現(xiàn)獲取第i個元素的數(shù)據(jù)的操作GetElem，在算法上相對要麻煩一些：

獲得鏈表第i個數(shù)據(jù)的算法思路：

1. 聲明一個結點p指向鏈表第一個結點，初始化j從1開始；
2. 當j<i時，就遍歷鏈表，讓p的指針向后移動，不斷指向一下結點，j+1；
3. 若到鏈表末尾p為空，則說明第i個元素不存在；
4. 否則查找成功，返回結點p的數(shù)據(jù)。

使用代碼實現(xiàn)GetElem.c：

/* 初始條件：順序線性表L已存在，1<=i<=ListLength(L) */
/* 操作結果：用e返回L中第i個數(shù)據(jù)元素的值 */

Status GetElem( LinkList L, int i, ElemType *e )
{
    int j;
    LinkList p;

    p = L->next;
    j = 1;

    while( p && j<i )
    {
        p = p->next;
        ++j;
    }

    if( !p || j>i )
    {
        return ERROR;
    }

    *e = p->data;

    return OK;
}

就是從頭開始找，直到第i個元素為止：

• 由于這個算法的時間復雜度取決于i的位置，當i=1時，則不需要遍歷，而i=n時則遍歷n-1次才可以。因此最壞情況的時間復雜度為O(n)。
• 由于單鏈表的結構中沒有定義表長，所以不能實現(xiàn)知道要循環(huán)多少次，因此也就不方便使用for來控制循環(huán)。
• 其核心思想叫做“工作指針后移”，這其實也是很多算法的常用技術。

2.插入

單鏈表的插入：假設存儲元素e的結點為s，要實現(xiàn)結點p、p->next和s之間邏輯關系的變化，如圖：

結點之間的邏輯關系.jpg

要將結點s插入到ai和ai+1之間，只需要讓s->next和p->next的指針做一點改變。
s->next = p->next;
p->next = s;
如圖：

插入操作.jpg

這兩句代碼的順序可不可以交換過來？
先p->next = s;
再s->next = p->next;

如果先執(zhí)行p->next的話會先被覆蓋為s的地址，那么s->next = p->next其實就等于s->next = s了。

所以這兩句是無論如何不能弄反的。

單鏈表第i個數(shù)據(jù)插入結點的算法思路：

1. 聲明一結點p指向鏈表頭結點，初始化j從1開始；
2. 當j<1時，就遍歷鏈表，讓p的指針向后移動，不斷指向下一結點，j累加1；
3. 若到鏈表末尾p為空，則說明第i個元素不存在；
4. 否則查找成功，在系統(tǒng)中生成一個空結點s；
5. 將數(shù)據(jù)元素e賦值給s->data；
6. 單鏈表的插入剛才兩個標準語句；
7. 返回成功。

代碼實現(xiàn)：

/* 初始條件：順序線性表L已存在，1<=i<=ListLength(L) */
/* 操作結果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L的長度加1 */

Status ListInsert(LinkList *L, int i, ElemType e)
{
    int j;
    LinkList p, s;

    p = *L;
    j = 1;

    while( p && j<i )   // 用于尋找第i個結點
    {
        p = p->next;
        j++;
    }

    if( !p || j>i )
    {
        return ERROR;
    }

    s = (LinkList)malloc(sizeof(Node));
    s->data = e;

    s->next = p->next;
    p->next = s;

    return OK;
}

3.刪除

單鏈表的刪除.png

假設元素a2的結點為q，要實現(xiàn)結點q刪除單鏈表的操作，其實就是將它的前繼結點的指針繞過指向后繼結點即可。

那我們所要做的，實際上就是一步：

可以這樣：p->next = p->next->next;
也可以是：q=p->next; p->next=q->next;

單鏈表第i個數(shù)據(jù)刪除結點的算法思路：

1. 聲明結點p指向鏈表第一個結點，初始化j=1；
2. 當j<1時，就遍歷鏈表，讓P的指針向后移動，不斷指向下一個結點，j累加1；
3. 若到鏈表末尾p為空，則說明第i個元素不存在；
4. 否則查找成功，將欲刪除結點p->next賦值給q；
5. 單鏈表的刪除標準語句p->next = q->next；
6. 將q結點中的數(shù)據(jù)賦值給e，作為返回；
7. 釋放q結點。

代碼實現(xiàn)：

/* 初始條件：順序線性表L已存在，1<=i<=ListLength(L) */
/* 操作結果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度-1 */

Status ListDelete(LinkList *L, int i, ElemType *e)
{
    int j;
    LinkList p, q;

    p = *L;
    j = 1;

    while( p->next && j<i )
    {
        p = p->next;
        ++j;
    }

    if( !(p->next) || j>i )
    {
        return ERROR;
    }

    q = p->next;
    p->next = q->next;

    *e = q->data;
    free(q);

    return OK;
}

效率問題：

無論是單鏈表插入還是刪除算法，它們其實都是由兩個部分組成：

第一部分就是遍歷查找第i個元素，
第二部分就是實現(xiàn)插入和刪除元素。

它們的時間復雜度都是O(n)。

• 如果在我們不知道第i個元素的指針位置，單鏈表數(shù)據(jù)結構在插入和刪除操作上，與線性表的順序存儲結構是沒有太大優(yōu)勢的。
• 但如果，我們希望從第i個位置開始，插入連續(xù)10個元素，對于順序存儲結構意味著，每一次插入都需要移動n-i個位置，所以每次都是O(n)。
• 而單鏈表，我們只需要在第一次時，找到第i個位置的指針，此時為O(n)，接下來只是簡單地通過賦值移動指針而已，時間復雜度都是O(1)。
• 顯然，對于插入或刪除數(shù)據(jù)越頻繁的操作，單鏈表的效率優(yōu)勢就越是明顯

四、單鏈表的整表創(chuàng)建

單鏈表的存儲結構，它的數(shù)據(jù)可以是分散在內存各個角落的，他的增長也是動態(tài)的。對于每個鏈表來說，它所占用空間的大小和位置是不需要預先分配劃定的，可以根據(jù)系統(tǒng)的情況和實際的需求即時生成。

單鏈表的整表創(chuàng)建：
創(chuàng)建單鏈表的過程是一個動態(tài)生成鏈表的過程，從“空表”的初始狀態(tài)起，依次建立各元素結點并逐個插入鏈表。

單鏈表整表創(chuàng)建的算法思路如下：

1. 聲明一結點p和計數(shù)器變量i；
2. 初始化一空鏈表L；
3. 讓L的頭結點的指針指向NULL，即建立一個帶頭結點的單鏈表；
4. 循環(huán)實現(xiàn)后繼結點的賦值和插入。

①頭插法建立單鏈表
頭插法從一個空表開始，生成新結點，讀取數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表頭上，直到結束為止。
就是把新加進的元素放在表頭后的第一個位置：

1. 先讓新節(jié)點的next指向頭節(jié)點之后
2. 然后讓表頭的next指向新節(jié)點

代碼實現(xiàn)：

/* 頭插法建立單鏈表示例 */

void CreateListHead(LinkList *L, int n)
{
    LinkList p;
    int i;

    srand(time(0));   // 初始化隨機數(shù)種子

    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;

    for( i=0; i < n; i++ )
    {
        p = (LinkList)malloc(sizeof(Node));  // 生成新結點
        p->data = rand()%100+1;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

頭插法演示.png

②尾插法建立單鏈表
頭插法建立鏈表雖然算法簡單，但生成的鏈表中結點的次序和輸入的順序相反。
我們可以把思維逆過來：把新結點都插入到最后，這種算法稱之為尾插法。

尾插法演示.png

代碼實現(xiàn)：

/* 尾插法建立單鏈表演示 */

void CreateListTail(LinkList *L, int n)
{
    LinkList p, r;
    int i;

    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    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，下一結點賦值給q；
3. 循環(huán)執(zhí)行釋放p和將q賦值給p的操作；

代碼實現(xiàn)：

Status ClearList(LinkList *L)
{
    LinkList p, q;

    p = (*L)->next;

    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }

    (*L)->next = NULL;

    return OK;
}

這段算法代碼里，常見的錯誤就是有同學會覺得q變量沒有存在的必要，只需要在循環(huán)體內直接寫free(p); p = p->next; 即可？
p是一個結點，它除了有數(shù)據(jù)域，還有指針域。當我們做free(p);時，其實是對它整個結點進行刪除和內存釋放的工作。而我們整表刪除是需要一個個結點刪除的，所以我們就需要q來記載p的下一個結點。

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

分別從存儲分配方式、時間性能、空間性能三方面來做對比：

1.存儲分配方式：

• 順序存儲結構用一段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。
• 單鏈表采用鏈式存儲結構，用一組任意的存儲單元存放線性表的元素。

2.時間性能：

查找：

• 順序存儲結構O(1)
• 單鏈表O(n)

插入和刪除：

• 順序存儲結構需要平均移動表長一半的元素，時間為O(n)
• 單鏈表在計算出某位置的指針后，插入和刪除時間僅為O(1)

3.空間性能：

• 順序存儲結構需要預分配存儲空間，分大了，容易造成空間浪費，分小了，容易發(fā)生溢出。
• 單鏈表不需要分配存儲空間，只要有就可以分配，元素個數(shù)也不受限制。

結論：

• 若線性表需要頻繁查找，很少進行插入和刪除操作時，宜采用順序存儲結構。
• 若需要頻繁插入和刪除時，宜采用單鏈表結構。
• 比如說游戲開發(fā)中，對于用戶注冊的個人信息，除了注冊時插入數(shù)據(jù)外，絕大多數(shù)情況都是讀取，所以應該考慮用順序存儲結構。
• 而游戲中的玩家的武器或者裝備列表，隨著玩家的游戲過程中，可能會隨時增加或刪除，此時再用順序存儲就不太合適了，單鏈表結構就可以大展拳腳了。
• 當線性表中的元素個數(shù)變化較大或者根本不知道有多大時，最好用單鏈表結構，這樣可以不需要考慮存儲空間的大小問題。
• 而如果事先知道線性表的大致長度，比如一年12個月，一周就是星期一至星期日共七天，這種用順序存儲結構效率會高很多。

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