In questo articolo, comprenderemo in dettaglio le applicazioni degli elenchi collegati.

algoritmi di ricerca binaria

Cosa intendi per elenco collegato?

Una lista concatenata è una struttura di dati lineare composta da elementi chiamati nodi in cui ciascun nodo è composto da due parti: una parte di informazioni e una parte di collegamento, chiamata anche parte del puntatore successivo.

L'elenco collegato viene utilizzato in un'ampia varietà di applicazioni come

• Rappresentazione della manipolazione polinomiale
• Addizione di interi positivi lunghi
• Rappresentazione di matrici sparse
• Addizione di interi positivi lunghi
• Creazione della tabella dei simboli
• Lista di posta
• Gestione della memoria
• Allocazione collegata dei file
• Aritmetica a precisione multipla ecc

Manipolazione polinomiale

Le manipolazioni polinomiali sono una delle applicazioni più importanti delle liste concatenate. I polinomi sono una parte importante della matematica non intrinsecamente supportata come tipo di dati dalla maggior parte dei linguaggi. Un polinomio è una raccolta di termini diversi, ciascuno comprendente coefficienti ed esponenti. Può essere rappresentato utilizzando un elenco collegato. Questa rappresentazione rende efficiente la manipolazione dei polinomi.

Pur rappresentando un polinomio utilizzando una lista concatenata, ciascun termine polinomiale rappresenta un nodo nella lista concatenata. Per ottenere una migliore efficienza nell'elaborazione, assumiamo che il termine di ogni polinomio sia memorizzato all'interno della lista concatenata in ordine di esponente decrescente. Inoltre, non esistono due termini che abbiano lo stesso esponente e nessun termine ha coefficiente zero e senza coefficienti. Il coefficiente assume valore 1.

Ciascun nodo di una lista concatenata che rappresenta il polinomio costituisce tre parti:

• La prima parte contiene il valore del coefficiente del termine.
• La seconda parte contiene il valore dell'esponente.
• La terza parte, LINK, punta al termine successivo (nodo successivo).

Di seguito è mostrata la struttura di un nodo di una lista concatenata che rappresenta un polinomio:

Consideriamo un polinomio P(x) = 7x²+15x³- 2 volte²+ 9. Qui 7, 15, -2 e 9 sono i coefficienti e 4,3,2,0 sono gli esponenti dei termini del polinomio. Rappresentando questo polinomio utilizzando una lista concatenata, abbiamo

Osserva che il numero dei nodi è uguale al numero dei termini del polinomio. Quindi abbiamo 4 nodi. Inoltre, i termini vengono memorizzati per diminuire gli esponenti nell'elenco collegato. Tale rappresentazione del polinomio utilizzando elenchi concatenati rende molto semplici le operazioni come sottrazione, addizione, moltiplicazione, ecc. Sul polinomio.

Addizione di polinomi:

Per sommare due polinomi, attraversiamo la lista P e Q. Prendiamo i termini corrispondenti della lista P e Q e confrontiamo i loro esponenti. Se i due esponenti sono uguali, i coefficienti vengono sommati per creare un nuovo coefficiente. Se il nuovo coefficiente è uguale a 0, allora il termine viene eliminato, e se non è zero, viene inserito alla fine della nuova lista concatenata contenente il polinomio risultante. Se uno degli esponenti è maggiore dell'altro, il termine corrispondente viene immediatamente inserito nella nuova lista concatenata, e il termine con l'esponente minore viene tenuto confrontato con il termine successivo dell'altra lista. Se una lista termina prima dell'altra, il resto dei termini della lista più lunga viene inserito alla fine della nuova lista concatenata contenente il polinomio risultante.

Consideriamo un esempio per mostrare come viene eseguita la somma di due polinomi,

P(x) = 3x⁴+ 2x³- 4 volte²+7

Q(x) = 5x³+ 4x²- 5

Questi polinomi sono rappresentati utilizzando un elenco concatenato in ordine di esponenti decrescenti come segue:

Per generare una nuova lista concatenata per i polinomi risultanti che si forma dall'addizione dei polinomi dati P(x) e Q(x), eseguiamo i seguenti passaggi,

1. Attraversa le due liste P e Q ed esamina tutti i nodi.
2. Confrontiamo gli esponenti dei termini corrispondenti di due polinomi. Il primo termine dei polinomi P e Q contiene rispettivamente gli esponenti 4 e 3. Poiché l'esponente del primo termine del polinomio P è maggiore dell'altro polinomio Q, nella nuova lista viene inserito il termine avente esponente maggiore. Il nuovo elenco inizialmente appare come mostrato di seguito:
   
