快捷導(dǎo)航

C語言算法學(xué)習(xí)之雙向鏈表詳解

更新時間：2022年05月14日 10:34:08 作者：英雄哪里出來

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點(diǎn)中都有兩個指針，分別指向直接后繼和直接前驅(qū)。本文主要介紹了C語言算法中雙向鏈表的實(shí)現(xiàn)，需要的可以參考一下

一、練習(xí)題目

題目鏈接	難度
1472. 設(shè)計瀏覽器歷史記錄	★★★☆☆
430. 扁平化多級雙向鏈表	★★★☆☆
劍指 Offer II 028. 展平多級雙向鏈表	★★★☆☆
劍指 Offer 36. 二叉搜索樹與雙向鏈表	★★★★☆

二、算法思路

1、設(shè)計瀏覽器歷史記錄

1.這是一個模擬題；

2.初始化生成一個頭結(jié)點(diǎn)，記錄一個當(dāng)前結(jié)點(diǎn)；

3.向前和向后是兩個類似的過程，可以統(tǒng)一實(shí)現(xiàn)，注意一些邊界條件。

struct Node {
    string val;
    Node* prev;
    Node* next;
};

class BrowserHistory {
    Node * List, *Current;
public:
    BrowserHistory(string homepage) {
        List = new Node();
        List->prev = List->next = nullptr;
        List->val = homepage;

        Current = List;
    }
    
    void visit(string url) {
        Node *Next = Current->next;
        if(Next == nullptr) {
            Current->next = new Node();
            Current->next->next = nullptr;
            Current->next->prev = Current;
        }else {
            Node *tmp = Next->next;
            Next->next = nullptr;
            // free
            while(tmp) {
                Node *node = tmp->next;
                delete tmp;
                tmp = node;
            }
        }
        Current->next->val = url;
        Current = Current->next;
    }
    
    string back(int steps) {
        string str = Current->val;
        Node *pre;
        while(steps-- && Current) {
            pre = Current;
            Current = Current->prev;
            if(Current) str = Current->val;
        }
        if(nullptr == Current) Current = pre;
        return str;

    }
    
    string forward(int steps) {
        string str = Current->val;
        Node *pre;
        while(steps-- && Current) {
            pre = Current;
            Current = Current->next;
            if(Current) str = Current->val;
        }
        if(nullptr == Current) Current = pre;
        return str;
    }
};

2、扁平化多級雙向鏈表

1.利用一個遞歸函數(shù)last = dfs(now)，一旦遇到child域非空的結(jié)點(diǎn)，則遞歸計算clast = dfs(now->child)，返回值是遞歸展平后的最后一個結(jié)點(diǎn)，然后進(jìn)行雙向鏈表的鏈接操作。

2.例如，當(dāng)前有 child域的結(jié)點(diǎn)為now，它的下一個結(jié)點(diǎn)是next，遞歸計算以后得到展平的鏈表的最后一個結(jié)點(diǎn)為 clast，則有如下關(guān)系：

 now <---> now->child    ...    clast <---> next

3.根據(jù)以上關(guān)系調(diào)整雙向鏈表，注意不要忘記將child域置空。

4.當(dāng)遍歷到這個雙向鏈表的最后一個結(jié)點(diǎn)的時候，如果它有child域，則當(dāng)前鏈表的最后一個結(jié)點(diǎn)就是clast，否則就是它自己now；

class Solution {
    Node* dfs(Node* head) {
        Node *now = head;
        Node *last = nullptr;

        while(now) {
            Node *cLast;
            if(now->child) {
                cLast = dfs(now->child);
                Node *next = now->next;

                // now <--> cFirst   ... cLast <---> next;
                now->next = now->child;
                now->child = nullptr;
                now->next->prev = now;

                if(next) {
                    next->prev = cLast; 
                }
                cLast->next = next;
            }
            if(now->next == nullptr) {
                if(now->child) {
                    last = cLast;
                }else {
                    last = now;
                }
            }
            now = now->next;
        }
        return last;
    }
public:
    Node* flatten(Node* head) {
        if(head == nullptr) {
            return nullptr;
        }
        Node *last = dfs(head);
        last->next = nullptr;
        return head;
    }
};

3、展平多級雙向鏈表

（1）同上一題。

4、二叉搜索樹與雙向鏈表

（1）遇到這樣的題，首先需要設(shè)計好遞歸函數(shù)；

（2）像這個問題，對于左子樹和右子樹，需要知道雙向鏈表的頭結(jié)點(diǎn) 和尾結(jié)點(diǎn)，所以遞歸的時候需要返回兩個值，于是可以直接采用函數(shù)傳指針進(jìn)行返回，由于二叉樹的結(jié)點(diǎn)本身就是指針，所以需要傳二級指針；

（3）遞歸計算左子樹變成雙向鏈表的情況；

（4）遞歸計算右子樹變成雙向鏈表的情況；

（5）將左子樹的雙向鏈表鏈接到root左邊，將右子樹的雙向鏈表鏈接到root右邊，然后根據(jù)遞歸函數(shù)的實(shí)際作用，返回頭結(jié)點(diǎn) 和尾結(jié)點(diǎn)。

class Solution {
    void dfs(Node *root, Node **minNode, Node **maxNode) {
        if(root == nullptr) {
            *minNode = nullptr;
            *maxNode = nullptr;
            return ;
        }
        Node *lminNode, *lmaxNode, *rminNode, *rmaxNode;
        if(root->left) {
            dfs(root->left, &lminNode, &lmaxNode);
            lmaxNode->right = root;
            root->left = lmaxNode;
            *minNode = lminNode;
        }else {
            *minNode = root;
        }

        if(root->right) {
            dfs(root->right, &rminNode, &rmaxNode);
            rminNode->left = root;
            root->right = rminNode;
            *maxNode = rmaxNode;
        }else {
            *maxNode = root;
        }
    }
public:
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) {
            return nullptr;
        }
        Node *minNode, *maxNode;
        dfs(root, &minNode, &maxNode);
        maxNode->right = minNode;
        minNode->left = maxNode;
        return minNode;
    }
};

到此這篇關(guān)于C語言算法學(xué)習(xí)之雙向鏈表詳解的文章就介紹到這了,更多相關(guān)C語言雙向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: