AVR / 1_Uniproff / Doc2

Постановка задачи.

1. Описать список заданной организации.

Массив M должен содержать ссылки на предыдущий, следующий элемент (или только на следующий в однонаправленном списке), а также индекс элемента массива Х и значение К(размер элемента массива Х) если К не строго задано.

Получаются у нас массивы:

M:

• next, prev – это индексы для определения следующего/предыдущего элементов в самом массиве M

• K – текущий размер элемента в массиве X

• idX – индекс (ссылка) элемента в массиве X

Для наглядности – пример данных в массиве M:

(индекс) {prev,next,K,idX}

0. {-1,1,3,0}

1. {0,2,2,1}

2. {1,-1,0,2}

ссылка -1 – означает неопределенное значение (порог) – это либо первый элемент списка, либо последний. Однако, в кольцевом списке ссылки должны быть циклическими (наверное):

0. {2,1,3,0}

1. {0,2,2,1}

2. {1,0,0,2}

В этом случае где первый, а где последний элемент покажут лишь параметры самого списка.

X:

Сам массив Х состоит из элементов, каждый из которых это массив от 0 до K-1, например:

0. {1, 2, 3} при этом в массиве М, К будет равен 3

1. {3, 5} – M.K=2

2. {} – M.K=0

в круглых скобках обозначены индексы элементов массива X, ссылки на которые будут храниться в idX массива M. В этом примере элементы целого типа, но могут быть и составного (тип значения 5 – целое число + символ).

Таким образом, список у нас будет содержать параметры (свойства):

• firstM – индекс первого элемента в массиве M

• lastM – индекс последнего элемента в массиве M(и в массиве Х)

• SIZE – размер списка(кол-во элементов в списке)

• массив M

• массив X

Теперь перейдем непосредственно к заданию.

В программе на C++ (можно и без ++) предусмотреть функции:

1 – печати списка

2 – добавление нового элемента в конец списка

3 – поиска индекса N-го элемента списка в массиве X

4 – удаление N-го элемента списка

5 – сборка мусора

6 – выполнение особого «волшебного» действия, как то:

• Добавление в список нового элемента после N-го

• Перестановка N-го и (N+1) элементов

• Замена содержимого N-го элемента на новые значения

Не скажу что все это просто, но у нас есть некоторые наработки в паскале, которые должны помочь. Для нас нет ничего невозможного и мы выполним все 6 пунктов задачи.

Теперь конкретнее. Вид нашего списка мне представляется например вот таким:

В начале, когда идет последовательное заполнение картинка выглядит таким образом (заполнено 5 элементов списка – желтые ячейки). Первый элемент содержит последовательность из 3-х значений (синие ячейки), второй – из двух, и т.д., пятый из 0 значений – нельзя и такой вариант упускать из виду. Каждый элемент массива М ссылается на элемент массива Х (стрелочки).

Далее, мы удаляем, например элементы 1 и 3 – серые ячейки (если считать от нуля):

При этом физически они не затираются, а изменяются только ссылки в элементе M: prev, next, а также SIZE списка. Если же будет удален один из крайних элементов, то нужно еще корректировать и firstM/lastM в зависимости от того, первый удален или последний.

Надеюсь ты уже в курсе этого по опыту прошлых лаб.

Серые элементы, которые физически остались в памяти, а логически были исключены из списка называются МУСОР (ни мент, ни фараон, а именно «мусор»!)

Идем далее. Ежели мы вот так удалили 2 элемента, список у нас (как видно из рисунка) максимум на 10 элементов, то еще 7 элементов мы можем вроде как вставить, не так ли? Однако свободной памяти у нас осталось только на 5 элементов! Вот тебе, приятель, и Прага, вот тебе, дружок, и Варшава… что остается нам делать ?

Для начала заполнить оставшихся 5 элементов:

Готово! Пусть пока нас не интересует сколько там голубых ячеек должно быть заполнено 

А вот теперь, когда вся память занята и данными и мусором, нам нужно «вынести мусор».

Алгоритм выноса мусора (вот ведь бывает же такой бред ) приведен в «рекомендации по уборке жилых помещений»… «рекомендации по алгоритму сборки мусора». Наверное логично так. Это в самом задании к задаче №2.

Че-то меня клинит уже от описания как Бандерлогина-Бочковского… Короче говоря, мусор нужно убирать (в соответствии с рекомендацией) в 2 этапа.

1 этап – ищем пропуски в массиве M и сдвигаем его элементы, чтобы освободить в конце массива ячейки, при этом ссылки на элементы массива X – остаются прежними:

2 этап – поступаем аналогично с массивом X, и корректируем ссылки idX в массиве M.

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