数据结构与算法03——单向循环链表

一、概述
链表属于线性表，包括三个部分：数据域、指针域、连续性；

• 数据域：存储需要保存的数据
• 指针域：各个节点之间的连接
• 连续性：链表在逻辑上是连续的，但物理上未必连续

链表分类：单向链表、双向链表、循环链表

单向链表VS单向循环链表

• 单向链表

  
  
  image.png

• 单向循环链表

  
  
  image.png

二者的区别：单向链表最后结点的指针域next设置为null，而单向循环链表最后一个结点指针域next重新指向它第一个首元结点的位置

二、单向循环列表的结构体设计
单向链表

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

typedef struct Node * NodeList;

单向循列表的创建

Status CreateNodeList(NodeList *L) {
    int item;
    NodeList temp = NULL;
    NodeList target = NULL;
    printf("Enter the value of the node, at the end  enter 0\n");
    while (1) {
        scanf("%d", &item);
        if (item == 0) {
         break;
        }
   
        if (*L == NULL) {
            *L = (LinkList)malloc(sizeof(Node));
            if (!L) exit(0);
            (*L)->data = item;
            (*L)->next = *L;
            target = *L;
        } else {
            temp = (LinkList)malloc(sizeof(Node));
            if (temp == NULL) return ERROR;
            temp->data = item;
            temp->next = *L;
            target->next = temp;
            target = temp;
        }
    }
    
    return OK;
}

判断是否第一次创建的链表：
是：创建一个新结点,使新结点的next 指向自身；
否：找链表尾结点,将尾结点的next指向新结点. 新结点的next指向(*L);

单向循环链表 ： 插入
···
Status LinkListInsert(LinkList *L, int place, int num) {
LinkList temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) return ERROR;
temp->data = num;

LinkList target;
if (place == 1) {
    for (target = *L; target->next != *L; target = target->next);
    temp->next = *L;
    target->next = temp;
    *L = temp;
} else {
    int i;
    for (target = *L, i = 1; target->next != *L && i != place - 1; target = target->next, i++);
    temp->next = target->next;
    target->next = temp;
}
return OK;

}
···
插入数据， 需要注意插入的位置是否在首元结点上。

单向循环链表 ： 删除
···
Status LinkListDelete(LinkList L, int place) {
if (L == NULL) return ERROR;

LinkList temp, target;
if (place == 1) {
    if ((*L)->next == *L) {
        *L = NULL;
        return OK;
    }
    for (target = *L; target->next != *L; target = target->next);
    temp = *L;
    *L = (*L)->next;
    target->next = *L;
    free(temp);
} else {
    int i;
    for (target = *L, i = 1; target->next != *L && i != place - 1; target = target->next, i++);
    temp = target->next;
    target->next = temp->next;
    free(temp);
}

return OK;

}
···

需要注意：

• 删除的位置在首元结点上；
• 链表只剩下一个节点时；

单向循环链表 ： 查询

int LocateElem(LinkList L, int value) {
    int i = 1;
    LinkList p = L;
    while (p->data != value && p->next != L) {
        i++;
        p = p->next;
    }
    if (p->next == L && p->data != value) {
        return -1;
    }
    return i;
}