上周的CCF/CSP认证成绩出来了，第四题用粗暴的Dijkstra的思想强行遍历，本来估计能拿个60分，结果爆0分，耿耿于怀。
我考试用的是C++。
#include<iostream> using namespace std; int main() {int dis[8000][8000];//代码 }
没记错的话，当时是因为像上面代码一样在main函数里面开了个8000*8000的数组（这道题用Vector来模拟链表确实是很省空间的做法，但既然用了O(n^2)的算法，就不指望能过60分以后的数据了，还有，这篇文章的重心不在怎么解题，所以我就不放题目了），结果DEV-CPP编译每次都报溢出，我就想着估计是DEV-CPP的问题吧，毕竟我平时用的都是CodeBlocks。当时还仔细算了下:
8000*8000*4/1024/1024≈244 MB.
8192*8192*4/1024/1024≈256 MB.
题目给了256MB的内存，能开8192*8192的数组，只开8000*8000怎么样都不应该爆空间吧。于是开着100*100的小数组，将各种可能的样例测试通过后，我就提交了代码，提交前刻意把100*100的改回8000*8000，想尽可能地蹭分。
结果——这道题0分了。
我不服，于是我用CodeBlocks将代码重新敲了一遍……呐，结果如下，看来不是代码编辑器配置的问题了。
再之后，改成1000*1000也会溢出。不科学啊？我以前刷过一些OJ，也开过百万级别的数组而且没有报错过啊！我立刻查了几道曾经在hduoj上提交的题目的代码，数组都是这么开的：
#include<iostream> using namespace std; int dis[8000][8000]; int main() {//代码 }
区别很明显，开成全局数组。改了重新码了一遍的代码，编译一下，果然通过了。提交了代码，也果然是我预计的60分（别说我没追求），空间使用也在估计的范围左右……
△所以，发生了啥？为啥数组作为全局变量空间可以开那么大，作为main函数里面的局部变量却只能开那么小？
这就涉及到了C语言的内存分配问题，上课的时候都听说过，C语言占用的内存可以分为5个区：
①代码区（Text Segment）：不难理解，就是用于放置编译过后的代码的二进制机器码。
②堆区（Heap）：用于动态内存分配。一般由程序员分配和释放，若程序员不释放，结束程序时有可能由操作系统回收。（其实就是malloc()函数能够掌控的内存区域）
③栈区（Stack）:由编译器自动分配和释放，一般用来存放局部变量、函数参数（敲黑板划重点了！）。
④全局初始化数据区/静态数据区（Data Segment）：顾名思义，就是存放全局变量和静态变量的地方。这个区域被整个进程共享。
⑤未初始化数据区（BSS）：在运行时改变值。改变值（初始化）的时候，会根据它是全局变量还是局部变量，进到他们该去的区。否则会持续待在BSS里面与世无争。（待会儿会用实验来证明并感受它的存在。）
代码区和堆区不赘述，不在我关注的范围内。貌似空间大小取决于内存的大小和CPU的寻址空间。
我今天只讲一讲Stack和Data Segment这两个导致我爆0分的玩意儿。
在Windows下，Data Segment的所允许的空间大小取决于剩余内存的大小，也就是说，如果电脑剩余8G内存的话，int类型的二维数组甚至可以开到46340*46340的大小；
而Stack的空间只有2M！！也就是2*1024*1024=2097152字节，局部变量空间顶多放得下下524288个int类型！
行吧，知道上述几个关键后，一开始的问题就不是问题了。但我想在局部中开一个大数组怎么办？很简单，将它归到Data Segment中：
#include<iostream> using namespace std; int main() {static int dis[8000][8000];//代码 }
由于静态变量和全局变量一样，都是存在Data Segment中的，所以这么做，相当于把大数组开在了Data Segment中，不会因为堆栈溢出2M空间而报错了。（这样做的话，需要注意局部函数的初始化）。
△深入：BSS区的存在！
其实，文章本来在这里就要结束了，但是我闲着蛋疼，手动二分，强行找到了Stack区所能开的int数组的大小（真实情况下不可能是2M刚好），然后发现了神奇的一幕（后来才知道BSS区的存在），于是干脆就写出来了：
#include<iostream> using namespace std; int main() {int dis[520072]; //520072 }
520072是我手动二分得到的结果，如果开520073的话会堆栈溢出（不同电脑不知道一不一样）。
520073*4/1024/1024≈1.984MB（接近2MB，没毛病）
然而，神奇的一幕出现了：
#include<iostream> using namespace std; int main() {int dis[520072];//520072int a1;int a2;int a3;int a4;int a5;int a6;int a7;int a8;int a9;int b1;int b2;int b3;int b4;int b5;int b6;int b7;int b8;int b9; ｝
理论上，我开第520073个整型出来的时候，编译器应该报堆栈溢出的错误才对，然而并没有！然而并没有！
这就涉及到了我刚才提到的未初始化数据区（BSS）的存在了——在运行时改变值。改变值（初始化）的时候，会根据它是全局变量还是局部变量，进到他们该去的区。否则会持续待在BSS里面与世无争。
在给未初始化的变量赋值之前，它们始终待在BSS区，所以Stack区并不会溢出。而在局部定义数组的时候，数组会自动初始化为全0，所以数组在刚被定义的时候就塞进Stack区了，才会出现int dis[520073]直接报堆栈溢出的问题。
证明上述说法的代码如下：
这段代码在运行时会堆栈溢出。#include<iostream> using namespace std; int main() {int dis[520072];//520072int a=10； }
这段代码会正常进入循环中，始终不会报堆栈溢出。#include<iostream> using namespace std; int main() {int dis[520072];//520072int a;while(1){}a=10; }
行了，就说这么多了，祭奠我可怜的0分题。实在好奇什么题的话……算了，贴个题目罢……
