表驱动法（Table-Driven Methods）

2023-10-29

背景

表驱动方法是一种方案，它允许您在表中查找信息，而不是使用逻辑语句（if和 case）来查明信息。实际上，您可以使用逻辑语句选择的任何内容，都可以使用表进行选择。在简单情况下，逻辑语句更容易，更直接。随着逻辑链变得越来越复杂，表格变得越来越有吸引力。

当使用表驱动方法时，必须解决两个问题。首先，您必须解决如何在表中查找条目的问题。您可以使用一些数据直接访问表。例如，如果您需要按月对数据进行分类，则键入月表很简单。您可以使用索引为1到12的数组。

但当其他数据太笨拙，则无法用于直接查找表条目。例如，如果需要按社会保险号分类数据，则除非可以负担在表中存储999-99-9999的条目，否则就不能直接使用社会保险号直接键入表中。您被迫使用更复杂的方法。以下是在表中查找条目的方法的列表：

直接访问
索引访问
阶梯访问

在选择表驱动法的时候，需要解决的第二个问题是，你应该在表里面存些什么。有的时候，表查询出来的结果是数据。如果你遇到的是这种情况，那么就可以把这些数据保持到表里面。在另外一些情况下，表查询出来的结果是动作（action）。在这种情况下，你可以保持一个描述该动作的代码，或者，在有些语言里，你可以保存对实现该动作的子程序的引用。无论是哪一种情况，表都会变得更为复杂

直接访问表

像所有查找表一样，直接访问表取代了更复杂的逻辑控制结构。它们是“直接访问”，因为您不必跳过任何复杂的步骤即可在表中查找所需的信息。
在这里插入图片描述

示例

假设您需要确定每月的天数（暂是不考虑平/润年）。当然，一种笨拙的方法是编写一个大型的if语句：

if ( month = 1 ) 
   days = 31
else if ( month = 2 ) 
   days = 28
else if ( month = 3 ) 
   days = 31
else if ( month = 4 )
   days = 30
else if ( month = 5 ) 
   days = 31
else if ( month = 6 ) 
   days = 30
else if ( month = 7 ) 
   days = 31
else if ( month = 8 ) 
   days = 31
else if ( month = 9 ) 
   days = 30
else if ( month = 10 )
   days = 31
else if ( month = 11 ) 
   days = 30
else if ( month = 12 ) 
   days = 31 End If

执行相同功能的一种更容易且更可修改的方法是将数据放入表中。

int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
days = months[month -1];

上面第一个例子很好理解，很快就能编写。但当你数组下标索引是不规律的时候呢？例如：

假设你在写一个保险费率的程序，这个费率会根据年龄、性别、婚姻状态等不同情况变化，如果你用逻辑控制结构（if、switch）来表示不同费率，那么会非常麻烦。

if ( gendar == Male )
{
        if ( maritalStatus == Single )
        {
                if ( age < 18 )
                {
                        rate = 80.00;
                }
                else if ( age < 30 )
                {
                        rate = 90.00;
                }
                //.......其他略
        }
        else if ( maritalStatus == Maried )
        {
                //又是一串年龄判断分支
        }
}
else if ( gendar == Female )
{
        //又是一串婚姻状况判断分支
}

但是从上面的日历例子来看，这个年龄却是个范围，不是个固定的值，没法用数组或者对象来做映射，那么该怎么办呢？这里涉及到了上面说的问题，如何从表中查询？
这个问题可以用阶梯访问表和直接访问表两种方法来解决，阶梯访问这个后续会介绍，这里只说直接访问表。

有两种解决方法：

复制信息从而能够直接使用键值

我们可以给1-17年龄范围的每个年龄都复制一份信息，然后直接用age来访问，同理对其他年龄段的也都一样。这种方法在于操作很简单，表的结构也很简单。但有个缺点就是会浪费空间，毕竟生成了很多冗余信息。
转换键值以使其能够直接使用

我们不妨再换种思路，如果我们把年龄范围转换成键值呢？这样就可以直接来访问了，唯一需要考虑的问题就是年龄如何转换为键值。
我们当然可以继续用if else完成这种转换。前面已经说过，简单的if else是没什么问题的，表驱动只是为了优化复杂的逻辑判断，使其变得更灵活、易扩展。
将键值转换提取成独立的子程序

如果你必要构造一些数据让它们像表键值一样使用，那么就把数据到键值的转换提取到独立的子程序。这么做可以避免在不同位置执行了不同的转换，也使得转换操作修改起来更加容易。

