ДИНАМИКА
(ЛАБОРАТОНАЯ РАБОТА №1)
Выполнила:
студентка 141 группы
математического факультета
Пухова Ю.И.
Проверила:
Швалева О. В.
Пермь
ГЛАВА 1 КРАТКАЯ ТЕОРИЯ
СПИСКИ
Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.
Каждый элемент связанного списка, во-первых, хранит какую-либо информацию, во-вторых, указывает на следующий за ним элемент. Так как элемент списка хранит разнотипные части (хранимая информация и указатель), то его естественно представить записью, в которой в одном поле располагается объект, а в другом – указатель на следующую запись такого же типа. Такая запись называется звеном, а структура из таких записей называется списком или цепочкой.
Лишь на самый первый элемент списка (голову) имеется отдельный указатель. Последний элемент списка никуда не указывает.
Описание списка
Пример описания списка
Type ukazat= ^ S;
S= record
Inf: integer;
Next: ukazat;
End;
В Паскале существует основное правило: перед использованием какого-либо объекта он должен быть описан. Исключение сделано лишь для указателей, которые могут ссылаться на еще не объявленный тип.
Формирование списка
Чтобы список существовал, надо определить указатель на его начало.
Пример описания списка
Type ukazat= ^S;
S= record
Inf: integer;
Next: ukazat;
End;
Создадим первый элемент списка:
New (u); {выделяем место в памяти}
u^. Next:= nil; {указатель пуст}
u^. Inf:=3;
Продолжим формирование списка. Для этого нужно добавить элемент либо в конец списка, либо в голову.
А) Добавим элемент в голову списка. Для этого необходимо выполнить последовательность действий:
получить память для нового элемента; поместить туда информацию; присоединить элемент к голове списка.
New(x);
Readln(x^.Inf);
x^. Next:= u;
u:= x;
Б) Добавление элемента в конец списк а. Для этого введем вспомогательную переменную, которая будет хранить адрес последнего элемента. Пусть это будет указатель с именем hv (хвост).
x:= hv;
New(x^. next); {выделяем память для следующего элемента}
x:= x^.next;
x^.next:= nil;
x^. inf:= 5;
hv:=x;
Просмотр списка
While u<> nil do
Begin
Writeln (u^.inf);
u:= u^.next;>
end;
Удаление элемента из списка
А) Удаление первого элемента. Для этого во вспомогательном указателе запомним первый элемент, указатель на голову списка переключим на следующий элемент списка и освободим область динамической памяти, на которую указывает вспомогательный указатель.
x:= u;
u:= u^.next;
dispose(x);
Б) Удаление элемента из середины списка. Для этого нужно знать адреса удаляемого элемента и элемента, стоящего перед ним. Допустим, что digit – это значение удаляемого элемента.
x:= u;
while (x<> nil) and (x^. inf<> digit) do
begin
dx:= x;
x:= x^.next;
end;
dx:= x^.next:
dispose(x);
В)Удаление из конца списка. Для этого нужно найти предпоследний элемент.
x:= u; dx:= u;
while x^.next<> nil do
begin
dx:= x; x:= x^.next;
end;
dx^.next:= nil;
dispose(x);
Прохождение списка. Важно уметь перебирать элементы списка, выполняя над ними какую-либо операцию. Пусть необходимо найти сумму элементов списка.
summa:= 0;
x:= u;
while x<> nil do
begin
summa:= summa+ x^.inf;
x:= x^.next;
ДВОИЧНОЕ ДЕРЕВО
Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.
В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.
Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень.
Представим себе генеалогическое дерево, корень которого - имя человека, на следующем уровне - имена его родителей, еще на следующем - имена родителей и их родителей и т.д. Такая структура называется двоичным деревом, рис. 1.36.
Рис. 1.36. Структура типа «двоичное дерево»;
пара ближайших по горизонтали кружков -мужское и женское имя.
Выделим типовые операции над двоичными деревьями поиска:
- добавление элемента в дерево;
- удаление элемента из дерева;
- обход дерева (для печати элементов и т.д.);
- поиск в дереве.
Поскольку определение двоичного дерева рекурсивно, то все указанные типовые операции могут быть реализованы в виде рекурсивных подпрограмм (на практике именно такой вариант чаще всего и применяется). Отметим лишь, что использование рекурсии замедляет работу программы и расходует лишнюю память при её выполнении.
Покажем два варианта добавления элемента в дерево: итеративный и рекурсивный.
{Итеративный вариант добавления элемента в дерево, Turbo Pascal}
Procedure InsIteration(Var T: U; X: BT);
Var vsp, A: U;
Begin
New(A); A^.Inf:= X; A^.L:=Nil; A^.R:= Nil;
If T=Nil Then T:=A
Else Begin vsp:= T;
While vsp <> Nil Do
If A^.Inf < vsp^.Inf
Then
If vsp^.L=Nil Then Begin vsp^.L:=A; vsp:=A^.L End Else vsp:=vsp^.L
Else
If vsp^.R = Nil Then Begin vsp^.R:= A; vsp:=A^.R End Else vsp:= vsp^.R;
End
End;
{Рекурсивный вариант добавления элемента в дерево, Turbo Pascal}
Procedure InsRec(Var Tree: U; x: BT);
Begin
If Tree = Nil
Then Begin
New(Tree);
Tree^.L:= Nil;
Tree^.R:= Nil;
Tree^.Inf:= x
End
Else If x < Tree^.inf
Then InsRec(Tree^.L, x)
Else InsRec(Tree^.R, x)
End;
Существует несколько способов обхода (прохождения) всех узлов дерева. Три наиболее часто используемых из них называются обход в прямом (префиксном) порядке, обход в обратном (постфиксном) порядке и обход во внутреннем порядке (или симметричный обход). Каждый из обходов реализуется с использованием рекурсии.
ГЛАВА 2. ЗАДАЧА 4
Кольцевой список из элементов с ключами.
Обозначения: D – данные, next – указатель на следующий элемент, P – указатель на предыдущий элемент, K – ключ, begin – указатель на начало списка.
ЛИСТИНГ ПРОГРАММЫ
Program Kolzevoy_Spisok;
type
ptr=^R;
R=Record
A:real;
K:integer;
next:ptr;
end;
var
nach:ptr;
nb,a,i,n:integer;
inf:real;
Procedure Init(var nach:ptr);
begin
nach:=nil;
end;
Procedure Print_Spisok(nach:ptr);
var q:ptr; i:integer;
begin
writeln('spisok:');
writeln;
i:=0;
if nach<>nil then
begin
q:=nach;
repeat
i:=i+1;
writeln(i:3,' ',q^.A:8:2,' ',q^.K);
q:=q^.next;
until q=nach;
writeln;
end;
if (nach=nil) then writeln('spisok pust');
end;
Procedure Clear_Spisok(var nach:ptr);
var q,r:ptr;
begin
if nach<>nil then
begin
q:=nach;
repeat
r:=q;
q:=r^.next;
Dispose(r);
until q=nach;
end;
nach:=nil;
end;
Procedure Dobavit_nach(var nach:ptr; inf:real);
var q,r:ptr;
begin
New(q);
if nach=nil then begin
nach:=q;
q^.next:=nach;
end
else begin
r:=nach;
while r^.next<>nach do r:=r^.next;
q^.next:=nach;
nach:=q;
r^.next:=q;
end;
q^.A:=inf;
q^.K:=nb;
nb:=nb+1;
end;
Procedure Dobavit_kon(var nach:ptr; inf:real);
var q,r:ptr;
begin
New(q);
r:=nach;
if nach<>nil then while r^.next<>nach do r:=r^.next;
if nach=nil then begin
nach:=q;
q^.next:=nach;
end
else begin
r^.next:=q;
q^.next:=nach;
end;
q^.A:=inf;
q^.K:=nb;
nb:=nb+1;
end;
Procedure Dobavit_nom(var nach:ptr; a:integer; inf:real);
var q,r:ptr; i:integer;
begin
q:=nach; i:=1;
if a<>1 then repeat
i:=i+1;
q:=q^.next;
until (i=a) or (q=nach);
if (i<>a) then writeln('nevernyi nomer')
else begin
New(r);
r^.A:=inf;
r^.K:=nb;
nb:=nb+1;
r^.next:=q^.next;
q^.next:=r;
end;
end;
Procedure Dobavit_kl(var nach:ptr; a:integer; inf:real);
var q,r:ptr;
begin
q:=nach;
if q^.K<>a then repeat
q:=q^.next;
until (q^.K=a) or (q=nach);
if (q^.K<>a) then writeln('nevernyi kluch')
else begin
New(r);
r^.A:=inf;
r^.K:=nb;
nb:=nb+1;
r^.next:=q^.next;
q^.next:=r;
end;
end;
Procedure Udalit_nach(var nach:ptr);
var q,r:ptr;
begin
if nach<>nil then begin
if nach^.next<>nach then
begin
r:=nach;
while r^.next<>nach do r:=r^.next;
q:=nach;
nach:=q^.next;
r^.next:=nach;
Dispose(q);
end
else
begin
q:=nach;
nach:=nil;
Dispose(q);
end;
end;
end;
Procedure Udalit_kon(var nach:ptr);
var q,r:ptr;
begin
r:=nach;
if nach<>nil then
begin
if nach^.next=nach then
begin
q:=nach;
nach:=nil;
Dispose(q);
end
else
begin
while r^.next^.next<>nach do r:=r^.next;
q:=r^.next;
r^.next:=nach;
Dispose(q);
end;
end;
end;
Procedure Udalit_nom(var nach:ptr; a3:integer);
var q,r:ptr; i:integer;
begin
if a3=1 then
Udalit_nach(nach)
else
begin
r:=nach; i:=1;
while (i<>a3-1) do
begin
i:=i+1;
r:=r^.next;
end;
q:=r^.next;
r^.next:=q^.next;
Dispose(q);
end;
end;
Procedure Udalit_kl(var nach:ptr; a3:integer);
var q,r:ptr;
begin
r:=nach;
if r^.K=a3 then
Udalit_nach(nach)
else
begin
while (r^.next^.K<>a3) do
r:=r^.next;
q:=r^.next;
r^.next:=q^.next;
Dispose(q);
end;
end;
Procedure Dobav_Element(var nach:ptr);
var a2,a3:byte; i:integer;
b:boolean;
begin
repeat
writeln('1 - v nachalo');
writeln('2 - v konec');
writeln('3 - posle elementa');
writeln('4 - posle klucha');
readln(a2);
if (a2<>1) and (a2<>2) and (a2<>3) and (a2<>4) then b:=false else b:=true;
until b;
if a2=3 then
begin
write('nomer:');
readln(a3);
end;
if a2=4 then
begin
write('kluch:');
readln(a3);
end;
write('element:');
readln(inf);
if (a2=1) then
Dobavit_nach(nach,inf);
if (a2=2) then
Dobavit_kon(nach,inf);
if (a2=3) then
Dobavit_nom(nach,a3,inf);
if (a2=4) then
Dobavit_kl(nach,a3,inf);
end;
Procedure Udal_Element(var nach:ptr);
var a2,a3:byte; i:integer;
b:boolean;
begin
repeat
writeln('1 - iz nachala');
writeln('2 - iz konca');
writeln('3 - ukazannyi element');
writeln('4 - ukazannyi kluch');
readln(a2);
if (a2<>1) and (a2<>2) and (a2<>3) and (a2<>4) then b:=false else b:=true;
until b;
if a2=3 then
begin
write('nomer:');
readln(a3);
end;
if a2=4 then
begin
write('kluch:');
readln(a3);
end;
if (a2=1) then
Udalit_nach(nach);
if (a2=2) then
Udalit_kon(nach);
if (a2=3) then
Udalit_nom(nach,a3);
if (a2=4) then
Udalit_kl(nach,a3);
end;
begin
nb:=1;
Init(nach);
write('chislo dobavlennyh elementov spiska:');
readln(n);
for i:=1 to n do begin
Dobav_Element(nach);
Print_Spisok(nach);
readln;
end;
write('chislo udalennyh elementov spiska:');
readln(n);
for i:=1 to n do begin
Udal_Element(nach);
Print_Spisok(nach);
readln;
end;
Clear_Spisok(nach);
end.
НАБОР ТЕСТОВ
2.2.1
При добавлении элемента в начало, нужный элемент занимает место перед предыдущим. Если список пуст, список заполняется одним элементом.
Теперь в списке находится элемент 6. Вставим в начало элемент 3. Список будет выглядеть следующим образом:
При добавлении элемента в конец, нужный элемент занимает место после последнего элемента. Вставим в конец нашего списка элемент 28. Тогда список будет выглядеть следующим образом:
Когда уже есть несколько элементов, то можно добавить элемент после любого элемента с каким либо номером. Вставим после элемента с номером два элемент 111.
Элементу 111 присваивается номер 3. И получается список:
Добавим элемент 609 после элемента с ключом 1.
При нажатии кнопки «удалить из начала» получим: 6, 609, 111, 28.
Удалим элемент из конца списка, получим: 6, 609, 111.
Можно удалить элемент с любым номером, который есть в этом списке, например с номером 2. Получим список: 6,111.
Удалим элемент с ключом 3. Получим список, состоящий из одного элемента: 6.
2.2.2
Проверим работу программы вторым вариантом тестов: пусть число вводимых элементов равно 6. Вставим первый элемент 123. Получим список, состоящий только из элемента 123.
Вставим в начало элемент 8. Ему присваивается номер 1, ключ 2.
Вставим элемент 333333 после элемента с ключом 2. Получим следующий список:
При добавлении элемента в конец, нужный элемент занимает место после последнего элемента. Вставим элемент 2 в конец списка:
Вставим элемент 8 после элемента с номером 1:
Вставим в начало списка элемент 3. Получился список, состоящий из шести элементов: 3, 8, 8, 333333, 123, 2.
Удалим из списка элемент под номером 4. Список состоит из 5 элементов: 3, 8, 8, 123, 2.
ГЛАВА 3. ЗАДАЧА II 5 e