数组模拟几种基本的数据结构

news/2024/11/15 0:04:28/

文章目录

  • 数组模拟单链表
  • 数组模拟双链表
  • 数组实现栈
  • 数组模拟队列
  • 总结

在这里插入图片描述

数组模拟单链表

首先类比结构体存储单链表,我们需要一个存放下一个节点下标的数组,还需要一个存储当前节点的值的数组,其次就是一个int类型的索引,这个索引指向的是下一个我们准备用的空间,还需要一个head,head存放的是头结点的下标

我们用下面一道题来更深刻的理解*

在这里插入图片描述

代码展示:

#include<iostream>
using namespace std;
//确定数组的大小
const int N = 100000;
//一个存放值,一个存放下一个节点的下标
int e[N],ne[N];
//一个是下一个节点的索引,一个变量存储头节点
int idx,head;
//操作次数
int M;void  Init()
{//零个节点的情况下我们的head等于-1,表示还没有任何节点head=-1;//idx定义为0,表示下一个节点的下标是0idx=0;
}
//在头部插插入节点
void PushFront(int x)
{//更新新节点存储的值e[idx]=x;//新节点的下一个节点是原来的头结点ne[idx]=head;//更新头结点,为idxhead=idx;//更新idxidx++;
}
//在第k个节点的后面插入一个数据
void Insert(int k,int x)
{//更新存储节点值的数组e[idx]=x;//准备插入的节点的下一个节点是k节点指向的下一个节点ne[idx]=ne[k];//k节点指向的下一个节点是idxne[k]=idx;//更新idxidx++;
}
//删除第k个节点的后一个节点
void Earase(int k)
{//第k个节点的下一个节点是第k个节点的下下个节点ne[k]=ne[ne[k]];
}int main()
{//初始化Init();//输入操作数cin>>M;while(M--){int x,k;char op;//根据样例写一个ifelsecin>>op;if(op=='H'){cin>>x;PushFront(x);}else if(op=='D'){cin>>k;if(!k) head=ne[head];Earase(k-1);}else{cin>>k>>x;Insert(k-1,x);}}//输出数据for(int i=head;i!=-1;i=ne[i])cout<<e[i]<<' ';return 0;
}

数组模拟双链表

双链表的实现和单链表类似,只不过我们需要三个数组,一个数组存储指向左边的的上一个节点的下标,一个数组存储下一个节点的下标,还有一个数组存储当前节点的值,还需要一个idx索引下一个元素。

看题!

题目在这里插入图片描述
样例
在这里插入图片描述

代码展示:

