两指针方法

最近我在代码强制编程竞赛期间遇到了一个问题。 问题标签提到可以通过使用两个指针方法来解决问题。 究竟什么是两指针方法?

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

他们在类似问题的背景下使用它

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

其中ij是指针(在术语“指针”的一般意义上,而不是C数据类型的意义)。

这不是什么异国情调,直到今天我还不知道有人为它创造了一个特定的术语。

当你与大多数C程序员交谈时,像“两指针方法”这样的术语会暗示涉及双重引用的内容,例如

 x = **p; 

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

可能他们意味着有一个指针指针。

在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); 

在这个例子中,我们当然也可以使用函数的返回值,但希望你能得到这个想法。

谷歌报道2350次点击“双指针方法”,但前几页使用这个短语来指代各种算法。 它很少资本化。 可能他们指的是已经在其他讨论,文献等中已经建立的几种替代方案中的一种,这些方案专门针对主办竞赛的小组。

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

 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; }