POJ1033磁盘文件碎片整理模拟题栈应用

以后一定要细心&＃xff0c;不能再犯这个低级的错误&＃xff0c;把WA控制在最低范围内

参考了 http://www.cnblogs.com/damacheng/archive/2010/09/24/1833983.html的题目分析

题目大意&＃xff1a;你要写一个OS&＃xff0c;要实现磁盘碎片整理的功能。磁盘分为N个簇&＃xff0c;一个文件可以占用K个簇&＃xff0c;(1 <&＃61; K

　　文件1&＃xff1a;2 3 11 12&＃xff0c;占用了4个簇&＃xff0c;编号为1-4。
　　文件2&＃xff1a;7&＃xff0c;占用了1个簇&＃xff0c;编号为5。

　　文件3&＃xff1a;18 5 10&＃xff0c;占用了3个簇&＃xff0c;编号为6-8。

　　初始状态是这样的&＃xff0c;0表示未占用&＃xff1a;

　　簇号&＃xff1a;　　1  2  3  4  5  6  7  8  9 10  11  12  13  14  15  16  17  18

　　逻辑编号&＃xff1a;0  1  2  0  7  0  5  0 0   8   3   4   0  0   0   0   0   6 

　　一共整理到最后&＃xff0c;磁盘的情况最后是这样的&＃xff1a;

　　簇号&＃xff1a;　　1  2  3  4  5  6  7  8  9 10  11  12  13  14  15  16  17  18

　　逻辑编号&＃xff1a;1  2  3  4  5  6  7  8 0   0   0   0  0   0   0   0  0   0 

　　写一个程序得到整理好碎片最少需要多少步操作&＃xff0c;并把这些操作打印出来。比如说第1个簇的内容放到第2个簇&＃xff0c;打印出1 2。操作的定义是这样的&＃xff1a;把一个簇的内容放到另个一个簇中&＃xff0c;算是一步操作。

　　注意这里是Special Judge&＃xff0c;意思是只要答案符合要求就行了&＃xff0c;不必和SAMPLE中的OUTPUT一样也可以AC。

　　怎么才能找到最少的步数呢&＃xff1f;我想了半天也没怎么想出来&＃xff0c;于是看了看DISCUSS&＃xff0c;总结以下&＃xff1a;

　　遍历整个磁盘&＃xff0c;设i为当前遍历的簇的编号&＃xff0c;clusters为整个磁盘&＃xff0c;clusters[i]表示第i个簇是否被占用&＃xff0c;被哪个编号的文件片段占据。

　　(1) 如果clusters[i]为0&＃xff0c;也就是未被使用&＃xff0c;不进行处理。

　　(2) 如果clusters[i]为i&＃xff0c;也就是已经到了整理好的状态&＃xff0c;不进行处理。

　　(3) 如果clusters[i]不满足1和2&＃xff0c;则又有两种情况。

　　　　情况一&＃xff1a;磁盘使用情况成链&＃xff1a;如图所示&＃xff1a;

　　　　簇号&＃xff1a;　　1  2  3  4  5  6 ...　　　　

　　　　逻辑编号&＃xff1a;5  0  4  2  3  0 ...

　　　　第1个簇被第5个文件片断占据&＃xff0c;第5个簇又被第3个文件片段占据&＃xff0c;第3个簇又被第4个文件片段占据&＃xff0c;第4个簇又被第2个文件片断占据&＃xff0c;第2个簇未被占据。算法就很简单了&＃xff0c;按照簇被访问的反方向&＃xff1a;

　　　　clusters[2] &＃61; clusters[4]&＃xff0c;clusters[4] &＃61; clusters[3]&＃xff0c;clusters[3] &＃61; clusters[5]&＃xff0c;

　　　　clusters[5] &＃61; clusters[1]&＃xff0c;最后clusters[1] &＃61; 0。怎么样反方向呢&＃xff0c;使用一个栈就好了。

　　　　情况二&＃xff1a;磁盘使用情况成环&＃xff1a;如图所示&＃xff1a;

　　　　簇号&＃xff1a;　　1  2  3  4  5  6 ...　　　　

　　　　逻辑编号&＃xff1a;5  1  4  2  3  0 ...

　　　　这种情况跟情况一差不多&＃xff0c;只是最后clusters[2]指向了第1个簇&＃xff0c;这样就形成了一个环&＃xff0c;这里只是需要额外处理一下&＃xff0c;就像交换2个变量一样&＃xff0c;先在从磁盘末尾找到1个空的簇&＃xff0c;因为题目保证至少有一个空的簇&＃xff0c;先把clusters[2]放到这个空的簇中&＃xff0c;然后再执行情况1中的操作&＃xff0c;最后再把空的簇的值赋给clusters[1]就好了。最后注意一点&＃xff0c;如果操作次数为0&＃xff0c;则需要输出一行信息。

Source Code