C语言实现单链表

一、什么是单链表

1.链表就是一种在物理存储上各个节点非连续的,随机的,元素的逻辑顺序是通过链表中的指针链接的次序而实现的。

图示:

二、单链表中节点的定义

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

typedef struct node{

        int data;//数据域

        struct node * next//指向下一个节点的指针

}Lnode,*LinkList;//Lnode 表示链表中的一个节点,二*LinkList表示整个链表,也可以表示单链表的头指针。

三、单链表的实现方式

1.带头节点的单链表:

1.头节点是一种不存数据,只存放下一个的地址的特殊节点,我们使用头节点是为了方便单链表接下来的插入与删除等操作。

2.带头节点的单链表的初始化操作

这里可以只用值传递而不用地址传递就可以完成对L头结点的空间开辟,是由于:

LinkList InitSqList(LinkList L){

        L = (Lnode*)malloc(sizeof(Lnode));

        if(L == NULL){

                printf("单链表初始化失败\n");

                return NULL;

        }

        L->data = 0;

        L->next = NULL;

        printf("单链表初始化成功\n");

        return L;

}

//在main函数里调用该函数

int main(){

        L = (Lnode*)malloc(sizeof(Lnode));

}

3.使用头插法创建单链表:

bool CreateListByHead(LinkList L){

    if(L == NULL){

        printf("链表还未初始化\n");

        return false;

    }

    int x;

    printf("请输入你要插入的值\n");

    scanf("%d",&x);

    Lnode* p = L;

    Lnode* node = NULL;

    while(x != 999){

        node = (Lnode*)malloc(sizeof(Lnode));

        node->data = x;

        node->next = p->next;

        p->next = node;

        scanf("%d",&x);

    }

    return true;

   

}

4.使用尾差法创建单链表:

开始:

/*4.2 头插法创建链表*/

bool CreateListByHead(LinkList L){

    if(L == NULL){

        printf("链表还未初始化\n");

        return false;

    }

    int x;

    printf("请输入你要插入的值\n");

    scanf("%d",&x);

    Lnode* p = L;

    Lnode* node = NULL;

    while(x != 999){

        node = (Lnode*)malloc(sizeof(Lnode));

        node->data = x;

        node->next = p->next;

        p->next = node;

        scanf("%d",&x);

    }

    return true;

   

}

5.根据指定位置插入指定元素

p节点开始指向头节点,定义一个int 类型的i变量初始值为0

我们的目标是找到插入位置的前一个节点,比如我们插入的位置为2,我们寻找的目标节点为1节点,接下来让p向后移动一个节点的位置,让i++

发现找到位置了,就让代插入节点插入1节点之后

这样就完成插入算法了。

我们再解释一下while(p != NULL && i < index - 1)循环推出条件,当满足 i < index - 1退出循环就是上面我说的情况,找到位置了,当满足的是p != NULL说明p指向空时依然没有找到你输入的位置说明你输入的位置过大。

/*2.根据指定位置插入指定元素 */

bool InsertElementByIndex(LinkList L,int index,int element){

    if(index < 1){

        printf("插入的位置不合法\n");

        return false;

    }

    Lnode* p = L;//定义一个指针指向头结点

    int i = 0;

    while(p != NULL && i < index - 1){

        p = p->next;

        i++;

    }

    if(p == NULL){

        printf("插入的位置过大\n");

        return false;

    }

    //创建一个新节点

    Lnode* node = (Lnode*)malloc(sizeof(Lnode));

    node->data = element;

    //插入操作

    node->next = p->next;

    p->next = node;

    printf("插入成功\n");

    return true;

}

5.删除指定位置的元素

/*删除指定位置的元素,位置为下表+1,并保存被删除的值*/

