Цель задания:
Получение навыков в задании переменных множественного типа и выполнении простейших операций над ними.
Знакомство с задачами, в которых целесообразно использовать переменные множественных типов.
Постановка задачи:
1. Ознакомиться с конечным и упорядоченным множеством символов.
2. Составить программу для одного из вариантов.
Содержание отчета:
1. Постановка задачи.
2. Текст программы.
3. Выводы.
Образец выполнения работы.
Лабораторная работа № 9, вариант № 3.
Работа с множественными типами данных.
Постановка задачи:
Ознакомиться с конечным и упорядоченным множеством символов.
Составить программу для одного из вариантов.
Методические указания:
Программа должна правильно работать для произвольного набора символов.
Вариант задания:
Дана непустая последовательность символов. Требуется построить и напечатать множество, элементами которого являются встречающиеся в последовательности:
19. знаки ‘%’ ,’!’ ,’?’ ,’$’, ’#’ и цифры от ‘1’ до ‘5’.
Текст программы:
Uses crt;
const
Length = 255;
var
m1,m2 : array [1..Length] of Char;
i,a : Integer;
Begin
ClrScr;
Randomize;
For i:=1 to Length do
m1[i]:=Chr(Random(255));
a:=1;
For i:=1 to Length do
Begin
Case m1[i] of
'%': Begin m2[a] := m1[i] Inc(a); End;
'!': Begin m2[a] := m1[i] Inc(a); End;
'?': Begin m2[a] := m1[i] Inc(a); End;
'$': Begin m2[a] := m1[i] Inc(a); End;
'#': Begin m2[a] := m1[i] Inc(a); End;
'1': Begin m2[a] := m1[i] Inc(a); End;
'2': Begin m2[a] := m1[i] Inc(a); End;
'3': Begin m2[a] := m1[i] Inc(a); End;
'4': Begin m2[a] := m1[i] Inc(a); End;
end;
End;
For i:=1 to Length do
Write(m2[i],' ');
ReadLn;
End.
Результаты работы:
| % 2 $ ! 5 5 5 5 |
Методические указания:
Программа должна правильно работать для произвольного набора символов.
Варианты заданий.
Дана непустая последовательность символов. Требуется построить и напечатать множество, элементами которого являются встречающиеся в последовательности:
1. цифры от ‘0’ до ‘9’.
2. буквы от ‘A’ до ‘F’ и от ‘X’ до ‘Z’.
3. буквы от ‘G’ до ‘N’ и цифры от ‘0’ до ‘9’.
4. знаки препинания.
5. буквы от ‘A’ до ‘Z’ и цифры от ‘0’ до ‘5’.
6. буквы от ‘T’ до ‘X’ и знаки препинания.
7. цифры от ‘5’ до ‘9’ и знаки арифметических операций.
8. знаки арифметических операций и знаки препинания.
9. цифры и знаки арифметических операций.
10. знаки препинания и буквы от ‘E’ до ‘N’.
11. знаки операций отношений.
12. цифры от ‘3’ до ‘9’, буквы от ‘A’ до ‘F’ и знаки препинания.
13. знаки арифметических операций и операций отношения.
14. буквы от ‘F’ до ‘M’ и знаки арифметических операций.
15. знаки препинания и операций отношения.
16. цифры от ‘6’ до ‘9’ и знаки операций отношения.
17. знаки арифметических операций и цифры от ‘2’ до ‘8’.
18. знаки ‘%’ ,’!’ ,’?’ ,’$’, ’#’, ’@’, ’&’ ,’*’.
19. цифры от ‘3’ до ‘7’ и знаки препинания.
20. знаки операций отношения и буквы от ‘A’ до ‘F’.
21. цифры от ‘4’ до ‘9’ , буквы от ‘G’ до ‘M’ и знаки ‘%’ ,’!’ ,’?’.
22. цифры от ‘4’ до ‘9’ и операции отношения.
23. цифры от ‘0’ до ‘8’ и знаки ‘&’,’#’,’@’.
24. знаки арифметических операций, цифры ‘2’и ‘5’, буквы ‘C’ до ‘H’.
Лабораторная работа № 10.
Операции над множествами.
Цель задания:
1. Получение навыков в организации ввода/вывода значений множественных типов.
2. Получение практических навыков в выполнении операций над множествами.
Постановка задачи:
Задан список объектов, включающий в зависимости от варианта названия ЭВМ или видов спорта. Известно, что в каждом институте имеется определенный набор вычислительных машин, а учащиеся каждой группы занимаются определенными видами спорта. Необходимо задать конкретные наборы ЭВМ (перечни видов спорта) для каждого института (каждой группы). Количество институтов(групп) указано в варианте.
Введя исходные данные, необходимо построить и распечатать множество, удовлетворяющее указанному в варианте условию.
Содержание отчета:
1. Постановка задачи для конкретного варианта.
2. Инструкция пользования программой.
3. Текст программы и результаты ее выполнения.
4. Выводы.
Образец выполнения работы.
Лабораторная работа № 10.
Операции над множествами.
Постановка задачи:
Задан список объектов, включающий в зависимости от варианта названия ЭВМ или видов спорта. Известно, что в каждом институте имеется определенный набор вычислительных машин, а учащиеся каждой группы занимаются определенными видами спорта. Необходимо задать конкретные наборы ЭВМ (перечни видов спорта) для каждого института (каждой группы). Количество институтов(групп) указано в варианте.
Введя исходные данные, необходимо построить и распечатать множество, удовлетворяющее указанному в варианте условию.
Варианты задания:
требуется построить и распечатать три множества : первое множество должно включать в себя ЭВМ, , имеющиеся во всех институтах; второе - ЭВМ, имеющиеся хотя бы в одном институте; третье - ЭВМ, которых нет ни в одном ин ституте(N=4).
Текст программы:
Program Sets;
Uses Crt;
Type
Comps = (i386, i486, Apple, Pentium, Acer, Macintosh);
TComps = set of Comps;
Const
All_comps : TComps = [i386, i486, Apple, Pentium, Acer, Macintosh];
Inst_1 : TComps = [i386,Acer, Pentium];
Inst_2 : TComps = [macintosh, Pentium];
Inst_3 : TComps = [Apple, Pentium ];
Inst_4 : TComps = [Pentium, Acer, i486];
Var
InAll, NoOne, InOne, All_Comps_In, NotInst_1,
NotInst_2, NotInst_3, NotInst_4 : TComps;
Flag : String;
Procedure OutPut(s : TComps);
Begin
If i386 in s then Write('i386 ');
If i486 in s then Write('i486 ');
If Pentium in s then Write('Pentium ');
If Apple in s then Write('Apple ');
If Acer in s then Write('Acer ');
If Macintosh in s then Write('Macintosh ');
End;
Begin
ClrScr;
All_Comps_In := Inst_1 + Inst_2 + Inst_3 + Inst_4;
NoOne := All_Comps - All_Comps_In;
Write('Comps not met in all VUZ: ');
OutPut(NoOne); WriteLn;
Write('Comps met in only one VUZ: '); OutPut(All_Comps_In-Inst_1-Inst_2-Inst_3);
OutPut(All_Comps_In-Inst_2-Inst_3-Inst_4);
OutPut(All_Comps_In-Inst_3-Inst_4-Inst_1);
OutPut(All_Comps_In-Inst_2-Inst_4-Inst_1);
WriteLn;
Write('Comps met in every VUZ: ');
NotInst_1 := All_Comps_In-Inst_1;
NotInst_2 := All_Comps_In-Inst_2;
NotInst_3 := All_Comps_In-Inst_3;
NotInst_4 := All_Comps_In-Inst_4;
OutPut(All_Comps_In-(NotInst_1 + NotInst_2 + NotInst_3 + NotInst_4));
While not KeyPressed Do;
End.
Результаты программы:
| Comps not met in all VUZ: Comps met in only one VUZ: i486 i386 Macintosh Apple Comps met in every VUZ: Pentium |
Варианты заданий.
Задано множество вычислительных машин, которыми может быть обеспечен институт: IBM-386, IBM-486, Pentium, Macintosh, APPLE, ACER. Известен набор машин, имеющихся в каждом институте. Количество институтов (N) указано в варианте:
1) требуется построить и распечатать множество, включающее в себя вычислительные машины:
· которыми обеспечены все институты (N=10).
· которые имеют хотя бы один институт.
· которых нет ни водном институте.
2) требуется построить и распечатать два множества:
· первое множество должно включать в себя ЭВМ, имеющиеся во всех институтах
второе - ЭВМ, имеющиеся хотя бы в одном институте(N=5).
· первое множество должно включать в себя ЭВМ, имеющиеся в одном институте; второе - ЭВМ, которых нет ни в одном институте(N=5).
· первое множество должно включать в себя ЭВМ, которых нет ни в одном институте; второе - ЭВМ, имеющиеся во всех институтах(N=5).
3) требуется построить и распечатать три множества :
· первое множество должно включать в себя ЭВМ, , имеющиеся во всех институтах;
· второе - ЭВМ, имеющиеся хотя бы в одном институте;
· третье - ЭВМ, которых нет ни в одном институте(N=4).
Министерство общего и профессионального образования РФ
Пермский государственный технический университет
Кафедра автоматизированных систем управления
Полякова О.А.
Методические указания для выполнения лабораторных работ по информатике для студентов специальности АСУ.
Часть 2.
Пермь 2001
Оглавление
9. Файловые типы данных................................................................................................................. 95
9.1. Инициализация файла.......................................................................................................... 95
9.2. Фалы и работа с ними............................................................................................................. 97
Лабораторная работа №11. Работа с внешними файлами................................................ 100
9.3. Сортировка файлов........................................................................................................... 105
9.3.1. Слияние упорядоченных последовательностей...................................................... 105
9.3.2. Сортировка сбалансированным слиянием.............................................................. 108
9.3.3. Сортировка простым слиянием............................................................................... 113
9.3.4. Сортировка естественным слиянием....................................................................... 120
9.3.5. Сортировка многофазным слиянием....................................................................... 131
Лабораторная работа №12. Сортировка файлов.................................................. 137
10. Динамическая память................................................................................................................ 142
10.1. Указатели.............................................................................................................................. 142
10.2. Списки................................................................................................................................... 144
Лабораторная работа № 13. Исключение элементов списка.............................................. 146
Лабораторная работа № 14. Работа со списками.............................................................. 154
Лабораторная работа № 15. Выполнение операций над списковыми структурами............ 170
10.3. Деревья................................................................................................................................ 174
10.4. Стеки, очереди...................................................................................................................... 181
Лабораторная работа № 16. Работа со стеками и очередями........................................... 191
11. Организация меню с использованием средств среды Turbo Pascal.......................................... 196
Лабораторная работа № 17. Составление меню................................................................. 197
Анкетные данные на абитуриентов..................................................................................................... 209
Файловые типы данных
Файл представляет собой произвольные последовательности элементов одного и того же типа, причём длина этих последовательностей заранее не определена, а конкретизируется в процессе выполнения программы. Этот тип значения получил в Паскале название файлового. Условно файл можно изобразить как некоторую ленту, у которой есть начало, а конец не фиксируется. Элементы файла записываются на эту ленту последовательно, друг за другом:
|
|
|
| |
где F- имя файла, а F1, F2, F3- его элементы.
В программировании существует несколько разновидностей файлов, отличающихся методом доступа к его компонентам. Мы рассмотрим простейший метод доступа, состоящий в том, что по файлу можно двигаться только последовательно, начиная с первого его элемента, и, кроме этого, всегда существует возможность начать просмотр файла с его начала. Таким образом, чтобы добраться до пятого элемента файла, необходимо, начав с первого элемента, пройти через предыдущие четыре элемента. Такие файлы называются файлами последовательного доступа, или последовательными файлами. Так что, например, невозможно прочитать 100-й элемент последовательного файла, не прочитав предыдущие 99.
Инициализация файла
Имя файла дает возможность программе работать одновременно с несколькими файлами, длина файла ограничивается только емкостью устройств внешней памяти.
Файловый тип или переменную файлового типа можно задать одним из трех способов:
<имя>=FILE OF <тип>;
<имя>=TEXT;
<имя>=FILE,
где <имя> - имя файлового типа,
FILE,OF - зарезервированные слова (файл, из);
TEXT - имя стандартного типа текстовых файлов.
От способа объявления можно выделить три вида файлов:
1. Типизированные файлы (задаются предложением FILE OF);
2. Текстовые файлы (тип TEXT);
3. Нетипизированные файлы (тип FILE).
Файлы, а также логические устройства, становятся доступны программе только после выполнения особой процедуры открытия файла(логического устройства). Эта процедура заключается в связывании ранее объявленной файловой переменной с именем существующего или вновь создаваемого файла, а также в указании направления обмена информацией: чтение из файла или запись в него.
Файловая переменная связывается с именем файла в результате обращения к стандартной процедуре ASSIGN:
ASSIGN(<ф.п.>,<имя файла или л.у.>);
здесь <ф.п.> - файловая переменная ( правильный идентификатор, объявленный в программе как переменная файлового типа);
<имя файла или л.у.> - текстовое выражение, содержащее имя файла или л.у.
Например:
Var: data:file of integer ; {задаём файловую переменную data содержащую целые числа типа integer}
begin
assign(data, ’ c:\tp\user. me ’); {связываем файловую переменную с существующим файлом или с файлом который будет создан}
end.
Инициировать файл означает указать для этого файла направление передачи данных. В TP можно открыть файл для чтения, для записи информации, и для чтения и записи одновременно.
Для чтения файл инициируется с помощью стандартной процедуры RESET:
RESET(<ф.п.>);
где <ф.п.> - файловая переменная, связанная ранее процедурой ASSIGN с уже существующим файлом.
Также можно обращаться к типизированным файлам, открытым процедурой RESET, с помощью процедуры REWRITE (для текстовых - нельзя).
Стандартная процедура:
REWRITE(<ф.п.>)
инициирует запись информации в файл, связанный ранее с файловой переменной. При выполнении этой процедуры старый файл уничтожается если таков был и создаётся новый файл.
Стандартная процедура:
APPEND(<ф.п.>)
инициирует запись в ранее существовавший текстовый файл для его расширения - эту процедуру можно использовать только для текстовых файлов.
CLOSE(<ф.п.>)
закрывает файл, но связь с <ф.п.> с именем файла сохраняется, при выходе из программы все файловые переменные задействованы процедурами RESET(<ф.п.>), REWRITE(<ф.п.>), APPEND(<ф.п.>), должны бать закрыты процедурой CLOSE(<ф.п.>).
ERASE(<ф.п.>)
уничтожение файла. Перед выполнением процедуры необходимо закрыть файл.
Например:
Var: data:file of integer ; {задаём файловую переменную data содержащую целые числа типа integer}
begin
assign(data, ’ c:\tp\user.me ’); {связываем файловую переменную с существующим файлом или с файлом который будет создан}
reset(data);
………….. {тело программы которая в своей работе }
………….. {использует данные записанные ранее в файл user.me }
…………..
…………..
close(data);
end.
Файлы и работа с ними
Для удобства описания действий над файлами введём понятие «окно файла» или просто «окно». Окно представляет позицию доступа, т.е. ту позицию файла, которая доступна для чтения в режиме чтения, либо для записи в режиме записи. Позиция файла, следующая за последней компонентой файла (или первая позиция пустого файла), помечается специальным маркером. Благодаря этому маркеру определяется конец файла.
Оператор RESET(F) или REWRITE(F) устанавливает файл с именем F в начальное состояние режима записи или чтения, в результате чего окно устанавливается на первую позицию файла.
После выполнения процедуры REWRITE(F) файл с именем F переходит в режим записи. Результат выполнения выглядит следующим образом:
| |
| |
| |
 | | ||
