数据结构 - 链表详解二 - 无头单向非循环链表

2024-04-24 23:52
文章标签 链表 详解 数据结构 循环 单向 无头

本文主要是介绍数据结构 - 链表详解二 - 无头单向非循环链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一. 单链表的介绍

上篇文章已经介绍了各种链表的概念了，这篇文章就带大家来实现一下无头单向非循环链表

无头单向非循环链表是一种简单而基本的链表结构，它没有哨兵或额外的头节点来简化操作，且不形成闭环。这种链表直接从首个数据节点开始，每个节点指向下一个节点，最后一个节点指向null以标示链表的结束。

1. 单链表 - 定义节点

typedef int SLTDataType; // 定义数据类型为整型，用SLTDataType代替int
//以提高代码的可读性和可维护性// 定义单向链表的节点结构
typedef struct SListNode {SLTDataType data; // 数据域：存储节点的数据，这里为整型数据struct SListNode* next; // 指针域：指向链表中下一个节点的指针
} SListNode;

2. 单链表 - 创建一个新的节点

//创建新的节点
SListNode* CreateNode(SLTDataType value)
{SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); // 动态分配内存if (newNode == NULL) // 检查内存是否成功分配{perror("malloc fail");exit(-1);}newNode->data = value; // 设置节点的数据域newNode->next = NULL;  // 初始化指针域，目前此节点不指向其他节点return newNode;        // 返回新创建的节点
}

3. 单链表 - 创建连续的节点 

这里有个问题：为什么SListNode** head使用的是双指针，

// 创建包含 num 个节点的单链表
SListNode* CreateSlist(int num) 
{SListNode* phead = NULL; // 头指针，初始为空SListNode* ptail = NULL; // 尾指针，用于追踪链表末尾for (int i = 0; i < num; i++) {SListNode* newnode = CreateNode(i); // 创建一个新节点if (phead == NULL) {ptail = phead = newnode; // 如果链表为空，初始化头尾指针为第一个节点}else {ptail->next = newnode; // 将新节点链接到链表末尾ptail = newnode;       // 更新尾指针指向新的末尾节点}}return phead; // 返回链表头指针
}

4. 单链表 - 打印

