首页 > 代码库 > 双链表的简单应用

双链表的简单应用

/*当对单链表理解后,对双链表就好理解多了,单链表就是只有在结构体或者类中只有一个指针用来存储下一个节点的地址,双链表就是在里面有两个指针,一个用来存储上一个节点的地址,一个用来存储下一个节点的地址。这样的链表就叫双链表。*/

#include<iostream>

using namespace std;
struct Node
{
    int a;
    Node *prior,*next;         //前指针,后指针
};
int main()
{
    Node *first,*r,*p;
    first=new Node();    //因为在一个双链表中插入数据要用到它的前一个节点,或者后一个节点,所以这儿r就代表first的后一个节点,下面会用到
    r=new Node();
    first->next=r;
    r->prior=NULL;
    for(int i=20;i>=0;i--)      //将21个p指针依次插入以first为头结点的链表中。
    {
        p=new Node();
        p->a=i;                                
        p->next=first->next;       //p的next指针存储了first 的next指针存储的地址,
        p->prior=first;                //p的前一个节点就是first,所以prior中存的是first的地址
        first->next->prior=p;    //first原来的节点现在存储的是p的地址。
        first->next=p;                //first的下一个节点就是p,  这儿四条语句的先后顺序需要注意一下
    }
    p=first->next;
    for(int i=0;i<=20;i+=2)
    {
        while(p->next!=NULL)
        {
            if(p->a==i)
            {
                p->prior->next=p->next;      //这儿是删除a值为偶数的节点,剩下的为奇数节点
                p->next->prior=p->prior;
                cout<<p->a<<" ";
                delete p;
                break;
            }
            p=p->next;
        }
    }
    p=first->next;
    cout<<endl;
    while(p->next!=NULL)
    { 
        cout<<p->a<<" ";                             //输出的是奇数节点
        p=p->next;
    }
}

双链表的简单应用