假设我们有一个整数的单链表,并且我们有以下要求:
- 对于给定节点,菜单选项 1 应在控制台输出中显示节点的数据字段和任何后续节点。
- 对于给定节点,菜单选项 2 应仅当数据是 2 的倍数时,才应在控制台输出中显示节点的数据字段和任何后续节点。
- 对于给定的节点,菜单选项 3 应该在控制台输出中显示节点的数据字段和任何后续节点,仅当数据是 3 的倍数时。
一个可能的解决方案如下:
struct node {
int data;
node *next;
};
void insertBeginning(node **list, int data)
{
node *n = new node;
n->data = data;
n->next = *list;
*list = n;
}
void option1(node *node)
{
if (node != NULL) {
cout << node->data << endl;
option1(node->next);
}
}
void option2(node *node)
{
if (node != NULL) {
if (node->data % 2 == 0)
cout << node->data << endl;
option2(node->next);
}
}
void option3(node *node)
{
if (node != NULL) {
if (node->data % 3 == 0)
cout << node->data << endl;
option3(node->next);
}
}
void main()
{
node *root = new node;
root->data = 5;
root->next = NULL;
insertBeginning(&root, 4);
insertBeginning(&root, 3);
insertBeginning(&root, 2);
insertBeginning(&root, 1);
cout << "OPTION 1" << endl;
option1(root);
cout << endl;
cout << "OPTION 2" << endl;
option2(root);
cout << endl;
cout << "OPTION 3" << endl;
option3(root);
}
但仔细检查会发现,在每个菜单选项中都有一个循环遍历节点的算法,这在所有选项中都是相同的,然后是一个特定的操作。因此,将循环算法与动作分开可能会很好。你会怎么做?
在这种情况下,循环算法和动作非常简单,因此进行分离将是杀手锏,但在我的情况下,循环算法和动作更复杂,我想避免复制和粘贴循环算法。此外,这种情况下使用单链表,但它可能是一棵树。无论如何,我不想用这些细节分散你的注意力。
最后考虑第四个选项:
- 对于给定节点,菜单选项 4 应在控制台输出中显示节点的数据字段和任何后续节点的总和。
一个可能的解决方案如下:
void loopNodes(node * n, void action(node * n))
{
if (n != NULL) {
action(n);
loopNodes(n->next, action);
}
}
void option1(node * node)
{
cout << node->data << endl;
}
void option2(node * node)
{
if (node->data % 2 == 0)
cout << node->data << endl;
}
void option3(node * node)
{
if (node->data % 3 == 0)
cout << node->data << endl;
}
int sum;
void option4(node * node)
{
sum += node->data;
}
void main()
{
node *root = new node;
root->data = 5;
root->next = NULL;
insertBeginning(&root, 4);
insertBeginning(&root, 3);
insertBeginning(&root, 2);
insertBeginning(&root, 1);
cout << "OPTION 1" << endl;
loopNodes(root, option1);
cout << endl;
cout << "OPTION 2" << endl;
loopNodes(root, option2);
cout << endl;
cout << "OPTION 3" << endl;
loopNodes(root, option3);
cout << endl;
cout << "OPTION 4" << endl;
sum = 0;
loopNodes(root, option4);
cout << "SUM = " << sum << endl;
}
选项 4 提出了挑战;需要保持状态。我使用了一个具有文件范围的变量,但替代方法可能是(这是我的最终解决方案):
void loopNodes(node * n, void action(node * n, void *state), void *state)
{
if (n != NULL) {
action(n, state);
loopNodes(n->next, action, state);
}
}
void option1(node * node, void *state)
{
cout << node->data << endl;
}
void option2(node * node, void *state)
{
if (node->data % 2 == 0)
cout << node->data << endl;
}
void option3(node * node, void *state)
{
if (node->data % 3 == 0)
cout << node->data << endl;
}
void option4(node * node, void *state)
{
*(int *) state += node->data;
}
void main()
{
node *root = new node;
root->data = 5;
root->next = NULL;
insertBeginning(&root, 4);
insertBeginning(&root, 3);
insertBeginning(&root, 2);
insertBeginning(&root, 1);
cout << "OPTION 1" << endl;
loopNodes(root, option1, NULL);
cout << endl;
cout << "OPTION 2" << endl;
loopNodes(root, option2, NULL);
cout << endl;
cout << "OPTION 3" << endl;
loopNodes(root, option3, NULL);
cout << endl;
cout << "OPTION 4" << endl;
int *sum = new int;
*sum = 0;
loopNodes(root, option4, sum);
cout << "SUM = " << *sum << endl;
}
你怎么看?
任何反馈都非常感谢!
注意:我必须使用核心语言工具(我不能使用标准库、boost 等)。