C语言算法学习之双向链表详解

 更新时间:2022年05月14日 10:34:08   作者:英雄哪里出来  
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。本文主要介绍了C语言算法中双向链表的实现,需要的可以参考一下

一、练习题目

题目链接难度
1472. 设计浏览器历史记录★★★☆☆
430. 扁平化多级双向链表★★★☆☆
剑指 Offer II 028. 展平多级双向链表★★★☆☆
剑指 Offer 36. 二叉搜索树与双向链表★★★★☆

二、算法思路

1、设计浏览器历史记录

1.这是一个模拟题;

2.初始化生成一个头结点,记录一个当前结点;

3.向前 和 向后 是两个类似的过程,可以统一实现,注意一些边界条件。

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.利用一个递归函数last = dfs(now),一旦遇到child域非空的结点,则递归计算clast = dfs(now->child),返回值是递归展平后的最后一个结点,然后进行双向链表的链接操作。

2.例如,当前有 child域的结点为now,它的下一个结点是next,递归计算以后得到展平的链表的最后一个结点为 clast,则有如下关系:

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

3.根据以上关系调整双向链表,注意不要忘记将child域置空。

4.当遍历到这个双向链表的最后一个结点的时候,如果它有child域,则当前链表的最后一个结点就是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)遇到这样的题,首先需要设计好递归函数;

(2)像这个问题,对于 左子树 和 右子树,需要知道双向链表的 头结点 和 尾结点,所以递归的时候需要返回 两个值,于是可以直接采用函数传指针进行返回,由于二叉树的结点本身就是指针,所以需要传 二级指针;

(3)递归计算左子树变成双向链表的情况;

(4)递归计算右子树变成双向链表的情况;

(5)将左子树的双向链表链接到root左边,将右子树的双向链表链接到root右边,然后根据递归函数的实际作用,返回 头结点 和 尾结点。

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语言双向链表内容请搜索得牛网以前的文章或继续浏览下面的相关文章希望大家以后多多支持得牛网!

相关文章

  • C++求阶乘的两种方法

    C++求阶乘的两种方法

    这篇文章主要介绍了C++求阶乘的两种方法,有需要的朋友可以参考一下
    2013-12-12
  • C语言实现斗地主的核心算法

    C语言实现斗地主的核心算法

    本文给大家分享的是使用C语言实现的斗地主游戏的核心算法,主要实现了面向对象设计,洗牌、发牌、判断牌型、比较牌的大小、游戏规则等算法。通过这个斗地主小项目的练习,提高了我的面向对象设计能力,加深了对算法的理解。最近把这些设计和算法分享给大家。
    2015-03-03
  • 应用程序操作NorFlash示例代码分享(norflash接口使用方法)

    应用程序操作NorFlash示例代码分享(norflash接口使用方法)

    相对于操作NandFlash,操作NorFlash相对简单,因为基本不需要考虑坏块,NorFlash也没有OOB区域,也跟ECC没有关系。读写擦除相对容易,下面看个例子吧
    2013-12-12
  • C语言中的fscanf()函数与vfscanf()函数使用

    C语言中的fscanf()函数与vfscanf()函数使用

    这篇文章主要介绍了C语言中的fscanf()函数与vfscanf()函数使用,是C语言入门学习中的基础知识,需要的朋友可以参考下
    2015-08-08
  • C基础 寻找随机函数的G点详解

    C基础 寻找随机函数的G点详解

    下面小编就为大家带来一篇C基础 寻找随机函数的G点详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
    2016-06-06
  • C++中CSTRINGLIST用法详解

    C++中CSTRINGLIST用法详解

    这篇文章主要介绍了C++中CSTRINGLIST用法详解的相关资料,需要的朋友可以参考下
    2015-06-06
  • 一篇文章带你了解C++语法基础--字符串

    一篇文章带你了解C++语法基础--字符串

    这篇文章主要介绍了C++常用字符串分割方法实例汇总,包括了strtok函数、STL、Boost等常用的各类字符串分割方法,非常具有实用价值,需要的朋友可以参考下
    2021-08-08
  • mac 配置Clion运行C和C++的环境的详细步骤

    mac 配置Clion运行C和C++的环境的详细步骤

    这篇文章主要介绍了mac 配置Clion运行C和C++的环境的步骤详解,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下
    2021-04-04
  • 解析shell排序的实现代码

    解析shell排序的实现代码

    本篇文章是对shell排序的实现代码进行了详细的分析介绍,需要的朋友参考下
    2013-05-05
  • 一篇文章教你在C++中操作符可分为哪几种类和用法

    一篇文章教你在C++中操作符可分为哪几种类和用法

    这篇文章主要介绍了C++编程中操作符的种类和用法,是C++入门学习中的基础知识,需要的朋友可以参考下,希望能够给你带来帮助
    2021-09-09

最新评论