表驱动法c语言_链表的前驱与后继图示

表驱动法c语言_链表的前驱与后继图示背景表驱动方法是一种方案,它允许您在表中查找信息,而不是使用逻辑语句(if和case)来查明信息

背景

表驱动方法是一种方案,它允许您在表中查找信息,而不是使用逻辑语句(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. 复制信息从而能够直接使用键值

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

  2. 转换键值以使其能够直接使用

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

  3. 将键值转换提取成独立的子程序

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

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

今天的文章表驱动法c语言_链表的前驱与后继图示分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/74472.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注