В основному, масив являє собою набір схожих об'єктів даних, що зберігаються в послідовних місцях пам'яті під загальним заголовком або ім'ям змінної.
Хоча пов'язаний список являє собою структуру даних, яка містить послідовність елементів, де кожен елемент пов'язаний з його наступним елементом. Є два поля в елементі зв'язаного списку. Одне - поле даних, а інше - поле поля, поле даних містить фактичне значення, яке потрібно зберегти та обробити. Крім того, поле зв'язків містить адресу наступного елемента даних у зв'язаному списку. Адреса, яка використовується для доступу до певного вузла, відома як покажчик.
Іншою істотною відмінністю між масивом і зв'язаним списком є те, що масив має фіксований розмір і повинен бути оголошений попередньо, але зв'язаний список не обмежується розміром і розширюється, а контрактується під час виконання.
Діаграма порівняння
| Основа для порівняння | Масив | Зв'язаний список |
|---|---|---|
| Основний | Це послідовний набір фіксованого числа елементів даних. | Це впорядкований набір, що містить змінну кількість елементів даних. |
| Розмір | Вказано під час декларування. | Не потрібно вказувати; ростуть і стискаються під час виконання. |
| Розміщення сховища | Розташування елемента виділяється під час компіляції. | Позиція елемента призначається під час виконання. |
| Порядок елементів | Зберігається послідовно | Зберігається випадково |
| Доступ до елемента | Прямий або випадковий доступ, тобто Вкажіть індекс масиву або індекс. | Послідовно доступний, тобто. Траверс, починаючи з першого вузла списку за допомогою покажчика. |
| Вставка і видалення елемента | Повільна відносно, як потрібно перемикання. | Легше, швидко і ефективно. |
| Пошук | Двійковий пошук і лінійний пошук | лінійний пошук |
| Необхідна пам'ять | менше | Більше |
| Використання пам'яті | Неефективна | Ефективний |
Визначення масиву
Масив визначається як набір певної кількості однорідних елементів або елементів даних. Це означає, що масив може містити тільки один тип даних, або всі цілі, всі числа з плаваючою точкою або всі символи. Декларація масиву така:
int a [10];
Де int вказує тип даних або тип елементів масиву сховищ. "A" - це ім'я масиву, а число, вказане в квадратних дужках, - це кількість елементів, які масив може зберігати, це також називається розміром або довжиною масиву.
Давайте подивимося на деякі поняття, які слід пам'ятати про масиви:
- Окремим елементам масиву можна звертатися, описуючи ім'я масиву, за яким слід індекс або індекс (визначаючи розташування елемента в масиві) всередині квадратних дужок. Наприклад, щоб витягти 5-й елемент масиву, нам потрібно написати формулу [4].
- У будь-якому випадку елементи масиву будуть зберігатися в послідовній пам'яті.
- Самий перший елемент масиву має нульовий індекс [0]. Це означає, що перший і останній елемент будуть вказані як [0], а [9] відповідно.
- Кількість елементів, які можуть зберігатися в масиві, тобто розмір масиву або його довжина, задається наступним рівнянням:
(верхня межа нижньої межі) + 1
Для вищевказаного масиву це буде (9-0) + 1 = 10. Де 0 - нижня межа масиву, а 9 - верхня межа масиву. - Масиви можуть бути прочитані або записані через цикл. Якщо ми читаємо одновимірний масив, він вимагає одного циклу для зчитування та іншого для запису (друку) масиву, наприклад:
a. Для читання масиву
для (i = 0; i <= 9; i ++)
{scanf ("% d", & a [i]); }
b. Для написання масиву
для (i = 0; i <= 9; i ++)
{printf ("% d", a [i]); } - У випадку 2-D масиву, потрібно було б дві петлі і аналогічно n-мерному масиву знадобилися б петлі.
Операції, що виконуються на масивах:
- Створення масиву
- Переміщення масиву
- Вставка нових елементів
- Видалення необхідних елементів.
- Модифікація елемента.
- Об'єднання масивів
Приклад
Наступна програма ілюструє читання і запис масиву.
#include #include void main () { int a[10], i; printf("Enter the array"); for ( i= 0; i <= 9; i++) { scanf ( "%d", &a[ i ] ) ; } printf( "Enter the array" ); for (i = 0 ; i <= 9 ; i++) { printf ( "%d\n", a[ i ] ) ; } getch (); }
Визначення пов'язаного списку
Зв'язаний список - це певний список деяких елементів даних, пов'язаних один з одним. При цьому кожен елемент вказує на наступний елемент, який представляє логічне впорядкування. Кожен елемент називається вузлом, який має дві частини.
INFO частина, в якій зберігається інформація і POINTER, яка вказує на наступний елемент. Як відомо для зберігання адреси, ми маємо унікальні структури даних в C, які називаються покажчиками. Отже, друге поле списку повинно бути типу покажчика.
Типи пов'язаних списків - це окремо пов'язаний список, подвійний пов'язаний список, круговий пов'язаний список, круговий подвійний пов'язаний список.
Операції, пов’язані зі списком посилань:
- Створення
- Перехід
- Вставка
- Видалення
- Пошук
- Конкатенація
- Дисплей
Приклад
Наступний фрагмент ілюструє створення зв'язаного списку:
struct node { int num; stuct node *next; } start = NULL; void create() { typedef struct node NODE; NODE *p, *q; char choice; first = NULL; do { p = (NODE *) malloc (sizeof (NODE)); printf ("Enter the data item\n"); scanf ("%d", & p -> num); if (p == NULL) { q = start; while (q -> next ! = NULL) { q = q -> next } p -> next = q -> next; q -> = p; } else { p -> next = start; start = p; } printf ("Do you want to continue (type y or n) ? \n"); scanf ("%c", &choice) ; } while ((choice == 'y') || (choice == 'Y')); }
Ключові відмінності між масивом і зв'язаним списком
- Масив являє собою структуру даних, що містить набір подібних елементів даних типу, тоді як список Зв'язаних вважається непримітивною структурою даних, що містить сукупність невпорядкованих пов'язаних елементів, відомих як вузли.
- У масиві елементи належать до індексів, тобто, якщо ви хочете потрапити в четвертий елемент, ви повинні написати назву змінної з її індексом або розташуванням у квадратній дужці.
У списку пов'язаних, хоча, ви повинні почати з голови і працювати ваш шлях, поки ви не отримаєте четвертий елемент. - Під час доступу до масиву елементів швидко, тоді як список Зв'язаний займає лінійний час, тож він досить повільний.
- Операції, такі як вставка і видалення в масивах, споживають багато часу. З іншого боку, ефективність цих операцій у списках зв'язаних є швидкими.
- Масиви мають фіксований розмір. На відміну від цього, списки "Зв'язані" є динамічними та гнучкими і можуть розширюватися і скорочуватися за розмірами.
- У масиві пам'ять призначається під час компіляції, у той час як у списку "Зв'язаний" вона виділяється під час виконання або часу виконання.
- Елементи зберігаються послідовно в масивах, тоді як вони зберігаються випадковим чином у списках зв'язаних.
- Вимога пам'яті менше через фактичні дані зберігаються в межах індексу в масиві. На відміну від цього, існує потреба у більшій кількості пам'яті у зв'язаних списках через зберігання додаткових наступних та попередніх елементів посилання.
- Крім того, використання масиву неефективно. І навпаки, використання масиву пам'яті є ефективним.
Висновок
Масиви та зв'язані списки - це типи структур даних, що відрізняються за своєю структурою, методами доступу та маніпуляцій, вимоги до пам'яті та використання. І мають особливі переваги і недоліки щодо його реалізації. Отже, будь-який з них може бути використаний за потребою.
