双链表

1）双链表的定义

typedef struct DNode{
    int data;
    DNode * next,* prior;
}DNode,*DLinkList;

bool InitList(DLinkList &L)
{
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->next=NULL;
    L->prior=NULL;
    return true;
}

bool Empty(DLinkList &L)
{
    return(L->next==NULL);
}

2）双链表的插入

bool ListInsert(DNode * p,DNode * s)
{
    if(p==NULL||s==NULL) return false;
    s->next=p->next; //1
    if(p->next!=NULL)
        p->next->prior=s; //2
    s->prior=p; //3
    p->next=s;  //4  1,2必须在4前
    return true;
}

这是指定结点的后插操作，按位序插入只需要设置尾指针，依次进行后插操作即可；前插操作只需要找到一个结点的前继结点，对其进行后插操作即可。

3）双链表的删除

bool ListDelete(DNode * p) //删除指定结点的后继节点
{
    if(p==NULL) return false;
    DNode * q=p->next; 
    if(q==NULL) return false;
    p->next=q->next;
    if(q->next!=NULL) q->next->prior=p;
    free(q);
    return true;
}

销毁一个双链表

void DestroyList(DLinkList &L)
{
    while(L->next!=NULL) ListDelete(L);
    free(L); //释放头结点
    L->next=NULL; //头指针置空
}

4）双链表的遍历

//后向遍历
while(p!=NULL)
{
    //...
    p=p->next;
}

//前向遍历
while(p->pror!=NULL) //跳过了头结点
{
    //...
    p=p->prior;
}