Question

c++双向循环链表怎么使用

若以下回答无法解决问题，邀请你更新回答

Answer 1

参考代码：

[cpp] view plain copy 
#include<iostream>  
using namespace std;  
  
/* 
*节点类 
*/  
struct DCNode  
{  
  int data;  
  DCNode * prior;  
  DCNode * next;  
};  
/* 
*链表类 
*/  
struct DCList  
{  
    DCList()  
    {  
        size = 0;  
    }  
    size_t size;//记录节点数的个数  
    DCNode * head;//指向链表的头结点  
};  
  
/* 
*分配一个节点，并给该节点的数据域赋值，默认值为0； 
*/  
DCNode * MakeNode(int t=0)  
{  
    DCNode * p = (DCNode *)malloc(sizeof(DCNode));  
    p->data = t;  
    return p;  
}  
  
//初始化一个空的双向循环链表  
void InitDCList(DCList &list)  
{  
    //分配一个头结点  
    DCNode * p = MakeNode();  
    list.head = p;  
    list.size = 0;  
    p->next = p;  
    p->prior = p;  
}  
  
//释放所指向的节点  
void FreeNode(DCNode * p)  
{  
    delete p;  
}  
  
//清空一个线性表  
void clear(DCList &list)  
{  
    DCNode * p = list.head;  
    p = p->next;  
    while(p!= list.head)  
    {    
        DCNode * p1 = p->next;  
        delete p;  
        p = p1;  
    }  
    list.size = 0;  
}  
  
//将s所指向的节点插入到链表的第一个节点之前  
bool InsFirst(DCList &list,DCNode * s)  
{  
      
    s->next = list.head->next;  
    list.head->next->prior = s;  
    list.head->next = s;  
    s->prior = list.head;  
    list.size++;  
    return true;  
}  
  
//删除链表中的第一个节点并以q指针返回  
bool DelFirst(DCList &list,DCNode *  & q)  
{  
    if(list.head->next==list.head)//如果链表为空  
    {  
        q = 0;  
        return false;  
    }  
    q = list.head->next;  
    list.head->next->next->prior = list.head;  
    list.head->next = list.head->next->next;  
    list.size--;  
    return true;  
}  
  
//将s所指向的节点串接在链表的最后一个节点之后  
bool Append(DCList &list,DCNode * s)  
{  
    s->prior = list.head->prior;  
    s->next = list.head;  
    list.head->prior->next = s;  
    list.head->prior = s;  
    list.size++;  
    return true;  
}  
  
//删除链表中的尾节点,并以指针q返回  
bool Remove(DCList &list,DCNode * & q)  
{  
    if(list.head->next==list.head)//如果链表为空  
    {  
        q = 0;  
        return false;  
    }  
    q = list.head->prior;  
    list.head->prior->prior->next = list.head;  
    list.head->prior = list.head->prior->prior;  
    list.size--;  
    return true;  
}  
  
//将s所指向的节点插入链表中p所指向的节点之前  
bool InsBefore(DCList &list,DCNode * p,DCNode * s)  
{  
    DCNode * p1 = list.head->next;  
    while(p1!=list.head)  
    {  
     if(p1==p)//找到该链表中是否存在p所指向的节点  
     {  
         s->next = p;  
         s->prior = p->prior;  
         p->prior->next = s;  
         p->prior = s;  
         list.size++;  
         return true;  
     }  
      p1 = p1->next;  
    }  
    //没找到  
    return false;  
}  
  
//将s所指向的节点插入链表中p所指向的节点之后  
bool InsAfter(DCList &list,DCNode * p,DCNode * s)  
{  
    DCNode * p1 = list.head->next;  
    while(p1!=list.head)  
    {  
     if(p1==p)//找到该链表中是否存在p所指向的节点  
     {  
         s->next = p->next;  
         s->prior = p;  
         p->next->prior = s;  
         p->next = s;  
         list.size++;  
         return true;  
     }  
     p1 = p1->next;  
    }  
    //没找到  
    return false;  
}  
  
