Рекомендуємо, 2024

Вибір Редакції

Різниця між масивом і зв'язаним списком

Основна відмінність між масивом і зв'язаним списком стосується їх структури. Масиви - це структура даних на основі індексів, де кожен елемент пов'язаний з індексом. З іншого боку, Зв'язаний список покладається на посилання, де кожен вузол складається з даних і посилань на попередній і наступний елемент.

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

Хоча пов'язаний список являє собою структуру даних, яка містить послідовність елементів, де кожен елемент пов'язаний з його наступним елементом. Є два поля в елементі зв'язаного списку. Одне - поле даних, а інше - поле поля, поле даних містить фактичне значення, яке потрібно зберегти та обробити. Крім того, поле зв'язків містить адресу наступного елемента даних у зв'язаному списку. Адреса, яка використовується для доступу до певного вузла, відома як покажчик.

Іншою істотною відмінністю між масивом і зв'язаним списком є ​​те, що масив має фіксований розмір і повинен бути оголошений попередньо, але зв'язаний список не обмежується розміром і розширюється, а контрактується під час виконання.

Діаграма порівняння

Основа для порівнянняМасивЗв'язаний список
ОсновнийЦе послідовний набір фіксованого числа елементів даних.Це впорядкований набір, що містить змінну кількість елементів даних.
РозмірВказано під час декларування.Не потрібно вказувати; ростуть і стискаються під час виконання.
Розміщення сховищаРозташування елемента виділяється під час компіляції.Позиція елемента призначається під час виконання.
Порядок елементівЗберігається послідовноЗберігається випадково
Доступ до елементаПрямий або випадковий доступ, тобто Вкажіть індекс масиву або індекс.Послідовно доступний, тобто. Траверс, починаючи з першого вузла списку за допомогою покажчика.
Вставка і видалення елементаПовільна відносно, як потрібно перемикання.Легше, швидко і ефективно.
ПошукДвійковий пошук і лінійний пошуклінійний пошук
Необхідна пам'ятьменшеБільше
Використання пам'ятіНеефективнаЕфективний

Визначення масиву

Масив визначається як набір певної кількості однорідних елементів або елементів даних. Це означає, що масив може містити тільки один тип даних, або всі цілі, всі числа з плаваючою точкою або всі символи. Декларація масиву така:
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-мерному масиву знадобилися б петлі.

Операції, що виконуються на масивах:

  1. Створення масиву
  2. Переміщення масиву
  3. Вставка нових елементів
  4. Видалення необхідних елементів.
  5. Модифікація елемента.
  6. Об'єднання масивів

Приклад

Наступна програма ілюструє читання і запис масиву.

#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, які називаються покажчиками. Отже, друге поле списку повинно бути типу покажчика.

Типи пов'язаних списків - це окремо пов'язаний список, подвійний пов'язаний список, круговий пов'язаний список, круговий подвійний пов'язаний список.

Операції, пов’язані зі списком посилань:

  1. Створення
  2. Перехід
  3. Вставка
  4. Видалення
  5. Пошук
  6. Конкатенація
  7. Дисплей

Приклад

Наступний фрагмент ілюструє створення зв'язаного списку:

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'));
}

Ключові відмінності між масивом і зв'язаним списком

  1. Масив являє собою структуру даних, що містить набір подібних елементів даних типу, тоді як список Зв'язаних вважається непримітивною структурою даних, що містить сукупність невпорядкованих пов'язаних елементів, відомих як вузли.
  2. У масиві елементи належать до індексів, тобто, якщо ви хочете потрапити в четвертий елемент, ви повинні написати назву змінної з її індексом або розташуванням у квадратній дужці.
    У списку пов'язаних, хоча, ви повинні почати з голови і працювати ваш шлях, поки ви не отримаєте четвертий елемент.
  3. Під час доступу до масиву елементів швидко, тоді як список Зв'язаний займає лінійний час, тож він досить повільний.
  4. Операції, такі як вставка і видалення в масивах, споживають багато часу. З іншого боку, ефективність цих операцій у списках зв'язаних є швидкими.
  5. Масиви мають фіксований розмір. На відміну від цього, списки "Зв'язані" є динамічними та гнучкими і можуть розширюватися і скорочуватися за розмірами.
  6. У масиві пам'ять призначається під час компіляції, у той час як у списку "Зв'язаний" вона виділяється під час виконання або часу виконання.
  7. Елементи зберігаються послідовно в масивах, тоді як вони зберігаються випадковим чином у списках зв'язаних.
  8. Вимога пам'яті менше через фактичні дані зберігаються в межах індексу в масиві. На відміну від цього, існує потреба у більшій кількості пам'яті у зв'язаних списках через зберігання додаткових наступних та попередніх елементів посилання.
  9. Крім того, використання масиву неефективно. І навпаки, використання масиву пам'яті є ефективним.

Висновок

Масиви та зв'язані списки - це типи структур даних, що відрізняються за своєю структурою, методами доступу та маніпуляцій, вимоги до пам'яті та використання. І мають особливі переваги і недоліки щодо його реалізації. Отже, будь-який з них може бути використаний за потребою.

Top