【数据结构】链表 详解

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

我们不废话,直入正题。

引入

什么是链表?

来看看百度怎么说:

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

可以发现:

每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域

链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

这些,就是链表的特性。

【数据结构】链表 详解

这就是链表的概念图。Blue、Yellow、Red 这 3 个字符串作为数据被存储于链表的数据域中。每个数据都有 1 个 “指针”,它指向下一个数据的内存地址,这被称为指针域


了解完概念,我们就要来看看基本操作了。

一.创建

上面看到:

每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

一个结点,可用一个结构体存储(此处表示为Lnode)。

数据域就很简单,我们通常用再搞一个结构体来存储。

而指针呢?

在链表的创建中,我们需要添加一个指向下一个节点的指针,这个指针保存的是下一个节点的地址

那么指针的类型是什么呢?当然是Lnode了,因为指针指向的,是下一个结点。

下面引入一段话来帮助理解:

将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量。

那么,就可以实现了。


struct Lnode{
    ElemType data;//数据域
    struct Node *next;//指针域
};

二.初始化

说是初始化,实际上是在创建结点。那么,只需开辟一个类型为Lnode的空间即可。

如何开辟空间?

我们需要一个new。

new是什么?

new其实就是计算机开辟一段新的空间,但是和一般的声明不同的是,new开辟的空间在堆上,而一般声明的变量存放在栈上。通常来说,当在局部函数中new出一段新的空间,该段空间在局部函数调用结束后仍然能够使用,可以用来向主函数传递参数。另外需要注意的是,new的使用格式,new出来的是一段空间的首地址。所以一般需要用指针来存放这段地址。
————————————————
版权声明:本内容为CSDN博主「柒笙歌」的原创
原文链接: C++之new的详解_new c++_柒笙歌的博客-CSDN博客

算了,不乱说了,自己搜搜看吧!然后,接着来。

真正的初始化

不过,这个结点后面还没有其它的结点,因此其指针域的指向应该是空的。

这里,我们用NULL表示。

NULL是什么?

Null是在计算中具有保留的值,用于指示 指针不引用有效对象。

这句话很显然的点明了。

在C++中,NULL可以直接赋值给指针。因此就很简单了!

代码实现


void InitList(Lnode* &L)//初始化 
{
    L=new Lnode;
    L->next=NULL;
}

三.判断是否为空链表

首先,我们要知道,什么是空链表?

空链表:链表中无元素。(头指针和头结点仍在)

也就是说,头结点的指针域的指向为空

那么,就非常简单了。


bool check(Lnode* L)//判断是否为空 
{
    if(L->next==NULL) return 0;//空 
    return 1;
}

四.清空链表(不留头结点)

用一个L表示当前头结点,用p表示当前节点。

每次就将p转到L的下一个,然后释放L,在将L变为p。以此不断循环,直到p为空。

代码如下:


void xiaohui(linklist &L)//全部删掉 (不留头结点)
{
    Lnode *p;//linklist L
    while(p)
    {
        L=p;
        p=p->next;
        free(L);
    }
} 

五.变成空表(留头结点)

这与上面的只有一个区别。题目写得很清楚:留头结点

那么我们只用q替代L,帮p探路。那么,在p为NULL时,我们还可知道原来的头结点的指针——就是L

好,上代码:


void qk(linklist &L)//变成空表(留头结点) 
{
    Lnode *p,*q;//linklist L
    q=L->next;
    while(p)
    {
        p=q;
        q=q->next;
        free(p);
    }
    L->next=NULL; 
}

五.查找、访问

【数据结构】链表 详解

相对于数组,链表的数据是分散储存于数组的随机位置的。

【数据结构】链表 详解

因为数据都是分散存储的,所以如果想要访问 数据,只能从第1个数据开始,顺着指针的指 向一一往下访问(这便是顺序访问)。比如,想 要找到Red这一数据,就得从Blue开始访问。

【数据结构】链表 详解

这之后,还要经过 Yellow,我们才能找到 Red。

也比较基础,上代码!


