Структура данных для номерной стены

Question

Мне интересно, какая хорошая структура данных для номерной стены будет. Два соседа подытоживают, чтобы дать номер над ними. Имейте все в порядке при прикрепленном изображении пожалуйста

.

Во-первых, я бы сказал, что это график, потому что одна часть участвует в терминах. Но это может быть завершено для поиска. Вторая идея - использовать дерево с удвоением одного листа/узла.

В конце концов, мне нужно заполнить нижнюю часть стены и наложить определенные маски тени (узоры), чтобы заполнить узлы и листья. Поэтому в конце мне нужно найти прямых соседей и их родителей для процедуры заполнения.

Как вы думаете?

Answer 1

Могу ли я предложить вектор вектора? т. Е. Вектор таких элементов, что элемент с индексом i сам по себе является вектором размера i.

Учитывая то, что будет n числа в нижнем ряду стены,

Создание

• создать вектор V из n элементов, где элемент с индексом i сам по себе является вектором размера i
• Присвойте каждому индексу в нижнем ряду вектор (V[n-1][0] до V[n-1][n-1]) с вашими начальными элементами

• Значение каждого элемента j в данной строке i может быть вычислена с помощью простой формулы:

  V[i][j] = V[i+1][j] + V[i+1][j+1] 
  

• Это позволяет заполнить остальную часть структуры (начиная со второго до нижней строке идти к вершине), используя два для петель:

  for (i = size(V)-2; i >= 0; i--) // starting with the second-to-bottom row 
      for (j = 0; j < size(V[i]); j++) 
       V[i][j] = V[i+1][j] + V[i+1][j+1] 
  

Update

для-Лоо ps выше можно понимать как шаг обновления структуры данных, который должен выполняться всякий раз, когда изменяются элементы нижнего ряда.

Удлинитель

Эта структура является расширяемой путем простого добавления вектора размера n+1 в качестве новой строки V[n+1] и затем выполняет операцию обновления.

доступа

Учитывая, любой элемент V[i][j],

• он имеет ровно 2 детей V[i+1][j] и V[i+1][j+1] (если оно не находится в нижнем ряду, конечно)
• он имеет по крайней мере 1 (за исключением верхний элемент) и до 2 родителей
  • V[i-1][j]
  • V[i-1][j-1]