bool DeleteElementByIndex(LinkList L,int index,int *element){

    if(L->next == NULL){

        printf("链表为空\n");

        return false;

    }

    if(index < 1){

        printf("删除的位置太小\n");

        return false;

    }

    //定义两个指针,p q

    Lnode* p = L;

    Lnode* q = L->next;

    int i = 1;

    while(q != NULL && i <= index-1){

        p = q;

        q = q->next;

        i++;

    }

    if(q == NULL){

        printf("你输入的位置过大\n");

        return false;

    }

    *element = q->data;

    p->next = q->next;

    free(q);

    printf("删除成功\n");

    return true;

}

6.删除链表中的元素,根据值删除元素,返回删除元素的个数

int DeleteElementByValue(LinkList L,int element){

    if(L->next == NULL){

        printf("链表为空\n");

        return false;

    }

    int count = 0;//记录删除元素的个数

    Lnode* p = L->next;

    Lnode* q = L;

    Lnode* f = NULL;

    while(p != NULL){

        if(p->data == element){

            f = p;

            p = p->next;

            q->next = f->next;

            free(f);

            f = NULL;

            count++;

        }else{

            q = p;

            p = p->next;

        }

       

    }

    printf("删除成功\n");

    return count;

}

7.查找链表中的元素,根据位置index查找对应的元素的值。

/*7,查找链表中的元素,根据位置index查找对应的元素的值。*/

int SelectElementByIndex(LinkList L,int index){

    if(L->next == NULL){

        printf("链表为空\n");

        exit(-1);

    }

    if(index < 1){

        printf("查找的位置太小\n");

        exit(-1);

    }

    //定义一个Lnode类型的指针指向L的头结点后的第一个元素

    Lnode* p = L->next;

    int i = 1;

    while(p != NULL && i <= index - 1){

        p = p->next;

        i++;

    }

    if(p == NULL){

        printf("你输入的位置过大\n");

        exit(-1);

    }

    printf("查找成功\n");

    return p->data;

}

8.修改链表的指定位置的值

/*8.修改链表的指定位置的值*/

bool UpdateElementByIndex(LinkList L,int index,int element){

    if(L->next == NULL){

        printf("链表为空\n");

        return false;

    }

    if(index < 1){

        printf("查找的位置太小\n");

        return false;

    }

    Lnode* p = L->next;

    int i = 1;

    while(p != NULL && i <= index-1){

        p = p->next;

        i++;

    }

    if(p == NULL){

        printf("你输入的位置过大\n");

        return false;

    }

    p->data = element;

    printf("修改成功\n");

    return true;

}

9.求表长

/*9.求表长*/

int ListLength(LinkList L){

    int len = 0;

    Lnode* p = L;

    while(p->next != NULL){

        p = p->next;

        len++;

    }

    return len;

}

10.翻转链表的内容

本题的思想是将链表的头结点与其他节点断开,在进行头插法实现链表内容的翻转。

先让指针p指向1节点,

断开头结点与1节点的链接,让头结点指向空

先让q指向p所指向的位置,再让p指向下一个节点

再让q所指向的节点使用头插法重新插入头结点后的位置

插入后再让指针q指向p,p再向后移动一个节点的位置。

再将q指向的2节点使用头插法进入左边的链表,

再将指针q指向指针p指向的节点,p再向后移动一个节点。

再使用头插法将q所指向的3节点插入左边的节点,

当p为空时,循环停止,这样就实现了链表内容的翻转。

/*10.翻转链表的内容*/

void reverseLinkList(LinkList L){

    if(L->next == NULL){

        printf("链表为空\n");

        return;

    }

    Lnode* p = L->next;

    Lnode* q = NULL;

    L->next = NULL;

    while(p != NULL){

        q = p;

        p = p->next;

        q->next = L->next;

        L->next = q;

    }

}

11.找到链表中的最大值

/*11.找到链表中的最大值*/

int FindMax(LinkList L){

    if(L->next == NULL){

        printf("链表为空\n");

        exit(-1);

    }

    Lnode* p = L->next;

    int max = p->data;

    while(p != NULL){

        if(max < p->data){

            max = p->data;

        }

        p = p->next;

    }

    return max;

}

