TILLÄMPNING AV LÄNKAD LISTA

I den här artikeln kommer vi att förstå de länkade listapplikationerna i detalj.

Vad menar du med länkad lista?

En länkad lista är en linjär datastruktur som består av element som kallas noder där varje nod är sammansatt av två delar: en informationsdel och en länkdel, även kallad nästa pekardel.

Länkad lista används i en mängd olika applikationer som t.ex

Polynom Manipulation representation
Tillägg av långa positiva heltal
Representation av glesa matriser
Tillägg av långa positiva heltal
Skapande av symbolbord
E-postlista
Minneshantering
Länkad tilldelning av filer
Aritmetik med flera precisions etc

Polynommanipulation

Polynommanipulationer är en av de viktigaste tillämpningarna av länkade listor. Polynom är en viktig del av matematik som inte i sig stöds som datatyp av de flesta språk. Ett polynom är en samling olika termer, som var och en består av koefficienter och exponenter. Det kan representeras med hjälp av en länkad lista. Denna representation gör polynommanipulation effektiv.

Medan det representerar ett polynom med hjälp av en länkad lista, representerar varje polynomterm en nod i den länkade listan. För att få bättre effektivitet i bearbetningen antar vi att termen för varje polynom lagras i den länkade listan i ordningen av minskande exponenter. Dessutom har inga två termer samma exponent, och ingen term har en nollkoefficient och utan koefficienter. Koefficienten har värdet 1.

arp - ett kommando

Varje nod i en länkad lista som representerar polynom består av tre delar:

Den första delen innehåller värdet av termens koefficient.
Den andra delen innehåller exponentens värde.
Den tredje delen, LINK pekar på nästa term (nästa nod).

Strukturen för en nod i en länkad lista som representerar ett polynom visas nedan:

Betrakta ett polynom P(x) = 7x²+ 15x³- 2 x²+ 9. Här är 7, 15, -2 och 9 koefficienterna, och 4,3,2,0 är exponenterna för termerna i polynomet. På att representera detta polynom med hjälp av en länkad lista har vi

Observera att antalet noder är lika med antalet termer i polynomet. Så vi har 4 noder. Dessutom lagras termerna för att minska exponenter i den länkade listan. Sådan representation av polynom med länkade listor gör operationer som subtraktion, addition, multiplikation, etc., på polynom mycket enkla.

Tillägg av polynom:

För att lägga till två polynom går vi igenom listan P och Q. Vi tar motsvarande termer i listan P och Q och jämför deras exponenter. Om de två exponenterna är lika, adderas koefficienterna för att skapa en ny koefficient. Om den nya koefficienten är lika med 0, tas termen bort, och om den inte är noll, infogas den i slutet av den nya länkade listan som innehåller det resulterande polynomet. Om en av exponenterna är större än den andra, placeras motsvarande term omedelbart i den nya länkade listan, och termen med den mindre exponenten hålls för att jämföras med nästa term från den andra listan. Om en lista slutar före den andra, infogas resten av termerna i den längre listan i slutet av den nya länkade listan som innehåller det resulterande polynomet.

Låt oss betrakta ett exempel som ett exempel för att visa hur additionen av två polynom utförs,

jämförbar sträng

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

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

Dessa polynom representeras med hjälp av en länkad lista i ordning med minskande exponenter enligt följande:

För att generera en ny länkad lista för de resulterande polynomen som bildas genom tillägg av givna polynom P(x) och Q(x), utför vi följande steg,

Gå igenom de två listorna P och Q och undersök alla noder.
Vi jämför exponenterna för motsvarande termer för två polynom. Den första termen i polynomen P och Q innehåller exponenterna 4 respektive 3. Eftersom exponenten för den första termen av polynomet P är större än det andra polynomet Q, infogas termen som har en större exponent i den nya listan. Den nya listan ser initialt ut som visas nedan:
Vi jämför sedan exponenten för nästa term i listan P med exponenterna för den nuvarande termen i lista Q. Eftersom de två exponenterna är lika, så läggs deras koefficienter till och läggs till den nya listan enligt följande:
Sedan går vi till nästa term av P- och Q-listor och jämför deras exponenter. Eftersom exponenter för båda dessa termer är lika och efter addering av deras koefficienter får vi 0, så termen tas bort och ingen nod läggs till den nya listan efter detta,
När vi går till nästa term av de två listorna, P och Q, finner vi att motsvarande termer har samma exponenter lika med 0. Vi lägger till deras koefficienter och lägger till dem i den nya listan för det resulterande polynomet som visas nedan:

Exempel:

C++-program för att lägga till två polynom

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

Förklaring:

greibach normal form

I exemplet ovan har vi skapat ett exempel på summan av två polynom med hjälp av länkad lista.

Produktion:

Nedan är resultatet av detta exempel.

Polynom av flera variabler

Vi kan representera ett polynom med mer än en variabel, dvs det kan vara två eller tre variabler. Nedan finns en nodstruktur som är lämplig för att representera ett polynom med tre variabler X, Y, Z med hjälp av en enkellänkad lista.

Betrakta ett polynom P(x, y, z) = 10x²och²z + 17 x²y z²- 5 xy²z+ 21 år⁴Med²+ 7. När du representerar detta polynom med hjälp av länkad lista är:

Termer i ett sådant polynom ordnas därefter i minskande grad i x. De med samma grad i x är ordnade efter minskande grad i y. De med samma grad i x och y ordnas efter minskande grader i z.

designmönster java

Exempel

Enkelt C++-program för att multiplicera två polynom

 #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