القائمة المرتبطة الدائرية: المزايا والعيوب

ما هي القائمة المرتبطة الدائرية؟

القائمة المرتبطة الدائرية هي سلسلة من العقد مرتبة بحيث يمكن إعادة كل عقدةtracكل "عقدة" هي عنصر مرجعي ذاتي مع مؤشرات إلى عقدة واحدة أو عقدتين في جوارها المباشر.

فيما يلي رسم لقائمة مرتبطة دائرية تحتوي على 3 عقد.

هنا، يمكنك أن ترى أن كل عقدة هي إعادةtracقابلة للتكرار. المثال الموضح أعلاه هو قائمة دائرية مرتبطة بشكل فردي.

ملاحظة: أبسط قائمة مرتبطة دائرية هي عقدة واحدة يكون مؤشرها التالي tracيعود إلى حالته الأصلية، كما هو موضح أدناه.

خفيف Operations in circularlinked Lists

العمليات الأساسية الثلاث على قائمة مرتبطة دائرية هي:

1. إدخال
2. الحذف و
3. اجتياز

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

يشرح القسم التالي كيفية عمل الإدراج ونوعي الإدراج الممكنين في قائمة مرتبطة أحادية دائرية.

إدخال Operaالإنتاج

تبدأ بإنشاء عقدة واحدة يشير مؤشرها التالي إلى نفسها، كما هو موضح أدناه. بدون هذه العقدة الأولية، يصبح الإدخال الأول هو العقدة الأولى في القائمة.

وبعد ذلك هناك احتمالان:

• الإدراج في الموضع الحالي للقائمة المرتبطة الدائرية. وهذا يُعادل الإدراج في بداية أو نهاية قائمة مرتبطة أحادية عادية - في القائمة المرتبطة الدائرية، تكون البداية والنهاية هي نفس النقطة.
• الإدراج بعد عقدة مفهرسة. يجب تحديد العقدة برقم فهرس يتوافق مع قيمة العنصر الخاص بها.

لإدراج عنصر في بداية أو نهاية القائمة الدائرية المرتبطة - أي في الموضع الذي تمت فيه إضافة أول عقدة على الإطلاق - اتبع الخطوات التالية:

• سيتعين عليك قطع الارتباط الذاتي الحالي بالعقدة الموجودة
• سيتم ربط المؤشر التالي للعقدة الجديدة بالعقدة الحالية.
• سيشير المؤشر التالي للعقدة الأخيرة إلى العقدة المدرجة.

ملاحظة: يمكن إعادة تعيين المؤشر الذي يحدد بداية أو نهاية الدائرة إلى أي عقدة. سيظل مسار الدائرة يعود إلى نفس العقدة، كما سيتم توضيحه لاحقًا في هذه المقالة.

الخطوات في (أ) i-iii مبينة أدناه:

(العقدة الموجودة)

الخطوة 1) قطع الارتباط الموجود

الخطوة 2) إنشاء رابط أمامي (من عقدة جديدة إلى عقدة موجودة)

الخطوة 3) قم بإنشاء رابط حلقة للعقدة الأولى

بعد ذلك، ستحاول الإدراج بعد العقدة.

على سبيل المثال، قم بإدراج "VALUE2" بعد العقدة التي تحتوي على "VALUE0"، بافتراض أن نقطة البداية هي العقدة التي تحتوي على "VALUE0".

• قم بفصل الرابط بين العقدة الأولى والثانية، وضع العقدة التي تحتوي على "VALUE2" بينهما.
• يشير المؤشر التالي للعقدة الأولى إلى العقدة الجديدة، ويشير المؤشر التالي للعقدة الجديدة إلى ما كان يُعرف سابقًا بالعقدة الثانية.
• باقي الترتيب يبقى دون تغيير. جميع العقد مُعاد ترتيبهاtracقادرون على أنفسهم.

ملاحظة: نظرًا لأن الترتيب دوري، فإن إجراء إدراج عقدة هو نفسه بغض النظر عن الموضع الذي تختاره. ويتصرف المؤشر الذي يُغلق الحلقة مثل أي مؤشر آخر في القائمة.

وهذا موضح أدناه:

(لنفترض أن هناك عقدتين فقط. هذه حالة تافهة)

الخطوة 1) قم بإزالة الرابط الداخلي بين العقد المتصلة

الخطوة 2) قم بتوصيل العقدة الموجودة على الجانب الأيسر بالعقدة الجديدة

الخطوة 3) قم بتوصيل العقدة الجديدة بالعقدة الموجودة على الجانب الأيمن.

شطب Operaالإنتاج

لنفترض وجود قائمة مرتبطة دائرية مكونة من 3 عقد. حالتا الحذف هما:

• حذف العنصر الحالي
• الحذف بعد العنصر.

الحذف في البداية/النهاية:

1. الانتقال إلى العقدة الأولى من العقدة الأخيرة.
2. لا يتطلب الحذف من النهاية سوى خطوة اجتياز واحدة، من العقدة الأخيرة إلى العقدة الأولى.
3. احذف الرابط بين العقدة الأخيرة والعقدة الأولى.
4. ربط العقدة الأخيرة بالعنصر التالي للعقدة الأولى.
5. تحرير العقدة الأولى.

