PRIMJENA POVEZANOG POPISA

U ovom ćemo članku detaljno razumjeti aplikacije povezanih popisa.

Što mislite pod povezanim popisom?

Povezani popis je linearna struktura podataka koja se sastoji od elemenata koji se nazivaju čvorovi gdje je svaki čvor sastavljen od dva dijela: informacijskog dijela i povezničkog dijela, koji se također naziva i sljedeći pokazivački dio.

Povezani popis koristi se u raznim aplikacijama kao što su

Predstavljanje polinomske manipulacije
Zbrajanje dugih pozitivnih cijelih brojeva
Predstavljanje rijetkih matrica
Zbrajanje dugih pozitivnih cijelih brojeva
Izrada tablice simbola
E-mail lista
Upravljanje memorijom
Povezana dodjela datoteka
Aritmetika višestruke preciznosti itd

Polinomska manipulacija

Manipulacije polinomima jedna su od najvažnijih primjena povezanih popisa. Polinomi su važan dio matematike koji većina jezika inherentno ne podržava kao vrstu podataka. Polinom je skup različitih članova, od kojih svaki sadrži koeficijente i eksponente. Može se prikazati pomoću povezanog popisa. Ovaj prikaz čini polinomnu manipulaciju učinkovitom.

Dok predstavlja polinom pomoću povezanog popisa, svaki izraz polinoma predstavlja čvor na povezanom popisu. Da bismo dobili bolju učinkovitost u obradi, pretpostavljamo da je član svakog polinoma pohranjen unutar povezanog popisa u opadajućem redoslijedu eksponenata. Također, niti jedan član nema isti eksponent, niti jedan član nema koeficijent nula i bez koeficijenata. Koeficijent ima vrijednost 1.

Svaki čvor povezane liste koja predstavlja polinom sastoji se od tri dijela:

Prvi dio sadrži vrijednost koeficijenta člana.
Drugi dio sadrži vrijednost eksponenta.
Treći dio, LINK pokazuje na sljedeći član (sljedeći čvor).

Struktura čvora povezane liste koja predstavlja polinom prikazana je u nastavku:

Promotrimo polinom P(x) = 7x²+ 15x³- 2 x²+ 9. Ovdje su 7, 15, -2 i 9 koeficijenti, a 4,3,2,0 eksponenti članova u polinomu. Predstavljajući ovaj polinom pomoću povezane liste, imamo

Uočite da je broj čvorova jednak broju članova u polinomu. Dakle, imamo 4 čvora. Štoviše, pojmovi se pohranjuju kako bi se smanjili eksponenti na povezanom popisu. Takva reprezentacija polinoma korištenjem povezanih popisa čini operacije poput oduzimanja, zbrajanja, množenja itd. na polinomu vrlo jednostavnima.

Zbrajanje polinoma:

Da bismo zbrojili dva polinoma, prelazimo listu P i Q. Uzimamo odgovarajuće članove liste P i Q i uspoređujemo njihove eksponente. Ako su dva eksponenta jednaka, koeficijenti se zbrajaju kako bi se dobio novi koeficijent. Ako je novi koeficijent jednak 0, tada se član ispušta, a ako nije nula, umeće se na kraj nove povezane liste koja sadrži rezultirajući polinom. Ako je jedan od eksponenata veći od drugog, odgovarajući termin se odmah stavlja u novi povezani popis, a termin s manjim eksponentom uspoređuje se sa sljedećim izrazom iz drugog popisa. Ako jedan popis završi prije drugog, ostatak članova duljeg popisa umeće se na kraj novog povezanog popisa koji sadrži rezultirajući polinom.

Razmotrimo primjer primjer koji pokazuje kako se izvodi zbrajanje dvaju polinoma,

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

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

Ovi polinomi predstavljeni su pomoću povezanog popisa prema opadajućem redoslijedu eksponenata kako slijedi:

Za generiranje novog povezanog popisa za rezultirajuće polinome koji se formira zbrajanjem zadanih polinoma P(x) i Q(x), izvodimo sljedeće korake,

Pređite dvije liste P i Q i ispitajte sve čvorove.
Uspoređujemo eksponente odgovarajućih članova dvaju polinoma. Prvi član polinoma P i Q sadrži eksponente 4, odnosno 3. Budući da je eksponent prvog člana polinoma P veći od drugog polinoma Q, član koji ima veći eksponent umetnut je u novu listu. Novi popis u početku izgleda kao što je prikazano u nastavku:
Zatim uspoređujemo eksponent sljedećeg člana liste P s eksponentima sadašnjeg člana liste Q. Budući da su dva eksponenta jednaka, njihovi se koeficijenti zbrajaju i dodaju novoj listi na sljedeći način:
Zatim prelazimo na sljedeći član P i Q lista i uspoređujemo njihove eksponente. Budući da su eksponenti oba ova izraza jednaki i nakon zbrajanja njihovih koeficijenata, dobivamo 0, tako da se član ispušta, a nijedan čvor se ne dodaje novoj listi nakon toga,
Prelaskom na sljedeći član dvaju popisa, P i Q, nalazimo da odgovarajući izrazi imaju iste eksponente jednake 0. Dodajemo njihove koeficijente i pridružujemo ih novom popisu za rezultirajući polinom kao što je prikazano u nastavku:

Primjer:

C++ program za zbrajanje dvaju polinoma

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

Obrazloženje:

U gornjem primjeru, stvorili smo primjer zbroja dvaju polinoma pomoću povezanog popisa.

Izlaz:

Ispod je rezultat ovog primjera.

Polinom više varijabli

Polinom možemo prikazati s više od jedne varijable, tj. to mogu biti dvije ili tri varijable. Ispod je struktura čvora prikladna za predstavljanje polinoma s tri varijable X, Y, Z pomoću jednostruko povezane liste.

Razmotrimo polinom P(x, y, z) = 10x²i²z + 17 x²y z²- 5 xy²z+ 21g⁴S²+ 7. Pri predstavljanju ovog polinoma pomoću povezane liste su:

Članovi u takvom polinomu poredani su prema opadajućem stupnju po x. Oni s istim stupnjem u x poredani su prema opadajućem stupnju u y. Oni s istim stupnjem u x i y poredani su prema opadajućim stupnjevima u z.

Primjer

Jednostavan C++ program za množenje dvaju polinoma

 #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