окно
Оператор WRITE(F, X) записывает в файл (в ту позицию, на которую указывает окно) очередную компоненту, содержащуюся в переменной X, после чего окно сдвигается на следующую позицию. Естественно тип переменной X должен совпадать с типом компонента файла F. Результат выполнения выглядит следующим образом:
X:=f1;
| |
| |
|
| | |||
| |
окно
X:=f2;
| |
|
|
| | |||
 |
окно
и так далее.
Запись в файл с помощью процедуры WRITE(F, X) можно производить только после выполнения процедуры REWRITE(F).
После выполнения процедуры RESET(F) файл с именем F переходит в режим чтения. Результат выполнения выглядит следующим образом:
|
|
|
| | | ||
окно
Оператор READ(F, X) читает из файла в переменную X (из той позиции, на которую указывает окно) очередную компоненту, после чего окно сдвигается на следующую позицию. Естественно тип переменной X должен совпадать с типом компонента файла F. Результат выполнения выглядит следующим образом:
|
|
|
| | |||
| |
Окно
X=f1;
|
|
|
| | |||
| |
окно
X=f2;
и так далее.
Чтение из файла с помощью процедуры READ(F, X) можно производить только после выполнения процедуры RESET(F).
При чтении из файла нужно определять, указывает ли окно на какую-то компоненту файла или указывает на маркер конца файла. Для определения этого факта в паскале введена в употребление стандартная логическая функция с именем EOF (от end of file), обращение к которой имеет вид eof(F).
Значение этой функции равно TRUE, если окно указывает на маркер конца файла с именем F, и значению FALSE в противном случае.
Недопустимо использовать процедуру READ(F, X) если eof(F)=TRUE.
Например:
Var: data:file of integer ; {задаём файловую переменную data содержащую целые}
x:integer ; {числа типа integer }
begin
assign(data, ’ c:\tp\user.me ’); {связываем файловую переменную с существующим }
reset(data); {файлом или с файлом который будет создан }
while not eof(data) {если не уверены что файл содержит данные сначала проверяем}
begin {а потом читаем }
read(data,x); {читаем все данные из файла до конца }
…………..
…………..
end;
close(data);
end.
или
Например:
Var: data:file of integer ; {задаём файловую переменную data содержащую целые}
x:integer ; {числа типа integer }
begin
assign(data, ’ c:\tp\user.me ’); {связываем файловую переменную с существующим }
reset(data); {файлом или с файлом который будет создан }
repeat
read(data,x); {читаем все данные из файла до конца }
…………..
…………..
until eof(data); {если уверены что файл содержит хоть одну компоненту, можно}
close(data); {сначала прочитать её в переменную X а потом проверить }
end.
Стандартная процедура чтения компоненты из файла READ(F, X) выполняет два действия: первое-это копирования компоненты файла в переменную X, а второе-это передвижение окна на следующую компонента. В некоторых задачах удобно иметь возможность производить эти два действия отдельно. Для таких случаев удобно использовать буферные переменные файлов.
Предположим, что файл F установлен в режим чтения. Тогда буферной переменной будем называть конструкцию F^, т.е. к имени файловой переменной справа приписывается символ ^. Эту переменную не надо описывать в разделе описания переменных, она определяется автоматически с введением в употребление файловой переменной. Тип буферной переменной совпадает с типом компоненты файла. Со значением этой буферной переменной можно выполнять любые действия, которые можно выполнять с любыми переменными.
В режиме чтения значение переменной F^ всегда является та компонента файла на которую указывает окно. При выполнении процедуры RESET(F) происходит не только установка окна на начало файла, но и присваивание значения первой компоненты файла буферной переменной:
|
|
|
| | | ||
окно
F^ = f1;
Для передвижения окна на следующую компоненту непустого файла предусмотрена процедура GET(F), параметром которой является имя файловой переменной. Результат этой процедуры состоит в передвижении окна на следующую позицию файла и присваиванием значения этой следующей компоненты буферной переменной.
В режиме записи буферная переменная выполняет роль поставщика значений компонент файла. Процедура PUT(F) производит запись в файл F в качестве очередной компоненты значение буферной переменной F^ и сдвигает окно на следующую позицию:
| |
| |
|
| | |||
 |
