C++ 数组模拟链表例题详解

C++ 数组模拟链表例题详解,第1张

例题: (原题链接:Acwing 826)

实现一个单链表,链表初始为空,支持三种 *** 作:

  1. 向链表头插入一个数;
  2. 删除第 k 个插入的数后面的数;
  3. 在第 k 个插入的数后插入一个数。


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


注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。


例如 *** 作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。


输入格式

第一行包含整数 MM,表示 *** 作次数。


接下来 MM 行,每行包含一个 *** 作命令, *** 作命令可能为以下几种:

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


  2. D k,表示删除第 k 个插入的数后面的数(当 k 为 0 时,表示删除头结点)。


  3. I k x,表示在第 k 个插入的数后面插入一个数 x(此 *** 作中 k 均大于 0)。


输出格式

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


数据范围

1≤M≤100000
所有 *** 作保证合法。


输入样例:

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

输出样例:

6 4 6 5
代码如下:
#include
using namespace std;
#define int long long
const int N = 111111;

//head表示头结点的下标 
//e[i]表示结点i的值
//ne[i]表示结点i的next指针值是多少
//idx表示当前已经用到了哪个点 
int head, e[N], ne[N], idx = 0;

//初始化链表 
void init(){
	head = -1; //此时链表为空,head指向-1 
	idx = 0; //表示起点从0号点开始
} 

//把一个x结点插入到头结点的后面 
void add_to_head(int x){
	e[idx] = x;
	ne[idx] = head; //待插入的结点的next指针指向head指向的结点
/*补充说明: 
head的作用一:链表初始化的时候等于-1,表示链表为空
二:指向下一个结点,即 head = 下标, "下标"指的是下一个结点的下标 
next的作用:指向下一个结点的下标,也就是idx值(head第二作用相当于next) 
*/
	head = idx;  //head指向插入的这个点的下标,也就是指向idx 
	idx++; //当前下标为idx的结点被占用,idx++ 
}

//在两个点之间插入新的结点(将x插入到下标是k个结点的后面) 
void add(int k, int x){
	e[idx] = x; //idx指的是新的结点占用的下标是idx 
	ne[idx] = ne[k]; //新结点的next指针,指向下标k结点的next指针所指向的结点 
	ne[k] = idx;  //下标k结点的next指针指向新插入的结点 
	idx++;   //新插入的结点占用了原来的idx,idx++ 
}

//将第k个点后面的一个结点删掉 
void remove(int k){
	ne[k] = ne[ne[k]]; //原来k结点next指针指向下一个结点,现在想把下一个结点删掉
	//那么直接让k结点next指针指向下一个结点的下一个结点
	//即直接将k结点的next指针指向下一个结点next指针指向的结点 
}	//这样就完成了删除 *** 作 

signed main(){
	int M;
	char ch;
	cin >> M;
	init();
	while(M--){
		cin >> ch;
		switch(ch)
		{
			case 'H':
				int x;
				cin >> x;
				add_to_head(x);
				break; 
			case 'D':
				int k;
				cin >> k;
				if (!k) head = ne[head]; //删除头结点 
				else remove(k - 1);
				break; 
			case 'I':
				cin >> k >> x;
				add(k - 1, x);
				break; 
		}
	}
	for(int i = head; i != -1; i = ne[i])
		cout << e[i] << " "; 
	
	return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/584754.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-12
下一篇 2022-04-12

发表评论

登录后才能评论

评论列表(0条)

保存