Структури даних, Детальна інформація

Реферат на тему:

Структури даних

Означення. Опис складних об’єктів засобами більш простих типів даних, які безпосередньо представляються у машині, називається структурами даних.

Найпоширеними складними об’єктами є множини та послідовності (впорядковані множини).

Списком називається впорядкована послідовність елементів a1, a2, ..., an. Розмір або довжина цього списку дорівнює n. Список розміру 0 називається порожнім. Список можна реалізувати або за допомогою масиву або за допомогою зв’язування його елементів вказівниками (зв’язаний список). У зв’язаному списку елементи лінійно впорядковані, їх порядок визначається вказівниками, що входять у склад елементів списка. Елемент двостороннього зв’язаного списка містить три поля: ключ та два вказівника – наступний та попередній. В односторонньому зв’язаному списку відсутнє поле ‘попередній’. У впорядкованому списку елементи розташовані в порядку зростання ключів на відміну від невпорядкованого списка.

Стеки та черги – це динамічні множини (або спеціальні типи списків), в яких елемент що додається, визначається структурою множини. Стек працює за принципом “останній прийшов – перший пішов (LIFO)”, а черга – за принципом “перший прийшов – перший пішов (FIFO)”.

Нехай PList – вказівник на однозв’язний список.

PList = ^List;

List = object

val: integer; /* значення */

next: PList; /* вказівник на наступний елемент списку */

end;

Стек має наступні методи:

PUSH – покласти елемент до стеку;

POP – взяти верхній елемент зі стеку;

TOP – повернути верхній елемент стеку без його вилучення;

IsEmpty – перевірити, чи є стек порожнім;

PRINT – надрукувати елементи стеку.

Pstack – вказівник на об’єкт стек.

PStack = ^Stack;

Stack = object

lst: PList;

procedure Push (Value: integer);

function Pop :integer;

function Top :integer;

function IsEmpty :boolean;

procedure Print;

end;

procedure Stack.Push (Value:integer);

var temp: PList;