循环双向链表的初始化及创建-头插法和尾插法

什么是循环双向链表？

为克服单链表的这种单向性特点，在双向链表的结点有两个指针域，一个指向直接后继，另一个指向直接前驱。

循环双向链表的操作

1.初始化
2.头插法创建链表
3.尾插法创建链表
4.打印链表中的所有元素
5.可以把循环单链表和循环双向链表来对比一下来理解。参考文章：循环单链表基本操作

循环双链表的结构

这个地方要区别循环单链表，单链表中只有一个指针域，而循环双链表有两个指针域。

typedef struct DuLNode{
    int data;  //数据域 
    struct DuLNode *prior;  //头指针 
    struct DuLNode *next;  //尾指针 
}DuLNode,*DuLinkList;

初始化链表

/*循环双链表的初始化*/ 
int InitDuList_L(DuLinkList &L){
    L = (DuLinkList)malloc(sizeof(DuLNode));
    if(L==NULL) {
        return 1;
    }
    L->prior = L;  //头结点的头指针指向自己 
    L->next = L;  //头结点的 
    return 0;
}

头插法创建链表

/*循环双链表的创建 头插法*/
int InsertDuList_Head_L(DuLinkList &L,int n){
    for(int i = n;i>0;i--){
        DuLinkList newNode = (DuLinkList)malloc(sizeof(DuLNode));
        printf("请输入第%d个元素值：",n-i+1);
        scanf("%d",&newNode->data);  //将输入的元素值 赋值给新创建的结点 
        newNode->next = L->next;
        L->next->prior = newNode; 
        newNode->prior = L;
        L->next = newNode;
    }
    return 0;
}

尾插法创建链表

/*循环双链表的创建 尾插法*/
int InsertDuList_Rear_L(DuLinkList &L,int n){
    DuLinkList p = L;
    while(p->next != L){  //将指针移动到最后一个结点 
        p = p->next;
    }
    for(int i = 0;i<n;i++){
        DuLinkList newNode = (DuLinkList)malloc(sizeof(DuLNode));
        printf("请输入第%d个元素：",i+1);
        scanf("%d",&newNode->data);
        newNode->next = p->next;
        p->next->prior = newNode; 
        newNode->prior = p;
        p->next = newNode;

        p = p->next;  //将p一直指到最后一个结点 
    } 
    return 0; 
}

打印链表中的元素

/*打印链表中的元素*/ 
int PrintList_L(DuLinkList L) {
    DuLinkList p = L;
    int i=1;
    while(p->next != L){
        p = p->next;
        printf("第%d个元素为：%d\n",i,p->data);
        i++;
    }
}

完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct DuLNode{
    int data;  //数据域 
    struct DuLNode *prior;  //头指针 
    struct DuLNode *next;  //尾指针 
}DuLNode,*DuLinkList;

/*循环双链表的初始化*/ 
int InitDuList_L(DuLinkList &L){
    L = (DuLinkList)malloc(sizeof(DuLNode));
    if(L==NULL) {
        return 1;
    }
    L->prior = L;  //头结点的头指针指向自己 
    L->next = L;  //头结点的 
    return 0;
} 

/*循环双链表的创建 头插法*/
int InsertDuList_Head_L(DuLinkList &L,int n){
    for(int i = n;i>0;i--){
        DuLinkList newNode = (DuLinkList)malloc(sizeof(DuLNode));
        printf("请输入第%d个元素值：",n-i+1);
        scanf("%d",&newNode->data);  //将输入的元素值 赋值给新创建的结点 
        newNode->next = L->next;
        L->next->prior = newNode; 
        newNode->prior = L;
        L->next = newNode;
    }
    return 0;
}

/*循环双链表的创建 尾插法*/
int InsertDuList_Rear_L(DuLinkList &L,int n){
    DuLinkList p = L;
    while(p->next != L){  //将指针移动到最后一个结点 
        p = p->next;
    }
    for(int i = 0;i<n;i++){
        DuLinkList newNode = (DuLinkList)malloc(sizeof(DuLNode));
        printf("请输入第%d个元素：",i+1);
        scanf("%d",&newNode->data);
        newNode->next = p->next;
        p->next->prior = newNode; 
        newNode->prior = p;
        p->next = newNode;

        p = p->next;  //将p一直指到最后一个结点 
    } 
    return 0; 
}

/*打印链表中的元素*/ 
int PrintList_L(DuLinkList L) {
    DuLinkList p = L;
    int i=1;
    while(p->next != L){
        p = p->next;
        printf("第%d个元素为：%d\n",i,p->data);
        i++;
    }
}


main(){
    DuLinkList L;
    int initStatus;
    int headStatus;
    int rearStatus;
    //循环链表的初始化 
    initStatus = InitDuList_L(L);
    if(initStatus==0){
        printf("链表初始化成功\n");
        printf("===============\n");
    }else{
        printf("链表初始化失败\n");
    }
    //头插法 
    headStatus = InsertDuList_Head_L(L,3);
    if(headStatus==0){
        printf("头插法插入成功\n");
    }else{
        printf("头插法插入失败\n");
    }
    //尾插法
    rearStatus = InsertDuList_Rear_L(L,3);
    if(rearStatus==0){
        printf("尾插法插入成功\n");
    }else{
        printf("尾插法插入失败\n");
    }
    //打印链表中的数据元素 
    PrintList_L(L);     
}

运行结果

头插法插入的元素与输入的元素顺序相反，尾插法插入的元素顺序与插入的顺序相同。