//打印
void PrintList(SListNode* head) 
{if (head == NULL) { // 如果头指针为 NULL，表示链表为空printf("The list is empty.\n");} else {printf("List: ");SListNode* current = head; // 使用一个临时指针从头节点开始遍历链表//保留 head 指针不变，使用另一个临时指针（current）进行遍历，//可以保证 head 指针始终指向链表的开始位置while (current != NULL) { // 遍历链表直到末尾printf("%d -> ", current->data); // 打印当前节点的数据current = current->next; // 移动到下一个节点}printf("NULL\n"); // 打印链表结束标志}
}

5. 单链表 - 销毁

void DestroyList(SListNode** pphead) 
{while (*pphead != NULL) {SListNode* temp = *pphead;       // 保存当前头节点*pphead = (*pphead)->next;       // 更新头指针到下一个节点free(temp);                      // 释放原头节点的内存}// 可选：确保链表完全清空后，外部指针也设置为NULL*pphead = NULL;
}

6. 单链表的头插

void SListPushFront(SListNode** pphead, SLTDataType value)
{SListNode* newNode = CreateNode(value); // 创建一个新节点newNode->next = *pphead; // 新节点的 next 指针指向当前的头节点*pphead = newNode;       // 更新头指针，现在它指向新的头节点
}

7. 单链表的头删

// 头删         注意：插入都不需要断言，删除需要断言，防止要删除得第一个为空
void SListPopFront(SListNode** pphead)
{assert(*pphead); //断言SListNode* temp = *pphead;*pphead = (*pphead)->next;free(temp);temp = NULL;
}

8. 单链表的尾插

//由于 pphead 是一个指向头指针的指针，这样设计允许函数内部直接修改头指针的值。这在链表为空时特别有用，因为需要将头指针指向新创建的第一个节点。如果只传递头指针的副本（即不通过双指针），函数内部的任何修改都不会反映到原始头指针上，从而无法更新链表的开始位置
void SListPushBack(SListNode** pphead, SLTDataType value)
{// 申请一个新结点，并初始化其数据为valueSListNode* newnode = CreateNode(value); // 该函数需要预先定义，用于创建新节点并设置其数据// 判断传入的链表指针是否指向NULL，即检查链表是否为空if (*pphead == NULL) // 如果链表为空（即没有任何节点）{*pphead = newnode; // 将链表的头指针指向新节点，使新节点成为链表的第一个（也是唯一一个）节点}else // 如果链表不为空{SListNode* tail = *pphead; // 使用一个辅助指针tail开始于链表的头节点// 遍历链表找到最后一个节点，即其next指针为NULL的节点while (tail->next != NULL) // 继续遍历，直到找到一个next指针为NULL的节点{tail = tail->next; // 移动tail指针到下一个节点}// 在链表的末尾添加新节点tail->next = newnode; // 将找到的最后一个节点的next指针指向新创建的节点，从而将新节点链接到链表的末尾}
}

  • 使用单指针：如果函数签名是 void SListPushBack(SListNode* pphead, SLTDataType value), 那么在添加节点到空链表时，即使我们设置 head = newNode;，这个变化也仅限于函数内部。函数结束后，外部的头指针仍然是 NULL。

  • 使用双指针：使用 void AppendNode(SListNode** pphead, SLTDataType value)，则允许我们通过 *head = newNode; 真正改变外部的头指针。

由于 pphead 是一个指向头指针的指针，这样设计允许函数内部直接修改头指针的值。这在链表为空时特别有用，因为需要将头指针指向新创建的第一个节点。如果只传递头指针的副本（即不通过双指针），函数内部的任何修改都不会反映到原始头指针上，从而无法更新链表的开始位置。 

9. 单链表的尾删

void SListPopBack(SListNode** pphead) {if (*pphead == NULL) { // 检查链表是否为空return; // 链表为空，直接返回}if ((*pphead)->next == NULL) { // 如果链表只有一个节点free(*pphead); // 释放这个节点*pphead = NULL; // 将头指针设置为 NULLreturn;}SListNode* current = *pphead; // 用于遍历链表的临时指针while (current->next->next != NULL) { // 找到倒数第二个节点current = current->next;}free(current->next); // 释放最后一个节点current->next = NULL; // 将倒数第二个节点的 next 指针设置为 NULL
}

10. 单链表在pos位置前插入数据

void InsertNodeBeforePos(SListNode** pphead, int pos, SLTDataType value) 
{if (pos < 0 || pphead == NULL) { // 检查位置是否有效return;}SListNode* newNode = CreateNode(value); // 创建新节点if (pos == 0) { // 如果位置是0，即在头部插入newNode->next = *pphead; // 新节点指向当前头节点*pphead = newNode; // 更新头节点为新节点return;}SListNode* current = *pphead;for (int i = 0; current != NULL && i < pos - 1; i++) { // 寻找位置 pos 的前一个节点current = current->next;}if (current == NULL) { // 如果位置超出链表长度free(newNode); // 释放新节点return;}// 插入新节点到链表中newNode->next = current->next; // 新节点指向当前节点的下一个节点current->next = newNode; // 当前节点的 next 更新为新节点
}

11. 单链表的在pos位置后插入数据

void InsertNodeAfterPos(SListNode** pphead, int pos, SLTDataType value) {if (pos < 0 || pphead == NULL) { // 检查位置是否有效return;}SListNode* current = *pphead;for (int i = 0; current != NULL && i < pos; i++) { // 寻找位置 pos 的节点current = current->next;}if (current == NULL) { // 如果位置超出链表长度或链表为空return;}SListNode* newNode = CreateNode(value); // 创建新节点newNode->next = current->next; // 新节点指向当前节点的下一个节点current->next = newNode; // 当前节点的 next 更新为新节点
}

12. 链表删除pos位置之后的元素

// 删除指定位置之后的所有节点
void DeleteNodesAfterPos(SListNode** pphead, int pos) {if (*pphead == NULL || pos < 0) { // 如果链表为空或位置无效return;}SListNode* current = *pphead; // 用于遍历链表的临时指针for (int i = 0; i < pos && current != NULL; i++) { // 遍历到指定位置current = current->next;}if (current == NULL || current->next == NULL) { // 如果位置超出链表范围或没有后续节点return;}SListNode* temp = current->next; // 保存要开始删除的第一个节点current->next = NULL; // 将指定位置的节点的 next 指针设置为 NULL，断开链接while (temp != NULL) { // 遍历并释放所有后继节点SListNode* toDelete = temp;temp = temp->next;free(toDelete);}
}

13. 链表删除pos位置的元素

void DeleteNodeAtPos(SListNode** pphead, int pos) {if (pos < 0 || *pphead == NULL) { // 检查位置是否有效或链表是否为空return;}SListNode* temp = *pphead; // 用于遍历的临时指针if (pos == 0) { // 如果要删除的是头节点*pphead = temp->next; // 更新头指针free(temp); // 释放头节点内存return;}for (int i = 0; i < pos - 1 && temp != NULL; i++) { // 寻找要删除节点的前一个节点temp = temp->next;}if (temp == NULL || temp->next == NULL) { // 如果位置无效或者pos超出了链表长度return; // 无操作}SListNode* toDelete = temp->next; // 指向要删除的节点temp->next = toDelete->next; // 将前一个节点的 next 指向要删除节点的下一个节点free(toDelete); // 释放要删除的节点的内存
}

14. 链表修改pos位置的数据

void SListModify(SListNode* pos, SLTDataType x)
{pos->data = x;//将结点的数据改为目标数据
}

二. 完整代码

SListNode.c

#include <stdio.h>
#include <string.h>
#include <cstdlib>typedef int SLTDataType; // 定义数据类型为整型，用SLTDataType代替int
//以提高代码的可读性和可维护性// 定义单向链表的节点结构
typedef struct SListNode {SLTDataType data; // 数据域：存储节点的数据，这里为整型数据struct SListNode* next; // 指针域：指向链表中下一个节点的指针
} SListNode;//创建新的节点
SListNode* CreateNode(SLTDataType value)
{SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); // 动态分配内存if (newNode == NULL) // 检查内存是否成功分配{perror("malloc fail");exit(-1);}newNode->data = value; // 设置节点的数据域newNode->next = NULL;  // 初始化指针域，目前此节点不指向其他节点return newNode;        // 返回新创建的节点
}// 创建包含 num 个节点的单链表
SListNode* CreateSlist(int num)
{SListNode* phead = NULL; // 头指针，初始为空SListNode* ptail = NULL; // 尾指针，用于追踪链表末尾for (int i = 0; i < num; i++) {SListNode* newnode = CreateNode(i); // 创建一个新节点if (phead == NULL) {ptail = phead = newnode; // 如果链表为空，初始化头尾指针为第一个节点}else {ptail->next = newnode; // 将新节点链接到链表末尾ptail = newnode;       // 更新尾指针指向新的末尾节点}}return phead; // 返回链表头指针
}//打印
void PrintList(SListNode* head)
{if (head == NULL) { // 如果头指针为 NULL，表示链表为空printf("The list is empty.\n");}else {printf("List: ");SListNode* current = head; // 使用一个临时指针从头节点开始遍历链表//保留 head 指针不变，使用另一个临时指针（current）进行遍历，//可以保证 head 指针始终指向链表的开始位置while (current != NULL) { // 遍历链表直到末尾printf("%d -> ", current->data); // 打印当前节点的数据current = current->next; // 移动到下一个节点}printf("NULL\n"); // 打印链表结束标志}
}//摧毁
void DestroyList(SListNode** pphead)
{while (*pphead != NULL) {SListNode* temp = *pphead;       // 保存当前头节点*pphead = (*pphead)->next;       // 更新头指针到下一个节点free(temp);                      // 释放原头节点的内存}// 可选：确保链表完全清空后，外部指针也设置为NULL*pphead = NULL;
}//头插
void SListPushFront(SListNode** pphead, SLTDataType value)
{SListNode* newNode = CreateNode(value); // 创建一个新节点newNode->next = *pphead; // 新节点的 next 指针指向当前的头节点*pphead = newNode;       // 更新头指针，现在它指向新的头节点
}// 头删         注意：插入都不需要断言，删除需要断言，防止要删除得第一个为空
void SListPopFront(SListNode** pphead)
{assert(*pphead); //断言SListNode* temp = *pphead;*pphead = (*pphead)->next;free(temp);temp = NULL;
}//尾插
//由于 pphead 是一个指向头指针的指针，这样设计允许函数内部直接修改头指针的值。这在链表为空时特别有用，因为需要将头指针指向新创建的第一个节点。如果只传递头指针的副本（即不通过双指针），函数内部的任何修改都不会反映到原始头指针上，从而无法更新链表的开始位置
void SListPushBack(SListNode** pphead, SLTDataType value)
{// 申请一个新结点，并初始化其数据为valueSListNode* newnode = CreateNode(value); // 该函数需要预先定义，用于创建新节点并设置其数据// 判断传入的链表指针是否指向NULL，即检查链表是否为空if (*pphead == NULL) // 如果链表为空（即没有任何节点）{*pphead = newnode; // 将链表的头指针指向新节点，使新节点成为链表的第一个（也是唯一一个）节点}else // 如果链表不为空{SListNode* tail = *pphead; // 使用一个辅助指针tail开始于链表的头节点// 遍历链表找到最后一个节点，即其next指针为NULL的节点while (tail->next != NULL) // 继续遍历，直到找到一个next指针为NULL的节点{tail = tail->next; // 移动tail指针到下一个节点}// 在链表的末尾添加新节点tail->next = newnode; // 将找到的最后一个节点的next指针指向新创建的节点，从而将新节点链接到链表的末尾}
}
//尾删
void SListPopBack(SListNode** pphead) {if (*pphead == NULL) { // 检查链表是否为空return; // 链表为空，直接返回}if ((*pphead)->next == NULL) { // 如果链表只有一个节点free(*pphead); // 释放这个节点*pphead = NULL; // 将头指针设置为 NULLreturn;}SListNode* current = *pphead; // 用于遍历链表的临时指针while (current->next->next != NULL) { // 找到倒数第二个节点current = current->next;}free(current->next); // 释放最后一个节点current->next = NULL; // 将倒数第二个节点的 next 指针设置为 NULL
}//单链表在pos位置前插入数据
void InsertNodeBeforePos(SListNode** pphead, int pos, SLTDataType value)
{if (pos < 0 || pphead == NULL) { // 检查位置是否有效return;}SListNode* newNode = CreateNode(value); // 创建新节点if (pos == 0) { // 如果位置是0，即在头部插入newNode->next = *pphead; // 新节点指向当前头节点*pphead = newNode; // 更新头节点为新节点return;}SListNode* current = *pphead;for (int i = 0; current != NULL && i < pos - 1; i++) { // 寻找位置 pos 的前一个节点current = current->next;}if (current == NULL) { // 如果位置超出链表长度free(newNode); // 释放新节点return;}// 插入新节点到链表中newNode->next = current->next; // 新节点指向当前节点的下一个节点current->next = newNode; // 当前节点的 next 更新为新节点
}//单链表在pos位置前插入数据
void InsertNodeAfterPos(SListNode** pphead, int pos, SLTDataType value) {if (pos < 0 || pphead == NULL) { // 检查位置是否有效return;}SListNode* current = *pphead;for (int i = 0; current != NULL && i < pos; i++) { // 寻找位置 pos 的节点current = current->next;}if (current == NULL) { // 如果位置超出链表长度或链表为空return;}SListNode* newNode = CreateNode(value); // 创建新节点newNode->next = current->next; // 新节点指向当前节点的下一个节点current->next = newNode; // 当前节点的 next 更新为新节点
}// 删除指定位置之后的所有节点
void DeleteNodesAfterPos(SListNode** pphead, int pos) {if (*pphead == NULL || pos < 0) { // 如果链表为空或位置无效return;}SListNode* current = *pphead; // 用于遍历链表的临时指针for (int i = 0; i < pos && current != NULL; i++) { // 遍历到指定位置current = current->next;}if (current == NULL || current->next == NULL) { // 如果位置超出链表范围或没有后续节点return;}SListNode* temp = current->next; // 保存要开始删除的第一个节点current->next = NULL; // 将指定位置的节点的 next 指针设置为 NULL，断开链接while (temp != NULL) { // 遍历并释放所有后继节点SListNode* toDelete = temp;temp = temp->next;free(toDelete);}
}//链表删除pos位置的元素
void DeleteNodeAtPos(SListNode** pphead, int pos) {if (pos < 0 || *pphead == NULL) { // 检查位置是否有效或链表是否为空return;}SListNode* temp = *pphead; // 用于遍历的临时指针if (pos == 0) { // 如果要删除的是头节点*pphead = temp->next; // 更新头指针free(temp); // 释放头节点内存return;}for (int i = 0; i < pos - 1 && temp != NULL; i++) { // 寻找要删除节点的前一个节点temp = temp->next;}if (temp == NULL || temp->next == NULL) { // 如果位置无效或者pos超出了链表长度return; // 无操作}SListNode* toDelete = temp->next; // 指向要删除的节点temp->next = toDelete->next; // 将前一个节点的 next 指向要删除节点的下一个节点free(toDelete); // 释放要删除的节点的内存
}//修改
void SListModify(SListNode* pos, SLTDataType x)
{pos->data = x;//将结点的数据改为目标数据
}

这篇关于数据结构 - 链表详解二 - 无头单向非循环链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/933184。

相关文章

Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
K8S（Kubernetes）开源的容器编排平台安装步骤详解

K8S（Kubernetes）开源的容器编排平台安装步骤详解

K8S（Kubernetes）是一个开源的容器编排平台，用于自动化部署、扩展和管理容器化应用程序。以下是K8S容器编排平台的安装步骤、使用方式及特点的概述： 安装步骤： 安装Docker：K8S需要基于Docker来运行容器化应用程序。首先要在所有节点上安装Docker引擎。 安装Kubernetes Master：在集群中选择一台主机作为Master节点，安装K8S的控制平面组件，如AP
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2