int cz(linklist L,char mz[])//查找 
{
    Lnode *p=L->next;
    while(p)
    {
        if(strcmp(mz,p->data.name)==0) break;
        p=p->next;
    }
    if(!p)
    {
        return 0;
    }
    return 1;
}

六.添加

【数据结构】链表 详解

如果想要添加数据,只需要改变添加位置前后 的指针指向就可以,非常简单。比如,在Blue 和Yellow之间添加Green。

【数据结构】链表 详解

将 Blue 的指针指向的位置变成 Green,然后再 把Green的指针指向Yellow,数据的添加就大功告成了。

代码如下:


int cr(linklist &L,int x,ElemType e)//插入
{
    int i=0;
    Lnode *p=L;
    while(p&&i<x-1)
    {
        p=p->next;
        i++;
    }
    Lnode *s=new Lnode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return 1;
}

七.删除

【数据结构】链表 详解

数据的删除也一样,只要改变指针的指向就可 以,比如删除Yellow。

这时,只需要把 Green 指针指向的位置从 Yellow 变成 Red,删除就完成了。但是, Yellow 本身还存储在 内存中,需要把它释放掉(可以用free数组)

看代码:


int cr(linklist &L,int x,ElemType &e)//删除第x个节点,并返回删除值 
{
    int i=1;
    Lnode *p=L->next,*t;
    while(p&&i<x-1)
    {
        p=p->next;
        i++;
    }
    t=p->next;
    p->next=p->next->next;
    free(t);
    return 1;
}

基本操作汇总


#include<bits/stdc++.h>
using namespace std;
typedef struct student{
    char name[8];
    int num;
    int cj;
}ElemType;
typedef struct Lnode{
    ElemType data;
    struct Lnode *next;
}Lnode,*linklist;
void InitList(linklist &L)//初始化 
{
    L=new Lnode;
    L->next=NULL;
}
bool check(linklist L)//判断是否为空 
{
    if(L->next==NULL) return 0;//空 
    return 1;
}
void xiaohui(linklist &L)//全部删掉 
{
    Lnode *p;//linklist L
    while(p)
    {
        L=p;
        p=p->next;
        free(L);
    }
}
void qk(linklist &L)//变成空表(留头结点) 
{
    Lnode *p,*q;//linklist L
    q=L->next;
    while(p)
    {
        p=q;
        q=q->next;
        free(p);
    }
    L->next=NULL; 
}
int bc(linklist &L)//链表的长度
{
    int s=0;
    Lnode *p;
    p=L->next;
    while(p)
    {
        s++;
        p=p->next;
    }
    return s;
}
int qz(linklist &L,int x,ElemType &a)//取第x个的值
{
    int i=1; 
    Lnode *p=L->next;
    while(p&&i<x)
    {
        p=p->next;
        i++;
    }
    if(!p)
    {
        return 0;
    }
    a=p->data;
    return 1;
}
int cz(linklist L,char mz[])//查找 
{
    Lnode *p=L->next;
    while(p)
    {
        if(strcmp(mz,p->data.name)==0) break;
        p=p->next;
    }
    if(!p)
    {
        return 0;
    }
    return 1;
}
int cr(linklist &L,int x,ElemType e)//插入
{
    int i=0;
    Lnode *p=L;
    while(p&&i<x-1)
    {
        p=p->next;
        i++;
    }
    Lnode *s=new Lnode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return 1;
}
int cr(linklist &L,int x,ElemType &e)//删除第x个节点,并返回删除值 
{
    int i=1;
    Lnode *p=L->next,*t;
    while(p&&i<x-1)
    {
        p=p->next;
        i++;
    }
    t=p->next;
    p->next=p->next->next;
    free(t);
    return 1;
}
int tc(int n,linklist &L)//建立头插法
{
    Lnode *p;
    for(int i=1;i<=n;i++)
    {
        p=new Lnode;
        //cin>>p->data;
        p->next=L->next;
        L->next=p;
    }
}
int tc(int n,linklist &L)//建立尾插法
{
    Lnode *p,*r=L;
    for(int i=1;i<=n;i++)
    {
        p=new Lnode;
        p->next=NULL;
        //cin>>p->data;
        r->next=p;
        r=p;
    }
} 
int main()
{
    
}

