简介

链表是线性表，包括两个部分：数据域、指针域；

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

链表主要有单向链表，双向链表，循环链表

单向链表与单向循环链表对比：

• 单向链表

  
  
  2020-04-03 13.52.57.gif

• 单向循环链表

  
  
  WX20200403-135743.png

与单向链表区别之处在于单向链表的最后的结点的指针域 next 是设置为 null. 但是单向循环链表最后一个结点是重新指向它的第一个首元结点的位置;

单向循环链表结构体设计

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

typedef struct Node * LinkList;

单向链表的创建

判断是否是第一次创建链表：

• YES：创建一个新结点,并使得新结点的next 指向自身；
• NO：找链表尾结点,将尾结点的next指向新结点. 新结点的next指向(*L);

Status CreateLinkList(LinkList *L) {
    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("Enter the value of the node and end when you 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;
}

单向循环链表 ---- 插入

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

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;
}

Demo：https://github.com/ShoukaiWang/DataStructuresAndAlgorithms