刷题检讨 --(1) 线性表

發表於 更新於 分類於

线性表

(1) 如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用 vector (数组) //iterator

除了用迭代器获取 vector 容器中的元素，[] 和 at 也可以
vector(v).swap (v); // 收缩内存

//vector 利用 v 调用拷贝构造函数，创建匿名对象，它会用 v 目前使用的元素个数来初始化这个匿名对象
//swap () 互换函数的本质类似于指针的交换
// 调换后 v 指向了创建的匿名对象，而本来匿名对象的指针 x 指向原本的 v，并且在该语句过后由系统自动回收

如果没有用 reserve 预留空间，随着 push 进去的数据越来越多，可能需要重新分配内存

1
2
3
4
5
6
7
8
9
10
11
12
13
// 统计内存重新开辟的次数
int num = 0;
int* p = NULL;
for (int i = 0; i < 100000; i++)
{
	v.push_back (i);
	if (p != &v [0])
	{
		p = &v [0];
		num++;
	}
}
cout << "num:" << num << endl;

(2) 如果你需要大量的插入和刪除，而不關心隨機存取，則應使用 list (双向循环链表) //const_iterator

list 的迭代器是双向迭代器，不支持随机访问（不可以通过 [] 或 at 方式访问数据）
it++ // 可以
it = it + 1 // 会报错

(3) 如果你需要隨機存取，而且關心兩端數據的插入和刪除，則應使用 deque

UVA12657

你有 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；
输入：最多有 10 组数据，每个数据会包含两个整数 n,m（1≤n,m<100,000）, 接下来是 m 行数据，表示操作。
输出：对于每组数据，输出他们奇数位置的编号的和。

思路：利用双向静态链表，且反转不用真的反转，只要做标记就好了。
(移动元素需要链表的特性，但是查找是链表不擅长的，所以使用静态链表)
检讨：一开始把 if (a!=3&&flag) a=3-a; 的顺序放在下两个 if 的后面，这样就没有考虑到翻转的情形

1
2
3
4
5
6
if (a!=3&&flag)
	a=3-a;
if (a==1&&x==l [y])
	continue;
if (a==2&&x==r [y])
	continue;

UVA101 The Blocks Problem

初始时从左到右有 nn 个木块，编号为 0 \ldots n-10…n−1, 要求实现下列四种操作：
move a onto b : 把 aa 和 bb 上方的木块归位，然后把 aa 放到 bb 上面。
move a over b : 把 aa 上方的木块归位，然后把 aa 放在 bb 所在木块堆的最上方。
pile a onto b : 把 bb 上方的木块归位，然后把 aa 及以上的木块坨到 bb 上面。
pile a over b : 把 aa 及以上的木块坨到 bb 的上面。
一组数据的结束标志为 quit，如果有非法指令（如 aa 与 bb 在同一堆），无需处理。
输出：所有操作输入完毕后，从左到右，从下到上输出每个位置的木块编号。

思路：使用线性表 vector 来实现
注释：vector 是单端数组（这题最主要涉及的动作是查找，还有向尾端加元素的移动）

UVA11988 破损的键盘 Broken Keyboard (a.k.a. Beiju Text)

你在输入文章的时候，键盘上的 Home 键和 End 键出了问题，会不定时的按下。你却不知道此问题，而是专心致志地打稿子，甚至显示器都没开。当你打开显示器之后，展现你面前的数一段悲剧文本。你的任务是在显示器打开前计算出这段悲剧的文本。 给你一段按键的文本，其中 '[' 表示 Home 键，']' 表示 End 键，输入结束标志是文件结束符（EOF）。
输出一行，即这段悲剧文本。

思路：涉及行首和行尾的操作，使用链表 list（不宜用线性表 vector）

1
2
3
4
5
6
7
void solve (string s)
{
	int len = s.length ();
	list<char> text;
	list<char>::iterator it = text.begin ();
...
}
1
2
3
4
5
6
7
8
// 报错 TLE
list<char> text;
void solve (string s)
{
	int len = s.length ();
	list<char>::iterator it = text.begin ();
...
}

为什么注释掉那行代码结果是错的？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve (string s)
{
	int len = s.length ();
	list<char> text;
	list<char>::iterator it = text.begin ();
	for (int i=0; i<len; i++)
	{
		it = text.insert (it, s [i]);
		it++;
		//text.insert (it++, s [i]);
	}
	for (it=text.begin (); it!=text.end (); it++)
		cout << *it;
	cout << endl;
}

C++ 刷題总览

三連擊（洛谷 P1008）
刷题检讨 —(1) 线性表
刷题检讨