首页 > 其他分享 >关于单向不循环链表的创建、插入、删除、遍历、检索

关于单向不循环链表的创建、插入、删除、遍历、检索

时间:2024-05-07 23:25:42浏览次数:19  
标签:检索 node head 遍历 链表 LINK printf 节点

关于单向不循环链表的创建、插入、删除、遍历、检索

单向不循环链表公式

image

初始化单向不循环链表

构建单向不循环链表结构体

//创建结构体类型
typedef struct one_way_node
{
    //数据域
    char data[DATA_LEN];

    //指针域
    struct one_way_node * next;

}ONE_WAY_NODE,*P_LINK;

创建一个新节点

//定义一个创建新节点的函数
P_LINK Create_New_Node()
{
    //申请堆空间并创建新节点
    P_LINK new_node = (P_LINK)malloc(sizeof(ONE_WAY_NODE));
    if(new_node == NULL)
    {
        perror("malloc failed");
        return (P_LINK)-1;
    }

    //对申请的堆空间进行清零
    memset(new_node,0,sizeof(ONE_WAY_NODE));

    //创建新节点的指针域指向空
    new_node->next = NULL;

    return new_node;
}

创建头节点

    //创建头节点
    P_LINK head_node = Create_New_Node();
    if(head_node == (P_LINK)NULL)
    {
        printf("创建头节点失败!\n");
        return -1;
    }
    else
    {
        printf("创建头节点成功!\n");
    }

创建一个模式选择函数

点击查看代码
// 创建一个功能函数用来进行检测操作链表的插入、删除、遍历、检索
int Mode_Selection(P_LINK head_node)
{
    // 如果头节点为空,输出提示信息并返回错误码
    if (head_node == (P_LINK)NULL)
    {
        printf("头节点为空!\n");
        return -1;
    }

    int select_num; // 用于存放用户输入的选择编号
    while (1)       // 无限循环,直到用户选择退出
    {
        system("clear"); // 清屏

        // 显示菜单项
        printf("<<<< 1 头插添加数据节点 >>>>\n");
        printf("<<<< 2 尾插添加数据节点 >>>>\n");
        printf("<<<< 3 指定检索数据节点 >>>>\n");
        printf("<<<< 4 指定添加数据节点 >>>>\n");
        printf("<<<< 5 指定删除数据节点 >>>>\n");
        printf("<<<< 6 遍历链表数据节点 >>>>\n");
        printf("<<<< 7 退出单向链表     >>>>\n");

        // 获取用户的指令输入
        scanf("%d", &select_num);

        // 根据用户选择进行相应的操作
        switch (select_num)
        {
            case 1:Head_Add_Node(head_node);break;                          // 头插法添加数据节点
            case 2:Tail_Add_Node(head_node);break;                          // 尾插法添加数据节点
            case 3:Retrieve_Add_Node(head_node,SEARCH_MODE_PRESENT);break;  // 检索目标数据节点并返回
            case 4:Appoint_Add_Node(head_node);break;                       // 目标位置添加数据节点
            case 5:Del_Add_Node(head_node);break;                           // 指定位置删除节点 
            case 6:Ergodic_List_Node(head_node);break;                      // 遍历整个链表并输出显示
            case 7:return 0;                                                // 退出单向链表
            default:printf("没有此项指令,请重新输入!\n");break;              // 输入无效,提示重新输入
        }
        sleep(1); // 延时1秒,使用户能看到执行结果
    }

    return 0;
}

插入数据节点

头插

点击查看代码
//头插法,插入链表
int Head_Add_Node(P_LINK head_node)
{
    //判断头节点是否异常
    if(head_node == (P_LINK)NULL)
    {
        printf("头节点异常!\n");
        return -1;
    }

    //创建一个新节点
    P_LINK new_node = Create_New_Node();
    if(new_node == (P_LINK)NULL)
    {
        printf("new node create failed!\n");
        return -1;
    }

    printf("请输入要添加的数据:");
    scanf("%s",new_node->data);
    while(getchar() != '\n');
    
    new_node->next  = head_node->next;  //头节点的下一个指针指向赋给新节点的下一个指针
    head_node->next = new_node;         //头节点的下一个指针指向新节点

    printf("头插成功,其数据:%s-----地址:%p\n",new_node->data,new_node);

    return 0;
}

尾插

点击查看代码
//尾插法,插入链表
int Tail_Add_Node(P_LINK head_node)
{
    //判断头节点是否异常
    if(head_node == (P_LINK)NULL)
    {
        printf("头节点异常!\n");
        return -1;
    }

    //创建新节点,进行尾插
    P_LINK new_node = Create_New_Node();
    if(new_node == (P_LINK)NULL)
    {
        printf("Create new node failed!\n");
        return -1;
    }

    
    printf("请输入要添加的数据:");
    scanf("%s",new_node->data);
    while(getchar() != '\n');

    //声明一个尾节点变量
    P_LINK end_node;
    //遍历整个链表,直到找到尾节点
    for(end_node = head_node;end_node->next != NULL; end_node = end_node->next);

    //找到尾节点后进行插入
    end_node->next = new_node;

    printf("尾插成功,其数据:%s-----地址:%p\n",new_node->data,new_node);

    return 0;
}

