APLICAÇÃO DE LISTA VINCULADA

Neste artigo, entenderemos detalhadamente os aplicativos de lista vinculada.

O que você quer dizer com lista vinculada?

Uma lista vinculada é uma estrutura de dados linear que consiste em elementos chamados nós, onde cada nó é composto por duas partes: uma parte de informação e uma parte de link, também chamada de próxima parte de ponteiro.

A lista vinculada é usada em uma ampla variedade de aplicações, como

Representação de manipulação polinomial
Adição de inteiros positivos longos
Representação de matrizes esparsas
Adição de inteiros positivos longos
Criação de tabela de símbolos
Lista de discussão
Gerenciamento de memória
Alocação vinculada de arquivos
Aritmética de precisão múltipla, etc.

Manipulação Polinomial

As manipulações polinomiais são uma das aplicações mais importantes das listas encadeadas. Polinômios são uma parte importante da matemática e não são inerentemente suportados como tipo de dados pela maioria das linguagens. Um polinômio é uma coleção de termos diferentes, cada um compreendendo coeficientes e expoentes. Pode ser representado por meio de uma lista vinculada. Esta representação torna a manipulação polinomial eficiente.

Ao representar um polinômio usando uma lista vinculada, cada termo polinomial representa um nó na lista vinculada. Para obter melhor eficiência no processamento, assumimos que o termo de cada polinômio é armazenado na lista vinculada em ordem decrescente de expoentes. Além disso, não existem dois termos com o mesmo expoente e nenhum termo tem coeficiente zero e sem coeficientes. O coeficiente assume o valor 1.

Cada nó de uma lista vinculada que representa um polinômio constitui três partes:

A primeira parte contém o valor do coeficiente do termo.
A segunda parte contém o valor do expoente.
A terceira parte, LINK, aponta para o próximo termo (próximo nó).

A estrutura de um nó de uma lista encadeada que representa um polinômio é mostrada abaixo:

Considere um polinômio P(x) = 7x²+ 15x³- 2 x²+ 9. Aqui 7, 15, -2 e 9 são os coeficientes e 4,3,2,0 são os expoentes dos termos no polinômio. Ao representar este polinômio usando uma lista vinculada, temos

Observe que o número de nós é igual ao número de termos no polinômio. Portanto, temos 4 nós. Além disso, os termos são armazenados para diminuir os expoentes na lista vinculada. Essa representação de polinômios usando listas vinculadas torna muito fáceis operações como subtração, adição, multiplicação, etc., em polinômios.

Adição de polinômios:

Para adicionar dois polinômios, percorremos a lista P e Q. Pegamos os termos correspondentes da lista P e Q e comparamos seus expoentes. Se os dois expoentes forem iguais, os coeficientes são somados para criar um novo coeficiente. Se o novo coeficiente for igual a 0, o termo é eliminado e, se não for zero, é inserido no final da nova lista encadeada contendo o polinômio resultante. Se um dos expoentes for maior que o outro, o termo correspondente é imediatamente colocado na nova lista vinculada, e o termo com o expoente menor é mantido para ser comparado com o próximo termo da outra lista. Se uma lista terminar antes da outra, o restante dos termos da lista mais longa será inserido no final da nova lista encadeada contendo o polinômio resultante.

Vamos considerar um exemplo para mostrar como é realizada a adição de dois polinômios,

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

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

Esses polinômios são representados usando uma lista vinculada em ordem decrescente de expoentes como segue:

Para gerar uma nova lista vinculada para os polinômios resultantes que é formada pela adição de determinados polinômios P(x) e Q(x), executamos as seguintes etapas,

Percorra as duas listas P e Q e examine todos os nós.
Comparamos os expoentes dos termos correspondentes de dois polinômios. O primeiro termo dos polinômios P e Q contém os expoentes 4 e 3, respectivamente. Como o expoente do primeiro termo do polinômio P é maior que o outro polinômio Q, o termo com expoente maior é inserido na nova lista. A nova lista inicialmente se parece com a mostrada abaixo:
Em seguida, comparamos o expoente do próximo termo da lista P com os expoentes do termo atual da lista Q. Como os dois expoentes são iguais, seus coeficientes são adicionados e anexados à nova lista da seguinte forma:
Em seguida, passamos para o próximo termo das listas P e Q e comparamos seus expoentes. Como os expoentes de ambos os termos são iguais e após a adição de seus coeficientes, obtemos 0, então o termo é eliminado e nenhum nó é anexado à nova lista depois disso,
Passando para o próximo termo das duas listas, P e Q, descobrimos que os termos correspondentes têm os mesmos expoentes iguais a 0. Adicionamos seus coeficientes e os acrescentamos à nova lista para o polinômio resultante, conforme mostrado abaixo:

Exemplo:

Programa C++ para adicionar dois polinômios

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

Explicação:

No exemplo acima, criamos um exemplo de soma de dois polinômios usando lista vinculada.

Saída:

Abaixo está a saída deste exemplo.

Polinômio de múltiplas variáveis

Podemos representar um polinômio com mais de uma variável, ou seja, podem ser duas ou três variáveis. Abaixo está uma estrutura de nós adequada para representar um polinômio com três variáveis X, Y, Z usando uma lista vinculada individualmente.

Considere um polinômio P(x, y, z) = 10x²e²z + 17x²e z²- 5xy²z + 21 anos⁴Com²+ 7. Ao representar este polinômio usando lista vinculada estão:

Os termos desse polinômio são ordenados de acordo com o grau decrescente em x. Aqueles com o mesmo grau em x são ordenados de acordo com o grau decrescente em y. Aqueles com o mesmo grau em xey são ordenados de acordo com graus decrescentes em z.

Exemplo

Programa C++ simples para multiplicar dois polinômios

 #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

Aplicação de lista vinculada