如何用数组来控制指针实现链表

Posted on
Words count in article: 3.3k | Reading time ≈ 15

如何用数组来控制指针实现链表.md

  • 我们一般看到的链表定义都是这样的
1
2
3
4
5
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

但是，我们可以用一个下标数组，来实现 *next的操作 我们可以用数组实现next指针的功能，并实现排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//比如这样，我们建立两个数组，第一个数组存储具体数字，第二个数组存储下标
//一般，我们要对头节点进行操作的话，需要设立dummyNode,这里A[0]就是个哑节点
//那么，我们要实现一个排序操作，我们就要对他的next数组进行操作。
//首先我们吧next数组初始化为-1
	A[7]= {0,2 1 4 5 8 6}
//排序完成后，A的下标数组如下
 	Next[7]={2，3，1，4，6，-1，5}
//我们可见，操作完成后，0节点指向2，2节点指向1，1结点指向3，3节点指向4.4节点指向6
//6节点指向5，5节点指向-1。然后映射到A[7]上，就完成了排列,
//打印顺序
A[0]（不打印）->A[2]->A[1]->A[3]->A[4]->A[6]->A[5]
//  所以，用数组来存储指针，并不改变A数组中元素的顺序，只改变A数组的打印顺序
    
//那么，每次新输入一个数，如何来实现A数组的排序呢
/*
	1.首先，把next数组初始化为 -1
	2.需要两个类似于迭代器的东西，然后，每次，都让迭代器从0开始遍历，一直到新插入的数所在的位置后
	也就是 A[p]<A[q]<A[nxt[p]]的时候。我们更新next[p]和next[q]的位置
	3.这时候next[q] = next[p] 
	       next[p] = q
 	4.事实上，这就实现了插入操作
*/
//核心的部分讲完了，我们现在要进行一些函数的封装
    1.如果我们要实现自定义的数据类型的有序列表操作，我们还需要建立一个Record类，在其中重写运算符
    2.建立链表类，里面含有next数组和A数组，以及初始化函数
    3.派生出一个新的有序链表类，让他继承链表类
    4.在有序链表类中完成上述操作，再设定一个打印操作
   
#include <bits/stdc++.h>
using namespace std;

/* 操作一：建立一个Record 类*/
template<class typeName>
class Record{
    tp v;
    bool operator < (const Record &t)const{
        return v<t.v;
    }
    bool operator >(const Record &t)const{
        return v>t.v;
    }
    bool operator ==(const Record &t)const{
        return v ==t.v;	
	}
};
const  int Maxn = 40;
/*操作2：建立链表类，里面含有next数组和A数组，以及初始化函数*/
class LinkList{
  public
    Record<int>A[Maxn];
    int next[Maxn],tot;
    LinkList(){
        memset(next,-1,sizeof(next));
        tot = 0;
	}
    int addElem (int x){
        A[++tot].v = x;
        return tot;
    } 	
};

class OrderedList:public LinkList{
    void insert(int x)
    {
        int p = 0;//从0开始遍历
        int q = addElem(x);//获取到x再A数组中的位置
        while(next[p]!=-1&&A[next[p]]<A[q])
        {
            p = next[p];
        }
        //现在 A[p]<A[q]<A[nxt[p]]
        //开始更新
        next[q] = next[p];
        next[p] = q;
    }
    void print()
    {
        int cur = 0;
        while(next[cur]!=-1)
        {
            p = next[p];
            cout<<A[p].v<<" ";
        }
    }
};
/*最后实现main函数*/
int main()
{
    OrderedList l;
    int x;
    while(scanf("%d",&x),x!=-1)
    {
        l.insert(x);
    }
    l.print();
    return 0;
}
  • 具体每次运行的结果，请看运行数据.md

上面的是简单的排序操作，我们再结合一下例题

