C++如何用数组模拟链表

2024-04-02 19:04:59 594人浏览八月长安

摘要

目录前言1.单链表2.双链表总结前言链表是指由一系列储存在非连续储存空间结点组成的储存结构。每个结点由两部分组成：一是储存元素的数据域，一是储存下一个节点地址的指针域。用数组模拟

前言

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

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

1.单链表

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

单链表

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

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.双链表

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

双链表

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

它的实现方法如下：

创建开始和结束结点。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++如何用数组模拟链表的文章就介绍到这了,更多相关C++数组模拟链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C++如何用数组模拟链表

本文链接: https://www.lsjlt.com/news/162320.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

C++如何用数组模拟链表

目录前言1.单链表2.双链表总结前言链表是指由一系列储存在非连续储存空间结点组成的储存结构。每个结点由两部分组成：一是储存元素的数据域，一是储存下一个节点地址的指针域。用数组模拟...

99+

2024-04-02
C++怎么用数组模拟链表

这篇文章的内容主要围绕C++怎么用数组模拟链表进行讲述，文章内容清晰易懂，条理清晰，非常适合新手学习，值得大家去阅读。感兴趣的朋友可以跟随小编一起阅读吧。希望大家通过这篇文章有所收获！前言链表是指由一系列储存在非连续储存空间结点组成的储存...

99+

2023-06-26
C++数组模拟之单链表与双链表和栈和队列的实现过程

目录前引一、数组模拟实现单链表1.1 数组模拟的单链表解析1.2 数组模拟实现单链表例题二、数组模拟实现双链表2.1 数组模拟实现双链表解析2.2 数组模拟实现双链表例题三、数组模拟...

99+

2023-02-13

C++数组模拟单链表 C++数组模拟双链表 C++数组模拟队列
C++中的数组、链表与哈希表

目录数组和链表数组链表什么是链表？链表的操作双向链表（list）list的成员函数哈希表什么是哈希表？哈希碰撞哈希表应用场景构建哈希表哈希表基本使用Leetcode对应题目前缀和差分...

99+

2024-04-02
C++ List链表如何使用

这篇文章主要介绍“C++ List链表如何使用”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“C++ List链表如何使用”文章能帮助大家解决问题。1. list的介绍及使用1.1...

99+

2023-07-05
如何使用Java数组和链表实现栈

小编给大家分享一下如何使用Java数组和链表实现栈，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！一、何为栈？栈（stack）又名堆栈，它是一种运算受限的线性表。限...

99+

2023-06-15
C++如何划分链表

这篇文章主要介绍了C++如何划分链表的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C++如何划分链表文章都会有所收获，下面我们一起来看看吧。划分链表For example,Given 1->4-...

99+

2023-06-19
C++中如何使用链栈模板

本篇文章给大家分享的是有关C++中如何使用链栈模板，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。C++链栈模板声明template <class T&...

99+

2023-06-17
C语言中如何使用链表

这篇文章主要介绍C语言中如何使用链表，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！一、结构体的概念比如说学生的信息，包含了学生名称、学号、性别、年龄等信息，这些参数可能有些是数组型、字符型、整型、甚至是结构体类型的数...

99+

2023-06-29
C#中的数组怎么转化成链表

在C#中，可以使用`LinkedList`类来将数组转换为链表。`LinkedList`类是C#中的一个内置泛型类，用于表示双向链表...

99+

2023-09-09

C#
C++如何实现单链表

小编给大家分享一下C++如何实现单链表，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！单链表的实现(从入门到熟练)概念和结构概念：链表是一种物理存储结构上非连续、非...

99+

2023-06-29
如何使用c++模板自定义数组

这篇文章主要介绍了如何使用c++模板自定义数组，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。前言：制造通用模板，创建自定义的数组，一个数组，里面有这么几个属性，数组容量，数组...

99+

2023-06-29
c语言链表如何实现

这篇“c语言链表如何实现”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“c语言链表如何实现”文章吧。在计算机领域离不开算法和数...

99+

2023-06-19
C++数据结构之单链表如何实现

这篇文章主要介绍了C++数据结构之单链表如何实现的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C++数据结构之单链表如何实现文章都会有所收获，下面我们一起来看看吧。一、单链表的定义线性表的链式存储又称为单链表，...

99+

2023-06-30
Golang如何用表单请求模拟POST

在Golang中，可以使用`net/http`包来模拟POST请求。以下是一个例子：```gopackage mainimport ...

99+

2023-08-19

Golang
C语言数据结构之数组模拟实现顺序表流程详解

目录线性表和顺序表线性表顺序表静态顺序表动态顺序表代码已经放在Gitee上，需要可以小伙伴可以去看看用C语言数组模拟实现顺序表 Gitee 线性表和顺序表线性表线性表（line...

99+

2024-04-02
C++如何实现二叉树链表

目录C++二叉树链表C++二叉树转链表C++二叉树链表 Node.h #ifndef NODE_H #define NODE_H #include <iostream> ...

99+

2024-04-02
C++详解如何实现单链表

目录单链表单链表的基本操作1.初始化2.取值3.查找4.插入5.删除示例代码开发环境运行结果单链表链表内存空间不一定连续，其扩展性较好。多余的不多说了。该文主要记录单链表的实现，该...

99+

2024-04-02
c语言单链表如何创建

创建单链表的基本思路如下：1. 定义一个结构体用来表示链表中的节点，结构体中包含一个数据域用来存储节点的值，还包含一个指针域用来指向...

99+

2023-08-25

c语言
C++和python如何实现单链表

这篇文章给大家分享的是有关C++和python如何实现单链表的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。一、链表的基本概念链表是数据元素的线性集合（Linear Collection），物理存储不连续。那么，这...

99+

2023-06-29