typedef enum gender
{
	 Man,
	 Woman
}Gender;

typedef enum marrialstatus
{
	 Single,
	 Married
}MaritalStatus;

typedef enum smokingstatus
{
	 Smoking,
	 NoSmoking
}SmokingStatus;

//表驱动法来代替多判断语句
//可通过赋值、读入数据等方式来进行表初始化
typedef std::map<Gender, std::map<MaritalStatus, std::map<SmokingStatus, double> > > RATETABLE;
static RATETABLE rateTable;

void InitRateTabel()
{
	 rateTable[Man][Single][Smoking] = 20.8;
	 rateTable[Man][Single][NoSmoking] = 18.2;
	 rateTable[Man][Married][Smoking] = 20.0;
	 //...初始化
}

索引访问表

有时，简单的数学转换功能不足以使从Age等数据跳转到表键。一些这样的情况适合于索引访问方案的使用。

使用索引时，可以使用主数据在索引表中查找键，然后使用索引表中的值查找您感兴趣的主数据。

假设您经营一个仓库，库存约为100件。进一步假设每个项目都有一个四位数的部件号，范围从0000到9999。在这种情况下，如果要使用部件号直接键入描述每个项目某些方面的表，需设置一个索引包含10,000个条目（从0到9999）的数组。除与仓库中100个物料的零件号相对应的100个条目外，其余数组将为空，这造成了大量空间的浪费。
在这里插入图片描述
在用一个简单方法无法将“英文单词”这样数据转换成表下标时,可以考虑使用索引来查找.在.net中的Dictionary<K,V> 就是一个典型的例子。

使用索引查询的主要优点就是代码的可读性大为增强,可维护性也更好。使用分段查找，
分段查找通过确定数据所处的范围确定分类(下标)

struct
{
    int key;
    string strdata;
}arr_datas[]={
    {1,"this is one"},
    {2,"this is two"},
    {3,"this is three"},
};
for (i = 0; i < 3; i++)
{
    if (arr_datas[i].key == val)
    {
        return arr_datas[i].strdata;
    }
}

使用分段查找,需要先把每一个区间的上限写在一个表中,然后通过循环确定所处的区段,最后获得相应的等级。

有人可能想到用stl的map，查找速度会快一些，不过想到定义一个map，然后调用一堆insert其实也挺麻烦的，而且例子中用的是int，但是并不是所有的类型都是可hash的，所以有些情况下map并不能胜任。

阶梯访问表

一种表访问方式是阶梯方法。这种访问方法不像索引结构那样直接，但是它不会浪费太多的数据空间。

如图18-5所示，阶梯结构的总体思想是，表中的记录对于不同的数据范围有效，而不是对不同的数据点有效。
在这里插入图片描述
例如，如果您正在编写评分程序，则“ B”输入范围可能从75％到90％。您可能有一天需要编程编制以下一系列成绩：

范围	评分
≥ 90.0%	A
< 90.0%	B
< 75.0%	C
< 65.0%	D
< 50.0%	E

这可能直接访问有点问题，因为您不能使用简单的数据转换功能来映射字母A到F。而索引方案会很尴尬，因为数字是浮点数。您可能考虑将浮点数转换为整数，在这种情况下，这将是一个有效的设计选项，但是为了说明起见，本示例将坚持使用浮点数。

要使用阶梯方法，您需要将每个范围的最大值放入表格中，然后编写一个循环以对照每个范围的最大值检查分数。当您发现分数首次超过范围最高点时，您就知道分数是多少。使用阶梯技术时，您必须小心地正确处理范围的端点。

  double rangeLimit[] = {50.0, 65.0, 75.0, 90.0, 100.0};
  string grade[] = {"F", "D", "C" , "B", "A"};
  
  int gradeLevel = 0;
  string studentGrade = "A";
  maxGradeLevel = grade.length()-1;
  
  while( (studentGrade  == "A") && (gradeLevel < maxGradeLevel))
  {
      if( StudentScore < rangeLimit(gradeLevel))
       {
           StudentGrade = grade[gradeLevel];
           break;
       }
       else
        gradeLevel++;
  }

需要注意的一些细节：
1，留心端点。
2，考虑用二分查找取代顺序查找。
3，考虑用索引访问来取代阶梯技术

参考：

代码大全（第二版）
https://learning.oreilly.com/library/view/Code+Complete,+Second+Edition/0735619670/ch18s02.html
https://blog.csdn.net/weixin_34072458/article/details/88655317
https://www.cnblogs.com/youxin/p/3202034.html

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构与算法