【数据结构】线性表（三）循环链表的各种操作（创建、插入、查找、删除、修改、遍历打印、释放内存空间）

news/2024/10/18 16:55:34/

目录

线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

四、线性表的链接存储结构

1. 单链表

2. 循环链表

a. 循环链表节点结构体

b. 创建新节点

c. 在循环链表末尾插入节点

d. 删除循环链表中指定值的节点

e. 在循环链表中查找指定值的节点

f. 修改循环链表中指定节点的值

g. 打印循环链表

h. 释放循环链表内存空间

i. 主函数

j. 代码整合

线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

一个线性表是由零个或多个具有相同类型的结点组成的有序集合。

         按照线性表结点间的逻辑顺序依次将它们存储于一组地址连续的存储单元中的存储方式被称为线性表的顺序存储方式。按顺序存储方式存储的线性表具有顺序存储结构，一般称之为顺序表。换言之，在程序中采用定长的一维数组，按照顺序存储方式存储的线性表，被称为顺序表。

【数据结构】线性表（一）线性表的定义及其基本操作（顺序表插入、删除、查找、修改）-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/m0_63834988/article/details/132089038?spm=1001.2014.3001.5501

四、线性表的链接存储结构

1. 单链表

    顺序表的优点是存取速度快。但是，无论是插入一个结点，还是删除一个结点，都需要调整一批结点的地址。要克服该缺点，就必须给出一种不同于顺序存储的存储方式。用链接存储方式存储的线性表被称为链表，可以克服上述缺点。

        链表中的结点用存储单元（若干个连续字节）来存放，存储单元之间既可以是（存储空间上）连续的，也可以是不连续的，甚至可以零散地分布在存储空间中的任何位置。换言之，链表中结点的逻辑次序和物理次序之间并无必然联系。最重要的是，链表可以在不移动结点位置的前提下根据需要随时添加删除结点，动态调整。

【数据结构】线性表（二）单链表及其基本操作（创建、插入、删除、修改、遍历打印）-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/m0_63834988/article/details/133914875?spm=1001.2014.3001.5501

2. 循环链表

        从单链表的一个结点出发，只能访问到链接在它后面的结点，而无法访问位于它前面的结点，这对一些实际应用很不方便。解决的办法是把链接结构“循环化”，即把表尾结点的next域存放指向哨位结点的指针，而不是存放空指针NULL，这样的单链表被称为循环链表。循环链表使用户可以从链表的任何位置开始，访问链表中的任意结点。

a. 循环链表节点结构体

typedef struct Node {int data;           // 数据域struct Node *next;  // 指针域
} Node;

        包含一个整型数据域 data 和一个指向下一个节点的指针域 next。

b. 创建新节点

Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;
}
  • 创建一个新的节点并返回指向该节点的指针：
    • 使用 malloc 分配了节点的内存空间；
    • 将传入的数据赋值给节点的 data 字段，并将 next 字段设置为 NULL。

c. 在循环链表末尾插入节点

void insert(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;(*head)->next = *head;  // 将尾节点指向头节点，形成循环} else {Node* temp = *head;while (temp->next != *head) {temp = temp->next;}temp->next = newNode;newNode->next = *head;}
}
  • 调用 createNode 函数创建一个新节点，并将新节点的指针保存在 newNode 中。
  • 检查链表是否为空
    • 如果为空，则将 head 指向新节点，并将新节点的指针域 next 设置为指向自己，这样形成一个只有一个节点的循环链表。
    • 如果链表不为空，遍历链表找到尾节点，将尾节点的指针域 next 指向新节点，新节点的指针域 next 指向头节点，完成节点的插入操作。

d. 删除循环链表中指定值的节点

void deleteNode(Node** head, int data) {if (*head == NULL) {return;}Node* currNode = *head;Node* prevNode = NULL;while (currNode->next != *head) {if (currNode->data == data) {if (prevNode == NULL) {Node* lastNode = *head;while (lastNode->next != *head) {lastNode = lastNode->next;}*head = currNode->next;lastNode->next = *head;} else {prevNode->next = currNode->next;}free(currNode);return;}prevNode = currNode;currNode = currNode->next;}if (currNode->data == data) {if (prevNode == NULL) {*head = NULL;} else {prevNode->next = *head;}free(currNode);}
}
  • 检查链表是否为空，如果为空则直接返回。
  • 定义两个指针 currNode 和 prevNode
    • currNode 指向当前节点，初始时指向头节点
    • prevNode指向前一个节点，初始为 NULL
  • 遍历链表，如果找到了与指定值相等的节点，则判断该节点是否为头节点，
    • 如果是头节点，则需要找到尾节点将其指向新的头节点，并更新 *head 的值为删除节点的下一个节点，最后释放删除节点的内存。
    • 如果不是头节点，直接将前一个节点的指针域 next 指向删除节点的下一个节点，然后释放删除节点的内存。

e. 在循环链表中查找指定值的节点

