ANWENDUNG DER VERKNÜPFTEN LISTE

In diesem Artikel werden wir die Anwendungen verknüpfter Listen im Detail verstehen.

Was meinst du mit verlinkter Liste?

Eine verknüpfte Liste ist eine lineare Datenstruktur, die aus Elementen besteht, die als Knoten bezeichnet werden, wobei jeder Knoten aus zwei Teilen besteht: einem Informationsteil und einem Verknüpfungsteil, der auch als nächster Zeigerteil bezeichnet wird.

String-Vergleich Java

Verknüpfte Listen werden in einer Vielzahl von Anwendungen verwendet, z

Darstellung der Polynommanipulation
Addition langer positiver Ganzzahlen
Darstellung dünn besetzter Matrizen
Addition langer positiver Ganzzahlen
Erstellung einer Symboltabelle
Mailingliste
Speicherverwaltung
Verknüpfte Zuordnung von Dateien
Mehrfachpräzisionsarithmetik usw

Polynommanipulation

Polynommanipulationen sind eine der wichtigsten Anwendungen verknüpfter Listen. Polynome sind ein wichtiger Teil der Mathematik und werden von den meisten Sprachen nicht grundsätzlich als Datentyp unterstützt. Ein Polynom ist eine Sammlung verschiedener Terme, die jeweils Koeffizienten und Exponenten umfassen. Es kann mithilfe einer verknüpften Liste dargestellt werden. Diese Darstellung macht die Polynommanipulation effizient.

Bei der Darstellung eines Polynoms mithilfe einer verknüpften Liste stellt jeder Polynomterm einen Knoten in der verknüpften Liste dar. Um eine effizientere Verarbeitung zu erreichen, gehen wir davon aus, dass der Term jedes Polynoms in der Reihenfolge abnehmender Exponenten in der verknüpften Liste gespeichert ist. Außerdem haben keine zwei Terme den gleichen Exponenten und kein Term hat einen Koeffizienten von Null und ohne Koeffizienten. Der Koeffizient nimmt den Wert 1 an.

Jeder Knoten einer verknüpften Liste, die ein Polynom darstellt, besteht aus drei Teilen:

Der erste Teil enthält den Wert des Koeffizienten des Termes.
Der zweite Teil enthält den Wert des Exponenten.
Der dritte Teil, LINK, zeigt auf den nächsten Begriff (nächsten Knoten).

Die Struktur eines Knotens einer verknüpften Liste, die ein Polynom darstellt, ist unten dargestellt:

Betrachten Sie ein Polynom P(x) = 7x²+ 15x³- 2x²+ 9. Hier sind 7, 15, -2 und 9 die Koeffizienten und 4,3,2,0 die Exponenten der Terme im Polynom. Bei der Darstellung dieses Polynoms mithilfe einer verknüpften Liste haben wir Folgendes:

Beachten Sie, dass die Anzahl der Knoten der Anzahl der Terme im Polynom entspricht. Wir haben also 4 Knoten. Darüber hinaus werden die Terme gespeichert, um Exponenten in der verknüpften Liste zu verringern. Eine solche Darstellung von Polynomen mithilfe verknüpfter Listen macht Operationen wie Subtraktion, Addition, Multiplikation usw. auf Polynomen sehr einfach.

Addition von Polynomen:

Um zwei Polynome zu addieren, durchlaufen wir die Liste P und Q. Wir nehmen entsprechende Terme der Liste P und Q und vergleichen ihre Exponenten. Wenn die beiden Exponenten gleich sind, werden die Koeffizienten addiert, um einen neuen Koeffizienten zu erstellen. Wenn der neue Koeffizient gleich 0 ist, wird der Term gelöscht, und wenn er nicht Null ist, wird er am Ende der neuen verknüpften Liste eingefügt, die das resultierende Polynom enthält. Wenn einer der Exponenten größer als der andere ist, wird der entsprechende Term sofort in die neue verknüpfte Liste eingefügt und der Term mit dem kleineren Exponenten wird zum Vergleich mit dem nächsten Term aus der anderen Liste zurückgehalten. Wenn eine Liste vor der anderen endet, werden die restlichen Terme der längeren Liste am Ende der neuen verknüpften Liste eingefügt, die das resultierende Polynom enthält.

Betrachten wir ein Beispiel, um zu zeigen, wie die Addition zweier Polynome durchgeführt wird:

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

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

Diese Polynome werden mithilfe einer verknüpften Liste in der Reihenfolge abnehmender Exponenten wie folgt dargestellt:

Um eine neue verknüpfte Liste für die resultierenden Polynome zu generieren, die durch Addition der gegebenen Polynome P(x) und Q(x) gebildet wird, führen wir die folgenden Schritte aus:

Durchlaufen Sie die beiden Listen P und Q und untersuchen Sie alle Knoten.
Wir vergleichen die Exponenten der entsprechenden Terme zweier Polynome. Der erste Term der Polynome P und Q enthält die Exponenten 4 bzw. 3. Da der Exponent des ersten Termes des Polynoms P größer ist als der des anderen Polynoms Q, wird der Term mit dem größeren Exponenten in die neue Liste eingefügt. Die neue Liste sieht zunächst wie folgt aus:
Anschließend vergleichen wir den Exponenten des nächsten Termes der Liste P mit den Exponenten des aktuellen Termes der Liste Q. Da die beiden Exponenten gleich sind, werden ihre Koeffizienten wie folgt addiert und an die neue Liste angehängt:
Dann gehen wir zum nächsten Term der P- und Q-Listen und vergleichen ihre Exponenten. Da die Exponenten dieser beiden Terme gleich sind und wir nach Addition ihrer Koeffizienten 0 erhalten, wird der Term gelöscht und danach kein Knoten an die neue Liste angehängt.
Wenn wir zum nächsten Term der beiden Listen, P und Q, übergehen, stellen wir fest, dass die entsprechenden Terme die gleichen Exponenten gleich 0 haben. Wir addieren ihre Koeffizienten und hängen sie an die neue Liste für das resultierende Polynom an, wie unten gezeigt:

Beispiel:

C++-Programm zum Addieren zweier Polynome

Dynamisches Java-Array

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

Erläuterung:

Im obigen Beispiel haben wir mithilfe einer verknüpften Liste ein Beispiel für die Summe zweier Polynome erstellt.

Ausgabe:

Unten finden Sie die Ausgabe dieses Beispiels.

Polynom mehrerer Variablen

Wir können ein Polynom mit mehr als einer Variablen darstellen, d. h. es können zwei oder drei Variablen sein. Nachfolgend finden Sie eine Knotenstruktur, die zur Darstellung eines Polynoms mit drei Variablen X, Y, Z mithilfe einer einfach verknüpften Liste geeignet ist.

wie man int in string umwandelt

Betrachten Sie ein Polynom P(x, y, z) = 10x²Und²z + 17 x²y z²- 5 xy²z+ 21y⁴Mit²+ 7. Zur Darstellung dieses Polynoms mithilfe einer verknüpften Liste gilt Folgendes:

Terme in einem solchen Polynom werden entsprechend dem abnehmenden Grad in x geordnet. Diejenigen mit demselben Grad in x werden nach abnehmendem Grad in y geordnet. Diejenigen mit demselben Grad in x und y werden nach abnehmendem Grad in z geordnet.

Beispiel

Einfaches C++-Programm zum Multiplizieren zweier Polynome

 #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