القائمة المرتبطة الدائرية (Circular Linked List)

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

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

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

يوجد أدناه وصف لقائمة مرتبطة دائرية تحتوي على 3 عقد.

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

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

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

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

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

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

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

عملية الإدراج

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

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

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

الإدراج بعد عقدة مفهرسة. يجب تحديد العقدة برقم فهرس يتوافق مع قيمة عنصرها.

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

سيتعين عليك قطع الارتباط الذاتي الموجود بالعقدة الحالية؛

سوف يرتبط المؤشر التالي للعقدة الجديدة بالعقدة الحالية.

سيشير المؤشر التالي للعقدة الأخيرة إلى العقدة المدرجة.

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

الخطوات في (A) من الأول إلى الثالث موضحة أدناه:

الخطوة 1) كسر الرابط الحالي.

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

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

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

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

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

على سبيل المثال دعنا ندخل “VALUE2” بعد العقدة بـ “VALUE0”. لنفترض أن نقطة البداية هي العقدة ذات “VALUE0”.

سيتعين عليك كسر الخط الفاصل بين العقدة الأولى والثانية ووضع العقدة مع “VALUE2” بينهما.

يجب أن يرتبط المؤشر التالي للعقدة الأولى بهذه العقدة ويجب أن يرتبط المؤشر التالي للعقدة بالعقدة الثانية السابقة.

بقي باقي الترتيب دون تغيير. يمكن استرجاع جميع العقد لأنفسهم.

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

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

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

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

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

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

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

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

عملية الحذف

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

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

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

الانتقال إلى العقدة الأولى من العقدة الأخيرة.

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

احذف الرابط بين العقدة الأخيرة والعقدة التالية.

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

حرر العقدة الأولى.

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

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

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

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

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

اجتياز حتى العقدة التالية هي العقدة المراد حذفها.

انتقل إلى العقدة التالية مع وضع مؤشر على العقدة السابقة.

قم بتوصيل العقدة السابقة بالعقدة بعد العقدة الحالية باستخدام مؤشرها التالي.

حرر العقدة الحالية (المفكوكة).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#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

أول سطرين من التعليمات البرمجية هي ملفات الرأس المضمنة الضرورية.

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

ترتبط كل بنية بشكل متكرر بكائنات هيكلية من نفس النوع.

هناك نماذج أولية مختلفة للوظائف من أجل:

إضافة عنصر إلى قائمة مرتبطة فارغة

الإدراج في الموضع المحدد حاليًا لقائمة مرتبطة دائرية.

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

الإزالة / الحذف بعد قيمة مفهرسة معينة في القائمة المرتبطة.

الإزالة في الموضع المحدد حاليًا لقائمة مرتبطة دائرية

تقوم الوظيفة الأخيرة بطباعة كل عنصر من خلال اجتياز دائري في أي حالة من القائمة المرتبطة.

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)

شرح الكود 2

بالنسبة للكود addEmpty قم بتخصيص عقدة فارغة باستخدام وظيفة malloc.

بالنسبة لهذه العقدة ضع البيانات في المتغير المؤقت.

قم بتعيين وربط المتغير الوحيد بالمتغير المؤقت

أعد العنصر الأخير إلى سياق التطبيق / main.

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

شرح الكود 3

إذا لم يكن هناك عنصر لإدراجه فعليك التأكد من إضافته إلى قائمة فارغة وإعادة التحكم.

قم بإنشاء عنصر مؤقت لوضعه بعد العنصر الحالي.

اربط المؤشرات كما هو موضح.

أعد المؤشر الأخير كما في الوظيفة السابقة.

...
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");
...

شرح الكود 4

إذا لم يكن هناك عنصر في القائمة فتجاهل البيانات وأضف العنصر الحالي باعتباره العنصر الأخير في القائمة ویعید Control

لكل تكرار في حلقة do-while تأكد من وجود مؤشر سابق يحمل آخر نتيجة تم اجتيازها.

عندها فقط يمكن أن يحدث الاجتياز التالي.

إذا تم العثور على البيانات أو عادت temp إلى المؤشر الأخير فإن 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)
...

شرح الكود 5

إذا تم اجتياز القائمة بأكملها ومع ذلك لم يتم العثور على العنصر اعرض رسالة “item not found” ثم أعد التحكم إلى المتصل.

إذا تم العثور على عقدة و / أو لم تكن العقدة هي آخر عقدة بعد فقم بإنشاء عقدة جديدة.

اربط العقدة السابقة بالعقدة الجديدة. ربط العقدة الحالية مع temp (متغير الاجتياز).

هذا يضمن وضع العنصر بعد عقدة معينة في القائمة المرتبطة الدائرية.

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)

شرح الكود 6

لإزالة العقدة الأخيرة (الحالية) فقط تحقق مما إذا كانت هذه القائمة فارغة. إذا كان الأمر كذلك فلا يمكن إزالة أي عنصر.

متغير temp يجتاز رابطًا واحدًا فقط للأمام.

اربط المؤشر الأخير بالمؤشر بعد الأول.

حرر مؤشر درجة الحرارة. يقوم بإلغاء تخصيص المؤشر الأخير غير المرتبط.

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");
...

شرح الكود 7

كما هو الحال مع وظيفة الإزالة السابقة تحقق من عدم وجود عنصر. إذا كان هذا صحيحًا فلا يمكن إزالة أي عنصر.

يتم تخصيص مواضع محددة للمؤشرات لتحديد موقع العنصر المراد حذفه.

المؤشرات متقدمة واحدة خلف الأخرى. (سابق خلف درجة الحرارة)

تستمر العملية حتى يتم العثور على عنصر أو يعود العنصر التالي إلى المؤشر الأخير.

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;	

شرح الكود 8

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

خلاف ذلك يتم فك ارتباط العنصر وتحريره في الخطوتين 3 و 4.

المؤشر السابق مرتبط بالعنوان المشار إليه على أنه “next” بواسطة العنصر المراد حذفه (مؤقت).

لذلك يتم إلغاء تخصيص المؤشر المؤقت وتحريره.

...
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;
    }
}

شرح الكود 9

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

إذا كانت هناك عقدة واحدة فقط فلا داعي للعبور ويمكن طباعة محتوى العقدة ولا يتم تنفيذ حلقة while.

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

لحظة الوصول إلى العنصر الأخير وتنتهي الحلقة وترجع الدالة استدعاء الوظيفة الرئيسية.

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

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

المصدر

منشور ذات صلة
قواعد البيانات 7 Minutes

أساسيات قواعد البيانات

علي شفیعي

تنشئ معالجات قواعد البيانات (Database) قاعدة بيانات بطريقة تتيح لمجموعة واحدة فقط من البرامج الوصول إلى البيانات لجميع المستخدمين.

خلايا Excel 7 Minutes

أساسيات خلايا Excel

علي شفیعي

تتكون كل ورقة عمل Excel من آلاف المستطيلات ، والتي تسمى الخلايا. الخلية هي تقاطع صف وعمود. بمعنى آخر ، هو المكان الذي يلتقي فيه الصف والعمود.

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

السلة