Лекция: Методические указания к домашней работе № 4
Приведем в качестве примера работы со списками программу, которая вводит с терминала названия учебников (последнее название является фиктивным, оно характеризует конец списка и состоит из десяти букв Я), динамически отводит место в памяти под каждое название и строит из них связанный список, упорядоченный по алфавиту. По окончании формирования каталог книг выводится на терминал. Использование списковых структур при решении подобных задач имеет определенные преимущества: исключает предварительное резервирование памяти, дает возможность сортировать (упорядочивать список одновременно с вводом), позволяет упрощать дальнейшую работу с данными, например, достаточно просто реализовать операции удаления и вставки новых элементов. Такой упорядоченный список можно переписать во внешний файл для долговременного хранения.
Program список (input,output);
Type Назв=packed array[1..10] of char;
Ссылка=^элемент;
Элемент=record
сс: Ссылка; Дан: Назв;
end;
Var Книга: Назв;
нач, тек, об, обпр: Ссылка;
I: integer
Begin {формирование 1-го элемента списка}
New (нач);
Writeln (‘Вводите первое название’);
For i:=1 to 10 do read (книга[i]);
нач^cc:=nil;
нач^.дан:=книга;
{ формирование списка }
While книга<>’ЯЯЯЯЯЯЯЯЯЯ’ do
begin
Тек:=нач; i:=i+1;
New (об);
Writeln (‘вводите очередное название’)
For i:=1 to 10 do Read (книга[i]); { Поиск подходящего места }
While (Тек <> NIL) and (Тек^.дан<книга) do
begin Обпр:=тек; Тек:= Тек^.сс; end;
{ Вставка нового элемента }
об^.сс:= Тек;
об^.дан:= книга;
if Тек =нач then нач:=об else Обпр^cc:=об;
end;
{ Вывод на терминал упорядоченного каталога книг }
writeln (‘Каталог учебников: ’);
Тек:=нач;
While Тек^.cc < > NIL do
Begin Writeln (Тек^.дан); Тек:= Тек^.cc; end;
Dispose(нач);
End.
В начале программы формируется первый элемент списка и задается значение начального указателя НАЧ. Затем, пока не будет введено название учебника состоящего из десяти букв Я, под каждое вводимое название динамически отводится место в памяти оператором NЕW, после чего просматривается список с самого начала до те пор, пока не будет найдена соответствующая позиция для нового элемента или не будет достигнут конец списка. В найденное место вставляется новый элемент списка. В конце программы упорядоченный список распечатывается.
Протокол работы программы:
ВВОДИТЕ ПЕРВОЕ НАЗВАНИЕ
МАТЕМАТИКА
ВВОДИ ОЧЕРЕДНОЕ НАЗВАНИЕ
АЛГЕБРА
ВВОДИ ОЧЕРЕДНОЕ НАЗВАНИЕ
ФИЗИКА
ВВОДИ ОЧЕРЕДНОЕ НАЗВАНИЕ
ЯЯЯЯЯЯЯЯЯЯ
КАТАЛОГ УЧЕБНИКОВ:
АЛГЕБРА
МАТЕМАТИКА
ФИЗИКА
Данная программа правильно работает на тех ЭВМ, на которых множество русских букв упорядочено по алфавиту. В противном случае операции отношения над строками, содержащими русские буквы, дают неправильный результат. Для реализации операций отношения в соответствии с русским алфавитом на таких ЭВМ необходимо создавать вспомогательное программное обеспечение. Этот вопрос выходит за рамки данного учебного пособия.
Варианты заданий
Для конкретного варианта составить входную информацию. Разработать программу, которая обеспечивает последовательное занесение информации в однонаправленный список с одновременным упорядочением по указанному в варианте признаку. По окончании формирования списка распечатать его.
1. Составить список учебников для N-го курса, указав название, фамилию автора, год издания, цену, тираж и упорядочить его по заданному признаку.
№ курса Название поля
I. Фамилия автора
II. Название
III. Год издания
IV. Цена
V. Тираж
2. Составить список кабинетов техникума для М этажа, указав название кабинета, номер комнаты, количество посадочных мест и упорядочить его по заданному признаку.
№ этажа Название поля
I. Название кабинета
II. Номер комнаты
III. Количество мест