线性表之双循环链表

下午睡了一觉起来继续写哈。本文中的双循环链表有以下特征：有头结点，每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior（这点与单链表区分开），将头结点和尾结点链接起来（即循环性）。相关的插入删除操作需要修改4个指针的指向。写的时候纠结了一会儿边界条件，比如删除第一个或最后一个结点，在第一个结点前或最后一个结点后插入新结点，调试了一会，应该调出来了吧~~囧~~错误之处，还请指出！（话说今晚超级杯，小激动哈~~前进吧，大皇马~~ ）

#include<cstdio>
#include<cstdlib>

typedef char Datatype;
typedef struct node{
    Datatype data;
    struct node *next,*prior;
}DListNode;
typedef DListNode *DLinkList;

//****************************建立双循环链表*************************************

DLinkList CreateListR1(){//尾插法建立带头结点的双循环链表，返回双循环链表的头指针
    char ch;
    DLinkList head=(DListNode *)malloc(sizeof(DListNode));  //生成头结点
    DListNode *s,*r;       //工作指针和尾指针
    r=s=head;               //尾指针初值也指向头结点
    while((ch=getchar())!='\n'){
        s=(DListNode *)malloc(sizeof(DListNode));     //生成新结点
        s->data=ch;       //将读入的数据放入新结点的数据域中
        r->next=s;        //连接原链表与新结点
        s->prior=r;
        r=s;              //尾指针移位
    }
    head->prior=s;
    r->next=head;         //终端结点的指针域指向头结点，或空表的头结点指针域指向自身
    return head;
}

//******************************双循环链表的查找运算******************************

DListNode* GetNode(DLinkList head,int i){
    //在带头结点的双循环链表head中查找第i个结点（设头结点为第0个结点）0<=i<=n
    //若找到，则返回该结点的存储位置，否则返回NULL
    int j=0;
    DListNode *p=head;           //从头结点开始扫描
    while(p->next!=head&&j<i){   //顺指针向后扫描，直到p->next为头指针或j=i为止
        p=p->next;
        j++;
    }
    if(j==i)  return p;    //找到了第i个结点
    else return NULL;      //当i<0或0<i<j时，找不到第i个结点
}

DListNode* LocateNode(DLinkList head,Datatype key){
    //在带头结点的双循环链表head中查找其值为key的结点
    //若找到，则返回首次找到的其值为key的结点的存储位置，否则返回头结点地址
    DListNode *p=head->next;   //从开始结点比较。表非空，p初始值指向开始结点
    while(p!=head && p->data!=key){    //直到p为head或p->data为key为止
        p=p->next;             //扫描下一结点
    }
    return p;                  //若p=head，则查找失败，否则p指向值为key的结点
}

//**************************双循环链表的插入与删除运算*****************************

void DInsertList(DLinkList head,Datatype x,int i){
    //将值为x的新结点插入到带头结点的双循环链表head的第i个结点的位置上,1<=i<=n+1
    DListNode *p;
    p=GetNode(head,i-1);     //寻找第i-1个结点p，将新结点插入到结点p之后
    if(p==NULL)              //i<1或i>n+1时插入位置i有错
        printf("Position Error!");
    DListNode *s=(DListNode *)malloc(sizeof(DListNode));    //生成新结点
    s->data=x;               //为新结点赋值
    s->prior=p;              //修改新结点的前趋
    s->next=p->next;         //修改新结点的后继
    p->next->prior=s;        //修改原链表第i个结点的前趋
    p->next=s;               //修改原链表第i-1个结点的后继
}

void DDeleteList(DLinkList head,int i){
    //删除带头结点的双循环链表head上的第i个结点
    //注意：设双循环链表的长度为n，则删去第i个结点仅当1≤i≤n时是合法的
    DListNode *p;
    p=GetNode(head,i);              //找到第i个结点
    if(p==NULL)                     //i<1或i>n时，删除位置错
        printf("Position Error!");
    p->prior->next=p->next;         //修改原链表第i-1个结点的后继
    p->next->prior=p->prior;        //修改原链表第i个结点的前趋
    free(p);                        //释放原链表第i个结点的空间给存储池
}

//*******************************双循环链表的其他函数*********************************
void PrintList(DLinkList head){
    //带头结点的双循环链表head的输出函数
    DListNode *p=head->next;
    while(p!=head){
        printf("%c",p->data);
        p=p->next;
        printf("<->");
    }
    printf("\n");
}

int ListLength(DLinkList head){
    //计算带头结点的双循环链表head的长度
    DListNode *p=head->next;
    int i=0;
    while(p!=head){
        i++;
        p=p->next;
    }
    return i;
}

bool ListEmpty(DLinkList head){
    //判断带头结点的双循环链表head是否是空链表
    //若是空链表则返回true，否则返回false
    if(head->next==head||head->prior==head)
        return true;
    else return false;
}

void DestroyList(DLinkList head){
    //销毁双循环链表head
    DListNode *p;
    while(head){
        p=head->next;
        free(head);
        head=p;
    }
}

//*********************************测试函数****************************************

int main(){
    printf("用尾插法生成双循环链表：\n");
    DLinkList head=CreateListR1();
    PrintList(head);
    if(ListEmpty(head))
        printf("链表是空链表\n");
    else
        printf("链表不是空链表，长度为%d\n",ListLength(head));
    printf("链表第3个位置上的元素是：%c\n",*GetNode(head,3));
    printf("链表在第4个位置上插入元素‘z’后为：\n");
    DInsertList(head,'z',4);
    PrintList(head);
    printf("链表删除第5个位置上元素后为：\n");
    DDeleteList(head,5);
    PrintList(head);
    DestroyList(head);
    return 0;
}
           

测试样例：