BRUK AV KOBLET LISTE

I denne artikkelen vil vi forstå de koblede listeapplikasjonene i detalj.

Hva mener du med lenket liste?

En koblet liste er en lineær datastruktur som består av elementer som kalles noder hvor hver node er sammensatt av to deler: en informasjonsdel og en linkdel, også kalt den neste pekerdelen.

Koblet liste brukes i en lang rekke applikasjoner som f.eks

Polynom manipulasjonsrepresentasjon
Addisjon av lange positive heltall
Representasjon av sparsomme matriser
Addisjon av lange positive heltall
Oppretting av symboltabeller
Mailingliste
Minnehåndtering
Koblet tildeling av filer
Aritmetikk med flere presisjoner etc

Polynommanipulasjon

Polynommanipulasjoner er en av de viktigste bruksområdene for koblede lister. Polynomer er en viktig del av matematikk som ikke iboende støttes som datatype av de fleste språk. Et polynom er en samling av forskjellige termer, som hver består av koeffisienter og eksponenter. Det kan representeres ved hjelp av en koblet liste. Denne representasjonen gjør polynommanipulasjon effektiv.

Mens du representerer et polynom ved å bruke en koblet liste, representerer hvert polynomled en node i den koblede listen. For å få bedre effektivitet i behandlingen, antar vi at termen til hvert polynom er lagret i den koblede listen i rekkefølgen av avtagende eksponenter. Dessuten har ingen to ledd den samme eksponenten, og ingen ledd har en null koeffisient og uten koeffisienter. Koeffisienten har en verdi på 1.

Hver node i en koblet liste som representerer polynom, utgjør tre deler:

Den første delen inneholder verdien av koeffisienten til begrepet.
Den andre delen inneholder verdien av eksponenten.
Den tredje delen, LINK peker på neste ledd (neste node).

Strukturen til en node i en koblet liste som representerer et polynom er vist nedenfor:

Tenk på et polynom P(x) = 7x²+ 15x³- 2 x²+ 9. Her er 7, 15, -2 og 9 koeffisientene, og 4,3,2,0 er eksponentene for leddene i polynomet. Ved å representere dette polynomet ved å bruke en koblet liste, har vi

Legg merke til at antall noder er lik antall ledd i polynomet. Så vi har 4 noder. Dessuten lagres termene for å redusere eksponenter i den koblede listen. Slik representasjon av polynom ved bruk av koblede lister gjør operasjoner som subtraksjon, addisjon, multiplikasjon, etc., på polynom veldig enkle.

Tillegg av polynomer:

For å legge til to polynomer, krysser vi listen P og Q. Vi tar tilsvarende ledd i listen P og Q og sammenligner eksponentene deres. Hvis de to eksponentene er like, legges koeffisientene til for å lage en ny koeffisient. Hvis den nye koeffisienten er lik 0, slettes termen, og hvis den ikke er null, settes den inn på slutten av den nye koblede listen som inneholder det resulterende polynomet. Hvis en av eksponentene er større enn den andre, plasseres den tilsvarende termen umiddelbart i den nye lenkede listen, og termen med den mindre eksponenten holdes for å bli sammenlignet med neste term fra den andre listen. Hvis en liste slutter før den andre, settes resten av termene i den lengre listen inn på slutten av den nye koblede listen som inneholder det resulterende polynomet.

La oss vurdere et eksempel som et eksempel for å vise hvordan addisjonen av to polynomer utføres,

jpa om våren

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

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

Disse polynomene er representert ved å bruke en koblet liste i rekkefølge av avtagende eksponenter som følger:

For å generere en ny koblet liste for de resulterende polynomene som er dannet ved tillegg av gitte polynomer P(x) og Q(x), utfører vi følgende trinn,

Gå gjennom de to listene P og Q og undersøk alle nodene.
Vi sammenligner eksponentene til de tilsvarende leddene til to polynomer. Det første leddet i polynomene P og Q inneholder henholdsvis eksponentene 4 og 3. Siden eksponenten til det første leddet til polynomet P er større enn det andre polynomet Q, blir begrepet som har en større eksponent satt inn i den nye listen. Den nye listen ser i utgangspunktet ut som vist nedenfor:
Vi sammenligner så eksponenten til neste ledd på listen P med eksponentene til nåværende ledd på liste Q. Siden de to eksponentene er like, blir koeffisientene deres lagt til og lagt til den nye listen som følger:
Deretter går vi til neste ledd av P- og Q-lister og sammenligner eksponentene deres. Siden eksponenter for begge disse leddene er like og etter addisjon av koeffisientene deres, får vi 0, så termen blir droppet, og ingen node blir lagt til den nye listen etter dette,
Går vi til neste ledd av de to listene, P og Q, finner vi at de tilsvarende leddene har de samme eksponentene lik 0. Vi legger til koeffisientene deres og legger dem til den nye listen for det resulterende polynomet som vist nedenfor:

Eksempel:

C++-program for å legge til to polynomer

 #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 eksemplet ovenfor har vi laget et eksempel på summen av to polynomer ved å bruke koblet liste.

Produksjon:

Nedenfor er resultatet av dette eksemplet.

Polynom av flere variabler

Vi kan representere et polynom med mer enn én variabel, det vil si at det kan være to eller tre variabler. Nedenfor er en nodestruktur egnet for å representere et polynom med tre variabler X, Y, Z ved å bruke en enkeltlenket liste.

Tenk på et polynom P(x, y, z) = 10x²og²z + 17 x²y z²- 5 xy²z+ 21 år⁴Med²+ 7. Ved å representere dette polynomet ved å bruke lenket liste er:

Leder i et slikt polynom er ordnet tilsvarende i avtagende grad i x. De med samme grad i x er ordnet etter avtagende grad i y. De med samme grad i x og y er ordnet etter avtagende grader i z.

dijkstra

Eksempel

Enkelt C++-program for å multiplisere to polynomer

 #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