检索

点击查看代码
//检索整个链表
P_LINK Retrieve_Add_Node(P_LINK head_node, int search_mode)
{
    //判断头节点是否异常
    if(head_node == (P_LINK)NULL)
    {
        printf("头节点异常!\n");
        return (P_LINK)-1;
    }
    //判断是否是空链表
    if(head_node->next == (P_LINK)NULL)
    {
        printf("空链表,无需检索\n");
        return (P_LINK)0;
    }

    //定义变量,存储输入目标数据
    char obj_data[DATA_LEN] ="\0";
    printf("请输入要操作的数据:");
    scanf("%s",obj_data);

    //遍历单项不循环链表,找目标数据
    for(P_LINK tmp_node = head_node; tmp_node->next != NULL; tmp_node = tmp_node->next)
    {
        if(strcmp(tmp_node->next->data,obj_data) == 0) //如果成立,则tmp_node就是上一个结点
        {
            printf("找到该节点,其数据:%s----地址:%p\n",tmp_node->next->data,tmp_node);

            if(search_mode == SEARCH_MODE_PRESENT)  //判断是否当前节点的下一个节点
            {
                return tmp_node->next;              // 返回目标节点的下一个节点
            }

            if(search_mode == SEARCH_MODE_BEFOR)    //判断是否当前节点
            {
                return tmp_node;                    // 返回目标当前节点
            }
        }
    }

    printf("找不到对应的操作结点!!!\n");

    return (P_LINK)0; //PS:找不到你要的数据
}

指定位置插入

点击查看代码
// 定义函数 Appoint_Add_Node,用于在单向不循环链表中指定位置插入新节点
int Appoint_Add_Node(P_LINK head_node)
{
    //判断头节点是否异常
    if(head_node == (P_LINK)NULL)
    {
        printf("头节点异常!\n");
        return -1;
    }
    //判断空链表或者是否是只有一个数据链表
    else if(head_node->next == (P_LINK)NULL || head_node->next->next == (P_LINK)NULL)
    {
        printf("空链表或者一个数据节点直接尾插!\n");
        Tail_Add_Node(head_node);
    }
    else
    {
        //检索目标节点并在相应位置进行插入
        P_LINK obj_node = Retrieve_Add_Node(head_node,SEARCH_MODE_PRESENT);
        if(obj_node == (P_LINK)-1)
        {
            printf("链表异常,无法找到节点!\n");
            return -1;
        }
        else if(obj_node == (P_LINK)0)
        {
            printf("无该节点数据,重新输入!\n");
            return 0;
        }
        else
        {
            //创建新节点,进行插入
            P_LINK new_node = Create_New_Node();
            if(new_node == (P_LINK)NULL)
            {
                printf("创建新节点失败!\n");
                return -1;
            }

            printf("输入插入的数据:");
            scanf("%s",new_node->data);
            while(getchar() !='\n');

            //节点位置添加
            new_node->next  = obj_node->next; //先将新节点的下一个连接到目标节点下一个
            obj_node->next = new_node;        //目标节点的下一个为新节点
            
            printf("指定位置插入成功!\n");
        }
    }
    return 0;
}

删除

指定位置删除节点

点击查看代码
// 定义函数 Del_Add_Node,用于删除单向不循环链表中的指定节点
P_LINK Del_Add_Node(P_LINK head_node)
{
    //判断头节点是否异常
    if(head_node == (P_LINK)NULL)
    {
        printf("头节点异常!\n");
        return (P_LINK)-1;
    }
    //判断是否是空链表
    else if(head_node->next == (P_LINK)NULL)
    {
        printf("空链表,无需删除节点!\n");
        return (P_LINK)0;
    }
    else
    {
        //检索要删除的目标节点上一个
        P_LINK before_del_node = Retrieve_Add_Node(head_node,SEARCH_MODE_BEFOR);
        if(before_del_node == (P_LINK)-1)
        {
            printf("链表异常,删除失败!\n");
            return (P_LINK)-1;
        }
        else if(before_del_node == (P_LINK)0)
        {
            printf("无该数据节点,重新输入");
            return (P_LINK)0;
        }
        else
        {
            //找到删除节点,进行删除操作
            printf("数据节点删除:");

            P_LINK del_node       = before_del_node->next;  // 创建指针节点,指向要删除节点的下一个节点
            before_del_node->next = del_node->next;         // 将要删除节点的前一个节点的指针指向要删除节点的下一个节点,跳过要删除的节点
            del_node->next        = NULL;                   // 将要删除节点的指针指向 NULL,从而断开它与链表的连接

            printf("删除数据成功!\n");
            //释放其删除的节点空间
            free(del_node);

            return (P_LINK)0;
        }
    }
}

遍历

遍历显示整个单向不循环链表的功能实现

点击查看代码