示例

  • 有n个盒子在桌子上的一条线上从左到右编号为1……n。你的任务是模拟四种操作

    1 X Y 移动盒子编号X到盒子编号Y的左边（如果X已经在Y的左边了就忽略）

    2 X Y 移动盒子编号X到盒子编号Y的右边（如果X已经在Y的右边了就忽略）

    3 X Y 交换盒子编号X与盒子编号Y的位置

    4 将整条线反转

    操作保证合法，X不等于Y

    举一个例子，如果n=6，操作 1 1 4然后就变成了2 3 1 4 5 6；再操作 2 3 5就变成了 2 1 4 5 3 6；再操作 3 1 6 就变成 2 6 4 5 3 1；最后操作4，就变成了 1 3 5 4 6 2

    输入

    最多有10组数据，每个数据会包含两个整数n,m（1≤n,m<100,000）, 接下来是m行数据，表示操作。

    输出

    对于每组数据，输出他们奇数位置的编号的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*
	这道题，也可以用数组来模仿链表来实现，而且，数组的操作方式更加高效
	上面的排序例子，我们只设计了一个next数组，但是这道题目，需要把链表断开来再连上去
	需要前后相连，所以，我们需要设计一个 prev数组。 同样，我们要新建一个 dummyNode
	首先，dummyNode的前驱，是n； dummyNode 的后继是1；
	所以我们看到这个链表其实是一个循环链表！
	因为这是从1，2，3，4......n的n个盒子。所以，不需要再建立一个数组存储数据
	所以不用建立一个映射，数组的下标其实就代表了第n个盒子的标号
*/
#include<bits/stdc++.h>
using namespace std;
int r[100000+5],l[100000+5];
void init(int n)
{
    for(int i = 1;i<=n;i++)
    {
        l[i]=i-1;//1到n的前驱，就是0，1，2，.....n-1；
        r[i]=(i+1)%(n+1);//1-n的后继，就是2，3，4，......0
    }
    //此外还要规定dummyNode的前驱和后继
    r[0]=1;//后继
    l[0]=n;//前驱
}
//这个函数的作用，是把L和R相连也就是说实现 L->R
//那么很显然 L->R只有一个链接，所以L的后继为R，R的前驱为L。这是双向的
void link(int L,int R)
{
    r[L] =R;
    l[R]=L;
}
int main() {
    int n, m, a, x, y, k = 0;
    bool flag;
    while (cin>>n>>m) {
        flag = false;
        init(n);
        for (int i = 0; i < m; i++) 
        {
            cin >> a;
            if (a == 4)
                flag = !flag;//有可能多次反转！
            else {
                    cin >> x >> y;
                    if (a == 3 && r[y] == x) swap(x, y);
                /*
                交换xy的值，不是交换r[x],r[y]的值。反正是互换，这里把x移到y左边，易于操作
                比如说 链表为 1 2 3 4 5，交换x=4与y=3 ，符合上面的条件
                那么我们换成x=3，y=4
                这样的swap其实是不会影响结果的，只是因为方便后面的判断 if (r[x] == y) 
                因为到后面还是交换3，4的值，不管x，y是哪一种，结果都是 1 2 4 3 5
                
                那么本来不是紧挨着的，那么可以换吗？？
                可以，但没必要，因为本来不是紧挨者的，再后面的操作，换不换无所谓
                */
                
                    if (a != 3 && flag) 
                    {
                        a = 3 - a;
                    }
                    if (a == 1 && x == l[y])//如果x本来就在y左边，那么不需要操作
                        continue;
                    if (a == 2 && x == r[y])//如果x本来就在y右边，那么不需要操作
                        continue;
                	//分别定义x，y的前驱和后继
                    int Lx = l[x], Rx = r[x], Ly = l[y], Ry = r[y];
                    if (a == 1)
                    {
                        //如果a=1，那么就需要实现 x--->y
                        link(Lx, Rx);//先让x的前驱后继相连，等于说x脱离链表
                        link(Ly, x);//现在要把y的前驱于x相连，实现y于前驱断开
                        link(x, y);//然后让x于y相连，实现x于y相连，x成为y的新前驱
                    } else if (a == 2)
                    {
                        //如果a= 2，那么就需要实现y------>x
                        link(Lx, Rx);// 等于说x脱离链表
                        link(y, x);//让y于x相连，y成为x的新前驱
                        link(x, Ry);//让本来y的后继成为x的后继，实现x的插入
                    } else if (a == 3)
                    {
                        //如果a=3，那么就需要实现x和y的 交换
                        //如果x本来就在y的左边，那么只要交换x，y两个的位置
                        if (r[x] == y)
                        {
                            //让x的前驱连接y
                            link(Lx, y);
                            //让y链接x
                            link(y, x);
                            //让x链接y原来的后继
                            link(x, Ry);
                        } else
                        {
                            //如果是有点距离的，那么需要多一点的操作
                            //让x的前驱链接y
                            link(Lx, y);
                            //让y链接x的后继
                            link(y, Rx);
                            //现在，y已经处于x的位置了
                            
                            link(Ly, x);
                            //让y的前驱和x相连
                            link(x, Ry);
                            //让x的后继与y原来的后继相连
                            //现在，xy已经实现交换了
                        }
               	 	}
           		 }
        }
        int t = 0;
        long long sum = 0;
        for (int i = 0; i < n; i++)
        {
            t = r[t];
            if(i%2==0)
                sum+=t;
        }
        if(flag&&n%2==0)
        {
            sum = (long long)n*(n+1)/2-sum;
        }
        cout<<"Case "<<++k<<": "<<sum<<endl;
    }
    return 0;
}

