Алгоритм

Укрупненные шаги алгоритма основной программы приведены под заголовком "содержание программы" (при оформлении отчета, алгоритмы следует включить в блок-схему программы). Рассмотрим строение процедур.

Добавление записи в дек. Исходя из схемы дека, приведенной на рис. 20, будем считать его пустым, если в нем нет ни одной записи, то есть указатели начала и конца дека указывают на nil. Если запись добавляется в пустой дек, то меняются оба указателя, если в непустой – меняется только один указатель (начала или конца). Проверку, что дек пуст, можно выполнять по содержимому любого указателя (nil или нет). Добавление записей к обоим концам выполняется почти одинаково: создается динамическая переменная типа звена дека, заполняется ее информационная часть, обе ссылки на соседние звенья делаются равными nil. Затем, в зависимости от того, к какому концу добавляется запись, меняется первая ссылка в новой записи (прицепляясь к деку) и вторая ссылка в концевой записи дека (связываясь с новой записью) или наоборот – вторая ссылка новой записи и первая ссылка конца дека. Наконец меняется указатель конца дека к которому добавлена запись.

Удаление записи из дека. В задаче требуется выбирать данные из дека с одной стороны, но для универсальности, составим процедуру выбора и удаления с заказанного конца дека. Как и в предыдущей процедуре, будем использовать логический параметр, равный истине, при работе с началом и лжи, при работе с концом дека. Если начало и конец ссылаются на одну и ту же область памяти (равны между собой), то при удалении записи дек становится пустым. Если нет, процесс выполняется в обратном порядке, по сравнению с добавлением записи.

Заполнение дека из текстового файла. Представляет собой цикл (пока не достигнут конец файла) чтения очередной строки текстового файла с заполнением информационной структуры, которую либо добавляют к началу дека (обе оценки – 5), либо к концу (обе оценки – 3), либо просто пропускают. Внутри цикла используются процедуры ввода одной строки и добавления записи в дек. При заполнении дека ведется подсчет количества записей дека.

Распечатка дека в выходной текстовый файл. Так как количество записей дека известно, вывод выполняется в форме арифметического цикла. Тело цикла содержит обращение к процедуре выбора записи из дека (из начала) и форматного вывода данных в выводной файл в виде строки таблицы.

При составлении блок-схем алгоритмов в отчете по лабораторной работе можно пользоваться именами переменных, описания которых предварительно заданы в таблице идентификаторов основной программы и подпрограмм.

Примечание: формальные параметры, передаваемые по имени (которым предшествует ключевое слово var), являются, по сути, указателями на данные, поэтому занимают в памяти по 4 байта, независимо от типа данных, на которые указывают.

Таблица идентификаторов

Таблица 32. Идентификаторы программы 31 варианта

Имя Тип Р-р, байт Назначение
Основная программа
Lab_9 имя программы - Работа с динамическими списками
data описатель - Описатель типа для структуры данных
.Name строка Поле структуры данных для фамилии
.Bal1 целое Поле структуры данных для первой оценки
.Bal2 целое Поле структуры данных для второй оценки
.SrBal вещественное Поле структуры данных для средней оценки.
Pd описатель - Описатель типа для указателей на звено дека
Dek описатель - Описатель типа для структуры данных записи дека
P1 указатель Ссылка на следующий элемент дека
P2 указатель Ссылка на предыдущий элемент дека
Student структура Структура – составное поле данных записи дека
Docum структура Данные одной записи
DN указатель Указатель первого конца дека (начала)
DK указатель Указатель второго конца дека (конца)
Fin последовательн. символьн. файл Входной текстовый файл с данными
Fout последовательн. символьн. файл Выходной текстовый файл с таблицей результатов
k целое Количество элементов дека
GetStud – процедура выбора строки из входного файла
St указатель на структуру Формальный параметр - адрес структуры с данными по студенту
F указатель на файл Формальный параметр - имя входного файла
P целое Счетчик пробелов во входной записи
i целое Порядковый № символа во входной записи
PutDek Процедура формирования нового звена дека
NK указатель Формальный параметр - адрес конца дека, к которому добавляют запись
KN указатель Формальный параметр - адрес второго конца дека
Inf структура Формальный параметр – добавляемые данные
Beg логическое Признак, что добавляется к началу
U указатель Вспомогательный указатель на добавляемое звено дека
DelDek Процедура удаления крайнего звена дека
NK указатель Формальный параметр - адрес конца дека, у которого удаляют запись
KN указатель Формальный параметр - адрес второго конца дека
Inf указатель на структуру Формальный параметр – адрес структуры, куда поместить выбираемые данные
Beg логическое Признак, что удаляется из начала
U указатель Вспомогательный указатель на удаляемое звено дека
ReadFile Процедура чтения записи из файла и заполнения дека
F указатель на файл Формальный параметр – указатель на входной файл для входных данных
DekN указатель Формальный параметр - адрес указателя на начало дека
DekK указатель Формальный параметр - адрес указателя на конец дека
N указатель Формальный параметр - адрес переменной для числа элементов дека
Stud структура Рабочая структура для данных о студенте

Разработанный алгоритм с использованием перечисленных идентификаторов реализуется на языке Турбо-Паскаль приведенной ниже программой.