TechCodeview

Šiame straipsnyje mes išsamiai suprasime susieto sąrašo programas.

Ką turite omenyje sakydami susietų sąrašą?

Susietas sąrašas yra linijinė duomenų struktūra, susidedanti iš elementų, vadinamų mazgais, kur kiekvienas mazgas susideda iš dviejų dalių: informacijos dalies ir nuorodos dalies, dar vadinamos kita rodyklės dalimi.

Susietas sąrašas naudojamas įvairiose programose, pvz

• Polinominis manipuliavimo vaizdavimas
• Ilgų teigiamų sveikųjų skaičių pridėjimas
• Retų matricų vaizdavimas
• Ilgų teigiamų sveikųjų skaičių pridėjimas
• Simbolių lentelės kūrimas
• Pašto adresų sąrašas
• Atminties valdymas
• Susietas failų paskirstymas
• Daugkartinė tiksli aritmetika ir kt

Polinominis manipuliavimas

Polinominės manipuliacijos yra viena iš svarbiausių susietų sąrašų taikymo būdų. Polinomai yra svarbi matematikos dalis, kuri daugeliu kalbų nėra palaikoma kaip duomenų tipas. Polinomas yra skirtingų terminų rinkinys, kurį sudaro koeficientai ir rodikliai. Jį galima pavaizduoti naudojant susietą sąrašą. Dėl šio vaizdavimo polinominis manipuliavimas yra efektyvus.

Atstovaujant daugianariui naudojant susietąjį sąrašą, kiekvienas daugianario terminas reiškia mazgą susietame sąraše. Kad apdorojimas būtų efektyvesnis, darome prielaidą, kad kiekvieno daugianario terminas yra saugomas susietame sąraše mažėjančių eksponentų tvarka. Be to, nėra dviejų dėmenų, kurių rodiklis būtų vienodas, ir joks terminas neturi nulinio koeficiento ir be koeficientų. Koeficientas įgyja 1 reikšmę.

teksto dydžio lateksas

Kiekvienas susieto sąrašo mazgas, vaizduojantis polinomą, sudaro tris dalis:

• Pirmoje dalyje pateikiama termino koeficiento reikšmė.
• Antroje dalyje yra eksponento reikšmė.
• Trečioji dalis LINK nurodo kitą terminą (kitą mazgą).

Žemiau parodyta susieto sąrašo mazgo, vaizduojančio polinomą, struktūra:

Apsvarstykite daugianarį P(x) = 7x²+ 15x³- 2x²+ 9. Čia 7, 15, -2 ir 9 yra koeficientai, o 4,3,2,0 yra daugianario terminų eksponentai. Pateikdami šį daugianarį naudodami susietą sąrašą, turime

Pastebėkite, kad mazgų skaičius yra lygus daugianario narių skaičiui. Taigi turime 4 mazgus. Be to, terminai išsaugomi, kad susietame sąraše būtų sumažinti eksponentai. Toks daugianario vaizdavimas naudojant susietus sąrašus labai palengvina tokias operacijas kaip atimtis, sudėtis, daugyba ir kt.

Polinomų pridėjimas:

Norėdami pridėti du daugianarius, pereiname sąrašą P ir Q. Paimame atitinkamus sąrašo P ir Q terminus ir palyginame jų eksponentus. Jei du rodikliai yra lygūs, koeficientai pridedami, kad būtų sukurtas naujas koeficientas. Jei naujasis koeficientas yra lygus 0, tada terminas išbraukiamas, o jei jis nėra nulis, jis įterpiamas į naujo susieto sąrašo, kuriame yra gautas daugianomas, pabaigoje. Jei vienas iš rodiklių yra didesnis už kitą, atitinkamas terminas nedelsiant įtraukiamas į naują susietą sąrašą, o terminas su mažesniu rodikliu laikomas lyginamas su kitu nariu iš kito sąrašo. Jei vienas sąrašas baigiasi prieš kitą, likusios ilgesnio sąrašo sąlygos įterpiamos į naujo susieto sąrašo, kuriame yra gautas daugianomas, pabaigoje.

Panagrinėkime pavyzdį, kaip pavyzdį, kaip sudedamas du polinomai,

kas yra build-essential ubuntu

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

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

Šie daugianariai vaizduojami naudojant susietą sąrašą mažėjančių eksponentų tvarka taip:

Norėdami sugeneruoti naują susietą gautų daugianarių sąrašą, kuris sudaromas pridedant duotus daugianorius P(x) ir Q(x), atliekame šiuos veiksmus:

1. Pereikite du sąrašus P ir Q ir patikrinkite visus mazgus.
2. Lyginame dviejų daugianario atitinkamų dėmenų rodiklius. Pirmasis daugianario P ir Q narys turi atitinkamai 4 ir 3 eksponentus. Kadangi daugianario P pirmojo nario rodiklis yra didesnis nei kito daugianario Q, į naująjį sąrašą įtraukiamas didesnis rodiklis. Iš pradžių naujas sąrašas atrodo taip, kaip parodyta žemiau:
   
3. Tada palyginame kito sąrašo nario P rodiklį su dabartinio sąrašo Q nario rodikliais. Kadangi abu rodikliai yra lygūs, todėl jų koeficientai pridedami ir pridedami prie naujo sąrašo taip:
   
4. Tada pereiname prie kito P ir Q sąrašų nario ir palyginame jų eksponentus. Kadangi abiejų šių dėmenų eksponentai yra lygūs ir pridėjus jų koeficientus gauname 0, todėl terminas išmetamas, o po to prie naujo sąrašo nepridedamas joks mazgas,
   
5. Pereinant prie kito dviejų sąrašų P ir Q nario, nustatome, kad atitinkamų terminų rodikliai yra tokie patys, lygūs 0. Pridedame jų koeficientus ir pridedame juos prie naujo gauto daugianario sąrašo, kaip parodyta toliau:
   

Pavyzdys:

C++ programa, skirta pridėti du polinomus

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

Paaiškinimas:

string.valueof java

Aukščiau pateiktame pavyzdyje sukūrėme dviejų polinomų sumos pavyzdį naudodami susietą sąrašą.

Išvestis:

Žemiau yra šio pavyzdžio išvestis.

Kelių kintamųjų polinomas

Galime pavaizduoti daugianarį su daugiau nei vienu kintamuoju, ty jis gali būti dviejų arba trijų kintamųjų. Žemiau pateikiama mazgo struktūra, tinkanti daugianariui su trimis kintamaisiais X, Y, Z, naudojant atskirai susietą sąrašą, atvaizduoti.

Apsvarstykite daugianarį P(x, y, z) = 10x²ir²z + 17 x²y z²- 5 xy²z+ 21m⁴Su²+ 7. Pateikiant šį daugianarį naudojant susietą sąrašą:

Tokio daugianario terminai išdėstomi atitinkamai mažėjančiu laipsniu x. Tie, kurių x laipsnis yra toks pat, suskirstomi pagal mažėjantį y laipsnį. Tie, kurių x ir y laipsniai yra vienodi, išdėstomi pagal mažėjančius z laipsnius.

iš naujo paleiskite mysql ubuntu

Pavyzdys

Paprasta C++ programa, skirta padauginti du polinomus

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