LINKITETYN LUETTELON SOVELTAMINEN

Tässä artikkelissa ymmärrämme linkitetyt luettelosovellukset yksityiskohtaisesti.

Mitä tarkoitat linkitetyllä listalla?

Linkitetty lista on lineaarinen tietorakenne, joka koostuu elementeistä, joita kutsutaan solmuiksi ja joissa kukin solmu koostuu kahdesta osasta: tietoosasta ja linkkiosasta, jota kutsutaan myös seuraavaksi osoitinosaksi.

Linkitettyä listaa käytetään monenlaisissa sovelluksissa, kuten

Polynomimanipulaatioesitys
Pitkien positiivisten kokonaislukujen lisääminen
Harvaiden matriisien esitys
Pitkien positiivisten kokonaislukujen lisääminen
Symbolitaulukon luominen
Postitus lista
Muistin hallinta
Linkitetty tiedostojen allokointi
Monitarkkuusaritmetiikka jne

Polynomimanipulaatio

Polynomimanipulaatiot ovat yksi linkitettyjen listojen tärkeimmistä sovelluksista. Polynomit ovat tärkeä osa matematiikkaa, jota useimmat kielet eivät luonnostaan tue tietotyyppinä. Polynomi on kokoelma erilaisia termejä, joista jokainen sisältää kertoimia ja eksponenteja. Se voidaan esittää linkitetyn luettelon avulla. Tämä esitys tekee polynomimanipulaatiosta tehokkaan.

Vaikka polynomi edustaa linkitettyä listaa, jokainen polynomitermi edustaa linkitetyn luettelon solmua. Paremman käsittelyn tehokkuuden saavuttamiseksi oletetaan, että jokaisen polynomin termi on tallennettu linkitettyyn listaan pienenevien eksponentien järjestyksessä. Myöskään kahdella termillä ei ole samaa eksponenttia, eikä millään termillä ole nollakerrointa ja ilman kertoimia. Kerroin saa arvon 1.

Jokainen polynomia edustavan linkitetyn luettelon solmu koostuu kolmesta osasta:

Ensimmäinen osa sisältää termin kertoimen arvon.
Toinen osa sisältää eksponentin arvon.
Kolmas osa, LINK osoittaa seuraavaan termiin (seuraavaan solmuun).

Polynomia edustavan linkitetyn luettelon solmun rakenne on esitetty alla:

Tarkastellaan polynomia P(x) = 7x²+ 15x³- 2 x²+ 9. Tässä 7, 15, -2 ja 9 ovat kertoimet ja 4,3,2,0 ovat polynomin termien eksponentit. Kun edustamme tätä polynomia linkitetyn luettelon avulla, meillä on

Huomaa, että solmujen lukumäärä on yhtä suuri kuin polynomin termien lukumäärä. Meillä on siis 4 solmua. Lisäksi termit tallennetaan vähentämään eksponenteja linkitetyssä luettelossa. Tällainen polynomin esittäminen linkitetyillä listoilla tekee polynomin toiminnoista, kuten vähennys-, yhteen-, kertolasku- jne., erittäin helpot.

Polynomien lisäys:

Kahden polynomin lisäämiseksi käymme läpi listan P ja Q. Otamme vastaavat listan P ja Q termit ja vertaamme niiden eksponenttia. Jos molemmat eksponentit ovat yhtä suuret, kertoimet lisätään uuden kertoimen luomiseksi. Jos uusi kerroin on yhtä suuri kuin 0, termi hylätään, ja jos se ei ole nolla, se lisätään uuden linkitetyn listan loppuun, joka sisältää tuloksena olevan polynomin. Jos yksi eksponenteista on suurempi kuin toinen, vastaava termi sijoitetaan välittömästi uuteen linkitettyyn listaan ja termiä, jolla on pienempi eksponentti, verrataan seuraavan listan seuraavaan termiin. Jos yksi lista päättyy ennen toista, pidemmän listan loput termit lisätään tuloksena olevan polynomin sisältävän uuden linkitetyn listan loppuun.

Tarkastellaan esimerkkiä esimerkkinä, joka näyttää kuinka kahden polynomin summaus suoritetaan,

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

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

Nämä polynomit esitetään linkitetyllä listalla eksponenttiarvojen pienenemisjärjestyksessä seuraavasti:

Luodaksemme uuden linkitetyn luettelon tuloksena oleville polynomeille, jotka muodostetaan yhteenlaskemalla tietyt polynomit P(x) ja Q(x), suoritamme seuraavat vaiheet:

Käy läpi kaksi listaa P ja Q ja tutki kaikki solmut.
Vertaamme kahden polynomin vastaavien ehtojen eksponenttia. Polynomien P ja Q ensimmäinen termi sisältää eksponentit 4 ja 3, vastaavasti. Koska polynomin P ensimmäisen termin eksponentti on suurempi kuin toisen polynomin Q, termi, jolla on suurempi eksponentti, lisätään uuteen luetteloon. Uusi lista näyttää aluksi alla olevan kuvan mukaiselta:
Verrataan sitten listan P seuraavan termin eksponenttia listan Q nykyisen termin eksponenteihin. Koska nämä kaksi eksponenttia ovat yhtä suuret, niin niiden kertoimet lisätään ja liitetään uuteen listaan seuraavasti:
Sitten siirrytään P- ja Q-listojen seuraavaan termiin ja verrataan niiden eksponenttia. Koska näiden molempien termien eksponentit ovat yhtä suuret ja niiden kertoimien lisäyksen jälkeen saadaan 0, joten termi jätetään pois, eikä solmua lisätä uuteen listaan tämän jälkeen,
Siirtyessämme kahden listan, P ja Q, seuraavaan termiin, havaitsemme, että vastaavilla termeillä on samat eksponentit, jotka ovat yhtä suuret kuin 0. Lisäämme niiden kertoimet ja liitämme ne uuteen luetteloon tuloksena olevalle polynomille alla esitetyllä tavalla:

Esimerkki:

C++-ohjelma kahden polynomin lisäämiseen

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

Selitys:

Yllä olevassa esimerkissä olemme luoneet esimerkin kahden polynomin summasta linkitetyn listan avulla.

Lähtö:

Alla on tämän esimerkin tulos.

Useiden muuttujien polynomi

Voimme esittää polynomin useammalla kuin yhdellä muuttujalla, eli se voi olla kaksi tai kolme muuttujaa. Alla on solmurakenne, joka soveltuu polynomin esittämiseen kolmella muuttujalla X, Y, Z käyttämällä erikseen linkitettyä listaa.

Tarkastellaan polynomia P(x, y, z) = 10x²ja²z + 17 x²y z²- 5 xy²z+ 21v⁴Kanssa²+ 7. Tämän polynomin esittäessä linkitettyä listaa ovat:

Tällaisen polynomin termit järjestetään x:n pienenevän asteen mukaan. Ne, joilla on sama aste x:ssä, järjestetään y:n pienenevän asteen mukaan. Ne, joilla on sama aste x:ssä ja y:ssä, järjestetään z:n pienenevien asteiden mukaan.

Esimerkki

Yksinkertainen C++-ohjelma kahden polynomin kertomiseen

 #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