12.整个代码实现:

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

typedef struct Lnode{

    int data;//单链表中的元素值

    struct Lnode* next;//单链表中指向下一个节点的指针

}Lnode,*LinkList;

/*1.初始化单链表*/

LinkList InitLinkList(LinkList L){

    //1.创建一个头结点并为其开辟空间

    L = (Lnode*)malloc(sizeof(Lnode));

    if(L == NULL){

        printf("创建失败\n");

        return NULL;

    }

    L->data = 0;

    L->next = NULL;

    printf("创建成功\n");

    return L;

}

/*2.根据指定位置插入指定元素 */

bool InsertElementByIndex(LinkList L,int index,int element){

    if(index < 1){

        printf("插入的位置不合法\n");

        return false;

    }

    Lnode* p = L;//定义一个指针指向头结点

    int i = 0;

    while(p != NULL && i < index - 1){

        p = p->next;

        i++;

    }

    if(p == NULL){

        printf("插入的位置过大\n");

        return false;

    }

    //创建一个新节点

    Lnode* node = (Lnode*)malloc(sizeof(Lnode));

    node->data = element;

    //插入操作

    node->next = p->next;

    p->next = node;

    printf("插入成功\n");

    return true;

}

/*3.打印链表*/

void printLinkList(LinkList L){

    if(L->next == NULL){

        printf("链表为空\n");

        return;

    }

    Lnode* p = L->next;

    while(p != NULL){

        printf("%d\t",p->data);

        p = p->next;

    }

    printf("\n");

}

/*4.头插法创建链表*/

bool InsertHead(LinkList L,int element){

    //判断链表为空

    if(L == NULL){

        printf("链表未初始化\n");

        return false;

    }

    //创建一个新节点,并插入到头节点后面

    Lnode* node = (Lnode*)malloc(sizeof(Lnode));

    node->data = element;

    node->next = L->next;

    L->next = node;

    printf("插入成功\n");

    return true;

}

/*4.2 头插法创建链表*/

bool CreateListByHead(LinkList L){

    if(L == NULL){

        printf("链表还未初始化\n");

        return false;

    }

    int x;

    printf("请输入你要插入的值\n");

    scanf("%d",&x);

    Lnode* p = L;

    Lnode* node = NULL;

    while(x != 999){

        node = (Lnode*)malloc(sizeof(Lnode));

        node->data = x;

        node->next = p->next;

        p->next = node;

        scanf("%d",&x);

    }

    return true;

   

}

/*5.尾差法创建链表*/

bool InsertTail(LinkList L,int element){

    if(L == NULL){

        printf("链表还未创建\n");

        return false;

    }

    //创建一个节点

    Lnode* node = (Lnode*)malloc(sizeof(Lnode));

    node->data = element;

    //创建一个指针指向头结点,并移动值最后一个节点。

    Lnode* p = L;

    while(p->next != NULL){

        p = p->next;

    }

    node->next = p->next;

    p->next = node;

    printf("创建成功\n");

    return true;

}

/*6.删除指定位置的元素,位置为下表,并保存被删除的值*/

bool DeleteElementByIndex(LinkList L,int index,int *element){

    if(L->next == NULL){

        printf("链表为空\n");

        return false;

    }

    if(index < 1){

        printf("删除的位置太小\n");

        return false;

    }

    //定义两个指针,p q

    Lnode* p = L;

    Lnode* q = L->next;

    int i = 1;

    while(q != NULL && i <= index-1){

        p = q;

        q = q->next;

        i++;

    }

    if(q == NULL){

        printf("你输入的位置过大\n");

        return false;

    }

    *element = q->data;

    p->next = q->next;

    free(q);

    printf("删除成功\n");

    return true;

}

/*6.2删除链表中的元素,根据值删除元素,返回删除元素的个数*/

