循环单链表及其实现

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

typedef int dataType;

typedef struct linkNode
{
    dataType data;
    struct linkNode *next;
}node,*linkList;

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

// 2.获取循环单链表的尾结点
node *rear(linkList head)
{
    node *p = head;
    while (p)
    {
        if(p->next == head)
            break;
        p = p->next;
    }
    return p;
}

// 3.输出循环单链表各结点的值
void display(linkList head)
{
    node *p = head;
    if(!p)
    {
        printf("循环单链表为空！\n");
        return;
    }
    while (p->next != head)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("%d\n",p->data);
}

// 4.查找值为x的结点
node* findX(linkList head, dataType x)
{
    node *p = head;
    if(!p)
    {
        printf("循环单链表为空！\n");
        return head;
    }
    while (p->next != head)
    {
        if(p->data == x)
            return p;
        p = p->next;
    }
    if(p->data == x)
        return p;
    else return NULL;
}

// 5.查找第i个结点
node *find(linkList head, int i)
{
    node *p = head;
    if(i < 1)
    {
        printf("索引非法！\n");
        return NULL;
    }
    if(!p)
    {
        printf("循环单链表为空！\n");
        return head;
    }
    int j = 1;
    while (p->next != head && i != j)
    {
        p = p->next;
        j++;
    }
    if(i == j)
        return p;
    return NULL;
}

// 6.循环单链表的尾部插入结点
void rearInsert(linkList *head, dataType x)
{
    node *p = *head,*q;
    q = (node*) malloc(sizeof(node));
    q->data = x;
    if(!p)
    {
        q->next = q;
        *head = q;
        return;
    }
    p = rear(*head);
    p->next = q;
    q->next = *head;
}

// 7.在循环单链表的第i个位置后插入元素x
void insert(linkList *head, int i, dataType x)
{
    if(i < 0)
    {
        printf("非法的插入位置，无法插入！\n");
        return;
    }
    node *p = *head,*q,*r;
    q = (node*) malloc(sizeof(node));
    q->data = x;
    if(i == 0) // 当要在链表最前方插入时
    {
        if(!p) // 链表为空时
        {
            *head = q;
            (*head)->next = *head;
            return;
        } // 链表非空时
        r = rear(*head); // 找到尾结点
        q->next = *head;
        r->next = q;
        *head = q;
        return;
    }
    p = find(*head,i); // 其他位置插入则需要找到插入位置
    if(!p)
        printf("非法的位置，无法插入！\n");
    else
    {
        if(p->next == (*head)) // 如果在尾结点后插入
        {
            p->next = q;
            q->next = *head;
            return;
        }
        q->next = p->next; // 中间的位置插入
        p->next = q;
    }
}

// 6.删除循环单链表中值为x的元素
void del(linkList *head, dataType x)
{
    node *p = *head,*q;
    if(!p)
    {
        printf("链表为空，无法删除！\n");
        return;
    }
    p = findX(p,x);
    if(!p)
    {
        printf("未找到这样的结点，无法删除！\n");
        return;
    }
    if((*head)->next == *head) // 只有一个结点时
    {
        free(p);
        *head = NULL;
        return;
    }
    if(p->next == *head) // 如果是删除最后一个结点
    {
        if(p == (*head)->next) // 只有两个结点时
        {
            (*head)->next = *head;
            free(p);
        } else // 多于两个结点时
        {
           p->data = p->next->data;
           q = p->next;
           p->next = p->next->next;
           *head = p;
           free(q);
            return;
        }
    } else
    {
        p->data = p->next->data; // 中间结点的删除
        q = p->next;
        p->next = p->next->next;
        free(q);
    }
}

int main()
{
    linkList list; // 声明循环单链表
    init(&list); // 初始化空的不带头结点的循环单链表
    display(list); // 输出单链表
    for (int i = 1; i <= 5; i++)
        rearInsert(&list,i);
    display(list);
    int i = 5;
    node *n = find(list,i); // 查找第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;
}