Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Варіанти індивідуальних завдань. 1. Для наступних варіантів представлення черги реалізувати функції:



1. Для наступних варіантів представлення черги реалізувати функції:

- St_init - створити чергу встановленого розміру;

- St_empty - визначити чи є черга Q пустою;

- St_push - добавити елемент до черги Q;

- St_clear - вилучити елемент із черги Q:

1.1. Варіант 1: для черги відводиться свій масив із n компонентів, в яких елементи черги займають групу сусідніх компонент, індекси першої та останньої з яких запам’ятовуються (рисунок 7.3); при цьому коли черга досягає правого краю масиву, то всі її елементи зміщуються до лівого краю;

 

Е1 Е2 Еm n

1 2 Н-1 Н К К+1

 

Рисунок 7.3

 

1.2. Варіант 2: представлення аналогічне варіанту 1, але масив склеюється у кільце, тому, якщо черга досягає правого краю масиву, то нові елементи записуються до початку масиву (рисунок 7.4);

Ei+1 Еm Е1 Е2 Ei

1 K K+1 Н-1 H H+1 n

 

 

Рисунок 7.4

 

1.3. Варіант 3: для кожної черги створюється свій список з одним напрямком із елементів черги, при цьому запам’ятовуються посилання на першу та останню ланку списку (рисунок 7.5).

 

 

Рисунок 7.5.

 

2. Використовуючи чергу, вирішити наступні завдання:

2.1. За один перегляд файлу f, без використання додаткових файлів, надрукувати елементи файлу f за наступним порядком:

а) усі числа менше а;

б) усі числа з відрізку [а, в];

в) усі числа, які більше та не входять до відрізку [а, в]; при цьому а, в – встановлені числа, а>в;

2.2. Зміст текстового файлу f , який розділено на строки, переписати до текстового файлу д, переносячи при цьому у кінець кожної строки всі цифри, що входять до неї (із збереженням вихідного взаємного порядку, як серед цифр, так і серед літер строки);

2.3. Маємо файл типу Д (х, у), де у визначає ім’я дитини чоловіка за ім’ям х. Необхідно записати до файлу П ім’я всіх потомків чоловіка на ім’я И у наступному порядку: спочатку ім’я всіх його дітей, після цього – всіх внуків, після цього – правнуків і т.д.

 

7.4 Контрольні питання та завдання

 

1. Опишіть, як логічно може бути представлена черга.

2. Яке значення мають черги у програмуванні?

3. Яким чином можливо реалізувати черги на базі масиву?

4. Яким чином можливо реалізувати чергу на базі масиву без зациклювання?

5. Яким чином можливо реалізувати чергу на базі масиву із зациклюванням?

6. Назвіть основні технологічні операції використання черг у програмах.

8 СТВОРЕННЯ ТА ОБРОБКА СТЕКІВ У СЕРЕДОВИЩІ С++

 

Мета роботи

 

Вивчення методів реалізації стеків у середовищі мови С++. Отримання практичних навичок використання стеків при вирішенні практичних завдань.

8.2 Організація самостійної роботи студентів

 

Під час підготовки до виконання лабораторної роботи необхідно вивчити індивідуальне завдання (п. 8.3), виконати розробку алгоритму вирішення задачі та підготовити текст програми щодо реалізації розробленого алгоритму, підготовити відповідні розділи звіту та вивчити відповідний теоретичний матеріал, який викладено у лекціях: „Прості структури даних у С++: стек, черга ”, „Технологія створення та використання стеків у С++”, та у наступних підручниках і навчальних посібниках [1, 4, 5, 7, 8].

Базою реалізації стека (рисунок 8.1) є масив розміру N, таким чином, реалізується стек обмеженого розміру, максимальна глибина якого не може перевищувати N. Індекси елементів масиву змінюються від 0 до N - 1. Елементи стека зберігаються в масиві таким чином: елемент на дні стека розташовується на початку масиву, тобто має з індекс 0. Елемент, розташований над самим нижнім елементом стека, зберігається в осередку з індексом 1, і так далі. Вершина стека зберігається десь у середині масиву. Індекс елемента на вершині стека зберігається в спеціальної змінної, котру називають покажчиком стека (по-англійському Stack Pointer або просто SP).

 

Рисунок 8.1

 

Коли стек порожній, покажчик стека має значення мінус одиниця. При додаванні елемента покажчик стека спочатку збільшується на одиницю, потім до масиву у відповідності із індексом, що знаходиться в покажчику стека, записується элемент. При добуванні елемента із стека спершу елемент масиву з індексом, що знаходиться в покажчику стека, переписується до тимчасової змінної, як результат операції, після чого покажчик стека зменшується на одиницю.

