ПРИЛОЖЕНИЕ НА СВЪРЗАН СПИСЪК

В тази статия ще разберем подробно свързаните списъчни приложения.

масив java

Какво имате предвид под свързан списък?

Свързаният списък е линейна структура от данни, състояща се от елементи, наречени възли, където всеки възел е съставен от две части: информационна част и част за връзка, наричана още част от следващия указател.

Свързаният списък се използва в голямо разнообразие от приложения, като напр

Представяне на полиномна манипулация
Събиране на дълги положителни числа
Представяне на разредени матрици
Събиране на дълги положителни числа
Създаване на таблица със символи
Пощенски списък
Управление на паметта
Свързано разпределение на файлове
Аритметика с множествена точност и др

Полиномиална манипулация

Полиномиалните манипулации са едно от най-важните приложения на свързаните списъци. Полиномите са важна част от математиката, която по своята същност не се поддържа като тип данни от повечето езици. Полиномът е набор от различни членове, всеки от които включва коефициенти и експоненти. Може да се представи с помощта на свързан списък. Това представяне прави полиномната манипулация ефективна.

Докато представлява полином с помощта на свързан списък, всеки полиномен член представлява възел в свързания списък. За да постигнем по-добра ефективност при обработката, приемаме, че членът на всеки полином се съхранява в свързания списък в реда на намаляващи експоненти. Освен това няма два члена с еднакъв показател и нито един член няма коефициент нула и без коефициенти. Коефициентът приема стойност 1.

Всеки възел на свързан списък, представляващ полином, се състои от три части:

Първата част съдържа стойността на коефициента на термина.
Втората част съдържа стойността на експонентата.
Третата част, LINK сочи към следващия член (следващ възел).

Структурата на възел от свързан списък, който представлява полином, е показана по-долу:

Да разгледаме полином P(x) = 7x²+ 15x³- 2 х²+ 9. Тук 7, 15, -2 и 9 са коефициентите, а 4,3,2,0 са показателите на членовете в полинома. При представянето на този полином с помощта на свързан списък имаме

Забележете, че броят на възлите е равен на броя на членовете в полинома. Така че имаме 4 възела. Освен това термините се съхраняват, за да намалят експонентите в свързания списък. Такова представяне на полином с помощта на свързани списъци прави много лесни операциите като изваждане, събиране, умножение и т.н. върху полинома.

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

За да добавим два полинома, преминаваме през списъка P и Q. Взимаме съответните членове от списъка P и Q и сравняваме техните показатели. Ако двата показателя са равни, коефициентите се добавят, за да се създаде нов коефициент. Ако новият коефициент е равен на 0, тогава членът отпада и ако не е нула, той се вмъква в края на новия свързан списък, съдържащ получения полином. Ако един от експонентите е по-голям от другия, съответният термин незабавно се поставя в новия свързан списък и терминът с по-малък експонент се държи за сравнение със следващия термин от другия списък. Ако един списък завършва преди другия, останалите членове на по-дългия списък се вмъкват в края на новия свързан списък, съдържащ получения полином.

Нека разгледаме един пример, за да покажем как се извършва събирането на два полинома,

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

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

Тези полиноми са представени с помощта на свързан списък в низходящ ред на експонентите, както следва:

За да генерираме нов свързан списък за получените полиноми, който се формира от добавянето на дадени полиноми P(x) и Q(x), изпълняваме следните стъпки,

Обходете двата списъка P и Q и разгледайте всички възли.
Сравняваме показателите на съответните членове на два полинома. Първият член на полиноми P и Q съдържа показатели 4 и 3, съответно. Тъй като показателят на първия член на полинома P е по-голям от другия полином Q, членът с по-голям показател се вмъква в новия списък. Новият списък първоначално изглежда както е показано по-долу:
След това сравняваме експонентата на следващия член на списъка P с експонентите на настоящия член на списъка Q. Тъй като двата показателя са равни, техните коефициенти се добавят и добавят към новия списък, както следва:
След това преминаваме към следващия член на списъците P и Q и сравняваме техните показатели. Тъй като експонентите и на двата члена са равни и след добавяне на техните коефициенти, получаваме 0, така че членът отпада и нито един възел не се добавя към новия списък след това,
Преминавайки към следващия член от двата списъка, P и Q, откриваме, че съответните членове имат едни и същи показатели, равни на 0. Добавяме техните коефициенти и ги добавяме към новия списък за получения полином, както е показано по-долу:

Пример:

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

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

Обяснение:

частична диференциация в латекс

В горния пример създадохме пример за сбор от два полинома, използвайки свързан списък.

Изход:

По-долу е резултатът от този пример.

Полином на множество променливи

Можем да представим полином с повече от една променлива, т.е. може да има две или три променливи. По-долу е дадена възлова структура, подходяща за представяне на полином с три променливи X, Y, Z, като се използва единично свързан списък.

Да разгледаме полином P(x, y, z) = 10x²и²z + 17 x²y z²- 5 xy²z+ 21y⁴с²+ 7. При представянето на този полином с помощта на свързан списък са:

Членовете в такъв полином се подреждат съответно на намаляващата степен по x. Тези с еднаква степен по x са подредени според намаляващата степен по y. Тези с еднаква степен по x и y са подредени според намаляващите степени по z.

Пример

Проста C++ програма за умножение на два полинома

 #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