單向鏈表(C++)

Node節(jié)點(diǎn)定義：

class IntSLLNode {
public:
    IntSLLNode() {
        next = 0;
    }

    IntSLLNode(int val, IntSLLNode *in = 0) {
        info = val;
        next = in;
    }

    int info;
    IntSLLNode *next;
};

這里有個(gè)地方，帶參數(shù)的構(gòu)造函數(shù)中的第二個(gè)參數(shù)是個(gè)小細(xì)節(jié)婶溯，在后面管理鏈表的InSLList類(lèi)中，addToHead里面，通過(guò)這個(gè)參數(shù)來(lái)連接節(jié)點(diǎn)主胧，從而使每次new出來(lái)的節(jié)點(diǎn)都是頭節(jié)點(diǎn)。

接下來(lái)就是構(gòu)造用來(lái)管理鏈表的管理類(lèi)习勤，增加頭結(jié)點(diǎn)踪栋，增加尾節(jié)點(diǎn)等等功能,這里我們起名為IntSLList，剛才提到過(guò)：

#include "IntSLLNode.h"

class IntSLList {
public:
    IntSLList() {
        head = tail = 0;
    }

    ~IntSLList();
    int isEmpty() {
        return head == 0;
    }

    void addToHead(int);
    void addToTail(int);
    int deleteFromHead();
    int deleteFromTail();
    void deleteNode(int);

    bool isInList(int) const;

private:
    IntSLLNode *head, *tail;
};

接下來(lái)實(shí)現(xiàn)這個(gè)類(lèi)中的每個(gè)函數(shù)的功能
1图毕、addToHead(int):

void IntSLList::addToHead(int val) {
    head = new IntSLLNode(val, head);
    if (tail == 0) {
        tail = head;
    }
}

這個(gè)函數(shù)很簡(jiǎn)單夷都，主要就是構(gòu)建頭節(jié)點(diǎn)和判斷頭節(jié)點(diǎn)是否相同，如果相同就是指向同一個(gè)節(jié)點(diǎn)予颤。其中head每次都是最新的頭節(jié)點(diǎn)囤官，這個(gè)地方剛才上面有所提到，不再描述蛤虐。接下來(lái)我們來(lái)看addToTail這個(gè)函數(shù)
2党饮、addToTail(int)：

void IntSLList::addToTail(int val) {
    if (tail != 0) {
        tail->next = new IntSLLNode(val);
        tail = tail->next;
    } else
        head = tail = new IntSLLNode(val);
}

這個(gè)函數(shù)也很簡(jiǎn)單，主要就是兩個(gè)思路驳庭，第一個(gè)判斷當(dāng)前鏈表里面有沒(méi)有節(jié)點(diǎn)刑顺，如果有直接創(chuàng)建一個(gè)新的，并賦值給tail->next饲常，然后再講next賦值給tail更新一下節(jié)點(diǎn)就好了蹲堂。如果當(dāng)前鏈表里面沒(méi)有節(jié)點(diǎn)，那就讓head和tail同時(shí)指向新節(jié)點(diǎn)即可贝淤。

以上就是添加節(jié)點(diǎn)的兩個(gè)函數(shù)柒竞，下面來(lái)看看刪除節(jié)點(diǎn)的三個(gè)函數(shù)：
1、deleteFromHead():

int IntSLList::deleteFromHead() {
    int val = head->info;
    IntSLLNode* temp = head;
    if (head == tail) {
        head = tail = 0;
    } else
        head = head->next;

    delete temp;
    return val;
}

函數(shù)返回值為Int霹娄，代表著你刪除頭節(jié)點(diǎn)存儲(chǔ)的val值是多少能犯，這么設(shè)計(jì)主要是為了當(dāng)節(jié)點(diǎn)要?jiǎng)h除時(shí)鲫骗，但是一時(shí)間還有用，就將val返回用來(lái)處理外部邏輯踩晶，然后進(jìn)入函數(shù)中之后执泰，用一個(gè)臨時(shí)int變量把要?jiǎng)h除的head存儲(chǔ)的值存儲(chǔ)起來(lái)用來(lái)返回，再用一個(gè)臨時(shí)指針保存當(dāng)前頭結(jié)點(diǎn)渡蜻，其次判斷當(dāng)前頭結(jié)點(diǎn)和尾節(jié)點(diǎn)是否相同术吝，如果相同，先將這兩個(gè)指針指向null茸苇，然后刪除排苍，如果不相等，先將當(dāng)前頭結(jié)點(diǎn)的下個(gè)結(jié)點(diǎn)賦值給當(dāng)前頭指針学密，讓這個(gè)結(jié)點(diǎn)成為新的節(jié)點(diǎn)淘衙，然后再把保存的節(jié)點(diǎn)刪除，然后被刪除頭結(jié)點(diǎn)的值腻暮。
刪除完了頭結(jié)點(diǎn)我們來(lái)看一下刪除尾節(jié)點(diǎn)彤守，刪除尾節(jié)點(diǎn)代碼稍微多一些。
2哭靖、deleteFromTail():

