单向链表(c/c++)

这篇具有很好参考价值的文章主要介绍了单向链表(c/c++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链表是一种常见的数据结构,其中运用到了结构体指针,链表可以实现动态存储分配,换而言之,链表是一个功能强大的数组,可以在某个节点定义多种数据类型,可以实现任意的添加,删除,插入节点等。(废话结束

前置知识:

地址,结构体,malloc函数与循环选择结构。


那我们先来学习一下malloc函数:

/*
格式为
(数据类型*)malloc(申请内存大小)
malloc函数可以通过传入要申请的内存大小在总堆里申请内存
之后会回归一个地址,在其前面的(数据类型*)是将这个地址定义
为要求数据类型。
*/

int* ptr=(int*)malloc(sizeof(int));
/*
sizeof是一个传入数据类型,返回其所占内存的函数
那么sizeof(int),就是一个int类型的数所占的内存
之后将申请到的内存转换为int类型存储
*/

int* ptd=(int*)malloc(5*sizeof(int));
//申请的内存大小为5*sizeof(int)也就是五个int类型的数字

之后我们来看通过结构体定义的链表节点

typedef struct Node{
    int data;//存储数据
    Node* next;//存储下个结点地址
}Node;//将结点名定义为Node

typedef Node* List;//相当于Node List[]
//一个结点数组就是一个链表

单向链表(c/c++),链表,c语言,c++

将多个结点通过next相连就变成了一个链表。


链表操作

        链表操作一般分为六部分:建立链表,插入结点,删除结点,查找结点,更新结点,遍历链表。我们将这六步写为六个函数依次实现。

建立链表:

        创建一个空链表,初始化头节点,并将头节点的指针置为NULL(在这里提一下,链表是没有规定长度的,我们一般在遍历到结点->next==NULL时认为链表结束)

void BuildList(List& L){
    node=(Node*)malloc(sizeof(Node));//申请一个结点内存
    //申请内存
    if(!node){//node==NULL时
        cout<<"申请失败\n";
        return;
    }
    node->next=NULL;
}

调用函数后,链表结构如下:(一个结点,data为空,看作头节点)

单向链表(c/c++),链表,c语言,c++

插入结点:

        插入结点分为两种方式:头插法和尾插法,我们通过动图来演示一下

        尾插法:

单向链表(c/c++),链表,c语言,c++

        头插法:

单向链表(c/c++),链表,c语言,c++

可以比较清楚的看出两者的差异,尾插法是将新建结点插入到链表末尾,头插法是将新建结点插入到链表头节点后面。下面分别是两种方法的代码实现:

void Postinsert(List& L){//尾插法
	Node* node=(Node*)malloc(sizeof(Node));
	//申请一个结点内存
	
	L->next=node;
	//尾结点更新为node 
	
	node->next=NULL;
	//尾结点下一位为NULL 
}
void Preinsert(List& L){//头插法
	Node node=(Node*)malloc(sizeof(Node));
	//申请一个结点内存
	
	node->next=L->next;
	//node结点下一位应为原来头节点下一位 
	
	L->next=node;
	//将node放入头节点的next位 
}

删除结点:

        找到要删除的节点,并将其删除,之后将删除节点的两侧相连。

        动图演示如下:

单向链表(c/c++),链表,c语言,c++

代码实现如下:

void DeleteNode(List& L,int t){//删除第t个结点
    Node* node=L->next;
    //定义结点指针
    Node* pre=L;
    //定义结点前一位指针
    
    while(--t){
    //while循环遍历第t个结点
        if(node==NULL){//当结点不存在时
            cout<<"此结点不存在\n";
            break;
        }
        pre=node;
        node=node->next;
        //更新pre,node指针
    }
    free(node);//释放内存   
}

查找结点:

        查找到 data为t 结点位于链表的第几位,并return位置

        动图演示如下:

        单向链表(c/c++),链表,c语言,c++

代码实现如下:

int SearchNode(List& L,int T){//查找data为T的结点
    int cnt=1;//记录位数
    Node* node=L->next;
    while(node!=NULL){
        if(node->data==T)
            return cnt;
        //找到时return位数
        
        node=node->next;
        cnt++;//更新node指针与位数
    }
    cout<<"未找到结点\n";
    return -1;
}

更新结点:

        找到要更新的节点位置,并将其data更新。

        动图演示如下:

        单向链表(c/c++),链表,c语言,c++

void UpdateNode(List& L,int a,int b){//将第a个结点data更新为b
    Node* node=L->next;
    //定义结点指针
    
    int cnt=1;
    //cnt用于计数
    
    while(node!=NULL){
        //while循环遍历找到第a个结点
        
        if(cnt==a){//找到结点时
            node->data=b;//update
            break;       //停止循环
        }
    
        cnt++;
        node=node->next;
        //更新cnt和结点指针
    }
    if(node==NULL)//结点不存在时
        cout<<"该结点不存在\n";
}

遍历链表:

        遍历整个链表,输出每个结点的值

        动图演示如下:

单向链表(c/c++),链表,c语言,c++

代码实现如下:

void ErgodicList(List& L){//遍历输出
    Node* node=L->next;
    cout<<"链表遍历结果如下:\n";
    while(node!=NULL){
        cout<<node->next<<" ";
        node=node->next;
    }
    cout<<"\n";
}

结束


 文章来源地址https://www.toymoban.com/news/detail-703842.html

到了这里,关于单向链表(c/c++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构初阶】三、 线性表里的链表(无头+单向+非循环链表 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】二、 线性表里的顺序表(C语言实现顺序表)-CSDN博客  =========================

    2024年02月08日
    浏览(57)
  • 数据结构入门(C语言版)线性表中链表介绍及无头单向非循环链表接口实现

    概念 : 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 。因此,为了表示每个数据元素与其直接后继数据元素之间的逻辑关系,对数据元素来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这

    2023年04月09日
    浏览(49)
  • 数据结构_链表_单向循环链表的初始化、插入、删除、修改、查询打印(基于C语言实现)

    版本: 2024年4月25日 V1.0 发布于博客园 目录 目录 单向循环链表公式 初始化单向循环链表 构建单向循环链表结点 创建一个空链表(仅头结点) 创建一个新结点 插入数据 头插 中插 尾插 删除数据 头删 中删 尾删 查询打印数据 遍历打印 测试 测试结果: 完整代码 CircularLinkedLis

    2024年04月25日
    浏览(51)
  • 数据结构:详解【链表】的实现(单向链表+双向链表)

    1.顺序表的问题和思考 问题: 中间/头部的插入删除,时间复杂度为O(N)。 增容需要申请新空间,拷贝数据,释放旧空间,会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据

    2024年03月26日
    浏览(65)
  • 【数据结构】单向链表

    哈喽,大家好,今天我们学习的是数据结构里的链表,这里主要讲的是不带哨兵卫头节点的单向链表,下篇将会继续带大家学习双向链表。 目录 1.链表的概念 2.单向链表接口的实现 2.1动态申请一个节点 2.2单链表打印 2.3单链表尾插 2.4单链表头插 2.5单链表尾删 2.6单链表头删

    2024年02月11日
    浏览(53)
  • 【算法】Java-使用数组模拟单向链表,双向链表

    目录 试题1:实现一个单链表,并实现以下功能: 试题2:实现一个双链表,并实现以下功能 思路总结: 什么情况下可能涉及到用数组实现链表呢?       在学习时了解到了可以用数组模拟链表,使其兼顾数据查找快,链表新增和删除快的缺点,找来一些试题实现了下,如下

    2024年02月09日
    浏览(48)
  • 数据结构——实现单向链表

    单链表是一种常见的数据结构,用于存储一系列的数据元素,每个节点包含数据和指向下一个节点的指针。 单链表通常用于实现某些算法或数据结构,如链式前向星、哈希表、链式栈、队列等等。 单链表在程序设计中的作用不可忽略,是很多基础算法的核心数据结构之一。

    2024年02月07日
    浏览(57)
  • 单向链表(c/c++)

    链表是一种常见的数据结构,其中运用到了结构体指针,链表可以实现动态存储分配,换而言之,链表是一个功能强大的数组,可以在某个节点定义多种数据类型,可以实现任意的添加,删除,插入节点等。(废话结束 前置知识: 地址,结构体,malloc函数与循环选择结构。 那

    2024年02月09日
    浏览(39)
  • 【数据结构篇】手写双向链表、单向链表(超详细)

    什么是链表 ? 链表(Linked List)是用链式存储结构实现的线性表。链表示意图: 链表的组成 : 数据域 + 引用域 (数据域和引用域合称结点或元素) 数据域存放数据元素自身的数据 引用域存放相邻结点的地址 链表的特点 : 链表中元素的联系依靠引用域 具有线性结构的特

    2024年02月11日
    浏览(41)
  • 单向不带头链表的使用

    后插(将值为x的元素插入到第i个位置)  前插操作     画图时应先画物理结构图在画逻辑结构图  链表的结点查找 结点的创建

    2024年01月20日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包