循环双链表的实现和相关操作

#include <stdio.h>
#include <stdlib.h>

typedef int dataType;

// 3.8.11 循环双链表
typedef struct dLinkNode
{
    dataType data;
    struct dLinkNode *lLink,*rLink;
}dNode,*dLinkList;

// 1.初始化不带头结点的循环双链表
void init(dLinkList *head)
{
    *head = NULL;
}

// 2.输出双链表各结点的值
void display(dLinkList head)
{
    dNode *p = head;
    if(!p)
    {
        printf("双链表为空！\n");
        return;
    }
    do{
        printf("%d ",p->data);
        p = p->rLink;
    } while (p != head);
    printf("\n");
}

// 3.查找双链表中第i个结点
dNode *find(dLinkList head, int i)
{
    dNode *p = head;
    if(i < 1)
    {
        printf("非法的索引！\n");
        return NULL;
    }
    if(!p)
    {
        printf("双链表为空！\n");
        return NULL;
    }
    if(i == 1)
        return p;
    int j = 1;
    do {
        p = p->rLink; // 向后遍历直到末尾
        j++;
    }while (p->rLink != head && i != j);
    if(i > j)
        return NULL;
    return p;
}

// 5.在双链表尾部插入值为x的结点
void rearInsert(dLinkList *head, dataType x)
{
    dNode *q = (dNode*) malloc(sizeof(dNode));
    q->data = x;
    if(!*head) // 链表为空时
    {
        *head = q;
        q->lLink = q->rLink =  q;
    } else
    {
        (*head)->lLink->rLink = q; // 插入新结点
        q->rLink = *head;
        q->lLink = (*head)->lLink;
        (*head)->lLink = q;
    }
}

// 6.在双链表的第i个结点后插入值为x的新结点
void insert(dLinkList *head, int i, dataType x)
{
    if(i < 0)
    {
        printf("非法的插入位置！\n");
        return;
    }
    dNode *p, *q = (dNode*) malloc(sizeof(dNode));
    q->data = x;
    if(i == 0) // 在表头插入
    {
        if(*head) // 链表非空时
        {
            q->rLink = *head;
            q->lLink = (*head)->lLink;
            (*head)->lLink->rLink = q;
            (*head)->lLink = q;
        } else
            q->lLink = q->rLink =  q;
        *head = q;
        return;
    }
    p = find(*head,i);
    if(p)
    {
        if(p->rLink == *head) // 如果p是尾结点
        {
            (*head)->lLink->rLink = q; // 插入新结点
            q->rLink = *head;
            q->lLink = (*head)->lLink;
            (*head)->lLink = q;
        } else
        {
            q->lLink = p;
            q->rLink = p->rLink;
            p->rLink->lLink = q;
            p->rLink = q;
        }
    } else
        printf("插入索引越界！\n");
}

// 7.双链表中删除一个值为x的结点
void del(dLinkList *head, dataType x)
{
    dNode *p = *head;
    if(!p)
    {
        printf("链表为空，无法删除！\n");
        return;
    }
    if(p->data == x) // 首结点特殊处理
    {
        if(p->rLink == *head) // 只有一个结点时
            *head = NULL;
        else
        {
            p->rLink->lLink = p->lLink;
            p->lLink->rLink = p->rLink;
            (*head) = p->rLink; // 更新头指针
        }
        free(p);
        return;
    }
    do {
        p = p->rLink; // 向后找到x结点
    } while (p != *head && p->data != x);
    if(p == *head) // 表示循环回到头结点
    {
        printf("没有找到这样的结点，无法删除！\n");
    } else
    {
        if(p->rLink == *head) // 需要删除的是尾结点
        {
            p->lLink->rLink = *head;
            (*head)->lLink = p->lLink;
        } else
        {
            p->lLink->rLink = p->rLink;
            p->rLink->lLink = p->lLink;
        }
        free(p);
    }
}

int main()
{
    dLinkList list; // 声明指向双链表的头指针
    init(&list); // 初始化双链表
    for (int i = 1; i <= 5; i++)
        rearInsert(&list,i); // 插入结点
    display(list); // 输出双链表
    int i = 5;
    dNode *n = find(list,i);
    if(n)
        printf("链表的第%d个元素是%d\n",i,n->data);
    else
        printf("链表访问越界！\n");
    dataType x = 6;
    printf("在第%d个位置后面插入元素%d\n",i,x);
    insert(&list,i,x);
    display(list);
    printf("删除一个值为%d的元素\n",x);
    del(&list,x);
    display(list);
    return 0;
}