int DeleteElementByValue(LinkList L,int element){

    if(L->next == NULL){

        printf("链表为空\n");

        return false;

    }

    int count = 0;//记录删除元素的个数

    Lnode* p = L->next;

    Lnode* q = L;

    Lnode* f = NULL;

    while(p != NULL){

        if(p->data == element){

            f = p;

            p = p->next;

            q->next = f->next;

            free(f);

            f = NULL;

            count++;

        }else{

            q = p;

            p = p->next;

        }

       

    }

    printf("删除成功\n");

    return count;

}

/*7,查找链表中的元素,根据位置index查找对应的元素的值。*/

int SelectElementByIndex(LinkList L,int index){

    if(L->next == NULL){

        printf("链表为空\n");

        exit(-1);

    }

    if(index < 1){

        printf("查找的位置太小\n");

        exit(-1);

    }

    //定义一个Lnode类型的指针指向L的头结点后的第一个元素

    Lnode* p = L->next;

    int i = 1;

    while(p != NULL && i <= index - 1){

        p = p->next;

        i++;

    }

    if(p == NULL){

        printf("你输入的位置过大\n");

        exit(-1);

    }

    printf("查找成功\n");

    return p->data;

}

/*8.修改链表的指定位置的值*/

bool UpdateElementByIndex(LinkList L,int index,int element){

    if(L->next == NULL){

        printf("链表为空\n");

        return false;

    }

    if(index < 1){

        printf("查找的位置太小\n");

        return false;

    }

    Lnode* p = L->next;

    int i = 1;

    while(p != NULL && i <= index-1){

        p = p->next;

        i++;

    }

    if(p == NULL){

        printf("你输入的位置过大\n");

        return false;

    }

    p->data = element;

    printf("修改成功\n");

    return true;

}

/*9.求表长*/

int ListLength(LinkList L){

    int len = 0;

    Lnode* p = L;

    while(p->next != NULL){

        p = p->next;

        len++;

    }

    return len;

}

/*10.翻转链表的内容*/

void reverseLinkList(LinkList L){

    if(L->next == NULL){

        printf("链表为空\n");

        return;

    }

    Lnode* p = L->next;

    Lnode* q = NULL;

    L->next = NULL;

    while(p != NULL){

        q = p;

        p = p->next;

        q->next = L->next;

        L->next = q;

    }

}

/*11.找到链表中的最大值*/

int FindMax(LinkList L){

    if(L->next == NULL){

        printf("链表为空\n");

        exit(-1);

    }

    Lnode* p = L->next;

    int max = p->data;

    while(p != NULL){

        if(max < p->data){

            max = p->data;

        }

        p = p->next;

    }

    return max;

}

int main(){

    LinkList L;

    L = InitLinkList(L);

    CreateListByHead(L);

    printLinkList(L);

    //InsertElementByIndex(L,6,100);

    reverseLinkList(L);

    printLinkList(L);

    int e = 0;

    DeleteElementByIndex(L,5,&e);

    printLinkList(L);

    //printf("最大值为%d\n",FindMax(L));

    // InsertElementByIndex(L,1,10);

    // InsertElementByIndex(L,1,20);

    // InsertElementByIndex(L,1,30);

    // InsertHead(L,10);

    // InsertHead(L,20);

    // InsertHead(L,30);

    // InsertHead(L,40);

    // InsertHead(L,50);

    // printLinkList(L);

    //printf("单链表的长度为:%d\n",ListLength(L));

    // InsertElementByIndex(L,2,1000);

    // InsertTail(L,10);

    // InsertTail(L,20);

    // InsertTail(L,10);

    // InsertTail(L,40);

    // InsertTail(L,10);

    // printLinkList(L);

    // int count = DeleteElementByValue(L,10);

    // printf("被删除的元素个数%d\n",count);

    // printLinkList(L);

    // int element;

    // DeleteElementByIndex(L,2,&element);

    // printf("删除的元素为%d\n",element);

    // printLinkList(L);

    // int e = SelectElementByIndex(L,2);

    // printf("查找的元素值为%d\n",e);

    // UpdateElementByIndex(L,0,1000);

    // printLinkList(L);

}

