Apkārtraksts Saistīts saraksts: Priekšrocības ar C programmas piemēru

Satura rādītājs:

Anonim

Kas ir apļveida sasaistītais saraksts?

Apļveida sasaistītais saraksts ir mezglu secība, kas sakārtota tā, ka katru mezglu var piesaistīt sev. Šeit "mezgls" ir pašreferenciāls elements ar norādēm uz vienu vai diviem mezgliem tiešā tuvumā.

Zemāk ir riņķveida saistīto sarakstu attēls ar 3 mezgliem.

Šeit jūs varat redzēt, ka katrs mezgls ir retracable pats par sevi. Iepriekš parādītais piemērs ir apļveida atsevišķi saistīts saraksts.

Piezīme: Visvienkāršākais apļveida saistīto saraksts ir mezgls, kas izseko tikai sev, kā parādīts

Šajā apkārtraksta saistītā saraksta apmācībā jūs uzzināsiet:

  • Kas ir apļveida sasaistītais saraksts?
  • Pamata darbības
  • Ievietošanas darbība
  • Dzēšanas darbība
  • Apļveida saistītā saraksta šķērsošana
  • Apļveida saistītā saraksta priekšrocības
  • Atsevišķi saistīts saraksts kā apļveida sasaistītais saraksts
  • Cirkulārā saistītā saraksta lietojumi

Pamata darbības

Apļveida saistīto sarakstu pamatdarbības ir šādas:

  1. Ievietošana
  2. Dzēšana un
  3. Pārceļošana
  • Ievietošana ir mezgla ievietošana noteiktā vietā apļveida saistīto sarakstā.
  • Dzēšana ir esoša mezgla noņemšana no saistītā saraksta. Mezglu var identificēt pēc tā vērtības rašanās vai atrašanās vietas.
  • Apļveida saistītā saraksta šķērsošana ir visa saistītā saraksta satura parādīšana un atgriešanās pie avota mezgla.

Nākamajā sadaļā jūs sapratīsit mezgla ievietošanu un iespējamos ievietošanas veidus cirkulārajā, tikai saistīto sarakstā.

Ievietošanas darbība

Sākumā jums jāizveido viens mezgls, kas norāda uz sevi, kā parādīts šajā attēlā. Bez šī mezgla ievietošana izveido pirmo mezglu.

Tālāk ir divas iespējas:

  • Ievietošana apļveida saistītā saraksta pašreizējā vietā. Tas atbilst ievietošanai parastā vienskaitļa saistītā saraksta beigās. Apkārtraksts saistītajā sarakstā sākums un beigas ir vienādas.
  • Ievietošana aiz indeksēta mezgla. Mezgls jāidentificē ar indeksa numuru, kas atbilst tā elementa vērtībai.

Ievietošanai apļveida saistītā saraksta sākumā / beigās, tas ir, vietā, kur tika pievienots pirmais mezgls,

  • Jums būs jāpārtrauc esošā pašsaite ar esošo mezglu
  • Jaunā mezgla nākamais rādītājs būs saistīts ar esošo mezglu.
  • Pēdējā mezgla nākamais rādītājs norādīs uz ievietoto mezglu.

PIEZĪME. Rādītāju, kas ir marķiera šablons vai apļa sākums / beigas, var mainīt. Tas joprojām atgriezīsies tajā pašā mezglā, kas tiks šķērsots, apspriežot iepriekš.

Turpmāk parādīti a) i-iii soļi:

(Esošais mezgls)

1. SOLIS. Pārtrauciet esošo saiti

2. SOLIS) Izveidojiet pārsūtīšanas saiti (no jauna mezgla uz esošu)

3. SOLIS) Izveidojiet cilpas saiti uz pirmo mezglu

Pēc tam mēģināsit ievietot aiz mezgla.

Piemēram, aiz mezgla ar “VALUE0” ievietosim “VALUE2”. Pieņemsim, ka sākumpunkts ir mezgls ar “VALUE0”.

  • Jums būs jāpārtrauc līnija starp pirmo un otro mezglu un starp tām jānovieto mezgls ar “VALUE2”.
  • Pirmā mezgla nākamajam rādītājam jābūt saistītam ar šo mezglu, un šī mezgla nākamajam rādītājam jābūt saistītam ar agrāko otro mezglu.
  • Pārējā vienošanās paliek nemainīga. Visi mezgli ir retrospektīvi paši sev.

PIEZĪME. Tā kā ir ciklisks izvietojums, mezgla ievietošana ietver to pašu procedūru jebkuram mezglam. Rādītājs, kas pabeidz ciklu, pabeidz ciklu tāpat kā jebkurš cits mezgls.

Tas parādīts zemāk:

(Pieņemsim, ka ir tikai divi mezgli. Šis ir niecīgs gadījums)

1. SOLIS) Noņemiet iekšējo saiti starp savienotajiem mezgliem

