单链表增序排列节点(单链表算法库拓展v2.0)

对单链表中元素进行排序(至少有2个数据节点)

/**************************************************
(13)函数名:LinkList_sorting
功  能:对单链表中元素进行排序(至少有2个数据节点)
参  数:LinkList *&L:要进行排序的单链表
注意: ① 空表,或者只有一个数据节点,则不需要排序,返回false
      ② 开始节点必须是头结点,因为我们会用到start_compare->next,
      ③ 把数据节点(第二个数据节点及以后)和原始链表(头结点+一个数据节点)
      ④ 在有序表中,一直找到比前一个节点大,比后一个节点小的空挡,
         所以时刻对比start_compare->next->data, 并且start_compare->next不能为空
         (为空代表到达末尾,交替空指针)
        ⑤ 顺序不能变, 避免丢失有序表后续信息(指针覆盖的一句话)
详细链接:https://blog.csdn.net/qq_57484399/article/details/127141307
返回值:bool: 是否符合排序标准,并排序成功  ? true: false
**************************************************/
bool LinkList_sorting(LinkList *&L)
{
    LinkList *compare,*start_compare,*Remaining_node;
    if(L->next == NULL || L->next->next == NULL)//①保证至少有2个数据节点
    {
        return false;
    }
    compare = L->next->next;
    start_compare = L;  //②开始节点必须是头结点
    Remaining_node = compare->next;
    L->next->next = NULL; //③把数据节点(第二个数据节点及以后)和原始链表(头结点+一个数据节点)

    while(compare != NULL)
    {
        Remaining_node = compare->next;
        start_compare = L;
        while((start_compare->next != NULL) && (compare->data > start_compare->next->data))
        {
            start_compare = start_compare->next;
        } //④

        compare->next = start_compare->next;
        start_compare->next = compare;     //⑤
        compare = Remaining_node;
    }
    return true;

}

单链表完整函数库:

singlelist.cpp

#include "singlelist.h"

/**************************************************
①函数名: CreatList_Head
功  能: 头插法建立单链表
参  数: (1)LinkList *&L: 传入的单链表指针地址
        (2)ElemType Array_used[]:要用来建表的数组
        (3)int Array_number: 数组的长度
返回值:    无
**************************************************/
void CreatList_Head(LinkList *&L, ElemType Array_used[], int Array_number)
{
    int counter;
    LinkList *newnode;
    L = (LinkList *)malloc(sizeof(LinkList)); //创建头结点
    L->next = NULL;
    for(counter = 0; counter < Array_number; counter++)
    {
        newnode = (LinkList *)malloc(sizeof(LinkList));  //创建新节点
        newnode->data = Array_used[counter];
        newnode->next = L->next;         //将newnode插在原开始结点之前,头结点之后
        L->next = newnode;
    }
}
/**************************************************
②函数名: CreatList_Tail
功  能: 尾插法建立单链表
参  数: (1)LinkList *&L: 传入的单链表指针地址
        (2)ElemType Array_used[]:要用来建表的数组
        (3)int Array_number:数组的长度
返回值:   无
**************************************************/
void CreatList_Tail(LinkList *&L, ElemType Array_used[], int Array_number)
{
    int counter;
    LinkList *newnode,*tailnode;
    L = (LinkList *)malloc(sizeof(LinkList));//创建头结点
    L->next = NULL;
    tailnode = L;       //尾结点tailnode始终指向终端结点,开始指向头结点
    for(counter = 0; counter < Array_number; counter++)
    {
        newnode = (LinkList *)malloc(sizeof(LinkList)); //创建新节点
        newnode->data = Array_used[counter];
        tailnode->next = newnode;   //将新节点插入到尾结点之后
        tailnode = newnode;         //更新尾结点
    }
    tailnode->next = NULL;          //终端结点next域置空
}

/**************************************************
③函数名: DisplayLinkList
功  能: 输出单链表
参  数: (1)LinkList *L:将要输出的单链表
返回值: 无
**************************************************/

