• 0
هاني الأتاسي

سلسلة - شغل مخك (33)

سؤال

بما أنو الحلقة 32 كانت بالlinked list فهذا السؤال كمان بال linked list ولكن المفروض يكون أسهل .. B)

فرضا كان لدينا linked list في الذاكرة و كل عقدة فيها عبارة عن التالي:

struct Node {
Data _data;
Node _next;
};

لدينا أيضا مؤشرين global إلى بداية اللائحة المترابطة ومؤشر إلى نهايتها ..

Node _head = {points to some node}
Node _tail = {points to some node}

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

تم تعديل بواسطه هاني الأتاسي
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

7 إجابة على هذا السؤال .

  • 0

السلام عليكم

هذه اول مشاركة لي في هذه السلسلة

اعتقد انه يمكن استخدام فكرة حل الحلقة 32 اي نعمل مؤشرين يسبق احدهما الاخر بعقدتين

مثال

----

نرغب بحدف العقدة رقم 4

1 -> 2 ->3 ->4 ->5 ->6 ->7

حيث h=1 و t=7

P_Del = 4

Int.

P_Slow = 1 P_Fast=1

P_Slow = 1 P_Fast=3

P_Slow = 2 P_Fast=4

P_Slow = 3 P_Fast=5

--------------------------------

هنا يتم الحدف لان

P_Fast = P_Del->NEXT

وبعد ذلك نحدث مؤشر كتالي

P_Slow = 1-->NEXT = P_Fast=1

تحياتي

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

في مثالك حصل أن أتت p_del بين p_slow و p_fast وبالتالي استطعت مسح p_del وجعل مؤشر التالي ل p_slow يؤشر إلى p_fast .. ولكن ماذا لو أردت مسح 5 فلن يظبط معك ..

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

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

هنا لدينا ثلاث حالات

- حدف العقدة h

P_h = P_h --->NEXT

THEN Del P_j

2- حدف العقدة t

3- حدف غقدة بين h و t

__________________

بالنسبة للحل السابق اعتقد انه صحيح و يمكن ان يطبق على الحالة الثانية و الثالثة

فمثلا لحدف العقدة رقم 5

h=1 و t=7

P_Del = 5

Int.

P_Slow = 1 P_Fast=1

P_Slow = 1 P_Fast=3

P_Slow = 2 P_Fast=4

P_Slow = 3 P_Fast=5

P_Slow = 4 P_Fast=6

--------------------------------

هنا يتم الحدف لان

P_Fast = P_Del->NEXT

وبعد ذلك نحدث مؤشر كتالي

P_Slow = 1-->NEXT = P_Fast=1

_______________________________

اما بالنسبة للحالة الثانية فيمكن فنفس الشي ولكن هنا سنبحث عن Null

اي

P_Fast = Null

OR

P_Fast = P_t->NEXT

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

لحل هذه المسئلة يكفى مؤشر إضافى واحد فقط, ويصبح الhead حالة خاصة .

x=head
if (value ==head){
head=head.next;
delete x;
}
else
{
while (x.next!=value){
x=x.next;
}
x.next=x.next.next;
delete x;
}

وطبعاً value هو المؤشر الذى يؤشر إلى العنصر المراد التخلص منه

,وكان الله يحب المحسنين..

والسلام عليكم

تم تعديل بواسطه احمد غريب
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

ثلثين المساله بسيط جدا , والثلث الأخير طوييييل

لحذف العقده س سنقوم بنقل العقده التاليه لها في مكانها

في حالة ما تكون العقده التي نريد حذفها هي عقده من وسط السلسله او أول عقده فلا توجد مشكله لأن العناوين لمم تتغير في هذه العقده

أما في حالة ما تكون العقده التي نريد حذفها هي الأخيره فـــ :s لا يوجد حل الا ان نمر على السلسله كلها

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

نعم Asm4all طريقتك صحيحة :) لا أعتقد يوجد اسرع منها في حالة أردنا حذف آخر عقدة ..

أي متبرع يضع كود؟

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أنا راح أتبرع بالكود هالمرة ..

void DeleteNode(Node* p) {
  if (!p) return;

  if (p == _tail && p == _head) {
     _tail = _head = NULL;
     delete p;

  } else if (p == _tail) {
     p = _head;
     while (p->_next != _tail)
        p = p->_next;
     p->_next = NULL;
     delete _tail;
     _tail = p;

  } else {
     Node* after = p->_next;
     p->_data = after->_data;
     p->_next = after->_next;
     delete t;
  }
}

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
زوار
This topic is now closed to further replies.

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .