Курсовая работа: Списки стеки очереди в C

Черга характеризується такими властивостями:

· елементи додаються в кінець черги;

· елементи зчитуються та видаляються з початку (вершини) черги;

· покажчик в останньому елементі черги дорівнює NULL;

· неможливо отримати елемент із середини черги, не вилучивши все елементи що ідуть попереду.

Наведемо приклади застосування черг в обчислювальній техніці. У мережній операційній системі процесор сервера обслуговує в певний момент часу тільки одного користувача. Запити інших користувачів записуються до черги. Під час обслуговування користувачів кожен запит просувається до початку черги. Перший в черзі запит підлягає «першочерговому» обслуговуванню. У комп’ютерній мережі за чергою обслуговуються інформаційні пакети. Черги застосовуються також для буферизації потоків даних, що виводяться на друк, якщо в комп’ютерній мережі використовується один принтер.

Крім цих структур існують і інші, наприклад деки, двонаправленні списки, кільцеві списки і т.і.

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

Дек по суті двонаправлений список.

У зв'язаному списку (linked list) елементи лінійно впорядковані, але порядок визначається не номерами, як у масиві, а покажчиками, що входять до складу елементів списку. Списки є зручним способом зберігання динамічних даних, що дозволяють реалізувати всі операції, (хоча й не завжди ефективно).

Інакше кажучи, елемент двостороннє зв'язаного списку (doubly linked list) — це запис, що містить три поля: key (ключ) і два покажчики — next (наступний) і prev (від previous-попередній). Крім цього, елементи списку можуть містити додаткові дані. Якщо х — елемент списку, то next вказує на наступний елемент списку, а prev — на попередній. Якщо prev {х}= nil, то в елемента х немає попереднього: це голова (head) списку. Якщо next{х}= nil, то х — останній елемент списку або, як говорять, його хвіст (tail). Ці дані є неявно загальноприйнятими в програмуванні.

Звичайно, динамічні структури даних не обмежуються наведеними вище. Існують і інші, зокрема графи, дерева що займають свою окрему нішу у програмуванні і почасти вирішення певних питань не можливе без їх застосування.

Розділ ІІ. Практична реалізація динамічних структур на мові програмування С++

2.1 Робота з динамічною пам’яттю

2.1.1 Вказівники

Робота із динамічними структурами у С++ передбачає безпосередню роботу із посиланнями і вказівниками. Розглянемо детально як же їх створювати і які операції можна над ними проводити.

Змінні-вказівники містять в якості своїх значень адреси пам’яті. Зазвичай змінна містить деяке значення. З іншої сторони, вказівники містять адрес змінної, яка містить деяке значення. В цьому смислі ім’я змінної відсилається до значення прямо, а вказівник – побічно. Перехід на значення через вказівник називається побічною адресацією.

Вказівники, подібно до будь-яких інших змінних, перед своїм використанням повинні бути оголошені. Оголошення

int *countP;

оголошує перемінну countP типу int* (тобто вказівник за ціле число). Символ * в оголошенні вказує що йде оголошення вказівника. Вказівники можна оголошувати, що вказувати на об’єкти довільного типу.

Вказівники повинні бути ініціалізовані або при своєму оголошенні, або в операторі присвоєння. Вказівник можу бути ініціалізований значенням 0, NULL або адресом. Вказівник із значенням 0 або NULL ні на що не вказує.

Для вказівників характерні ряд операцій, так поряд із ними використовується операція адресації або ж &, - унарна операція, що повертає адрес свого операнда. Наприклад, якщо маємо оголошення

int y=5;

int *yP;

то операнд

yP-&y;

присвоює адрес змінної у вказівнику уР. Кажуть, що змінна уР «вказує» на у.

Операція *, зазвичай називається операцією побічною адресацією або операцією розіменування, повертає значення об’єкта, на який вказує її операдн (тобто вказівник). Наприклад, оператор