void DisplayLinkList(LinkList *L)
{
    LinkList *shownode;
    shownode = L->next;
    while(shownode != NULL)
    {
        printf("%d",shownode->data);
        shownode = shownode->next;        //一直遍历,直到指向尾->newt = NULL
    }
    printf("\n");
}
/**************************************************
④函数名: DestroyLinkList
功  能: 销毁单链表
参  数: (1)LinkList *&L:要销毁的单链表
注意:① 等到指引下一个节点的指针为Null时就跳出,避免出现野指针,此时再销毁destroyNode
    ② 避免断开联系,记录 销毁节点的下一个节点
返回值: 无
**************************************************/
void DestroyLinkList(LinkList *&L)
{
    LinkList *destoryNode,*nextNode;
    destoryNode = L;
    nextNode = destoryNode->next;
    while(nextNode != NULL)        //①
    {
        free(destoryNode);
        destoryNode = nextNode;
        nextNode = destoryNode->next;   //②
    }
    free(destoryNode);

}
/**************************************************
⑤函数名: InitLinkList
功  能: 初始化单链表
参  数: LinkList *&L:要被初始化的链表指针地址
返回值: 无
**************************************************/
void InitLinkList(LinkList *&L)
{
    L = (LinkList *)malloc(sizeof(LinkList));//创建头结点
    L->next = NULL;
}
/**************************************************
⑥函数名: LinkListEmpty
功  能: 判断单链表是否为空
参  数: (1)LinkList *L:要判断的单链表
返回值: bool: 是否为空? treu:false
**************************************************/
bool LinkListEmpty(LinkList *L)
{
    return (L->next == NULL);
}

/**************************************************
⑦函数名: LinkListLength
功  能: 返回单链表L中数据节点的个数
参  数: LinkList *L:要计算的数据节点
返回值: int: 线性表数据节点个数值
**************************************************/
int LinkListLength(LinkList *L)
{
    int counter = 0;
    LinkList *nowNode = L;
    while(nowNode->next != NULL)
    {
        counter++;
        nowNode = nowNode->next;
    }
    return counter;
}

/**************************************************
⑧函数名: GetLocateValue
功  能: 求特定位置的数据元素值
参  数: (1)LinkList *L:要找的单链表
        (2)int location:所要找的位置
        (3)ElemType &value: 传递回所要找的值
注意: ① 判断跳出的时候, 是查找成功, 还是抵达末尾
     ② counter == 要找到序号,则跳出,所以counter < location  ,
    nowNode指向的节点为空,则到末尾,则跳出
    ③④ 这两条语句, 所指向的序号和节点, 是同步的, 位置到或者此节点为空,则跳出
返回值: bool: 是否查找成功? true:false
**************************************************/
bool SpecificLocate_Value(LinkList *L,int location, ElemType &value)
{
    int counter = 0;
    LinkList *nowNode = L;
    while(counter < location && nowNode != NULL)//②
    {
        counter++;          //③  当前计数的节点
        nowNode = nowNode->next;//④当前遍历到的节点
    }
    if(nowNode == NULL)                //①
    {
        return false;
    }
    else
    {
        value = nowNode->data;
        return true;
    }

}

