c++ - 解开 Knuth 的结 : how to restructure spaghetti code?

Question

这个问题的灵感来自 How to transform a flow chart into an implementation?它询问从代码中通过算法消除 goto 语句的方法。 answer this 中描述了一般问题科学论文。

我已经根据 Knuth 的计算机编程艺术中的算法 X 的高级草图实现了一些代码，描述了具有受限前缀的字典排列的生成(参见 draft 的第 16 页)。

这是对应的flow chart上述算法。

这可能是一个非常聪明且非常高效的算法，但是代码的结构似乎很难遵循。我最终使用了很好的旧 goto 风格的实现:

//Algorithm X;
1:
initialize();
2:
enter_level(k);
3:
set(a[k],q);
if(test() == ok) {
  if (k == n) {
    visit();
    goto 6;
  }
  goto 4;
}
goto 5;
4:
increase(k);
goto 2;
5:
increasev2(a[k]);
if (q != 0) {
  goto 3;
}
6:
decrease(k);
if (k==0) {
  goto 7;
}
set(p,u_k);
goto 5;
7:
return;

问题是:如何重构此代码以消除所有 goto 调用？

一个(伪造的)答案是建议“查找引用的科学论文，并逐行跟进” - 事实上，这当然是有可能的。但这个问题是关于有经验的程序员一旦瞥了一眼这个 spaghetti code 就会立即看到什么。 .

我对如何重构感兴趣，而不仅仅是代码。

---

注意:

1. 根据高级规范和goto 跳转，实际实现算法 X 很简单。实现黑盒函数 initialize() 等只需要一些额外的指令，但这些与代码的结构无关。函数调用期间发生了什么并不重要，因为现在的重点是程序的流程。
2. 关于“是 GOTO still considered harmful?”的通常辩论与这个问题完全无关，根本不应该在答案和评论中解决。

---

相关:how to work with or complete the spaghetti code?

Answer 1

无需太多努力(而且风险不大)，您可以快速减少 goto 和标签的数量。

1) 删除未在任何地方引用的标签(这将是标签 1:)

2) 查找只有通过 goto 才能输入的代码块，这些代码块在少数地方被调用。这些通常可以简单地分解出来。 4:可以通过将代码移动到它被调用的地方来处理，并且安全地完成，因为它唯一的导出是一个 goto。这也允许我们删除它上面的 goto 5，因为该代码将简单地跳转到 5:。 7:可以通过修改if语句来处理。此时我们有

initialize();
2:
enter_level(k);
3:
set(a[k],q);
if(test() == ok) {
  if (k == n) {
    visit();
    goto 6;
  }
  increase(k);
  goto 2;
}
5:
increasev2(a[k]);
if (q != 0) {
  goto 3;
}
6:
decrease(k);
if (k!=0) {
  set(p,u_k);
  goto 5;
}
return;

我倾向于在这里停下来。但如果继续，就会变成识别循环并用循环结构替换 goto 的问题。但是，由于代码的结构方式，进行这些更改的风险似乎要大得多。此外，您可能会以 breaks 和 continues 结束，这无论如何都是一种 gotos。我最终得到的是这个(如果没有一些非常严格的测试，我不会保证它的正确性):

initialize();
enter_level(k);
while (true) {
  set(a[k],q);
  if(test() == ok) {
    if (k == n) {
      visit();
    } else {
      increase(k);
      enter_level(k);
      continue;
    }
  } else {
    increasev2(a[k]);
    if (q != 0) {
      continue; 
    }
  }
  while (true) {
    decrease(k);
    if (k!=0) {
      set(p,u_k);
      increasev2(a[k]);
      if (q != 0) {
        break; 
      }
    } else {
      return;
    }
  }
}

我做了 3:一个循环，和 6:一个内循环。我通过复制 5: 代码代替 goto 并用 break 替换 goto 3 摆脱了 goto 5。这使得制作更干净的循环变得更容易一些。 goto 6 通过使用 else 来修复。 goto 3 变为继续。

在此之后(如果您还有精力)，您可以尝试将循环从 while(true) with continues 更改为 whiles with actual conditions。

最好先开发测试，然后进行一两处更改并进行测试。进行另一个更改，然后再次测试。如果您不这样做，很容易在早期犯下结构性错误，然后使后续步骤无效并迫使您重新开始。