Текст программы

Алгоритм

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

Добавление записи в дек. Исходя из схемы дека, приведенной на рис. 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	структура		Рабочая структура для данных о студенте

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

Program Lab_9;

{ Программа Лабораторной работы N 9

Динамические переменные. Списки.

Вариант N 31.

А.Я.Умненькая, ст. гр. Я-007}

TYPE data = record {описатель структуры данных студента}

Name: string[15]; { поле для Фамилии И.О.}

Bal1,Bal2: integer; {поля баллов за 2 семестра}

SrBal: real; {поле для среднего балла }

end;

Pd=^Dek; {описатель указателей на вершины дека}

Dek= record { описатель звена дека}

P1:Pd; {поле указателя следующего звена от начала}

P2:Pd; {поле указателя следующего звена от конца }

Student: data; { поле данных студента}

end;

VAR

Docum: data; {рабочая структура данных о студенте }

DN,DK: Pd; { указатели на начало и конец дека }

Fin,Fout:text; {Файлы входных данных и результатов работы}

k:integer; { количество элементов дека}

Procedure GetStud(Var F:text; var St:data);

{процедура чтения одной записи файла и формирования данных студента}

Var

P,i:integer;

Begin

i:=0;

P:=0;

St.Name:='---------------'; поле фамилии заполняем строкой из прочерков максимальной длины

while P<2 do {пока не прочтем второй пробел }

begin

inc(i);

read(F,St.Name[i]); {читаем из файла по символу в поле имени }

if St.Name[i]=' ' then P:=P+1; { подсчет пробелов}

end;

St.Name:=Copy(St.Name,1,i); { Из полной строки поля фамилии вырезаем подстроку по второй пробел (включительно) и заносим обратно в поле фамилии }

readln(F,St.Bal1,St.Bal2,St.SrBal); { остаток записи файла читаем в поля оценок }

End;

Procedure PutDek(Var NK,KN:Pd; Inf:data; Beg:boolean);

{процедура добавления элемента в дек с заказанного конца}

Var U:Pd;

Begin

New(U);

U^.Student:=Inf;

U^.P1:=nil;

U^.P2:=nil;

if NK=nil then { если дек перед этим был пуст }

KN:=U

else

if Beg then { если добавляем в начало }

begin

U^.P1:=NK;

NK^.P2:=U;

end

else { если добавляем в конец }

begin

U^.P2:=NK;

NK^.P1:=U;

end;

NK:=U;

End;

Procedure DelDek(Var NK,KN:Pd; var Inf:data; Beg:boolean);

{процедура выбора элемента из заказанного конца дека }

Var U:Pd;

Begin

U:=NK;

Inf:=U^.Student;

if NK=KN then { если в деке был всего один элемент}

begin { делаем дек пустым}

KN:=nil;

NK:=nil;

end

else

if Beg then { если удаление из начала }

begin

NK:=U^.P1;

NK^.P2:=nil;

end

else { если удаление из конца }

begin

NK:=U^.P2;

NK^.P1:=nil;

end;

Dispose(U); { собственно освобождение памяти от элемента }

End;

Procedure ReadFile(Var F:text; Var DekN,DekK:Pd; var N:integer);

{ чтение файла с заполнением дека }

Var

Stud:data;

Begin

N:=0;

While Not Eof(F) do

begin

GetStud(F,Stud);

N:=N+1;

if (Stud.Bal1=5) and (Stud.Bal2=5) then

PutDek(DekN,DekK,Stud,TRUE)

else

if (Stud.Bal1=3) and (Stud.Bal2=3) then

PutDek(DekK,DekN,Stud,FALSE)

else { если данные не заносим в дек }

N:=N-1;

end;

End;

Procedure WriteFile(Var F:text; Var NK,KN:Pd; N:integer);

{ процедура распечатки дека в выводной файл с удалением дека}

Var

i:integer;

Stud:data;

Begin

Writeln(F,'|--------------------------------------',

'--------------|');

Writeln(F,'| N | Фамилия И.О. | 1-й балл | 2-й ',

'балл | Ср.балл |');

For i:=1 to N do

begin

Writeln(F,'|---|----------------|----------|----',

'------|---------|');

DelDek(NK,KN,Stud,TRUE);

WriteLn(F,'|',i:2,' | ',Stud.Name:15,'|',Stud.Bal1:6,

' |',Stud.Bal2:6,' |', Stud.SrBal:6:1,' |');

