كشف حلقة في قائمة مرتبطة في C ++

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

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

في C ++ ، توجد طرق عديدة للعثور على الحلقات في قائمة مرتبطة:

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

نهج دورة فلويد : خوارزمية 'السلحفاة والأرنب' ، المعروفة باسم خوارزمية فلويد لإيجاد الدورة: تستخدم هذه التقنية مؤشرين ، أحدهما يتحرك ببطء أكثر من الآخر والآخر يتحرك بسرعة أكبر. سيتجاوز المؤشر الأسرع في النهاية المؤشر الأبطأ إذا كانت هناك حلقة في القائمة المرتبطة ، تكشف عن وجود الحلقة.

طريقة تكرارية : تمر هذه الطريقة عبر القائمة المرتبطة عن طريق استدعاء نفسها مرارًا وتكرارًا. تحتوي القائمة المرتبطة على حلقة إذا تمت زيارة العقدة الحالية مسبقًا.

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

دعونا نشرح كل نهج بالتفصيل لفهم المفهوم.

النهج 1: نهج HashSet

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

سيكون من السهل جدًا تنفيذ هذه الاستراتيجية.

أثناء اجتياز القائمة المرتبطة ، سوف نستخدم unordered_hashmap ونستمر في إضافة العقد إليها.

الآن ، بمجرد أن نواجه عقدة معروضة بالفعل في الخريطة ، سنعرف أننا وصلنا إلى بداية الحلقة.

• • بالإضافة إلى ذلك ، احتفظنا بمؤشرين في كل خطوة ، عقدة الرأس مشيرا إلى العقدة الحالية و العقدة الأخيرة للإشارة إلى العقدة السابقة للعقدة الحالية ، أثناء التكرار.
  • كخاصتنا عقدة الرأس يشير الآن إلى عقدة البداية للحلقة و العقدة الأخيرة كان يشير إلى العقدة التي يشير إليها الرأس (أي أنه يشير إلى العقدة الأخيرة من الحلقة) ، لدينا عقدة الرأس يشير حاليًا إلى عقدة البداية للحلقة.
  • سيتم كسر الحلقة عن طريق ضبط l astNode-> التالي == NULL .

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

متوسط ​​الوقت والتعقيد المكاني لطريقة التجزئة هو O (n). يجب أن يدرك القارئ دائمًا أن تنفيذ Hashing DataStructure المضمنة في لغة البرمجة سيحدد مدى تعقيد الوقت الإجمالي في حالة حدوث تضارب في التجزئة.

تنفيذ برنامج C ++ للطريقة المذكورة أعلاه (HashSet):

انتاج:

يتم توفير شرح التعليمات البرمجية خطوة بخطوة أدناه:

1. 1. يتم تضمين ملف bits / stdc ++. h> header ، الذي يحتوي على جميع مكتبات C ++ الشائعة ، في الكود.
   2. يتم إنشاء بنية تسمى 'العقدة' ، وتتكون من عضوين: مرجع إلى العقدة التالية في القائمة وعدد صحيح يسمى 'القيمة'.
   3. مع وجود قيمة عدد صحيح كمدخل له وتعيين المؤشر 'التالي' على NULL ، تنشئ الوظيفة 'newNode' عقدة جديدة بهذه القيمة.
   4. الوظيفة الوظيفة تم تعريفه ، والذي يأخذ مؤشرًا إلى العقدة الرئيسية للقائمة المرتبطة كمدخل.
   5. داخل الوظيفة 'دالة ، يتم إنشاء خريطة غير مرتبة باسم' hash_map '، والتي تُستخدم لتنفيذ بنية بيانات خريطة التجزئة.
   6. تتم تهيئة مؤشر آخر عقدة من القائمة إلى NULL.
   7. تُستخدم حلقة while لتجاوز القائمة المرتبطة ، والتي تبدأ من العقدة الرئيسية وتستمر حتى تصبح العقدة الرئيسية NULL.
   8. يتم تحديث مؤشر lastNode إلى العقدة الحالية داخل حلقة while إذا لم تكن العقدة الحالية (headNode) موجودة بالفعل في خريطة التجزئة.
   9. إذا تم العثور على العقدة الحالية في الخريطة ، فهذا يعني أن الحلقة موجودة في القائمة المرتبطة. لإزالة الحلقة ، يكون المؤشر التالي لملف العقدة الأخيرة تم تعيينه على باطل والحلقة أثناء مكسورة.
   10. تُستخدم عقدة رأس القائمة المرتبطة كمدخل لوظيفة تسمى 'عرض' ، والتي تُخرج قيمة كل عقدة في القائمة من البداية إلى النهاية.
   11. في ال رئيسي وظيفة ، وخلق حلقة.
   12. يتم استدعاء الوظيفة 'functionHashMap' بمؤشر headNode كمدخل ، والذي يزيل الحلقة من القائمة.
   13. يتم عرض القائمة المعدلة باستخدام وظيفة 'العرض'.

