Forskel mellem matrix og tilknyttet liste
Indhold
- Sammenligningstabel
- Definition af Array
- Lad os se på nogle af de begreber, der skal huskes om matriser:
- Operationer, der udføres på arrays, er:
- Eksempel
- Definition af linket liste
- Handlinger, der udføres på Linked List, er:
- Eksempel
- Konklusion
Den største forskel mellem Array og Tilknyttet liste med hensyn til deres struktur. Arrays er indeksbaseret datastruktur, hvor hvert element er knyttet til et indeks. På den anden side er den linkede liste afhængig af referencer hvor hver knude består af dataene og referencerne til det forrige og næste element.
Grundlæggende er en matrix et sæt af lignende dataobjekter, der er gemt i sekventielle hukommelsessteder under en fælles overskrift eller et variabelt navn.
Mens en tilknyttet liste er en datastruktur, der indeholder en sekvens af de elementer, hvor hvert element er knyttet til det næste element. Der er to felter i et element i den linkede liste. Det ene er Datafelt, og det andet er linkfelt, Datafelt indeholder den aktuelle værdi, der skal gemmes og behandles. Endvidere indeholder linkfeltet adressen på det næste dataelement på den linkede liste. Den adresse, der bruges til at få adgang til en bestemt knude er kendt som en markør.
En anden markant forskel mellem en matrix og en linket liste er, at Array har en fast størrelse og kræves erklæret forud, men den tilknyttede liste er ikke begrænset til størrelse og udvidelse og kontrakt under udførelsen.
- Sammenligningstabel
- Definition
- Vigtige forskelle
- Konklusion
Sammenligningstabel
| Grundlag for sammenligning | Array | Tilknyttet liste |
|---|---|---|
| Grundlæggende | Det er et konsistent sæt af et fast antal dataelementer. | Det er et ordnet sæt, der indeholder et variabelt antal dataelementer. |
| Størrelse | Specificeret under erklæringen. | Ingen grund til at specificere; vokse og skrumpe under udførelse. |
| Lagringstildeling | Elementplacering tildeles under kompileringstiden. | Elementposition tildeles under kørselstid. |
| Elementernes rækkefølge | Opbevares fortløbende | Gemt tilfældigt |
| Adgang til elementet | Direkte eller tilfældigt adgang, dvs. specificere matrixindekset eller abonnementet. | Sekventielt adgang, dvs. Traverse startende fra den første knude på listen af markøren. |
| Indsættelse og sletning af element | Langsomt relativt, da skift er påkrævet. | Nemmere, hurtig og effektiv. |
| Søger | Binær søgning og lineær søgning | lineær søgning |
| Hukommelse kræves | mindre | Mere |
| Hukommelsesudnyttelse | Ineffektiv | Effektiv |
Definition af Array
En matrix er defineret som et sæt af et bestemt antal homogene elementer eller dataelementer. Det betyder, at en matrix kun kan indeholde en type data, enten alle heltal, alle flydende numre eller alle tegn. Erklæring om en matrix er som følger:
int a;
Hvor int specificerer datatypen eller typeelementerne matrixlagre. "A" er navnet på en matrix, og det nummer, der er angivet inden i de firkantede parenteser, er antallet af elementer, som en matrix kan gemme, dette kaldes også størrelse eller længde på matrixen.
Lad os se på nogle af de begreber, der skal huskes om matriser:
- De enkelte elementer i en matrix kan fås ved at beskrive array-navnet, efterfulgt af et indeks eller et underskrift (bestemme placeringen af elementet i arrayet) inden i de firkantede parenteser. For at hente det femte element i arrayet, skal vi for eksempel skrive en erklæring a.
- Under alle omstændigheder gemmes elementerne i en matrix på en fortløbende hukommelsesplacering.
- Det allerførste element i arrayet har indeks nul. Det betyder, at det første og det sidste element specificeres som henholdsvis en og en.
- Antallet af elementer, der kan gemmes i en matrix, dvs. størrelsen på en matrix eller dens længde er angivet ved følgende ligning:
(øvre grænse-nedre grænse) + 1
For ovenstående array ville det være (9-0) + 1 = 10. Hvor 0 er den nedre grænse af matrixen, og 9 er den øvre grænse af matrixen. - Arrays kan læses eller skrives gennem løkken. Hvis vi læser den endimensionelle matrix, kræver den en løkke til læsning og anden til skrivning (ing) af matrixen, for eksempel:
en. Til læsning af en matrix
for (i = 0; i <= 9; i ++)
{scanf (“% d”, & a); }
b. Til at skrive en matrix
for (i = 0; i <= 9; i ++)
{f (“% d”, a); } - I tilfælde af en 2-D-matrix kræver den to sløjfer, og lignende n-dimensionelle array ville have brug for n løkker.
Operationer, der udføres på arrays, er:
- Oprettelse af matrix
- Kryds over en matrix
- Indsættelse af nye elementer
- Sletning af nødvendige elementer.
- Ændring af et element.
- Fusion af arrays
Eksempel
Det følgende program illustrerer læsning og skrivning af matrixen.
#omfatte
#omfatte
void main ()
{
int a, i;
f ("Indtast matrixen");
for (i = 0; i <= 9; i ++)
{
scanf ("% d", & a);
}
f ("Indtast matrixen");
for (i = 0; i <= 9; i ++)
{
f ("% d n", a);
}
getch ();
}
Definition af linket liste
Tilknyttet liste er en bestemt liste over nogle dataelementer, der er knyttet til hinanden. I dette peger hvert element på det næste element, der repræsenterer den logiske rækkefølge. Hvert element kaldes en knude, der har to dele.
INFO-del, der gemmer informationen og POINTER, der peger på det næste element. Som du ved til lagring af adresse, har vi en unik datastruktur i C kaldet pointers. Derfor skal det andet felt på listen være en piktype.
Typer af sammenkoblede lister er enkeltstående link, dobbeltkædet liste, cirkulær link liste, cirkulær dobbeltkoblet liste.
Handlinger, der udføres på Linked List, er:
- Skabelse
- gennemkører
- Indsættelse
- Sletning
- Søger
- sammenkædning
- Skærm
Eksempel
Følgende kodestykke illustrerer oprettelsen af en linket liste:
strukt knude
{
int num;
stude node * næste;
}
start = NULL;
ugyldig oprettelse ()
{
typedef struct knude NODE;
NODE * p, * q;
char valg;
først = NULL;
gøre
{
p = (NODE *) malloc (størrelse af (NODE));
f ("Indtast dataelementet n");
scanf ("% d", & p -> num);
hvis (p == NULL)
{
q = start;
mens (q -> næste! = NULL)
{q = q -> næste
}
p -> næste = q -> næste;
q -> = p;
}
andet
{
p -> næste = start;
start = p;
}
f ("Vil du fortsætte (skriv y eller n)? n");
scanf ("% c", & valg);
}
mens ((valg == y) || (valg == Y));
}
- En matrix er datastrukturen indeholder en samling af dataelementer af lignende type, hvorimod den tilknyttede liste betragtes som ikke-primitiv datastruktur indeholder en samling af uordnede linkede elementer kendt som noder.
- I matrixen hører elementerne til indekser, dvs. hvis du vil komme ind i det fjerde element, skal du skrive variabelnavnet med dets indeks eller placering i den firkantede beslag.
På en sammenkoblet liste skal du dog starte fra hovedet og arbejde dig igennem, indtil du kommer til det fjerde element. - Selvom det er hurtigt at få adgang til et elementarray, mens den tilknyttede liste tager lineær tid, er det ganske lidt langsommere.
- Handlinger som indsættelse og sletning i arrays bruger meget tid. På den anden side er udførelsen af disse operationer i tilknyttede lister hurtig.
- Arrays er af fast størrelse. I modsætning hertil er tilknyttede lister dynamiske og fleksible og kan udvide og kontraktens størrelse.
- I en matrix tildeles hukommelse under kompileringstiden, mens den i en tilknyttet liste tildeles under udførelse eller kørselstid.
- Elementer gemmes fortløbende i matriser, mens de gemmes tilfældigt i lænkede links.
- Kravet til hukommelse skyldes mindre, at faktiske data gemmes i indekset i matrixen. I modsætning hertil er der behov for mere hukommelse i tilknyttede lister på grund af lagring af yderligere næste og tidligere henvisningselementer.
- Derudover er hukommelsesudnyttelsen ineffektiv i matrixen. Omvendt er hukommelsesudnyttelse effektiv i matrixen.
Konklusion
Array- og sammenkoblede lister er typerne af datastrukturer, der er forskellige i deres struktur, adgangs- og manipuleringsmetoder, hukommelseskrav og anvendelse. Og har særlig fordel og ulempe i forhold til dens implementering. Følgelig kan begge sider bruges efter behov.
