5.5　难以构成跳转表的switch（1）

通过5.4节的学习可知，当switch为一个有序线性组合时，会对其case语句块制作地址表，以减少比较跳转次数。但并非所有switch结构都是有序线性的，当两个case值的间隔较大时，仍然使用switch的结尾地址或者default语句块的首地址来代替地址表中缺少的case地址，这样就会造成极大的空间浪费。

对于非线性的switch结构，可以采用制作索引表的方法来进行优化。索引表优化，需要两张表：一张为case语句块地址表，另一张为case语句块索引表。

地址表中的每一项保存一个case语句块的首地址，有几个case语句块就有几项。default语句块也在其中，如果没有则保存一个switch结束地址。这个结束地址在地址表中只会保存一份，不会像有序线性地址表那样，重复保存switch的结束地址。

索引表中保存地址表的编号，它的大小等于最大case值和最小case值的差。当差值大于255时，这种优化方案也会浪费空间，可通过树方式优化，这里就只讨论差值小于或等于255的情况。表中的每一项为一个字节大小，保存的数据为case语句块地址表中的索引编号。

当case值比较稀疏，且没有明显的线性关系时，如将代码清单5-11中case 7改为case 15，并且还采用有序线性的方式优化，则在case地址表中，下标7~15之间将保存switch结构的结尾地址，这样会浪费很多空间。所以，这样的情况可以采用二次查表法来查找地址。

首先将所有case语句块的首地址保存在一个地址表中，参见图5-8。地址表中的表项个数会根据程序中case分支来决定。有多少个case分支，地址表就会有多少项，不会像有序线性那样过多浪费内存。但是，如何通过case值获取对应地址表中保存的case语句块首地址呢？为此建立了一张对应的索引表，参见图5-7，索引表中保存了地址表中的下标值。索引表中最多可以存储256项，每一项的大小为1字节，这决定了case值不可以超过1字节的最大表示范围（0~255），因此索引表也只能存储256项索引编号。

在数值间隔过多的情况下，与上节介绍的制作单一的case线性地址表相比，制作索引表的方式更加节省空间，但是由于在执行时需要通过索引表来查询地址表，会多出一次查询地址表的过程，因此效率会有所下降。我们可以通过图5-6来了解非线性索引表的组成结构。

此方案所占用的内存空间如下①：

（MAX - MIN）* 1字节 = 索引表大小

SUM * 4字节 = 地址表大小

占用总字节数 = （（MAX - MIN）* 1字节）+（SUM * 4字节）

（点击查看大图）图5-6　索引表结构模拟图

看了这么多的理论，你可能会觉得烦琐，通过实际调试，你会发现这个优化结构很简单，并没有想象中的那么复杂，如代码清单5-15所示。

代码清单5-15　非线性索引表的C++(www.cppentry.com)代码

int nIndex = 0;  
scanf("%d", &nIndex);  
switch(nIndex){  
case 1: printf("nIndex == 1");break;  
case 2: printf("nIndex == 2");break;  
case 3: printf("nIndex == 3");break;  
case 5: printf("nIndex == 5");break;  
case 6: printf("nIndex == 6");break;  
case 255: printf("nIndex == 255");break;  
}