النهج 2: دورة فلويد

توفر خوارزمية Floyd للكشف عن الدورة ، والتي تُعرف غالبًا باسم خوارزمية السلحفاة والأرنب ، الأساس لهذه الطريقة لتحديد الدورات في قائمة مرتبطة. المؤشر 'البطيء' والمؤشر 'السريع' ، اللذان يجتازان القائمة بسرعات مختلفة ، هما المؤشران المستخدمان في هذه التقنية. يتقدم المؤشر السريع بخطوتين بينما يتقدم المؤشر البطيء خطوة واحدة كل تكرار. توجد دورة في القائمة المرتبطة إذا واجهت النقطتان وجهًا لوجه.

1. باستخدام العقدة الرئيسية للقائمة المرتبطة ، نقوم بتهيئة مؤشرين يسمى سريع وبطيء.

2. الآن نقوم بتشغيل حلقة للتنقل عبر القائمة المرتبطة. يجب تحريك المؤشر السريع موقعين أمام المؤشر البطيء في كل خطوة من خطوات التكرار.

3. لن تكون هناك حلقة في القائمة المرتبطة إذا وصل المؤشر السريع إلى نهاية القائمة (fastPointer == NULL أو fastPointer-> next == NULL). إذا لم يكن الأمر كذلك ، فستلتقي المؤشرات السريعة والبطيئة في النهاية ، مما يعني أن القائمة المرتبطة بها حلقة.

تنفيذ برنامج C ++ للطريقة المذكورة أعلاه (دورة فلويد):

انتاج:

توضيح:

1. 1. يتم تضمين الرؤوس ذات الصلة ، مثل 'bits / stdc ++. h' و 'std :: cout' أولاً.
   2. ثم يتم الإعلان عن بنية 'العقدة' ، والتي تعني عقدة في القائمة المرتبطة. يتم تضمين المؤشر التالي الذي يؤدي إلى العقدة التالية في القائمة مع حقل بيانات عدد صحيح في كل عقدة.
   3. ثم يقوم بتعريف 'deleteLoop' و 'detAndDeleteLoop' وهما وظيفتان. تتم إزالة حلقة من قائمة مرتبطة باستخدام الطريقة الأولى ، ويتم اكتشاف حلقة في القائمة باستخدام الوظيفة الثانية ، والتي تستدعي بعد ذلك الإجراء الأول لإزالة الحلقة.
   4. يتم إنشاء قائمة مرتبطة جديدة بخمس عقد في الوظيفة الرئيسية ، ويتم إنشاء حلقة عن طريق تعيين المؤشر التالي للعقدة الأخيرة على العقدة الثالثة.
   5. ثم يقوم باستدعاء طريقة “DiscoverAndDeleteLoop” أثناء تمرير عقدة رأس القائمة المرتبطة كوسيطة. لتحديد الحلقات ، تستخدم هذه الوظيفة نهج 'المؤشرات البطيئة والسريعة'. وهي تستخدم مؤشرين يبدأان في أعلى القائمة ، وهما slowPTR و fastPTR. بينما يقوم المؤشر السريع بتحريك عقدتين في وقت واحد ، فإن المؤشر البطيء يتحرك فقط عقدة واحدة في كل مرة. سيتجاوز المؤشر السريع المؤشر البطيء في النهاية إذا كانت القائمة تحتوي على حلقة ، وستصطدم النقطتان في نفس العقدة.
   6. تستدعي الوظيفة وظيفة 'deleteLoop' إذا وجدت حلقة ، تزود العقدة الرئيسية للقائمة وتقاطع المؤشرات البطيئة والسريعة كمدخلات. ينشئ هذا الإجراء مؤشرين ، ptr1 و ptr2 ، إلى عقدة رأس القائمة ويحسب عدد العقد في الحلقة. بعد ذلك ، يقوم بتقدم مؤشر واحد k عقدة ، حيث k هو العدد الإجمالي للعقد في الحلقة. ثم ، حتى يلتقيان في بداية الحلقة ، فإنه يدفع كلا النقطتين عقدة واحدة في كل مرة. ثم يتم كسر الحلقة عن طريق تعيين المؤشر التالي للعقدة في نهاية الحلقة إلى NULL.
   7. بعد إزالة الحلقة ، تعرض القائمة المرتبطة كخطوة أخيرة.

النهج 3: العودية

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

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

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

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

تنفيذ برنامج C ++ للطريقة المذكورة أعلاه (العودية):

