יישום של רשימה מקושרת

במאמר זה נבין בפירוט את יישומי הרשימה המקושרת.

למה אתה מתכוון ברשימה מקושרת?

רשימה מקושרת היא מבנה נתונים ליניארי המורכב מאלמנטים הנקראים צמתים כאשר כל צומת מורכב משני חלקים: חלק מידע וחלק קישור, הנקרא גם חלק המצביע הבא.

רשימה מקושרת משמשת במגוון רחב של יישומים כגון

ייצוג מניפולציה פולינומית
הוספת מספרים שלמים חיוביים ארוכים
ייצוג מטריצות דלילות
הוספת מספרים שלמים חיוביים ארוכים
יצירת טבלת סמלים
רשימת תפוצה
ניהול זיכרון
הקצאה מקושרת של קבצים
חשבון דיוק מרובה וכו'

מניפולציה פולינומית

מניפולציות פולינומיות הן אחד היישומים החשובים ביותר של רשימות מקושרות. פולינומים הם חלק חשוב במתמטיקה שאינם נתמכים מטבעם כסוג נתונים על ידי רוב השפות. פולינום הוא אוסף של מונחים שונים, שכל אחד מהם כולל מקדמים ומעריכים. זה יכול להיות מיוצג באמצעות רשימה מקושרת. ייצוג זה הופך את המניפולציה של פולינום ליעילה.

בעוד שמייצג פולינום באמצעות רשימה מקושרת, כל מונח פולינום מייצג צומת ברשימה המקושרת. כדי להשיג יעילות טובה יותר בעיבוד, אנו מניחים שהמונח של כל פולינום מאוחסן בתוך הרשימה המקושרת בסדר המעריכים יורד. כמו כן, אין שני איברים בעלי אותו מעריך, ולאף איבר אין מקדם אפס וללא מקדמים. המקדם מקבל ערך של 1.

טבלת אמת האפעה המלאה

כל צומת ברשימה מקושרת המייצגת פולינום מורכב משלושה חלקים:

החלק הראשון מכיל את הערך של מקדם המונח.
החלק השני מכיל את הערך של המעריך.
החלק השלישי, LINK מצביע על המונח הבא (הצומת הבא).

המבנה של צומת של רשימה מקושרת המייצגת פולינום מוצג להלן:

שקול פולינום P(x) = 7x²+ 15x³- 2 x²+ 9. כאן 7, 15, -2 ו-9 הם המקדמים, ו-4,3,2,0 הם המעריכים של האיברים בפולינום. על ייצוג הפולינום הזה באמצעות רשימה מקושרת, יש לנו

שימו לב שמספר הצמתים שווה למספר האיברים בפולינום. אז יש לנו 4 צמתים. יתר על כן, המונחים מאוחסנים כדי להקטין מעריכים ברשימה המקושרת. ייצוג כזה של פולינום באמצעות רשימות מקושרות מקל מאוד על פעולות כמו חיסור, חיבור, כפל וכו'.

הוספת פולינומים:

כדי להוסיף שני פולינומים, אנו חוצים את הרשימה P ו-Q. אנו לוקחים מונחים מתאימים של הרשימה P ו-Q ומשווים את המעריכים שלהם. אם שני המעריכים שווים, המקדמים מתווספים ליצירת מקדם חדש. אם המקדם החדש שווה ל-0, המונח נשמט, ואם הוא אינו אפס, הוא מוכנס בסוף הרשימה המקושרת החדשה המכילה את הפולינום שנוצר. אם אחד המעריכים גדול מהשני, המונח המתאים מוכנס מיד לרשימה המקושרת החדשה, והמונח עם המעריך הקטן יותר מוחזק להשוואה למונח הבא מהרשימה השנייה. אם רשימה אחת מסתיימת לפני השנייה, שאר המונחים של הרשימה הארוכה יותר יוכנסו בסוף הרשימה המקושרת החדשה המכילה את הפולינום שנוצר.

הבה נבחן דוגמה לדוגמא כדי להראות כיצד מתבצעת חיבור של שני פולינומים,

ניצב משנה למשטרה

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

Q (x) = 5x³+ 4 x²- 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;>

הֶסבֵּר:

דפוסי עיצוב java

בדוגמה לעיל, יצרנו דוגמה של סכום של שני פולינומים באמצעות רשימה מקושרת.

תְפוּקָה:

להלן הפלט של דוגמה זו.

פולינום של משתנים מרובים

אנו יכולים לייצג פולינום עם יותר ממשתנה אחד, כלומר, הוא יכול להיות שניים או שלושה משתנים. להלן מבנה צומת המתאים לייצוג פולינום עם שלושה משתנים X, Y, Z באמצעות רשימה מקושרת בודדת.

שקול פולינום P(x, y, z) = 10x²ו²z + 17 x²y z²- 5 xy²z+ 21y⁴עם²+ 7. על ייצוג הפולינום הזה באמצעות רשימה מקושרת הם:

מונחים בפולינום כזה מסודרים בהתאם לדרגה היורדת ב-x. אלה עם אותה תואר ב-x מסודרים לפי דרגה יורדת ב-y. אלה עם אותה תואר ב-x וב-y מסודרים לפי מעלות יורדות ב-z.

התייחסות לסוגי נתונים ב-java

דוגמא

תוכנית 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;>