/**************************************************
⑨函数名:SpecificValue_Location
功  能: 查找特定数据值的节点,并返回其位置
参  数: (1)LinkList *L: 被查找的单链表(2)ElemType e:
注  意:  ①从头结点后的第一个节点开始找
         ②while循环内的两条语句是同步指向的
         ③当nowNode为空时(到达末尾仍未找到), counter作废
         ④当nowNode不为空时,跳出时, counter表示所指向节点存在,并符合所需
返回值:
**************************************************/
int SpecificValue_Location(LinkList *L, ElemType value)
{
    int counter = 1;
    LinkList *nowNode = L->next;    //①
    while(nowNode != NULL && nowNode->data != value)
    {
        nowNode = nowNode->next;
        counter++;                     //②
    }
    if(nowNode == NULL)           //③
    {
        return 0;
    }
    else                    //④
    {
        return counter;
    }

}
/**************************************************
⑩函数名: LinkList_InsertElement
功  能: 在单链表特定位置插入节点
参  数: (1)LinkList *&L:要插入的单链表
        (2)int location:要插入的位置
        (3) ElemType &value:插入的数据
思路:    先在单链表L中,找到第 i-1个节点(不算头结点),若存在这样的节点,
        将值为value的节点 插入到其后面
注意:    ① 计数器和 nowNode是同步往后移动(从L->next开始算第一个节点),
         直到 找到counter = location-1,
         ②此时 nowNode不为空,则此时nowNode指向
         要插入位置的 前一个节点
         ③ 覆盖指针前, 牢记 nowNode->next里面存放的是后继节点信息,所以要先处理
          newNode->next = nowNode->next;
          然后我们才能再把 nowNode->next指向新节点 newNode
返回值: bool: 是否存在第i-1个节点,并插入成功? true : false
**************************************************/
bool LinkList_InsertElement(LinkList *&L, int location, ElemType &value)
{
        int counter = 0;
        LinkList *nowNode = L;
        LinkList *newNode;
        while((counter < (location-1)) && (nowNode != NULL)) //①
        {
            counter++;
            nowNode = nowNode->next;
        }
        if(nowNode == NULL)//②
        {
            return false;
        }
        else
        {
            newNode = (LinkList *)malloc(sizeof(LinkList));
            newNode->data = value;
            newNode->next = nowNode->next;//③
            nowNode->next = newNode;
            return true;
        }
}
/**************************************************
(11)函数名: LinkList_Delete_Location
功  能: 删除特定位置的节点元素
参  数: (1)LinkList *&L:被删除的单链表 (2)int location:特定位置
        (3) ElemType &value:被删除的元素值
思路:    找到第location-1个元素, 存储第locataion个元素值(判断null),然后free
        链接 location-1 和 location+1
注意:    ① counter和指针节点是同步的,要么找到location-1个节点,要么到末尾
        ② 虽然可能找到location-1个元素,其可能是最后一个元素,从而导致删除失败
        需要判断一下,deleteNode是否为空,才能得出是否任务成功
        ③ 指针覆盖还是老生常谈,先存储一下deleteNode(方便free),
           然后指针交替,然后free
返回值:  bool: 是否删除成功? true:false
**************************************************/
bool LinkList_Delete_Location(LinkList *&L,int location, ElemType &value)
{
    int counter = 0;
    LinkList *nowNode = L;
    LinkList *deleteNode;
    while(counter < (location-1) && nowNode != NULL)   //①
    {
        counter++;
        nowNode = nowNode->next;
    }
    if(nowNode == NULL)
    {
        return false;
    }
    else
    {
        deleteNode = nowNode->next;
        if(deleteNode == NULL)    //②
        {
            return false;
        }
        value = deleteNode->data;
        nowNode->next = deleteNode->next;  //③
        free(deleteNode);
        return true;
    }
}

/**************************************************
(12)函数名: DeleteMaxNode
功  能: 删除单链表中最大的一个节点
参  数: (1)LinkList *&L:要删除节点的单链表
思路: 四个指针, 最大指针,最大指针前一个节点
    目前遍历的指针,遍历指针的前一个节点, 边比较,边替换,边遍历
注意:①避免只有一个头结点,造成空指针替换异常
    ②③ 顺序不能变,因为③跳出的时候, 会利用到while的非空条件,
   避免对比的时候, 出现野指针,直到为空时,即可直接跳出,非空则比较替换
返回值:是否删除成功 ? true:false
**************************************************/
bool   DeleteMaxNode(LinkList *&L)
{
    LinkList *nowNode,*preNode;
    LinkList *maxNode,*preMaxNode;
    nowNode = L->next;
    preNode = L;
    maxNode = nowNode;
    preMaxNode = preNode;
    if(nowNode == NULL) //①
    {
        return false;
    }
    while(nowNode != NULL) //直到末尾
    {
        if(nowNode->data > maxNode->data)   //②
        {
            maxNode = nowNode;
            preMaxNode = preNode;
        }
        preNode = nowNode;       //接着走下一个节点
        nowNode = nowNode->next;   //③
    }
    preMaxNode->next = maxNode->next;
    free(maxNode);
    return true;
}