انتاج:

توضيح:

1. 1. الوظيفة DiscoverLoopLinkedList () في هذا البرنامج يقبل رأس القائمة المرتبطة كمدخل.
   2. يتم استخدام العودية بواسطة الوظيفة للتكرار عبر القائمة المرتبطة. كحالة أساسية للتكرار ، يبدأ بتحديد ما إذا كانت العقدة الحالية فارغة. إذا كان الأمر كذلك ، فإن الطريقة ترجع خطأ ، مما يشير إلى عدم وجود حلقة.
   3. ثم يتم التحقق من قيمة الخاصية 'تمت زيارتها' للعقدة الحالية لمعرفة ما إذا تمت زيارتها مسبقًا. يعود صحيحًا إذا تمت زيارته ، مما يشير إلى أنه تم العثور على حلقة.
   4. تحدد الوظيفة العقدة الحالية على أنها تمت زيارتها إذا تمت زيارتها بالفعل عن طريق تغيير خاصية 'تمت زيارتها' إلى 'صحيح'.
   5. ثم يتم التحقق من قيمة المتغير الذي تمت زيارته لمعرفة ما إذا كانت العقدة الحالية قد تمت زيارتها مسبقًا. إذا تم استخدامه من قبل ، فيجب أن توجد حلقة ، وترجع الدالة صحيحًا.
   6. أخيرًا ، تستدعي الوظيفة نفسها بالعقدة التالية في القائمة عن طريق التمرير headNode-> التالي كحجة. بشكل متكرر ، يتم تنفيذ ذلك حتى يتم العثور على حلقة أو زيارة جميع العقد. يعني أن الوظيفة تضبط المتغير الذي تمت زيارته على صحيح إذا لم تتم زيارة العقدة الحالية مطلقًا قبل استدعاء نفسها بشكل متكرر للعقدة التالية في القائمة المرتبطة.
   7. يقوم الكود ببناء ثلاث عقد وينضم إليها لإنتاج قائمة مرتبطة في ملف الوظيفة الأساسية . طريقة DiscoverLoopLinkedList () ثم يتم استدعاؤها على عقدة رأس القائمة. ينتج البرنامج ' حلقة مخصومة في قائمة مرتبطة ' لو DiscoverLoopLinkedList () يعود صحيحا وإلا فإنه ينتج ' لم يتم الكشف عن حلقة في القائمة المرتبطة '.
   8. ثم تُدرج الشفرة حلقة في القائمة المرتبطة عن طريق تعيين المؤشر التالي للعقدة الأخيرة على العقدة الثانية. ثم ، بناءً على نتيجة الوظيفة ، يتم تشغيلها DiscoverLoopLinkedList () مرة أخرى وتنتج إما ' حلقة مخصومة في قائمة مرتبطة ' أو ' لم يتم الكشف عن حلقة في القائمة المرتبطة . '

الأسلوب 4: استخدام المكدس

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

فيما يلي وصف موجز للإجراء:

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

تنفيذ برنامج C ++ للطريقة المذكورة أعلاه (Stack)

انتاج:

توضيح:

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

• 1. توجد مكتبة تدفق الإدخال / الإخراج ومكتبة المكدس في السطر الأول.

  2. تم تضمين مساحة الاسم القياسية في السطر الثاني ، مما يسمح لنا بالوصول إلى وظائف مكتبة دفق الإدخال / الإخراج دون الحاجة إلى إضافة بادئة بـ 'std ::.'

  3. يحدد السطر التالي عقدة البنية ، والتي تتكون من عضوين: عدد صحيح يسمى 'البيانات' ومؤشر إلى عقدة أخرى تسمى 'التالي'.

  4. رأس القائمة المرتبطة هو إدخال لطريقة DiscoverLoopLinkedList () ، والتي تم تحديدها في السطر التالي. تنتج الدالة قيمة منطقية تشير إلى ما إذا تم العثور على حلقة أم لا.

  5. يتم إنشاء كومة من مؤشرات العقدة تسمى 'stack' ومؤشر إلى العقدة المسماة 'tempNode' والتي تمت تهيئتها بقيمة headNode داخل الوظيفة.

  6. ثم ، طالما أن tempNode ليس مؤشرًا فارغًا ، فإننا ندخل حلقة while.

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

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

  7. نعيد القيمة false بعد حلقة while لأنه لم يتم ملاحظة أي حلقة.

  8. نقوم ببناء ثلاثة كائنات Node وتهيئتها في الدالة main (). نظرًا لعدم وجود حلقة في المثال الأول ، قمنا بتعيين المؤشرات 'التالية' لكل عقدة بشكل صحيح.

خاتمة:

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