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

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

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

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

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

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

Basic Operaفي القوائم المرتبطة الدائرية

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

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

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

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

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

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

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

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

للإدراج في بداية/نهاية القائمة المرتبطة الدائرية، أي في الموضع الذي تمت فيه إضافة العقدة الأولى على الإطلاق،

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

شطب Operaالإنتاج

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#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. بالنسبة لرمز addEmpty، قم بتخصيص عقدة فارغة باستخدام الدالة 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. إذا لم يكن هناك عنصر لإدراجه، فيجب عليك التأكد من إضافته إلى قائمة فارغة وإرجاع التحكم.
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. في حالة العثور على البيانات، أو عودة درجة الحرارة إلى المؤشر الأخير، تنتهي فترة العمل. يقرر القسم التالي من التعليمات البرمجية ما يجب فعله بالعنصر.

...
    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. Pointers يتم تعيين مواقع محددة لتحديد العنصر المراد حذفه.
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. إذا كانت هناك عقدة واحدة فقط، فليست هناك حاجة للاجتياز، ويمكن طباعة محتوى العقدة، ولا يتم تنفيذ الحلقة أثناء ذلك.
3. إذا كان هناك أكثر من عقدة واحدة، فسيقوم المؤقت بطباعة كل العنصر حتى العنصر الأخير.
4. في اللحظة التي يتم فيها الوصول إلى العنصر الأخير، تنتهي الحلقة، وترجع الوظيفة الاتصال بالوظيفة الرئيسية.

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

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