112
правок
Изменения
Добавлен псевдокод построения модифицированных массивов
<br> Для наглядности заведем таблицу, где в <tex>i</tex>-ой строке <tex> j </tex>-ая ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке.
<br>
Из-за необходимости хранения ссылок будет удобно завести структуру для хранения элементов в модифицированных каталогах.:
struct node :
element key
node *left, *right, *down
bool is_alien
Псевдокод построения модифицированных каталогов:
M[k] = C[k]
'''for''' i = k - 1 '''to''' 1
pointer_in_C = 1
pointer_in_next_M = 1
pointer_in_M = 1
last_non_alien = NULL
last_alien = NULL
'''while'''('''true''')
'''if''' (pointer_in_next_M > M[i + 1].size && pointer_in_C > C[i].size)
'''break'''
'''if''' (pointer_in_next_M > M[i + 1].size || M[i + 1][pointer_in_next_M] >= C[i][pointer_in_C])
M[i][pointer_in_M].key = C[i][pointer_in_C].key
M[i][pointer_in_M].key = last_alien
last_non_alien = M[i][pointer_in_M]
pointer_in_C++
'''else'''
M[i][pointer_in_M].key = M[i + 1][pointer_in_next_M].key
M[i][pointer_in_M].down = M[i + 1][pointer_in_next_M]
M[i][pointer_in_M].is_alien = '''true'''
M[i][pointer_in_M].left = last_non_alien
lst_alien = M[i][pointer_in_M]
pointer_in_next_M += 2
pointer_in_M++
last_non_alien = (!M[i][M[i].size].is_alien ? M[i][M[i].size] : NULL)
'''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]
=== Ответ на запрос ===
