Навигация
4.4 Вывод элементов дерева
Данная задача также может быть решена с помощью механизма рекурсии.
procedure PrintTree( Tree: Pointer);
var
ServiceVar: Assoc1;
begin
ServiceVar:= Tree;
writeln( ServiceVar^.Elem );
if ServiceVar^.Right <> nil then PrintTree(ServiceVar^.Right);
if ServiceVar^.Left <> nil then PrintTree(ServiceVar^.Left);
end;
Разберем решение типичной задачи, связанной с обработкой двоичных деревьев.
Текст задания
Описать процедуру copy( T, T1) которая строит T1 √ копию дерева T.
Решение
procedure CopyTree( T: Tree; var T1: Tree );
begin
if T= nil then T1:= nil
else
begin
new( T1 );
T1^.Elem:= T^.Elem;
CopyTree( T^.Left, T1^.Left );
CopyTree( T^.Right, T1^.Right )
end
end;
Глава II. Практическая часть
1-Задача 1. Программа «Калькулятор»
Постановка задачи. Составить программу калькулятор.
Листинг программы
program Kalkulator;
var
M:array[1..50] of string;
j,i,n:integer;
s,s1,s2,s3:string;
x,y:real;
begin
writeln('BBeDi OPeRAciy');
readln(s);
n:=length(s);
for i:=0 to n-1 do
begin
M[i]:=copy(s,i,1);
if (m[i]='+')or(m[i]='-')or(m[i]='*')or(m[i]='/') then j:=i;
end;
s1:=copy(s,0,j-1);
s2:=copy(s,j,1);
s3:=copy(s,j+1,n);
val(s1,x,n);
val(s3,y,n);
if s2='+' then writeln(x+y:4:1);
if s2='-' then writeln(x-y:4:1);
if s2='*' then writeln(x*y:4:1);
if s2='/' then writeln(x/y:4:1);
readln;
end.
Блок-схема
Пояснение к блок-схеме
| № блока | Назначение |
| 1 | Начало программы |
| 2 | Ввод/вывод данных |
| 3 | Выполнение операции N:=length(s) |
| 4 | Цикл i:=0 to n-1 |
| 5 | Тело цикла, выполнение операции M[i]:=copy(s,i,1) |
| 6 | Тело цикла, условие (m[i]=’+’) or (m[i]=’-‘) or (m[i]=’*’) or m[i]=’/’) |
| 7 | Тело цикла выполнение операции j:=i |
| 8 | Выполнение операции s1:=copy (s,o,j-1); s2:=copy (s,j,1); s3:=copy (s,j+1,n) |
| 9 | Выполнение операции val(s1,x,n); val(s3,y,n) |
| 10 | Блок условия s2=’+’ |
| 11 | Ввод/вывод данных x+y |
| 12 | Блок условия s2=’-‘ |
| 13 | Ввод/вывод данных x-y |
| 14 | Блок условия s2=’*’ |
| 15 | Ввод/вывод данных x*y |
| 16 | Блок условия s2=’/’ |
| 17 | Ввод/вывод данных x/y |
| 18 | Конец программы |
Протокол программы
BBeDi OPeRaciy
56*9
504,0
2-Задача2. Выполнить сортировку по латинскому алфавиту
Постановка задачи. Составить программу которая, сортирует буквы латинского алфавита по алфавиту.
Листинг программы
program Alfavit;
var
M:array[1..50] of string;
j,i,n:integer;
b:boolean;
s,tmp:string;
begin
writeln('BBeDu TekcT');
readln(s);
n:=length(s);
for i:=0 to n-1 do
begin
M[i]:=copy(s,i,1);
end;
b:=true;
while b do
begin
b:=false;
for i:=1 to n-1 do
begin
if m[i] > m[i+1] then
begin
tmp:= m[i];
m[i]:=m[i+1];
m[i+1]:=tmp;
b:=true;
end;
end;
end;
for i:=0 to n-1 do begin;
write(m[i],' ');
end;
readln;
end.
Блок-схема
Пояснение к блок-схеме
| № блока | Назначение |
| 1 | Начало программы |
| 2 | Ввод/вывод данных n:=length(s) |
| 3 | Цикл i:=0 to n-1 |
| 4 | Тело цикла M:=copy(s,i,1) |
| 5 | Выполнение операции b:=true |
| 6 | Выполнение операции b:=false |
| 7 | Цикл i:=1 to n-1 |
| 8 | Тело цикла, условие m[i]>m[i+1] |
| 9 | Выполнение операции tmp:=m[i]; m[i]:=m[i+1]; m[i+1]:=tmp; b:=true |
| 10 | Цикл i:=o to n-1 |
| 11 | Ввод/вывод данных m[i] |
| 12 | Конец программы |
Протокол программы
BBeDu TekcT
abrakadabra
aaaaabbdkr
Приложения
Рис. 1. Линейный список (связанный список)
Рис. 2. Двунаправленный список
Рис. 3. Однонаправленный циклический список.
Рис. 4. Двунаправленный циклический список.
Рис. 5. Организация дека на основе линейного списка.
Рис. 6. Организация стека на основе линейного списка.
Рис. 7. Представление бинарного дерева в виде списковой структуры.
Список литературыРапаков Г. Г. и Ржецукая С. Ю.. Turbo Pascal для студентов и школьников. BHV – С.-Петербург 2004
Меженный О. А. Turbo Pascal: учитель программирования. Диалектива 2001.
Культин Н.. Программирование в Turbo Pascal и Delphi. BHV 2003
Фаронов В. В. Turbo Pascal: учебное пособие. BHV
Похожие работы
... ссылочного типа: <задание ссылочного типа>::= ^<имя типа> ^ - признак ссылочного типа; <имя типа> - имя стандартного либо описанного ранее типа. Это тип динамических объектов, которые может представлять переменная ссылочного типа. Надо подчеркнуть , что здесь может быть только имя типа. Сами переменные ссылочного типа вводятся обычным образом. type массив = array ...
... ячейка, а имя переменной превращается в адрес ячейки. Появление этого адреса происходит в результате работы специального оператора языка (NEW), однако его значение в большинстве случаев не используется при программировании на алгоритмических языках типа Паскаль. Условимся считать, что адрес ячейки, которая будет хранить переменную А, есть А. Или, другими словами, А - это общее имя переменной и ...
... Закрыть программу можно нажатием на кнопку «Закрыть» или F10. Заключение В квалификационной работе мы попытались раскрыть более полно и наглядно понятие линейного списка, однонаправленного и двунаправленного списков, стека, дека и очереди. Сформировать и закрепить познавательный интерес к данной теме у учащихся. Выявлять и развивать творческие способности в использовании полученного навыка при ...
... "nсреднее целое равно " << MidInt / double(NMax) << "n"; cout << "среднее вещественное равно: " << MidReal / n << "n"; fclose(t); } Списки Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера. Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) ...
0 комментариев