前言

进行 OJ 练习以来做的最复杂的一个题目,A 完之后趁热打铁写个解题报告.

题目描述

详情访问268.进程管理

大体的意思就是实现操作系统中进程管理基本的 fork, kill 和查询功能

输入输出处理

输入

第一行是整数 T, 表示有多少组输入数据.

第二行是整数 N, 表示本组数据中有多少行命令.

接下来每一行是一条命令.形式如下

FORK PID_1 PID_2

KILL PID

QUERY PID

难点一: 同时出现输入组数和操作的数量

这是在之前做的题目中没出现过的.解决办法如下面代码

1
2
3
4
5
6
7
while(T--){
int n;
scanf("%d",&n);
while(n--){
//do something
}
}

难点二: 如何应对输入命令的不同格式

从给出的示例可见, FORK 后面有两个整形参数,其他两个命令后面都只有一个参数,这个时候如果只使用scanf()函数处理输入,会因为输入的变量个数不一致而出现奇奇怪怪的问题,所以转而先使用gets( char*) 获取一整行命令读进 buff 数组,然后用sscanf(char* source, char* fomat, …)进行处理.

要注意的是,因为 scanf("%d",&n)之后会有个\n 会塞在缓冲区, 影响 gets() 函数的正常读入,所以要先getchar() 一下.

另外, gets() 函数在 c11标准中不再被支持,使用之前要注意运行环境限制.

输出

当输入命令为QUERY PID 的形式时会产生输出,如果查询的进程存在则输出 Yes, 否则输出 No.( 注意大小写)

解题思路和坑点

数据储存

首先要解决数据储存的问题.

  1. 采用 bool 类型数组记录每个进程的存在情况, 并且使用下标记录进程号.
  2. map<int,vector<int> >来记录每个进程及其子进程的映射.按照操作系统课本的思想采用链表记录最为恰当,但在 OJ 这种特殊情况下, 自然可以选择更加”偷懒”的方法.更何况 STL 的性能还是相当可靠的.
  3. 对于每一条命令,用sscanf 处理后将指令部分赋值到string 变量, 方便判断.

坑点一: 0进程不能被删除

题目条件中说到0进程在任何情况下都是存在的,因此输入KILL 0不会有任何响应.

坑点二: 子进程的子进程要被删除

比如说如下以来关系0->1->2->3->4,杀死1进程之后,后继的2,3,4进程都必须被杀死,否则会导致 WA.

使用递归删除的办法可以确保子进程的子进程会被安全删除.

不算坑的坑点三

题目中还说到KILL 指令中如果是不存在或者已经结束的进程,则不采取任何操作.这一点在本题中靠输入来保证了,所以不用在代码中额外处理.否则,需要额外的数组来记录每个进程的出现情况.

程序代码

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
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<map>
using std::vector;
using std::map;
using std::string;
char buff[20];
char cmd[10];;
map<int,vector<int> > relation;
bool pid[105];
void killKids(int x){
if(!relation[x].empty()){
//no empty
vector<int>::iterator j;
for(j=relation[x].begin();j!=relation[x].end();j++){
pid[*j] = false;//kill it
killKids(*j);//kill them all
}
relation[x].clear();
}
}// kill kids method
int main(){
int T;
scanf("%d",&T);
while(T--){
relation.clear();//init
memset(pid,0,sizeof(pid));
pid[0] = true;
int n;
scanf("%d",&n);
getchar();
for(int z = n;z>0;z--){
int x,y;
gets(buff);
if(sscanf(buff,"%s%d%d",cmd,&x,&y)==3){
//FORK command
if(pid[x]){
//x exist
relation[x].push_back(y);
pid[y] = true;
}
}else{
string act = cmd;
if(act == "QUERY"){
if(pid[x]==1){
puts("Yes");
}else{
puts("No");
}
}else if(act == "KILL"){
//end all kids
if(pid[x]&&(x!=0)){
killKids(x);
pid[x] = false;//kill x
}
}
}
}
}
}