3. Confrontiamo quindi l'esponente del termine successivo della lista P con gli esponenti del termine attuale della lista Q. Poiché i due esponenti sono uguali, i loro coefficienti vengono sommati e aggiunti alla nuova lista come segue:
   
4. Poi passiamo al termine successivo delle liste P e Q e confrontiamo i loro esponenti. Poiché gli esponenti di entrambi questi termini sono uguali e dopo l'aggiunta dei loro coefficienti, otteniamo 0, quindi il termine viene eliminato e nessun nodo viene aggiunto alla nuova lista dopo questo,
   
5. Passando al termine successivo delle due liste, P e Q, troviamo che i termini corrispondenti hanno gli stessi esponenti pari a 0. Sommiamo i loro coefficienti e li aggiungiamo alla nuova lista per il polinomio risultante come mostrato di seguito:
   

Esempio:

Programma C++ per sommare due polinomi

 #include using namespace std; int max(int m, int n) { return (m &gt; n)? m: n; } int *add(int A[], int B[], int m, int n) { int size = max(m, n); int *sum = new int[size]; for (int i = 0; i<m; 4 6 i++) sum[i]="A[i];" for (int i="0;" i<n; +="B[i];" return sum; } void printpoly(int poly[], int n) { cout << poly[i]; if (i !="0)" 'x^' ; ' '; main() a[]="{" 5, 0, 10, }; b[]="{" 1, 2, m="sizeof(A)/sizeof(A[0]);" n="sizeof(B)/sizeof(B[0]);" 'first polynomial is 