окно
F^:=f2; {присваиваем значение буферной переменной}
Get(F);
| |
|
|
| | |||
 |
окно
Лабораторная работа №11.
Работа с внешними файлами
Цель задания.
1. Ознакомление с возможностями организации файлов на внешних носителях в ЭВМ.
2. Получение навыков работы с внешними файлами.
Постановка задачи.
Подготовить данные об абитуриентах, поступающих в институт. Информацию о каждом абитуриенте оформить в виде записи, содержащей следующие поля:
1. ФИО.
2. Год рождения.
3. Год окончания школы.
4. Оценки в аттестате.
5. Признак - нуждается ли в общежитии.
6. Оценки вступительных экзаменов.
Разработать программу записи подготовленных данных во внешний файл и программу обработки созданного внешнего файла.
Удалить из внешнего файла все записи, удовлетворяющие условию, заданному в варианте, и распечатать записи , оставшиеся в файле.
Добавить N записей в начало(конец) внешнего файла и распечатать записи полученного файла согласно конкретному варианту.
Содержание отчета.
1. Постановка задачи.
2. Анкетные данные абитуриентов.
3. Тексты программ.
4. Распечатка результатов выполнения программы.
Методические указания.
При подготовке исходных данных необходимо учесть, что выходная информация программы обработки внешнего файла должна составлять не менее одной четверти от входной.
Образец выполнения задания.
Лабораторная работа №11, вариант № 5.
Работа с внешними файлами
Постановка задачи.
Подготовить данные об абитуриентах, поступающих в институт. Информацию о каждом абитуриенте оформить в виде записи, содержащей следующие поля:
1. ФИО.
2. Год рождения.
3. Год окончания школы.
4. Оценки в аттестате.
5. Признак - нуждается ли в общежитии.
6. Оценки вступительных экзаменов.
Разработать программу записи подготовленных данных во внешний файл и программу обработки созданного внешнего файла.
Удалить из внешнего файла все карточки иногородних студентов которым больше 18 лет, и распечатать записи оставшиеся в файле.
Добавить 4 записи в начало(конец) внешнего файла и распечатать список студентов не нуждающихся в общежитии.