Курсовая работа: Распределение памяти

Когда исполнитель зайдёт в текущий узел второй раз он тоже самое проделает с указателем2. Это исполнитель будет проделывать до тех пор пока есть указатели ВПЕРЁД которыми он ещё не пользовался. А вот дополнительное однобайтовое поле (назовём его счетчик) как раз и пригодится для запоминание номера указателя которым ещё не пользовались.

Перед началом работы проинициализируем поле Счетчик всех узлов сети нулями. Затем каждый раз при входе в очередной узел будем увеличивать значение счётчика на 1. Тогда его значение будет определять номер неиспользованного указателя.

Рано или поздно исполнитель израсходует все указатели и попав в наш текущий узел в очередной раз обнаружит, что вперёд идти некуда, а стало быть нужно идти назад. Если исполнитель впервые пришел к такому выводу, то очевидно путь назад хранится в последнем указателе. Если исполнитель уже второй раз в данном узле решил идти назад, то адрес его пути хранится в предпоследнем указателе и т.д.

Иначе говоря

Идя вперёд исполнитель использует все указатели узла последовательно начиная с первого, занося в них адреса из указателя ОБРАТНО. Когда исполнитель идёт назад он использует указатели в обратном порядке. Относительно динамики изменения счётчика можно сказать, что пока в узле есть неиспользованные указатели вперёд, счётчик растёт (+1 на каждом шаге). Когда начинается движение назад, счётчик убывает (-1 на каждом шаге).

Аналогия с лабиринтом

Представьте себя в лабиринте в котором узлу соответствуют комнаты, а указатели это коридоры. Счетчик это некоторая доска на которой мы можем записывать число и кроме того у нас есть возможность соединять коридоры линиями. Чтобы корректно проверить весь лабиринт мы должны обойти все коридоры по порядку и на каждом шаге коридор из которого вошли в комнату соединять направленным отрезком с тем коридором в который собираемся уйти. А номер коридора в который идти мы будем определять по числу написанному на доске. Когда не останется ни одного не пройденного коридора, мы начиная с последнего и до первого будем выполнять следующее:

1. Выбираем очередной коридор.

2. Определяем, с каким коридором он связан (указатель ОБРАТНО) и уходим по нему.

Алгоритм

Тек_узел=Первый узел

Пока процес не завершён делать

Найти последний значимый указатель

Если номер указателя меньшего счётчика вхождений

То

Движение вперёд

Иначе

Движение назад

Движение вперёд

Вычислить номер неиспользованного указателя ВПЕРЁД

Увеличить значение счётчика вхождений

Запомнить текущий указатель ОБРАТНО в найденном неиспользованном указателе ВПЕРЁД

Указатель ОБРАТНО=адресу текущего узла.

Указатель на текущий узел=указателю с вычисленным номером

Движение назад

Определить значение указателя ОБРАТНО (хранится в последнем ненулевом указателе)

Указатель на текущий узел=указателю ОБРАТНО

Обнулить последний ненулевой указатель (определить его как указывающий в никуда)

Описание программы

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

В качестве сети используется массив записей содержащих массив указателей на узлы и счетчик вхождений. Дополнительное числовое поле нужно только для того, чтобы как-то показать присутствие исполнителя в узле, значение этого поля будет распечатываться когда исполнитель впервые зайдёт в узел. В качестве адреса узла используется его номер.

program example;

uses crt;