Пример 3 Begin

Лабораторная работа № 15-16.

ТЕМА: Разработка алгоритмов и программ с использованием динамических структур данных.

ЦЕЛЬ РАБОТЫ:

1. Получить практические навыки по разработке программ с использованием динамических массивов.

2. Развивать абстрактное мышление.

ОТЧЕТ ДОЛЖЕН СОДЕРЖАТЬ:

1. Название и номер работы.

2. Цель работы.

3. Тексты задач.

4. Протокол выполнения программы.

5. Результаты работы программы.

КОНТРОЛЬНЫЕ ВОПРОСЫ.

1. Статическая память

2. Автоматическая память

3. Динамическая память

4. Динамическая память в языке Turbo Pascal

ЛИТЕРАТУРА:

1. В.Л.Kатков, Э.З.Любимский "Программирование." Минск "Вышэйшая школа." 1992г.

2. Ю.С.Бородич,А.H.Вальвачев,И.А.Kузьмич "Паскаль для персональных компьютеров." Минск "Вышэйшая школа." 1991г.

3. Г.И.Светозарова,А.А.Меньшиков,А.В.Kозловский "Практикум по программированию на языке Бейсик."

Москва "Hаука." 1988г.

Задание.

Вам предложены примеры динамических структур. Написать комментарии к данным примерам.

Задача 1.

Составить программу формирования стека, заполняющегося путем ввода целых положительных чисел с клавиатуры. Как только будет введено первое отрицательное число, содержимое стека выводится на экран. Данная программа выглядит следующим образом:

Program st;

Type Uk=^Stek;

Stek= record

I:integer;

A:Uk;

end;

Var

U1, U2:Uk; I1:integer;

Begin

{формирование стека}

U2:=Nil;

I1:=0;

While I1>=0 do

Begin

New(U1);

writeln('введите число'); read(I1);

U1^.I:=I1; U1^.A:=U2; U2:=U1

end;

{Вывод содержимого стека}

Repeat

writeln('элемент стека',U1^.I);

U2:=U1^.A;

Dispose(U1);

U1:=U2;

until (U1=Nil);

end.

Задача 2.

А)

Формирование очереди осуществляется с помощью следующей процедуры:

Procedure Form;

Label M;

Begin

write('1-й элемент:');

read(k); {Чтение первого элемента} {Пусть значение -32000 будет

признаком окончания процесса формирования очереди}

New(Ku); {Резервируется память под первый элемент очереди}

Ku^.P:=Nil; {Первый элемент не имеет ссылки}

Ku^.I:=K; {Занесение в очередь первого элемента}

Rw:=Ku;

Lw:=Ku;

while True do

Begin

write('i-й элемент:');

read(K); {Значение очередного элемента}

if K=-32000

then goto M;

New(Ku);

Lw^.P:=Ku;

Ku^.P:=Nil;

Ku^.I:=K;

Lw:=Ku

end;

M: writeln('Формирование очереди закончено')

end;

В данной процедуре Rw - указатель начала очереди, Lw - указатель конца очереди.

Б)

Удаление элемента из начала очереди производится с помощью следующей процедуры:

Procedure Ud;

Begin

T:=Rw;

Rw:=Rw^.P;

Dispose(T);

writeln('удален');

end;

В)

Процедура добавления элемента в конец очереди имеет вид:

Procedure Dob;

Begin

write('добавление элемента:');

read(k);

New(ku);

Ku^.P:=Nil;

Lw^.P:=Ku;

Ku^.I:=K;

Lw:=Ku;

writeln('Новый элемент помещен в очередь');

end;

С использованием вышеприведенных процедур раздел операторов основной программы имеет вид:

Begin

form;

Dob;

Ud;

{Печать очереди}

Repeat

writeln('элемент очереди',Rw^.I);

Ku:=Rw^.P;

Dispose(Rw);

Rw:=Ku;

until (Rw=Nil);

end.

Пример 3.

Рассмотрим программу транспонирования квадратной матрицы размера N*N:

Program Trans;

Type

Mas = array [1..2] of integer;

MasUk = array [1..2] of ^Mas;

Var

M:^MasUk;

N,I,J,R:integer;

Begin

{$R-}

writeln('введите размерность квадратной матрицы');

read(N);

GetMem(M,SizeOf(Mas)*N);

{Ввод матрицы}

For I:=1 to N do

Begin

GetMem(M^[I],2*N);

for J:=1 to N do

read(M^[I]^[J]);

end;

{Транспонирование матрицы}

for I:=1 to N do

if I<N

then for J:=I+1 to N do

Begin

R:=M^[I]^[J];

M^[I]^[J]:=M^[J]^[I];

M^[J]^[I]:=R;

end;

{Вывод результатов}

for I:=1 to N do

Begin

writeln;

for J:=1 to N do

write(M^[I]^[J],' ');

FreeMem(M^[I],2*N);

end;

FreeMem(M,SizeOf(Mas)*N); {$R+} End.