logo

Saistītais saraksts

  • Saistīto sarakstu var definēt kā izsaukto objektu kolekciju mezgli kas tiek nejauši saglabāti atmiņā.
  • Mezglā ir divi lauki, t.i., dati, kas tiek glabāti konkrētajā adresē, un rādītājs, kas satur nākamā mezgla adresi atmiņā.
  • Saraksta pēdējā mezglā ir rādītājs uz nulli.
DS saistītais saraksts

Saistītā saraksta lietojumi

  • Sarakstam nav obligāti jāatrodas atmiņā. Mezgls var atrasties jebkurā vietā atmiņā un savienots kopā, lai izveidotu sarakstu. Tas nodrošina optimālu telpas izmantošanu.
  • saraksta lielums ir ierobežots līdz atmiņas apjomam, un tas nav iepriekš jādeklarē.
  • Saistītajā sarakstā nevar būt tukšs mezgls.
  • Mēs varam saglabāt primitīvu tipu vai objektu vērtības atsevišķi saistītajā sarakstā.

Kāpēc izmantot saistīto sarakstu masīvā?

Līdz šim mēs izmantojām masīva datu struktūru, lai sakārtotu elementu grupu, kas atsevišķi jāuzglabā atmiņā. Tomēr masīvam ir vairākas priekšrocības un trūkumi, kas jāzina, lai noteiktu datu struktūru, kas tiks izmantota visā programmā.

Masīvā ir šādi ierobežojumi:

  1. Masīva lielums ir iepriekš jāzina pirms tā izmantošanas programmā.
  2. Masīva lieluma palielināšana ir laikietilpīgs process. Ir gandrīz neiespējami paplašināt masīva izmēru izpildes laikā.
  3. Visi masīva elementi ir nepārtraukti jāsaglabā atmiņā. Jebkura elementa ievietošanai masīvā ir jāpārvieto visi tā priekšgājēji.

Saistītais saraksts ir datu struktūra, kas var pārvarēt visus masīva ierobežojumus. Saistītā saraksta izmantošana ir noderīga, jo

Android izstrādātāja režīma izslēgšana
  1. Tas dinamiski piešķir atmiņu. Visi saistītie saraksta mezgli tiek glabāti atmiņā nevienmērīgi un savienoti kopā ar rādītāju palīdzību.
  2. Izmēru noteikšana vairs nav problēma, jo mums nav jādefinē tā lielums deklarēšanas laikā. Saraksts tiek papildināts atbilstoši programmas pieprasījumam un ierobežots līdz pieejamajai atmiņas vietai.

Atsevišķi saistīts saraksts vai vienvirziena ķēde

Atsevišķi saistīto sarakstu var definēt kā sakārtotu elementu kopu. Elementu skaits var atšķirties atkarībā no programmas vajadzībām. Mezgls atsevišķi saistītajā sarakstā sastāv no divām daļām: datu daļas un saites daļas. Mezgla datu daļa glabā faktisko informāciju, kas jāatspoguļo mezglam, savukārt mezgla saites daļa saglabā tā tiešā pēcteča adresi.

Vienvirziena ķēdi vai atsevišķi saistītu sarakstu var šķērsot tikai vienā virzienā. Citiem vārdiem sakot, mēs varam teikt, ka katrs mezgls satur tikai nākamo rādītāju, tāpēc mēs nevaram šķērsot sarakstu pretējā virzienā.

skābes īpašības dbms

Apsveriet piemēru, kur skolēna iegūtās atzīmes trīs priekšmetos tiek saglabātas saistītā sarakstā, kā parādīts attēlā.

DS atsevišķi saistītais saraksts

Iepriekš redzamajā attēlā bultiņa apzīmē saites. Katra mezgla datu daļa satur studenta iegūtās atzīmes dažādās priekšmetā. Pēdējais mezgls sarakstā tiek identificēts ar nulles rādītāju, kas atrodas pēdējā mezgla adreses daļā. Saraksta datu daļā var būt tik daudz elementu, cik mums nepieciešams.

atsperu moduļi

Sarežģītība

Datu struktūra Laika sarežģītība Kosmosa pilnība
Vidēji Sliktākais Sliktākais
Piekļuve Meklēt Ievietošana Dzēšana Piekļuve Meklēt Ievietošana Dzēšana
Atsevišķi saistītais saraksts i(n) i(n) i (1) i (1) O(n) O(n) O(1) O(1) O(n)

Operācijas atsevišķi saistītajā sarakstā

Ir dažādas darbības, kuras var veikt atsevišķi piesaistītā sarakstā. Tālāk ir sniegts visu šādu darbību saraksts.

Mezglu izveide

 struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 

Ievietošana

Ievietošanu atsevišķi saistītā sarakstā var veikt dažādās pozīcijās. Pamatojoties uz ievietojamā jaunā mezgla pozīciju, ievietošana tiek iedalīta šādās kategorijās.

SN Darbība Apraksts
1 Ievietošana sākumā Tas ietver jebkura elementa ievietošanu saraksta sākumā. Mums tikai jāveic dažas saišu korekcijas, lai jaunais mezgls kļūtu par saraksta galveno vietu.
2 Ievietošana saraksta beigās Tas ietver ievietošanu saistītā saraksta pēdējā vietā. Jauno mezglu var ievietot kā vienīgo mezglu sarakstā vai to var ievietot kā pēdējo. Katrā scenārijā tiek īstenota atšķirīga loģika.
3 Ievietošana pēc norādītā mezgla Tas ietver ievietošanu aiz norādītā saistītā saraksta mezgla. Mums ir jāizlaiž vēlamais mezglu skaits, lai sasniegtu mezglu, pēc kura tiks ievietots jaunais mezgls. .

Dzēšana un pārvietošana

Mezgla dzēšanu no atsevišķi saistīta saraksta var veikt dažādās pozīcijās. Pamatojoties uz dzēšamā mezgla pozīciju, darbība tiek iedalīta šādās kategorijās.

SN Darbība Apraksts
1 Dzēšana sākumā Tas ietver mezgla dzēšanu no saraksta sākuma. Šī ir vienkāršākā darbība starp visām. Tam ir nepieciešamas tikai dažas korekcijas mezglu rādītājos.
2 Dzēšana saraksta beigās Tas ietver saraksta pēdējā mezgla dzēšanu. Saraksts var būt tukšs vai pilns. Dažādiem scenārijiem tiek īstenota atšķirīga loģika.
3 Dzēšana pēc norādītā mezgla Tas ietver mezgla dzēšanu pēc norādītā mezgla sarakstā. mums ir jāizlaiž vēlamais mezglu skaits, lai sasniegtu mezglu, pēc kura mezgls tiks dzēsts. Tas prasa sarakstu.
4 Šķērsošana Traversējot, mēs vienkārši apmeklējam katru saraksta mezglu vismaz vienu reizi, lai ar to veiktu kādu konkrētu darbību, piemēram, izdrukātu katra sarakstā esošā mezgla datu daļu.
5 Meklēšana Meklējot, mēs saskaņojam katru saraksta elementu ar doto elementu. Ja elements tiek atrasts kādā no atrašanās vietām, tiek atgriezta šī elementa atrašanās vieta, pretējā gadījumā tiek atgriezta null. .

Saistītais saraksts sadaļā C: Izvēlnes vadīta programma

 #include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('

*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
 5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
 Enter the location of the node after which you want to perform deletion 
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } 

Izvade:

 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9