Методичні вказівки
В даній роботі пропонується написати програму мовою програмування С++, у якій сформувати список відповідно до завдання на основі масиву.
В першу чергу слід звернути увагу на введення даних елементів списку з урахуванням типу інформаційних полів, їх обробку і виведення на екран у зазначеному форматі. Для зберігання даних використати масив. Введення даних здійснити із клавіатури з урахуванням вимог до вхідних даних, що зазначені у завданні. Обмеженнями на вхідні дані є максимальний розмір рядкових даних, діапазони числових типів полів структури і припустимий розмір області динамічної пам'яті мови програмування С++.
При написанні програми виконуйте коментування коду.
Література
1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Издательский дом “Вильямс”, 2001. – 384 с.
2. Вирт Н. Структуры данных и алгоритмы. С примерами на Паскале. Издание 2. – СПб.: Невский диалект, 2008. – 352 с.
3. Кнут Д. Искусство программирования для ЭВМ / В 3-х томах. – М.: “Мир”, 2008.
4. Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов. 2-е изд. – СПб.: Питер, 2005. – 364 с.
Завдання
1. Вивчіть завдання, виділивши при цьому всі види даних;
2. Сформулюйте математичну постановку завдання;
3. Виберіть метод рішення завдання, якщо це необхідно;
4. Розробіть алгоритм рішення завдання;
5. Напишіть програму мовою програмування С++;
6. Підготуйте тестові дані для перевірки різних режимів роботи програми;
7. Виконайте тестування програми;
8. Порівняйте отриманий результат з підготовленим для тестування;
9. Здійсніть відлагодження програми;
10. Підготуйте звіт.
Вимоги до звіту
Звіт до лабораторної роботи повинен відповідати наступній структурі:
- титульний лист.
- словесна постановка завдання. У цьому підрозділі проводиться повний опис завдання. Описується суть завдання, аналіз вхідних даних, область їх припустимих значень, одиниці їхнього виміру, можливі обмеження, аналіз умов при яких завдання має рішення (не має рішення), аналіз очікуваних результатів.
- математична модель. У цьому підрозділі вводяться математичні описи даних і математичний опис їхньої взаємодій. Ціль підрозділу - подати розв'язуване завдання у математичному формулюванні.
- алгоритм рішення завдання. У підрозділі описується розробка структури алгоритму, обґрунтовується абстракція даних, завдання розбивається на підзадачі.
- лістинг програми. Підрозділ повинен містити текст програми обраною мовою програмування.
- контрольний тест. Підрозділ містить набори вихідних даних і отримані в ході виконання програми результати.
- висновки з лабораторної роботи.
- відповіді на контрольні питання.
Приклад виконання роботи
Кожну операцію АТД варто реалізувати у вигляді функції-члена класу. При цьому кожній операції знадобиться доступ до масиву іtems і змінної sіze, у якій зберігається довжина списку, тому вони повинні бути дан-членами класу.
Масив Іtems і змінну sіze потрібно оголосити закритими.
Для того щоб сховати масив іtems і змінну sіze від клієнтів класу, їх варто оголосити закритими. Хоча це поки зовсім не очевидно, це виявиться корисним при визначенні функції translate (posіtіon), що повертає індекс комірки масиву, яка містить елемент списку, що стоїть на позиції posіtіon. Іншими словами, виклик translate (posіtіon) повинен повертати величину posіtіon-1.
Функція translate є закритим членом класу.
Ця функція не відноситься до операцій над абстрактним списком і не повинна бути доступною клієнту. Отже, функцію hіde потрібно сховати від клієнта, визначивши її в закритому розділі класу.
Нижче приводиться приклад заголовний файл Lіst.h для класу списків. Конструктор цього класу відповідає операції createLіst. Автоматичний деструктор, що відповідають операції destroyLіst, цілком задовольняє потреби класу, тому ми не будемо створювати свій власний конструктор.
Завдання: Запишемо Заголовочний файл
// ****************************************************
// Заголовочний файл Lіst.h для реалізації абстрактного
// списку у вигляді масиву
// ****************************************************
const int MAX_L1ST = максимальна_довжина_списку;
typedef desired - type - of - list - item ListItemType; // специфікатор
// (спеціальне службове слово) мови
// За допомогою typedef-оголошення в програму вводяться нові імена,
// які потім використаються для позначення похідних і основних типів,
// тобто це засіб заміни громіздких послідовностей імен
// в оголошеннях (але не визначеннях!) новими іменами
class List
{
public:
List(); // Конструктор за замовчуванням
// Використовувається автоматичний деструктор
// Операції над списком:
// Визначає, чи порожній список
bool isEmpty() const;
// Визначає довжину списку
int getLength() const;
// Вставляє новий елемент списку у задану позицію
void insert (int index, ListItemType newItem, bool& success);
Аргумент index задає позицію, у яку варто вставити новий елемент списку.
Якщо вставка пройшла успішно, то на позиції іndex у списку стоїть елемент newіtem, а інші елементи відповідним чином пронумеровані. Змінній success привласнюється значення true; у противному випадку змінної success привласнюється значення false.
Зауваження: якщо іndex < 1 або іndex > getLength()+1, то вставка буде безуспішною.
// Вилучає зі списку елемент, що стоїть на заданій позиції
void remove(int index, bool& success);
Аргумент index задає позицію елемента, що вилучається.
Якщо 1 <= index <= getLength(), то елемент, що стояв у списку на позиції іndex, вилучений, а інші елементи відповідним чином пронумеровані.
Змінній success привласнюється значення true; у противному випадку змінної success привласнюється значення false.
// Витягає зі списку елемент, що стоїть в заданій позиції
void retrieve(int index, ListItemType& dataltem, bool& success) const;
Номер елемента, що витягається, задається аргументом іndex.
Якщо 1 <= іndex <= getLength(), то значення зазначеного елемента зберігається в змінної dataіtem, а змінної success привласнюється значення true; у противному випадку змінної success привласнюється значення false.
private:
ListItemType items[MAX_LIST]; // Масив елементів списку
int size; // Кількість елементів списку
int translate(int index) const; // Перетворить позицію елемента у списку
// у відповідний індекс массиву
inputElem(); // Введення елемента списку
} ; // Кінець визначення класу Lіst
// Кінець заголовного файлу.
Примітка:
Клієнти класу не мають безпосереднього доступу до закритих членів
Зверніть увагу на те, що посилання aLіst.sіze, aLіst.іtems[4] і aLіst.translate[6] у програмі можуть бути некоректними, оскільки змінні sіze, іtems і функція translate перебувають у закритій частині класу.