欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言算法學習之雙向鏈表詳解

 更新時間：2022年05月14日 10:34:08   作者：英雄哪里出來  
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。本文主要介紹了C語言算法中雙向鏈表的實現(xiàn)，需要的可以參考一下

一、練習題目

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

二、算法思路

1、設計瀏覽器歷史記錄

1.這是一個模擬題；

2.初始化生成一個頭結(jié)點，記錄一個當前結(jié)點；

3.向前 和 向后 是兩個類似的過程，可以統(tǒng)一實現(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é)點，則遞歸計算clast = dfs(now->child)，返回值是遞歸展平后的最后一個結(jié)點，然后進行雙向鏈表的鏈接操作。

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

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

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

4.當遍歷到這個雙向鏈表的最后一個結(jié)點的時候，如果它有child域，則當前鏈表的最后一個結(jié)點就是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ù)；

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

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

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

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

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;
    }
};

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

相關文章

  • Opencv Hough算法實現(xiàn)圖片中直線檢測

    Opencv Hough算法實現(xiàn)圖片中直線檢測

    這篇文章主要為大家詳細介紹了Opencv Hough算法實現(xiàn)圖片中直線檢測，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2018-12-12
  • C++?分割字符串數(shù)據(jù)的實現(xiàn)方法

    C++?分割字符串數(shù)據(jù)的實現(xiàn)方法

    這篇文章主要介紹了C++?分割字符串數(shù)據(jù)的實現(xiàn)方法,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-09-09
  • C++鏈式二叉樹深入分析

    C++鏈式二叉樹深入分析

    二叉樹的鏈式存儲結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址
    2022-06-06
  • C語言MultiByteToWideChar和WideCharToMultiByte案例詳解

    C語言MultiByteToWideChar和WideCharToMultiByte案例詳解

    這篇文章主要介紹了C語言MultiByteToWideChar和WideCharToMultiByte案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • C語言當函數(shù)執(zhí)行成功時return1還是0

    C語言當函數(shù)執(zhí)行成功時return1還是0

    本文主要介紹了C語言當函數(shù)執(zhí)行成功時return1還是0，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2021-09-09
  • C語言與Lua之間的相互調(diào)用詳解

    C語言與Lua之間的相互調(diào)用詳解

    這篇文章主要給大家介紹了關于C語言與Lua之間的相互調(diào)用的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。
    2018-01-01
  • C++多線程中互斥量的使用詳解

    C++多線程中互斥量的使用詳解

    這篇文章主要介紹了C++多線程中互斥量的使用,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-08-08
  • C語言實現(xiàn)電子英漢詞典系統(tǒng)

    C語言實現(xiàn)電子英漢詞典系統(tǒng)

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)電子英漢詞典系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-06-06
  • Windows安裝Qt6.4.2及簡單驗證

    Windows安裝Qt6.4.2及簡單驗證

    本文主要介紹了Windows安裝Qt6.4.2及簡單驗證，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2023-02-02
  • C++實現(xiàn)學生檔案管理系統(tǒng)

    C++實現(xiàn)學生檔案管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C++實現(xiàn)學生檔案管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-05-05

最新評論