其实拿数组来模拟链表还是很不错的

蒙自市蒙自一中马晨烨  •  1年前


代码如下:

include <bits/stdc++.h>

using namespace std; const int Maxn = 1e6 + 10; int hand1, idx1, hand2, idx2, x, k, sum1 = 0, sum2 = 0, a, b;//a,b为准备插入链表的值 int e1[Maxn], e2[Maxn], ne1[Maxn], ne2[Maxn];

void init() {

hand1 = -1, idx1 = 0, hand2 = -1, idx2 = 0;

}//初始化操作

void add_to_hand2(int x) {

e2[idx2] = x, ne2[idx2] = hand2, hand2 = idx2++;

}//对我的第二条链做头后插入

void add_to_hand1(int x) {

e1[idx1] = x, ne1[idx1] = hand1, hand1 = idx1++;

}//对第一条链做头后插入

void add1(int k, int x) {

e1[idx1] = x, ne1[idx1] = ne1[k], ne1[k] = idx1++;

}//对第一条链子k后面插入x

void add2(int k, int x) {

e2[idx2] = x, ne2[idx2] = ne2[k], ne2[k] = idx2++;

}//对第二条链子k后面插入x

void running() {

cin >> a >> b;
add_to_hand1(a);
add_to_hand2(b);
for (int i = 1; i <= 9; i++) {
	cin >> a >> b;
	//cout << "1";
	add1(i - 1, a);
	add2(i - 1, b);
}
for (int i = hand1; i != -1; i = ne1[i])//遍历第一条链
	sum1 += e1[i] ;
//cout << endl;
for (int i = hand2; i != -1; i = ne2[i])//遍历第二条链
	sum2 += e2[i] ;

}

int main() {

std::ios::sync_with_stdio(false);
std::cin.tie(0);//偶然在luogu考试时看到的加快cin/cout的方法
init();
running();
cout << sum1 << "+" << sum2 << 'i';
return 0;

}

其实我们还是可以看到用数组模拟链表的优点的 首先就是很快 其次思想也是很重要的

**void add_to_hand(int x){

e[idx] = x, ne[idx] = hand, hand = idx++;

}** 这一个部分主要就是跟换hand指向的位置 让hand指向我们原来准备插入的值的位置 然后再让插入的值指向原本hand后面指向的数

**void add_to_back(int k,int x){

e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;

}** 原理一样就不多赘述了(其实就是懒)

void delete_it(int k){

ne[k] = ne[ne[k]];

} 聪明的人已经发现了 其实并没有直接把这个节点删掉 反正这种操作是没有问题的,可以等后来新节点加入使之被覆盖掉


评论:

666


蒙自市蒙自一中马晨烨  •  1年前

请先登录,才能进行评论