// 定义函数 Ergodic_List_Node,用于遍历单向不循环链表并在用户终端显示
int Ergodic_List_Node(P_LINK head_node)
{
    //判断头节点是否异常
    if(head_node == (P_LINK)NULL)
    {
        printf("头节点异常!\n");
        return -1;
    }
    //判断是否是空链表
    if(head_node->next == (P_LINK)NULL)
    {
        printf("空链表,无需遍历\n");
    }

    //遍历并输出显示
    for(P_LINK tmp_node = head_node->next; tmp_node != NULL; tmp_node = tmp_node->next)
    {
        printf("%s----结点地址:%p\n",tmp_node->data,tmp_node);
    }

    return 0;
}

其它

头文件

#include <stdio.h>       // 标准输入输出头文件
#include <string.h>      // 字符串处理头文件        memset/清空
#include <stdlib.h>      // 标准库头文件            malloc/申请堆空间
#include <unistd.h>      // POSIX操作系统API头文件  sleep延时

//宏定义
#define DATA_LEN 20
#define SEARCH_MODE_PRESENT 1 //找当前
#define SEARCH_MODE_BEFOR   2 //上一个

函数声明

//声明一个创建新节点的函数
P_LINK Create_New_Node();
//声明一个指定删除的函数
P_LINK Del_Add_Node(P_LINK head_node);
//声明一个检索整个链表的函数
P_LINK Retrieve_Add_Node(P_LINK head_node, int search_mode);
//声明一个功能选择函数,检测链表各种模式
int Mode_Selection(P_LINK head_node);
//声明一个头插函数
int Head_Add_Node(P_LINK head_node);
//声明一个尾插函数
int Tail_Add_Node(P_LINK head_ndoe);
//声明一个遍历函数
int Ergodic_List_Node(P_LINK head_node);
//声明一个指定位置添加函数
int Appoint_Add_Node(P_LINK head_node);

main函数

int main()
{
    //创建头节点
    P_LINK head_node = Create_New_Node();
    if(head_node == (P_LINK)NULL)
    {
        printf("创建头节点失败!\n");
        return -1;
    }
    else
    {
        printf("创建头节点成功!\n");
    }

    //功能函数调用
    Mode_Selection(head_node);

    return 0;
}

标签:检索,node,head,遍历,链表,LINK,printf,节点
From: https://www.cnblogs.com/zhengdianshutiao-blogs/p/18178670

相关文章

  • Leetcode --- 203. 移除链表元素
    题目描述给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val==val 的节点,并返回 新的头节点 。示例1: 示例输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]输入:head=[7,7,7,7],val=7输出:[]参考实现方式1、使用递归实现......
  • 自定义单链表(非循环)的基本接口函数
    文件描述及头文件包含/********************************************************************* 文件名称: 单链表(非循环)的基本接口程序* 文件作者:[email protected]* 创建日期:2024/05/07* 文件功能:对单链表的增删改查功能的定义* 注意事项:No......
  • 自定义单链表(非循环)反转的基本函数接口
    题干structListNode*ReverseList(structListNode*head){if(head==NULL||head->next==NULL){returnhead;}else{structListNode*Phead=head;structListNode*temp=head->next;Phead->next=NULL;......
  • 检索增强生成(RAG)实践:基于LlamaIndex和Qwen1.5搭建智能问答系统
    检索增强生成(RAG)实践:基于LlamaIndex和Qwen1.5搭建智能问答系统什么是RAGLLM会产生误导性的“幻觉”,依赖的信息可能过时,处理特定知识时效率不高,缺乏专业领域的深度洞察,同时在推理能力上也有所欠缺。正是在这样的背景下,检索增强生成技术(Retrieval-AugmentedGeneration,RAG......
  • 如何根据二叉树遍历结果快速绘制二叉树
    一、已知前序遍历和中序遍历(1)前序遍历(根结点--->左子树--->右子树)ABDGHCEIF(2)中序遍历(左子树--->根结点--->右子树)GDHBAEICF注意:在最后连接二叉树时,注意先完玩左子树,再连右子树二、已知前后序遍历和中序遍历(1)后序遍历(左子树--->右......
  • 双向循环链表的实现
    /********************************************************************************************************** filename: Zqh_链表.c* author : [email protected]* date : 2024/05/05* function: 链表的增删改查* note : 模板* *Copyright(c)2023-202......
  • 双向链表实现
    /********************************************************************************************************** filename: Zqh_链表.c* author : [email protected]* date : 2024/05/05* function: 链表的增删改查* note : 模板* *Copyright(c)2023-202......
  • 单向循环链表的实现
    /********************************************************************************************************** filename: Zqh_链表.c* author : [email protected]* date : 2024/05/05* function: 链表的增删改查* note : 模板* *Copyright(c)2023-202......
  • 已知前中后序遍历的其中两种推断出最后一种序遍历
    已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是?方法1:首先可以确定c为根d为最左子树由中序debac假设b为第2排的子树那么后序的后两位应该是bcyu本题题目后序不符合由中序debac假设e为第2排的字数那么后序的后两位应该是ec符合本题题目后序由后......
  • 单链表逆序
    逆序原理:保留头节点下一个结点地址,将头节点断开,遍历除头节点以外的节点,将那些节点头插入头节点中。就能实习逆序。/********************************************************************* filename: demo2.c* author :lzj* date :2024/04/23* function:单向链......