ZASTOSOWANIE LISTY POŁĄCZONEJ

W tym artykule szczegółowo omówimy aplikacje z listami połączonymi.

Co masz na myśli mówiąc lista połączona?

Lista połączona to liniowa struktura danych składająca się z elementów zwanych węzłami, przy czym każdy węzeł składa się z dwóch części: części informacyjnej i części łączącej, zwanej także częścią następnego wskaźnika.

Lista połączona jest używana w wielu różnych zastosowaniach, takich jak

Reprezentacja manipulacji wielomianowej
Dodawanie długich dodatnich liczb całkowitych
Reprezentacja rzadkich macierzy
Dodawanie długich dodatnich liczb całkowitych
Tworzenie tabeli symboli
Lista mailingowa
Zarządzanie pamięcią
Połączona alokacja plików
Arytmetyka wielokrotnej precyzji itp

Manipulacja wielomianami

Manipulacje wielomianami są jednym z najważniejszych zastosowań list połączonych. Wielomiany są ważną częścią matematyki, która nie jest z natury obsługiwana jako typ danych w większości języków. Wielomian to zbiór różnych terminów, z których każdy zawiera współczynniki i wykładniki. Można to przedstawić za pomocą połączonej listy. Taka reprezentacja sprawia, że manipulacja wielomianami jest wydajna.

Reprezentując wielomian za pomocą listy połączonej, każdy składnik wielomianu reprezentuje węzeł na liście połączonej. Aby uzyskać lepszą efektywność przetwarzania, zakładamy, że wyraz każdego wielomianu jest przechowywany na połączonej liście w kolejności malejących wykładników. Ponadto żadne dwa wyrazy nie mają tego samego wykładnika i żaden termin nie ma współczynnika zerowego i nie ma współczynników. Współczynnik przyjmuje wartość 1.

Każdy węzeł połączonej listy reprezentującej wielomian składa się z trzech części:

Pierwsza część zawiera wartość współczynnika składnika.
Druga część zawiera wartość wykładnika.
Trzecia część LINK wskazuje na kolejny termin (następny węzeł).

Poniżej pokazano strukturę węzła połączonej listy reprezentującej wielomian:

Rozważmy wielomian P(x) = 7x²+ 15x³- 2x²+ 9. Tutaj 7, 15, -2 i 9 to współczynniki, a 4,3,2,0 to wykładniki wyrazów wielomianu. Przedstawiając ten wielomian za pomocą połączonej listy, mamy

Zauważ, że liczba węzłów jest równa liczbie wyrazów wielomianu. Mamy więc 4 węzły. Co więcej, terminy są przechowywane w celu zmniejszenia wykładników na połączonej liście. Taka reprezentacja wielomianu za pomocą połączonych list sprawia, że operacje takie jak odejmowanie, dodawanie, mnożenie itp. na wielomianach są bardzo łatwe.

Dodawanie wielomianów:

Aby dodać dwa wielomiany, przechodzimy przez listę P i Q. Bierzemy odpowiednie wyrazy z listy P i Q i porównujemy ich wykładniki. Jeśli oba wykładniki są równe, współczynniki są dodawane, aby utworzyć nowy współczynnik. Jeśli nowy współczynnik jest równy 0, wówczas termin jest usuwany, a jeśli nie wynosi zero, jest wstawiany na końcu nowej połączonej listy zawierającej wynikowy wielomian. Jeśli jeden z wykładników jest większy od drugiego, odpowiedni termin jest natychmiast umieszczany na nowej połączonej liście, a termin z mniejszym wykładnikiem jest porównywany z kolejnym terminem z drugiej listy. Jeśli jedna lista kończy się przed drugą, pozostałe terminy dłuższej listy wstawiane są na końcu nowej połączonej listy zawierającej wynikowy wielomian.

Rozważmy przykład, który pokaże, jak przeprowadzane jest dodawanie dwóch wielomianów,

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

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

Te wielomiany są reprezentowane za pomocą połączonej listy w kolejności malejących wykładników w następujący sposób:

Aby wygenerować nową listę połączoną dla wynikowych wielomianów, utworzoną przez dodanie danych wielomianów P(x) i Q(x), wykonujemy następujące kroki:

Przejdź przez dwie listy P i Q i sprawdź wszystkie węzły.
Porównujemy wykładniki odpowiednich wyrazów dwóch wielomianów. Pierwszy wyraz wielomianów P i Q zawiera odpowiednio wykładniki 4 i 3. Ponieważ wykładnik pierwszego wyrazu wielomianu P jest większy niż drugiego wielomianu Q, do nowej listy wstawiany jest wyraz mający większy wykładnik. Nowa lista początkowo wygląda tak, jak pokazano poniżej:
Następnie porównujemy wykładnik następnego wyrazu listy P z wykładnikami obecnego wyrazu listy Q. Ponieważ oba wykładniki są równe, ich współczynniki są dodawane i dołączane do nowej listy w następujący sposób:
Następnie przechodzimy do kolejnego wyrazu list P i Q i porównujemy ich wykładniki. Ponieważ wykładniki obu tych wyrazów są równe i po dodaniu ich współczynników otrzymujemy 0, więc wyraz jest usuwany i po tym nie jest dodawany żaden węzeł do nowej listy,
Przechodząc do następnego wyrazu obu list, P i Q, stwierdzamy, że odpowiednie wyrazy mają te same wykładniki równe 0. Dodajemy ich współczynniki i dołączamy je do nowej listy dla powstałego wielomianu, jak pokazano poniżej:

Przykład:

Program w C++ dodający dwa wielomiany

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

Wyjaśnienie:

W powyższym przykładzie utworzyliśmy przykład sumy dwóch wielomianów za pomocą listy połączonej.

Wyjście:

polecenie powrotu Java

Poniżej znajduje się wynik tego przykładu.

Wielomian wielu zmiennych

Możemy przedstawić wielomian z więcej niż jedną zmienną, to znaczy może to być dwie lub trzy zmienne. Poniżej znajduje się struktura węzłowa odpowiednia do reprezentowania wielomianu z trzema zmiennymi X, Y, Z przy użyciu pojedynczo połączonej listy.

Rozważmy wielomian P(x, y, z) = 10x²I²z + 17 x²y z²- 5x²z+ 21y⁴z²+ 7. Do reprezentacji tego wielomianu za pomocą listy połączonej należą:

Wyrazy takiego wielomianu są uporządkowane odpowiednio do stopnia malejącego w x. Te o tym samym stopniu w x są uporządkowane według malejącego stopnia w y. Te o tym samym stopniu w x i y są uporządkowane według malejących stopni w z.

Przykład

Prosty program w C++ służący do mnożenia dwóch wielomianów

 #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