TechCodeview

V tomto článku podrobně porozumíme aplikacím propojeného seznamu.

Co myslíte propojeným seznamem?

Propojený seznam je lineární datová struktura sestávající z prvků nazývaných uzly, kde se každý uzel skládá ze dvou částí: informační části a spojovací části, které se také říká další ukazatel.

příkaz java case

Propojený seznam se používá v celé řadě aplikací, jako je např

• Reprezentace manipulace s polynomem
• Sčítání dlouhých kladných celých čísel
• Reprezentace řídkých matic
• Sčítání dlouhých kladných celých čísel
• Vytvoření tabulky symbolů
• Poštovní seznam
• Správa paměti
• Propojená alokace souborů
• Vícenásobná přesná aritmetika atd

Polynomiální manipulace

Polynomiální manipulace jsou jednou z nejdůležitějších aplikací spojených seznamů. Polynomy jsou důležitou součástí matematiky, kterou většina jazyků jako datový typ ze své podstaty nepodporuje. Polynom je sbírka různých termínů, z nichž každý obsahuje koeficienty a exponenty. Může být reprezentován pomocí propojeného seznamu. Tato reprezentace umožňuje efektivní manipulaci s polynomem.

Zatímco představuje polynom pomocí propojeného seznamu, každý termín polynomu představuje uzel v propojeném seznamu. Abychom získali lepší efektivitu při zpracování, předpokládáme, že člen každého polynomu je uložen v propojeném seznamu v pořadí klesajících exponentů. Také žádné dva členy nemají stejný exponent a žádný člen nemá nulový koeficient a bez koeficientů. Koeficient má hodnotu 1.

Každý uzel spojeného seznamu představující polynom tvoří tři části:

• První část obsahuje hodnotu koeficientu termínu.
• Druhá část obsahuje hodnotu exponentu.
• Třetí část, LINK, ukazuje na další termín (další uzel).

Struktura uzlu propojeného seznamu, který představuje polynom, je uvedena níže:

Uvažujme polynom P(x) = 7x²+ 15x³- 2x²+ 9. Zde jsou 7, 15, -2 a 9 koeficienty a 4,3,2,0 jsou exponenty členů v polynomu. Při reprezentaci tohoto polynomu pomocí propojeného seznamu máme

java kolekce java

Všimněte si, že počet uzlů se rovná počtu členů v polynomu. Máme tedy 4 uzly. Kromě toho jsou termíny uloženy pro snížení exponentů v propojeném seznamu. Taková reprezentace polynomu pomocí spojených seznamů velmi usnadňuje operace jako odčítání, sčítání, násobení atd. s polynomem.

Sčítání polynomů:

Pro sečtení dvou polynomů procházíme seznam P a Q. Vezmeme odpovídající členy ze seznamu P a Q a porovnáme jejich exponenty. Pokud jsou dva exponenty stejné, koeficienty se sečtou a vytvoří se nový koeficient. Pokud je nový koeficient roven 0, pak se člen vypustí, a pokud není nula, vloží se na konec nového spojeného seznamu obsahujícího výsledný polynom. Pokud je jeden z exponentů větší než druhý, odpovídající výraz se okamžitě umístí do nového spojeného seznamu a výraz s menším exponentem se porovná s dalším výrazem z druhého seznamu. Pokud jeden seznam končí před druhým, zbytek podmínek delšího seznamu se vloží na konec nového propojeného seznamu obsahujícího výsledný polynom.

Podívejme se na příklad, který ukazuje, jak se provádí sčítání dvou polynomů,

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

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

Tyto polynomy jsou reprezentovány pomocí propojeného seznamu v pořadí klesajících exponentů takto:

Pro vygenerování nového propojeného seznamu pro výsledné polynomy, který se vytvoří sčítáním daných polynomů P(x) a Q(x), provedeme následující kroky:

1. Projděte dva seznamy P a Q a prozkoumejte všechny uzly.
2. Porovnáme exponenty odpovídajících členů dvou polynomů. První člen polynomů P a Q obsahuje exponenty 4 a 3, v tomto pořadí. Protože exponent prvního členu polynomu P je větší než druhého polynomu Q, je do nového seznamu vložen člen s větším exponentem. Nový seznam zpočátku vypadá takto:
   
3. Potom porovnáme exponent dalšího členu seznamu P s exponenty současného členu seznamu Q. Protože jsou oba exponenty stejné, jejich koeficienty se sčítají a připojují k novému seznamu následovně:
   
4. Poté přejdeme k dalšímu členu seznamů P a Q a porovnáme jejich exponenty. Vzhledem k tomu, že exponenty obou těchto členů jsou stejné a po sečtení jejich koeficientů dostaneme 0, takže člen je vypuštěn a do nového seznamu se poté nepřipojí žádný uzel,
   
5. Přesuneme-li se na další člen ze dvou seznamů, P a Q, zjistíme, že odpovídající členy mají stejné exponenty rovné 0. Sečteme jejich koeficienty a připojíme je k novému seznamu pro výsledný polynom, jak je ukázáno níže:
   

Příklad:

C++ program pro přidání dvou polynomů

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

Vysvětlení:

přeškrtnutí

Ve výše uvedeném příkladu jsme vytvořili příklad součtu dvou polynomů pomocí propojeného seznamu.

Výstup:

Níže je výstup tohoto příkladu.

Polynom více proměnných

Můžeme reprezentovat polynom s více než jednou proměnnou, tj. mohou to být dvě nebo tři proměnné. Níže je uvedena struktura uzlů vhodná pro reprezentaci polynomu se třemi proměnnými X, Y, Z pomocí jednoduše propojeného seznamu.

Uvažujme polynom P(x, y, z) = 10x²a²z + 17 x²y z²- 5 xy²z+ 21 let⁴S²+ 7. Při znázornění tohoto polynomu pomocí propojeného seznamu jsou:

Termíny v takovém polynomu jsou seřazeny podle klesajícího stupně v x. Ty se stejným stupněm v x jsou seřazeny podle klesajícího stupně v y. Ty se stejným stupněm v x a y jsou seřazeny podle klesajících stupňů v z.

javascriptový komentář

Příklad

Jednoduchý program v C++ pro násobení dvou polynomů

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