112
правок
Изменения
К псевдокоду добавлены некоторые комментарии, исправлен пункт 11
M[k] = C[k]
'''for''' i = k - 1 '''to''' 1
pointer_in_C = 1 <font color=green>// указатель на самый левый элемент каталога C[i], который еще не рассмотрели </font> pointer_in_next_M = 1 <font color=green>// указатель на самый левый элемент каталога M[i + 1], который еще не рассмотрели </font> pointer_in_M = 1 <font color=green>// указатель на самый левый элемент каталога M[i], в который будем добавлять элемент </font> node last_non_alien = NULL <font color=green>// указатель на последний ''неподставной элемент'' для текущей позиции </font> node last_alien = NULL <font color=green>// указатель на последний ''подставной элемент'' для текущей позиции</font>
'''while'''('''true''')
'''if''' (pointer_in_next_M > M[i + 1].size && pointer_in_C > C[i].size)
pointer_in_next_M += 2
pointer_in_M++
last_non_alien = (!M[i][M[i].size].is_alien ? M[i][M[i].size] : NULL) <font color=green>// теперь это указатель на первый справа ''неподставной элемент'' для текущей позиции</font>
'''for''' j = M[i].size - 1 '''to''' 1
'''if ''' (M[i][j].is_alien)
M[i][j].right = last_non_alien
'''else'''
M[i][j].right = M[i][j + 1]
last_non_alien = M[i][j]
'''for''' i = 2 '''to''' k
cell = cell.left.down
'''if ''' (cell.right <= x) <font color=green>// Попытка сдвинуться к большему элементу </font> cell = cell.right '''if ''' (cell.right <= x) <font color=green>// Попытка сдвинуться к большему элементу </font> cell = cell.right <font color=green>// Замечание: по построению, если мы стоим в ''неподставном элементе'', то при сдвиге вправо мы можем оказаться в элементе любого типа</font> '''if ''' (cell.is_alien) <font color=green>// Для этого есть проверка </font>
cell = cell.left
ans[i] = cell.key
