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


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

Варіанти індивідуальних завдань. 1. Розробити програму, яка формує список L, включаючи до нього по одному разу елементи



1. Розробити програму, яка формує список L, включаючи до нього по одному разу елементи, які:

1.1. Входять хоч би до одного із списків L1, L2;

1.2. Входять одночасно до обох списків L1 та L2;

1.3. Входять до списку L1, але не входять до списку L2;

1.4. Входять до одного із списків L1 та L2, але у той же час не входять до іншого з них.

 

2. Розробити програму, яка об’єднує два відсортованих по збільшенню списки L1 та L2 у один відсортований по збільшенню список:

2.1. Побудувавши новий список L;

2.2. Замінюючи відповідним чином посилання у L1 та L2 та присвоївши отриманий список параметру L1.

 

3. L є кільцевим списком з двома напрямками (циклічним) із заголовним елементом (рисунок 6.4). Необхідно написати функцію, яка:

 

 
 

              Е1       Е2           Еn  

 

Рисунок 6.4

 

3.1. Визначає чи є список L пустим;

3.2. Друкує у зворотному порядку елементи непустого списку L;

3.3. Підраховує кількість елементів списку L, у якого рівні сусіди;

3.4. Визначає, чи є у списку L хоч один елемент, який дорівнює наступному за ним (по кому) елементу;

3.5. У списку L переставляє у зворотному порядку всі елементи між першим та останнім входженням елемента Е, якщо Е входить до L не менш двох разів;

3.6. Із списку L, який має не менш двох елементів, видаляє всі елементи, у яких однакові «сусіди» (перший та останній елементи вважати сусідніми);

3.7. Будує список L за списком L1,який має один напрямок;

3.8. В кінець непустого списку L додає всі його елементи, розміщуючи їх у зворотному порядку (наприклад, по списку 1, 2, 3 необхідно побудувати список з елементів 1, 2, 3, 3, 2, 1.

 

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

 

1. Яким чином виконується реалізація структур даних на основі посилань.

2. Що таке масові операції? В чому причина виникнення масових операцій, які засоби можна використовувати для боротьби із масовими операціями?

3. Що представляє собою структура даних типу «лінійний список»?

4. Що таке список з одним напрямком?

5. Що таке список з двома напрямками?

6. Яким чином виконується реалізація списку на основі посилань?

7. Які методи реалізації списків з одним та двома напрямками у С++ вам відомі?

7. СТВОРЕННЯ ТА ОБРОБКА ЧЕРГ У СЕРЕДОВИЩІ С++

 

Мета роботи

 

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

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

 

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

Масив даний є базовою структурою, всі інші структури даних потрібно реалізовувати на його основі. Така реалізація може бути багатоетапною, і не завжди масив виступає як безпосередня база реалізації. У випадку черги найбільш популярні дві реалізації: безперервна на базі масиву, що називають також реалізацією на базі кільцевого буфера, та реалізація на основі посилань, або реалізація на базі списку. Розглянемо безперервну реалізацію черги на базі масиву.

При безперервній реалізації черги як база виступає масив фіксованої довжини N, таким чином, черга обмежена і не може містити більше N елементів. Індекси елементів масиву змінюються в межах від 0 до N - 1. Крім масиву, реалізація черги зберігає три прості змінні: індекс початку черги, індекс кінця черги, кількість елементів черги. Елементи черги знаходяться у відрізку масиву від індексу початку до індексу кінця (рисунок 7.1).

Індекс початку Індекс кінця черги черги

 

Рисунок 7.1

 

При додаванні нового елемента в кінець черги індекс кінця спершу збільшується на одиницю, потім новий елемент записується в осередок масиву із цим індексом. Аналогічно, при добуванні елемента з початку черги вміст осередку масиву з індексом початку черги запам'ятовується як результат операції, потім індекс початку черги збільшується на одиницю. Як індекс початку черги, так і індекс кінця при роботі рухаються зліва направо. Що виходить, коли індекс кінця черги досягає кінця масиву, тобто N - 1?

Основна ідея реалізації черги полягає в тому, що масив нібито зациклюється в кільце. Вважається, що за останнім елементом масиву знаходиться його перший елемент (нагадаємо, що останній елемент має індекс N - 1, а перший – індекс 0). При зміщенні індексу кінця черги вправо у випадку, коли він вказує на останній елемент масиву, він переходить на перший елемент. Таким чином, безперервний відрізок масиву, зайнятий елементами черги, може переходити через кінець масиву на його початок (рисунок 7.2).

Індекс початку Індекс кінця черги черги

 

Рисунок 7.2

 

При реалізації черги необхідно реалізувати окремі функції для роботи з елементами черги: вставити елемент до черги, вилучити елемент з черги, та додаткові функції: визначення останнього елемента черги, визначити початок черги, визначити довжину черги, тобто кількість елементів, що знаходяться в черзі, змінити показники черги.

 




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

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