Разлика между масив и свързан списък

• 2019

Основната разлика между масив и свързан списък се отнася до тяхната структура. Масивите са индексни базирани данни, където всеки елемент е свързан с индекс. От друга страна, свързаният списък разчита на референции, където всеки възел се състои от данни и препратки към предишния и следващия елемент.

По принцип, масив е набор от подобни обекти за данни, съхранявани в последователни места с памет под общо заглавие или име на променлива.

Докато свързан списък е структура от данни, която съдържа последователност от елементи, където всеки елемент е свързан със следващия елемент. Има два полета в елемент от свързан списък. Едното е полето за данни, а друго е полето за връзка, полето Данни съдържа действителната стойност, която трябва да се съхранява и обработва. Освен това, полето за връзка съдържа адреса на следващия елемент от данни в свързания списък. Адресът, използван за достъп до определен възел, е известен като указател.

Друга съществена разлика между масив и свързан списък е, че Array има фиксиран размер и се изисква да бъде деклариран преди, но Linked List не е ограничен до размер и не се разширява и свива по време на изпълнение.

Сравнителна таблица

Основа за сравнение	Array	Свързан списък
Основен	Това е последователен набор от фиксиран брой елементи от данни.	Той е подреден набор, съдържащ променлив брой елементи от данни.
размер	Посочено по време на декларацията.	Няма нужда да се уточнява; расте и свива по време на изпълнение.
Разпределение на съхранение	Местоположението на елемента се разпределя по време на компилация.	Позицията на елемента се задава по време на работа.
Ред на елементите	Запазва се последователно	Съхранява се на случаен принцип
Достъп до елемента	Директен или произволно достъп, т.е. Укажете индекса на масива или индекса.	Достъпът е последователен, т.е. преминава се от първия възел в списъка с показалеца.
Вмъкване и изтриване на елемент	Необходима е бавна и относителна промяна.	По-лесно, бързо и ефективно.
търсене	Двоично търсене и линейно търсене	линейно търсене
Изисква се памет	по-малко	| Повече ▼
Използване на паметта	неефективен	ефикасен

Дефиниция на масива

Масивът се определя като набор от определен брой хомогенни елементи или елементи от данни. Това означава, че масивът може да съдържа само един тип данни, или цели числа, всички числа с плаваща запетая или всички символи. Декларацията на масив е както следва:
int a [10];
Където int указва типа на хранилището или типа масив от данни. "A" е името на масив, а числото, посочено в квадратните скоби, е броят на елементите, които масивът може да съхрани, също се нарича размер или дължина на масива.

Нека разгледаме някои от понятията, които трябва да се запомнят за масиви:

• Отделните елементи на масив могат да бъдат достъпни чрез описване на името на масива, последвано от индекс или индекс (определяне на местоположението на елемента в масива) в квадратните скоби. Например, за да извлечем 5-ти елемент от масива, трябва да напишем изявление a [4].
• Във всеки случай елементите на масив ще се съхраняват в последователна памет.
• Първият елемент на масива има индекс нула [0]. Това означава, че първият и последният елемент ще бъдат определени като [0], и a [9] съответно.
• Броят на елементите, които могат да се съхраняват в масив, т.е. размерът на масив или неговата дължина, се дава от следното уравнение:
  (горна граница-долна граница) + 1
  За горния масив би било (9-0) + 1 = 10. Където 0 е долната граница на масива, а 9 е горната граница на масива.
• Масивите могат да се четат или записват чрез цикъла. Ако четем едномерния масив, той изисква един цикъл за четене и друг за писане (отпечатване) на масива, например:
  а. За четене на масив
  за (i = 0; i <= 9; i ++)
  {scanf ("% d", & a [i]); }
  б. За писане на масив
  за (i = 0; i <= 9; i ++)
  {printf (“% d”, a [i]); }
• В случай на 2-D масив, ще са необходими два контура и по същия начин n-мерният масив ще изисква 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, която сочи към следващия елемент. Както знаете за съхраняване на адрес, имаме уникални структури от данни в С, наречени указатели. Следователно второто поле на списъка трябва да бъде тип указател.

Видове свързани списъци са единично свързан списък, двойно свързан списък, кръгов свързан списък, кръгов двойно свързан списък.

Операциите, извършени в свързан списък, са:

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. Освен това използването на паметта е неефективно в масива. Обратно, използването на паметта е ефективно в масива.

заключение

Масивите и свързаните списъци са типовете структури от данни, които се различават по своята структура, методи за достъп и манипулация, изискване за памет и използване. И имат особени предимства и недостатъци по отношение на неговото прилагане. Следователно, всеки от тях може да се използва според нуждите.