2.数据结构与算法--双向循环链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2.数据结构与算法--双向循环链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4593字，纯文字阅读大概需要7分钟。

内容图文

1.双向循环链表

• 节点结构，prior域存放前驱节点的地址，next域存放后继节点的地址，data域存放数据

• 代码结构

• 

双向链表结构

 

1.1.双向链表的节点插入

插入的顺序非常的重要：

插入与单链表不同，选取后一个位置的节点作为P

• s的next域指向P节点
• S的prio域指向O节点
• O节点的next域指向s节点
• P的prio域指向s节点
• 节点个数加一

1.1.双向链表的节点删除

选取要删除的节点作为P

• O节点的next域指向Q；
• Q节点的prio域指向O;
• 释放节点P；节点个数减一

代码：

// 双向循环链表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
class Node
{
public:
    int data;
    Node* pre;
    Node* next;
};
class DouList :public Node
{
public:
    Node* head;
    int length;
    DouList();
    ~DouList();
    Node* CreDouList(int n); //返回尾结点
    bool TraList();
    void InsertNode(int posi, int data);
    bool InserTail(int data);
    bool DeleteNode(int posi);
    //bool DeleteTail();
    
    

};
DouList::DouList()
{
    head = new Node;
    head->next = NULL;
    head->pre = NULL;
    head->data = 888888;
    length = 0;
}
DouList::~DouList()
{
    delete head;
}
Node* DouList::CreDouList(int n) //返回尾结点
{
    Node* p = head;
    Node* s = NULL;
    int i = 0;
    int data = 1;
    while (i<n)
    {
        s = new Node;
        s->data = data++;
        p->next = s;
        s->pre = p;
        p = s;
        i++;
    }
    s->next = head;
    head->pre = s;
    return s;
}
bool DouList::TraList()
{
    Node* p = head->next;
    Node* tail;
    cout << "正向遍历节点：";
    while (p != head)
    {
        cout << p->data;
        p = p->next;
        if (p != head)
        {
            cout << " ->";
        }
    }
    cout << endl;
    cout << "反向遍历节点 :"; //这时候p等于head
     tail = p->pre;
    while (tail != head)
    {
        cout << tail->data ;
        tail = tail->pre;      
        if (tail != head)
        {
            cout << "<- ";
        }
    }
    cout << endl;
    return true;
}
void DouList::InsertNode(int posi, int data)
{
    Node* p;
    p = head;
    Node* s = NULL;
    if (posi < 1)
    {
        cout << "输入位置不合法" << endl;
        return;
    }
    for (int i = 0; i < posi; i++)
    {
        p = p->next;
    }
    s = new Node;
    s->data = data;
    s->next = p;
    s->pre=p->pre;
    p->pre->next = s;
    p->pre = s;
}

bool DouList::InserTail( int data)
{
    Node* p = head;
    Node* s = new Node;
    s->data = data;
    //if()空表
    s->pre = p->pre;
    s->next = p;
    p->pre->next = s;
    p->pre = s;
    
    return true;
}
bool DouList::DeleteNode(int posi)
{
    Node* p = head;
    Node* q;
    for (int i = 0; i < posi; i++)
    {
        p = p->next;
    }
    p->pre->next = p->next;
    p->next->pre = p->pre;
    delete p;
    return true;
}


int main()
{
    DouList* L = new DouList();
    int posi, value, number;
    cout << "输入创建节点的个数:"; cin >> number;
    L->CreDouList(number);
    L->TraList();
    cout << "输入插入的位置："; cin >> posi;
    cout << "输入数值"; cin >> value;
    L->InsertNode(posi, value);
    L->TraList();
    cout << "输入尾插的值："; cin >> value;
    L->InserTail(value);
    L->TraList();
    cout << "输入删除的位置："; cin >> posi;
    L->DeleteNode(posi);
    L->TraList();
    return 0;
}

 

例题：

代码：

// 双向循环链表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
class Node_vca
{
public:
    char data;
    Node_vca* pr;
    Node_vca* nex;
};

class ListWorks
{
public:
    Node_vca* head_vca;
    int length_vca;
    ListWorks();
    ~ListWorks();
    Node_vca* CreVcaList(); //返回尾结点
    bool TraList_vca();
    bool ChangeList(int posi);

};
ListWorks* L = new ListWorks();
ListWorks::ListWorks()
{
    head_vca = new Node_vca;
    head_vca->nex = NULL;
    head_vca->pr = NULL;
    head_vca->data = 'a';
    length_vca = 0;
}
Node_vca* ListWorks::CreVcaList()
{
    Node_vca* p = head_vca;
    Node_vca* s = NULL;
    int i = 0;
    char data = 'A';
    while (i < 26)
    {
        s = new Node_vca;
        s->data = data++;
        p->nex = s;
        s->pr = p;
        p = s;
        i++;
    }
    s->nex = head_vca;
    head_vca->pr = s;
    return s;
}
bool ListWorks::TraList_vca()
{
    Node_vca* p = head_vca->nex;
    Node_vca* tail;
    cout << "正向遍历节点：";
    while (p != head_vca)
    {
        cout << p->data;
        p = p->nex;
        if (p != head_vca)
        {
            cout << " ->";
        }
    }
    cout << endl;
    cout << "反向遍历节点 :"; //这时候p等于head
    tail = p->pr;
    while (tail != head_vca)
    {
        cout << tail->data;
        tail = tail->pr;
        if (tail != head_vca)
        {
            cout << "<- ";
        }
    }
    cout << endl;
    return true;
}
bool ListWorks::ChangeList(int posi)
{
    Node_vca* p = head_vca->nex;
    Node_vca* q = head_vca->pr;
    cout << "重排序后的链表：";
    if (posi > 0)
    {
        for (int i = 1; i < posi; i++)
        {
            p = p->nex; //从C开始
        }
        for (int i = 1; i < 27; i++)
        {
            p = p->nex;
            
            if ((p) == head_vca)//如果碰到头结点，就跳过头结点的数据，i--就可以使循环多走一次
            {
                i--;
            }
            else
            {
                cout << p->data << " ";
            }
        }
    }
    else if (posi == 0)
    {
        L->TraList_vca(); //bianlishuchu 
    }
    else {
        for (int i = posi; i < 0; i++)
        {
            q = q->pr;
       }
        for (int i = 1; i < 27; i++)
        {
            q = q->nex;

            if ((q) == head_vca) //如果碰到头结点，就跳过头结点的数据，i--就可以使循环多走一次
            {
                i--;
            }
            else
            {
                cout << q->data << " ";
            }
        }
    }

    return true;
}

int main()
{
    {

        int posi;
        L->CreVcaList();
        L->TraList_vca();
        cout << "输入要重排的位置：" << endl; cin >> posi;
        L->ChangeList(posi);
    }


    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的2.数据结构与算法--双向循环链表全部内容，希望文章能够帮你解决2.数据结构与算法--双向循环链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---