Лабораторная работа n 13 Изучение методов работы с односвязными и двусвязными линейными списками.
ЦЕЛЬ РАБОТЫ.
Изучить средства языка ПАСКАЛЬ для организации динамических структур данных, знать способы выполнения основных операций над списочными структурами данных и освоить основные приемы реализации списочных структур данных на языке ПАСКАЛЬ.
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
- Разработать алгоритм решения задачи;
- Подготовить исходные данные, подлежащие организации в виде списочной структуры;
- Составить таблицу символических имен (идентификаторов).
- Составить программу на языке ПАСКАЛЬ.
- Hабрать текст программы на ПЭВМ, отладить и решить задачу на ПЭВМ;
- Распечатать текст программы и результаты решения;
- Оформить отчет.
Отчет должен содержать:
1. Hаименование и номер лабораторной работы;
2. Условие задачи;
3. Описание метода решения задачи;
4. Таблица имен (идентификаторов). Для записей (объектов) должны быть указаны имена полей;
5. Схема алгоритма решения задачи;
6. Распечатка (или рукопись) программы решения задачи;
7. Распечатка результатов решения задачи;
8. Выводы по результатам решения задачи, анализ ошибок, выявленных в ходе отладки программы.
Варианты заданий и условия задач.
Разработать программу реализующую заданную списочную структуру данных. Заданные действия (инициализация, создание структуры данных, и т. п.) должны быть оформлены в виде отдельных процедур или функций. Память под очередной элемент списка должна выделяться динамически. Выполнение действий по обслуживанию списочной структуры должно осуществляться в режиме диалога с пользователем.
Варианты заданий приведены в таблице 13.1.
Варианты структурных схем списочных структур приведены на рисунке 13.1.
Обозначения, принятые в структурных схемах:
D – Поле данных; тип данных указан в варианте задания;
K – Поле ключа, представляющее собой дополнительное поле элемента списка, заполняемое уникальным значением. Предлагается содержимое его выбрать самостоятельно, в зависимости от типа данных в поле D. Возможные варианты: номер элемента в списке (например, номер студента в списке группы), номер элемента при его создании, и т. п.;
Next – указатель на следующий элемент списка;
Prev – указатель на предыдущий элемент списка;
NIL – пустой (нулевой) указатель, использующийся в том случае, если для конкретного списка отсутствуют последующий или предыдущие элементы.
|
Варианты заданий Таблица 5.1. |
|||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
N п/п |
Вариант структуры / тип данных |
Соз-дание пусто-го списка |
Добавление элемента в список |
Вывод списка на дисплей (или принтер) |
Удаление элемента из списка |
Запись списка в файл |
Унич-тоже-ние списка |
Чтение списка из файла |
|
|||||||||||
В на-чало |
В ко-нец |
После элемента с заданным |
Номер элемен-та |
Содержимое поля |
Значение указателя на |
Из начала |
Из конца |
С заданным |
|
|||||||||||
Номе-ром |
Клю-чом |
|
||||||||||||||||||
Номе-ром |
Клю-чом |
|
||||||||||||||||||
Дан-ных |
Клю-ча |
Следую-щий |
Преды-дущий |
|
||||||||||||||||
элемент |
|
|||||||||||||||||||
1 |
A / string[8] |
+ |
+ |
+ |
+ |
|
+ |
+ |
|
+ |
|
|
|
+ |
|
+ |
+ |
+ |
|
|
2 |
B / integer |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
+ |
+ |
+ |
|
|
3 |
C / real |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
|
4 |
D / LongInt |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
|
5 |
E / char |
+ |
|
+ |
+ |
|
|
+ |
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
6 |
F / string[6] |
+ |
|
+ |
+ |
+ |
|
+ |
+ |
|
|
|
|
|
+ |
|
|
|
|
|
7 |
C / word |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
|
8 |
D / integer |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
|
9 |
A / real |
+ |
+ |
+ |
+ |
|
|
+ |
|
+ |
|
|
+ |
+ |
|
+ |
+ |
+ |
|
|
10 |
B / LongInt |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
+ |
+ |
+ |
|
|
11 |
F / char |
+ |
|
+ |
+ |
|
|
+ |
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
12 |
E / word |
+ |
|
+ |
+ |
+ |
|
+ |
+ |
|
|
|
|
|
+ |
|
|
|
|
|
13 |
B / string[9] |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
+ |
+ |
+ |
|
|
14 |
A / integer |
+ |
+ |
+ |
+ |
|
|
+ |
|
+ |
|
+ |
|
+ |
|
+ |
+ |
+ |
|
|
15 |
E / real |
+ |
|
+ |
+ |
|
|
+ |
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
16 |
F / LongInt |
+ |
|
+ |
+ |
+ |
|
+ |
+ |
|
|
|
|
|
+ |
|
|
|
|
|
17 |
C / char |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
|
18 |
D / string[5] |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
|
19 |
A / string[3] |
+ |
|
+ |
+ |
|
+ |
+ |
|
+ |
|
+ |
|
+ |
|
+ |
+ |
+ |
|
|
20 |
C / integer |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
|
21 |
B / real |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
+ |
+ |
+ |
|
|
22 |
E / LongInt |
+ |
|
+ |
+ |
+ |
|
+ |
+ |
|
|
|
|
|
+ |
|
|
|
|
|
23 |
D / char |
+ |
|
+ |
+ |
|
|
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
|
24 |
F / byte |
+ |
|
+ |
+ |
|
|
+ |
+ |
|
+ |
|
|
|
+ |
|
|
|
|
|
25 |
A / LongInt |
+ |
|
+ |
+ |
|
+ |
+ |
|
+ |
|
|
+ |
+ |
|
+ |
+ |
+ |
|