4

最近我在一个关于 codeforces 的编程竞赛中遇到了一个问题。问题标签是指使用两个指针的方法可以解决问题。究竟什么是两指针方法？

4

4 回答 4

2

从我在这些链接中可以看出，“双指针方法”只是指使用两个不同的索引索引到两个不同的数组（它们将数组索引称为指针，这与大多数 C 程序员使用该术语的方式有些不同） .

他们在类似问题的情况下使用它

if (a[i] + b[j] == X)
  // do something with i and j

wherei和jare 指针（在术语“指针”的一般意义上，而不是 C 数据类型意义上）。

这并不是什么非常奇特的东西，直到今天我才知道有人为它创造了一个特定的术语。

当您与大多数 C 程序员交谈时，“双指针方法”之类的术语意味着涉及双重取消引用，例如

x = **p;

这与他们在 codeforces 链接上谈论的完全不同。

于 2012-12-07T14:53:33.643 回答
1

谷歌报告“双指针方法”的点击次数为 2350，但前几页使用该短语来指代各种算法。它很少大写。可能他们指的是在其他讨论、文献等中已经建立的几个备选方案之一，这些备选方案特定于主办比赛的小组。

于 2012-12-07T11:24:16.240 回答
0

可能他们的意思是有一个指向指针的指针。

在 C 中，这通常在您需要调用函数来修改调用者拥有的指针时使用。

一个示例可能是在二叉树中插入树节点的函数：

void tree_insert(Node **root, int value)
{
  Node *here = *root;

  if(here == NULL)
  {
    if((*root = malloc(sizeof ***root)) != NULL)
      (*root)->value = value;
  }
  else if(value < here->value)
    tree_insert(&root->left, value);
  else if(value > here->value)
    tree_insert(&root->right, value);
}

通过传递一个指向树根的指针（它本身就是一个指针），函数可以改变它。

使用它，可以通过以下方式初始化树：

Node *tree = NULL;

tree_insert(&tree, 42);
tree_insert(&tree, 4711);

在这个例子中，我们当然也可以使用函数的返回值，但希望你明白这一点。

于 2012-12-07T10:23:16.920 回答
0

我猜你在谈论这样的事情：

int **allocation(int n, int m) {
   int **matrix;
   int i;

   matrix = (int **) malloc(sizeof(int *) * n);
   for (i = 0; i < n; i++)
     matrix[i] = (int *) malloc(sizeof(int) * m);

   return matrix;
}
于 2012-12-07T10:27:47.190 回答