A LINKELT LISTA ALKALMAZÁSA

Ebben a cikkben részletesen megismerjük a linkelt listás alkalmazásokat.

Mit értesz linkelt lista alatt?

A linkelt lista egy lineáris adatstruktúra, amely csomópontoknak nevezett elemekből áll, ahol minden csomópont két részből áll: egy információs részből és egy hivatkozási részből, amelyeket a következő mutató résznek is neveznek.

A linkelt listát sokféle alkalmazásban használják, mint pl

vékony algoritmus

Polinomiális manipulációs ábrázolás
Hosszú pozitív egész számok összeadása
Ritka mátrixok ábrázolása
Hosszú pozitív egész számok összeadása
Szimbólumtábla létrehozása
Levelezőlista
Memóriakezelés
A fájlok összekapcsolt kiosztása
Többszörös precíziós aritmetika stb

Polinomiális manipuláció

A polinommanipulációk a linkelt listák egyik legfontosabb alkalmazása. A polinomok a matematika fontos részét képezik, amelyet a legtöbb nyelv nem támogat adattípusként. A polinom különböző tagok gyűjteménye, amelyek mindegyike együtthatókat és kitevőket tartalmaz. Ez egy linkelt lista segítségével ábrázolható. Ez az ábrázolás hatékonysá teszi a polinomiális manipulációt.

Miközben egy polinomot csatolt listával ábrázol, minden polinom tag egy csomópontot jelent a hivatkozott listában. A feldolgozás jobb hatékonysága érdekében feltételezzük, hogy minden polinom tagját a kapcsolódó listában tároljuk a csökkenő kitevők sorrendjében. Ezenkívül nincs két tagnak egyforma kitevője, és nincs nulla együtthatója és együtthatók nélkül. Az együttható értéke 1.

A polinomot képviselő linkelt lista minden csomópontja három részből áll:

Az első rész a tag együtthatójának értékét tartalmazza.
A második rész a kitevő értékét tartalmazza.
A harmadik rész, a LINK a következő tagra (következő csomópontra) mutat.

Az alábbiakban látható egy csatolt lista csomópontjának szerkezete, amely polinomot reprezentál:

Tekintsünk egy P(x) = 7x polinomot²+ 15x³- 2x²+ 9. Itt 7, 15, -2 és 9 az együtthatók, a 4,3,2,0 pedig a polinomban szereplő tagok kitevői. Ennek a polinomnak egy csatolt listával történő ábrázolására van lehetőségünk

Figyeljük meg, hogy a csomópontok száma megegyezik a polinom tagjainak számával. Tehát 4 csomópontunk van. Ezen túlmenően a kifejezések tárolásra kerülnek, hogy csökkentsék a kitevőket a hivatkozott listában. A polinom ilyen ábrázolása linkelt listákkal nagyon egyszerűvé teszi a műveleteket, mint a kivonás, összeadás, szorzás stb., a polinomon.

Polinomok hozzáadása:

Két polinom hozzáadásához bejárjuk a P és Q listát. Vegyük a P és Q lista megfelelő tagjait, és összehasonlítjuk kitevőiket. Ha a két kitevő egyenlő, az együtthatók hozzáadásával új együttható jön létre. Ha az új együttható egyenlő 0-val, akkor a tag kiesik, ha pedig nem nulla, akkor az eredményül kapott polinomot tartalmazó új csatolt lista végére kerül. Ha az egyik kitevő nagyobb, mint a másik, akkor a megfelelő tag azonnal bekerül az új csatolt listába, és a kisebb kitevővel rendelkező tagot összehasonlítja a másik lista következő tagjával. Ha az egyik lista a másik előtt ér véget, akkor a hosszabb lista többi tagja a kapott polinomot tartalmazó új csatolt lista végére kerül beillesztésre.

Tekintsünk egy példát, amely bemutatja, hogyan történik két polinom összeadása,

szoftver tesztelés és típusok

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

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

Ezeket a polinomokat egy linkelt lista segítségével ábrázoljuk a csökkenő kitevők sorrendjében az alábbiak szerint:

Új linkelt lista létrehozásához a kapott polinomokhoz, amely adott P(x) és Q(x) polinomok összeadásával jön létre, a következő lépéseket hajtjuk végre:

Járja be a két P és Q listát, és vizsgálja meg az összes csomópontot.
Összehasonlítjuk két polinom megfelelő tagjának kitevőit. A P és Q polinomok első tagja 4-es, illetve 3-as kitevőt tartalmaz. Mivel a P polinom első tagjának kitevője nagyobb, mint a másik Q polinomé, a nagyobb kitevővel rendelkező tag bekerül az új listába. Az új lista kezdetben az alábbiak szerint néz ki:
Ezután összehasonlítjuk a P lista következő tagjának kitevőjét a Q lista jelenlegi tagjának kitevőivel. Mivel a két kitevő egyenlő, így együtthatóikat hozzáadjuk és hozzáfűzzük az új listához a következőképpen:
Ezután lépjünk a P és Q listák következő tagjára, és hasonlítsuk össze kitevőiket. Mivel mindkét tag kitevője egyenlő, és együtthatóik összeadása után 0-t kapunk, így a tag kiesik, és ezután nem kerül csomópont az új listára,
A két lista, a P és a Q következő tagjára lépve azt találjuk, hogy a megfelelő tagok kitevői azonosak 0-val. Összeadjuk az együtthatóikat, és hozzáfűzzük őket az eredményül kapott polinom új listájához az alábbiak szerint:

Példa:

C++ program két polinom hozzáadásához

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

Magyarázat:

A fenti példában egy példát hoztunk létre két polinom összegére hivatkozott lista használatával.

Kimenet:

Az alábbiakban ennek a példának a kimenete látható.

Többváltozós polinom

Egy polinomot egynél több változóval is ábrázolhatunk, azaz lehet két vagy három változó. Az alábbiakban egy csomóponti struktúra látható, amely alkalmas három változós X, Y, Z polinom reprezentálására egy egyszeresen csatolt lista segítségével.

Tekintsünk egy P(x, y, z) = 10x polinomot²és²z + 17 x²y z²- 5 xy²z+ 21 év⁴Val vel²+ 7. Ennek a polinomnak a linkelt listával történő ábrázolásakor a következők:

Az ilyen polinomban lévő tagok az x csökkenő fokának megfelelően vannak rendezve. Az x-ben azonos fokszámmal rendelkezőket y-ban csökkenő fok szerint rendezzük. Az x-ben és y-ban azonos fokszámúakat z-ben csökkenő fokok szerint rendezzük.

jvm

Példa

Egyszerű C++ program két polinom szorzására

 #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