У наведеній реалізації стік росте убік збільшення індексів елементів масиву. Часто використовується інший варіант реалізації стека на базі вектора (рисунок 8.2), коли дно стека міститься в останньому елементі масиву, тобто в елементі з індексом N - 1. Елементи стека займають неперервний відрізок масиву, починаючи з елемента, індекс якого зберігається в покажчику стека, та закінчуючи останнім елементом масиву. У цьому варіанті стік росте убік зменшення індексів. Якщо стек порожній, то покажчик стека має значення N (яке на одиницю більше, ніж індекс останнього елемента масиву).

 

 

Рисунок 8.2

 

Розглянемо приклад реалізації стеку дійсних чисел. Реалізація включає два файли: "streal.h", у якому описується інтерфейс виконавця "Стек", та "streal.cpp", що реалізує функції роботи із стеком. Слово real позначає дійсне число.

Будемо використовувати перший варіант реалізації стека на базі масиву (рисунок 8.1), коли стек росте убік збільшення індексів масиву. Простір під масив елементів стека захоплюється в динамічній пам'яті в момент ініціалізації стека. Функції ініціалізації st_init передається розмір масиву, тобто максимально можливе число елементів у стеку. Для завершення роботи стека потрібно викликати функцію st_terminate, що звільняє захоплену в st_init пам'ять. Нижче наведений уміст файлу "streal.h", що описує інтерфейс стека.

// Файл "streal.h"// Стек дійсних чисел, інтерфейс//#ifndef ST_REAL_H#define ST_REAL_H// Прототипи функцій, що реалізують приписи стека: void st_init(int maxSize); //Почати роботу (вх: цілий //макс. розмір стека)void st_terminate(); // Закінчити роботуvoid st_push(double x); // Додати эл-т (вх: дійсн. x)double st_pop(); // Взяти елемент: дійсн.double st_top(); // Вершина стека: дійсн.int st_size(); // Поточний розмір стека: цілаbool st_empty(); // Стік порожній? int st_maxSize(); // Макс. розмір стека: цілаbool st_freeSpace(); // Є вільне місце? void st_clear(); // Видалити всі елементиdouble st_elementAt(int i); // Елемент стека на // глибині (вх: i): дійсн.#endif// Кінець файлу "streal.h"

 

Відзначимо, що директиви умовної трансляції

#ifndef ST_REAL_H#define ST_REAL_H. . .#endif

 

використовуються для запобігання повторного включення h-файлу: при першому включенні файлу визначається змінна препроцесора ST_REAL_H, а директива "#ifndef ST_REAL_H" підключає текст тільки тоді, коли ця змінна не визначена. Такий послідовність використовується практично у всіх h-файлах. Потрібний він тому, що одні h-файли можуть підключати інші, і без цього механізму уникнути повторного включення того самого файлу важко.

Файл "streal.cpp" описує загальні статичні змінні, над якими працюють функції, що відповідають приписам стека, та реалізує ці функції.

// Файл "streal.cpp"// Стек дійсних чисел, реалізація//#include <stdlib.h>#include <assert.h>#include "streal.h" //Підключити опис функцій стека// Загальні змінні для функцій, що реалізуються// приписи стека:static double *elements = 0; //Покажчик на масив эл-тов //стека в дин. пам'ятіstatic int max_size = 0; //Розмір масивуstatic int sp = (-1); //Індекс вершини стека// Приписи стека:void st_init(int maxSize) { //Почати роботу (вх: //макс. розмір стека) assert(elements == 0); max_size = maxSize; elements = (double *) malloc( max_size * sizeof(double) ); sp = (-1);}void st_terminate() { //Закінчити роботу if (elements != 0) { free(elements); }}void st_push(double x) { //Додати эл-т (вх: вещ x) assert( //твердження: elements != 0 && //стік почав роботу ы sp < max_ size-1 //є выльне місце ); ++sp; elements[sp] = x;}double st_pop() { //Узяти елемент: дійсний assert(sp >= 0); //твердження: стек не порожній ---іsp; //елемент вилучаэться зі стека return elements[sp + 1];}double st_top() { //Вершина стека: дійсний assert(sp >= 0); //твердження: стек не порожній return elements[sp];} int st_size() { //Поточний розмір стека: ціла return (sp + 1);}bool st_empty() { //Стек порожній? return (sp < 0);}int st_maxSize() { //Макс. розмір стека: ціла return max_size;}bool st_freeSpace() { //Є вільне місце? return (sp < max_size - 1);}void st_clear() { //Вилучити всі елементи sp = (-1);}double st_elementAt(int i) { //Елемент стека на //глибині (вх: i): дійсне assert( //твердження: elements != 0 && //стек почав роботу й 0 <= i && i < st_size() //0 <= i < розмір стека ); return elements[sp - i];}// Кінець файлу "streal.cpp"

