C++ - 具有下限/上限的圆形数组？

Question

我想创建一个类似于双链表(但有数组)的东西,它与下限/上限一起使用.

典型的圆形阵列可能看起来像:

next = (current + 1) % count;
previous = (current - 1) % count;

但是,将下限/上限正确地纳入其中的数学运算是什么？

• 0(下界第1项)
• 1
• 2(上限项目1)
• 3(下界第2项)
• 4(上限项目2)

以便:

- >索引2上的下一个项目1返回0

- >上一个索引0,项目1返回2

- >对于项目2,索引4上的下一步返回3

- >上一个索引3,项目2返回4

谢谢 !

注意:不能使用外部库.

Answer 1

一般数学术语:

next === current + 1 (mod count)
prev === current - 1 (mod count)

其中===是'congruent'运算符.将其转换为模数运算符,它将是:

count = upper - lower
next = ((current + 1 - (lower%count) + count) % count) + lower
prev = ((current - 1 - (lower%count) + count) % count) + lower

您可以自行查找每个项目的上限和下限.您可以将其存储在二叉树中以便快速检索.也许我不理解你的问题.

(请注意,这假设低<上,低> 0)

Answer 2

          +=======+        +=======+        +=======+
          |  Obj  | --->   |  Obj  |  --->  |  Obj  |
buffer    |   1   | <---   |   2   |  <---  |   3   |
          +=======+        +=======+        +=======+  

index       0                  1                2        /* our first run */

index       3                  4                5        /* second run */

and so on ...

因此,您看到3个成员列表,第1个项目被索引0, 3, 6,等.同样,第二个项目被索引1, 4 (1 + 3), 7 (4 + 3), ...

一般规则是:next <- (next + 1) % size,在哪里size = upper - lower + 1

使用这个公式我们得到:

  curr |      next  
-------+-----------------
   0   | (0 + 1) % 3 = 1
-------+-----------------
   1   | (1 + 1) % 3 = 2
-------+-----------------
   2   | (2 + 1) % 3 = 0
-------+-----------------

希望有所帮助