/**************************************************
(13)函数名:LinkList_sorting
功  能:对单链表中元素进行排序(至少有2个数据节点)
参  数:LinkList *&L:要进行排序的单链表
注意: ① 空表,或者只有一个数据节点,则不需要排序,返回false
      ② 开始节点必须是头结点,因为我们会用到start_compare->next,
      ③ 把数据节点(第二个数据节点及以后)和原始链表(头结点+一个数据节点)
      ④ 在有序表中,一直找到比前一个节点大,比后一个节点小的空挡,
         所以时刻对比start_compare->next->data, 并且start_compare->next不能为空
         (为空代表到达末尾,交替空指针)
        ⑤ 顺序不能变, 避免丢失有序表后续信息(指针覆盖的一句话)
详细链接:https://blog.csdn.net/qq_57484399/article/details/127141307
返回值:bool: 是否符合排序标准,并排序成功  ? true: false
**************************************************/
bool LinkList_sorting(LinkList *&L)
{
    LinkList *compare,*start_compare,*Remaining_node;
    if(L->next == NULL || L->next->next == NULL)//①保证至少有2个数据节点
    {
        return false;
    }
    compare = L->next->next;
    start_compare = L;  //②开始节点必须是头结点
    Remaining_node = compare->next;
    L->next->next = NULL; //③把数据节点(第二个数据节点及以后)和原始链表(头结点+一个数据节点)

    while(compare != NULL)
    {
        Remaining_node = compare->next;
        start_compare = L;
        while((start_compare->next != NULL) && (compare->data > start_compare->next->data))
        {
            start_compare = start_compare->next;
        } //④

        compare->next = start_compare->next;
        start_compare->next = compare;     //⑤
        compare = Remaining_node;
    }
    return true;

}

singlelist.h

#ifndef SINGLELIST_H_INCLUDE
#define SINGLELIST_H_INCLUDE

#include <stdio.h>
#include <malloc.h>

typedef int ElemType;   //定义单链表节点类型

typedef struct LNode
{
    ElemType data;
    struct LNode *next; //指向后继节点

}LinkList;
//①头插法建立单链表
void CreatList_Head(LinkList *&L, ElemType Array_used[], int Array_number);
//②尾插法建立单链表
void CreatList_Tail(LinkList *&L, ElemType Array_used[], int Array_number);
//③输出单链表
void DisplayLinkList(LinkList *L);
//④销毁单链表
void DestroyLinkList(LinkList *&L);
//⑤ 初始化线性表
void InitLinkList(LinkList *&L);
//⑥ 判断线性表是否为空表
bool LinkListEmpty(LinkList *L);
//⑦ 返回单链表L中数据节点的个数
int LinkListLength(LinkList *L);
//⑧ 求线性表L中指定位置的某个数据元素
bool SpecificLocate_Value(LinkList *L,int location, ElemType &value);
//⑨ 按元素值查找特定元素的位置
int SpecificValue_Location(LinkList *L, ElemType value);
//⑩ 把元素插入到特定位置
bool LinkList_InsertElement(LinkList *&L, int location, ElemType &value);
//(11) 删除特定位置的节点元素
bool LinkList_Delete_Location(LinkList *&L,int location, ElemType &value);
//(12)单链表删除其中其最大节点元素
bool  DeleteMaxNode(LinkList *&L);
//(13)对单链表中元素进行排序(至少有2个数据节点)
bool LinkList_sorting(LinkList *&L);
#endif // SINGLELIST_H_INCLUDE

main.cpp演示函数:

#include <stdio.h>
#include <malloc.h>
#include "singlelist.h"

int main()
{
    LinkList *L1;
    ElemType shuzu[8] = {3,2,4,5,1,7,8,6};
    CreatList_Tail(L1,shuzu,6);
    DisplayLinkList(L1);
    if(LinkList_sorting(L1))
    {
        printf("排序成功:\n");
        DisplayLinkList(L1);
    }
    else
    {
        printf("排序失败!\n");
    }


}