2. SOLIS) Pievienojiet kreisās puses mezglu jaunajam

3. SOLIS) Pievienojiet jauno mezglu labās puses mezglam.

Dzēšanas darbība

Pieņemsim 3 mezglu apļveida saistīto sarakstu. Dzēšanas gadījumi ir norādīti zemāk:

  • Pašreizējā elementa dzēšana
  • Dzēšana pēc elementa.

Dzēšana sākumā / beigās:

  1. Pārvietojieties uz pirmo mezglu no pēdējā mezgla.
  2. Lai izdzēstu no beigām, jābūt tikai vienam šķērsošanas solim, sākot no pēdējā mezgla līdz pirmajam.
  3. Dzēsiet saiti starp pēdējo un nākamo mezglu.
  4. Saistiet pēdējo mezglu ar nākamo pirmā mezgla elementu.
  5. Atbrīvojiet pirmo mezglu.

(Esošā iestatīšana)

1. SOLIS ) Noņemiet apļveida saiti

SOLIS 2) Noņemiet saiti starp pirmo un nākamo, saistiet pēdējo mezglu ar mezglu, kas seko pirmajam

3. SOLIS) Atbrīvojiet / sadaliet pirmo mezglu

Dzēšana pēc mezgla:

  1. Traverss līdz nākamajam mezglam ir dzēšamais mezgls.
  2. Pārvietojieties uz nākamo mezglu, novietojot rādītāju uz iepriekšējā mezgla.
  3. Savienojiet iepriekšējo mezglu ar mezglu aiz pašreizējā mezgla, izmantojot tā nākamo rādītāju.
  4. Atbrīvojiet pašreizējo (svītroto) mezglu.

1. SOLIS. Pieņemsim, ka mums ir jāizdzēš mezgls ar vērtību “VALUE1”.

2. SOLIS) Noņemiet saiti starp iepriekšējo un pašreizējo mezglu. Saistiet tā iepriekšējo mezglu ar nākamo mezglu, uz kuru norāda pašreizējais mezgls (ar VALUE1).

3. SOLIS) Atbrīvojiet vai sadaliet pašreizējo mezglu.

Apļveida saistītā saraksta šķērsošana

Lai šķērsotu apļveida saistīto sarakstu, sākot no pēdējā rādītāja, pārbaudiet, vai pats pēdējais rādītājs ir NULL. Ja šis nosacījums ir kļūdains, pārbaudiet, vai tajā ir tikai viens elements. Pretējā gadījumā pārvietojieties, izmantojot pagaidu rādītāju, līdz pēdējais rādītājs tiek sasniegts vēlreiz vai tik reižu, cik nepieciešams, kā parādīts zemāk esošajā GIF.

Apļveida saistītā saraksta priekšrocības

Dažas no apļveida saistīto sarakstu priekšrocībām ir:

  1. Kodā nav nepieciešama NULL piešķiršana. Apkārtraksts nekad nenorāda uz NULL rādītāju, ja vien tas nav pilnībā sadalīts.
  2. Apļveida saistītie saraksti ir izdevīgi beigu darbībām, jo ​​sākums un beigas sakrīt. Tādi algoritmi kā Round Robin plānošana var kārtīgi novērst procesus, kuri ir rindā riņķveidīgi, nesaskaroties ar nokareniem vai NULL atsauces rādītājiem.
  3. Apļveida sasaistītais saraksts veic arī visas atsevišķi saistītā saraksta regulārās funkcijas. Patiesībā zemāk aplūkotie apļveida divkārši saistītie saraksti var pat novērst vajadzību pēc pilnmetrāžas šķērsošanas elementa atrašanai. Šis elements būtu tikai tieši pretējs sākumam, aizpildot tikai pusi no saistītā saraksta.

Atsevišķi saistīts saraksts kā apļveida sasaistītais saraksts