#include<iostream>
using namespace std;
const int N=100000;
int l[N],r[N],idx;
int e[N];int m;void Init()
{r[0]=1;l[1]=0;idx=2;
}
void Push_Right(int k,int x)
{//赋值e[idx]=x;//idx的右边是k节点的右边的节点r[idx]=r[k];//idx的左边是kl[idx]=k;//k的右边的指向的左边是idxl[r[k]]=idx;//k指向的右边是idxr[k]=idx;//idx++;idx++;
}void Earase(int k)
{l[r[k]]=l[k];r[l[k]]=r[k];
}int main()
{cin>>m;Init();while(m--){int k=0,x=0;string op;cin>>op;//在零的右边插入if(op == "L"){cin>>x;Push_Right(0,x);}//在1的左边插入,1代表最后一个节点,所以只需要在最后一个节点的左边插入else if(op == "R"){cin>>x;Push_Right(l[1],x);}//删除,因为idx是从2开始的,他是删除第k个节点,存值的节点是从2开始,所以删除第k个//实际是删除第k+1个else if(op == "D"){cin>>k;Earase(k+1);}//在第看个节点的左边插入,相当于在第k+1个节点的左边节点的右边插入一个值else if(op=="IL"){cin>>k>>x;Push_Right(l[k+1],x);}//在右边插入,相当于就是在第k+1哥节点的右边插入一个数else if(op=="IR"){cin>>k>>x;Push_Right(k+1,x);}}//打印,第一个节点是在0节点的右边开始,然后到1结束for(int i=r[0];i!=1;i=r[i])cout<<e[i]<<' ';cout<<endl;return 0;
}

数组实现栈

数组实现栈和数组实现单链表类似,甚至比单链表更简单,由于栈先进后出的性质,所以我们根本、不需要用到什么head

看题!

题目
在这里插入图片描述
样例
在这里插入图片描述

代码展示:

#include<iostream>
using namespace std;
const int N=100000;
//存储值的数组和存储下一个节点下标的数组
int e[N],ne[N];
//索引
int idx;
//操作数
int m;
void Init()
{//这里我们直接将idx置零idx=0;
}
void Push(int x)
{e[idx]=x;idx++;
}
void Pop()
{idx--;
}bool Empty()
{return idx==0;
}
int Query()
{return e[idx-1];
}
int main()
{cin>>m;Init();while(m--){string op;cin>>op;int x;if(op=="push"){cin>>x;Push(x);}else if(op=="pop"){Pop();}else if(op=="empty"){if(Empty()){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}else if(op=="query"){cout<<Query()<<endl;}}return 0;
} 

数组模拟队列

数组模拟队列类似于数组模拟单链表,但是由于队列的特殊性质,先进先出,所以我们需要一个指向头的索引,当我们需要出队列的时候,时间复杂度可以达到O(1),也需要一个存储值的数组,和存储下一个节点下标的数组

看题!

**题目在这里插入图片描述
样例
在这里插入图片描述

代码展示:

#include<iostream>
using namespace std;
const int N=100000;
int head,idx,e[N],ne[N];
int tail;
int m;
void Init()
{head=-1;idx=0;tail=-1;m=0;
}void Push(int x) {e[idx] = x;ne[idx] = -1; // 将新元素的下一个位置设置为 -1,表示末尾if (head == -1) { // 如果队列为空,将 head 和 tail 都设置为当前的 idxhead = idx;tail = idx;} else {ne[tail] = idx; // 将当前的 tail 指向新元素的位置tail = idx; // 更新 tail}idx++;
}void Pop()
{head=ne[head];if(head==-1){tail=-1;}
}
bool Empty()
{return head==-1;
}
int Query()
{return e[head];
}
int main()
{Init();cin>>m;while(m--){string op;cin>>op;int x;if(op=="push"){cin>>x;Push(x);}else if(op=="pop"){Pop();}else if(op=="empty"){if(Empty()){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}else if(op=="query"){cout<<Query()<<endl;}}return 0;
}

总结

在本文中,我们深入探讨了如何使用数组来模拟基本的数据结构,包括栈、队列和链表。通过这些模拟,我们不仅加深了对这些数据结构的理解,还学会了如何利用数组的特性来实现它们。通过使用数组,我们可以更好地理解数据结构的底层原理,并且在实际编程中更灵活地应用这些概念。无论是在算法竞赛中还是在实际项目中,对数组模拟数据结构的掌握都将为我们带来更多的解决方案和优化思路。希望本文能够帮助你更深入地理解数组和数据结构,并在你的编程旅程中有所启发!


http://www.ppmy.cn/news/1442373.html

相关文章

Codeforces Round 941 (Div. 2) ABC

Dashboard - Codeforces Round 941 (Div. 2) - Codeforces A. Card Exchange 既然只看数量&#xff0c;咱也别统计是谁了&#xff0c;就看能不能变了。 首先先明确&#xff0c;如果现在都一样比如n个&#xff0c;可以一直操作直到 k-1。 我们可以先根据数量用map统计&#x…

基础算法前缀和与差分

前言 本次博客会介绍一维和二维的前缀和&#xff0c;以及一维二维差分的基本使用&#xff0c;尽量画图&#xff0c;多使用配合文字 使大家理解&#xff0c;希望有所帮助吧 一维前缀和 问题描述 这里有一个长度为n的数组&#xff0c;我们要算出【2,5】区间的元素和 暴力思…

详解JVM类加载

从类被加载到虚拟机内存中开始&#xff0c;到释放内存总共有7个步骤&#xff1a;加载&#xff08;Loading&#xff09;、验证&#xff08;Verification&#xff09;、准备&#xff08;Preparation&#xff09;、解析&#xff08;Resolution&#xff09;、初始化&#xff08;Ini…

负二 进制

负二进制转换 题目&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 位于力扣的题解&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 目录 一、进制转换法&#xff1a; 二、拆分法&#xff0c;拆分正负位为a,b两个数&#xff0c;去构造这两个数 这里的bitset…

为什么二维数组初始化第一维数组长度可以为空,第二维不可以为空呢?

注意&#xff0c;数组第二维的长度声明永远不能省略。这是因为C语言中的二维数组元素在c编译程序为其分配的连续存储空间中是按行存放的&#xff0c;即存在完整第一行后存第二行&#xff0c;然后再第三行&#xff0c;以此类推。存放时系统必须知道每一行有多少个元素才能正确计…

Docker 备忘清单(一)

随着年龄的增长&#xff0c;记性开始退步&#xff0c;所以接下来打算把常用的一些语言命令&#xff0c;收集整理&#xff0c;以作备忘或查找使用。希望对自己或他人有所用途。 入门 1、入门 1.1、安装 curl -sSL https://get.docker.com/ | sh sudo chmod 777 /var/run/doc…

webpack配置文件

配置文件 webpack提供的cli支持很多的参数&#xff0c;例如--mode&#xff0c;但更多的时候&#xff0c;我们会使用更加灵活的配置文件来控制webpack的行为 默认情况下&#xff0c;webpack会读取webpack.config.js文件作为配置文件&#xff0c;但也可以通过CLI参数--config来…

K8S 部署和访问 Kubernetes 仪表板(Dashboard)

文章目录 部署 Dashboard UI浏览器访问登陆系统 Dashboard 是基于网页的 Kubernetes 用户界面。 你可以使用 Dashboard 将容器应用部署到 Kubernetes 集群中&#xff0c;也可以对容器应用排错&#xff0c;还能管理集群资源。 你可以使用 Dashboard 获取运行在集群中的应用的概览…