演示结果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/490974.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

企业级快速开发框架 nbsaas-boot 1.1.8-2024 发布了

<parent><groupId>com.nbsaas.boot</groupId><artifactId>nbsaas-boot</artifactId><version>1.1.8-2024</version> </parent> 本次更新内容 1. 重构代码生成器&#xff0c;采用类提取和字段提取两种方式&#xff0c;提取功能…

查看 Debian 系统版本的 6 种方式

本篇文章将为大家介绍 6 种查看 Dibian 系统发行版本号的方式。 1. 使用 lsb_release 命令 lsb_release 命令可用于查看 Linux 发行版操作系统的具体版本。它可能尚未安装在你的操作系统中&#xff0c;因此你需要先安装它。运行以下命令来安装 lsb_release&#xff1a; apt-…

云原生靶场kebernetesGoat、Metarget

靶场 文章目录 靶场kebernetesGoat靶场安装Docker in DockerSSRF漏洞容器逃逸到主系统Docker CIS 基线分析Kubernetes CIS 安全基线分析分析被部署挖矿软件的容器镜像获取环境信息Hidden in layersRBAC最低权限配置错误使用 Sysdig Falco 进行运行时安全监控和检测 Metarget ke…

MT6762_联发科MTK6762安卓核心板规格参数

MTK6762核心板是一款集成了蓝牙、fm、wlan和gps模块的高度集成基带平台&#xff0c;为LTE/LTE-A和C2K智能手机应用程序提供支持。该安卓核心板集成了ARM Cortex-A53处理器&#xff0c;工作频率可达2.0GHz&#xff0c;并且还集成了功能强大的多标准视频编解码器。除此之外&#…

VScode 内存溢出 yarn/npm内存溢出问题解决

当前目录下执行 increase-memory-limit 然后再启动

优化卡顿实力派,品质表现更出彩

游戏卡顿无疑是开发者最需要关注的重要性能问题之一。它影响玩家的游戏进程&#xff0c;并直接对玩家的游戏体验产生不良的影响。为助力开发者应对这一难题&#xff0c;在之前的版本中&#xff0c;卡顿分析页已经陆续推出了重点函数分析、卡顿点分析以及Timeline等功能&#xf…

C# wpf 嵌入winform控件

WPF Hwnd窗口互操作系列 第一章 嵌入Hwnd窗口 第二章 嵌入WinForm控件&#xff08;本章&#xff09; 第三章 嵌入WPF控件 文章目录 WPF Hwnd窗口互操作系列前言一、导入WinForm1、.Net Framwork&#xff08;1&#xff09;、右键添加引用&#xff08;2&#xff09;、勾选程序集…

DMA知识

提示&#xff1a;文章 文章目录 前言一、背景二、 2.1 2.2 总结 前言 前期疑问&#xff1a; 本文目标&#xff1a; 一、背景 2024年3月26日23:32:43 今天看了DMA存储器到存储器的DMA传输和存储器到外设的DMA实验&#xff0c;在keil仿真可以看到效果。还没有在protues和开发…

Spire.PDF for .NET【文档操作】演示:查找并删除 PDF 中的空白页

PDF 中的空白页并不罕见&#xff0c;因为它们可能是作者故意留下的或在操作文档时意外添加的。当您阅读或打印文档时&#xff0c;这些空白页可能会很烦人&#xff0c;因此可能非常有必要将其删除。在本文中&#xff0c;您将了解如何使用Spire.PDF for .NET以编程方式查找和删除…

CODESYS和AB的PLC走ETHERNET/IP

添加Ethernet->添加EtherNet_IP_Adapter_1->EtherNet_IP_Module 添加数据&#xff1a;需要发送多少就写多少 填写数量类型&#xff1a; 2.导出EDS文件&#xff0c;此处导出EDS文件需修改版本号&#xff0c;此处版本号不能与AB库中从站版本号存在冲突&#xff0c;否则在…

