TOEPASSING VAN GEKOPPELDE LIJST

In dit artikel zullen we de gekoppelde lijsttoepassingen in detail begrijpen.

Wat bedoel je met gekoppelde lijst?

Een gekoppelde lijst is een lineaire datastructuur die bestaat uit elementen die knooppunten worden genoemd, waarbij elk knooppunt uit twee delen bestaat: een informatiegedeelte en een linkgedeelte, ook wel het volgende pointergedeelte genoemd.

Gekoppelde lijst wordt gebruikt in een breed scala aan toepassingen, zoals

abstracte methoden

Polynomiale manipulatierepresentatie
Optelling van lange positieve gehele getallen
Vertegenwoordiging van schaarse matrices
Optelling van lange positieve gehele getallen
Het maken van symbooltabellen
Mailinglijst
Geheugen management
Gekoppelde toewijzing van bestanden
Meerdere precisie rekenkunde etc

Polynomiale manipulatie

Polynomiale manipulaties zijn een van de belangrijkste toepassingen van gekoppelde lijsten. Polynomen vormen een belangrijk onderdeel van de wiskunde en worden door de meeste talen niet inherent als gegevenstype ondersteund. Een polynoom is een verzameling verschillende termen, elk bestaande uit coëfficiënten en exponenten. Het kan worden weergegeven met behulp van een gekoppelde lijst. Deze representatie maakt polynomiale manipulatie efficiënt.

Hoewel een polynoom wordt weergegeven met behulp van een gekoppelde lijst, vertegenwoordigt elke polynoomterm een knooppunt in de gekoppelde lijst. Om een betere efficiëntie bij de verwerking te krijgen, gaan we ervan uit dat de term van elke polynoom in de gekoppelde lijst wordt opgeslagen in de volgorde van afnemende exponenten. Bovendien hebben geen twee termen dezelfde exponent, en geen enkele term heeft een nulcoëfficiënt en zonder coëfficiënten. De coëfficiënt heeft de waarde 1.

Elk knooppunt van een gekoppelde lijst die een polynoom vertegenwoordigt, bestaat uit drie delen:

Het eerste deel bevat de waarde van de coëfficiënt van de term.
Het tweede deel bevat de waarde van de exponent.
Het derde deel, LINK, verwijst naar de volgende term (volgende knoop).

De structuur van een knooppunt van een gekoppelde lijst die een polynoom vertegenwoordigt, wordt hieronder weergegeven:

Beschouw een polynoom P(x) = 7x²+ 15x³- 2x²+ 9. Hier zijn 7, 15, -2 en 9 de coëfficiënten, en 4,3,2,0 de exponenten van de termen in de polynoom. Als we deze polynoom weergeven met behulp van een gekoppelde lijst, hebben we dat gedaan

Merk op dat het aantal knooppunten gelijk is aan het aantal termen in de polynoom. We hebben dus 4 knooppunten. Bovendien worden de termen opgeslagen om het aantal exponenten in de gekoppelde lijst te verkleinen. Een dergelijke weergave van polynomen met behulp van gekoppelde lijsten maakt de bewerkingen zoals aftrekken, optellen, vermenigvuldigen, enz., op polynomen zeer eenvoudig.

Optelling van veeltermen:

Om twee polynomen op te tellen, doorkruisen we de lijst P en Q. We nemen overeenkomstige termen van de lijst P en Q en vergelijken hun exponenten. Als de twee exponenten gelijk zijn, worden de coëfficiënten opgeteld om een nieuwe coëfficiënt te creëren. Als de nieuwe coëfficiënt gelijk is aan 0, wordt de term geschrapt, en als deze niet nul is, wordt deze ingevoegd aan het einde van de nieuwe gekoppelde lijst die de resulterende polynoom bevat. Als een van de exponenten groter is dan de andere, wordt de corresponderende term onmiddellijk in de nieuwe gekoppelde lijst geplaatst en wordt de term met de kleinere exponent geacht te worden vergeleken met de volgende term uit de andere lijst. Als de ene lijst eerder eindigt dan de andere, wordt de rest van de termen van de langere lijst ingevoegd aan het einde van de nieuwe gekoppelde lijst die de resulterende polynoom bevat.

Laten we een voorbeeld bekijken om te laten zien hoe de optelling van twee polynomen wordt uitgevoerd,

aangrenzende hoeken

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

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

csma en csma-cd

Deze polynomen worden als volgt weergegeven met behulp van een gekoppelde lijst in volgorde van afnemende exponenten:

Om een nieuwe gekoppelde lijst te genereren voor de resulterende polynomen die wordt gevormd door de optelling van gegeven polynomen P(x) en Q(x), voeren we de volgende stappen uit:

Doorloop de twee lijsten P en Q en onderzoek alle knooppunten.
We vergelijken de exponenten van de overeenkomstige termen van twee polynomen. De eerste term van polynomen P en Q bevatten respectievelijk exponenten 4 en 3. Omdat de exponent van de eerste term van de polynoom P groter is dan de andere polynoom Q, wordt de term met een grotere exponent in de nieuwe lijst ingevoegd. De nieuwe lijst ziet er in eerste instantie uit zoals hieronder weergegeven:
Vervolgens vergelijken we de exponent van de volgende term van de lijst P met de exponenten van de huidige term van lijst Q. Omdat de twee exponenten gelijk zijn, worden hun coëfficiënten als volgt opgeteld en toegevoegd aan de nieuwe lijst:
Vervolgens gaan we naar de volgende term van de P- en Q-lijsten en vergelijken we hun exponenten. Omdat exponenten van beide termen gelijk zijn en na optelling van hun coëfficiënten krijgen we 0, dus de term vervalt en er wordt hierna geen knooppunt aan de nieuwe lijst toegevoegd.
Als we naar de volgende term van de twee lijsten gaan, P en Q, zien we dat de overeenkomstige termen dezelfde exponenten hebben die gelijk zijn aan 0. We voegen hun coëfficiënten toe en voegen ze toe aan de nieuwe lijst voor de resulterende polynoom, zoals hieronder weergegeven:

Voorbeeld:

C++-programma om twee polynomen toe te voegen

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

Uitleg:

In het bovenstaande voorbeeld hebben we een voorbeeld gemaakt van de som van twee polynomen met behulp van een gekoppelde lijst.

Uitgang:

Java-vergelijkbare interface

Hieronder ziet u de uitvoer van dit voorbeeld.

Polynoom van meerdere variabelen

We kunnen een polynoom met meer dan één variabele weergeven, d.w.z. het kunnen twee of drie variabelen zijn. Hieronder ziet u een knooppuntstructuur die geschikt is voor het weergeven van een polynoom met drie variabelen X, Y, Z met behulp van een enkelvoudig gekoppelde lijst.

Beschouw een polynoom P(x, y, z) = 10x²En²z + 17 x²y z²- 5 xy²z+ 21j⁴Met²+ 7. Over het weergeven van deze polynoom met behulp van een gekoppelde lijst zijn:

Termen in zo'n polynoom worden dienovereenkomstig geordend in afnemende mate in x. Degenen met dezelfde graad in x worden geordend volgens afnemende graad in y. Degenen met dezelfde graad in x en y worden geordend volgens afnemende graden in z.

Voorbeeld

Eenvoudig C++-programma om twee polynomen te vermenigvuldigen

 #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