首页 > 其他分享 >数据结构——单向循环链表

数据结构——单向循环链表

时间：2024-07-06 16:56:07浏览次数：14  
标签：head 单向 list next 链表 数据结构 节点 size

文章目录

1. 概念

2. 区别

2.1 结构区别

2.2 访问方式区别

2.3 优缺点对比

3. 流程

4. 基本操作

5. 代码示例

1. 概念

单向循环链表是一种特殊的单链表，其中最后一个节点的后继指针指向头节点，形成一个环。单向循环链表适合用于需要循环访问数据的场景，如约瑟夫环问题。

节点定义

每个节点包含两个部分：数据域和指针域。

typedef struct Node {
    int data;           // 数据域，存储节点的值
    struct Node *next;  // 指针域，指向下一个节点
} Node;

结构定义

单向循环链表包含一个头指针和链表中的节点个数。

typedef struct {
    Node *head; // 指向单向循环链表的头节点
    size_t size; // 单向循环链表中的节点个数
} CircularLinkedList;

2. 区别

单向链表和单向循环链表的区别

2.1 结构区别

单向链表（Singly Linked List）：

  • 每个节点包含一个数据域和一个指向下一个节点的指针。
  • 最后一个节点的指针指向 NULL，表示链表的结束。
  • 只能单向遍历，从头节点开始到尾节点结束。

单向循环链表（Singly Circular Linked List）：

  • 每个节点也包含一个数据域和一个指向下一个节点的指针。
  • 最后一个节点的指针指向头节点，形成一个循环。
  • 可以从链表中的任何一个节点开始遍历，最终会回到该节点。

2.2 访问方式区别

单向链表：

  • 从头节点开始遍历，直到找到目标节点或者到达链表末尾。

单向循环链表：

  • 从任意节点开始遍历，最终会回到该节点，因此在循环中进行操作时更加方便。

2.3 优缺点对比

单向链表的优缺点

优点：

  1. 实现简单：实现和维护相对简单，每个节点只包含一个指针。
  2. 内存开销小：每个节点只包含一个指针，内存占用较少。
  3. 插入和删除操作效率较高：在已知前驱节点的情况下，插入和删除节点的时间复杂度为 O(1)。

缺点：

  1. 只能单向遍历：不能从尾节点向前遍历到头节点，灵活性差。
  2. 查找效率较低：从头节点遍历到目标节点的时间复杂度为 O(n)。

单向循环链表的优缺点

优点：

  1. 循环访问方便：适合需要循环访问数据的应用场景，如约瑟夫环问题。
  2. 无需处理链表末尾：由于最后一个节点指向头节点，不需要特殊处理链表末尾的情况。

缺点：

  1. 实现和维护复杂：插入和删除操作需要特别注意尾节点和头节点之间的关系。
  2. 查找效率较低：和单向链表一样，需要遍历链表才能找到特定节点，时间复杂度为 O(n)。

3. 流程

初始化单向循环链表：

  • 设置头指针为NULL。
  • 设置节点个数为0。

插入新节点：

  • 判断插入位置是否是0。
  • 如果是0，进一步判断链表是否为空：
    • 如果链表为空，新节点指向自己，头指针指向新节点。
    • 如果链表不为空，找到尾节点，新节点指向头节点，头指针指向新节点，尾节点指向新节点。
  • 如果插入位置不是0，找到插入位置的前一个节点，新节点指向前一个节点的后继节点，前一个节点指向新节点。
  • 节点个数加1。

删除节点：

  • 判断删除位置是否是0。
  • 如果是0，保存头节点，进一步判断链表是否只有一个节点：
    • 如果链表只有一个节点，头指针置为NULL。
    • 如果链表有多个节点，找到尾节点，头指针指向头节点的后继节点，尾节点指向新头节点。
  • 如果删除位置不是0，找到删除位置前一个节点，保存要删除的节点，前一个节点指向要删除节点的后继节点。
  • 释放被删除的节点，节点个数减1。

获取指定位置的元素：

  • 判断索引是否合法，如果不合法返回无效索引。
  • 从头节点开始遍历，遍历到目标位置节点，返回节点数据。