У вищенаведеній реалізації стека на Сі неодноразово використовувалася функція assert – "твердження". Фактичним аргументом функції є логічний вираз. Якщо він вірний, то нічого не відбувається; якщо не вірний, то програма завершується аварійно, виводячи діагностику помилки.

Функція assert є реалізацією конструкції "твердження", використання якої має дві мети:

1. Програміст у процесі написання програми може явно сформулювати твердження, що, на його думку, повинне виконуватися в даній точці програми. У цьому випадку конструкція "твердження" виконує роль коментарію, полегшуючи створення та розуміння програми;

2. Комп'ютер при виконанні програми перевіряє всі явно сформульовані твердження. Істинність твердження відповідає припущенням програміста, зробленим у процесі написання програми, тому виконання програми триває. Хибність твердження свідчить про помилку програміста. При цьому видається повідомлення про помилку і виконання програми негайно припиняється. Таким чином, конструкція "твердження" дозволяє комп'ютеру перевіряти коректність програми безпосередньо в процесі її виконання.

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

Багато приписів структури даних здійсненні не у всіх ситуаціях. Наприклад, елемент можна взяти зі стека тільки у випадку, коли стек не порожній. Тому перед початком виконання припису "Взяти елемент" перевіряється умова "Стек не порожній":

double st_pop() { // Взяти елемент: вещ assert(sp >= 0); // утв: стік не порожній . . .

 

Якщо це твердження не вірне, то виникає ситуація "відмова": комп'ютер завершує роботу, видаючи діагностику помилки. Невиконання твердження завжди свідчить про помилку програміста: програма повинна бути написана таким чином, щоб некоректні вихідні дані не призводили до відмови.

Використання конструкції "твердження" – потужний засіб налагодження програми. Важливість ситуації "відмова" була усвідомлена в процесі еволюції програмування далеко не відразу. На зорі розвитку програмування на першому плані були вимоги ефективності програми – її компактності та швидкодії. І лише в міру проникнення комп'ютерів в усі області життя на перший план виступила надійність програми. У сучасному світі від надійності програми в багатьох випадках залежить людське життя, тому будь-які способи підвищення надійності дуже важливі.

Чому у випадку невиконання твердження виникає ситуація "відмова"? Альтернативою могло б бути ігнорування некоректної ситуації і те або інше продовження програми: наприклад, при спробі добування елемента з порожнього стека видавався б нуль. Насправді це гірше рішення із всіх, які тільки можна придумати! Будь-яку помилку треба діагностувати та виправляти якомога раніше, а імітація корисної діяльності в некоректній ситуації вкрай небезпечна. Це може призвести, наприклад, до того, що програма, що керує посадкою літаків, буде успішно саджати в середньому 999 літаків з 1000, а кожен тисячний буде розбиватися.

Практична рекомендація: використовуйте конструкцію "твердження" якнайчастіше. Якщо при розробці програми ви вважаєте, що в даній точці повинне виконуватися деяке твердження, сформулюйте його явно, щоб комп'ютер при виконанні програми міг би його перевірити.

При частому використанні конструкції "твердження" виникає проблема зі зменшенням швидкості виконання програми. Вона вирішена в мові С++ у такий спосіб: насправді конструкція assert – це не функція, а макровизначення, що обробляється препроцесором. Текст Сі-програми може транслюватися у двох режимах: налагоджельному та нормальному. У нормальному режимі у відповідності із стандартом ANSI визначена змінна NDEBUG препроцесора. Для визначення макрокоманди assert використовується умовна трансляція: якщо змінна NDEBUG визначена, то assert визначається як порожній вираз; якщо ні, то assert визначається як перевірка умови та виклик функції _assert (до ім'я доданий символ підкреслення) у випадку, коли умова не вірна. Функція _assert друкує діагностику помилки та завершує виконання програми, тобто реалізує ситуацію "відмова".

Таким чином, умова реально перевіряється лише при трансляції програми в режимі налагодження. Завдяки цьому швидкодія програми не знижується, однак, у нормальному режимі умова не перевіряється.

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.