ANVENDELSE AF LINKET LISTE

I denne artikel vil vi forstå de linkede listeapplikationer i detaljer.

Hvad mener du med linket liste?

En sammenkædet liste er en lineær datastruktur bestående af elementer kaldet noder, hvor hver node er sammensat af to dele: en informationsdel og en linkdel, også kaldet den næste pointerdel.

Linket liste bruges i en lang række applikationer som f.eks

Polynomisk manipulation repræsentation
Tilføjelse af lange positive heltal
Repræsentation af sparsomme matricer
Tilføjelse af lange positive heltal
Oprettelse af symbolbord
Postliste
Hukommelseshåndtering
Sammenkædet tildeling af filer
Flere præcisionsregninger osv

Polynomisk manipulation

Polynomielle manipulationer er en af de vigtigste anvendelser af linkede lister. Polynomier er en vigtig del af matematik, der ikke i sig selv understøttes som datatype af de fleste sprog. Et polynomium er en samling af forskellige udtryk, som hver omfatter koefficienter og eksponenter. Det kan repræsenteres ved hjælp af en linket liste. Denne repræsentation gør polynomiemanipulation effektiv.

Mens det repræsenterer et polynomium ved hjælp af en sammenkædet liste, repræsenterer hvert polynomium en node i den sammenkædede liste. For at opnå bedre effektivitet i behandlingen, antager vi, at termen for hvert polynomium er gemt i den sammenkædede liste i rækkefølgen af faldende eksponenter. Heller ikke to led har den samme eksponent, og intet led har en nulkoefficient og uden koefficienter. Koefficienten har en værdi på 1.

Hver knude på en sammenkædet liste, der repræsenterer polynomium, består af tre dele:

Den første del indeholder værdien af udtrykkets koefficient.
Den anden del indeholder værdien af eksponenten.
Den tredje del, LINK peger på næste led (næste knude).

Strukturen af en knude på en sammenkædet liste, der repræsenterer et polynomium, er vist nedenfor:

Betragt et polynomium P(x) = 7x²+ 15x³- 2 x²+ 9. Her er 7, 15, -2 og 9 koefficienterne, og 4,3,2,0 er eksponenterne for vilkårene i polynomiet. Ved at repræsentere dette polynomium ved hjælp af en sammenkædet liste, har vi

Bemærk, at antallet af noder er lig med antallet af led i polynomiet. Så vi har 4 noder. Desuden gemmes termerne for at reducere eksponenter i den sammenkædede liste. Sådan repræsentation af polynomium ved hjælp af forbundne lister gør operationer som subtraktion, addition, multiplikation osv. på polynomium meget nemme.

Tilføjelse af polynomier:

For at tilføje to polynomier krydser vi listen P og Q. Vi tager tilsvarende led i listen P og Q og sammenligner deres eksponenter. Hvis de to eksponenter er ens, tilføjes koefficienterne for at skabe en ny koefficient. Hvis den nye koefficient er lig med 0, slettes udtrykket, og hvis det ikke er nul, indsættes det i slutningen af den nye sammenkædede liste, der indeholder det resulterende polynomium. Hvis en af eksponenterne er større end den anden, placeres det tilsvarende led straks i den nye sammenkædede liste, og termen med den mindre eksponent holdes til at blive sammenlignet med næste led fra den anden liste. Hvis den ene liste slutter før den anden, indsættes resten af termerne i den længere liste i slutningen af den nye sammenkædede liste, der indeholder det resulterende polynomium.

Lad os betragte et eksempel som et eksempel for at vise, hvordan tilføjelsen af to polynomier udføres,

hvordan man viser en applikation på Android

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

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

Disse polynomier er repræsenteret ved hjælp af en sammenkædet liste i rækkefølge af faldende eksponenter som følger:

For at generere en ny sammenkædet liste for de resulterende polynomier, der er dannet ved tilføjelse af givne polynomier P(x) og Q(x), udfører vi følgende trin,

Gå gennem de to lister P og Q og undersøg alle knudepunkterne.
Vi sammenligner eksponenterne for de tilsvarende led i to polynomier. Det første led af polynomier P og Q indeholder henholdsvis eksponent 4 og 3. Da eksponenten af det første led af polynomiet P er større end det andet polynomium Q, indsættes udtrykket med en større eksponent i den nye liste. Den nye liste ser i første omgang ud som vist nedenfor:
Vi sammenligner derefter eksponenten for det næste led på listen P med eksponenterne for det nuværende led på liste Q. Da de to eksponenter er lige store, så tilføjes deres koefficienter og tilføjes til den nye liste som følger:
Så går vi til næste led af P- og Q-lister og sammenligner deres eksponenter. Da eksponenter af begge disse led er ens og efter tilføjelse af deres koefficienter, får vi 0, så udtrykket slettes, og ingen node tilføjes til den nye liste efter dette,
Går vi til næste led af de to lister, P og Q, finder vi, at de tilsvarende led har de samme eksponenter lig med 0. Vi tilføjer deres koefficienter og tilføjer dem til den nye liste for det resulterende polynomium som vist nedenfor:

Eksempel:

C++-program til at tilføje to polynomier

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

Forklaring:

I ovenstående eksempel har vi lavet et eksempel på summen af to polynomier ved hjælp af linket liste.

Produktion:

Nedenfor er resultatet af dette eksempel.

Polynomium af flere variable

Vi kan repræsentere et polynomium med mere end én variabel, dvs. det kan være to eller tre variable. Nedenfor er en nodestruktur, der er egnet til at repræsentere et polynomium med tre variable X, Y, Z ved hjælp af en enkeltforbundet liste.

Betragt et polynomium P(x, y, z) = 10x²og²z + 17 x²y z²- 5 xy²z+ 21 år⁴Med²+ 7. Ved at repræsentere dette polynomium ved hjælp af linket liste er:

Termer i et sådant polynomium er ordnet i overensstemmelse hermed i faldende grad i x. Dem med samme grad i x er ordnet efter faldende grad i y. Dem med samme grad i x og y er ordnet efter faldende grader i z.

dijkstra

Eksempel

Simpelt C++-program til at gange to polynomier

 #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

Anvendelse af linket liste