În acest articol, vom înțelege în detaliu aplicațiile din lista legată.

Ce vrei să spui prin listă legată?

O listă legată este o structură de date liniară constând din elemente numite noduri în care fiecare nod este compus din două părți: o parte de informații și o parte de legătură, numită și următoarea parte de indicator.

Lista legată este utilizată într-o mare varietate de aplicații, cum ar fi

• Reprezentare Manipulare polinomială
• Adunarea numerelor întregi pozitive lungi
• Reprezentarea matricelor rare
• Adunarea numerelor întregi pozitive lungi
• Crearea tabelului de simboluri
• Listă de email-uri
• Gestionarea memoriei
• Alocarea legată de fișiere
• Aritmetică de precizie multiplă etc

Manipularea polinomului

Manipulările polinomiale sunt una dintre cele mai importante aplicații ale listelor legate. Polinoamele sunt o parte importantă a matematicii care nu sunt susținute în mod inerent ca tip de date de majoritatea limbilor. Un polinom este o colecție de termeni diferiți, fiecare cuprinzând coeficienți și exponenți. Poate fi reprezentat folosind o listă legată. Această reprezentare face manipularea polinomială eficientă.

În timp ce se reprezintă un polinom folosind o listă legată, fiecare termen polinom reprezintă un nod în lista legată. Pentru a obține o eficiență mai bună în procesare, presupunem că termenul fiecărui polinom este stocat în lista legată în ordinea exponenților descrescători. De asemenea, niciun termen nu are același exponent și niciun termen nu are coeficient zero și fără coeficienți. Coeficientul ia valoarea 1.

Fiecare nod al unei liste legate reprezentând polinom constituie trei părți:

• Prima parte conține valoarea coeficientului termenului.
• A doua parte conține valoarea exponentului.
• A treia parte, LINK indică următorul termen (următorul nod).

Structura unui nod dintr-o listă legată care reprezintă un polinom este prezentată mai jos:

Se consideră un polinom P(x) = 7x²+ 15x³- 2 x²+ 9. Aici 7, 15, -2 și 9 sunt coeficienții, iar 4,3,2,0 sunt exponenții termenilor din polinom. Reprezentând acest polinom folosind o listă legată, avem

Observați că numărul de noduri este egal cu numărul de termeni din polinom. Deci avem 4 noduri. Mai mult decât atât, termenii sunt stocați pentru a reduce exponenții din lista legată. O astfel de reprezentare a polinomului folosind liste legate face operațiunile precum scăderea, adunarea, înmulțirea etc. pe polinom foarte ușoare.

Adunarea polinoamelor:

Pentru a adăuga două polinoame, parcurgem lista P și Q. Luăm termenii corespunzători din lista P și Q și comparăm exponenții acestora. Dacă cei doi exponenți sunt egali, se adaugă coeficienții pentru a crea un nou coeficient. Dacă noul coeficient este egal cu 0, atunci termenul este abandonat, iar dacă nu este zero, este inserat la sfârșitul noii liste legate care conține polinomul rezultat. Dacă unul dintre exponenți este mai mare decât celălalt, termenul corespunzător este plasat imediat în noua listă legată, iar termenul cu exponentul mai mic este considerat a fi comparat cu următorul termen din cealaltă listă. Dacă o listă se termină înaintea celeilalte, restul termenilor listei mai lungi sunt inserați la sfârșitul noii liste legate care conține polinomul rezultat.

Să considerăm un exemplu un exemplu pentru a arăta cum se realizează adăugarea a două polinoame,

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

„ce” înseamnă 10 din 100”

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

Aceste polinoame sunt reprezentate folosind o listă legată în ordinea descrescătoare a exponenților, după cum urmează:

Pentru a genera o nouă listă legată pentru polinoamele rezultate care se formează prin adăugarea polinoamelor date P(x) și Q(x), parcurgem următorii pași,

1. Parcurgeți cele două liste P și Q și examinați toate nodurile.
2. Comparăm exponenții termenilor corespunzători a două polinoame. Primul termen al polinoamelor P și Q conține exponenții 4 și, respectiv, 3. Deoarece exponentul primului termen al polinomului P este mai mare decât celălalt polinom Q, termenul care are un exponent mai mare este inserat în noua listă. Noua listă arată inițial așa cum se arată mai jos:
   
3. Apoi comparăm exponentul următorului termen al listei P cu exponenții termenului actual al listei Q. Deoarece cei doi exponenți sunt egali, deci coeficienții lor se adaugă și se adaugă la noua listă după cum urmează:
   
4. Apoi trecem la următorul termen al listelor P și Q și comparăm exponenții acestora. Deoarece exponenții ambilor termeni sunt egali și după adăugarea coeficienților lor, obținem 0, deci termenul este abandonat și niciun nod nu este adăugat la noua listă după aceasta,
   
5. Trecând la următorul termen din cele două liste, P și Q, constatăm că termenii corespunzători au aceiași exponenți egali cu 0. Adăugăm coeficienții lor și îi anexăm la noua listă pentru polinomul rezultat, așa cum se arată mai jos:
   

Exemplu:

Program C++ pentru a adăuga două polinoame

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

Explicaţie:

În exemplul de mai sus, am creat un exemplu de sumă a două polinoame folosind lista legată.

Ieșire:

Mai jos este rezultatul acestui exemplu.

Polinom de variabile multiple

Putem reprezenta un polinom cu mai mult de o variabilă, adică poate fi două sau trei variabile. Mai jos este o structură de nod potrivită pentru reprezentarea unui polinom cu trei variabile X, Y, Z folosind o listă unică legată.

Se consideră un polinom P(x, y, z) = 10x²și²z + 17 x²y z²- 5 xy²z+ 21y⁴Cu²+ 7. La reprezentarea acestui polinom folosind lista legată sunt:

Termenii dintr-un astfel de polinom sunt ordonați în funcție de gradul descrescător în x. Cele cu același grad în x sunt ordonate în funcție de gradul descrescător în y. Cele cu același grad în x și y sunt ordonate în funcție de grade descrescătoare în z.

Exemplu

Program simplu C++ pentru înmulțirea a două polinoame

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