Razlika med nizom in povezanim seznamom

2019

Glavna razlika med seznamom in povezanim seznamom se nanaša na njihovo strukturo. Polja so indeksna podatkovna struktura, kjer je vsak element povezan z indeksom. Po drugi strani pa se povezani seznam opira na reference, kjer je vsako vozlišče sestavljeno iz podatkov in sklici na prejšnji in naslednji element.

V osnovi je niz podobnih podatkovnih objektov, shranjenih v zaporednih mestih pomnilnika pod skupnim naslovom ali imenom spremenljivke.

Medtem ko je povezan seznam podatkovna struktura, ki vsebuje zaporedje elementov, kjer je vsak element povezan z naslednjim elementom. V elementu povezanega seznama sta dve polji. Ena je Podatkovno polje, drugo pa polje Povezava, Podatkovno polje vsebuje dejansko vrednost, ki jo želite shraniti in obdelati. Poleg tega polje povezave vsebuje naslov naslednjega podatkovnega elementa na povezanem seznamu. Naslov za dostop do določenega vozlišča je znan kot kazalec.

Druga pomembna razlika med nizom in povezanim seznamom je v tem, da ima Array fiksno velikost in jo je treba deklarirati prej, vendar Linked List ni omejen na velikost in se razširja in pogoduje med izvajanjem.

Primerjalna tabela

Podlaga za primerjavo	Array	Povezani seznam
Osnovno	Je skladen niz določenega števila podatkovnih postavk.	Je urejen niz, ki vsebuje spremenljivo število podatkovnih elementov.
Velikost	Navedeno med deklaracijo.	Ni potrebe po navedbi; rastejo in se skrčijo med izvajanjem.
Dodelitev pomnilnika	Lokacija elementa je dodeljena v času prevajanja.	Položaj elementa je dodeljen med izvajanjem.
Vrstni red elementov	Shranjeno zaporedno	Shranjeno naključno
Dostop do elementa	Neposredno ali naključno, tj. Določite indeks indeksa ali indeks.	Dostop po sekvenci, tj. Prehod, ki se začne s prvim vozliščem na seznamu s kazalcem.
Vstavljanje in brisanje elementa	Počasna relativna sprememba je potrebna.	Lažje, hitrejše in učinkovitejše.
Iskanje	Binarno iskanje in linearno iskanje	linearno iskanje
Potreben je pomnilnik	manj	Več
Uporaba pomnilnika	Neučinkovita	Učinkovito

Opredelitev polja

Niz je definiran kot niz določenega števila homogenih elementov ali podatkovnih elementov. To pomeni, da lahko polje vsebuje samo eno vrsto podatkov, ali celo cela števila, vse številke s plavajočo vejico ali vse znake. Izjava o matriki je naslednja:
int a [10];
Kjer int opredeljuje podatkovne tipe ali elemente vrste array. "A" je ime matrike in število, ki je določeno v oglatih oklepajih, je število elementov, ki jih polje lahko shrani, kar se imenuje tudi velikost ali dolžina matrike.

Oglejmo si nekaj konceptov, ki jih je treba zapomniti o nizih:

Do posameznih elementov matrike lahko dostopate tako, da opišete ime matrike, ki ji sledi indeks ali indeks (določanje lokacije elementa v matriki) znotraj oglatih oklepajev. Na primer, za pridobitev 5. elementa matrike, moramo napisati izjavo a [4].
V vsakem primeru bodo elementi matrike shranjeni v zaporedni pomnilniški lokaciji.
Prvi element matrike ima indeks nič [0]. To pomeni, da bosta prvi in zadnji element določena kot [0] in a [9].
Število elementov, ki se lahko shranijo v matriki, tj. Velikost polja ali njegova dolžina, je podano z naslednjo enačbo:
(zgornja in spodnja meja) + 1
Za zgornjo matriko bi bilo (9-0) + 1 = 10. Kjer je 0 spodnja meja matrike, in 9 je zgornja meja matrike.
Nizi se lahko preberejo ali zapišejo prek zanke. Če beremo enodimenzionalno matriko, potrebujemo eno zanko za branje in drugo za pisanje (tiskanje) matrike, na primer:
a. Za branje matrike
za (i = 0; i <= 9; i ++)
{scanf (“% d”, & a [i]); }
b. Za pisanje matrike
za (i = 0; i <= 9; i ++)
{printf (“% d”, a [i]); }
V primeru dvodimenzionalnega polja bi potrebovali dve zanki in podobno n-dimenzionalno polje bi potrebovalo n zank.

Operacije, ki se izvajajo na nizih, so:

Primer

Naslednji program ponazarja branje in pisanje matrike.

#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 ();
}

Opredelitev povezanega seznama

Povezani seznam je poseben seznam nekaterih podatkovnih elementov, povezanih z drugimi. Pri tem vsak element kaže na naslednji element, ki predstavlja logično urejanje. Vsak element se imenuje vozlišče, ki ima dva dela.

INFO del, ki shranjuje informacije in POINTER, ki kaže na naslednji element. Kot veste za shranjevanje naslova, imamo v C imenujemo edinstvene podatkovne strukture, ki se imenujejo kazalci. Zato mora biti drugo polje seznama tip kazalca.

Vrste povezanih seznamov so posamezno povezani seznam, dvojno povezani seznam, krožni povezani seznam, krožni dvojni povezani seznam.

Operacije, ki se izvajajo na povezani seznam, so:

Primer

Naslednji odsek prikazuje ustvarjanje povezanega seznama:

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

Ključne razlike med nizom in povezanim seznamom

Matrika je podatkovna struktura, ki vsebuje zbirko podobnih podatkovnih elementov, medtem ko se povezani seznam obravnava kot ne-primitivna podatkovna struktura, ki vsebuje zbirko neurejenih povezanih elementov, znanih kot vozlišča.
V matriki elementi pripadajo indeksom, kar pomeni, da morate v četrti element zapisati ime spremenljivke z indeksom ali lokacijo znotraj oglatih oklepajev.
Na povezanem seznamu pa morate začeti od glave in delati skozi, dokler ne pridete do četrtega elementa.
Medtem ko je dostop do niza elementov hiter, medtem ko Povezani seznam traja linearno, je precej počasnejši.
Operacije, kot so vstavljanje in brisanje v nizih, porabijo veliko časa. Po drugi strani pa je uspešnost teh operacij na povezanih seznamih hitra.
Nizi so fiksne velikosti. Nasprotno pa so povezani seznami dinamični in prilagodljivi ter se lahko razširijo in zmanjšajo njegovo velikost.
V matriki je pomnilnik dodeljen med časom prevajanja, medtem ko je na povezanem seznamu dodeljen med izvajanjem ali izvajalnim časom.
Elementi se zaporedno shranjujejo v nizih, medtem ko se naključno shranjujejo na povezanih seznamih.
Zahteva po pomnilniku je manj zaradi dejanskih podatkov, shranjenih v indeksu v matriki. V primerjavi s tem obstaja potreba po več pomnilnika na povezanih seznamih zaradi shranjevanja dodatnih naslednjih in prejšnjih elementov referenciranja.
Poleg tega je izkoriščenost pomnilnika v matriki neučinkovita. Nasprotno pa je izkoristek pomnilnika učinkovit v polju.

Zaključek

Array in Linked liste so vrste podatkovnih struktur, ki se razlikujejo po svoji strukturi, metodah dostopa in manipulacije, zahtevi po pomnilniku in uporabi. In imajo posebno prednost in pomanjkljivost glede njegovega izvajanja. Posledično je mogoče uporabiti eno ali drugo.