总结

  • 综上，我们可以用数组来模拟链表，并做一些类似于链表的操作，还有链式前项星等应用也是通过数组模仿链表来实现的，如果需要操作的对象是无序的，我们需要不仅要建立指针数组，还要建立一个存储数据的数组，来做一个映射。但是如果操作的是有序的1，2，3，…..n的话，其实没必要再新建一个数组存放数据了，直接用数组下标就可以完成操作了
  • 其次，我们在做题目分析的时候需要判断头节点是否会被操作，如果需要被操作，我们还要新建一个dummyNode作为哨兵节点。

下面是运行的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
​```c++
Before the Operation
nxt[0] = -1 nxt[1] = -1
 A[0]= -1  A[1]= 3

After the Operation
nxt[0] = 1 nxt[1] = -1
 A[0]= -1  A[1]= 3
3

Before the Operation
nxt[0] = 1 nxt[1] = -1 nxt[2] = -1
 A[0]= -1  A[1]= 3  A[2]= 6

After the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = -1
 A[0]= -1  A[1]= 3  A[2]= 6
3 6

Before the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = -1 nxt[3] = -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9

After the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = 3 nxt[3] = -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9
3 6 9

Before the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = 3 nxt[3] = -1 nxt[4] = -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8

After the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = 4 nxt[3] = -1 nxt[4] = 3
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8
3 6 8 9

Before the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = 4 nxt[3] = -1 nxt[4] = 3 nxt[5] = -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10

After the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = 4 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10
3 6 8 9 10

Before the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = 4 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7

After the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = 6 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = 4
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7
3 6 7 8 9 10

Before the Operation
nxt[0] = 1 nxt[1] = 2 nxt[2] = 6 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = 4 nxt[7] = -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7  A[7]= 5

After the Operation
nxt[0] = 1 nxt[1] = 7 nxt[2] = 6 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = 4 nxt[7] = 2
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7  A[7]= 5
3 5 6 7 8 9 10

Before the Operation
nxt[0] = 1 nxt[1] = 7 nxt[2] = 6 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = 4 nxt[7] = 2 nxt[8] = -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7  A[7]= 5  A[8]= 4

After the Operation
nxt[0] = 1 nxt[1] = 8 nxt[2] = 6 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = 4 nxt[7] = 2 nxt[8] = 7
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7  A[7]= 5  A[8]= 4
3 4 5 6 7 8 9 10

Before the Operation
nxt[0] = 1 nxt[1] = 8 nxt[2] = 6 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = 4 nxt[7] = 2 nxt[8] = 7 nxt[9] = -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7  A[7]= 5  A[8]= 4  A[9]= 2

After the Operation
nxt[0] = 9 nxt[1] = 8 nxt[2] = 6 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = 4 nxt[7] = 2 nxt[8] = 7 nxt[9] = 1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7  A[7]= 5  A[8]= 4  A[9]= 2
2 3 4 5 6 7 8 9 10

Before the Operation
nxt[0] = 9 nxt[1] = 8 nxt[2] = 6 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = 4 nxt[7] = 2 nxt[8] = 7 nxt[9] = 1 nxt[10] =
 -1
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7  A[7]= 5  A[8]= 4  A[9]= 2  A[10]= 1

After the Operation
nxt[0] = 10 nxt[1] = 8 nxt[2] = 6 nxt[3] = 5 nxt[4] = 3 nxt[5] = -1 nxt[6] = 4 nxt[7] = 2 nxt[8] = 7 nxt[9] = 1 nxt[10]
= 9
 A[0]= -1  A[1]= 3  A[2]= 6  A[3]= 9  A[4]= 8  A[5]= 10  A[6]= 7  A[7]= 5  A[8]= 4  A[9]= 2  A[10]= 1
1 2 3 4 5 6 7 8 9 10
​

```

-------------本文结束，感谢您的阅读-------------