Šajā apmācībā jūs uzzināsiet dažādus saistīto sarakstu veidus. Saistītā saraksta ieviešanu atradīsit arī C.
Pirms uzzināt par saistītā saraksta veidu, pārliecinieties, vai zināt par LinkedList datu struktūru.
Saistītajam sarakstam ir trīs izplatīti veidi.
- Atsevišķi saistīts saraksts
- Apšaubāmi saistīts saraksts
- Apkārtraksts Saistīts saraksts
Atsevišķi saistīts saraksts
Tas ir visizplatītākais. Katrā mezglā ir dati un rādītājs uz nākamo mezglu.
Atsevišķi saistīts saraksts
Mezgls tiek attēlots kā:
struct node ( int data; struct node *next; )
Trīs locekļu atsevišķi saistītu sarakstu var izveidot kā:
/* 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;
Apšaubāmi saistīts saraksts
Divkārši saistītā sarakstā mēs pievienojam rādītāju iepriekšējam mezglam. Tādējādi mēs varam iet jebkurā virzienā: uz priekšu vai atpakaļ.
Divreiz saistīts saraksts
Mezgls tiek attēlots kā
struct node ( int data; struct node *next; struct node *prev; )
Trīs dalībnieku divkārši saistītu sarakstu var izveidot kā
/* 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;
Apkārtraksts Saistīts saraksts
Apkārtraksts saistīts saraksts ir saistīts saraksta variants, kurā pēdējais elements ir saistīts ar pirmo elementu. Tas veido apļveida cilpu.
Apkārtraksts saistīts saraksts
Apkārtraksts saistīts saraksts var būt vai nu atsevišķi, vai divkārši saistīts.
- atsevišķi saistītam sarakstam nākamais pēdējās vienības rādītājs norāda uz pirmo vienumu
- Divkārt saistītā sarakstā pirmās pozīcijas iepriekšējais rādītājs norāda arī uz pēdējo vienumu.
Trīs dalībnieku apkārtrakstu, kas saistīts ar vienu saiti, var izveidot kā:
/* 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;
