2018-01-08
461Теоретичні відомості.
Для роботи з динамічними структурами даних застосовуються вказівники.
Вказівники являють собою спеціальний тип даних. Вони приймають значення, що відповідають адресам розміщення в оперативній пам’яті відповідних динамічних змінних.
Список – це структура даних, кожний елемент якого через вказівник зв’язується з наступним елементом.
Із визначення виходить, що кожен елемент списку містить поле даних (воно може мати складну структуру) та поле посилання на наступний елемент. Поле посилання останнього або першого елементу списку повинно містити вказівник NULL.
Кількість елементів подібного списку може зростати або зменшуватися в залежності від того, скільки даних ми хочемо в ньому зберігати.
Елемент списку складається з різнотипних частин (інформація, що зберігається, і вказівник), тому його природньо представити записом або в С – структурою. Наприклад, елемент структури можна представити так:
struct spis {
int data;
struct spis *adr;
};
Це структура, що посилається сама на себе. Вказівник в цій структурі виконує роль зв’язки.
Зв’язанний список - це набір «розміщених в ряд» елементів даних, в будь-якому місці якого можна виконувати вставки та вилучення.
Зв’язанний список- це набір структур, що посилаються на себе, і звуться вузлами, і об’’днаних вказівником-зв’язкою.
Щоб мати доступ до зв’язного списку потрібно мати вказівник на один з граничних вузлів, або перший, або останній.
Доступ до наступних вузлів здійснюється через вказівник, що зберігається в кожному вузлі.
За спільним погодженням зв’язуючий вказівник в останньому або першому вузлах списку встановлюються в NULL.
Дані зберігаються в такому списку динамічно-кожен вузол створюється по мірі необхідності.
Хоча вузли списку не розташовані в пам’яті в одній неперервній області, проте логічно список виглядає неперервним.
Переваги зв’язанного списку:
1. Зручний, коли наперед невідомо, скільки елементів даних повинно бути. Це динамічна структура, тому при необхідності довжина списку може збільшуватися або зменшуватися.
2. Зв’язані списку не обмежуються. Займають весь обсяг доступної пам’яті.
3. Якщо потрібно вилучити або вставити якийсь елемент в список, це робиться без серії зсувів наступних або попередніх елементів.
4. Використовуючи динамічний розподіл пам’яті замість масиву для структур даних, розмір яких може збільшуватись або зменшуватись під час виконання програми, можна зекономити пам’ять.
Деякі недоліки:
1. Відносна складність для розуміння.
2. Елементи масиву зберігаються в послідовних комірках пам’яті. Це забезпечує миттевий доступ до будь-якого елементу масиву на основі вказівника на перший елемент масиву та індекс елемента в масиві. В цей же час зв’язані списки не дають змогу такого миттівого доступу до своїх елементів.
3. Вказівники для себе забирають деяке місце в пам’яті.
Створення та використання динамічних структур даних вимагає динамічного розподілення пам’яті.
Для цього необхідно використання функцій malloc і free, а також операція sizeof.
Приклад:
newptr=malloc(sizeof(struct spis));
Функція malloc в якості аргумента приймає розмір в байтах, який необхідно виділити, і повертає вказівник на виділену область пам’яті.
Якщо необхідної кількості пам’яті нема, то функція malloc повертає вказівник NULL.
Функція malloc повертає вказівник типу void*.
Функція free(newptr) звільнює пам’ять. Тобто пам’ять повертається системі і її можна виділяти знову.
Приклад 1: Зформувати та вивести на екран зв’язаний список.
| #include <stdio.h> #include <stdlib.h> #include <conio.h> | |
| struct spis{ int data; struct spis *ptr; }; | Елемент списку складається з різнотипних частин (інформація, що зберігається, і вказівник), тому його природньо представити записом або в С – структурою. Наприклад, елемент структури можна представити так: struct spis { int data; struct spis *adr; }; Це структура, що посилається сама на себе. Вказівник в цій структурі виконує роль зв’язки. |
| main() { clrscr(); | |
| spis* startptr; spis* newptr; startptr=NULL; int a; | Опис типів вказівників, а також ініціалізація початкового значення вказівника значенням NULL |
| for(int i=0;i<10;i++) { newptr=(spis*) malloc(sizeof(spis)); if (newptr!=NULL) { printf("Input element\n"); scanf("%d",&a); newptr->data=a; newptr->ptr=startptr; startptr=newptr; } } | В рядку newptr=(spis*) malloc(sizeof(spis)); відбувається приведення типу вказівника до типу структури spis. Це необхідно здійснювати тому, що функція malloc повертає вказівник типу void*, а в наведеному прикладі вказівник описано як spis* newptr. Якщо значення вказівника не пусте, тобто не NULL, пам’ять виділено успішно і вказівник newptr містить адресу виділеної області пам’яті. Розмір цієї області відповідає розміру структури spis (для одного елемента!). Блок newptr->data=a; newptr->ptr=startptr; заповнює структуру даними, що ввели з клавіатури, і обов’язково заносимо адресу попереднього елементу. Оскільки перед першим елементом нічого нема, то адреса, що занесеться NULL (newptr->ptr=startptr; а спочатку startptr=NULL; ). На наступних кроках циклу значення startptr приймає значення адреси попереднього елементу. Отже, перший вказує на NULL, а наступні – на попередній. |
| clrscr(); while (newptr!=NULL) { printf("%d\n",newptr->data); newptr=newptr->ptr; } getch(); } | В даному місці програми вказівник newptr вказує на останньо створену область - на останній елемент. Починаємо рухатися з кінця. Виводимо останній елемент, бо вказівник вказує саме на нього. На наступному кроці потрібно змінити вказівник на попередній newptr=newptr->ptr; І так продовжуємо до тих пір, поки значення вказівника не буде пустим. |
| Результат: 10 9 8 7 6 5 4 3 2 1 |
Хід виконання роботи:
1. Розробити програму, що створює зв’язаний список з кількістю вузлів, що задається користувачем (не менше 20).
2. Значення елементів задаються за допомогою генератора випадкових чисел в зазначених за варіантами діапазонах.
3. Вивести сформований список на екран.
4. Задати необхідні умови згідно варіанту для виведення елементів зв’язаного списку, підрахувати кількість таких елементів.
5. Вивести новий зв’язаний список, в якому замінено всі елементи, які задовільняють вказаним умовам стовпця В, на значення згідно варіанту.
| Номер | Діапазон зміни значень елементів | Умова для виведення елементу списку | Умова для того, щоб здійснити заміну елементів | Якщо виконується умова стовпця Г, замінити всі елементи, що задовільняють умові стовпця В на зазначене значення |
| А | Б | В | Г | Д |
| -15..30 | Кратне 3, позитивне | Якщо парних елементів списку більше, ніж непарних | Найменше | |
| -67..45 | Кратне 5, негативне | Якщо додатніх елементів списку більше, ніж нульових | Найбільше | |
| -10..120 | Кратне 7 та не більше 10 | Якщо непарних елементів списку більше, ніж парних | Середнє | |
| -40..50 | Кратне 4, позитивне | Якщо кількість від’ємних елементів більша 3 | Найменше за абсолютним значенням | |
| -34..80 | Кратне 11, негативне | Якщо парних елементів списку більше, ніж 10 | Найбільше за абсолютним значенням | |
| -26..56 | Кратне 5 та не більше 40 | Якщо додатніх елементів списку більше, ніж від’ємних | Середнє | |
| -23..17 | Кратне 3, позитивне, не менше 20 | Якщо непарних елементів списку більше, ніж 5 | Найменше | |
| -11..100 | Кратне 15, негативне | Якщо парних елементів списку більше, ніж непарних | Найбільше | |
| -4..37 | Кратне 7 та не більше 20 | Якщо додатніх елементів списку більше, ніж нульових | Середнє | |
| -12..16 | Кратне 3 та не більше 40 | Якщо непарних елементів списку більше, ніж парних | Найменше | |
| -15..30 | Кратне 3, позитивне | Якщо кількість від’ємних елементів більша 3 | Найбільше | |
| -67..45 | Кратне 5, негативне | Якщо парних елементів списку більше, ніж 10 | Середнє | |
| -10..120 | Кратне 7 та не більше 10 | Якщо додатніх елементів списку більше, ніж від’ємних | Найменше за абсолютним значенням | |
| -40..50 | Кратне 4, позитивне | Якщо непарних елементів списку більше, ніж 5 | Найбільше за абсолютним значенням | |
| -34..80 | Кратне 11, негативне | Якщо парних елементів списку більше, ніж непарних | Найменше | |
| -26..56 | Кратне 5 та не більше 40 | Якщо додатніх елементів списку більше, ніж нульових | Найбільше | |
| -23..17 | Кратне 3, позитивне, не менше 20 | Якщо непарних елементів списку більше, ніж парних | Найменше | |
| -11..100 | Кратне 15, негативне | Якщо кількість від’ємних елементів більша 3 | Найбільше | |
| -4..37 | Кратне 7 та не більше 20 | Якщо парних елементів списку більше, ніж 10 | Середнє | |
| -12..16 | Кратне 3 та не більше 40 | Якщо додатніх елементів списку більше, ніж від’ємних | Найменше за абсолютним значенням |
