APPLICATION DE LA LISTE CHAÎNÉE

Dans cet article, nous comprendrons en détail les applications de listes chaînées.

Qu'entendez-vous par liste chaînée ?

Une liste chaînée est une structure de données linéaire composée d'éléments appelés nœuds où chaque nœud est composé de deux parties : une partie information et une partie lien, également appelée partie pointeur suivant.

La liste chaînée est utilisée dans une grande variété d'applications telles que

Représentation de manipulation polynomiale
Ajout d'entiers longs positifs
Représentation de matrices clairsemées
Ajout d'entiers longs positifs
Création d'une table de symboles
Liste de diffusion
Gestion de la mémoire
Allocation liée des fichiers
Arithmétique à précision multiple, etc.

Manipulation polynomiale

Les manipulations polynomiales sont l'une des applications les plus importantes des listes chaînées. Les polynômes constituent une partie importante des mathématiques et ne sont pas intrinsèquement pris en charge en tant que type de données par la plupart des langages. Un polynôme est un ensemble de termes différents, chacun comprenant des coefficients et des exposants. Il peut être représenté à l’aide d’une liste chaînée. Cette représentation rend la manipulation polynomiale efficace.

Lors de la représentation d'un polynôme à l'aide d'une liste chaînée, chaque terme polynomial représente un nœud dans la liste chaînée. Pour obtenir une meilleure efficacité du traitement, nous supposons que le terme de chaque polynôme est stocké dans la liste chaînée dans l'ordre des exposants décroissants. De plus, il n'y a pas deux termes qui aient le même exposant, et aucun terme n'a un coefficient nul et sans coefficients. Le coefficient prend la valeur 1.

Chaque nœud d'une liste chaînée représentant un polynôme constitue trois parties :

La première partie contient la valeur du coefficient du terme.
La deuxième partie contient la valeur de l'exposant.
La troisième partie, LINK pointe vers le terme suivant (nœud suivant).

La structure d'un nœud d'une liste chaînée qui représente un polynôme est présentée ci-dessous :

Considérons un polynôme P(x) = 7x²+15x³- 2x²+ 9. Ici 7, 15, -2 et 9 sont les coefficients et 4,3,2,0 sont les exposants des termes du polynôme. En représentant ce polynôme à l'aide d'une liste chaînée, nous avons

Observez que le nombre de nœuds est égal au nombre de termes du polynôme. Nous avons donc 4 nœuds. De plus, les termes sont stockés pour diminuer les exposants dans la liste chaînée. Une telle représentation du polynôme à l'aide de listes chaînées rend les opérations telles que la soustraction, l'addition, la multiplication, etc. sur le polynôme très faciles.

Ajout de polynômes :

Pour ajouter deux polynômes, nous parcourons la liste P et Q. Nous prenons les termes correspondants de la liste P et Q et comparons leurs exposants. Si les deux exposants sont égaux, les coefficients sont ajoutés pour créer un nouveau coefficient. Si le nouveau coefficient est égal à 0, alors le terme est supprimé, et s'il n'est pas nul, il est inséré à la fin de la nouvelle liste chaînée contenant le polynôme résultant. Si l'un des exposants est plus grand que l'autre, le terme correspondant est immédiatement placé dans la nouvelle liste chaînée et le terme avec l'exposant le plus petit est censé être comparé au terme suivant de l'autre liste. Si une liste se termine avant l'autre, le reste des termes de la liste la plus longue est inséré à la fin de la nouvelle liste chaînée contenant le polynôme résultant.

Prenons un exemple pour montrer comment s'effectue l'addition de deux polynômes,

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

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

Ces polynômes sont représentés à l'aide d'une liste chaînée par ordre d'exposants décroissants comme suit :

Pour générer une nouvelle liste chaînée pour les polynômes résultants formés lors de l'ajout de polynômes donnés P(x) et Q(x), nous effectuons les étapes suivantes,

Parcourez les deux listes P et Q et examinez tous les nœuds.
Nous comparons les exposants des termes correspondants de deux polynômes. Le premier terme des polynômes P et Q contiennent respectivement les exposants 4 et 3. Puisque l'exposant du premier terme du polynôme P est supérieur à celui de l'autre polynôme Q, le terme ayant un exposant plus grand est inséré dans la nouvelle liste. La nouvelle liste ressemble initialement à celle ci-dessous :
Nous comparons ensuite l'exposant du terme suivant de la liste P avec les exposants du terme actuel de la liste Q. Puisque les deux exposants sont égaux, leurs coefficients sont donc ajoutés et ajoutés à la nouvelle liste comme suit :
Ensuite, nous passons au terme suivant des listes P et Q et comparons leurs exposants. Puisque les exposants de ces deux termes sont égaux et qu'après addition de leurs coefficients, nous obtenons 0, donc le terme est supprimé et aucun nœud n'est ajouté à la nouvelle liste après cela,
En passant au terme suivant des deux listes, P et Q, nous constatons que les termes correspondants ont les mêmes exposants égaux à 0. Nous ajoutons leurs coefficients et les ajoutons à la nouvelle liste pour le polynôme résultant comme indiqué ci-dessous :

Exemple:

Programme C++ pour ajouter deux polynômes

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

Explication:

Dans l'exemple ci-dessus, nous avons créé un exemple de somme de deux polynômes en utilisant une liste chaînée.

Sortir:

fenêtre.ouvrir javascript

Vous trouverez ci-dessous le résultat de cet exemple.

Polynôme de plusieurs variables

Nous pouvons représenter un polynôme avec plus d’une variable, c’est-à-dire qu’il peut s’agir de deux ou trois variables. Vous trouverez ci-dessous une structure de nœuds adaptée pour représenter un polynôme avec trois variables X, Y, Z à l'aide d'une liste à chaînage unique.

Considérons un polynôme P(x, y, z) = 10x²et²z + 17x²oui²- 5 xy²z+ 21a⁴Avec²+ 7. Pour représenter ce polynôme à l'aide d'une liste chaînée, on trouve :

Les termes d'un tel polynôme sont ordonnés en fonction du degré décroissant en x. Ceux qui ont le même degré en x sont classés selon leur degré décroissant en y. Ceux qui ont le même degré en x et y sont classés selon des degrés décroissants en z.

Exemple

Programme C++ simple pour multiplier deux polynômes

 #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