修改指定位置的元素：

  • 判断索引是否合法，如果不合法忽略位置。
  • 从头节点开始遍历，遍历到目标位置节点，修改节点数据。

释放单向循环链表内存：

  • 判断链表是否为空，如果为空直接返回。
  • 从头节点开始遍历，保存下一个节点，释放当前节点，继续遍历，直到回到头节点。
  • 头指针置为NULL，节点个数置为0。

 

4. 基本操作

初始化单向循环链表

void initCircularLinkedList(CircularLinkedList *list) {
    list->head = NULL; // 初始化头节点为空
    list->size = 0;    // 初始化节点个数为0
}
  • 功能：初始化一个空的单向循环链表。
  • 参数：CircularLinkedList *list，指向需要初始化的链表结构。
  • 操作：
    • 将链表的头节点指针 head 设置为 NULL。
    • 将链表的节点个数 size 设置为 0。

 

插入节点

在单向循环链表的指定位置插入新节点。

void insertAt(CircularLinkedList *list, size_t index, int element) {
    if (index > list->size) {
        return; // 忽略无效的插入位置
    }

    Node *newNode = (Node *)malloc(sizeof(Node)); // 创建新节点
    newNode->data = element;

    if (index == 0) { // 插入位置是头节点
        if (list->head == NULL) { // 如果链表为空
            newNode->next = newNode;
            list->head = newNode;
        } else {
            Node *tail = list->head;
            while (tail->next != list->head) {
                tail = tail->next;
            }
            newNode->next = list->head;
            list->head = newNode;
            tail->next = newNode;
        }
    } else {
        Node *prevNode = list->head;
        for (size_t i = 0; i < index - 1; i++) {
            prevNode = prevNode->next;
        }
        newNode->next = prevNode->next;
        prevNode->next = newNode;
    }

    list->size++; // 更新节点个数
}
  • 功能：在指定位置插入新节点。
  • 参数：
    • CircularLinkedList *list，指向链表结构。
    • size_t index，插入位置的索引。
    • int element，插入节点的值。
  • 操作：
    • 检查插入位置是否合法，如果不合法则直接返回。
    • 创建一个新节点并赋值。
    • 如果插入位置是头节点：
      • 如果链表为空，直接将新节点的 next 指针指向自己，并将 head 指针指向新节点。
      • 如果链表不为空，找到尾节点，更新尾节点和新节点的指针，使新节点成为头节点。
    • 如果插入位置不是头节点，找到插入位置的前一个节点，更新前一个节点和新节点的指针，使新节点插入到指定位置。
    • 更新链表的节点个数。

 

删除节点

删除指定位置的节点并返回被删除的元素。

int deleteAt(CircularLinkedList *list, size_t index) {
    if (index >= list->size) {
        return -1; // 忽略无效的删除位置
    }

    int deletedElement;

    if (index == 0) { // 删除位置是头节点
        Node *temp = list->head;
        if (list->head->next == list->head) { // 如果链表只有一个节点
            list->head = NULL;
        } else {
            Node *tail = list->head;
            while (tail->next != list->head) {
                tail = tail->next;
            }
            list->head = temp->next;
            tail->next = list->head;
        }
        deletedElement = temp->data;
        free(temp); // 释放被删除节点的内存
    } else {
        Node *prevNode = list->head;
        for (size_t i = 0; i < index - 1; i++) {
            prevNode = prevNode->next;
        }
        Node *temp = prevNode->next;
        prevNode->next = temp->next;
        deletedElement = temp->data;
        free(temp); // 释放被删除节点的内存
    }

    list->size--; // 更新节点个数
    return deletedElement;
}
  • 功能：删除指定位置的节点并返回被删除的节点的值。
  • 参数：
    • CircularLinkedList *list，指向链表结构。
    • size_t index，删除位置的索引。
  • 操作：
    • 检查删除位置是否合法，如果不合法则返回 -1。
    • 如果删除位置是头节点：
      • 如果链表只有一个节点，将 head 指针置为 NULL。
      • 如果链表有多个节点，找到尾节点，更新尾节点和头节点的指针，使头节点指向下一个节点。
      • 释放被删除节点的内存，返回被删除节点的值。
    • 如果删除位置不是头节点，找到删除位置的前一个节点，更新前一个节点和下一个节点的指针，删除指定位置的节点。
    • 更新链表的节点个数，返回被删除节点的值。

