ПРИМЕНА ПОВЕЗАНЕ ЛИСТЕ

У овом чланку ћемо детаљно разумети апликације повезане листе.

Шта подразумевате под повезаном листом?

Повезана листа је линеарна структура података која се састоји од елемената који се називају чворови где се сваки чвор састоји од два дела: информационог дела и дела везе, који се такође назива следећи део показивача.

Повезана листа се користи у широком спектру апликација као што су

Представљање полиномске манипулације
Сабирање дугих позитивних целих бројева
Представљање разређених матрица
Сабирање дугих позитивних целих бројева
Креирање табеле симбола
Списак адреса
Управљање меморијом
Повезана алокација датотека
Вишеструка прецизна аритметика итд

Полиномска манипулација

Полиномске манипулације су једна од најважнијих примена повезаних листа. Полиноми су важан део математике који већина језика инхерентно не подржава као тип података. Полином је скуп различитих појмова, од којих сваки садржи коефицијенте и експоненте. Може се представити помоћу повезане листе. Ова репрезентација чини полиномску манипулацију ефикасном.

Док представља полином користећи повезану листу, сваки полиномски термин представља чвор у повезаној листи. Да бисмо постигли бољу ефикасност у обради, претпостављамо да се термин сваког полинома чува унутар повезане листе по опадајућем експоненту. Такође, два члана немају исти експонент, нити један члан нема коефицијент нуле и без коефицијената. Коефицијент узима вредност 1.

Сваки чвор повезане листе који представља полином чине три дела:

Први део садржи вредност коефицијента појма.
Други део садржи вредност експонента.
Трећи део, ЛИНК указује на следећи термин (следећи чвор).

Структура чвора повезане листе која представља полином је приказана у наставку:

Размотримо полином П(к) = 7к²+ 15к³- 2 к²+ 9. Овде су 7, 15, -2 и 9 коефицијенти, а 4,3,2,0 су експоненти чланова у полиному. О представљању овог полинома помоћу повезане листе, имамо

Запазите да је број чворова једнак броју чланова у полиному. Дакле, имамо 4 чвора. Штавише, термини се чувају да би смањили експоненте на повезаној листи. Таква репрезентација полинома помоћу повезаних листа чини операције као што су одузимање, сабирање, множење, итд., на полиному веома лаким.

Сабирање полинома:

Да бисмо сабрали два полинома, прелазимо преко листе П и К. Узимамо одговарајуће чланове листе П и К и упоредимо њихове експоненте. Ако су два експонента једнака, коефицијенти се додају да би се створио нови коефицијент. Ако је нови коефицијент једнак 0, онда се термин испушта, а ако није нула, убацује се на крај нове повезане листе која садржи резултујући полином. Ако је један од експонента већи од другог, одговарајући термин се одмах ставља у нову повезану листу, а термин са мањим експонентом се упоређује са следећим чланом са друге листе. Ако се једна листа заврши пре друге, остали термини дуже листе се убацују на крај нове повезане листе која садржи резултујући полином.

Хајде да размотримо пример као пример да покажемо како се врши сабирање два полинома,

П(к) = 3к⁴+ 2к³- 4 к²+ 7

К (к) = 5к³+ 4 к²- 5

Ови полиноми су представљени помоћу повезане листе по опадајућем експоненту на следећи начин:

Да бисмо генерисали нову повезану листу за резултујуће полиноме која се формира сабирањем датих полинома П(к) и К(к), изводимо следеће кораке,

Пређите две листе П и К и испитајте све чворове.
Упоређујемо експоненте одговарајућих чланова два полинома. Први члан полинома П и К садржи експоненте 4 и 3, респективно. Пошто је експонент првог члана полинома П већи од другог полинома К, члан који има већи експонент се убацује у нову листу. Нова листа у почетку изгледа као што је приказано у наставку:
Затим поредимо експонент следећег члана листе П са експонентима садашњег члана листе К. Пошто су два експонента једнака, њихови коефицијенти се додају и додају новој листи на следећи начин:
Затим прелазимо на следећи члан П и К листе и упоређујемо њихове експоненте. Пошто су експоненти оба ова члана једнаки и након сабирања њихових коефицијената, добијамо 0, тако да се термин испушта и ниједан чвор се не додаје новој листи након овога,
Прелазећи на следећи члан две листе, П и К, налазимо да одговарајући термини имају исте експоненте једнаке 0. Додајемо њихове коефицијенте и додајемо их новој листи за резултујући полином као што је приказано испод:

Пример:

Ц++ програм за сабирање два полинома

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

Објашњење:

У горњем примеру, креирали смо пример збира два полинома користећи повезану листу.

Излаз:

Испод је излаз овог примера.

Полином вишеструких променљивих

Можемо да представимо полином са више од једне променљиве, односно може бити две или три променљиве. Испод је структура чвора погодна за представљање полинома са три променљиве Кс, И, З коришћењем једноструко повезане листе.

Размотримо полином П(к, и, з) = 10к²и²з + 17 к²и з²- 5 ки²з+ 21г⁴Витх²+ 7. Приликом представљања овог полинома помоћу повезане листе су:

Чланови у таквом полиному су поређани према опадајућем степену по к. Они са истим степеном у к су поређани према опадајућем степену у и. Они са истим степеном по к и и поређани су према опадајућим степенима у з.

Пример

Једноставан Ц++ програм за множење два полинома

 #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