asyan.org
добавить свой файл
1

Лабораторна робота № 3
Структури даних: масиви, зв’язні списки


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

3.1 Теоретичні відомості



В останні роки персональний комп’ютер все частіше використовується не лише для виконання обчислень, а й для аналізу та обробки тексту. Текст при цьому подається як сукупність символьних даних, які об’єднуються в структури типу символьного масиву, динамічного списку чи рядка (конструкція String в Паскалі або С++). Ці структури розрізняються формою свого внутрішнього представлення в пам’яті комп’ютера.

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

Отже, текст фізично можна представити як масивом символів, так і списком символів. При цьому символьний масив може бути як статичний, так і динамічний.

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

Для оптимізації витрат пам’яті можна використовувати динамічний масив. Його перевагою є те, що пам'ять під динамічний масив виділяється під час виконання програми за відповідним запитом. Але слід враховувати, що при необхідності додати в масив ще один елемент, доведеться кожного разу відсилати запит в пам'ять для створення динамічного масиву нової довжини, що потребує часу на пошук неперервної ділянки пам’яті (концепція масиву потребує, щоб сусідні елементи розташувались в послідовних байтах пам’яті), а також виділення цієї пам’яті, перепису в неї даних зі «старого» масиву і збереження нової довжини. Таким чином, уникнувши втрат пам’яті, ми прийдемо до додаткових витрат часу. Відповідно, зміна розміру динамічного масиву на одиницю – дуже ресурсоємна та недоцільна дія. Пам’ять під динамічний масив необхідно запитувати «розумними» частинами, щоб мінімізувати можливі втрати ресурсів. Зазвичай новий масив подвоює використовуваний масив пам’яті.

Список – це динамічна структура даних, кожен елемент якої, містить дані і адресу наступного елемента (вказівник на наступний елемент). Ця адреса у останнього елемента – нульова. Пам’ять під кожен елемент списку виділяється динамічно по мірі необхідності. При цьому в статичній пам’яті зберігається адреса першого елемента або нульовий вказівник, якщо список порожній.

Для доступу до елемента списку необхідно переглянути список з «голови». Такий доступ називається послідовним. В елементі списку можна зберігати адресу не лише наступного, а й попереднього елемента. В цьому випадку список називається двозв’язним. Адреса попереднього у першого елемента і наступного у останнього елемента – нульова. Двозв’язні списки можна переглядати у двох напрямках, тобто, доступ до елементів двозв’язного списку можливий з будь-якого кінця.

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

  • якщо заздалегідь неможливо визначити кількість елементів в структурі, то її краще реалізовувати списком;

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

  • операції включення або виключення елемента із масиву виконуються важче і довше, ніж в списку;

  • використання масивів передбачає неекономне виділення пам’яті (відразу під весь масив), однак у списку потрібна додаткова пам’ять в кожному елементі для зберігання вказівника на наступний (попередній) елемент.

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

3.2. Порядок виконання роботи


Слова тексту із малих латинських літер записані не менше, ніж через один пробіл; текст закінчується крапкою. БЕЗ ВИКОРИСТАННЯ конструкції String і стандартних процедур роботи з рядками написати програму введення такого тексту з клавіатури та його обробки, використовуючи: а) масив символів та  б) список символів. Виконати завдання відповідно до свого варіанту.

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

Інтерфейс програми має бути зрозумілим непідготовленому користувачеві. При розробці інтерфейсу програми слід передбачити:

  • задання формату і діапазону даних, що вводяться;

  • блокування введення невірних за типом і форматом даних;

  • задання операції, яка виконується програмою;

  • наявність пояснень при виведенні результату.

Потрібно також вивести на екран інформацію про час виконання програми при використанні масиву і списку та про об’єм пам’яті, необхідний у кожному з цих випадків.

При тестуванні програми необхідно:

  • перевірити правильність введення та виведення даних (зокрема, відстежити спроби введення даних, неправильних за типом і форматом);

  • забезпечити виведення повідомлень за відсутності вхідних даних («пусте введення»);

  • перевірити правильність виконання операцій, зокрема, при повністю заповненому масиві;

  • відстежити вихід за межі масиву;

  • забезпечити виведення відповідних повідомлень при спробі видалення елемента з пустого списку або масиву;

  • відстежити переповнення масиву.

При представленні тексту у вигляді списку необхідно:

  • перевірити можливість вставки елемента в початок, в кінець і в середину списку;

  • проконтролювати правильність видалення елемента з кінця, середини, початку списку;

  • відстежити видалення єдиного елемента і видалення елемента з порожнього списку;

  • перевірити, як звільняється пам’ять при видаленні елемента зі списку.

3.3. Варіанти завдань


1. Надрукувати всі слова, у яких непарна кількість літер. Перед друком видалити першу та останню літеру кожного слова.

2. Надрукувати всі слова, які відрізняються від першого слова і співпадають з початковим відрізком алфавіту (a, ab, abc тощо). Видалити першу літеру в цих словах. До кожного слова дописати крапку.

3. Надрукувати всі слова, які починаються на літеру, відмінну від літери, з якої починається перше слово тексту. Перед друком видалити зі слів всі літери ’a’ та ’o’.

4. Надрукувати всі слова, які відрізняються від першого слова. Перед друком подвоїти першу літеру, якщо в слові парна кількість літер, та видалити останню літеру, якщо в слові непарна кількість літер. Якщо слів менше, ніж два, видати повідомлення.