打印
[其它应用]

C语言跳转表的实现与应用

[复制链接]
1958|10
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
一、跳转表的概念
引用笔者在 Wikipedia 上看到的关于跳转表的概念:
In computer programming, a branch table or jump table is a method of transferring program control (branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch or jump instructions
大概意思是说,跳转表或者也可以被称之为分支表,是一种利用分支或者跳转指令表将程序控制转移到程序另一部分(或者是已经动态加载的其他程序)的方法。
关于跳转到程序的另一部分最常用的方法就是使用 switch 语句,但是使用 switch 语句存在的一个弊端就是如果分支过多,会造成程序的冗长。而跳转表刚好能解决这个问题,对于优化程序的结构有很大地帮助。
在介绍跳转表之前,本文先介绍一下跳转表所涉及到的指针数组和函数指针的概念。
二、指针数组
首先,它是一个数组,数组的元素都是指针,如果有如下指针数组的定义:
  • int*p1[5];

那么,可以采用如下的一个图表明它的含义:
三、函数指针
函数指针的意思就如名称称所示,它是一个指针,一个函数的指针,指向一个函数,比如下面我们就可以定义一个函数指针变量。
  • int(*pf)(int,int);

上述指针变量的意思是定义了一个 pf 的函数指针变量,这个指针变量可以指向的是一个返回值为 int 的,函数两个 int 类型的参数的函数。假设现在我们有一个这样的函数用于两数相加:
  • int add(int num1,int num2);

那么,我们可以通过函数指针变量指向这个函数的形式来调用函数,比如这样:
  • pf = add;
  • pf(5,8);

上述就是关于函数指针的简单叙述。
四、跳转表
在介绍了指针数组和函数指针后,我们就可以来构建我们的跳转表,比如这样:
  • void(*pf[])(void) = {fna,fnb,fnc,fnd};

其中,fna、fnb、fnc、fnd 都是返回值和参数都为 void 的函数,上述定义的函数跳转表的意思也就是有一个函数指针数组,这个数组里面存放的都是函数的指针。
之所以称之为跳转表,就是因为能通过索引的方式进行调用函数,下面就是在定义了上述调转表后的一个应用:
  • void test(constint jump_index)
  • {
  •     pf[jump_index]();
  • }

下面的图片很形象的表达了跳转表的原理:
通过调用 test 函数,带以不同的参数,就可以通过 test 运行不同函数的功能。试想一下,如果这里使用 switch 的方式实现上述功能,代码量是不是要多出许多?
五、举个例子
下面的例子是笔者在一位国外的网友的帖子下看到的,但是网友并没有给出所有代码,缺少一些较为细节的东西,不过并不影响我们理解。
背景: 有一个工业电源接口盒,现通过一个简单的 ASCII 码助记符来作为命令,该接口盒是通过输入命令的形式执行相关操作,并且通过 RS-232 接口向外返回输入的参数值。
通过背景可以知道我们需要定义一个数组存储命令,代码如下:
  • staticconstchar read_str[] =
  • "0SV0SN0MO0WF
  • 1ST1MF1CL1SZ
  • 2SP2VO2CC2CA";

由于背景中要求需要返回参数并通过 RS-232 串口进行传输,因此,通过输入命令后跳转执行的函数都是具有如下返回值和形参的。
  • constchar*fna(void); 

另外,这个函数声明的意思是,函数值类型是 const char *,形参是 void ,返回值类型也与刚刚我们所定义的 read_str 所对应。
综上,就可以定义我们的跳转表了,跳转表定义如下:
  • staticconstchar*
  • (*readfns[sizeof(read_str)/4])(void) =
  • {
  • /*这里是伪代码,因为命令太多,所以这样进行表示*/
  •     una,fna,fnb,...
  • }

una、fnb 等都是与 fna 同类型的函数。说到这里,比较关键的代码就说完了,如下是整个处理过程的代码:
  • constchar*fna(void);

  • staticvoid process_read(constchar*buf)
  • {
  • char*cmdptr;
  • unsignedchar offset;
  • constchar*replyptr;

  • staticconstchar read_str[] =
  • "0SV0SN0MO0WF
  • 1ST1MF1CL1SZ
  • 2SP2VO2CC2CA";

  • staticconstchar*
  • (*readfns[sizeof(read_str)/4])(void) =
  • {
  • /*这里是伪代码,因为命令太多,所以这样进行表示*/
  •         una,fnb,fnc,...
  • }

  • /*cmdptr获得的是当前输入字符的地址*/
  •     cmdptr = strstr(read_str,buf);

  • if(cmdptr != NULL)
  • {
  • /*(当前地址 - 数组基地址)/4 = 索引*/
  •         offset = (cmdptr - read_str) / 4;

  •         replyptr = (*readfns[offset])();
  • }
  • }

上述 strstr 函数的功能,是返回一个输入字符串与数组中字符串匹配的元素的地址。最后根据索引值调用相应的函数执行,所以也就实现了背景中所述的根据输入命令执行相应操作的功能。如果命令有很多个,可想而知使用 switch 将是多么冗长的一段代码。
六、总结
通过上述的例子,很清楚地展示了跳转表在优化代码结构上的强大作用,如果有一组操作所对应的函数具有相同的函数返回值和相同的形参,应该考虑使用跳转表,它将帮助你写出漂亮的代码。

使用特权

评论回复
沙发
AdaMaYun| | 2023-10-28 20:50 | 只看该作者
楼主这个指针跳转真的很实用

使用特权

评论回复
板凳
小夏天的大西瓜| | 2023-10-28 21:23 | 只看该作者
指针跳转确实很好的优化数据代码

使用特权

评论回复
地板
tpgf| | 2023-11-3 10:45 | 只看该作者
跳转表的执行效率如何?高不高

使用特权

评论回复
5
qcliu| | 2023-11-3 12:14 | 只看该作者
这种跳转表的实现需要对指针的应用比较熟练

使用特权

评论回复
6
drer| | 2023-11-3 13:25 | 只看该作者
在什么情况下我们会用到跳转表呢

使用特权

评论回复
7
coshi| | 2023-11-3 14:14 | 只看该作者
跳转表的初衷在于,相对于二叉树更加直观简便

使用特权

评论回复
8
wiba| | 2023-11-3 14:51 | 只看该作者
跳转表直接继承了链表和词典的接口,从而具备两者的功能

使用特权

评论回复
9
kxsi| | 2023-11-3 21:00 | 只看该作者
跳转表是一种基于链表的结构,不同之处在于,节点需要包含上下左右四个方向的指针,查询和动态操作仅需要O(logn)的时间

使用特权

评论回复
10
AdaMaYun| | 2023-11-6 20:42 | 只看该作者
函数指针的意思就是指向一个函数的指针

使用特权

评论回复
11
jf101| | 2023-11-8 20:40 | 只看该作者
C语言的跳转表如何编写ne

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

279

主题

1458

帖子

2

粉丝