تطبيق القائمة المرتبطة

في هذه المقالة، سوف نفهم تطبيقات القائمة المرتبطة بالتفصيل.

ماذا تقصد بالقائمة المرتبطة؟

القائمة المرتبطة هي بنية بيانات خطية تتكون من عناصر تسمى العقد حيث تتكون كل عقدة من جزأين: جزء المعلومات وجزء الارتباط، ويسمى أيضًا جزء المؤشر التالي.

يتم استخدام القائمة المرتبطة في مجموعة واسعة من التطبيقات مثل

تمثيل التلاعب متعدد الحدود
إضافة الأعداد الصحيحة الإيجابية الطويلة
تمثيل المصفوفات المتفرقة
إضافة الأعداد الصحيحة الإيجابية الطويلة
إنشاء جدول الرموز
القائمة البريدية
إدارة الذاكرة
التخصيص المرتبط للملفات
حسابات متعددة الدقة وما إلى ذلك

التلاعب متعدد الحدود

تعد معالجة كثيرات الحدود أحد أهم تطبيقات القوائم المرتبطة. تعد كثيرات الحدود جزءًا مهمًا من الرياضيات ولا يتم دعمها بطبيعتها كنوع بيانات في معظم اللغات. كثيرة الحدود عبارة عن مجموعة من الحدود المختلفة، يشتمل كل منها على معاملات وأسس. يمكن تمثيله باستخدام قائمة مرتبطة. هذا التمثيل يجعل معالجة كثيرات الحدود فعالة.

أثناء تمثيل كثير الحدود باستخدام قائمة مرتبطة، يمثل كل مصطلح متعدد الحدود عقدة في القائمة المرتبطة. للحصول على كفاءة أفضل في المعالجة، نفترض أن حد كل كثيرة الحدود يتم تخزينه ضمن القائمة المرتبطة بترتيب الأسس المتناقصة. كما أنه لا يوجد حدان لهما نفس الأس، ولا يوجد حد معامله صفر وبدون معاملات. يأخذ المعامل قيمة 1.

تشكل كل عقدة من القائمة المرتبطة التي تمثل كثيرات الحدود ثلاثة أجزاء:

يحتوي الجزء الأول على قيمة معامل المصطلح.
الجزء الثاني يحتوي على قيمة الأس.
الجزء الثالث، LINK يشير إلى المصطلح التالي (العقدة التالية).

يظهر أدناه هيكل عقدة القائمة المرتبطة التي تمثل كثير الحدود:

فكر في كثيرة الحدود P(x) = 7x²+ 15x³- 2 ×²+ 9. هنا 7، 15، -2، و9 هي المعاملات، و4,3,2,0 هي أسس الحدود في كثيرة الحدود. عند تمثيل كثير الحدود هذا باستخدام قائمة مرتبطة، لدينا

لاحظ أن عدد العقد يساوي عدد المصطلحات في كثيرة الحدود. إذن لدينا 4 عقد. علاوة على ذلك، يتم تخزين المصطلحات لتقليل الأسس في القائمة المرتبطة. مثل هذا التمثيل لكثيرات الحدود باستخدام القوائم المرتبطة يجعل العمليات مثل الطرح والجمع والضرب وما إلى ذلك، على كثيرات الحدود سهلة للغاية.

إضافة كثيرات الحدود:

لإضافة كثيرتي الحدود، نجتاز القائمة P وQ. ونأخذ المصطلحات المقابلة من القائمة P وQ ونقارن أسسهما. إذا كان الأسان متساويين، تتم إضافة المعاملات لإنشاء معامل جديد. إذا كان المعامل الجديد يساوي 0، فسيتم إسقاط المصطلح، وإذا لم يكن صفرًا، فسيتم إدراجه في نهاية القائمة المرتبطة الجديدة التي تحتوي على كثير الحدود الناتج. إذا كان أحد الأسس أكبر من الآخر، فسيتم وضع المصطلح المقابل على الفور في القائمة المرتبطة الجديدة، ويتم مقارنة المصطلح ذي الأس الأصغر مع المصطلح التالي من القائمة الأخرى. إذا انتهت إحدى القائمة قبل الأخرى، يتم إدراج بقية مصطلحات القائمة الأطول في نهاية القائمة المرتبطة الجديدة التي تحتوي على كثير الحدود الناتج.

دعونا نفكر في مثال لتوضيح كيفية إجراء عملية جمع كثيرتي الحدود،

ف(س) = 3س⁴+ 2x³- 4 ×²+ 7

س (س) = 5س³+ 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²و²ض + 17 س²ذ ض²- 5 س ص²ض + 21 ذ⁴مع²+ 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;>