Node* search(Node* head, int data) {if (head == NULL) {return NULL;}Node* currNode = head;while (currNode->next != head) {if (currNode->data == data) {return currNode;}currNode = currNode->next;}if (currNode->data == data) {return currNode;}return NULL;
}
  • 链表是否为空，如果为空则返回 NULL。
  • 定义一个指针 currNode，初始时指向头节点。
  • 遍历链表，如果找到了与指定值相等的节点，则返回该节点的指针。
  • 如果遍历完整个链表都没找到相等的节点，则返回 NULL。

f. 修改循环链表中指定节点的值

void modify(Node* head, int oldData, int newData) {Node* nodeToModify = search(head, oldData);if (nodeToModify != NULL) {nodeToModify->data = newData;}
}
  • 调用上述e中 search 函数查找指定值的节点，并将返回的节点指针保存在 nodeToModify 中
  • 如果找到了节点，则将该节点的数据域 data 更新为 newData。

g. 打印循环链表

void printList(Node* head) {if (head == NULL) {printf("循环链表为空\n");return;}Node* currNode = head;do {printf("%d ", currNode->data);currNode = currNode->next;} while (currNode != head);printf("\n");
}
  • 检查链表是否为空，如果为空则打印提示信息并返回。
  • 定义一个指针 currNode，初始时指向头节点。
  • 使用 do-while 循环遍历链表，打印当前节点的数据，然后将指针移动到下一个节点，直到回到头节点为止。

h. 释放循环链表内存空间

void freeList(Node** head) {if (*head == NULL) {return;}Node* currNode = *head;Node* nextNode = NULL;while (currNode->next != *head) {nextNode = currNode->next;free(currNode);currNode = nextNode;}free(currNode);*head = NULL;
}
  • 检查链表是否为空，如果为空则直接返回。
  • 定义两个指针 currNode 和 nextNode
    • currNode 指向当前节点，初始时指向头节点
    • nextNode指向下一个节点，初始为 NULL
  • 使用 while 循环遍历链表，将 nextNode 指向 currNode 的下一个节点，释放 currNode 指向的节点的内存，然后将 currNode 更新为 nextNode。重复以上步骤，直到遍历完整个链表，并最后释放头节点的内存。

i. 主函数

int main() {Node* head = NULL;// 在循环链表中插入节点insert(&head, 10);insert(&head, 20);insert(&head, 30);insert(&head, 40);// 打印循环链表printf("循环链表: ");printList(head);// 删除循环链表中的节点deleteNode(&head, 20);// 打印删除节点后的循环链表printf("删除节点后的循环链表: ");printList(head);// 在循环链表中查找节点Node* searchResult = search(head, 30);if (searchResult != NULL) {printf("找到节点 %d\n", searchResult->data);} else {printf("未找到节点\n");}// 修改循环链表中的节点值modify(head, 30, 50);// 打印修改节点值后的循环链表printf("修改节点值后的循环链表: ");printList(head);// 释放循环链表内存空间freeList(&head);return 0;
}
  • 定义一个指向头节点的指针 head，初始时为 NULL。
  • 通过调用 insert 函数，在循环链表中插入了四个节点，其数据分别为 10、20、30 和 40。
  • 调用 deleteNode 函数删除了值为 20 的节点，并再次调用 printList 函数打印删除节点后的循环链表。
  • 调用 search 函数查找值为 30 的节点，并根据返回结果打印相应的信息。
  • 调用 modify 函数修改值为 30 的节点的数据为 50，
  • 最后调用 freeList 函数释放循环链表占用的内存空间。

j. 代码整合