四、总结:

链表的实现不难,我们在写代码时最好一边写代码一边画图,这样更方便我们理解。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

机械学习—零基础学习日志(数学基础汇总2)

零基础为了学人工智能&#xff0c;正在艰苦的学习 我比较推荐&#xff0c;《三个月从零入门深度学习&#xff0c;保姆级学习路线图》的整体学习思路&#xff0c;但因为数学基础太差&#xff0c;而且针对所需的数学系统知识&#xff0c;我依然没有很明确的学习方向。 所以直接使…

高性能日志系统 日志格式化输出逻辑

概述 日志消息是由许多要素组成&#xff0c;而日志格式化的主要作用&#xff0c;即是对日志消息进行格式化&#xff0c;组织成自己指定好的字符串结构 总体架构 日志消息&#xff08;LogMsg&#xff09; 用于存储各种日志信息&#xff0c;例如存储日志的级别、时间、行号等信息…

Summernote 富文本编辑器的内容变成只读模式

我 | 在这里 ⭐ 全栈开发攻城狮、全网10W粉丝、2022博客之星后端领域Top1、专家博主。 &#x1f393;擅长 指导毕设 | 论文指导 | 系统开发 | 毕业答辩 | 系统讲解等。已指导60位同学顺利毕业 ✈️个人公众号&#xff1a;热爱技术的小郑。回复 Java全套视频教程 或 前端全套视频…

【安卓】动态加载布局技巧

文章目录 使用限定符常见限定符 使用最小宽度限定符 使用限定符 修改FragmentTest项目中的activity_main.xml文件 <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"android:orientation"horizontal"android:layout_width&quo…

JavaScript constructor原型原型继承

constructor 在 JavaScript 中&#xff0c;构造函数是一种特殊的函数&#xff0c;使用 new 关键字来调用&#xff0c;用于创建对象实例。JavaScript 中的构造函数通常通过 function 关键字定义。 例如&#xff1a; function Person(name, age) {this.name name;this.age a…

4.MySQL数据类型

目录 数据类型 ​编辑数值类型 tinyint类型 bit类型 float类型 decimal类型 字符串类型 char类型 varchar varchar和char的区别 日期和时间类型 数据类型 数值类型 说明一下&#xff1a;MySQL本身是不支持bool类型的&#xff0c;当把一个数据设置成bool类型时&#x…

C#复习之封装_构造函数,析构函数,垃圾回收

知识点一&#xff1a;构造函数 基本概念 在实例化对象时 会调用的用于初始化的函数 如果不写 默认存在一个无参构造函数 构造函数的写法 1.没有返回值 2.函数名和类名必须相同 3.没有特殊需求时 一般都是public的 4.构造函数可以被重载 5.this代表当前调用该函数的对象自己 注…

【多线程】synchronized原理

文章目录 一、锁升级 (面试经常考)偏向锁 二、锁消除三、锁粗化锁的粒度 四、相关面试题 结合 锁策略&#xff0c;我们就可以总结出&#xff0c;synchronized具有以下特性&#xff1a; 乐观悲观&#xff0c;自适应重量轻量&#xff0c;自适应自旋挂起等待&#xff0c;自适应非…

Gradio 快速开发网页应用

Gradio 是一个开源的 Python 框架&#xff0c;可以快速开发页面&#xff0c;Gradio 主要用于 AI 模型 Demo 的开发&#xff0c;通过几行代码可以快速生成一个 Web Demo&#xff0c;由于 AI 算法工程师使用的都是 Python 语言&#xff0c;使用 Python 开发 Demo 会相对简单&…

演示:基于WPF的DrawingVisual开发GS(2019)1822号矢量中国地图一

