C++实现线性表 - 03 双向循环链表

简介: 上一讲我们学会了如何创建一个单链表,这一讲我们来看看双向循环链表是如何进行操作的,我相信经过上面的学习,这一讲对你来说不会太吃力~
写在前面:
上一讲我们学会了如何创建一个单链表,这一讲我们来看看双向循环链表是如何进行操作的,我相信经过上面的学习,这一讲对你来说不会太吃力~

什么是双向链表 

9.jpg

正如上图所示,双向链表就只是在单向链表的基础上,增加了一个指向上一个结点的指针,操作上就只用多考虑一个指针罢了。而双向循环链表就是在双向链表的基础上将头尾结点也连接起来,如下图所示。

10.jpg

另外要注意的是,我们这里的头指针和尾指针指向的结点不存放数据,这样可能会更易于初学者去理解(我当初就是这样的doge),当然你也可以不用尾指针,因为头结点的指向上一个结点的指针就是最后一个结点,这里全凭个人喜好啦~

链表的创建

这里的结点的结构体就增加了一个front指针。

struct Node {
    int val;        //数据
    Node* front;    //指向上一个结点的指针
    Node* next;        //指向下一个结点的指针
};

我们这里初始化的时候顺带创建一个存储数据的新结点,这样我们的尾结点的front在头插法的时候也能一直指向最后一个结点啦。

void initnode(int key) {
    Node* new_node = new Node;
    new_node->val = key;
    head = new Node;
    last = new Node;
    //将新结点连接到头结点和尾结点当中
    head->next = new_node;
    last->front = new_node;
    //将头尾结点相连
    head->front = last;
    last->next = head;
    head->val = last->val = -1;    //将两个结点赋一个不可能的值
}

头插法

其实双向链表的插入操作相对于单向链表而言会更加方便,因为想要插入一个结点到链表中的话不用找到删除结点的上一个结点了,直接调用删除结点的front就可以找到,我们这里还是给大家讲解头插法和尾插法的做法。
11.jpg

12.jpg

13.jpg

 其实做法和单向链表差不了多少,直接来看代码。

void head_insert(int key) {
    Node* new_node = new Node;
    new_node->val = key;
    new_node->next = head->next;    //将新结点的next指向头结点的next
    new_node->front = head;            //将新结点的front指向头结点
    head->next->front = new_node;    //将头结点的下一个结点的front指向新结点
    head->next = new_node;            //将头结点的next指向新结点
}

尾插法

尾插法和头插法几乎没什么差别,同样直接来看代码。

void end_insert(int key) {
    Node* new_node = new Node;
    new_node->val = key;
    new_node->next = last;                //将新结点的next指向尾结点
    new_node->front = last->front;        //将新结点的front指向尾结点的上一个结点
    new_node->front->next = new_node;    //将新结点的上一个结点的下一个结点指向新结点
    last->front = new_node;                //将尾结点的front指向新结点
}

删除结点

删除结点的操作和单向链表几乎一样,而且上面提到过,咱不需要另外创建一个临时指针寻找删除结点的上一个结点,直接调用删除结点的front即可,不过这里方便大家理解,我们创建三个临时指针,分别指向删除结点的上一个结点、删除结点和删除结点的下一个结点。

void delete_node(int key) {
    Node* temp = head->next;
    while (temp->val != key){
        //判断是否有该结点
        if (temp->val == -1){
            cout << "没有此结点" << endl;
            return;
        }
        temp = temp->next;
    }

    Node* Prev = temp->front;    //创建临时结点指向删除结点的上一个结点
    Node* Next = temp->next;    //创建临时结点指向删除结点的下一个结点
    Prev->next = Next;            //删除结点的上一个结点的next指向删除结点的下一个结点
    Next->front = Prev;            //删除结点的下一个节点的front指向删除结点的上一个结点
    /*
    也可以不用创建Prev和Next指针
    temp->front->next = temp->next;
    temp->next->front = temp->front;
    */

    temp->front = temp->next = NULL;
    delete[]temp;
    temp = NULL;
}

遍历链表

双向链表的遍历和我们的单向链表的遍历是几乎一样的,直接看代码!

