初级线性表
vector
v.resize(n,m)
重新调整数组大小为 \(n\)，如果比原来的小，就删除多余信息。如果比原来的大，就把新增的部分初始化为 \(m\)，其中 \(m\) 可以省略。
vector<int> a(n + 1)
初始化。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
using vi = vector<int>;
int main()
{
int n, q;
cin >> n >> q;
vector<vi> a(n + 1);
while(q--)
{
int t;
cin >> t;
if (t == 1)
{
int i,j,k;
cin >> i >> j >> k;
if (a[i].size() < j + 1)
{
a[i].resize(j + 1);
}
a[i][j] = k;
}
if (t == 2)
{
int i, j;
cin >> i >> j;
cout << a[i][j] << endl;
}
}
return 0;
}
- 优势
- 高效存储与查询，复杂度 \(\operatorname O(1)\)
- 劣势
- 移位操作
- 在任意位置插入删除若干数据
- 搜索指定元素
- 无序下
- 复杂度可达 \(\operatorname O(n)\)
- 移位操作
stack
- 手写栈
int stack[maxn];
int p = 0;//栈顶指针
void push(int x)
{
if (p >= maxn)
{
printf("Stack overflow.");
}
else
{
stack[p] = x;p++;
}
}
void pop()
{
if (p == 0)
{
printf("Stack is empty.");
}
else
{
p--;
}
}
int top()
{
if (p == 0)
{
printf("Stack is empty.");
return -1;
}
else
{
return stack[p - 1];
}
}
//栈底为stack[0],栈顶为stack[p - 1]
-
STLs.push(a)s.pop()- ...同理
-
栈模拟递归
-
递归
-
void play(int n) { ans += n; if (n == 1 || n == 2) { return ; } play(n - 1); play(n - 2); } -
栈模拟
-
int stackPlay(int n) { int sum = 0; stack<int> s; s.push(n); while(!s.empty()) { int t = s.top(); sum += s.top(); s.pop(); if (t == 1 || t == 2) continue; s.push(t - 1); s.push(t - 2); } }
-
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
bool is_left(char ch)
{
return (ch == '(' || ch == '[');
}
bool check(char ch1, char ch2)
{
return (ch1 == '(' && ch2 == ')') || (ch1 == '[' && ch2 == ']');
}
int main()
{
int t;
char ch;
string ss;
cin >> t;
while(t--)
{
stack<char> s;
cin >> ss;
if (ss.empty())
{
cout << "Yes\n";
}
for (auto ch : ss)
{
if(s.empty())
{
s.push(ch);
continue;
}
if(check(s.top(), ch))
{
s.pop();
}
else
{
s.push(ch);
}
}
if (s.empty())
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
int s = 0, x, y;
stack<int> n;
int main()
{
char ch;
do
{
ch = getchar();
if (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
}
else if (ch == '.')
{
n.push(s);
s = 0;
}
else if (ch != '@')
{
x = n.top(); n.pop();
y = n.top(); n.pop();
switch (ch)
{
case '+': n.push(y + x); break;
case '-': n.push(y - x); break;
case '*': n.push(y * x); break;
case '/': n.push(y / x); break;
}
}
}while(ch != '@');
printf("%d\n", n.top());
return 0;
}
- 适用于后进先出，先进后出的过程。
queue
- 手写队列
int queue[maxn];
int head, tail;
void push(int x)
{
if(tail >= maxn)
{
printf("Queue overflow.");
}
else
{
queue[tail] = x;
tail++:
}
}
void pop()
{
if(head == tail)
{
printf("Queue is empty.");
}
else
{
head++;
}
}
int front()
{
if(head == tail)
{
printf("Queue is empty.");
return -1;
}
else
{
return queue[head];
}
}
STLq.push(a)- ...
q.front()q.back()- ...
- P1996 约瑟夫问题
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int n, m, t;
queue<int> q;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
q.push(i);
}
while(q.size() != 1)
{
for (int i = 1; i < m; i++)
{
q.push(q.front());
q.pop();
}
printf("%d ", q.front());
q.pop();
}
printf("%d", q.front());
return 0;
}
- 适用于先进先出的过程，如
BFS.
list
-
即通过记录每个元素的下一个元素是谁来实现存储元素排列顺序的表
-
排队例子
-
每个人以
next数组记录下一个人是谁。 -
插队
-
如果以数组实现，要把插队后的元素都后移一位，\(\operatorname O(n)\)
-
链表实现只需在
next上面做文章即可。-
如
y插到x后面 -
void insert(int x, int y) { next[y] = next[x]; next[x] = y; }
-
-
-
退队
-
数组老样子要把后面元素都往前移。
-
链表实现只需在
next上面做文章即可。-
删除
x后面的那位同学 -
void remove(int x) { next[x] = next[next[x]]; } -
可是无法直接删除
x，因为不知道x前面的元素。- 通过双链表，再开一个数组，记录一个元素后面的元素。
-
-
-
-
链表分类
- 单链表
- 每个结点记录自己的后继
- 双链表
- 每个结点记录自己的前驱和后继
- 循环单链表
- 最后一个结点的后继是第一个结点的单链表，形成环形结构。
- 循环双链表
- 块状链表
- 将若干元素分块，串联块
- 跳表
- 相当于平衡树。每个结点有自己的右指针和下指针，通过分层的方式加速查询，而每个元素的层数由概率决定。
- 单链表
-
手写双链表
struct node
{
int pre, nxt;
int key;
node(int _pre = 0, int _nxt = 0, int _key = 0)
{
pre = _pre; nxt = _nxt; key = _key;
}
}s[1005];
int tot = 0;//记录s数组目前使用了多少个位置
int find(int x)//O(n)的查询,可以用map或者数组直接记录一个元素对应的下标
{
int now = 1;
while(now && s[now].key != x) now = s[now].nxt;
return now;
}
void insert_back(int x, int y)//y 插在 x 后面
{
int now = find(x);
s[++tot] = node(now, s[now].nxt, y);
s[s[now].nxt].pre = tot;
s[now].nxt = tot;
}
void insert_front(int x, int y)//y 插在 x 前面
{
int now = find(x);
s[++tot] = node(s[now].pre, now, y);
s[s[now].pre].nxt = tot;
s[now].pre = tot;
}
int ask_back(int x)
{
int now = find(x);
return s[s[now].nxt].key;
}
int ask_front(int x)
{
int now = find(x);
return s[s[now].pre].key;
}
void del(int x)
{
int now = find(x);
int le = s[now].pre, rt = s[now].nxt;
s[le].nxt = rt;
s[rt].pre = le;
}
#include<iostream>
#include<algorithm>
#include<cstdio>
struct node
{
int pre, nxt;
int key;
node(int _pre = 0, int _nxt = 0, int _key = 0)
{
pre = _pre; nxt = _nxt; key = _key;
}
}s[100005];
int tot = 0;
int index[100005] = {0};
int find(int x)
{
int now = 1;
while(now && s[now].key != x) now = s[now].nxt;
return now;
}
void insert_back(int x, int y)
{
int now = index[x];
s[++tot] = node(now, s[now].nxt, y);
s[s[now].nxt].pre = tot;
s[now].nxt = tot;
index[y] = tot;
}
void insert_front(int x, int y)
{
int now = index[x];
s[++tot] = node(s[now].pre, now, y);
s[s[now].pre].nxt = tot;
s[now].pre = tot;
index[y] = tot;
}
void del(int x)
{
int now = index[x];
int le = s[now].pre, rt = s[now].nxt;
s[le].nxt = rt;
s[rt].pre = le;
index[x] = 0;
}
int n, m;
int k, p;
int main()
{
scanf("%d", &n);
s[0] = node();//令 0 恒为最左边的结点
insert_back(0, 1);
for (int i = 2; i <= n; i++)
{
scanf("%d %d", &k, &p);
if (p)
{
insert_back(k, i);
}
else
{
insert_front(k, i);
}
}
scanf("%d", &m);
while(m--)
{
scanf("%d", &p);
if(index[p])
{
del(p);
}
}
int now = s[0].nxt;
while(now)
{
printf("%d ", s[now].key);
now = s[now].nxt;
}
return 0;
}
STLint arr[100] = {1, 2, 3}; list<int> a(arr, arr + 3)- 从
arr中选前三个元素作为list的初始值
- 从
list<int>::iterator it;it++;it--;
a.push_front(x);a.push_back(x)a.insert(it, x)a.pop_front();a.pop_back()a.erase(it)for (it = a.begin(); it != a.end(); it++)
- 优势
- 插入、删除等操作快
- 劣势
- 查询慢，麻烦。