SAISTĪTĀ SARAKSTA PIELIETOŠANA

Šajā rakstā mēs detalizēti sapratīsim saistīto sarakstu lietojumprogrammas.

Ko jūs domājat ar saistīto sarakstu?

Saistītais saraksts ir lineāra datu struktūra, kas sastāv no elementiem, ko sauc par mezgliem, kur katrs mezgls sastāv no divām daļām: informācijas daļas un saites daļas, ko sauc arī par nākamo rādītāja daļu.

Saistītais saraksts tiek izmantots dažādās lietojumprogrammās, piemēram,

Polinomu manipulācijas attēlojums
Garu pozitīvu veselu skaitļu pievienošana
Retu matricu attēlojums
Garu pozitīvu veselu skaitļu pievienošana
Simbolu tabulas izveide
Adresātu sarakstu
Atmiņas pārvaldība
Saistītā failu piešķiršana
Vairākas precizitātes aritmētika utt

Polinomu manipulācijas

Polinomu manipulācijas ir viens no svarīgākajiem saistīto sarakstu lietojumiem. Polinomi ir svarīga matemātikas daļa, ko lielākā daļa valodu neatbalsta kā datu tipu. Polinoms ir dažādu terminu kopums, katrs no tiem ietver koeficientus un eksponentus. To var attēlot, izmantojot saistīto sarakstu. Šis attēlojums padara polinoma manipulācijas efektīvu.

Atspoguļojot polinomu, izmantojot saistīto sarakstu, katrs polinoma termins apzīmē mezglu saistītajā sarakstā. Lai iegūtu labāku apstrādes efektivitāti, mēs pieņemam, ka katra polinoma termins tiek saglabāts saistītajā sarakstā dilstošo eksponentu secībā. Turklāt nevienam terminam nav vienāds eksponents, un nevienam terminam nav nulles koeficienta un bez koeficientiem. Koeficients iegūst vērtību 1.

Katrs saistītā saraksta mezgls, kas pārstāv polinomu, veido trīs daļas:

Pirmajā daļā ir norādīta termiņa koeficienta vērtība.
Otrajā daļā ir eksponenta vērtība.
Trešā daļa, LINK norāda uz nākamo terminu (nākamo mezglu).

Saistītā saraksta mezgla struktūra, kas attēlo polinomu, ir parādīta zemāk:

Apsveriet polinomu P(x) = 7x²+ 15x³- 2x²+ 9. Šeit 7, 15, -2 un 9 ir koeficienti, un 4,3,2,0 ir polinoma terminu eksponenti. Par šī polinoma attēlošanu, izmantojot saistīto sarakstu, mums ir

Ievērojiet, ka mezglu skaits ir vienāds ar terminu skaitu polinomā. Tātad mums ir 4 mezgli. Turklāt termini tiek saglabāti, lai samazinātu eksponentus saistītajā sarakstā. Šāds polinoma attēlojums, izmantojot saistītos sarakstus, ļoti atvieglo tādas darbības kā atņemšana, saskaitīšana, reizināšana utt.

Polinomu pievienošana:

Lai pievienotu divus polinomus, mēs šķērsojam sarakstu P un Q. Ņemam atbilstošos saraksta P un Q vārdus un salīdzinām to eksponentus. Ja abi eksponenti ir vienādi, koeficienti tiek pievienoti, lai izveidotu jaunu koeficientu. Ja jaunais koeficients ir vienāds ar 0, termins tiek atmests, un, ja tas nav nulle, tas tiek ievietots jaunā saistītā saraksta beigās, kurā ir iegūtais polinoms. Ja viens no eksponentiem ir lielāks par otru, attiecīgais vārds nekavējoties tiek ievietots jaunajā saistītajā sarakstā, un termins ar mazāku eksponentu tiek uzskatīts par salīdzināmu ar nākamo vārdu no cita saraksta. Ja viens saraksts beidzas pirms otra, pārējie garākā saraksta termini tiek ievietoti jaunā saistītā saraksta beigās, kas satur iegūto polinomu.

Apskatīsim piemēru, lai parādītu, kā tiek veikta divu polinomu pievienošana,

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

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

Šie polinomi tiek attēloti, izmantojot saistīto sarakstu eksponentu samazināšanas secībā:

Lai ģenerētu jaunu saistīto sarakstu iegūtajiem polinomiem, kas veidojas, pievienojot dotos polinomus P(x) un Q(x), veicam šādas darbības:

Pārvietojiet divus sarakstus P un Q un pārbaudiet visus mezglus.
Mēs salīdzinām divu polinomu atbilstošo vārdu eksponentus. Polinomu P un Q pirmais loceklis satur attiecīgi eksponentus 4 un 3. Tā kā polinoma P pirmā locekļa eksponents ir lielāks par otru polinomu Q, jaunajā sarakstā tiek ievietots termins ar lielāku eksponentu. Sākotnēji jaunais saraksts izskatās šādi:
Pēc tam mēs salīdzinām saraksta P nākamā vārda eksponentus ar pašreizējā saraksta Q eksponentiem. Tā kā abi eksponenti ir vienādi, to koeficienti tiek pievienoti un pievienoti jaunajam sarakstam šādi:
Pēc tam mēs pārejam uz nākamo P un Q sarakstu termiņu un salīdzinām to eksponentus. Tā kā abu šo terminu eksponenti ir vienādi un pēc to koeficientu pievienošanas mēs iegūstam 0, tāpēc termins tiek izmests un pēc tam jaunajam sarakstam netiek pievienots neviens mezgls,
Pārejot uz nākamo divu sarakstu P un Q vārdu, mēs atklājam, ka attiecīgajiem terminiem ir vienādi eksponenti, kas vienādi ar 0. Mēs pievienojam to koeficientus un pievienojam tos jaunajam iegūtā polinoma sarakstam, kā parādīts tālāk:

Piemērs:

C++ programma divu polinomu pievienošanai

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

Paskaidrojums:

Iepriekš minētajā piemērā mēs esam izveidojuši divu polinoma summas piemēru, izmantojot saistīto sarakstu.

Izvade:

Zemāk ir šī piemēra izvade.

Vairāku mainīgo polinoms

Mēs varam attēlot polinomu ar vairāk nekā vienu mainīgo, t.i., tas var būt divi vai trīs mainīgie. Tālāk ir parādīta mezgla struktūra, kas piemērota polinoma attēlošanai ar trim mainīgajiem X, Y, Z, izmantojot atsevišķi saistītu sarakstu.

Apsveriet polinomu P(x, y, z) = 10x²un²z + 17 x²y z²- 5 xy²z+ 21 g⁴Ar²+ 7. Lai attēlotu šo polinomu, izmantojot saistīto sarakstu, ir:

Termini šādā polinomā ir sakārtoti atbilstoši x dilstošajai pakāpei. Tie, kuriem x ir vienāda pakāpe, tiek sakārtoti atbilstoši y pakāpei, kas samazinās. Tie, kuriem ir vienāda pakāpe x un y, tiek sakārtoti atbilstoši z pakāpes samazinājumam.

Piemērs

Vienkārša C++ programma divu polinomu reizināšanai

 #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