void show()
{
    Node* temp = head->next;  //创建一个临时指针
    if (temp->val == -1)
    {
        cout << "当前还没有创建结点" << endl;
        return;
    }
    while (temp->val != -1)      //遍历整个链表
    {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}

全部代码

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;        //数据
    Node* front;    //指向上一个结点的指针
    Node* next;        //指向下一个结点的指针
};

Node* head;        //头指针,设为全局变量方便使用
Node* last;        //尾指针

void initnode(int);
void head_insert(int);
void end_insert(int);
void delete_node(int);
void show();

int main() {
    initnode(1);
    head_insert(5);
    head_insert(2);
    end_insert(3);
    show();
    delete_node(2);
    show();
}

void initnode(int key) {
    Node* new_node = new Node;
    new_node->val = key;
    head = new Node;
    last = new Node;
    //将新结点连接到头结点和尾结点当中
    head->next = new_node;
    last->front = new_node;
    new_node->next = last;
    new_node->front = head;
    //将头尾结点相连
    head->front = last;
    last->next = head;
    head->val = last->val = -1;    //将两个结点赋一个不可能的值
}

void head_insert(int key) {
    Node* new_node = new Node;
    new_node->val = key;
    new_node->next = head->next;    //将新结点的next指向头结点的next
    new_node->front = head;            //将新结点的front指向头结点
    head->next->front = new_node;    //将头结点的下一个结点的front指向新结点
    head->next = new_node;            //将头结点的next指向新结点
}

void end_insert(int key) {
    Node* new_node = new Node;
    new_node->val = key;
    new_node->next = last;                //将新结点的next指向尾结点
    new_node->front = last->front;        //将新结点的front指向尾结点的上一个结点
    new_node->front->next = new_node;    //将新结点的上一个结点的下一个结点指向新结点
    last->front = new_node;                //将尾结点的front指向新结点
}

void delete_node(int key) {
    Node* temp = head->next;
    while (temp->val != key){
        //判断是否有该结点
        if (temp->val == -1){
            cout << "没有此结点" << endl;
            return;
        }
        temp = temp->next;
    }

    Node* Prev = temp->front;    //创建临时结点指向删除结点的上一个结点
    Node* Next = temp->next;    //创建临时结点指向删除结点的下一个结点
    Prev->next = Next;            //删除结点的上一个结点的next指向删除结点的下一个结点
    Next->front = Prev;            //删除结点的下一个节点的front指向删除结点的上一个结点
    /*
    也可以不用创建Prev和Next指针
    temp->front->next = temp->next;
    temp->next->front = temp->front;
    */

    temp->front = temp->next = NULL;
    delete[]temp;
    temp = NULL;
}

void show()
{
    Node* temp = head->next;  //创建一个临时指针
    if (temp->val == -1)
    {
        cout << "当前还没有创建结点" << endl;
        return;
    }
    while (temp->val != -1)      //遍历整个链表
    {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}

如果大家有什么问题的话,欢迎在下方评论区进行讨论哦~

目录
相关文章
|
13天前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
19 0
|
1月前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
|
5天前
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧
9 0
|
8天前
|
存储 C++
C++的list-map链表与映射表
这篇教程介绍了C++中`list`链表和`map`映射表的基本使用。`list`链表可通过`push_front()`、`push_back()`、`pop_front()`和`pop_back()`进行元素的添加和删除,使用迭代器遍历并支持在任意位置插入或删除元素。`map`是一个键值对的集合,元素自动按键值排序,可使用下标操作符或`insert()`函数插入元素,通过迭代器遍历并修改键值对,同时提供`count()`方法统计键值出现次数。教程中包含多个示例代码以帮助理解和学习。
13 2
|
13天前
|
算法
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
10 0
|
13天前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
9 0
|
13天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
10 0
|
22天前
|
存储 缓存 算法
【数据结构】线性表----链表详解
【数据结构】线性表----链表详解
62 0
|
26天前
|
算法 C++
c++算法学习笔记 (13) 链表
c++算法学习笔记 (13) 链表
|
1月前
|
存储 机器学习/深度学习 人工智能
c/c++线性表实现附源码(超详解)
c/c++线性表实现附源码(超详解)
21 0