云曦

Choice is more important than effort

0%

数组模拟数据结构

发表于 分类于
本文字数： 6.9k 阅读时长 ≈ 6 分钟

我们可以用数组模拟数据结构，自定义一些函数和变量表示地址和value，而免去了过多的数据结构的定义，特别是指针的麻烦。

1.模拟散列表

把一个较大范围内的数转化为较小范围的数的集合。

模上一个数(x%N+N)%N防止下标出现负数

数据结构

用一个数组表示要插入的槽，如果哈希产生了冲突，则把数插入到槽中(单链表)。

数组+模拟链表

拉链法

实现代码：

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
#include<cstring>
#include<iostream>
using namespace std;

const int N = 100003; // 最好选质数
int h[N],e[N],ne[N],idx;

// 把某个数插入到槽内
void insert(int x)
{
    int k = (x%N+N) % N; // 求槽的下标
    e[idx] = x; // e数组是存取插入所有数的数据
    ne[idx] = h[k]; // 开始终点为-1，指向上一个结点,记录单链表
    // 的上一个结点
    h[k] = idx++; // 结点递增
}
// 散列表查询
bool find(int x)
{
    // 找到所在的槽
    int k = (x%N+N)%N;
    for(int = h[k];i != -1;i=ne[i])
    {
        if(e[i] == x)	return true;
    }
    return false;
}
int main()
{
    // 先把每个槽都置为-1，因为没有上个结点存在
    memset(h,-1,sizeof h);
    
}

开放寻址法

在一个数组中存数，如果当前位置没有人，则可以插入；否则一直向后查找，直到找到一个空位进行插入。

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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003, nul = 0x3f3f3f3f;
// N 应该为数据总数的整数倍数
int h[N];

int find(int x) // 查找和插入通用的函数
{
    int k = (x%N+N)%N;// 先锁定下标,再找空位
    while(h[k] != nul && h[k]!=x)
    {
        k++;
        if(k==N) k = 0; // 到尾了，返回头部进行插入
    }
    return k;
}
int main()
{
    memset(h,0x3f,sizeof h);
    int x;
    cin >> x;
    int k = find(x);
    // 插入
    h[k] = x; // 找到可以插入的空位
    
    // 查询
    if(h[k] != nul)	puts("存在该数字");
    // 如果当前的位置为空位，说明之前这个数字并没有进行插入，所以没有出现过
    
}

2.模拟链表

e数组表示当前位置的数值；ne数组表示当前位置下一个节点的位置

该题目详细题解

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
#include<iostream>
using namespace std;
const int N = 100010;
int idx, a[N], ae[N]; 
int head;
// idx 表示当前还未填入的数，可以表示第几个插入的顺序，不过从0开始
// a[i]表示第 i + 1 次插入的数值,ae[i] 表示当前元素的下一个元素在 a 数组中的下标idx
void add_to_head(int x)
{
    a[idx] = x;
    ae[idx] = head;
    head = idx;
    idx++;
}

void add(int k, int x) // 在第k个插入的数后插入x
{
    a[idx] = x;
    ae[idx] = ae[k];
    ae[k] = idx;
    idx++;
}

void delt(int k) // k是第k个插入的数
{
    ae[k] = ae[ae[k]]; // 指向把第k个数指向下下个下标位置
}


int main(){
    int n;
    idx = 0, head = -1;
    cin >> n;

    while(n--)
    {
        char op;
        cin >> op;
        int k, x;
        if(op == 'H')
        {

            cin >> x;
            add_to_head(x);
        }
        if(op == 'D')
        {

            cin >> k;
            if(!k)  head = ae[head]; // k为0时删除头节点,head原来指向的第一个节点下标，那么head的值就是第一个节点的下标
            // 所以ne[head]是第二个节点的下标
             delt(k-1); // 第k个插入的数下标为 k - 1
        }
        else if(op == 'I'){
            int k, x;
            cin>>k>>x;
            add(k-1,x);
        }

    }
    for(int i=head;i!=-1;i=ae[i])
      cout<<a[i]<<" ";

    return 0;
}

