双链表的定义以及正序、倒序输入输出

双链表的一个结点用一个struct变量表示，一个结点具有三个部分

• 保存数据的变量n
• 保存上一个结点地址的指针变量last
• 保存下一个结点地址的指针变量next

对于一整个双链表来说，还需要具有头结点和尾结点（此处也可用头指针与尾指针来表示，区别仅仅在于

• 头指针与尾指针指向的地址要保存数据
• 头结点与尾结点所指向的数据不保存数据

头结点与尾结点性质：

• 头节点的last与n不用管
• 尾结点的next与n不用管
• 头结点的next保存第一个结点的地址
• 尾结点的last保存最后一个结点的地址

带头结点与尾结点的链表拓展成循环链：

• 头结点与尾结点都存储数据
• 头结点的last指向尾结点
• 尾结点的next指向头结点

下面上代码：（注释即为易错点）

#include<bits/stdc++.h>
using namespace std;
class dbl{
public:    
int n;    
dbl* last;   
dbl* next;
};
int main()
{   
int n;    
cin>>n;
dbl * head,* tail;    
dbl * p,* q,* l;    //pql的用处见for循环后面的注释
head=new dbl;    //头尾结点要记得开空间（初始化），否则会变成野指针
tail=new dbl;      
q=new dbl;    
p=head;    
head->next=q;    
for(int i=0;i<n;i++)    //p为要操作的结点前一个结点，q为要操作（输入数据）的结点，l为要操作的结点后一个结点
{                        //需要在操作p时给l开空间
l=new dbl;        
cin>>q->n;        
q->next=l;        
q->last=p;        
p=q;        
q=l;    
}    
p->next=tail;    //for循环结束后由于p q l的迭代，指向最后一个结点的指针并不是q而是**p**。
tail->last=p;    //for循环之后两句是**设置尾结点**
/*
输出时设置临界值有两种方法
 1. head中不存数据。如果将p指向head，则在循环中先执行p=p->next;再cout<<p->n;
    由于循环中先移动指针再输出，则临界值**p->next=tail就停止执行**，否则就会输出尾结点数据（乱码）
    
 2. 如果将p指向head->next（即第一个结点），则while中应该先输出再迭代p，此时当p->next=tail时表示p指向最后一个结点，循环会输出最后一个结点的值然后把p->next赋值给p（即p指向tail），这时才应该结束输出。所以结束值应该设置成p！=tail。

第二种方法如括号所示


*/

//正序输出
p=head;    //(p=head->next;)
while(p->next!=tail)//p！=tail;    
{    
p=p->next;        //while循环体换成(cout<<p->n<<' ';p=p->next;)
cout<<p->n<<' ';    
}    
cout<<endl;

//逆序输出（只要把正序时head和tail反向即可）
p=tail;    
while(p->last!=head)    
{           
p=p->last;        
cout<<p->n<<' ';    
}    
cout<<endl;      
return 0;
}