Файл: Структуры лабы.doc

1.

Организовать программно линейный односвязный список следующей структуры:

Опишите в программе запись, в полеbukv которой заносится буква. Порождая записи, поместить их в стек, а затем «вытолкнуть» их из списка, получив буквы в порядке, обратном исходному. Проверьте работу примера для исходного набора букв: const A: array [1 .. 9] of char =(‘A’, ’P’, ‘Y’, ‘T’, ‘K’, ‘Y’, ’P’, ‘T’, ‘C’).

2.

С помощью стека, организованного в соответствии со структурой вар. 1 организовать получение палиндрома, в котором вторая половина является зеркальным отражение первой без последнего символа. Первую половину вводить с клавиатуры. Например:

3.

Программно организазать очередь в виде однонаправленого списка из элементов типа rec:

Type ptr =^ rec;

rec = record

key : integer;

s : ptr;

end;

var t : rec;

Заполняются ссылки на первое ипоследнее звенья списка.

Во входном файле задана последовательность из равного количества положительных и отрицательных целых чисел, за которой следует нуль. Ввести эти числа и вывести их, чередуя положитедльные числа (на нечетных местах) с отрицательными ( на четных), причем исходный взаимный порядок как среди положительных, так и среди отрицательных чисел должен быть сохранен.

4.

Многочлен

P(х) = a_nxⁿ + a_n-1x^n-1 +… + a₁x + a₀

с целыми коэффициентами можно представить в виде списка, элементы которого расположены по убыванию степеней одночленов:

Описать на Object Pascal тип данных, соответствующий такому представлению многочленов, и определить следующие функции и процедуры для работы с этими списками-многочленами:

а) логическую функцию Equal(p,q), проверяющую на равенство многочлены p и q;

б) функцию Value(p,x), вычисляющую значение p в точке x;

в) процедуру Dif(p,q), которая строит многочлен p-производную многочлена q;

г) процедуру Addit(p,q,r), которая строит многочлен p-сумму многочленов q и r.

5.

Кольцевым списком называется однонаправленный список, в последнем звене которого вместо Nil указывается ссылка на первое звено:

Пусть L  кольцевой список с элементами типа Type prt =^ rec

rec = record;

key : integer;

s : ptr;

end;

а E  величина типа rec.

Описать и отладить:

а) процедуру, которая строит кольцевой список L и выводит в компонент класса TstringGrid таблицу:

t₁ t₂ … t_n-1 t_n

t₂ t₃ … t_n t₁

t₃ t₄ … t₁ t₂

-- - - - - - - - - -

t_n t₁ … t_n-2 t_n-1

б) процедуру, которая строит кольцевой список L и функцию, которая удаляет из непустого списка L последний элемент.

в) процедуру, которая строит кольцевой список L и функцию, которая добавляет в конец списка L новый элемент.

1.

а )Организовать и отладить программу для построения и печати идеально сбалансированного двоичного дерева ( Function Tree , Function PrintTree ) .

б )Запрограммировать и отладить алгоритм обхода построенного бинарного дерева слева направо (в качестве примера построить и обойти дерево , отображающее заданное арифметическое выражение с бинарными операциями).

2.

а )Организовать программно двоичное дерево с помощью процедуры поиска и включения ключа (Search).

б )Написать и отладить программу для поэлементного вывода значений узлов построенного дерева обходом дерева слева направо(Inorder).

Замечание: при правильной организации бинарного дерева с целочисленными ключами в результате отображения ключей при обходе в порядке Inorder , должна получиться отсортированная в порядке возрастания последовательность ключей.

3.

а )Написать и отладить программу, которая позволит построить идеально сбалансированное двоичное дерево (с целочисленными ключами).

б )Организовать процедуру удаления элемента из организованного двоичного дерева( Procedure Delete).

4.

Организовать и отладить программу для построения и отображения сбалансированного AVL-дерева(высоты в поддеревьях отличаются не более , чем на 1) с помощью алгоритма поиска и включения элемента; учесть необходимость балансировки AVL-дерева с использованием LL, RR, LR, RL-поворотов.

5.

Программно организовать построение дерева Фибоначчи(Ф-дерево), как пример AVL-дерева.

Замечание: дерево Фибоначчи определяется следующим образом:

1) пустое дерево есть Ф-дерево высотой 0;

2)единственная вершина есть дерево высотой 1;

3)если T_h-1 и T_h-2 -Ф-деревья с высотами (h-1) и (h-2), то

T_h =(T_h-1,x,T_h-2) также Ф-дерево высотой h;

4)других деревьев Фибоначчи не существует.

6.

Программно построить недвоичное сильноветвящееся В-дерево с помощью алгоритма поиска и включения элемента на страницу(Procedure SearchB). В программе учесть, что при переполнении страницы происходит расщепление страницы и ,соответственно реорганизация структуры В-дерева.

7.

Написать и отладить программу исключения элемента из недвоичного сильноветвящегося В-дерева(Procedure UnderFlow). В программе учесть возможность реорганизации структуры В-дерева в результате исключения элемента со страницы.