(الإعداد الحالي)

الخطوة 1) قم بإزالة الرابط الدائري

الخطوة 2) قم بإزالة الرابط بين العقدة الأولى والتالية، وربط العقدة الأخيرة بالعقدة التي تلي الأولى

الخطوة 3) تحرير / إلغاء تخصيص العقدة الأولى

الحذف بعد العقدة:

1. استمر في التصفح حتى تصل إلى العقدة التالية التي سيتم حذفها.
2. انتقل إلى العقدة التالية، مع وضع المؤشر على العقدة السابقة.
3. قم بتوصيل العقدة السابقة بالعقدة التالية للعقدة الحالية باستخدام المؤشر التالي.
4. حرر العقدة الحالية (المفصولة).

الخطوة 1) لنفترض أننا بحاجة إلى حذف عقدة ذات "VALUE1".

الخطوة 2) قم بإزالة الرابط بين العقدة السابقة والعقدة الحالية، ثم قم بربط العقدة السابقة مباشرة بالعقدة التي يشير إليها المؤشر التالي للعقدة الحالية (العقدة التي تلي VALUE1).

الخطوة 3) تحرير أو إلغاء تخصيص العقدة الحالية.

اجتياز قائمة مرتبطة دائرية

للتنقل عبر قائمة مرتبطة دائرية من المؤشر الأخير، تحقق أولاً مما إذا كان المؤشر الأخير يساوي NULL. إذا لم يكن كذلك، فتحقق مما إذا كانت القائمة تحتوي على عنصر واحد فقط. وإلا، فانتقل عبر القائمة باستخدام مؤشر مؤقت حتى تصل إلى المؤشر الأخير مرة أخرى، كما هو موضح في الرسوم المتحركة أدناه.

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

بعض مزايا القوائم المرتبطة الدائرية هي:

1. لا يوجد شرط لتعيين NULL في التعليمات البرمجية. لا تشير القائمة الدائرية أبدًا إلى مؤشر NULL ما لم يتم إلغاء تخصيصها بالكامل.
2. تُعد القوائم المرتبطة الدائرية مفيدة لعمليات نهاية القائمة لأن البداية والنهاية تتطابقان. Algorithms مثل جدولة التناوب الدوري، يمكنها الانتقال عبر العمليات الموجودة في قائمة الانتظار بسلاسة، دون مواجهة مؤشرات معلقة أو فارغة.
3. تدعم القائمة المرتبطة الدائرية جميع العمليات الاعتيادية للقائمة المرتبطة المفردة. قائمة مرتبطة مزدوجة بل ويمكنها حتى إلغاء الحاجة إلى اجتياز كامل لتحديد موقع عنصر ما - في أسوأ الأحوال، يكون الهدف مقابل مؤشر البداية، لذلك لا يلزم اجتياز أكثر من نصف القائمة.

عيوب القائمة المرتبطة الدائرية

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

1. تُعد القوائم الدائرية أكثر تعقيدًا من قوائم مرتبطة منفردة.
2. Revإن عكس قائمة دائرية أكثر تعقيدًا من عكس قائمة مرتبطة بشكل فردي أو مزدوج.
3. إذا لم يتم التعامل مع إنهاء الحلقة بعناية، فقد يدخل رمز الاجتياز في حلقة لا نهائية.
4. من الصعب العثور على نهاية القائمة وكتابة شروط التحكم في الحلقة بشكل صحيح.
5. يتطلب الإدراج في البداية اجتياز القائمة بأكملها للوصول إلى العقدة الأخيرة (من منظور التنفيذ).

قائمة مرتبطة منفردة كقائمة مرتبطة دائرية

نشجعك على قراءة وتطبيق كود لغة C أدناه. فهو يوضح العمليات الحسابية على المؤشرات المرتبطة بقائمة مرتبطة أحادية دائرية.

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

شرح الكود:

1. أول سطرين من التعليمات البرمجية هما ملفات الرأس المضمنة الضرورية.
2. يُحدد القسم التالي بنية كل عقدة ذاتية الإشارة. تحتوي هذه العقدة على قيمة ومؤشر من نفس نوع البنية.
3. يرتبط كل مثيل من مثيلات البنية بكائنات بنية أخرى من نفس النوع.
4. هناك نماذج أولية مختلفة للوظائف من أجل:
   1. إضافة عنصر إلى قائمة مرتبطة فارغة
   2. الإدراج في وأشار حاليا موضع القائمة المرتبطة الدائرية.
   3. الإدراج بعد معين مفهرس القيمة في القائمة المرتبطة.
   4. إزالة/حذف بعد معين مفهرس القيمة في القائمة المرتبطة.
   5. الإزالة من الموضع المشار إليه حاليًا لقائمة مرتبطة دائرية
5. تقوم الوظيفة الأخيرة بطباعة كل عنصر من خلال اجتياز دائري في أي حالة من القائمة المرتبطة.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