3.邻接表模拟图

  • 用数组邻接表模拟无向图

https://www.acwing.com/blog/content/4663/详细分析点此链接

1
2
3
int h[N] // 下标为结点的编号
int e[M], w[M], nxt[M]; // e,w,nxt数组下标为边的编号
int idx; // idx为边的编号

图片解析

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
const int N = 1010, M = 1010 * 2;
int h[N],e[M],nxt[M],idx;

void add(int a, int b, int weight) // 起点、终点、权重
{
    e[idx] = b; // 记录终点
    w[idx] = weight; // 记录权重
    nxt[idx] = h[a]; // 与该条边邻接的边(以a为起点的边)的编号
    h[a] = idx; // 以a为起点对应的上一条边的编号,更行h[a],方便下一条边记录数据
    idx++;
    
    /*
     e[eidx] = v;        // 记录边的终点
    w[eidx] = weight;   // 记录边的权重
    nxt[eidx] = h[u];   // 将下一条边指向结点u此时的第一条边
    h[u] = eidx;        // 将结点u的第一条边的编号改为此时的eidx
    eidx++;             // 递增边的编号edix, 为将来使用
    */
}

// 遍历结点u的所有相邻的边
void iterate(int u)
{
    for(int eid = h[u];eid != -1;eid = nxt[eid])
    {
        int v = e[eid];
        int weight = w[eid];
        cout << u << "->" << v << ",weight:" << we
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    memset(h,-1,sizeof h);
    idx = 0; // 编号从0开始
    
    while(m--)
    {
        int u, v, weight;
        cin >> u >> v >> weight;
        add(u,v,weight);
    }
    
    for(int u = 1; u <= n;u++)
        iterate(u);
    return 0;
}

在有向图中， 1->2和1->3表示的才是领边，才会被nxt数组记录；

又如2->4和3->4之间 2 和 3是不相通的，所以nxt数组值为 -1，表示没有邻接边

  • 模拟有向图

如果要模拟无向图那么只要双向的边都看作不同的两条边添加就行了，比如

add(a,b) and add(b,a)即可

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010, M = N * 2;
int h[N], e[N], ne[M], w[N], idx; // 注意w表示结点的评分，而不是边的权值
LL f[N]; // 状态数组

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u,int fa) // 记录父节点防止又回头往上搜,u 表示的是结点编号从 1 - n
{
    f[u] = w[u]; // 记录点的值
    for(int i = h[u];i != -1;i = ne[i]) // h[u]表示的是 u 为起点的边的编号，再用ne[i]找到上一个以 u 为起点的编号，直到找到所有
    // 在其之前加入的领边
    {
        int j = e[i]; // 记录的是终点
        if(j != fa)
        {
            dfs(j,u); // 此时的父节点是u
        }
    }
}
int main()
{
    int n; 
    cin >> n;
    memset(h,-1,sizeof h);
    for(int i = 1;i <= n;i++)   scanf("%d",&w[i]);
    
    // 边数 = 点数 - 1
    for(int i = 0;i < n - 1; i ++)
    {
        int a, b;
        scanf("%d%d",&a, &b);
        add(a,b), add(b,a);
    }
    dfs(1,-1); // 从上面的1结点开始向下搜
    return 0;
}

注意事项

1.无向图与有向图e, ne, w数组的数组大小
(1). 无向图
h[N], e[M * 2], ne[M * 2], w[M * 2], idx;

(2). 有向图
h[N], e[M], ne[M], w[M], idx;

邻接表图的遍历

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = N * 2;
int h[N], e[M], ne[M], idx;
bool st[N];

// 添加一条边a->b
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// dfs遍历邻接点函数
void dfs(int u) {
	printf("%d\n", u);
	st[u] = true;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		printf("%d\n", j);
	}
}
// dfs遍历所有点的函数

