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

目录
  • 一、练习题目
  • 二、算法思路
    • 1、设计浏览器历史记录
    • 2、扁平化多级双向链表
    • 3、展平多级双向链表
    • 4、二叉搜索树与双向链表

一、练习题目

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

时间: 2022-05-12

C语言之双向链表详解及实例代码

1,双向链表简介. 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 2,例子要求: 完成双向链表的插入.删除以及查找,将学生管理系统使用的数组,以双向链表的方式实现,能够支持无限制的学生人数的增删改查以及保存. 3,代码实现. #include <stdio.h> #include <string.h> #include <

C语言实现双向链表

这个小代码是我凭自己对指针和链表的理解和认识,自己实现的,没有参考其他人的代码,如果有相同的地方,那真的只是巧合,代码我在ubuntu 15.04下测试通过,可能存在很多错误和漏洞. doublelist.c /************************************************************************* > File Name: doublelist.c > Author: ChenYiLiang > Mail: chenyilian

C语言实现数据结构和双向链表操作

数据结构  双向链表的实现 双向链表中的每一个结点都含有两个指针域,一个指针域存放其后继结点的存储地址,另一个指针域则存放其前驱结点的存储地址. 双向链表结点的类型描述: //双向链表的类型描述 typedef int ElemType; typedef struct node{ ElemType data; struct node *prior,*next; }DuLNode,*DuLinkList; 其中,prior域存放的是其前驱结点的存储地址,next域存放的是其后继结点的存储地址. 双

C语言类的双向链表详解

目录 前言 双向链表的定义 双向链表的创建 节点的创建 双向链表节点查找 双向链表的插入 双向链表的节点删除 双向链表的删除 总结 前言 链表(linked list)是一种这样的数据结构,其中的各对象按线性排列.数组的线性顺序是由数组下标决定的,然而于数组不同的是,链表的各顺序是由链表中的指针决定的. 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循

C语言双向链表的表示与实现实例详解

1.概述: C语言中一种更复杂的链表是"双向链表"或"双面链表".其表中的每个节点有两个连接:一个指向前一个节点,(当这个"连接"为第一个"连接"时,指向空值或者空列表):而另一个指向下一个节点,(当这个"连接"为最后一个"连接"时,指向空值或者空列表) 一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接 在一些低级语言中, XOR-linking 提供一种在双向链表中

C语言 数据结构双向链表简单实例

双向链表的基本操作 1.利用尾插法建立一个双向链表. 2.遍历双向链表. 3.实现双向链表中删除一个指定元素. 4.在非递减有序双向链表中实现插入元素e仍有序算法. 5.判断双向链表中元素是否对称若对称返回1否则返回0. 6.设元素为正整型,实现算法把所有奇数排列在偶数之前. 7.在主函数中设计一个简单的菜单调试上述算法. 实例代码: //排序的时候因为没有说明奇数和偶数需不需要各自再排序,我就没有排序,只是将奇数放在偶数后面. //创建链表的时候,因为这个实验没有要求输出链表的长度,所以我就输

C语言数据结构二叉树简单应用

 C语言数据结构二叉树简单应用 在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree),接下来我就在这里给大家介绍一下二叉树在算法中的简单使用: 我们要完成总共有 (1)二叉树的创建 (2)二叉树的先中后序递归遍历 (3)统计叶子结点的总数 (4)求树的高度 (5)反转二叉树 (6)输出每个叶子结点到根节点的路径 (7)输出根结点到每个叶子结点的路径. 定义二叉树结点类型

C语言指针应用简单实例

C语言指针应用简单实例 这次来说交换函数的实现: 1. #include <stdio.h> #include <stdlib.h> void swap(int x, int y) { int temp; temp = x; x = y; y = temp; } int main() { int a = 10, b = 20; printf("交换前:\n a = %d, b = %d\n", a, b); swap(a, b); printf("交换

C语言数据结构 双向链表的建立与基本操作

C语言数据结构 双向链表的建立与基本操作 双向链表比单链表有更好的灵活性,其大部分操作与线性表相同.下面总结双向链表与单链表之间的不同之处及我在实现过程中所遇到的问题. 1.双向链表的建立 双向链表在初始化时,要给首尾两个节点分配内存空间.成功分配后,要将首节点的prior指针和尾节点的next指针指向NULL,这是十分关键的一步,因为这是之后用来判断空表的条件.同时,当链表为空时,要将首节点的next指向尾节点,尾节点的prior指向首节点. 2.双向链表的插入操作 由于定义双向链表时指针域中

C语言 数据结构链表的实例(十九种操作)

C语言 数据结构链表的实例(十九种操作) #include <stdio.h> #include <string.h> #include <stdlib.h> /*************************************************************************************/ /* 第一版博主 原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/30915

Python实现的调用C语言函数功能简单实例

本文实例讲述了Python实现的调用C语言函数功能.分享给大家供大家参考,具体如下: 实例参考python cookbook 中的15.1节中的例子P612页 先把 c文件编译成 so文件 gcc a.c -fpic -shared -o lib.so 通过上面编译成so文件 利用ctypes模块. from ctypes import cdll a=cdll.LoadLibrary("./lib.so") a.say() 能过上面代码测试通过. 更多关于Python相关内容感兴趣的读

C语言数据结构 快速排序实例详解

C语言数据结构 快速排序实例详解 一.快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序. 二.代码实现 #include <stdio.h> /* 将两个数据交换 */ void swap(int* Ina , int* Inb) { int temp = *Ina; *Ina = *Inb; *Inb = temp; } /* 进行一趟的快速排序,把一个序列分为两个部分 */ int getPart

C语言数据结构之平衡二叉树(AVL树)实现方法示例

本文实例讲述了C语言数据结构之平衡二叉树(AVL树)实现方法.分享给大家供大家参考,具体如下: AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树. 要维持这个树,必须在插入和删除的时候都检测是否出现破坏树结构的情况.然后立刻进行调整. 看了好久,网上各种各种的AVL树,千奇百怪. 关键是要理解插入的时候旋转的概念. // // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 201

C语言数据结构之循环链表的简单实例

 C语言数据结构之循环链表的简单实例 实例代码: # include <stdio.h> # include <stdlib.h> typedef struct node //定义链表中结点的结构 { int code; struct node *next; }NODE,*LinkList; /*错误信息输出函数*/ void Error(char *message) { fprintf(stderr,"Error:%s/n",message); exit(1)

C语言数据结构实现字符串分割的实例

C语言数据结构实现字符串分割的实例 以下为"字符串分割"的简单示例: 1. 用c语言实现的版本 #include<stdio.h> /* 根据空格分隔字符串 */ int partition(char *src, char *par, int pos) { int i,j; i = pos; //取到第一个非空格字符 while(src[i] == ' ') { ++i; } if(src[i] != '\0') { j = 0; while((src[i] != '\0'