文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C++怎么用数组模拟链表

2023-06-26 05:26

关注

这篇文章的内容主要围绕C++怎么用数组模拟链表进行讲述,文章内容清晰易懂,条理清晰,非常适合新手学习,值得大家去阅读。感兴趣的朋友可以跟随小编一起阅读吧。希望大家通过这篇文章有所收获!

前言

链表是指由一系列储存在非连续储存空间 结点组成的储存结构。每个结点由两部分组成:一是储存元素的数据域,一是储存下一个节点地址的指针域。用数组模拟链表可以十分清晰明了地理解这一定义。

在这里,我们简单地介绍一下单链表和双链表两种链表以及用数组模拟实现它们的方式。

1.单链表

单链表是指针方向单向的链表,即a结点的指针域储存着b结点的地址,而b结点的指针域内没有储存a结点的地址。在访问时,可以由a到b访问,而不能由b到a访问。

C++怎么用数组模拟链表

如图可以清晰地看到,各个结点的指向都是单向的。

Q: 那么,如何用数组来实现它呢?

A: 方法如下

在k结点右侧插入元素x。先将x赋值给该节点的数据域(e[idx]),然后将k结点的指针域赋值给该结点的指针域,最后将k结点的指针域储存的地址改为该节点的地址。

void add(int k, int x){    e[idx] = x;    ne[idx] = ne[k];    ne[k] = idx++;}
删除k结点指向的结点。这里所指的删除,是将k的指向改为该结点的指向。原本为a -> b -> c,改为a -> c,b结点依然存在,只是没有其他结点指向它,也就无法通过链表访问它,我们认为它就再链表上被删除了。
void remove(int k){    ne[k] = ne[ne[k]];}

读取链表。读取链表只用注意一点,在用单指针扫描时不是将指针位置右移,而是将指针移动到该结点指向的位置。

for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';cout << endl;

主要的操作就是如此,下边看看完整代码:

这是较为经典的写法,我个人认为有些麻烦,head不必单独拿出来写一个函数。但是有助于理解。

#include<iostream>using namespace std;const int M = 1e5 + 10;int m, k, x, idx, head;int e[M], ne[M];void init(){    head = -1, idx = 0;}void add_head(int x){    e[idx] = x;    ne[idx] = head;    head = idx++;}void remove(int k){    ne[k] = ne[ne[k]];}void add(int k, int x){    e[idx] = x;    ne[idx] = ne[k];    ne[k] = idx++;}int main(){    init();    cin >> m;    while (m--)    {        char op;        cin >> op;        if (op == 'H')        {            cin >> x;            add_head(x);        }        else if (op == 'D')        {            cin >> k;            if (!k) head = ne[head];            remove(k - 1);        }        else        {            cin >> k >> x;            add(k - 1, x);        }    }    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';    cout << endl;    return 0;}

这种写法稍微简便一些,用a[0]替代head。

#include<iostream>using namespace std;const int M = 1e5 + 10;int m, k, x, idx, head;int e[M], ne[M];void init(){    ne[0] = -1, idx = 1;}void remove(int k){    ne[k] = ne[ne[k]];}void add(int k, int x){    e[idx] = x;    ne[idx] = ne[k];    ne[k] = idx++;}int main(){    init();    cin >> m;    while (m--)    {        char op;        cin >> op;        if (op == 'H')        {            cin >> x;            add(0, x);        }        else if (op == 'D')        {            cin >> k;            if (!k) head = ne[head];            remove(k);        }        else        {            cin >> k >> x;            add(k, x);        }    }    for (int i = ne[0]; i != -1; i = ne[i]) cout << e[i] << ' ';    cout << endl;    return 0;}

2.双链表

双链表顾名思义就是指针方向双向的链表。

C++怎么用数组模拟链表

可以看到除了头尾他们的指针都是双向的。

它的实现方法如下:

创建开始和结束结点。0表示开始,1表示结束,互相指向,在插入时直接往中间插入即可。

void init(){r[0] = 1, l[1] = 0;idx = 2;}

插入结点。双链表插入结点的方法与单链表相同,但是操作要稍微复杂一些,这是在k结点右边插入一结点的代码。它要顾及结点左右的结点指向,对于两边都要操作。面临在k结点左边插入一结点时,不必单独在写一个函数,而改成在l[k]结点的右边插入一个结点。

void add(int k, int x){a[idx] = x;r[idx] = r[k], l[idx] = l[r[k]];l[r[k]] = idx, r[k] = idx;idx++;}

删除节点。删除结点与插入结点同理,我就不多赘述了。

void remove(int k){r[l[k]] = r[k];l[r[k]] = l[k];}

输出链表。可以选择输出方向,这里是从左往右输出。

for (int i = r[0]; i != 1; i = r[i])cout << a[i] << ' ';cout << endl;

以下是完整代码:

#include<iostream>using namespace std;const int N = 1e5 + 10;int a[N], l[N], r[N];int idx;int m;void init(){r[0] = 1, l[1] = 0;idx = 2;}void add(int k, int x){a[idx] = x;r[idx] = r[k], l[idx] = l[r[k]];l[r[k]] = idx, r[k] = idx;idx++;}void remove(int k){r[l[k]] = r[k];l[r[k]] = l[k];}int main(){init();cin >> m;while (m--){int k, x;string op;cin >> op;if (op == "L"){cin >> x;add(0, x);}else if (op == "R"){cin >> x;add(l[1], x);}else if (op == "D"){cin >> k;remove(k + 1);}else if (op == "IL"){cin >> k >> x;add(l[k + 1], x);}else if (op == "IR"){cin >> k >> x;add(k + 1, x);}}for (int i = r[0]; i != 1; i = r[i])cout << a[i] << ' ';cout << endl;return 0;}

感谢你的阅读,相信你对“C++怎么用数组模拟链表”这一问题有一定的了解,快去动手实践吧,如果想了解更多相关知识点,可以关注编程网网站!小编会继续为大家带来更好的文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