Šioje pamokoje sužinosite įvairių tipų susietus sąrašus. Be to, C susietojo sąrašo įgyvendinimą rasite.
Prieš sužinodami apie susieto sąrašo tipą, įsitikinkite, kad žinote apie „LinkedList“ duomenų struktūrą.
Yra trys įprasti susietų sąrašų tipai.
- Vienas susietas sąrašas
- Dvigubai susietas sąrašas
- Apskritasis susietasis sąrašas
Vienas susietas sąrašas
Tai yra labiausiai paplitusi. Kiekvienas mazgas turi duomenų ir rodyklę į kitą mazgą.
Atskirai susietas sąrašas
Mazgas vaizduojamas kaip:
struct node ( int data; struct node *next; )
Trijų narių atskirai susietą sąrašą galima sukurti taip:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Dvigubai susietas sąrašas
Pridedame žymeklį prie ankstesnio mazgo dvigubai susietame sąraše. Taigi galime eiti į abi puses: pirmyn arba atgal.
Dvigubai susietas sąrašas
Mazgas vaizduojamas kaip
struct node ( int data; struct node *next; struct node *prev; )
Trijų narių dvigubai susietas sąrašas gali būti sukurtas kaip
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; one->prev = NULL; two->next = three; two->prev = one; three->next = NULL; three->prev = two; /* Save address of first node in head */ head = one;
Apskritasis susietasis sąrašas
Apskritasis susietasis sąrašas yra susieto sąrašo, kuriame paskutinis elementas susietas su pirmuoju, variantas. Tai suformuoja apskritą kilpą.
Apskritas susietas sąrašas
Apskritasis susietasis sąrašas gali būti susietas atskirai arba dvigubai.
- atskirai susietam sąrašui kitas paskutinio elemento žymeklis nurodo pirmąjį elementą
- Dvigubai susietame sąraše pirmojo elemento ankstesnis žymeklis taip pat nurodo paskutinį elementą.
Trijų narių žiedinį atskirai susietą sąrašą galima sukurti taip:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = one; /* Save address of first node in head */ head = one;