获取节点

// 获取指定位置的元素
int getElementAt(const CircularLinkedList *list, size_t index) {
    if (index >= list->size) {
        return -1; // 返回无效的索引
    }

    Node *currentNode = list->head;
    for (size_t i = 0; i < index; i++) {
        currentNode = currentNode->next;
    }

    return currentNode->data; // 返回指定位置的元素
}
  • 功能：获取指定位置的节点值。
  • 参数：
    • const CircularLinkedList *list，指向链表结构。
    • size_t index，目标位置的索引。
  • 操作：
    • 检查索引是否合法，如果不合法则返回 -1。
    • 从头节点开始遍历，直到找到目标位置的节点。
    • 返回目标位置节点的值。

修改节点

// 修改指定位置的元素
void modifyAt(CircularLinkedList *list, size_t index, int newValue) {
    if (index >= list->size) {
        return; // 忽略无效的修改位置
    }

    Node *currentNode = list->head;
    for (size_t i = 0; i < index; i++) {
        currentNode = currentNode->next;
    }

    currentNode->data = newValue; // 修改节点的值
}
  • 功能：修改指定位置的节点值。
  • 参数：
    • CircularLinkedList *list，指向链表结构。
    • size_t index，目标位置的索引。
    • int newValue，新值。
  • 操作：
    • 检查索引是否合法，如果不合法则直接返回。
    • 从头节点开始遍历，直到找到目标位置的节点。
    • 修改目标位置节点的值。

打印所有元素

void printCircularLinkedList(const CircularLinkedList *list) {
    if (list->head == NULL) {
        printf("链表为空\n");
        return;
    }
    Node *currentNode = list->head;
    do {
        printf("%d ", currentNode->data);
        currentNode = currentNode->next;
    } while (currentNode != list->head);
    printf("\n");
}
  • 功能：打印单向循环链表中的所有节点值。
  • 参数：const CircularLinkedList *list，指向需要打印的链表结构。
  • 操作：
    • 如果链表为空，打印“链表为空”并返回。
    • 从头节点开始遍历，每次打印当前节点的值。
    • 继续遍历，直到回到头节点。

 

释放单向循环链表的内存

void destroyCircularLinkedList(CircularLinkedList *list) {
    if (list->head == NULL) {
        return;
    }
    Node *currentNode = list->head;
    Node *nextNode;
    do {
        nextNode = currentNode->next;
        free(currentNode);
        currentNode = nextNode;
    } while (currentNode != list->head);

    list->head = NULL;
    list->size = 0;
}
  • 功能：释放单向循环链表中所有节点的内存。
  • 参数：CircularLinkedList *list，指向需要释放的链表结构。
  • 操作：
    • 如果链表为空，直接返回。
    • 从头节点开始遍历，每次保存当前节点的下一个节点的指针，释放当前节点的内存。
    • 继续遍历，直到回到头节点。
    • 将链表的头节点指针 head 置为 NULL，将链表的节点个数 size 置为 0。

5. 代码示例

以下是一个完整的单向循环链表实现代码，包括初始化、插入、删除、获取和修改元素，以及释放链表的内存的所有基本操作：

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

// 单向循环链表节点结构定义
typedef struct Node {
    int data;           // 节点存储的数据
    struct Node *next;  // 指向下一个节点的指针
} Node;

// 单向循环链表结构定义
typedef struct {
    Node *head;         // 单向循环链表头节点指针
    size_t size;        // 单向循环链表中的节点个数
} CircularLinkedList;

// 初始化单向循环链表
void initCircularLinkedList(CircularLinkedList *list) {
    list->head = NULL; // 初始化头节点为空
    list->size = 0;    // 初始化节点个数为0
}

