单链表模拟（也是邻接表的前置）
创始人
2024-06-02 14:53:25
0次

实现一个单链表，链表初始为空，支持三种操作：

  1. 向链表头插入一个数；

  1. 删除第 k� 个插入的数后面的数；

  1. 在第 k� 个插入的数后插入一个数。

现在要对该链表进行 M� 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k� 个插入的数并不是指当前链表的第 k� 个数。例如操作过程中一共插入了 n� 个数，则按照插入的时间顺序，这 n� 个数依次为：第 11 个插入的数，第 22 个插入的数，…第 n� 个插入的数。

输入格式

第一行包含整数 M�，表示操作次数。

接下来 M� 行，每行包含一个操作命令，操作命令可能为以下几种：

  1. H x，表示向链表头插入一个数 x�。

  1. D k，表示删除第 k� 个插入的数后面的数（当 k� 为 00 时，表示删除头结点）。

  1. I k x，表示在第 k� 个插入的数后面插入一个数 x�（此操作中 k� 均大于 00）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

1≤M≤1000001≤�≤100000

所有操作保证合法。

#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair PII;
const ll maxx = 1e9;
int n, m, T;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
int dx[4] = { 0 , 1 , -1 , 0 }, dy[4] = { 1 , 0 , 0 , -1 };
int h[N], e[N], ne[N], head, idx;
void in()
{head = -1;//在没有元素的时候指向-1，在有元素的情况下指向第一个元素的指针idx = 0;//在一开始作为链表的下标，在链表的各种插入 ， 删除的时候作为辅助工作,并且是}
void into(int x)//插入
{e[idx] = x;//将值放入ne[idx] = head;head现在作为指针指向空节点 ， 现在ne[idx] = headhead = idx;idx++;//所有的操作进行后idx都得++，idx指向的是当前地址//所有的访问是靠ne[]来访问的，包括遍历链表也是靠ne[]，这样不管下标如何混乱都可以继续操作
}
void add(int k, int x)//将x插入到k点之后
{e[idx] = x;//先将元素插入ne[idx] = ne[k];//让元素x配套指针，指向它要站位的元素下一位ne[k] = idx;//让原来的指针指向自己idx++;//将idx向后挪
}
void remove(int k)
{ne[k] = ne[ne[k]];//让k的指针指向下一个，k下一个的下一人，那中间那位就被挤掉了//这里idx
}
void solve()
{cin >> n;in();//初始化for (int i = 0; i < n; i++){char s;cin >> s;if (s == 'H'){int x;cin >> x;into(x);//进行插入}if (s == 'D'){int k;cin >> k;if (k == 0){head = ne[head];//删除头结点}else{remove(k - 1);}}if (s == 'I'){int k, x;cin >> k >> x;add(k - 1, x);}}for (int i = head; i != -1; i = ne[i]){cout << e[i] << " ";}cout << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//cin >> T;//while (T--)//{solve();//}return 0;
}
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Flink学习笔记（二）Flink常用API详解

下一篇：手机解锁方法：8个顶级的 Android 手机解锁软件

相关内容

热门资讯

bbugreport.exe：... 哎呀，说到这个bbugreport.exe，我的心情真是五味杂陈啊！你懂的，就是那个时不时蹦出来，让...
双网叠加路由器：让网络速度如火... 哎呀，说到这个双网叠加路由器，我简直要跳起来了！你知道吗，自从我换了这款路由器，家里的网络速度简直像...
枭雄怎么重新开始-从失败到新生... 在江湖的沧桑岁月中，每一个枭雄都有过辉煌的巅峰，也有过跌入谷底的苦涩。曾经的我，手握重兵，叱咤风云，...
邮件炸弹攻击主要是什么-警惕！... 邮件炸弹攻击，听起来就像是从科幻电影里跳出来的东西，对吧？但它可是真实存在的，而且就在我们的电子邮箱...
ubuntu 1404关闭3d... 哎呀，说到这个Ubuntu14.04啊，我真的是有点头疼。尤其是那个3D效果，简直是让我眼花缭乱，头...
android操作系统耗电-安... 哎呀，说到安卓手机，我这心里就一肚子火！每次出门前，手机电量还满格，结果没一会儿，就剩下个位数了。这...
雨田蜂蜜：承载童年记忆的甜蜜滋... 在那些细雨蒙蒙的日子里，我总是不由自主地想起家乡的那片雨田，以及那从田间飘来的蜂蜜香。那是一种无法用...
身份证号码查姓名地址，背后隐藏... 嘿，小伙伴们，今天咱们来聊聊一个有点儿神秘的话题——身份证号码查姓名地址。你有没有想过，那些冷冰冰的...
巫师3 dsound.dll在... 哎呀，朋友们，今天咱们来聊聊那个让人抓狂的dsound.dll问题。你知道的，就是那个在《巫师3》里...
android+验证身份证号码... 哎呀，今天咱们来聊聊这个有点严肃但又挺重要的话题——Android手机上怎么验证身份证号码。我知道，...
360数据恢复免费吗-360 ... 大家好，我是一个对电脑一窍不通的小白。前段时间，我不小心删了电脑里的一些重要文件，心里那个急啊，就像...
苹果7使用说明书图解-探索苹果... 大家好呀！今天我要带你们一起探索苹果7的奇妙世界，用最酷炫的方式解锁它的所有秘密！别担心，我们不需要...
win10开机启动项 命令-W... 哎呀，说到Win10开机启动项，我就一肚子火！每次开机，那屏幕就像在跟我玩捉迷藏，转啊转的，半天不见...
相机内存卡文件为空-珍贵照片离... 哎呀，真是气死我了！今天兴冲冲地打开相机，准备回味一下上个周末的欢乐时光，结果一看，我的天，那些珍贵...
苹果手机怎么快速省电-掌握这些... 哎呀呀，说到苹果手机省电，我可是有一肚子的话要说！你知道吗，每次看到手机电量从满格到红线，我的心就像...
北京朝阳医院儿科电话：希望的传... 在北京这座快节奏的都市里，每一个角落都充满了匆忙与喧嚣。但如果你细心倾听，会发现有一个声音始终温暖而...
易购分销平台：海量商品、超实惠... 大家好，我是小张，一个在街角开小店的老板。今天我要给大家聊聊我最近发现的一个超级棒的地方——易购分销...
opensuse 42.2壁纸... 嘿，亲爱的OpenSUSE爱好者们，今天咱们聊聊那些让人眼前一亮的OpenSUSE42.2壁纸！这些...
帝国 政府 模板-在宏伟帝国里... 在这个宏伟的帝国里，每一天都像是政府精心布置的一盘棋。我，一个深陷其中的小卒，感受着这场游戏的起伏与...
苹果恢复大师收费标准揭秘：基本... 大家好，今天咱们来聊聊这个让人又爱又恨的“苹果恢复大师”！你知道吗？这玩意儿简直就是苹果界的救星，但...