ЗАСТОСУВАННЯ ЗВ'ЯЗАНОГО СПИСКУ

У цій статті ми детально розберемо програми пов’язаного списку.

перетворення int на рядок

Що ви маєте на увазі під пов’язаним списком?

Зв’язаний список — це лінійна структура даних, що складається з елементів, які називаються вузлами, де кожен вузол складається з двох частин: інформаційної частини та частини посилання, яку також називають частиною вказівника наступного.

Зв'язаний список використовується в широкому спектрі програм, наприклад

Поліноміальне представлення маніпуляції
Додавання довгих натуральних чисел
Представлення розріджених матриць
Додавання довгих натуральних чисел
Створення таблиці символів
Список адресатів
Управління пам'яттю
Зв'язане розміщення файлів
Арифметика множинної точності тощо

Поліноміальна маніпуляція

Поліноміальні маніпуляції є одним із найважливіших застосувань пов’язаних списків. Поліноми є важливою частиною математики, яка за своєю суттю не підтримується як тип даних більшістю мов. Поліном — це сукупність різних членів, кожен з яких містить коефіцієнти та показники степеня. Його можна представити за допомогою зв'язаного списку. Це представлення робить поліноміальні маніпуляції ефективними.

Під час представлення полінома за допомогою зв’язаного списку кожен термін полінома представляє вузол у зв’язаному списку. Щоб підвищити ефективність обробки, ми припускаємо, що член кожного полінома зберігається в зв’язаному списку в порядку зменшення експонент. Крім того, немає двох доданків з однаковим показником степеня, і жоден доданок не має нульового коефіцієнта або без коефіцієнтів. Коефіцієнт приймає значення 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⁴+ 2х³- 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;>

Пояснення:

gimp змінює колір

У наведеному вище прикладі ми створили приклад суми двох поліномів за допомогою зв’язаного списку.

Вихід:

Нижче наведено результати цього прикладу.

Поліном багатьох змінних

Ми можемо представити поліном більш ніж однією змінною, тобто це може бути дві або три змінні. Нижче наведено структуру вузлів, придатну для представлення полінома з трьома змінними X, Y, Z за допомогою однозв’язаного списку.

Розглянемо поліном P(x, y, z) = 10x²і²z + 17 x²y z²- 5 ху²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