單鏈表的讀取、插入與刪除

  鏈表是由一個個結點構成，而每一個結點都是由存儲數據的數據域以及存儲下一個結點地址的地址域兩部分構成。

  鏈表的一大優點就是，可以在任意兩個數之間毫無限制的插入無限多的數據。在很多時候，我們都需要對數據做個查找工作，就比如，一個班的同學去上課，結果老師發現人數不對，于是就開始點名，點到后來發現某某某同學沒有到，這就是典型的數據查找。那么如何實現對鏈表的數據元素的查找呢？

比如，我想知道鏈表的第5個元素的值是多少，我應該怎么做呢？由于，鏈表是依靠地址來查找數據的，那比如說鏈表的第一個結點的數據域中保存了某一個元素值，而它的地址域中則保存了下個結點的地址，也就是說，每一個結點的地址都被保存在上一個結點的地址域中。那么，很明顯，第5個元素的地址被保存在了第4個元素的地址域中，那么，也就是說，我想知道第5個元素在哪個位置，我首先得知道第四個元素在什么位置，那么以此類推，就需要知道第1個元素的存儲位置，也就是說，我想要知道第5個元素的存儲的位置，我首先就得從鏈表的頭部開始查找。那么，我想知道鏈表的第i個元素的位置，我還是得從表頭開始查起。很明顯，想要知道第i個元素的位置，就需要申明一個循環變量j以及一個指針變量p來遍歷鏈表。

  當然，想要查找鏈表的元素，前提還得是鏈表不能為空，如果為空，那元素怎么可能查得到。這就好比，一個班的同學都沒去上課，那老師還用的著點名嗎，根本就沒有點名的必要性了。

那么，查找單鏈表的一個元素，代碼如下：

Status GetElem ( LinkList L, int i, ElemType e *e )
{
    int j;
    LinkList p;
    
    j = 1;
    p = L->next;
    while ( p != NULL && j < i ){
        
        p = p->next;   //p指向下一個結點
        ++j;
    
    }
    
    if ( p == NULL || j > i )
    return ERROR;
    
    *e = p->data;

}

  接下來，就是關于單鏈表的元素插入了。假設，一個鏈表有5個元素，也就是它有1~5這五個結點，那么我想在第4個結點之前插入一個新的元素，那我該怎么做呢？也就是說，這個元素我會插入在第3和第4個元素之間。很明顯的一點就是，第4個結點的地址保存在第3個結點的后繼指針中，那么，我想插入這個結點s，那豈不是我首先要把第4個結點的地址保存下來，也就是說我首先要向第3個結點索要第4個結點的地址，然后，再把s的地址給第3個結點p。

代碼如下：

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

  因為，之前我們是假設有5個元素，并且是假設在第4個元素之前插入數據，那假設我要在第6個元素之前插入數據，那么怎么辦呢？很多人就說了，這不可能的，因為，一共就5個數據，你怎么插入在第6個元素之前，你這不是扯淡嗎。沒錯，但是，程序并不知道，如果，我們從鍵盤輸入的是第6個數據，那么，毫無疑問的程序就會出現bug。所以，我們在做元素的插入之前，我們的判斷插入的位置合不合理。如果不合理，那么我們就返回一個ERROR值。代碼如下：

Status ListInsert ( LinkList *L, int i, ElemType e )
{
    int j;
    LinkList p;
    
    p = *L;
    j = 1;
    while ( p != NULL && j < i ){
    
        p = p->next;
        ++j;
    }
    
    if ( p == NULL || j > i )
    return ERROR;
    
    s = ( LinkList ) malloc ( sizeof ( struct Node ) );  //動態申請一個結點
    s->data = e;
    s->next = p->next;
    p->next = s;
    
    return OK;

}

  最后，就是單鏈表元素的刪除操作。與元素的插入操作類似，我們在刪除之前要判斷它刪除點是否有問題，如果刪除點有問題，那么就返回一個ERROR。

  那么，我們應該如何刪除一個結點元素呢？假設我們仍然有5個結點元素，現在我們想要刪除第3個結點的元素。那么我們應該如何做呢？首先，我們很清楚的是，第3個結點的后繼指針中保存著第4個結點的地址，如果，刪除第3個結點，那么豈不是第4個結點的地址也跟著丟失了，那豈不是這根鏈表就斷開來了。所以，在刪除第3個結點之前，就得把第3個結點的后繼指針中的值保存下來。然后，將第3個結點的地址保存在第2個結點的后繼指針中。代碼如下：

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

其實，以上兩條語句可以用一條語句來代替，

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

  最后，刪除了結點之后，還得釋放該結點。

代碼如下：

Status ListDelete ( LinkList *L, int i, ElemType *e )
{
    int j;
    LinkList p;
    LinkList q;
    
    p = *L;
    j = 1;
    while ( p != NULL && j < i ){
        
        p = p->next;
        ++j;
    }
    
    if ( p == NULL || j > i )
    return EEROR;
    
    q = p->next;
    p->next = q->next;
    
    free ( q );
    
    return OK;

}

到這里，基本上，對單鏈表的插入，刪除，以及元素的獲取就差不多了。事實上，對單鏈表的操作并不復雜，只要，對幾個關鍵數據進行預先判別，那么，出現bug的幾率就會降低很多。