DataStructure_DLinkList

1.双链表

1.1双链表的定义

#include "iostream"
using namespace std;
typedef int ElemType;
typedef struct DNode{					//定义双链表结点类型
    ElemType data;						//数据域
    struct DNode *prior,*next;			//前驱和后继指针
}DNode,*DLinkList;

1.2双链表的插入(这里是在p节点之后插入节点s)

//在p节点之后插入s
bool InsertNextDNode(DNode *p,DNode *s){
    if (p==NULL || s==NULL){
        return false;
    }
    s->next = p->next;                  //将节点s插入到节点p之后
    if (p->next!=NULL){					//这里判断的是我们的最后一个节点
        p->next->prior = s;				//要知道最后的一个节点指向的NULL那么他的prior可不存在的
    }
    s->prior = p;						//因为s在p之后。所以s的前驱得指向p
    p->next = s;						//p的后继得指向s
    return true;
}

1.3双链表的删除(在p节点之后删除)

//双链表的删除(删除p节点的后继节点)
bool DeleteNextDNode(DNode *p){
    if (p==NULL){                       //非空判断
        return false;
    }
    DNode *q = p->next;                 //找到p的后继节点
    if (q==NULL){                       //如果为空，那么p就是最后一个节点嘛
        return false;
    }
    p->next = q->next;					//删除q那么p得指向它指向的下一个节点的节点
    if (q->next!=NULL){					//老规矩最后一个节点的判断
        q->next->prior = p;
    }
    free(p);
    return true;

}

1.4双链表的遍历

//后遍历
void PrintHEADlist(DNode *L){
    DNode *p = L->next;
    while (p!=NULL){
        p=p->next;
        cout<<"依次向后遍历的值是:"<<p->data<<endl;
    }
}

//前遍历 这个L得是最后一个节点
void PrintBEHINDlist(DNode *L){
    while (L!=NULL){
        L=L->prior;
        cout<<"依次向前遍历的值是:"<<L->data<<endl;
    }
}

1.5双链表的摧毁

//摧毁双链表
void DestoryList(DLinkList &L){
    //循环找到各个数据节点
    while (L->next!=NULL){
        DeleteNextDNode(L);   //调用上面的删除后一个节点
    }
    free(L);                  //删除完了后面的节点是不是需要释放头节点
    L=NULL;                   //头指针得指向NULL 当然我们不考虑prior，因为他本来就是NULL
}

注释:
	这里我们得注意一下对于双链表的判断我们都知道头节点。那么如果prior和next都指向头节点head那么这个
	表是不是为空
	|---------⬇--⬇--------|
	[prior]<-[head]->[next]
	很容易理解吧
	
	当然对于循环单链表我没有给出其他的代码也就是最后一个元素指向的next是头节点L
	判断为空的话那就不是是否->next=NULL了，要知道循环链表的next是都不会指向NULL的。所以我们的判断条件是
	 ⬇----------|
	[head][L]->next :即头节点的next是否是头指针