Pole je v podstate súbor podobných dátových objektov uložených v polohách sekvenčnej pamäte pod spoločnou hlavičkou alebo názvom premennej.
Zatiaľ čo prepojený zoznam je dátová štruktúra, ktorá obsahuje sekvenciu prvkov, kde každý prvok je prepojený s jeho ďalším prvkom. V prvku prepojeného zoznamu sú dve polia. Jedným z nich je údajové pole a iné pole odkazu. Údajové pole obsahuje skutočnú hodnotu, ktorá sa má uložiť a spracovať. Okrem toho pole odkazu obsahuje adresu nasledujúcej údajovej položky v prepojenom zozname. Adresa použitá na prístup k určitému uzlu je známa ako ukazovateľ.
Ďalším významným rozdielom medzi poľom a prepojeným zoznamom je to, že Array má pevnú veľkosť a vyžaduje sa, aby bol deklarovaný ako predtým, ale Linked List nie je obmedzený na veľkosť a rozširovať a kontrahovať počas vykonávania.
Porovnávacia tabuľka
| Základ pre porovnanie | rad | Prepojený zoznam |
|---|---|---|
| základné | Ide o konzistentnú sadu pevného počtu dátových položiek. | Ide o objednanú sadu obsahujúcu premenlivý počet dátových položiek. |
| veľkosť | Špecifikované počas vyhlásenia. | Nie je potrebné špecifikovať; rast a zmenšovanie počas vykonávania. |
| Uloženie úložiska | Umiestnenie prvku je priradené počas kompilácie. | Položka prvku je priradená počas doby spustenia. |
| Poradie prvkov | Uložené postupne | Uložené náhodne |
| Prístup k prvku | Priamy alebo náhodný prístup, tj Zadajte index alebo index. | Sekvenčne prístupný, tj traverz začína od prvého uzla v zozname ukazovateľom. |
| Vloženie a odstránenie prvku | Pomalá relatívna zmena je potrebná. | Jednoduchšie, rýchlejšie a efektívnejšie. |
| vyhľadávanie | Binárne vyhľadávanie a lineárne vyhľadávanie | lineárne vyhľadávanie |
| Požadovaná pamäť | menej | viac |
| Využitie pamäte | neúčinný | účinný |
Definícia poľa
Pole je definované ako súbor určitého počtu homogénnych prvkov alebo dátových položiek. Znamená to, že pole môže obsahovať iba jeden typ údajov, buď celé čísla, všetky čísla s pohyblivou čiarkou alebo všetky znaky. Vyhlásenie poľa je nasledovné:
int a [10];
Kde int špecifikuje dátový typ alebo typy prvkov ukladá pole. "A" je názov poľa a číslo špecifikované vnútri hranatých zátvoriek je počet prvkov, ktoré pole môže uložiť, toto sa tiež nazýva veľkosť alebo dĺžka poľa.
Pozrime sa na niektoré pojmy, ktoré sa majú pamätať na poli:
- Jednotlivé prvky poľa môžu byť prístupné opisom názvu poľa, po ktorom nasleduje index alebo index (určujúci umiestnenie prvku v poli) vnútri hranatých zátvoriek. Napríklad, ak chceme načítať 5. prvok poľa, musíme napísať vyhlásenie a [4].
- V každom prípade budú prvky poľa uložené v po sebe idúcom mieste pamäte.
- Prvý prvok poľa má index nula [0]. Znamená to, že prvý a posledný prvok bude špecifikovaný ako [0] a [9].
- Počet prvkov, ktoré môžu byť uložené v poli, tj veľkosť poľa alebo jeho dĺžka, je daná nasledujúcou rovnicou:
(horná hranica - dolná hranica) + 1
Pre vyššie uvedené pole by bolo (9-0) + 1 = 10. Kde 0 je dolná hranica poľa a 9 je horná hranica poľa. - Polia môžu byť čítané alebo zapísané cez slučku. Ak čítame jednorozmerné pole, vyžaduje jednu slučku na čítanie a inú pre písanie (tlač) poľa, napríklad:
a. Pre čítanie poľa
pre (i = 0; i <= 9; i ++)
{scanf ("% d", & a [i]); }
b. Pri písaní poľa
pre (i = 0; i <= 9; i ++)
{printf ("% d", a [i]); } - V prípade 2-D poľa by to vyžadovalo dve slučky a podobne n-rozmerné pole by potrebovalo n slučky.
Operácie vykonávané na poli sú:
- Vytvorenie poľa
- Prechod po poli
- Vloženie nových prvkov
- Vymazanie požadovaných prvkov.
- Úprava prvku.
- Zlúčenie polí
príklad
Nasledujúci program znázorňuje čítanie a zápis poľa.
#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 (); }
Definícia prepojeného zoznamu
Prepojený zoznam je konkrétny zoznam niektorých dátových prvkov prepojených s iným. V tomto každom prvku smeruje k ďalšiemu prvku, ktorý predstavuje logické usporiadanie. Každý prvok sa nazýva uzol, ktorý má dve časti.
INFO časť, ktorá ukladá informácie a POINTER, ktoré ukazujú na ďalší prvok. Ako viete pri ukladaní adresy, máme v C nazývané ukazovatele jedinečné dátové štruktúry. Preto druhé pole zoznamu musí byť typ ukazovateľa.
Typy prepojených zoznamov sú zoznamy s jednoduchým prepojením, zoznam s dvojitým prepojením, zoznam s okrúhlym prepojením, zoznam s dvojitým prepojením.
Operácie vykonávané na prepojenom zozname sú:
- stvorenia
- kríženie
- vloženie
- vymazanie
- vyhľadávanie
- zreťazenie
- zobraziť
príklad
Nasledujúci úryvok ilustruje vytvorenie prepojeného zoznamu:
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')); }
Kľúčové rozdiely medzi poľom a prepojeným zoznamom
- Pole je dátová štruktúra obsahuje kolekciu podobných dátových prvkov typu, zatiaľ čo prepojený zoznam sa považuje za primitívnu dátovú štruktúru, ktorá obsahuje súbor neusporiadaných prepojených prvkov známych ako uzly.
- V poli pole elementy patria indexy, tj ak sa chcete dostať do štvrtého prvku, musíte napísať názov premennej s jeho indexom alebo umiestnením v rámci štvorcového závorky.
V prepojenom zozname však musíte začať od hlavy a pracovať si až dovtedy, kým sa nedostanete k štvrtému prvku. - Prístup k prvku pole je rýchly, zatiaľ čo prepojený zoznam má lineárny čas, takže je pomerne pomalší.
- Operácie ako vloženie a vymazávanie v poliach spotrebúvajú veľa času. Na druhej strane výkon týchto operácií v prepojených zoznamoch je rýchly.
- Polia majú pevnú veľkosť. Naproti tomu prepojené zoznamy sú dynamické a flexibilné a môžu rozšíriť a zmenšiť svoju veľkosť.
- V poli je priradená pamäť počas kompilácie, kým je v prepojenom zozname priradená počas vykonávania alebo spustenia.
- Prvky sa ukladajú postupne do polí, pričom sú náhodne uložené v prepojených zoznamoch.
- Požiadavka pamäte je menšia v dôsledku skutočných údajov uložených v indexe v poli. V porovnaní s tým existuje potreba väčšej pamäte v prepojených zoznamoch v dôsledku ukladania ďalších nasledujúcich a predchádzajúcich referenčných prvkov.
- Okrem toho je využitie pamäte v poli neúčinné. Naopak, využitie pamäte je účinné v poli.
záver
Pole a prepojené zoznamy sú typy dátových štruktúr, ktoré sa líšia v štruktúre, prístupových a manipulačných metódach, požiadavkách na pamäť a využití. A majú mimoriadnu výhodu a nevýhodu vo svojej implementácii. V dôsledku toho môže byť jeden použitý podľa potreby.