最后

因为太懒了,就拖了很久,今天开网,终于发布了,麻烦来个三连,谢谢!文章来源地址https://www.toymoban.com/news/detail-418113.html

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

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

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

相关文章

  • 数据结构入门 — 链表详解_双向链表

    数据结构入门 — 双向链表详解 博客主页链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 文章末尾有源码 *****感谢观看,希望对你有所帮助***** 第一篇:数据结构入门 — 链表详解_单链表 第二篇:数据结构入门 — 链表详解_双向链表 第三篇:数据结构入门

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

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

    2024年03月26日
    浏览(64)
  • 数据结构之链表详解

    链表是一种常见的数据结构,它可以用来存储一组数据,并支持快速的插入和删除操作。相比于数组,链表的大小可以动态地增加或减小,因此在某些场景下更加灵活和高效。本文将详细介绍链表的定义、基本操作和应用场景,希望能够帮助读者深入理解链表的原理和实现。

    2024年02月03日
    浏览(47)
  • 【数据结构】双向链表详解

    当我们学习完单链表后,双向链表就简单的多了,双向链表中的头插,尾插,头删,尾删,以及任意位置插,任意位置删除比单链表简单,今天就跟着小张一起学习吧!! 还有双向带头不循环链表,双向不带头循环链表,着重使用双向带头循环链表,带头也就是有哨兵位。

    2024年02月09日
    浏览(49)
  • 【数据结构】动图详解单向链表

    目录 1.什么是链表         1.问题引入         2. 链表的概念及结构         3. 问题解决 2.单向链表接口的实现         1.接口1,2---头插,尾插         2. 接口3,4---头删,尾删         3. 接口5---查找          4. 接口6,7---插入,删除         5. 接口

    2024年01月18日
    浏览(56)
  • [数据结构]链表之单链表(详解)

    在学习 链表 之前,我们已经学习了 顺序表 了 根据 顺序表 的特点,我们可以发现 顺序表 有优点,也有一些缺陷。 所以根据 顺序表 的缺点,链表就横空出世啦~ **概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次

    2023年04月08日
    浏览(53)
  • 【数据结构二】链表和LinkedList详解

    目录 链表和LinkedList  1.链表的实现 2.LinkedList的使用 3.ArrayList和LinkedList的区别 4.链表OJ题训练         当 在 ArrayList 任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后 搬移,时间复杂度为 O(n) ,效率比较低,因此 ArrayList 不适合做任意位置插入和删除比较多

    2024年01月20日
    浏览(45)
  • 数据结构之双向链表详解

    😽博主CSDN主页:小源_😽 🖋️个人专栏:《数据结构》🖋️ 😀努力追逐大佬们的步伐~ 上一篇文章中我们重点讲解了无头单向非循环链表的模拟实现,现在我们来讲解LinkedList(无头双向链表实现 )的模拟实现。 本章重点: 本文着重讲解了LinkedList(无头双向单链表)的实现

    2024年02月04日
    浏览(53)
  • 【数据结构】动图详解双向链表

    目录 1.单向链表的劣势 2.带头双向循环链表         1.逻辑结构        2.结点的代码实现 3.双向链表接口的实现         1.接口1---初始化         2.接口2,3---头插,尾插         3. 接口4,5---头删,尾删         3. 接口6---查找          4. 接口7,8--插入,

    2024年01月23日
    浏览(55)
  • (纯c)数据结构之------>链表(详解)

    目录 一.  链表的定义         1.链表的结构.         2.为啥要存在链表及链表的优势. 二. 无头单向链表的常用接口         1.头插尾插         2.头删尾删         3.销毁链表/ 打印链表         4.在pos位置后插入一个值         5.消除pos位置后的值         6.查找链表

    2024年02月10日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包