一、目的&#xff1a;基于WPF的DrawingVisual开发的矢量地图 二、预览 默认样式 深黑样式 深蓝色样式 深蓝色透明样式 演示&#xff1a;基于WPF的DrawingVisual开发GS(2019)1822号矢量中国地图二-CSDN博客VS2022&#xff0c;net7演示&#xff1a;基于WPF的DrawingVisual开发GS…

DVWA—SQL(Blind)实例

DVWA—SQL Injection&#xff08;Blind&#xff09;实例 预备知识 在SQL注入中会有回显注入和盲注入的形式&#xff0c;在前面的文章中展示了回显注入的情况&#xff0c;而盲注入就是当我输入查询语句的时候数据并不会直接显示在页面中而是以程序员规定的输出格式来进行显示&…

【数据结构和算法】(基础篇二)——链表

链表 数组最麻烦的地方就是其在建立之后大小固定&#xff0c;对于增删数据很不方便。链表的出现解决了这个问题&#xff0c;链表的元素不是在内存中连续存储的&#xff0c;而是通过指针链接在一起的节点集合&#xff0c;这样的设计让链表有了动态的大小。链表是树和图结构的基…

Windows11 WSL2 Ubuntu编译安装perf工具

在Windows 11上通过WSL2安装并编译perf工具&#xff08;Linux性能分析工具&#xff09;可以按以下步骤进行。perf工具通常与Linux内核一起发布&#xff0c;因此你需要确保你的内核版本和perf版本匹配。以下是安装和编译perf的步骤&#xff1a; 1. 更新并升级系统 首先&#x…

Unity数据持久化 之 Json序列化与反序列化

语法规则可以看这篇文章&#xff1a;Unity数据持久化 之 Json 语法速通-CSDN博客 Q:Unity是通过什么来对Json文件进行处理的&#xff1f; A:JsonUtility&#xff1a;Unity 提供了 JsonUtility 类&#xff0c;用于将对象序列化为 JSON 字符串或将 JSON 字符串反序列化为对象。…

大数据-72 Kafka 高级特性 稳定性-事务 (概念多枯燥) 定义、概览、组、协调器、流程、中止、失败

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…

DC-5靶机渗透测试

DC-5靶场 文章目录 DC-5靶场信息收集漏洞发现漏洞利用 --- 日志文件包含漏洞利用 --- 文件包含过滤器链的RCEshell反弹权限提升 信息收集 使用--scriptvuln扫描发现了一个thankyou.php界面 感觉会有问题&#xff0c;前往访问网站信息 漏洞发现 来到thankyou.php界面&#xff…

haproxy详解

目录 一、haproxy简介 二、什么是负载均衡 2.1 负载均衡的类型 2.2.1 硬件 2.2.2 四层负载均衡 2.2.3 七层负载均衡 2.2.4 四层和七层的区别 三、haproxy的安装及服务信息 3.1 示例的环境部署&#xff1a; 3.2 haproxy的基本配置信息 3.2.1 global 配置参数介绍 3…

sleuth+zipkin分布式链路追踪

概述 结构图 常见的链路追踪 cat zipkin pinpoint skywalking sleuth Sleuth介绍 Trace Span Annotation 使用Sleuth 添加依赖 <!--sleuth--><dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starte…

运维工具的衍化对运维工作的新挑战

运维工具的衍化对运维工作产生了深远的影响&#xff0c;这些影响体现在多个方面&#xff0c;包括提升运维效率、优化资源配置、增强故障应对能力、促进团队协作与沟通&#xff0c;以及面临新的挑战如数据安全和隐私保护等。运维工具的衍化对运维工作带来了多方面的新挑战&#…

Yolo-World初步使用

Yolo v8目前已经支持Yolo-World&#xff0c;整理一下初步使用步骤。 使用步骤 1 先下载Yolo-World的pt文件&#xff0c;下载地址&#xff1a;GitHub - AILab-CVC/YOLO-World: [CVPR 2024] Real-Time Open-Vocabulary Object Detection 官网应该是点这里&#xff08;有个笑脸…