//判断链表是否为空  
bool Empty(DCList &list)  
{  
    if(list.size==0)  
    return  true;  
    else  
    return false;  
  
}  
  
//返回链表的长度  
int GetLength(DCList &list)  
{  
    return list.size;  
}  
  
//返回链表中第i个节点的指针  
DCNode * LocatePos(DCList &list,int i)  
{  
    if(i<=0&&i>(int)list.size ) return 0;//如果不存在第i个节点则返回一个0指针  
    int n = 0;  
    DCNode * p1 = list.head->next;  
    while(p1!=list.head)  
    {  
     n++;  
     if(n==i)//找到  
     {  
        return p1;  
     }  
     p1 = p1->next;  
    }  
    return 0;  
}  
  
//在链表中查找第一个元素值与t相等的节点指针  
DCNode * LocateElem(DCList &list,int t)  
{  
    if(list.head->next==list.head)//如果链表为空  
    {  
        return 0;  
    }  
    DCNode * p1 = list.head->next;  
    while(p1!=list.head)  
    {  
        if(p1->data==t)//找到  
     {  
        return p1;  
     }  
     p1 = p1->next;  
    }  
    return 0;  
}  
  
//在链表中查找第一个元素值与t满足compare函数关系的节点指针  
DCNode * LocateElem(DCList &list,int t,bool (* compare)(int ,int))  
{  
    if(list.head->next==list.head)//如果链表为空  
    {  
        return 0;  
    }  
    DCNode * p1 = list.head->next;  
    while(p1!=list.head)  
    {  
        if((*compare)(p1->data,t))//找到了  
     {  
        return p1;  
     }  
     p1 = p1->next;  
    }  
    return 0;  
}  
  
//依次对链表中的每一个元素调用visit函数，一旦visit函数调用失败，则整个操作失败  
bool ListTraverse(DCList &list,bool (*visit)(int &))  
{  
  
    DCNode * p1 = list.head->next;  
    while(p1!=list.head)  
    {  
        if(!(*visit)(p1->data))//找到了  
     {  
        return false;  
     }  
     p1 = p1->next;  
    }  
    return true;  
}  
  
//合并两个双向循环链表  
DCList & MergeList(DCList &list1,DCList &list2)  
{  
    if(Empty(list1))  
    {  
        return list2;  
    }  
    if(Empty(list2))  
    {  
        return list1;  
    }  
    list1.head->prior->next = list2.head->next;  
    list2.head->next->prior = list1.head->prior;  
    list1.head->prior = list2.head->prior;  
    list2.head->prior->next = list1.head;  
    return list1;  
}  
  
//判断是否一个数为偶数  
bool judge(int a,int b)  
{  
    if(a%b==0) return true;  
    return false;  
}  
  
bool visit(int & t)  
{  
    t = t+1;  
    return true;  
}  
  