int IntSLList::deleteFromTail() {
    int val = tail->info;
    if (head == tail) {
       delete head;
       head = tail = 0;
    } else {
        IntSLLNode *temp;
        for (temp = head; temp->next != tail; temp = temp->next);
        delete tail;
        tail = temp;
        tail->next = 0;
    }

    return val;
}

跟刪除頭結(jié)點(diǎn)一樣具垫，先用一個(gè)int的臨時(shí)變量保存要?jiǎng)h除尾節(jié)點(diǎn)存儲(chǔ)的值，用于返回试幽，接下來(lái)判斷頭指針和尾指針是不是指向同一個(gè)節(jié)點(diǎn)筝蚕，如果是的話，將tail節(jié)點(diǎn)刪除铺坞，然后將兩個(gè)指針都指向null起宽，如果不是，聲明一個(gè)臨時(shí)節(jié)點(diǎn)指針康震，然后for循環(huán)查找尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)并讓臨時(shí)節(jié)點(diǎn)指針指向這個(gè)節(jié)點(diǎn)燎含，刪除tail尾幾點(diǎn)，然后并重新更新tail腿短，讓tail=tmp，更新完之后绘梦，讓這個(gè)新尾尾節(jié)點(diǎn)的next指向null橘忱。
下面我們來(lái)看看最后一個(gè)刪除函數(shù)
3、deleteNode(int)：

void IntSLList::deleteNode(int val) {
    if (head != 0) {
        if (head == tail) {
            delete head;
            head = tail = 0;
        } else if(val == head->info) {
            IntSLLNode *temp = head;
            head = head->next;
            delete temp;
        } else {
            IntSLLNode *pred, *tmp;
            for (pred = head, tmp = head->next; tmp != 0 && !(tmp->info == val);pred=pred->next, tmp=tmp->next);
            if (tmp != 0) {
                pred->next = tmp->next;
                if (tmp == tail) {
                    tail = pred;
                }
                delete tmp;
            }
        }

    }
}

先判斷當(dāng)前鏈表里面是否有節(jié)點(diǎn)卸奉，如果沒(méi)有就不做任何處理钝诚，如果有，有三種情況需要處理榄棵，第一種是不是只有一個(gè)節(jié)點(diǎn)凝颇，如果是的話潘拱，刪除節(jié)點(diǎn)，然后將head和tail指針指向null拧略，第二種情況芦岂，要?jiǎng)h除的節(jié)點(diǎn)剛好是頭結(jié)點(diǎn)，方法跟以前一樣垫蛆，用一根臨時(shí)節(jié)點(diǎn)指針保存當(dāng)前頭結(jié)點(diǎn)禽最，然后將head指針指向下一個(gè)節(jié)點(diǎn)，然后刪除剛才保存的節(jié)點(diǎn)袱饭，這樣就刪除掉了川无，第三種情況，如果要?jiǎng)h除節(jié)點(diǎn)不符合上述兩種情況虑乖，就代表刪除鏈表其中某個(gè)一個(gè)節(jié)點(diǎn)懦趋，我們用兩個(gè)節(jié)點(diǎn)指針來(lái)操作，一個(gè)是pred疹味，一個(gè)是tmp愕够，為什么要聲明兩個(gè)節(jié)點(diǎn)指針，我們一會(huì)再討論佛猛，第一個(gè)思路惑芭，用tmp找出要?jiǎng)h除節(jié)點(diǎn)的位置，當(dāng)找到了之后并且節(jié)點(diǎn)指針指向的不是null继找，現(xiàn)在將上一個(gè)節(jié)點(diǎn)的next更新到tmp的next遂跟，用來(lái)斷開(kāi)刪除的節(jié)點(diǎn)，然后判斷是否等于尾節(jié)點(diǎn)婴渡，如果是幻锁，這個(gè)時(shí)候pred就起到作用了，更新tail尾節(jié)點(diǎn)指針边臼，然后將tmp指向的節(jié)點(diǎn)刪除哄尔，如果不是，直接刪除tmp節(jié)點(diǎn)柠并。
根據(jù)上述分析岭接，鏈表的增刪的管理類(lèi)就完成了，改和查臼予，相對(duì)簡(jiǎn)單鸣戴，這里就不描述了，感興趣的可以自己研究一下