شرح الكود:

1. بالنسبة لرمز addToEmpty، قم بتخصيص عقدة فارغة باستخدام الدالة malloc().
2. ضع البيانات الواردة في العقدة المؤقتة.
3. قم بتعيين العقدة المؤقتة لتكون الأخيرة واضبط مؤشرها التالي على نفسها بحيث تشير العقدة المفردة إلى نفسها.
4. أعد المؤشر الأخير إلى سياق التطبيق الرئيسي ()/.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

شرح الكود

1. إذا كانت القائمة فارغة، فقم بتسليمها إلى addToEmpty() وأعد التحكم.
2. أنشئ عقدة مؤقتة لوضعها بعد العقدة الحالية.
3. قم بتوصيل المؤشرات كما هو موضح في الرسم التخطيطي أعلاه.
4. أعد المؤشر الأخير، الذي يطابق النمط المستخدم في الدالة السابقة.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

شرح الكود:

1. إذا كانت القائمة فارغة، فتجاهل مفتاح البحث، وأضف العنصر الحالي كعقدة وحيدة في القائمة، ثم أعد التحكم.
2. في كل تكرار لحلقة do-while، يحتوي المؤشر السابق على النتيجة التي تم اجتيازها آخر مرة.
3. عندها فقط تحدث خطوة الاجتياز التالية.
4. تنتهي حلقة التكرار "do-while" عند العثور على البيانات المستهدفة أو عند وصول المتغير المؤقت إلى المؤشر الأخير مرة أخرى. يحدد الجزء البرمجي التالي الإجراء المطلوب مع العنصر الذي تم العثور عليه.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

شرح الكود:

1. إذا تم استعراض القائمة بأكملها ولكن لم يتم العثور على العنصر، فاعرض رسالة "العنصر غير موجود" وأعد التحكم إلى المتصل.
2. إذا تم العثور على العقدة المستهدفة، فقم بتخصيص عقدة جديدة للقيمة المراد إدراجها.
3. الرابط قم بربط العقدة السابقة بالعقدة الجديدة، وقم بربط مؤشر العقدة الجديدة التالي بالمتغير المؤقت (متغير الاجتياز).
4. يؤدي هذا إلى وضع العنصر الجديد مباشرةً بعد العقدة المستهدفة في القائمة المرتبطة الدائرية. ثم يعود التحكم إلى المُستدعي.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

شرح الكود

1. لإزالة العقدة الأخيرة (الحالية)، تحقق أولاً مما إذا كانت القائمة فارغة. إذا كانت كذلك، فلا يمكن إزالة أي عنصر.
2. يؤدي المتغير الحراري إلى تقدم وصلة واحدة للأمام.
3. قم بربط المؤشر الأخير بالعقدة التي تلي العقدة الأولى.
4. قم بتحرير المؤشر المؤقت لإلغاء تخصيص العقدة غير المرتبطة.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

شرح الكود

1. كما هو الحال مع دالة الحذف السابقة، تحقق أولاً مما إذا كانت القائمة فارغة. إذا كانت كذلك، فلا يمكن حذف أي عنصر.
2. أنظمة مؤشرات يتم تعيين مواقع محددة لتحديد العنصر المراد حذفه.
3. يتم تحريك المؤشرات واحداً تلو الآخر (المسارات السابقة درجة الحرارة).
4. يستمر التصفح حتى يتم العثور على العنصر المستهدف أو يصل المؤشر التالي إلى العقدة الأخيرة مرة أخرى.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

شرح البرنامج

1. إذا تم استعراض القائمة المرتبطة بأكملها دون العثور على الهدف، فسيتم عرض رسالة "العنصر غير موجود".
2. وإلا، يتم فصل العنصر وتحريره في الخطوتين 3 و 4.
3. يرتبط المؤشر السابق بالعقدة التي يشير إليها المؤشر التالي الخاص بالعقدة المؤقتة (العقدة التي تلي العقدة التي يتم حذفها).
4. ثم يتم تحرير المؤشر المؤقت.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

شرح الكود

1. لا يمكن إجراء عملية التصفح السريع إذا لم يكن هناك أي عقد - يجب على المستخدم أولاً تخصيص أو إدراج عقدة.
2. إذا كانت هناك عقدة واحدة فقط، فلا حاجة إلى اجتيازها - تتم طباعة محتوى العقدة مباشرة ولا يتم تنفيذ حلقة while.
3. إذا كان هناك أكثر من عقدة واحدة، فإن الأمر temp يطبع كل عنصر حتى العنصر الأخير.
4. بمجرد الوصول إلى العنصر الأخير، تنتهي الحلقة وتعيد الدالة التحكم إلى الدالة الرئيسية main().

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

• تنفيذ جدولة دائرية في عمليات النظام وجدولة دائرية في الرسومات عالية السرعة.
• جدولة حلقات الرموز في شبكات الحاسوب.
• تُستخدم في وحدات العرض مثل لوحات المتاجر الرقمية التي تتطلب استعراضًا مستمرًا للبيانات.

الأسئلة الشائعة