线性表-单向循环链表

单向循环链表

单向循环链表示意图如下：

单向循环链表空表.jpg 单向循环链表非空表.jpg

数据结构定义（同普通链表）

typedef int Status;
typedef int ElemType;

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

单向循环链表初始化与赋值

Status CreateList(LinkList *list) {
    int item;
    LinkList tmp;
    LinkList target;
    printf("请输入节点的值，输入0结束\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) {
            break;
        }
        
        if (NULL == *list) {
            *list = (LinkList)malloc(sizeof(Node));
            if (NULL == list) {
                return ERROR;
            }
            (*list)->data = item;
            (*list)->next = *list;
        } else {
            for (target = *list; target->next != *list; target = target->next);
            tmp = (LinkList)malloc(sizeof(Node));
            if (!tmp) {
                return ERROR;
            }
            tmp->data = item;
            tmp->next = *list;
            target->next = tmp;
        }
    }
    return OK;
}

在上面循环遍历查找尾节点的基础上，优化算法，可以在每次插入的时候记录下当前尾节点的位置。

Status CreateList2(LinkList *list) {
    int item;
    LinkList tmp;
    LinkList rear = NULL;
    printf("请输入节点的值，输入0结束\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) {
            break;
        }
        
        if (NULL == *list) {
            *list = (LinkList)malloc(sizeof(Node));
            if (NULL == list) {
                return ERROR;
            }
            (*list)->data = item;
            (*list)->next = *list;
            rear = *list;
        } else {
            tmp = (LinkList)malloc(sizeof(Node));
            if (!tmp) {
                return ERROR;
            }
            tmp->data = item;
            tmp->next = *list;
            rear->next = tmp;
            rear = tmp;
        }
    }
    return OK;
}

单向循环链表插入

Status insert(LinkList *list, int place, int num) {
    LinkList node = malloc(sizeof(Node));
    node->data = num;
    LinkList target;
    if (1 == place) {
        for (target = *list; target->next != *list; target = target->next);
        node->next = *list;
        target->next = node;
        *list = node;
    } else {
        int i;
        for (i = 1, target = *list; target->next != *list && i < place -1; target = target->next,i++);
        node->next = target->next;
        target->next =node;
    }
    return OK;
}

单向循环链表删除

Status deleteItem(LinkList *list, int i) {
    LinkList target, tmp;
    if (1 == i) {
        if ((*list)->next == *list) {
            *list = NULL;//free(*list);why?
        } else {
            for (target = *list; target->next != *list; target = target->next);
            tmp = *list;
            target->next = (*list)->next;
            *list = target->next;
            free(tmp);
        }
    } else {
        int j;
        for ( j = 1,target = *list; j < i-1; j++, target = target->next);
        tmp = target->next;
        target->next = tmp->next;
        free(tmp);
    }
    return OK;
}

单向循环链表打印输出

void Print(LinkList list) {
    LinkList node = list;
    if (node) {
        do {
            printf("%d\n",node->data);
            node = node->next;
        } while (node != list);
    } else {
        printf("没有元素\n");
    }
}

附上算法图解如下：

• 单向循环链表的初始化，使用尾插的方式来进行实现，并且分空表时候，和非空表时候插入两种情况。

  
  单链表空表创建.jpg

插入第一个结点.jpg 插入其它结点.jpg

• 在单向循环链表中，插入一个新的结点时候，分两种情况：1.插在第一个位置；2.插在其他位置，因为第一个位置需要找到尾指针，其他结点是找到插入位置的前一个结点，来进行指针域的操作。

  
  插入位置再首元结点.jpg

其他位置插入.jpg 其他位置插入.jpg

总结：单向循环链表的操作，由于尾结点指针指向在首元结点，插入和删除的时候注意分情况考虑。