數字牆的數據結構

Question

我想知道數字牆的好數據結構是什麼。兩個鄰居總結給他們上面的數字。請在附圖中有所有確定

。

首先，我會說這是一個圖，因爲一部分涉及到術語。但它可能會被搜索到。第二個想法是使用一個具有雙葉/節點的樹。

最後，我需要填充牆底，並應用特定的陰影遮罩（圖案）來填充節點和葉子。所以最後，我需要找到直接的鄰居和他們的父母填寫程序。

您認爲如何？

Answer 1

可能我建議一個矢量向量？ 即元素的向量，使得索引i處的元素本身是大小爲i的向量。

鑑於會有壁的底行中n號碼，

創作

• 創建矢量n的V元素，其中在索引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循環：

  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] 
  

更新

的換廁所上面的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]