Go语言学习Day4:函数(上)

名人说&#xff1a;莫愁千里路&#xff0c;自有到来风。 ——钱珝 创作者&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 目录 1、函数的概念与定义①函数的概念②函数的具体定义③多返回值 2、函数参数与作用域①可变参数②形…

windows安装tomcat

安装之前需要安装jdk1.8可以参考windows安装jdk1.8-CSDN博客 一、下载tomcat Apache Tomcat - Apache Tomcat 8 Software Downloads 解压到D盘的D:\Program Files\tomcat目录下 二、配置环境变量 电脑右键属性-高级系统设置-高级-环境变量 1、在系统变量配置CATALINA_HOME环…

[flask]请求全局钩子

flask从入门到精通之钩子、异常、context、jinjia模板、过滤器 - 异步非阻塞 - 博客园 (cnblogs.com) 参考的这个博客&#xff0c;但有一个需要注意的是&#xff0c;最新版本的flask不知道是不是更新了还是怎么了&#xff0c;他的before_first_request不见了&#xff0c;如果继…

鸿蒙HarmonyOS 开发如果实现多端协同?

多端协同流程 多端协同流程如下图所示。 图1 多端协同流程图 约束限制 由于“多端协同任务管理”能力尚未具备&#xff0c;开发者当前只能通过开发系统应用获取设备列表&#xff0c;不支持三方应用接入。 多端协同需遵循 分布式跨设备组件启动规则 。 为了获得最佳体验&…

迭代实现二叉树的遍历-算法通关村

迭代实现二叉树的遍历-算法通关村 理论上&#xff0c;递归能做的迭代一定能做&#xff0c;但可能会比较复杂。有时候面试官要求不使用递归实现三种遍历&#xff0c;递归就是每次执行方法调用都会先把当前的局部变量、参数值和返回地址等压入栈中&#xff0c;后面在递归返回的时…

uniapp 使用命令行创建vue3 ts 项目

命令行创建 uni-app 项目&#xff1a; vue3 ts 版 npx degit dcloudio/uni-preset-vue#vite-ts 项目名称注意 Vue3/Vite版要求 node 版本^14.18.0 || >16.0.0 如果下载失败&#xff0c;请去gitee下载 https://gitee.com/dcloud/uni-preset-vue/repository/archive/vite-ts…

基于nodejs+vue的Spark的共享单车数据存储系统的设计与实现python-flask-django-php

本文拟采用nodejs技术和express搭建系统框架&#xff0c;后台使用MySQL数据库进行信息管理&#xff0c;设计开发的共享单车数据存储系统。通过调研和分析&#xff0c;系统拥有管理员和用户两个角色&#xff0c;主要具备个人中心、用户管理、共享单车管理、系统管理等功能模块。…

力扣爆刷第105天之CodeTop100五连刷11-15

力扣爆刷第105天之CodeTop100五连刷11-15 文章目录 力扣爆刷第105天之CodeTop100五连刷11-15一、5. 最长回文子串二、33. 搜索旋转排序数组三、102. 二叉树的层序遍历四、200. 岛屿数量五、121. 买卖股票的最佳时机 一、5. 最长回文子串 题目链接&#xff1a;https://leetcode…

Unity VisionOS开发流程

Unity开发环境 Unity Pro, Unity Enterprise and Unity Industry 国际版 Mac Unity Editor(Apple silicon) visionOS Build Support (experimental) 实验版 Unity 2022.3.11f1 NOTE: 国际版与国服版Pro账通用&#xff0c;需要激活Pro的许可证。官方模板v0.6.2,非Pro版本会打…

微软开源项目Garnet:Redis的竞争者还是替代者?

对于开源社区&#xff0c;最近的一大新闻就是Redis宣布从7.4版本开始&#xff0c;将采用Redis源代码可用许可证&#xff08;RSALv2&#xff09;和服务器端公共许可证&#xff08;SSPLv1&#xff09;的双重许可证&#xff0c;取代原有的BSD三条款许可证。这一变化引发了开发者社…