数据结构-单链表的读取,插入与删除

链表定义:

struct ListNode
{
  int value;
  ListNode *next;
};

单链表读取

在顺序存储结构中,比如数组中,想要获取某一个位置的数据是非常容易的一件事,但是在链表中却要麻烦一些,因为链表的存储单元并不是连续的,而且我们只知道链表的头结点,也就是想知道第i个位置的数据,只能从头找下去,并没有什么其他的好方法。 需要注意的是,如果i大于链表的长度的话程序会异常,所以需要加上判断。

#include<iostream>
using namespace std;

struct ListNode
{
int value;
ListNode *next;
};

ListNode* GetElem(ListNode * L,int i);
void CreateList(ListNode * L,int n);
int main()
{
    ListNode * L = new ListNode;
    L->next = nullptr;
    CreateList(L,5);
    ListNode* elem = GetElem(L,3);
    if (elem==nullptr)
    {
     cout<<"error"<<endl;
    } 
    else
    {
     cout<<elem->value<<endl;
    }
    getchar();
    getchar();
    return 0;
}
void CreateList(ListNode * L,int n)
{
    cin>>L->value;//输入第一个结点的数据值
    n--;
    for (int i = 0; i < n; i++)
    {
        ListNode * p = new ListNode;
        cin>>p->value;
        p->next = nullptr;
        L->next = p;
        L = p;
    }
}
ListNode* GetElem(ListNode * L,int i)
{
    int j;
    ListNode *p=L;
    j =1;
    while (p && j<i)
    {
        p = p->next;
        j++;
    }
    if (!p || j>i)
    {
        return nullptr;
    }
    return p;
}

在上面的代码中,传入GetElem函数的是链表的头结点,这个代码和《大话数据结构》这本书里面的例程有些不同,如果有人也碰巧看那本书的话,可以留意一下。

单链表插入

相比于顺序存储结构,链表的读取确实麻烦了些,但是好在插入和删除方便。比如要在链表的第三个结点之后插入一个结点。

这里的1-6只是结点里面存的数据,不决定结点的顺序。 (1)找到链表中第三个结点p (2)创建一个新的结点q ListNode *q=(ListNode*)malloc(sizeof(ListNode));q->value=4; (3)q先与原链表第四个结点链接q->next = p->next; (4)原链表第三个结点与q链接p->next = q; (3和4的顺序不能对调,所以图示就是这样)

我们假设一下,如果3,4对调了,也就是说先让第三个结点指向q,因为我们是可以在原链表上找到第三个结点的,但是一旦指向发生了变化,原链表断了,原链表的第四个结点就已经找不到了。但是不对调的话,在原链表没有断开之前就把q与第四个结点连起来了,又由于本来我们就找到了原链表的第三个结点,所以即便断开了,那又能怎么样呢??

#include<iostream>
using namespace std;

struct ListNode
{
int value;
ListNode *next;
};
void showList(ListNode * L);
ListNode* ListInsert(ListNode * L,int i);
void CreateList(ListNode * L,int n);
int main()
{
    ListNode * L = new ListNode;
    L->next = nullptr;
    CreateList(L,5);
    ListNode* Head = ListInsert(L,3);
    showList(Head);
    getchar();
    getchar();
    return 0;
}
void CreateList(ListNode * L,int n)
{
    cin>>L->value;//输入第一个结点的数据值
    n--;
    for (int i = 0; i < n; i++)
    {
        ListNode * p = new ListNode;
        cin>>p->value;
        p->next = nullptr;
        L->next = p;
        L = p;
    }
}
ListNode* ListInsert(ListNode * L,int i)
{
    int j;

    ListNode *p=L;
    j =1;
    while (p && j<i)
    {
        p = p->next;
        j++;
    }
    if (!p || j>i)
    {
        return nullptr;
    }

    ListNode *q=(ListNode*)malloc(sizeof(ListNode));

    q->value=4;
    //3
    q->next = p->next;
    //4
    p->next = q; 

    return L;
}
void showList(ListNode * L)
{
    ListNode * p = L;
    while (p)
    {
        cout<<p->value<<' ';
        p = p->next;
    }
    cout<<endl;
}

单链表删除

要删除一个链表中第三个结点后面的结点,逻辑与插入操作很类似,同样要考虑原链表断开后的情况:

步骤是这样: (1)找到第三个结点p (2)找到p后面的结点q(在图中是第四个)q= p->next; (3)将p指向q后面的结点(在图中是第五个)p->next = q->next; (4)释放qfree(q);

#include<iostream>
using namespace std;

struct ListNode
{
int value;
ListNode *next;
};
void showList(ListNode * L);
ListNode* ListDelete(ListNode * L,int i);
void CreateList(ListNode * L,int n);
int main()
{
    ListNode * L = new ListNode;
    L->next = nullptr;
    CreateList(L,5);
    ListNode* Head = ListDelete(L,3);
    showList(Head);
    getchar();
    getchar();
    return 0;
}
void CreateList(ListNode * L,int n)
{
    cin>>L->value;//输入第一个结点的数据值
    n--;
    for (int i = 0; i < n; i++)
    {
        ListNode * p = new ListNode;
        cin>>p->value;
        p->next = nullptr;
        L->next = p;
        L = p;
    }
}
ListNode* ListDelete(ListNode * L,int i)
{
    int j;
    ListNode *q;
    ListNode *p=L;
    j =1;
    while (p && j<i)
    {
        p = p->next;
        j++;
    }
    if (!p || j>i)
    {
        return nullptr;
    }

    //3
    q= p->next;
    //4
    p->next = q->next; 
    free(q);
    return L;
}
void showList(ListNode * L)
{
    ListNode * p = L;
    while (p)
    {
        cout<<p->value<<' ';
        p = p->next;
    }
    cout<<endl;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏钱塘大数据

【干货】十大必须掌握的基础实用算法及其讲解

作者:CSDN大数据 算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下...

2726
来自专栏CSDN技术头条

程序员必须知道的十大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较...

1785
来自专栏华章科技

程序员必须知道的十大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见。...

702
来自专栏我是攻城师

十大算法,让你轻松进阶高手

3457
来自专栏老九学堂

程序员必须知道的十大基础实用算法及讲解!

最近社群很多的小伙伴们对算法进行了激烈的讨论与学习,今天老九君就给大家介绍一些编程语言里的基础算法,提高小伙伴们的算法知识及编程里对算法的运用。 我们一起来看看...

3245
来自专栏随笔小哥哥

程序员必须知道的10大基础实用算法及其讲解:排序、查找、搜索和分类等

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

200
来自专栏CDA数据分析师

数据分析师不可不知的10大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

1978
来自专栏Spark学习技巧

最大子序列和问题之算法优化

833
来自专栏程序员互动联盟

程序员必须要掌握的十大经典算法

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

35413
来自专栏算法channel

图算法|Dijkstra最短路径算法

01 — 单源最短路径 首先解释什么是单源最短路径,所谓单源最短路径就是指定一个出发顶点,计算从该源点出发到其他所有顶点的最短路径。如下图所示,如果源点设为A,...

2955

扫码关注云+社区