UPORABA POVEZANEGA SEZNAMA

V tem članku bomo podrobno razumeli aplikacije povezanih seznamov.

Kaj mislite s povezanim seznamom?

Povezani seznam je linearna podatkovna struktura, sestavljena iz elementov, imenovanih vozlišča, pri čemer je vsako vozlišče sestavljeno iz dveh delov: informacijskega dela in povezovalnega dela, imenovanega tudi del naslednjega kazalca.

Povezani seznam se uporablja v najrazličnejših aplikacijah, kot je npr

Predstavitev polinomske manipulacije
Seštevanje dolgih pozitivnih celih števil
Predstavitev redkih matrik
Seštevanje dolgih pozitivnih celih števil
Izdelava tabele simbolov
Poštni seznam
Upravljanje pomnilnika
Povezana dodelitev datotek
Aritmetika z več natančnostjo itd

Polinomska manipulacija

Polinomske manipulacije so ena najpomembnejših aplikacij povezanih seznamov. Polinomi so pomemben del matematike, ki jih večina jezikov ne podpira kot podatkovni tip. Polinom je zbirka različnih členov, od katerih vsak obsega koeficiente in eksponente. Lahko ga predstavimo s povezanim seznamom. Ta predstavitev naredi polinomsko manipulacijo učinkovito.

Medtem ko predstavlja polinom s povezanim seznamom, vsak izraz polinoma predstavlja vozlišče na povezanem seznamu. Za večjo učinkovitost pri obdelavi predpostavimo, da je člen vsakega polinoma shranjen v povezanem seznamu v padajočem vrstnem redu eksponentov. Prav tako noben člen nima enakega eksponenta in noben člen nima koeficienta nič in brez koeficientov. Koeficient ima vrednost 1.

Vsako vozlišče povezanega seznama, ki predstavlja polinom, je sestavljeno iz treh delov:

Prvi del vsebuje vrednost koeficienta izraza.
Drugi del vsebuje vrednost eksponenta.
Tretji del, LINK kaže na naslednji člen (naslednje vozlišče).

Struktura vozlišča povezanega seznama, ki predstavlja polinom, je prikazana spodaj:

Razmislite o polinomu P(x) = 7x²+ 15x³- 2 x²+ 9. Tukaj so 7, 15, -2 in 9 koeficienti, 4,3,2,0 pa eksponenti členov v polinomu. Če ta polinom predstavimo s povezanim seznamom, imamo

Upoštevajte, da je število vozlišč enako številu členov v polinomu. Torej imamo 4 vozlišča. Poleg tega so izrazi shranjeni za zmanjšanje eksponentov na povezanem seznamu. Takšna predstavitev polinoma z uporabo povezanih seznamov zelo olajša operacije, kot so odštevanje, seštevanje, množenje itd., na polinomu.

Seštevanje polinomov:

Da seštejemo dva polinoma, prečkamo seznam P in Q. Vzamemo ustrezne člene seznama P in Q in primerjamo njune eksponente. Če sta eksponenta enaka, se koeficienta seštejeta, da se ustvari nov koeficient. Če je novi koeficient enak 0, se člen izpusti, in če ni nič, se vstavi na konec novega povezanega seznama, ki vsebuje nastali polinom. Če je eden od eksponentov večji od drugega, je ustrezen člen takoj uvrščen na nov povezan seznam, člen z manjšim eksponentom pa se primerja z naslednjim členom iz drugega seznama. Če se en seznam konča pred drugim, se preostali členi daljšega seznama vstavijo na konec novega povezanega seznama, ki vsebuje nastali polinom.

Oglejmo si primer, da pokažemo, kako se izvede seštevanje dveh polinomov,

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

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

Ti polinomi so predstavljeni s povezanim seznamom v padajočem vrstnem redu eksponentov, kot sledi:

Za ustvarjanje novega povezanega seznama za nastale polinome, ki nastanejo pri seštevanju danih polinomov P(x) in Q(x), izvedemo naslednje korake,

Prečkajte dva seznama P in Q in preglejte vsa vozlišča.
Primerjamo eksponente ustreznih členov dveh polinomov. Prvi člen polinomov P in Q vsebujeta eksponenta 4 oziroma 3. Ker je eksponent prvega člena polinoma P večji od drugega polinoma Q, je člen z večjim eksponentom vstavljen v nov seznam. Nov seznam je na začetku videti tako, kot je prikazano spodaj:
Nato primerjamo eksponent naslednjega člena seznama P z eksponenti trenutnega člena seznama Q. Ker sta eksponenta enaka, se njuna koeficienta seštejeta in dodajata novemu seznamu, kot sledi:
Nato preidemo na naslednji člen seznamov P in Q in primerjamo njune eksponente. Ker so eksponenti obeh členov enaki in po seštevanju njunih koeficientov dobimo 0, zato je člen opuščen in novemu seznamu po tem ni dodano nobeno vozlišče,
Če se premaknemo na naslednji člen obeh seznamov, P in Q, ugotovimo, da imata ustrezna člena enake eksponente, enake 0. Dodamo njihove koeficiente in jih dodamo novemu seznamu za dobljeni polinom, kot je prikazano spodaj:

primer:

Program C++ za seštevanje dveh polinomov

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

Pojasnilo:

V zgornjem primeru smo ustvarili primer vsote dveh polinomov z uporabo povezanega seznama.

Izhod:

Spodaj je rezultat tega primera.

Polinom več spremenljivk

Polinom lahko predstavimo z več kot eno spremenljivko, to je lahko dve ali tri spremenljivke. Spodaj je struktura vozlišča, primerna za predstavitev polinoma s tremi spremenljivkami X, Y, Z z uporabo enojno povezanega seznama.

Razmislite o polinomu P(x, y, z) = 10x²in²z + 17 x²y z²- 5 xy²z+ 21 let⁴z²+ 7. Pri predstavitvi tega polinoma z uporabo povezanega seznama so:

Členi v takem polinomu so urejeni glede na padajočo stopnjo po x. Tisti z enako stopnjo v x so razvrščeni glede na padajočo stopnjo v y. Tisti z enako stopnjo v x in y so razvrščeni glede na padajoče stopnje v z.

Primer

Preprost program C++ za množenje dveh polinomov

 #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