اجتياز قائمة مرتبطة منفردة في C++

Question

كنت أتساءل عما إذا كان من الممكن اجتياز قائمة مرتبطة مثل هذا:

currentNode = randomNode;//where randomNode may or may not = firstNode
prevNode = firstNode;
while(prevNode != currentNode && prevNode->link != currentNode)
{
    prevNode = prevNode->link;
}

هل من الممكن القيام بذلك في C++ عندما أحاول العثور على العقدة قبل currentNode في قائمة مرتبطة بشكل فردي؟

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

Answer 1

قد ترغب في التأكد من أن الرابط السابق> ليس مرجعا فارغا أيضا، في حالة عدم ربط Case CurrentNode بالفعل.

Answer 2

يجب أن تعمل على ما يرام. هل جربتها بعد؟

Answer 3

سيقوم هذا الرمز بنزالية جزء من قائمتك، ولكن الجزء الذي يعتمد على الطريقة التي ترتبط بها قائمة قائمتك. إذا كنت تذهب من الرأس -> الذيل (اقرأ: روابط عقدة الرأس إلى عقدة يرتبط تجاه الذيل) ثم تقوم بتجاوز قائمتك تبدأ من الموقع العشوائي إلى الذيل. إذا كانت الروابط هي رأس <-Tail فأنت ستعمل من الموقع العشوائي إلى الرأس. في كلتا الحالتين، لن تلمس كل العقد في القائمة.

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

[head]<->[0...N Nodes]<->[Tail]

الروابط يمكن أن تكون في كلتا الحالتين.

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

Answer 4

تأكد من مراعاة جميع حالات الحافة المحتملة:

• ما يحدث randomNode يساوي firstNode؟ماذا ترجع؟ماذا يجب لقد عدت؟
• ماذا يحدث عندما randomNode هي العقدة الأخيرة في القائمة؟
• ماذا يحدث عندما randomNode يكون NULL?
• ماذا يحدث عندما randomNode ليس في القائمة؟

الآن، قد لا تكون كل هذه الحالات قابلة للتطبيق، اعتمادًا على ما إذا كنت تعرف أي شيء عنها randomNode, ، وبعضها قد يكون تافهاً.لكنها كلها تستحق التفكير فيها.

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

Answer 5

يبدو الرمز جيدا، لكنني أقترح تغييرا بسيطا while شرط

while(prevNode != currentNode && prevNode != NULL)

لسببين

• رمزك، كما هو مذكور حاليا، يمكن أن تتوقف إذا تمت الإشارة إلى العقدة التي نبحث عنها بواسطة أي prevNode أو prevNode->link (وبالتالي لن يكون لدينا فكرة واحدة خاصة من النقاط currentNode - إذا أردنا أن نعرف، فيمكننا التحقق من if شرط). مع التغيير أعلاه، مضمونة العقدة المستهدفة prevNode (إذا كان على الإطلاق - انظر النقطة التالية).
• من أجل السلامة، سيكون من الجيد التحقق من ذلك prevNode ليس NULL. وبعد ومع ذلك، كما يذكر بافل، هذا الاختبار غير ضروري إذا currentNode مضمون أن تكون في القائمة.

---

تحرير استجابة للتعليق

بالنظر إلى أنك لست بحاجة إلى معرفة ما إذا كان currentNode في داخل prevNode أو prevNode->link, ، وبما أنك تريد أن تتوقف (إن أمكن) currentNode == prevNode->link, ، ثم الأصلي الخاص بك while على ما يرام. ومع ذلك...

هناك بيان إذا أعلى في التعليمات البرمجية التي تمنع prevNode من كونها فارغة بالفعل

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

while(prevNode != NULL && prevNode != currentNode && prevNode->link!=currentNode)

إذا كنت متأكد تماما الذي - التي currentNode سيكون في القائمة، ثم أنا خمن هذا الشيك هو أيضا غير ضروري، لكنها عادة جيدة حقا للدخول.

Answer 6

يمكنك حتى:

while (prevNode && prevNode != currentNode)
    prevNode = prevNode->link;

ولكن ما لديك تبدو جيدة.

Answer 7

شيء صغير أغيره مع التعليمات البرمجية باسم نشر (بصرف النظر عن الاحتمال الذي تمت مناقشته في إجابات أخرى من تشغيل نهاية القائمة إذا لم يكن CurrentNode في القائمة أو معالجة الأخطاء الأخرى) هو أنه عندما يتم الحلقة أثناء ذلك أنت لا تعرف ما إذا كان prevNode أو prevNode->link نقاط ل currentNode. وبعد هذه ليست مشكلة ضخمة (نظرا لأنك تستطيع اختبارها بسهولة)، لكن يبدو لي أنه من الأفضل اختبار هذا الوضع الخاص بهذا الحالة قبل البحث، لذلك من الواضح أنه حالة خاصة.