0603-0605读书报告

学习内容:队列与链表

队列:

通过数组进行队列操作,会费时间较多如图所示

5cfa181397ae265980

每次删除会交换位置,时间较长

于是用指针(我喜欢用int)来记录队列首位末尾便可以快速完成

不多说了

链表

顾名思义就是一条链子,有单向、双向、环形;

一般我会这样用

1
2
3
4
5
6
struct queueDat
{
int data;

queueDat *front = NULL, *back = NULL;
}que[100001];

就是一个结构体,然后除了数据以外有两个指针

于是做了道题目

P1160

就是一道模拟+链表

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
#include <bits/stdc++.h>

using namespace std;
struct queueDat
{
int ID;
queueDat *front = NULL, *back = NULL;
} que[100001];
queueDat *head = &que[1];
void _cut(int ID)
{
queueDat *cut = &que[ID];
if (cut->ID == head->ID)
head = cut->back;
cut = cut->front;
cut->back = cut->back->back;
cut = cut->back;
cut->front = cut->front->front;
}
void _add(int num, int ID, bool back)
{
queueDat *find = &que[ID], *add = &que[num];
if (back)
{
add->front = find;
add->back = find->back;
find->back = add;
find = find->back->back;
find->front = add;
return;
}
else
{
add->back = find;
add->front = find->front;
find = find->front;
find->back = add;
find = find->back->back;
find->front = add;
if (ID == head->ID)
head = add;
}
}
int main()
{
bool inQueue[100001];
memset(inQueue, false, sizeof(inQueue));
inQueue[1] = true;
for (int i = 1; i < 100001; i++)
que[i].ID = i;
que[1].back = &que[1];
que[1].front = &que[1];
int totStudents, a, b;
cin >> totStudents;
for (int i = 2; i <= totStudents; i++)
{
inQueue[i] = true;
cin >> a >> b;
_add(i, a, ((b == 0) ? false : true));
}
cin >> totStudents;
for (int i = 0; i < totStudents; i++)
{
cin >> a;
if (inQueue[a] == true)
{
inQueue[a] = false;
_cut(a);
}
}
b = head->ID;
do
{
cout << head->ID << " ";
head = head->back;
}
while (b != head->ID);
return 0;
}

指针的数据操作一般是->/‘.’

呼~~

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