void dfs(int u) {
	st[u] = true; // st[u] 表示点u已经被遍历过

	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];

		if (!st[j]) {
			printf("%d\n", j);
			dfs(j); // 继续递归
		}
	}
}

int main() {
	int n;
	memset(h, -1, sizeof h);
	cin >> n; // 设有n个点  1- n
	for (int i = 0; i < n - 1; i++) { // n - 1条边
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	dfs(1);
	return 0;
}

c3bKje.png
可以看到输入 6 条边(7个点)的图，从1开始遍历它只会输出1的领边的终点，ne[idx] = h[a],记录的是以a为起点的边的编号，

2<—->6 和 7<—->2并没有以1为起点，或1的领边的终点没有交集，所以不会遍历到下面的边。

c3b0Bj.png
后加入的线路先输出，但是先输出的最相邻的，因为要先遍历邻边的终点k，再以k为起点遍历下一层的边

4.模拟队列

我们可以不采用queue来模拟队列完成bfs操作

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
int hh = 0; // 队头
int tt = -1; // 队尾
int q[N];

// 当 hh <= tt 时，表示队列中有元素
hh.....tt
队头	  队尾
// 队尾插入元素
void push(int x)
{
    q[++tt] = x; // 插入的第一个元素为q[0]
}

// 队头删除元素
void pop()
{
 	hh++;
}

// 判断空
bool empty()
{
    if(hh > tt)	return true;
    else return false;
}

// 取出队头元素
int query()
{
    return q[hh];
}

5.单调队列

单调队列是维护一个单调递增或递减的队列

入队和出队操作满足以下两点：

1、入队：对于一个点而言，如果加入队列后满足队列的单调性质，就可以入队

2、出队：对于一个点而言,如果说新加入的点,比它更加具有潜力,潜力一般指(拓展性更强,生存能力更高,节点入队时间短

单调队列适用于那些范围

单调队列,其实是单调栈的一个升级plus版本,或者说是具有[l,r]区间性质的单调栈.(注:单调栈一般来说是[0,r]类型的)

单调队列算法步骤
对于一个数而言,它可以从队尾入队,必须满足题目的特定条件
对于一个队头的数而言,如果说新来的数,不仅是新来的具有潜力,而且又自身价值还比它价值高,那么不用说队头出队.
总而言之,队列的单调条件,性质如何设置,是我们解题的关键.

*\*单调队列的****核心****（我认为的哈）：得到当前的某个范围内的最小值或最大值

题目

题目描述
有一个序列a[1],a[2],……,a[n],求其中长度<=m的最大连续子序列和.

题解：可以使用前缀和来求解，a[i]+a[i+1]+...+a[j]可以表示为s[j]- s[i-1]

我们可以枚举每 m 段数据的右端点，并在左边1<= i-j <= m维护左端点，即找出最小的s[j]，使得队头的元素永远是最小值。每次只要取队头的ql就是当前队列的最小值

用q数组保存前缀和数组的下标

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
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
int n,m,q[N],ql,qr;
ll s[N];
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>s[i];
        s[i]+=s[i-1];
    }
    ll res=INT_MIN;
    // q数组存储下标
    ql=qr=1; // 先把0入队表示s[0]，那么 ql = 1
    q[1]=0;//初始决策
    for (int i=1;i<=n;i++) {
        while(ql<=qr&&i-q[ql]>m) ql++; // 限定范围，超过范围则前面的数要出队
        res=max(res,s[i]-s[q[ql]]);
        // 更新队头，要保持单调的性质
        while(ql<=qr&&s[q[qr]]>=s[i]) qr--; // 新加入的数比前面的小，那么前面的数要出队空出位置给新加入的数
        qr++;
        q[qr]=i;
    }
    cout<<res<<endl;
    return 0;
}

详情也可看这篇文章：

https://blog.csdn.net/LJD201724114126/article/details/80663855