Doporučená, 2021

Redakce Choice

Rozdíl mezi seznamem a propojeným seznamem

Hlavní rozdíl mezi Array a propojeným seznamem se týká jejich struktury. Pole jsou datová struktura založená na indexu, kde každý prvek spojený s indexem. Na druhé straně, Linkovaný seznam se spoléhá na odkazy, kde každý uzel sestává z dat a odkazů na předchozí a další prvek.

Pole je v podstatě sada podobných datových objektů uložených v sekvenčních paměťových umístěních pod společným názvem nebo názvem proměnné.

Zatímco propojený seznam je datová struktura, která obsahuje posloupnost prvků, kde je každý prvek spojen s dalším elementem. V prvku propojeného seznamu jsou dvě pole. Jedním z nich je datové pole a další pole je odkaz, pole Data obsahuje aktuální hodnotu, která má být uložena a zpracována. Pole propojení dále obsahuje adresu další datové položky v propojeném seznamu. Adresa použitá pro přístup k určitému uzlu je známa jako ukazatel.

Dalším významným rozdílem mezi polem a propojeným seznamem je, že Array má pevnou velikost a musí být deklarován jako předchozí, ale Link List není omezen na velikost a rozšiřovat a uzavírat smlouvy během provádění.

Srovnávací graf

Základ pro porovnáníArraySpojový seznam
ZákladníJedná se o konzistentní sadu pevného počtu datových položek.Jedná se o objednanou množinu obsahující variabilní počet datových položek.
VelikostSpecifikováno během prohlášení.Není třeba specifikovat; rostou a zmenšují se během provádění.
Přidělení úložištěUmístění prvku je přiděleno během kompilace.Poloha prvku je přiřazena během doby běhu.
Pořadí prvkůUloženo postupněUloženo náhodně
Přístup k prvkuPřímý nebo náhodný přístup, tj. Zadejte index pole nebo dolní index.Sekvenčně zpřístupněno, tj. Přechod od prvního uzlu v seznamu ukazatelem.
Vložení a vymazání prvkuPoměrně pomalá, protože je požadováno řazení.Snadnější, rychlejší a efektivnější.
VyhledáváníBinární vyhledávání a lineární vyhledávánílineární vyhledávání
Vyžaduje paměťméněVíce
Využití pamětiNeefektivníÚčinný

Definice pole

Pole je definováno jako množina určitého počtu homogenních prvků nebo datových položek. To znamená, že pole může obsahovat pouze jeden typ dat, buď celá čísla, všechna čísla s plovoucí desetinnou čárkou nebo všechny znaky. Prohlášení pole je následující:
int a [10];
Kde int specifikuje typ dat nebo typ pole pole obchody. „A“ je název pole a číslo uvedené v hranatých závorkách je počet prvků, které pole může uložit, což se také nazývá velikost nebo délka pole.

Podívejme se na některé koncepty, které je třeba si pamatovat o polích:

  • K jednotlivým prvkům pole lze přistupovat pomocí popisu názvu pole, za nímž následuje index nebo index (určující umístění prvku v poli) uvnitř hranatých závorek. Chcete-li například načíst 5. prvek pole, musíme napsat příkaz a [4].
  • V každém případě budou prvky pole uloženy v po sobě jdoucím paměťovém místě.
  • První prvek pole má index nula [0]. To znamená, že první a poslední prvek bude specifikován jako [0] a [9].
  • Počet prvků, které mohou být uloženy v poli, tj. Velikost pole nebo jeho délka je dána následující rovnicí:
    (horní ohraničená dolní hranice) + 1
    Pro výše uvedené pole by to bylo (9-0) + 1 = 10. Kde 0 je dolní mez pole a 9 je horní hranice pole.
  • Pole lze číst nebo zapisovat přes smyčku. Pokud čteme jednorozměrné pole, vyžaduje jednu smyčku pro čtení a další pro zápis (tisk) pole, například:
    A. Pro čtení pole
    pro (i = 0; i <= 9; i ++)
    {scanf (“% d”, a a [i]); }
    b. Pro zápis pole
    pro (i = 0; i <= 9; i ++)
    {printf (“% d”, a [i]); }
  • V případě 2-D pole by vyžadovalo dvě smyčky a podobně n-rozměrné pole by vyžadovalo n smyček.

Operace prováděné na polích jsou:

  1. Vytvoření pole
  2. Přechod pole
  3. Vložení nových prvků
  4. Vymazání požadovaných prvků.
  5. Modifikace prvku.
  6. Sloučení polí

Příklad

Následující program ilustruje čtení a zápis pole.

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

Definice propojeného seznamu

Propojený seznam je určitý seznam některých datových prvků, které jsou k sobě navzájem propojeny. V tomto bodě každý prvek ukazuje na další prvek, který představuje logické uspořádání. Každý prvek se nazývá uzel, který má dvě části.

INFO část, která ukládá informace a POINTER, která ukazuje na další prvek. Jak víte pro ukládání adresy, máme v C jedinečné datové struktury nazvané ukazatele. Druhé pole seznamu tedy musí být typu ukazatele.

Typy propojených seznamů jsou Seznamy s jednotlivým spojením, Seznam s dvojitou vazbou, Seznam s kruhovým spojením, Seznam s kruhovým spojením.

Operace prováděné na Link List jsou:

  1. Tvorba
  2. Traversing
  3. Vložení
  4. Smazání
  5. Vyhledávání
  6. Zřetězení
  7. Zobrazit

Příklad

Následující úryvek ukazuje vytvoření propojeného seznamu:

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

Klíčové rozdíly mezi polem a propojeným seznamem

  1. Pole je datová struktura obsahuje kolekci podobných datových prvků, zatímco Linkovaný seznam je považován za neprimitivní datovou strukturu obsahující kolekci neuspořádaných propojených prvků známých jako uzly.
  2. V poli prvky patří do indexů, tj. Pokud se chcete dostat do čtvrtého elementu, musíte napsat název proměnné s jeho indexem nebo umístěním v hranaté závorce.
    V propojeném seznamu však musíte začít od hlavy a pracovat si, dokud se nedostanete ke čtvrtému prvku.
  3. Při přístupu k elementovému poli je rychlý, zatímco Linkovaný seznam trvá lineárně, takže je poměrně pomalejší.
  4. Operace jako vkládání a mazání v polích spotřebovávají mnoho času. Na druhé straně je výkon těchto operací v seznamu odkazů rychlý.
  5. Pole mají pevnou velikost. Naproti tomu jsou propojené seznamy dynamické a flexibilní a mohou rozšířit a zkrátit svou velikost.
  6. V matici je paměť přiřazena během kompilace, zatímco v Linkovaném seznamu je přidělena během provádění nebo runtime.
  7. Prvky jsou uloženy postupně v polích, zatímco v odkazovaných seznamech jsou uloženy náhodně.
  8. Požadavek paměti je menší kvůli skutečným datům uloženým v indexu v poli. Na rozdíl od toho je potřeba více paměti v seznamech odkazů kvůli uložení dalších dalších a předchozích referenčních prvků.
  9. Využití paměti je navíc v poli neefektivní. Naopak využití paměti je efektivní v poli.

Závěr

Pole a propojené seznamy jsou typy datových struktur, které se liší svou strukturou, přístupovými a manipulačními metodami, požadavky na paměť a využitím. A mají zvláštní výhodu a nevýhodu nad jeho implementací. V důsledku toho může být jeden z nich použit podle potřeby.

Top