亚洲三级免费无码,国产91富婆在线观看91

劍指offer之C++語言實現(xiàn)鏈表（兩種刪除節(jié)點方式）

1 問題

用C++語言實現(xiàn)鏈表

2 代碼實現(xiàn)

    #include <iostream>
    #include <stdlib.h>

    using namespace std;

    class List
    {
    public:
        List();
        ~List();
        List* createNode(int value);//創(chuàng)建節(jié)點
        bool insertNode(List *node);//插入節(jié)點
        void printList();//打印節(jié)點
        bool deleteNode(List *node);//刪除節(jié)點不移動頭節(jié)點
        bool deleteNode1(List *node);//刪除節(jié)點移動頭節(jié)點
        int listSize();//長度
        void printNode();//打印但前的value
        void freeList();//釋放鏈表
    private:
        int value;
        List *head;
        List *next;
    };

    bool List::deleteNode(List *node)
    {
        if (node == NULL)
        {
            std:cout << "node is NULL" << std::endl;
            return false;
        }
        if (head == NULL)
        {
            std::cout << "head is NULL" << std::endl;
            return false;
        }
        //如果node等于head
        if (head == node)
        {
            head = head->next;
        }
        List *p = head;
        while (p->next != NULL)
        {
            if (p->next == node)
            {
                p->next = p->next->next;
                return true;
            }
            p = p->next;
        }
        return false;
    }

    bool List::deleteNode1(List *node)
    {
        if (node == NULL)
        {
            std:cout << "node is NULL" << std::endl;
            return false;
        }
        if (head == NULL)
        {
            std::cout << "head is NULL" << std::endl;
            return false;
        }
        //如果node等于head
        if (head == node)
        {
            head = head->next;
        }
        List *p = head;
        while (head->next != NULL)
        {
            if (head->next == node)
            {
                head->next = head->next->next;
                std::cout << "delete node success head->value" << head->value << std::endl;
                //這里要記得把頭節(jié)點的指針移動最后還原,這里的頭節(jié)點是保存在這個類里面,改變了就是改變了
                //如果這里是把head作為參數(shù)傳遞,最后head會被銷毀那么不需要移動頭指針
                head = p;
                return true;
            }
            //注意,這里由于head是成員變量,改變了就是改變了,所以需要最后重新指定
            head = head->next;
        }
        std::cout << "delete node fail head->value" << head->value << std::endl;
        //這里要記得把頭節(jié)點的指針移動最后還原,這里的頭節(jié)點是保存在這個類里面,改變了就是改變了
        //如果這里是把head作為參數(shù)傳遞,最后head會被銷毀那么不需要移動頭指針
        head = p;
        return false;
    }

    List::List()
    {
        value = 0;
        head = NULL;
        next = NULL;
    }

    List::~List()
    {
        delete head;
        delete next;
    }


    List* List::createNode(int value)
    {
        List *list = NULL;
        list = new List();
        if (list)
        {
            list->value = value;
            return list;
        }
        return NULL;
    }

    bool List::insertNode(List *node)
    {
        node->next = head;
        head = node;
        return true;
    }

    void List::printList()
    {    if (head == NULL)
        {
            std::cout << "head is NULL" << std::endl;
            return;
        }
        List *p = head;
        while (p != NULL)
        {
            std::cout << p->value << std::endl;
            p = p->next;
        }
        return;
    }

    void List::printNode()
    {
        std::cout << value << std::endl;
    }

    int List::listSize()
    {
        if (head == NULL)
        {
            std::cout << "head is NULL" << std::endl;
            return 0;
        }
        int len = 0;
        List *p = head;
        while (p != NULL)
        {
            p = p->next;
            ++len;
        }
        return len;
    }

    void List::freeList()
    {
        if (head == NULL)
        {
            std::cout << "head is NULL" << std::endl;
            return;
        }
        List *p;
        while (head != NULL)
        {
            p = head;
            head = head->next;
            free(p);
        }
    }

    int main()
    {
        List list;
        List *list1 = list.createNode(5);
        list.insertNode(list1);

        List *list2 = list.createNode(6);
        list.insertNode(list2);

        List *list3 = list.createNode(1);
        list.insertNode(list3);

        List *list4 = list.createNode(3);
        list.insertNode(list4);

        List *list5 = list.createNode(2);
        list.insertNode(list5);

        list.printList();

        std::cout << "list size is " << list.listSize() << std::endl;

        std::cout << "-----------開始刪除節(jié)點值為3的節(jié)點" << std::endl;

        list.deleteNode1(list4);
        list.printList();

        std::cout << "list size is " << list.listSize() << std::endl;

        list.freeList();

        list.printList();
        return 0;
    }

3 運行結(jié)果

    2
    3
    1
    6
    5
    list size is 5
    -----------開始刪除節(jié)點值為3的節(jié)點
    delete node success head->value2
    2
    1
    6
    5
    list size is 4
    head is NULL

4 總結(jié)

很明顯用C語言實現(xiàn)，我們習(xí)慣在外面搞個頭結(jié)點，然后用C++實現(xiàn)，我們直接在類的里面放一個head指針，然后我們在增加節(jié)點的時候我們會把head進行移動，放在最前面，所以后面的便利和刪除操作等最好是不要動head的位置了，因為head動了，下次便利就有問題，如果刪除函數(shù)移動了head，我們最后需要復(fù)原h(huán)ead

比如我們的頭指針盡量不要移動，我們可以用一個指針變量來保存這個head指針，然后我們移動保存的指針變量，同時把保存的指針變量在一些情況下改變下一個指向的指針，那么我們下次便利head也是生效的，這樣保證了頭指針不被污染

比如下面的例子

    #include <stdio.h>

    void change(char *a)
    {
        *(a + 1) = 's';
    }
    int main()
    {
        char value[10] = "chenyu";
        change(value);
        printf("value is %s\n", value);
        return 0;
    }


    #include <stdio.h>

    void change(char *a)
    {
        char *p = a;
        *(p + 1) = 's';
    }
    int main()
    {
        char value[10] = "chenyu";
        change(value);
        printf("value is %s\n", value);
        return 0;
    }

其實最后的結(jié)果都是一樣，csenyu

頭指針是指向這塊內(nèi)存的地址，如果我們用指針變量保存了，然后這個指針變量也指向了這里，用指針變量去操作后，然后頭指針也是指向這里，后面數(shù)據(jù)的指向也會改變

作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭或掃描下面二維碼
零基礎(chǔ)入門進階人工智能(鏈接)

在线午夜精品自拍小视频_无码av无码专区线_亚洲无码精品人妻_人人澡欧美一区

其他