// 在指定位置插入元素
void insertAt(CircularLinkedList *list, size_t index, int element) {
    if (index > list->size) {
        return; // 忽略无效的插入位置
    }

    Node *newNode = (Node *)malloc(sizeof(Node)); // 创建新节点
    newNode->data = element;

    if (index == 0) { // 插入位置是头节点
        if (list->head == NULL) { // 如果链表为空
            newNode->next = newNode;
            list->head = newNode;
        } else {
            Node *tail = list->head;
            while (tail->next != list->head) {
                tail = tail->next;
            }
            newNode->next = list->head;
            list->head = newNode;
            tail->next = newNode;
        }
    } else {
        Node *prevNode = list->head;
        for (size_t i = 0; i < index - 1; i++) {
            prevNode = prevNode->next;
        }
        newNode->next = prevNode->next;
        prevNode->next = newNode;
    }

    list->size++; // 更新节点个数
}

// 删除指定位置的元素并返回被删除的元素
int deleteAt(CircularLinkedList *list, size_t index) {
    if (index >= list->size) {
        return -1; // 忽略无效的删除位置
    }

    int deletedElement;

    if (index == 0) { // 删除位置是头节点
        Node *temp = list->head;
        if (list->head->next == list->head) { // 如果链表只有一个节点
            list->head = NULL;
        } else {
            Node *tail = list->head;
            while (tail->next != list->head) {
                tail = tail->next;
            }
            list->head = temp->next;
            tail->next = list->head;
        }
        deletedElement = temp->data;
        free(temp); // 释放被删除节点的内存
    } else {
        Node *prevNode = list->head;
        for (size_t i = 0; i < index - 1; i++) {
            prevNode = prevNode->next;
        }
        Node *temp = prevNode->next;
        prevNode->next = temp->next;
        deletedElement = temp->data;
        free(temp); // 释放被删除节点的内存
    }

    list->size--; // 更新节点个数
    return deletedElement;
}

// 获取指定位置的元素
int getElementAt(const CircularLinkedList *list, size_t index) {
    if (index >= list->size) {
        return -1; // 返回无效的索引
    }

    Node *currentNode = list->head;
    for (size_t i = 0; i < index; i++) {
        currentNode = currentNode->next;
    }

    return currentNode->data; // 返回指定位置的元素
}

// 修改指定位置的元素
void modifyAt(CircularLinkedList *list, size_t index, int newValue) {
    if (index >= list->size) {
        return; // 忽略无效的修改位置
    }

    Node *currentNode = list->head;
    for (size_t i = 0; i < index; i++) {
        currentNode = currentNode->next;
    }

    currentNode->data = newValue; // 修改节点的值
}

// 释放单向循环链表内存
void destroyCircularLinkedList(CircularLinkedList *list) {
    if (list->head == NULL) {
        return;
    }
    Node *currentNode = list->head;
    Node *nextNode;
    do {
        nextNode = currentNode->next;
        free(currentNode);
        currentNode = nextNode;
    } while (currentNode != list->head);

    list->head = NULL;
    list->size = 0;
}

// 打印单向循环链表中的所有元素
void printCircularLinkedList(const CircularLinkedList *list) {
    if (list->head == NULL) {
        printf("链表为空\n");
        return;
    }
    Node *currentNode = list->head;
    do {
        printf("%d ", currentNode->data);
        currentNode = currentNode->next;
    } while (currentNode != list->head);
    printf("\n");
}

// 主函数测试单向循环链表操作
int main() {
    CircularLinkedList myList; // 声明单向循环链表

    initCircularLinkedList(&myList); // 初始化单向循环链表
    printf("初始化单向循环链表成功!\n");

    insertAt(&myList, 0, 1); // 在索引0处插入元素1
    insertAt(&myList, 1, 2); // 在索引1处插入元素2
    insertAt(&myList, 2, 3); // 在索引2处插入元素3
    printf("向单向循环链表插入了3个元素\n");
    printCircularLinkedList(&myList); // 打印链表中的元素

    printf("单向循环链表长度为: %zu\n", myList.size); // 获取单向循环链表长度

    insertAt(&myList, 1, 4); // 在索引1处插入元素4
    printf("在索引1处插入元素4\n");
    printCircularLinkedList(&myList); // 打印链表中的元素

    printf("单向循环链表长度为: %zu\n", myList.size); // 再次获取单向循环链表长度

    printf("删除索引1处的元素,该元素值是: %d\n", deleteAt(&myList, 1)); // 删除索引1处的元素
    printCircularLinkedList(&myList); // 打印链表中的元素

    destroyCircularLinkedList(&myList); // 销毁单向循环链表
    printf("单向循环链表销毁成功!\n");

    return 0;
}

