Dev - jw

线性结构 - 单向循环链表小结

定义

在单链表的基础上，表的最后一个结点的指针域指向链表头结点，不再是为空，从而得到一种 ”循环性“的单向链表，称为单向循环链表。

  1. 非空表：尾结点的next指向首元结点
  2. 空表：首元结点的next指向本身

C语言结构设计：

/* ElemType是数据类型，具体类型根据实际情况而定，这里假设为int */
typedef int ElemType;

/* 结点类型设计 */
typedef struct Node {
    ElemType data;
    struct Node *next;
}Node, *LinkList;

基本操作（c语言）

以下的所有链表不包含头结点，但并不是说单向循环链表不支持头结点的存在。

因为单向循环链表中如果使用头结点，遍历会比较麻烦，所以直接使用首元结点

1. 构建单向循环链表

构建单向链表常用的两种方法：头插法和尾插法，其中，尾插法更贴近实际输入的效果。

这里采用尾插法构建单向循环链表。

链表的构建

分析：通过单向循环链表图示，在构建单向循环链表有两种情况

  1. 当链表为空表
  2. 当链表为非空表

代码实现：

// 1. 先判断是否是第一次构建，即链表为空表
//  1.1 初始化首元结点，将结点的next指向本身
// 2. 先寻找非空链表的尾结点
//  2.1 将尾结点的next指向新结点，新结点的next指向首元结点

Status initList(LinkList *L) {
    int length = MAXSIZE; // 输入计数

    Node *temp; // 新结点
    Node *last; // 尾结点
    
    while (length--) {
        int item;           // 接收输入的值
        scanf("%d", &item); // 输入
        
        if (*L == NULL) {
            // 链表为空表，初始化新结点，并将结点的next指向自己
            *L = (LinkList)malloc(sizeof(Node));
            if (!*L) {
                return ERROR;
            }
            (*L)->data = item;
            (*L)->next = *L;
        }else {
            // 链表为非空表
            // 寻找尾结点
            for (last = *L; last->next != *L; last=last->next){}
            
            temp = malloc(sizeof(Node));
            if (!temp) {
                return ERROR;
            }
            temp->data = item;
            temp->next = last->next;
            last->next = temp;
        }
    }
    return OK;
}

上面的方法中，寻找尾结点是通过for循环的方式，我们完全可以用一个局部变量来存储尾结点。

修改后的代码：

Status initList2(LinkList *L) {
    int length = MAXSIZE; // 输入计数

    Node *temp; // 新结点
    Node *r = NULL; //局部变量
    
    while (length--) {
        int item;           // 接收输入的值
        scanf("%d", &item); // 输入
        
        if (*L == NULL) {
            // 链表为空表，初始化新结点，并将结点的next指向自己
            *L = (LinkList)malloc(sizeof(Node));
            if (!*L) {
                return ERROR;
            }
            (*L)->data = item;
            (*L)->next = *L;
            // 记录尾结点            
            r = *L;
        }else {
            // 链表为非空表
            temp = malloc(sizeof(Node));
            if (!temp) {
                return ERROR;
            }
            temp->data = item;
            temp->next = r->next;
            r->next = temp;
            // 记录尾结点  
            r = temp;
        }
    }
    return OK;
}

2. 遍历

代码实现：

// 遍历单向循环链表
void traversList(LinkList L) {
    if (L == NULL) {
        printf("当前链表为空！\n");
        return;
    }else {
        Node *temp1 = L;
        
        printf("1.do-while打印\n");
        do {
            printf("%2d", temp1->data);
            temp1 = temp1->next;
        } while (temp1 != L);
        
        printf("\n2.while打印\n");
        printf("%2d", L->data);
        Node *temp2 = L;
        while (temp2 -> next != L) {
            printf("%2d", temp2->next->data);
            temp2 = temp2->next;
        }
        
        printf("\n3.for打印\n");
        printf("%2d", L->data);
        for (Node *dump = L; dump->next != L; dump = dump->next) {
            printf("%2d", dump->next->data);
        }
    }
    printf("\n");
}

输出：

当前链表的值：
1.do-while打印
 1 2 3 4 5
2.while打印
 1 2 3 4 5
3.for打印
 1 2 3 4 5

3. 插入

当新结点插入在首元结点位置时

当新结点插入不在首元结点位置时

代码实现：

// 1. 创建新结点temp
// 2. 首元位置插入，先找到尾结点
//  2.1 将temp的next指向尾结点的next
//  2.2 将尾结点的next指向temp
//  2.3 让头指针指回首元结点
// 3. 不在首元结点位置插入
//  3.1 找到插入位置的结点, 如果超过链表长度，则自动插入到链表尾部
//  3.2 找到插入位置的结点的前驱target, temp->next = target->next
//  3.3 将target的next指向temp

Status insertList(LinkList *L, int index, int value) {
    Node *temp;
    
    // 创建新结点
    temp = malloc(sizeof(Node));
    if (!temp) {
        return ERROR;
    }
    temp->data = value;
    
    // 判断是否是在首元结点位置
    if (index == 1) {
        
        // 找到尾结点
        Node *last;
        for (last = *L; last->next != *L; last = last->next) {
        }
        
        temp->next = last->next;
        last->next = temp; 
        *L = temp; // 头指针指回新结点（首元结点）
    }else {
        
        // 先找到插入的位置，如果超过链表长度，则自动插入表尾
        Node *target = *L;
        for (int i = 1; i != index - 1; i++) {
            if (target->next != *L) {
                // 找到插入位置的前一个结点
                target = target->next;
            }
        }
        temp->next = target->next;
        target->next = temp;
    }
    return OK;
}

4. 删除

当删除位置位于首元结点时
  • 删除后为空表
  • 删除后为非空表

当删除位置不位于首元结点时

代码实现：

Status deletList(LinkList *L, int index) {
    // 首先判断链表是否为空
    if (*L == NULL) {
        printf("当前链表为空!\n");
        return ERROR;
    }
    
    if (index == 1) {
        // 在首元结点删除
    
        // 1. 删除后为空表, 即只有一个结点, 直接释放首元结点
        if ((*L)->next == *L) {
            free(*L);
            return OK;
        }
        
        // 2. 删除后为非空表
        // 2.1 寻找尾结点target
        // 2.2 将target的next指向新的首元结点
        // 2.3 将头指针指向新的首元结点
        // 2.4 释放删除结点
        Node *target;
        for (target = *L; target->next != *L; target = target->next) {
            
        }
        Node *delete = target->next;
        target->next = delete->next;
        *L = delete->next;
        free(delete);
    }else {
        // 在其他位置删除时
        // 1. 先找到删除结点的前驱target
        // 2. 将target的next指向删除结点的next
        // 3. 释放删除结点
        Node *target = *L;
        int i;
        for (i = 1; i != index - 1; i++) {
            if (target->next != *L) {
                // 找到插入位置的前一个结点
                target = target->next;
            }
        }
        
        // 输入位置超过链表的结点个数, 没有找到删除位置时，返回ERROR
        if (i == index - 1 && target->next == *L) {
            return ERROR;
        }
        
        Node *delete = target->next;
        target->next = delete->next;
        free(delete);
    }
    
    return OK;
}

查看demo

单向循环链表 - 相关算法题

  1. 约瑟夫问题
  2. 环形链表