Kort gezegd is een array een verzameling vergelijkbare gegevensobjecten die zijn opgeslagen op sequentiële geheugenlocaties onder een gemeenschappelijke kop of een variabelenaam.
Hoewel een gekoppelde lijst een gegevensstructuur is die een reeks elementen bevat waarbij elk element is gekoppeld aan het volgende element. Er zijn twee velden in een element van de gekoppelde lijst. Een daarvan is Gegevensveld en een ander is een koppelingsveld. Het gegevensveld bevat de werkelijke waarde die moet worden opgeslagen en verwerkt. Verder bevat het koppelingsveld het adres van het volgende gegevensitem in de gekoppelde lijst. Het adres dat wordt gebruikt om toegang te krijgen tot een bepaald knooppunt staat bekend als een aanwijzer.
Een ander significant verschil tussen een array en een gekoppelde lijst is dat Array een vaste grootte heeft en eerder moet worden gedeclareerd, maar Linked List is niet beperkt tot grootte en wordt uitgebreid en inkrimpt tijdens uitvoering.
Vergelijkingstabel
| Basis voor vergelijking | reeks | Gekoppelde lijst |
|---|---|---|
| basis- | Het is een consistente set van een vast aantal gegevensitems. | Het is een geordende set met een variabel aantal gegevensitems. |
| Grootte | Opgegeven tijdens de aangifte. | Niet nodig om op te geven; groeien en krimpen tijdens de uitvoering. |
| Opslagtoewijzing | Elementlocatie wordt toegewezen tijdens het compileren. | Elementpositie wordt toegewezen tijdens runtime. |
| Volgorde van de elementen | Achtereenvolgens opgeslagen | Willekeurig opgeslagen |
| Toegang tot het element | Direct of willekeurig geraadpleegd, dwz specificeer de array-index of het subscript. | Achtereenvolgens geopend, dwz Traverse starten vanaf het eerste knooppunt in de lijst door de aanwijzer. |
| Invoegen en verwijderen van element | Langzaam relatief omdat schakelen vereist is. | Gemakkelijker, snel en efficiënt. |
| Zoeken | Binair zoeken en lineair zoeken | lineair zoeken |
| Geheugen vereist | minder | Meer |
| Geheugengebruik | Niet effectief | doeltreffend |
Definitie van Array
Een array wordt gedefinieerd als een verzameling van een bepaald aantal homogene elementen of gegevensitems. Dit betekent dat een array slechts één type gegevens kan bevatten, alle gehele getallen, alle drijvende-kommagetallen of alle tekens. Declaratie van een array is als volgt:
int a [10];
Waar int specificeert het gegevenstype of type elementen array-opslag. "A" is de naam van een array en het binnen de vierkante haken aangegeven getal is het aantal elementen dat een array kan opslaan, dit wordt ook wel size of length van de array genoemd.
Laten we eens kijken naar enkele concepten die nog moeten worden onthouden over arrays:
- De afzonderlijke elementen van een array kunnen worden benaderd door de naam van de array te beschrijven, gevolgd door index of subscript (bepalen van de locatie van het element in de array) binnen de vierkante haken. Als u bijvoorbeeld het 5e element van de array wilt ophalen, moeten we een instructie a [4] schrijven.
- In elk geval worden de elementen van een array opgeslagen in een opeenvolgende geheugenlocatie.
- Het allereerste element van de array heeft index nul [0]. Het betekent dat het eerste en laatste element worden gespecificeerd als respectievelijk een [0] en een [9].
- Het aantal elementen dat kan worden opgeslagen in een array, dat wil zeggen de grootte van een array of de lengte ervan, wordt gegeven door de volgende vergelijking:
(bovengrens-ondergrens) + 1
Voor de bovenstaande array zou dit (9-0) + 1 = 10 zijn. Waarbij 0 de ondergrens van de array is en 9 de bovengrens van de array. - Arrays kunnen door de lus worden gelezen of geschreven. Als we de eendimensionale array lezen, is er één lus nodig voor lezen en andere voor het schrijven (afdrukken) van de array, bijvoorbeeld:
een. Voor het lezen van een array
voor (i = 0; i <= 9; i ++)
{scanf ("% d", & a [i]); }
b. Voor het schrijven van een array
voor (i = 0; i <= 9; i ++)
{printf ("% d", a [i]); } - In het geval van een 2-D array zou het twee lussen vereisen en een vergelijkbare n-dimensionale array zou n lussen nodig hebben.
Bewerkingen die worden uitgevoerd op arrays zijn:
- Creëren van array
- Een array doorkruisen
- Insertie van nieuwe elementen
- Verwijderen van vereiste elementen.
- Modificatie van een element.
- Samenvoegen van matrices
Voorbeeld
Het volgende programma illustreert het lezen en schrijven van de array.
#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 (); }
Definitie van gekoppelde lijst
Gekoppelde lijst is een specifieke lijst van sommige gegevenselementen die aan elkaar zijn gekoppeld. Hierin wijst elk element naar het volgende element dat de logische volgorde vertegenwoordigt. Elk element wordt een knoop genoemd, die uit twee delen bestaat.
INFO-gedeelte dat de informatie opslaat en POINTER die naar het volgende element verwijst. Zoals u weet voor het opslaan van het adres, hebben we een unieke datastructuur in C die pointers wordt genoemd. Daarom moet het tweede veld van de lijst een aanwijzertype zijn.
Typen gekoppelde lijsten zijn Singly-linked list, Doubly linked list, Circular linked list, Circular double linked list.
Bewerkingen uitgevoerd op gekoppelde lijst zijn:
- schepping
- doorkruisen
- Invoeging
- verwijdering
- Zoeken
- Aaneenschakeling
- tonen
Voorbeeld
Het volgende fragment illustreert het maken van een gekoppelde lijst:
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')); }
Belangrijkste verschillen tussen matrix en gekoppelde lijst
- Een array is de gegevensstructuur die een verzameling gegevenselementen van vergelijkbaar type bevat, terwijl de gekoppelde lijst wordt beschouwd als een niet-primitieve gegevensstructuur die een verzameling niet-geordende gekoppelde elementen bevat die bekend staan als knooppunten.
- In de array behoren de elementen tot indexen, dwz als u naar het vierde element wilt gaan, moet u de variabelenaam met de index of locatie binnen de vierkante haakjes schrijven.
In een gelinkte lijst moet je echter vanuit het hoofd beginnen en je doorwerken totdat je bij het vierde element bent. - Terwijl het gebruiken van een elementarray snel is, terwijl de gelinkte lijst een lineaire tijd in beslag neemt, is het een beetje langzamer.
- Bewerkingen zoals invoegen en verwijderen in arrays verbruiken veel tijd. Aan de andere kant is de uitvoering van deze bewerkingen in gekoppelde lijsten snel.
- Arrays hebben een vaste grootte. Gekoppelde lijsten zijn daarentegen dynamisch en flexibel en kunnen worden uitgebreid en kleiner worden.
- In een array wordt geheugen toegewezen tijdens het compileren, terwijl het in een gekoppelde lijst wordt toegewezen tijdens uitvoering of runtime.
- Elementen worden achtereenvolgens in arrays opgeslagen terwijl het willekeurig in gekoppelde lijsten wordt opgeslagen.
- De geheugenbehoefte is minder omdat de werkelijke gegevens worden opgeslagen in de index in de array. Daar tegenover staat dat er behoefte is aan meer geheugen in gekoppelde lijsten vanwege de opslag van aanvullende volgende en vorige verwijzingselementen.
- Bovendien is het geheugengebruik inefficiënt in de array. Omgekeerd is het geheugengebruik efficiënt in de array.
Conclusie
Matrix- en gelinkte lijsten zijn de soorten datastructuren verschillen in hun structuur, toegangs- en manipulatiemethoden, geheugenvereisten en gebruik. En hebben vooral voordeel en nadeel ten opzichte van de implementatie. Bijgevolg kan elk van deze vanaf behoefte worden gebruikt.