标签：head,单向,list,next,链表,数据结构,节点,size
From： https://blog.csdn.net/TENET123/article/details/140191098

相关文章

  • 数据结构小学期第六天
    今天完全实现了九宫格拼图游戏，具备一键通关功能按下W键，查看原图功能按住A键不松，移动图片按上下左右键，如果你自己想要实现这个功能，需要自己的图片，图片格式要求。每个小图片是105*105，完整图片是315*315.有人想要做一下，可以试一试。代码如下启动类1importcom.itheima.ui.GameJ......
  • 【数据结构】栈和队列
    文章目录1.栈1.1栈的概念及结构1.2栈的实现2.队列2.1队列的概念及结构2.2队列的实现3.栈和队列面试题4.概念选择题1.栈1.1栈的概念及结构栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈......
  • 代码随想录算法训练营第二天 | 203.移除链表元素 707.设计链表 206.反转链表
    代码随想录算法训练营第二天|203.移除链表元素707.设计链表206.反转链表进入链表章节，就要和虚拟头结点（dummyhead）打交道了，还要注意边界条件和空指针异常移除链表元素题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A......
  • 一种尽可能减小内存占用的数据结构设计方法
         背景：以三维点为例，随着采集设备的日新月异，三维点的属性信息也越来越多（例如颜色、强度、回波信息、gps时间等）；导致点云数据在处理时加载到计算机中所需要的内存空间也越来越大，但是有些数据往往只有x、y、z三个坐标值，则不需要为其开辟多余的内存空间，那一套统一的数据结......
  • pwn的linux基础（计算机内部数据结构存储形式）
    linux基础保护层级:分为四个ring0-ring3一般来说就两个，0和30为内核3为用户 权限:用户分为多个组文件和目录等等的权限一般都是三个，即可读可写可执行。读:R，写:W，执行:X赋予一个可执行文件执行权限就是chmod+xfilename虚拟内存和物理内存：物理内存很直白，就是内存......
  • 「代码随想录算法训练营」第四天 | 链表 part2
    24.两两交换链表中的节点题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/题目难度：中等文章讲解：https://programmercarl.com/0024.两两交换链表中的节点.html#算法公开课视频讲解：https://www.bilibili.com/video/BV1YT411g7br题目状态：有思路，但细节缺乏考虑个......
  • 代码随想录算法训练营第3天 | 链表删除元素
    删除链表元素，技巧是设置一个虚拟头节点，这样就可以把原始头节点当做普通节点处理了，最后再返回虚拟头结点的next即可。题203.移除链表元素/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*......
  • 代码随想录刷题day 3 | 链表理论基础 203.移除链表元素 707.设计链表 206.反转链
    203.移除链表元素classSolution{publicListNoderemoveElements(ListNodehead,intval){ListNodevirHead=newListNode(0,head);ListNodetmp=virHead;while(tmp.next!=null){if(tmp.next.val==val){......
  • 代码随想录算法训练营第3天| 203.移除链表元素 ，707.设计链表 ，206.反转链表
    学习任务：链表理论基础Leetcode203.移除链表元素Leetcode707.设计链表Leetcode206.反转链表Leetcode203.移除链表元素难度：简单|相关标签：递归、链表题目：给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val==val的节点，并返回新的头节......
  • python数据结构（树和二叉树）
    树非线性结构一对多根结点（无前驱）多个叶子结点（无后继）其他数据元素（一个前驱，多个后驱）树与二叉树转换树与二叉树均可用二叉链表作为存储结构，则以二叉链表为媒介可导出树之间的一个对应关系-----即给定一颗树，可以找到唯一一颗二叉树与之对应。把树转化为二叉树步骤一：加线......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99