int main()  
{  
//创建并初始化一个空的双向循环链表  
    DCList myList;  
    InitDCList(myList);  
  
//在链表的尾端添加元素  
    //现分配一个节点  
    DCNode * s = MakeNode(1);  
    Append(myList,s);  
    s = MakeNode(3);  
    Append(myList,s);  
    s = MakeNode(5);  
    Append(myList,s);  
    s = MakeNode(7);  
    Append(myList,s);  
  
//遍历该链表，并输出该链表的元素个数  
    DCNode * p1 = myList.head->next;  
    cout<<"新建一个双向链表，并初始化元素值为1，3，5，7"<<endl;  
    while(p1!=myList.head)  
    {  
        cout<<p1->data<<"  ";  
     p1 = p1->next;  
    }  
    cout<<endl;  
    cout<<"链表的元素个数为:"<<GetLength(myList)<<endl;  
  
//在链表的第一个数据节点之前插入两个元素  
  
    s = MakeNode(9);  
    InsFirst(myList,s);  
    s = MakeNode(0);  
    InsFirst(myList,s);  
     cout<<"在链表的第一个数据节点之前插入两个元素值为0，9的节点:"<<endl;  
     p1 = myList.head->next;  
    while(p1!=myList.head)  
    {  
        cout<<p1->data<<"  ";  
     p1 = p1->next;  
    }  
    cout<<endl;  
  
//删除链表中的第一个节点和尾节点   
     cout<<"删除的第一个节点"<<endl;  
     if(DelFirst(myList,s))  
     {  
         cout<<"被删除的第一个节点数据为："<<s->data<<endl;  
     }  
      p1 = myList.head->next;  
    while(p1!=myList.head)  
    {  
        cout<<p1->data<<"  ";  
     p1 = p1->next;  
    }  
    cout<<endl;  
    //释放被删除的节点空间  
     FreeNode(s);  
     cout<<"删除的尾节点"<<endl;  
    if( Remove(myList,s) )  
    {  
         cout<<"被删除的尾节点数据为："<<s->data<<endl;  
    }  
     p1 = myList.head->next;  
    while(p1!=myList.head)  
    {  
        cout<<p1->data<<"  ";  
     p1 = p1->next;  
    }  
    cout<<endl;  
    //释放被删除的节点空间  
    FreeNode(s);  
  
//在第二个节点之前插入元素  
     p1 = LocatePos(myList,2);  
     cout<<"第二个节点数据为："<<p1->data<<endl;  
     s = MakeNode(11);  
     InsBefore(myList,p1,s);  
     cout<<"在第二个节点之前插入一个元素值为11的新节点:"<<endl;  
     p1 = myList.head->next;  
     while(p1!=myList.head)  
     {  
        cout<<p1->data<<"  ";  
     p1 = p1->next;  
     }  
     cout<<endl;  
  
//在第二个节点之后插入元素  
     s = MakeNode(16);  
     p1 = LocatePos(myList,2);  
     InsAfter(myList,p1,s);  
     cout<<"再在第二个节点之后插入一个元素值为16的新节点:"<<endl;  
     p1 = myList.head->next;  
     while(p1!=myList.head)  
     {  
        cout<<p1->data<<"  ";  
     p1 = p1->next;  
     }  
     cout<<endl;  
  
//查找第一个元素值为4的倍数的节点  
     p1 = LocateElem(myList,4,judge);  
     cout<<"找到第一个元素值为4的倍数的节点数据为："<<p1->data<<endl;  
  
//将链表中所有的元素值都增加1  
     ListTraverse(myList,visit);  
     cout<<"将链表中所有的元素值都增加1:"<<endl;  
     p1 = myList.head->next;  
     while(p1!=myList.head)  
     {  
        cout<<p1->data<<"  ";  
     p1 = p1->next;  
     }  
     cout<<endl;  
  
//新建一个元素值为1，3，9的链表  
     DCList myList2;  
    InitDCList(myList2);  
  
//在链表的尾端添加元素  
    //现分配一个节点  
     s = MakeNode(1);  
    Append(myList2,s);  
    s = MakeNode(3);  
    Append(myList2,s);  
    s = MakeNode(9);  
    Append(myList2,s);  
  
//遍历该链表，并输出该链表的元素个数  
     cout<<"新建一个元素值为1，3，9的链表:"<<endl;  
    p1 = myList2.head->next;  
    while(p1!=myList2.head)  
    {  
        cout<<p1->data<<"  ";  
     p1 = p1->next;  
    }  
    cout<<endl;  
  
//合并两个链表  
     myList = MergeList(myList,myList2);  
     cout<<"合并两个链表:"<<endl;  
     p1 = myList.head->next;  
     while(p1!=myList.head)  
     {  
        cout<<p1->data<<"  ";  
        p1 = p1->next;  
     }  
     cout<<endl;  
     cout<<"最后清空myList链表！"<<endl;  
     clear(myList);  
}