'; printpoly(a, m); '
 second printpoly(b, n); *sum="add(A," b, m, size="max(m," sum of printpoly(sum, size); 0; < pre> <p> <strong>Explanation:</strong> </p> <p>In the above example, we have created an example of sum of two polynomial using array.</p> <p> <strong>Output:</strong> </p> <p>Below is the output of this example.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-9.webp" alt="Application of Linked List"> <h3>Addition of long positive integer using linked list</h3> <p>Most programming languages allow restrictions on the maximum value of integers stored. The maximum value of the largest integers is 32767, and the largest is 2147483647. Sometimes, applications such as security algorithms and cryptography require storing and manipulating integers of unlimited size. So in such a situation, it is desirable to use a linked list for storing and manipulating integers of arbitrary length.</p> <p>Adding long positive integers can be performed effectively using a circular linked list. As we know that when we add two long integers, the digits of the given numbers are individually traversed from right to left, and the corresponding digits of the two numbers along with a carry from prior digits sum are added. So to accomplish addition, we must need to know how the digits of a long integer are stored in a linked list.</p> <p>The digits of a long integer must be stored from right to left in a linked list so that the first node on the list contains the least significant digit, i.e., the rightmost digit, and the last node contains the most significant digit, i.e., leftmost digit.</p> <p> <strong>Example:</strong> An integer value 543467 can be represented using a linked list as</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-10.webp" alt="Application of Linked List"> <p> <strong>For performing the addition of two long integers, the following steps need to be followed:</strong> </p> <ul> <li>Traverse the two linked lists in parallel from left to right.</li> <li>During traversal, corresponding digits and a carry from prior digits sum are added, then stored in the new node of the resultant linked list.</li> </ul> <p>The first positive long integer 543467 is represented using a linked list whose first node is pointed by NUM1 pointer. Similarly, the second positive long integer 48315 is represented using the second linked list whose first node is pointed by NUM2 pointer. These two numbers are stored in the third linked list whose first node is pointed to by the RESULT pointer.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-11.webp" alt="Application of Linked List"> <h3>Example:</h3> <p> <strong>C++ program for addition of two polynomials using Linked Lists</strong> </p> <pre> #include #include using namespace std; struct Node { int coeff; int pow; struct Node* next; }; void create_node(int x, int y, struct Node** temp) { struct Node *r, *z; z = *temp; if (z == NULL) { r = (struct Node*)malloc(sizeof(struct Node)); r-&gt;coeff = x; r-&gt;pow = y; *temp = r; r-&gt;next = (struct Node*)malloc(sizeof(struct Node)); r = r-&gt;next; r-&gt;next = NULL; } else { r-&gt;coeff = x; r-&gt;pow = y; r-&gt;next = (struct Node*)malloc(sizeof(struct Node)); r = r-&gt;next; r-&gt;next = NULL; } } void polyadd(struct Node* poly1, struct Node* poly2, struct Node* poly) { while (poly1-&gt;next &amp;&amp; poly2-&gt;next) { if (poly1-&gt;pow &gt; poly2-&gt;pow) { poly-&gt;pow = poly1-&gt;pow; poly-&gt;coeff = poly1-&gt;coeff; poly1 = poly1-&gt;next; } else if (poly1-&gt;pow pow) { poly-&gt;pow = poly2-&gt;pow; poly-&gt;coeff = poly2-&gt;coeff; poly2 = poly2-&gt;next; } else { poly-&gt;pow = poly1-&gt;pow; poly-&gt;coeff = poly1-&gt;coeff + poly2-&gt;coeff; poly1 = poly1-&gt;next; poly2 = poly2-&gt;next; } poly-&gt;next = (struct Node*)malloc(sizeof(struct Node)); poly = poly-&gt;next; poly-&gt;next = NULL; } while (poly1-&gt;next || poly2-&gt;next) { if (poly1-&gt;next) { poly-&gt;pow = poly1-&gt;pow; poly-&gt;coeff = poly1-&gt;coeff; poly1 = poly1-&gt;next; } if (poly2-&gt;next) { poly-&gt;pow = poly2-&gt;pow; poly-&gt;coeff = poly2-&gt;coeff; poly2 = poly2-&gt;next; } poly-&gt;next = (struct Node*)malloc(sizeof(struct Node)); poly = poly-&gt;next; poly-&gt;next = NULL; } } void show(struct Node* node) { while (node-&gt;next != NULL) { printf(&apos;%dx^%d&apos;, node-&gt;coeff, node-&gt;pow); node = node-&gt;next; if (node-&gt;coeff &gt;= 0) { if (node-&gt;next != NULL) printf(&apos;+&apos;); } } } int main() { struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL; create_node(5, 2, &amp;poly1); create_node(4, 1, &amp;poly1); create_node(2, 0, &amp;poly1); create_node(-5, 1, &amp;poly2); create_node(-5, 0, &amp;poly2); printf(&apos;1st Number: &apos;); show(poly1); printf(&apos;
 2nd Number: &apos;); show(poly2); poly = (struct Node*)malloc(sizeof(struct Node)); polyadd(poly1, poly2, poly); printf(&apos;
 Sum of polynomial after addition: &apos;); show(poly); return 0; } </pre> <p> <strong>Explanation:</strong> </p> <p>In the above example, we have created an example of sum of two polynomial using linked list.</p> <p> <strong>Output:</strong> </p> <p>Below is the output of this example.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-12.webp" alt="Application of Linked List"> <h3>Polynomial of Multiple Variables</h3> <p>We can represent a polynomial with more than one variable, i.e., it can be two or three variables. Below is a node structure suitable for representing a polynomial with three variables X, Y, Z using a singly linked list.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-13.webp" alt="Application of Linked List"> <p>Consider a polynomial P(x, y, z) = 10x<sup>2</sup>y<sup>2</sup>z + 17 x<sup>2</sup>y z<sup>2</sup> - 5 xy<sup>2</sup> z+ 21y<sup>4</sup>z<sup>2</sup> + 7. On represnting this polynomial using linked list are:</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-14.webp" alt="Application of Linked List"> <p>Terms in such a polynomial are ordered accordingly to the decreasing degree in x. Those with the same degree in x are ordered according to decreasing degree in y. Those with the same degree in x and y are ordered according to decreasing degrees in z.</p> <h3>Example</h3> <p> <strong>Simple C++ program to multiply two polynomials</strong> </p> <pre> #include using namespace std; int *multiply(int A[], int B[], int m, int n) { int *prod = new int[m+n-1]; for (int i = 0; i<m+n-1; 4 6 i++) prod[i]="0;" for (int i="0;" i<m; { j="0;" j<n; j++) prod[i+j] +="A[i]*B[j];" } return prod; void printpoly(int poly[], int n) i<n; cout << poly[i]; if (i !="0)" 'x^' ; ' '; main() a[]="{" 5, 0, 10, }; b[]="{" 1, 2, m="sizeof(A)/sizeof(A[0]);" n="sizeof(B)/sizeof(B[0]);" 'first polynomial is 
'; printpoly(a, m); '
second printpoly(b, n); *prod="multiply(A," b, m, '
product of two printpoly(prod, m+n-1); 0; < pre> <p> <strong>Explanation:</strong> </p> <p>In the above example, we have created an example of multiple of two polynomial using arrays.</p> <p> <strong>Output:</strong> </p> <p>Below is the output of this example.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-15.webp" alt="Application of Linked List"> <h2>Some other applications of linked list:</h2> <ul> <tr><td>Memory Management:</td> Memory management is one of the operating system&apos;s key features. It decides how to allocate and reclaim storage for processes running on the system. We can use a linked list to keep track of portions of memory available for allocation. </tr><tr><td>Mailing List:</td> Linked lists have their use in email applications. Since it is difficult to predict multiple lists, maybe a mailer builds a linked list of addresses before sending a message. </tr><tr><td>LISP:</td> LISP is an acronym for LIST processor, an important programming language in artificial intelligence. This language extensively uses linked lists in performing symbolic processing. </tr><tr><td>Linked allocation of files:</td> A file of large size may not be stored in one place on a disk. So there must be some mechanism to link all the scattered parts of the file together. The use of a linked list allows an efficient file allocation method in which each block of a file contains a pointer to the file&apos;s text block. But this method is good only for sequential access. </tr><tr><td>Virtual Memory:</td> An interesting application of linked lists is found in the way systems support virtual memory. </tr><tr><td>Support for other data structures:</td> Some other data structures like stacks, queues, hash tables, graphs can be implemented using a linked list. </tr></ul> <hr></m+n-1;></pre></m;>

Spiegazione:

variabili globali js

Nell'esempio sopra, abbiamo creato un esempio di somma di due polinomi utilizzando la lista concatenata.

Produzione:

Di seguito è riportato l'output di questo esempio.

Polinomio di più variabili

Possiamo rappresentare un polinomio con più di una variabile, ovvero possono essere due o tre variabili. Di seguito è riportata una struttura di nodi adatta a rappresentare un polinomio con tre variabili X, Y, Z utilizzando una lista concatenata singolarmente.

Consideriamo un polinomio P(x, y, z) = 10x²E²z + 17x²e z²- 5xy²z+ 21 anni⁴Con²+ 7. Per rappresentare questo polinomio utilizzando la lista concatenata sono:

I termini in tale polinomio sono ordinati di conseguenza in base al grado decrescente in x. Quelli con lo stesso grado in x sono ordinati secondo il grado decrescente in y. Quelli con lo stesso grado in xey sono ordinati secondo gradi decrescenti in z.

Esempio

Semplice programma C++ per moltiplicare due polinomi

 #include using namespace std; int *multiply(int A[], int B[], int m, int n) { int *prod = new int[m+n-1]; for (int i = 0; i<m+n-1; 4 6 i++) prod[i]="0;" for (int i="0;" i<m; { j="0;" j<n; j++) prod[i+j] +="A[i]*B[j];" } return prod; void printpoly(int poly[], int n) i<n; cout << poly[i]; if (i !="0)" \'x^\' ; \' \'; main() a[]="{" 5, 0, 10, }; b[]="{" 1, 2, m="sizeof(A)/sizeof(A[0]);" n="sizeof(B)/sizeof(B[0]);" \'first polynomial is 
\'; printpoly(a, m); \'
second printpoly(b, n); *prod="multiply(A," b, m, \'
product of two printpoly(prod, m+n-1); 0; < pre> <p> <strong>Explanation:</strong> </p> <p>In the above example, we have created an example of multiple of two polynomial using arrays.</p> <p> <strong>Output:</strong> </p> <p>Below is the output of this example.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-15.webp" alt="Application of Linked List"> <h2>Some other applications of linked list:</h2> <ul> <tr><td>Memory Management:</td> Memory management is one of the operating system&apos;s key features. It decides how to allocate and reclaim storage for processes running on the system. We can use a linked list to keep track of portions of memory available for allocation. </tr><tr><td>Mailing List:</td> Linked lists have their use in email applications. Since it is difficult to predict multiple lists, maybe a mailer builds a linked list of addresses before sending a message. </tr><tr><td>LISP:</td> LISP is an acronym for LIST processor, an important programming language in artificial intelligence. This language extensively uses linked lists in performing symbolic processing. </tr><tr><td>Linked allocation of files:</td> A file of large size may not be stored in one place on a disk. So there must be some mechanism to link all the scattered parts of the file together. The use of a linked list allows an efficient file allocation method in which each block of a file contains a pointer to the file&apos;s text block. But this method is good only for sequential access. </tr><tr><td>Virtual Memory:</td> An interesting application of linked lists is found in the way systems support virtual memory. </tr><tr><td>Support for other data structures:</td> Some other data structures like stacks, queues, hash tables, graphs can be implemented using a linked list. </tr></ul> <hr></m+n-1;>