APLICACIÓ DE LLISTA ENLLAÇADA

En aquest article, entendrem detalladament les aplicacions de la llista enllaçada.

Què entens per llista enllaçada?

Una llista enllaçada és una estructura de dades lineal que consta d'elements anomenats nodes on cada node es compon de dues parts: una part d'informació i una part d'enllaç, també anomenada part del punter següent.

La llista enllaçada s'utilitza en una gran varietat d'aplicacions, com ara

Representació de la manipulació polinomial
Suma de nombres enters positius llargs
Representació de matrius escasses
Suma de nombres enters positius llargs
Creació de la taula de símbols
Llista d'enviament
Gestió de la memòria
Assignació enllaçada de fitxers
Aritmètica de precisió múltiple, etc

Manipulació de polinomis

Les manipulacions polinomials són una de les aplicacions més importants de les llistes enllaçades. Els polinomis són una part important de les matemàtiques que no són compatibles de manera inherent com a tipus de dades per la majoria dels idiomes. Un polinomi és una col·lecció de termes diferents, cadascun d'ells format per coeficients i exponents. Es pot representar mitjançant una llista enllaçada. Aquesta representació fa que la manipulació polinomial sigui eficient.

Mentre es representa un polinomi mitjançant una llista enllaçada, cada terme polinomi representa un node de la llista enllaçada. Per obtenir una millor eficiència en el processament, suposem que el terme de cada polinomi s'emmagatzema dins de la llista enllaçada en l'ordre dels exponents decreixents. A més, no hi ha dos termes que tinguin el mateix exponent, ni cap terme té un coeficient zero i sense coeficients. El coeficient pren un valor d'1.

Cada node d'una llista enllaçada que representa un polinomi constitueix tres parts:

La primera part conté el valor del coeficient del terme.
La segona part conté el valor de l'exponent.
La tercera part, LINK apunta al següent terme (node següent).

L'estructura d'un node d'una llista enllaçada que representa un polinomi es mostra a continuació:

Considereu un polinomi P(x) = 7x²+ 15x³- 2 x²+ 9. Aquí 7, 15, -2 i 9 són els coeficients, i 4,3,2,0 són els exponents dels termes del polinomi. En representar aquest polinomi mitjançant una llista enllaçada, tenim

Observeu que el nombre de nodes és igual al nombre de termes del polinomi. Així que tenim 4 nodes. A més, els termes s'emmagatzemen per disminuir els exponents a la llista enllaçada. Aquesta representació de polinomis mitjançant llistes enllaçades fa que les operacions com la resta, la suma, la multiplicació, etc., en polinomis siguin molt fàcils.

Suma de polinomis:

Per sumar dos polinomis, recorrem la llista P i Q. Agafem els termes corresponents de la llista P i Q i comparem els seus exponents. Si els dos exponents són iguals, s'afegeixen els coeficients per crear un nou coeficient. Si el nou coeficient és igual a 0, el terme s'elimina i, si no és zero, s'insereix al final de la nova llista enllaçada que conté el polinomi resultant. Si un dels exponents és més gran que l'altre, el terme corresponent es col·loca immediatament a la nova llista enllaçada i el terme amb l'exponent més petit es compara amb el terme següent de l'altra llista. Si una llista acaba abans que l'altra, la resta de termes de la llista més llarga s'insereixen al final de la nova llista enllaçada que conté el polinomi resultant.

Considerem un exemple un exemple per mostrar com es realitza la suma de dos polinomis,

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

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

Aquests polinomis es representen mitjançant una llista enllaçada en ordre decreixent dels exponents de la manera següent:

Per generar una nova llista enllaçada per als polinomis resultants que es formen amb la suma de polinomis donats P(x) i Q(x), realitzem els passos següents:

Travessa les dues llistes P i Q i examina tots els nodes.
Comparem els exponents dels termes corresponents de dos polinomis. El primer terme dels polinomis P i Q conté els exponents 4 i 3, respectivament. Com que l'exponent del primer terme del polinomi P és més gran que l'altre polinomi Q, el terme que té un exponent més gran s'insereix a la nova llista. La nova llista inicialment es veu com es mostra a continuació:
Aleshores comparem l'exponent del terme següent de la llista P amb els exponents del terme actual de la llista Q. Com que els dos exponents són iguals, els seus coeficients s'afegeixen i s'afegeixen a la nova llista de la manera següent:
A continuació, passem al següent terme de les llistes P i Q i comparem els seus exponents. Com que els exponents d'aquests dos termes són iguals i després d'afegir els seus coeficients, obtenim 0, de manera que el terme s'elimina i no s'afegeix cap node a la llista nova després d'això,
Passant al següent terme de les dues llistes, P i Q, trobem que els termes corresponents tenen els mateixos exponents iguals a 0. Sumem els seus coeficients i els afegim a la nova llista per al polinomi resultant tal com es mostra a continuació:

Exemple:

Programa C++ per afegir dos polinomis

 #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;>

Explicació:

A l'exemple anterior, hem creat un exemple de suma de dos polinomis mitjançant una llista enllaçada.

Sortida:

A continuació es mostra la sortida d'aquest exemple.

Polinomi de Variables Múltiples

Podem representar un polinomi amb més d'una variable, és a dir, pot ser dues o tres variables. A continuació es mostra una estructura de nodes adequada per representar un polinomi amb tres variables X, Y, Z mitjançant una llista enllaçada individualment.

Considereu un polinomi P(x, y, z) = 10x²i²z + 17 x²y z²- 5 xy²z+ 21y⁴Amb²+ 7. En representar aquest polinomi utilitzant una llista enllaçada són:

Els termes d'aquest polinomi s'ordenen segons el grau decreixent en x. Els que tenen el mateix grau en x s'ordenen segons el grau decreixent en y. Els que tenen el mateix grau en x i y s'ordenen segons graus decreixents en z.

Exemple

Programa senzill en C++ per multiplicar dos polinomis

 #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;>

TechCodeview