Mēs iesakām mēģināt izlasīt un ieviest zemāk esošo kodu. Tas parāda rādītāja aritmētiku, kas saistīta ar apļveida saistītajiem sarakstiem.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Koda skaidrojums:

  1. Pirmās divas koda rindas ir nepieciešamie iekļauti galvenes faili.
  2. Nākamajā sadaļā ir aprakstīta katra pašreferenciālā mezgla struktūra. Tajā ir tāda paša veida vērtība un rādītājs kā struktūrai.
  3. Katra struktūra atkārtoti saista ar tāda paša veida struktūras objektiem.
  4. Ir dažādi funkciju prototipi:
    1. Elementa pievienošana tukšam saistītajam sarakstam
    2. Iekļaušana apļveida sasaistītā saraksta pašreizējā pozīcijā.
    3. Ievietošana pēc konkrētas indeksētas vērtības saistītajā sarakstā.
    4. Noņemšana / dzēšana pēc konkrētas indeksētās vērtības saistītajā sarakstā.
    5. Notiek noņemšana apļveida saistītā saraksta pašreizējā pozīcijā
  5. Pēdējā funkcija izdrukā katru elementu caur apļveida šķērsošanu jebkurā saistītā saraksta stāvoklī.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Koda skaidrojums:

  1. Kodam addEmpty piešķiriet tukšu mezglu, izmantojot malloc funkciju.
  2. Šajā mezglā ievietojiet datus mainīgajā temp.
  3. Piešķiriet un saistiet vienīgo mainīgo ar temp mainīgo
  4. Atgrieziet pēdējo elementu galvenajā () / lietojumprogrammas kontekstā.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Koda skaidrojums

  1. Ja nav neviena elementa, kuru ievietot, pārliecinieties, vai esat to pievienojis tukšam sarakstam un atgrieziet vadību.
  2. Izveidojiet pagaidu elementu, kuru ievietot aiz pašreizējā elementa.
  3. Saistiet rādītājus, kā parādīts.
  4. Atgrieziet pēdējo rādītāju tāpat kā iepriekšējā funkcijā.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Koda skaidrojums:

  1. Ja sarakstā nav neviena elementa, ignorējiet datus, pievienojiet pašreizējo vienumu kā pēdējo vienumu sarakstā un atgrieziet vadību
  2. Katrai iterācijai ciklā do-while pārliecinieties, ka ir kāds iepriekšējais rādītājs, kas satur pēdējo šķērsoto rezultātu.
  3. Tikai pēc tam var notikt nākamā šķērsošana.
  4. Ja dati ir atrasti vai temp sasniedz pēdējo rādītāju, do-while izbeidzas. Nākamā koda sadaļa izlemj, kas jādara ar vienumu.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Koda skaidrojums:

  1. Ja viss saraksts ir šķērsots, tomēr vienums nav atrasts, parādiet ziņojumu "Vienums nav atrasts" un pēc tam atgrieziet vadību zvanītājam.
  2. Ja ir atrasts mezgls un / vai mezgls vēl nav pēdējais, izveidojiet jaunu mezglu.
  3. Saistiet iepriekšējo mezglu ar jauno. Saistiet pašreizējo mezglu ar temp (pārvietošanās mainīgais).
  4. Tas nodrošina, ka elements tiek ievietots ap konkrēto mezglu apļveida saistīto sarakstā. Atgriezieties pie zvanītāja.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Koda skaidrojums

  1. Lai noņemtu tikai pēdējo (pašreizējo) mezglu, pārbaudiet, vai šis saraksts ir tukšs. Ja tā ir, tad nevienu elementu nevar noņemt.
  2. Temp mainīgais vienkārši pārvieto vienu saiti uz priekšu.
  3. Saistiet pēdējo rādītāju ar rādītāju pēc pirmā.
  4. Atbrīvojiet temp rādītāju. Tas izceļ nesaistīto pēdējo rādītāju.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Koda skaidrojums

  1. Tāpat kā ar iepriekšējo noņemšanas funkciju, pārbaudiet, vai nav elementa. Ja tā ir taisnība, nevienu elementu nevar noņemt.
  2. Rādītājiem tiek piešķirtas noteiktas pozīcijas, lai atrastu dzēšamo elementu.
  3. Rādītāji ir pavirzījušies viens aiz otra. (iepriekšējais aiz temp)
  4. Process turpinās, līdz tiek atrasts elements vai nākamais elements atgriežas līdz pēdējam rādītājam.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Programmas skaidrojums

  1. Ja elements ir atrasts pēc visa saistītā saraksta šķērsošanas, tiek parādīts kļūdas ziņojums, ka vienums netika atrasts.
  2. Pretējā gadījumā elements tiek noņemts un atbrīvots 3. un 4. darbībā.
  3. Iepriekšējais rādītājs ir saistīts ar adresi, kuru izdzēšamais elements (temp) norāda kā "nākamo".
  4. Tāpēc temp rādītājs tiek sadalīts un atbrīvots.
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Koda skaidrojums

  1. Palūrēšana vai šķērsošana nav iespējama, ja ir nepieciešama nulle. Lietotājam jāpiešķir vai jāievieto mezgls.
  2. Ja ir tikai viens mezgls, nav nepieciešams šķērsot, mezgla saturu var izdrukāt, un cilpa while netiek izpildīta.
  3. Ja ir vairāk nekā viens mezgls, tad temp izdrukā visu vienumu līdz pēdējam elementam.
  4. Brīdī, kad ir sasniegts pēdējais elements, cilpa tiek pārtraukta, un funkcija atgriež zvanu uz galveno funkciju.

Cirkulārā saistītā saraksta lietojumi

  • Apkārtējās plānošanas ieviešana sistēmas procesos un apļveida plānošana ātrgaitas grafikā.
  • Marķiera zvani plāno datortīklos.
  • To lieto displeja blokos, piemēram, veikalu dēļos, kur nepieciešama nepārtraukta datu šķērsošana.