Как реализовать двойной связанный список только с одним указателем?
Простое решение должно идти вокруг края полигона. Учитывая текущий край om граничные соединительные точки P0 и P1, следующий вопрос на граничном P2 будет точкой с самым маленьким A, где
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
Тогда Вы устанавливаете
P0 <- P1
P1 <- P2
и повторение, пока Вы не возвращаетесь, где Вы запустили.
Это все еще O (N^2), таким образом, Вы захотите отсортировать свой pointlist немного. Можно ограничить набор точек, который необходимо рассмотреть при каждом повторении при сортировке точек на, скажем, их переносе от центроида города.
5 ответов
Звучит так, как будто это невозможно, как сказано. В общем, вы не можете реализовать два указателя, используя только один.
Возможно, вы сможете втиснуть два 16-битных смещения в пространство, используемое единственным (предполагаемым 32-битным) указателем, или каким-нибудь другим "хитрым приемом". , но в целом это кажется невозможным.
В этой статье описывается трюк, основанный на XOR: обработка значений указателя, но я бы счел это хакерством (он выполняет побитовую арифметику над значениями указателя).
Есть классический прием: сохраните XOR двух указателей (Prev и Next), и, путешествуя по списку, у вас всегда есть один из них под рукой (вы только что пришли оттуда), и вы может выполнить операцию XOR с сохраненным значением, чтобы получить другой указатель.
Излишне говорить, что это не будет работать в среде GC.
Одно из уже предложенных решений - это решение XOR .
Другое решение - решение "обратной стороны":
p1 p2
| |
V V
i1 <- i2 <- i3 <- i4 i5 -> i6 -> i7
p1 указывает на текущий элемент, p2 указывает на следующий элемент, i1 ... i7 - это элементы в списке
Переход вперед выполняется в O (1), и поэтому идет назад путем переворачивания указателей :
Forward one step:
p1 p2
| |
V V
i1 <- i2 <- i3 <- i4 <- i5 i6 -> i7
Backward one step:
p1 p2
| |
V V
i1 <- i2 <- i3 i4 -> i5 -> i6 -> i7
Это решение лучше, чем решение XOR, с точки зрения читаемости и того, что оно более понятно для людей. Недостатком является то, что у вас не может быть нескольких точек входа в связанный список.
Если sizeof (int) == sizeof (Node *) , то есть промежуточный узел, который содержит обратный указатель.
Например
(реальный узел) -> (промежуточный узел) -> (узел чтения) -> (и т. д.)
где (реальный узел) содержит значение и указатель на следующий (промежуточный узел) , и (промежуточный узел) содержит in val обратный указатель на предыдущий промежуточный узел и in pa прямой указатель на следующий (узел чтения) .
Кстати, это глупо , глупый вопрос. Я не вижу, чтобы это учит чему-то ценному.