end;

Writeln(F,'|--------------------------------------',

'--------------|');

End;

BEGIN { ОСНОВНАЯ ПРОГРАММА }

Assign(Fin,'Dan.txt');

Reset(Fin);

Assign(Fout,'Umnik9.res');

ReWrite(Fout);

DN:=nil;

DK:=nil;

k:=0;

ReadFile(Fin,DN,DK,k);

Close(Fin);

With Docum do

begin

Bal1:=k;

Bal2:=0;

SrBal:=0.0;

Name:='Список типа S0D';

end;

PutDek(DN,DK,Docum,TRUE); { добавление в начало дека записи со сводной информацией. }

DelDek(DN,DK,Docum,TRUE); {Выбор из дека сводной информации для печати }

Writeln(Fout, Docum.Name:20,' из ',Docum.Bal1,' строк');

WriteFile(Fout,DN,DK,k); {печать дека в файл с удалением элементов дека}

close(Fout);

End.

Варианты заданий

Таблица 33. Варианты заданий лабораторной работы № 9

№ вар.	Требования к записям, выбираемым из файла и помещаемым в список	Тип Списка	Файл данных
	Средний балл выше 3	S2KI	dan.dat
	Отличные оценки во всех полях	S2KO	dan.txt
	Первые буквы фамилий А, Б, В	S0S	dan.dat
	Оценки во всех полях ниже 4 баллов	S0O	dan.txt
	Первая оценка выше 3	S1L	dan.dat
	Первая или вторая оценка выше 3	S1KI	dan.txt
	Первая оценкой ниже 5, а вторая выше 3	S1KO	dan.dat
	Первые буквы фамилий А, В, Е и средние оценки выше 3	S2L	dan.txt
	Оценки 3 во всех полях оценок	S2KI	dan.dat
	Средние оценки выше 3 баллов	S2KO	dan.txt
	Вторая оценка выше 4, а первая выше 3 баллов	S0S	dan.dat
	Первая и вторая оценки выше 4 баллов	S0O	dan.txt
	В начало –со средней оценкой <4 балла, в конец – прочие	S0D	dan.dat
	Первые буквы фамилий А, Б, В и средние оценки выше 4	S1L	dan.txt
	Вторые и средние оценки выше 4 баллов	S1KI	dan.dat
	Первая оценка выше 3 баллов, а средняя оценка выше 3,5	S1KO	dan.txt
	Все оценки не ниже 4 баллов	S2L	dan.dat
	Вторая и средняя оценки выше 4 баллов	S2KI	dan.txt
	Средняя оценка выше 3,5 баллов	S2KO	dan.dat
	Средняя оценка ниже 4,5 и фамилии начинаются с букв А и В	S0S	dan.txt
	Средняя оценка выше 4 баллов и фамилии, начинаются с букв от А до К	S0O	dan.dat
	В начало – если первая оценка 3, в конец – если первая – 5	S0D	dan.txt
	Первая оценка выше 3 балов, а средняя оценка 4 балла	S1L	dan.dat
	Все оценки выше 4 и фамилии начинаются с букв А - Е	S1KI	dan.txt
	Первая и средняя оценки выше 4 баллов	S1KO	dan.dat
	Все оценки ниже 5 баллов	S2L	dan.txt
	Первая или вторая оценка выше 4 баллов	S2KI	dan.dat
	Первая или средняя оценки ниже 4 баллов	S2KO	dan.txt
	Средняя оценка выше 4 баллов	S0S	dan.dat
	Все оценки выше 4 или фамилии начинаются с букв А - Е	S0O	dan.txt
	В начало – только с пятерками, в конец – только с тройками	S0D	dan.txt

Литература

1. Бородич Ю.С., Вальвачев А.Н., Кузьмич А.И. Паскаль для персональных компьютеров: Справочне пособие. Минск: "Вышейшая школа", 1991.
2. Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0 (третье издание). М.: "Диалог-МИФИ", 1996.
3. Немнюгин С.А. Turbo Pascal: практикум. СПб.: Питер, 2001.
4. Кнут Д. Искусство программирования для ЭВМ. /Пер. с англ.: В 3-х томах. т.3. Сортировки и поиск. М.: Мир, 1976.
5. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся ВТУЗов (Изд. 13-е). М.: "Наука", 1986.

Приложение А.
Система меню и команды Турбо-Паскаля

Дата добавления: 2017-02-01