#include <stdio.h>
#include <stdlib.h>// 定义循环链表节点结构体
typedef struct Node {int data;           // 数据域struct Node *next;  // 指针域
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 在循环链表末尾插入节点
void insert(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;(*head)->next = *head;  // 将尾节点指向头节点，形成循环} else {Node* temp = *head;while (temp->next != *head) {temp = temp->next;}temp->next = newNode;newNode->next = *head;}
}// 删除循环链表中指定值的节点
void deleteNode(Node** head, int data) {if (*head == NULL) {return;}Node* currNode = *head;Node* prevNode = NULL;while (currNode->next != *head) {if (currNode->data == data) {if (prevNode == NULL) {Node* lastNode = *head;while (lastNode->next != *head) {lastNode = lastNode->next;}*head = currNode->next;lastNode->next = *head;} else {prevNode->next = currNode->next;}free(currNode);return;}prevNode = currNode;currNode = currNode->next;}if (currNode->data == data) {if (prevNode == NULL) {*head = NULL;} else {prevNode->next = *head;}free(currNode);}
}// 在循环链表中查找指定值的节点
Node* search(Node* head, int data) {if (head == NULL) {return NULL;}Node* currNode = head;while (currNode->next != head) {if (currNode->data == data) {return currNode;}currNode = currNode->next;}if (currNode->data == data) {return currNode;}return NULL;
}// 修改循环链表中指定节点的值
void modify(Node* head, int oldData, int newData) {Node* nodeToModify = search(head, oldData);if (nodeToModify != NULL) {nodeToModify->data = newData;}
}// 打印循环链表
void printList(Node* head) {if (head == NULL) {printf("循环链表为空\n");return;}Node* currNode = head;do {printf("%d ", currNode->data);currNode = currNode->next;} while (currNode != head);printf("\n");
}// 释放循环链表内存空间
void freeList(Node** head) {if (*head == NULL) {return;}Node* currNode = *head;Node* nextNode = NULL;while (currNode->next != *head) {nextNode = currNode->next;free(currNode);currNode = nextNode;}free(currNode);*head = NULL;
}int main() {Node* head = NULL;// 在循环链表中插入节点insert(&head, 10);insert(&head, 20);insert(&head, 30);insert(&head, 40);// 打印循环链表printf("循环链表: ");printList(head);// 删除循环链表中的节点deleteNode(&head, 20);// 打印删除节点后的循环链表printf("删除节点后的循环链表: ");printList(head);// 在循环链表中查找节点Node* searchResult = search(head, 30);if (searchResult != NULL) {printf("找到节点 %d\n", searchResult->data);} else {printf("未找到节点\n");}// 修改循环链表中的节点值modify(head, 30, 50);// 打印修改节点值后的循环链表printf("修改节点值后的循环链表: ");printList(head);// 释放循环链表内存空间freeList(&head);return 0;
}


http://www.ppmy.cn/news/1165543.html

相关文章

【Java 进阶篇】JavaScript 表格全选案例详解

【Java 进阶篇】JavaScript 表格全选案例详解

在网页开发中&#xff0c;表格&#xff08;Table&#xff09;是一种常用的HTML元素&#xff0c;用于以表格形式展示数据。对于包含大量数据的表格&#xff0c;提供一个全选复选框可以极大地提高用户体验&#xff0c;方便用户一次性选择或取消选择所有项目。本篇博客将详细介绍如…
阅读更多...
FPGA片上RAM、片上ROM Nios 程序不起作用的解决方法

FPGA片上RAM、片上ROM Nios 程序不起作用的解决方法

ctrl B 编译Nios工程 将 Nios software 的 meminit.qip onchip_rom.hex onchip_ram.hex meminit.spd 文件拷贝到FPGA目录下&#xff0c;再编译FPGA能起作用 Nios设置&#xff1a; reset 设置为 ROM 异常设置为 RAM 无优化
阅读更多...
Git 安装和基础命令、IDEA 基础操作

Git 安装和基础命令、IDEA 基础操作

目录 总结命令&#xff1a;1、安装&#xff1a;1、安装2、配置环境变量&#xff1a; 2、Git操作&#xff1a;1、初始化&#xff1a;1、姓名邮箱&#xff1a;2、初始化仓库&#xff1a;3、工作区和暂存区分析 2、提交文件3、查看版本库状态4、安装小乌龟git不显示图标 5、查看提…
阅读更多...
WINCC趋势画面模板

WINCC趋势画面模板

加载按钮 Sub OnClick(Byval Item) Dim Chart,tag,ctrl,objTrendWnd,objTimeAxis,objValAxis,objTrendSet ChartScreenItems("组合框2")Chart tagChart.SelTextSet ctrl ScreenItems("控件1")threadSet objTrend…
阅读更多...
星环科技向量数据库Transwarp Hippo1.1发布：一库搞定向量+全文联合检索，提升大模型准确率

星环科技向量数据库Transwarp Hippo1.1发布：一库搞定向量+全文联合检索，提升大模型准确率

星环科技向量数据库Transwarp Hippo自发布已来，受到了众多用户的欢迎，帮助用户实现向量数据的存储、管理和检索，探索和实践大模型场景。在与用户不断地深入交流以及实践中，Hippo迎来了V1.1版本，一套系统即可支持向量与全文联合检索，提高文本数据的召回精度，从而提升大语…
阅读更多...
【分享】7-Zip压缩包的密码可以取消吗？

【分享】7-Zip压缩包的密码可以取消吗？

7-Zip压缩包设置了“密码保护”&#xff0c;后面又不想要了&#xff0c;可以取消吗&#xff1f; 首先&#xff0c;我们要分两种情况来看&#xff0c;是记得密码&#xff0c;但不想每次打开压缩包都要输入密码&#xff0c;所以想取消密码&#xff0c;还是把密码忘记了所以想取消…
阅读更多...
python、SQL日新增人数统计

python、SQL日新增人数统计

提供思路&#xff1a; 新增人数统计&#xff0c;就是要看比前一天新加的人。 用一个SQL语句解决。 解决的方案SQL&#xff0c;按日期排序后只保留第一次出现的数据&#xff0c;这个问题就解决了。保留第一次出现的数据按日进行统计&#xff0c;日数据就是新增的数据。
阅读更多...
Leetcode 第 363 场周赛题解

Leetcode 第 363 场周赛题解

Leetcode 第 363 场周赛题解 Leetcode 第 363 场周赛题解题目1&#xff1a;2859. 计算 K 置位下标对应元素的和思路代码复杂度分析 题目2&#xff1a;让所有学生保持开心的分组方法数思路&#xff1a;排序 枚举代码复杂度分析 题目3&#xff1a;最大合金数思路&#xff1a;二分…
阅读更多...
最新文章

Copyright @ 2022~2023