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

البحث عن next = null

إذا لم تجد null كانت السلسلة حلقية...

طيب إذا كانت حلقية وضليت تبحث عن null ..

شو راح يصير معك ;) بإذن واحد أحد ماراح تخرج من الloop ..

سجل أول وصلة، وقارنها مع كل (تالي) ،، إذا كانت تساوي نفس الوصلة إذن هي حلقية!

إذا وجدت null يعني خطية!

طبعا لايمكن ياأبو مازن أن تكون بهذه البساطة أسئلة هاني :D ,,

لو كان لديك ذاكرة 600 تيرابايت , وبها لنك لست ملئت هذه الذاكرة , ستعرف أنها حلقية بعد قيام الساعة :D

لأنك ستذهب إلى نهاية اللنك لست , وستأخذ وقت طويل جدا ,,

هاني يريد فكرة سريعة لاتضر بالزمن ولابالذاكرة ,,

أبو مازن :D

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

نعم هيثم أقصد أسرع طريقة أي بتعقيد خطي O(N) ولا تستخدم مصفوفة في الذاكرة B)

السلام عليكم

بما انك فى head ما عليك سوى العودة إلى الخلف لتعرف إذا كانت السلسلة مترابطة, ولا انا فاهم السؤال غلط ؟؟؟

اسف انا كنت فعلاً فاهم السؤال غلط انت تتحدث عن linked list و ليس double linked list :blink:

سندخل بذلك في خوارزمية بحث , في هذه الحال يمكن أن نقارن أول خانة مع كل الروابط next , إن لم نجد نقارن من الخانة الثانية مع كل next , إن لم نجد , نقارن من الثالثة مع كل Next ,, "هذه أسهل خوارزمية بحث " , لكنها ليست الأسرع ...

هل تقصد أننا لايمكن أن نستخدم مصفوفة في الذاكرة , أي مصفوفة بمعناها الحرفي , "متتالية عناوين في الذاكرة" أم أننا لانحجز لأي خانات في الذاكرة إطلاقا ؟

يعني مثلا يمكن أن أنشيء Linklist للبحث بطريقة أخرى ,,

هناك طريقة ولو انها ليست جميلة ولكنها تؤدى الغرض..

احصل على عنوان الذاكر وهو الذى يحمل المؤشر head إطرح منه عدد يساوى حجم الnode وفى الخانة التى من المفترض انها تحتوى على عنوان next إقراء محتوى هذه الذاكرة, إذا كان يساوى عنوان الذاكر node إذاً فهى حلقة وإذا كانت غير ذلك فهى ليست حلقة ...

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

أحمد حتى لو كانت doublly linked list لا يمكن حلها بطريقة العودة للوراء . أيضا أحمد أنت تتكلم على طريقة الأسمبلي .. أنا أريد خوارزمية والكود يأتي بعدها .. في السي يمكنك الوصول إلى next فقط عن طريق التالي p->next

راجع جوابي السابق على أبو مازن لتعرف أن الطريقة التي ذكرتها لا تعمل هنا

هيثم طريقتك تعقديها O(N^2)

//First i defined a tail for point to the end of the linked list
NODE* tail;
bool IsCircularLinkedList(NODE *head)
{
 if(head !=0)   //so their an exist linkedlist
  {
   if(tail  == head)  //or if(tail->Data() ==head->Data()) or tail->Next() == head->Next()  //Data method for Get the Data from the node
    return true;
   else
    return false;

  }
}

على ما أعتقد

توضيح

إذا كان node عنوانها 0x00403000 وحجم الnode يساوى 10 بايت نقوم بالتالى :

0x00403000-0xA=0x0042FFF5

ولنفترض ان next موقعها هو اول dword ما علينا سوى التحقق من محتوى الذاكره 0x0042fff5 إذا كان هذا العنوان يحتوى على الرقم 0x0043000 إذاُ فهى حلقة اما غير ذلك فهى ليست حلقة

والسلام

أحمد غريب :

linklist تقوم بحجز العقد وقت الإستخدام , أي ليس بالضرورة أن تكون عناوين العقد مرتبة بمتتالية كما الحال في المصفوفات العادية ,,

يمكن أن تكون كل عقدة موجودة في مكان أو بلوك بعيد تماما في الذاكرة وبصورة عشوائية ولن تربط هذه العقد إلا الروابط next فقط ,,, وإلا ستضيع عقدك في الذاكرة ,, لذلك تحرير الذاكرة في Linklist لديها خوارزميات خاصة تحذف العقدة من مكانها وتربط العقدة السابقة والتالية مع بعضها ,,

هاني .... صبرا B)

كيف ذلك اخى هانى إذا كانت double linked list إذاُ لديك مؤشرين احدهما next والاخر preveous وحسب قانون الdouble linked list كل node له مؤشر للامام عدى اخر عنصر وكل node له مؤشر للخلف عدى اول node إلا إذا كانت الحلقة مغلقة ...

eng_3llam ال circular linked list ليس لها tail

معك حق يا اخ هيثم الlinked list تكون مرتبة عند إنشائها ولكن إذا قمت بعملية حذف او تعديل فهى بالفعل تفقد الترتيب فى الذاكرة...

إذاً الحل الوحيد هو المرور على المصفوفة ومقارنة كل next ب head او بnull وهذه تستدعى O(N); لاننا نمر على المصفوفة مرة واحدة فقط....

هل لنا أن نكتب على الوصلة شيئا؟؟

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

وأعتقد أن سرعة البرنامج ستكون (1) والله أعلم!

int temp=head;
if(temp.next==null)
return false;
temp=temp.next;
while(temp!=null || temp!=head)
temp=temp.next;
end while;
if(temp.next==null)
return false;
else return true;
end if;

أبو مازن طريقتك صحيحة في حالة كان بامكانك كتابة شئ في العقدة بأنك زرتها .. :) .. ولكن للتصعيب أكثر لا .. لا يمكنك كتابة أي شئ في العقدة .

أحمد غريب : اقرأ تعريف اللائحة الحلقية .. حيث ليس من الشرط ان يكون آخر عقدة تشير إلى أول اللائحة بل ممكن أن تشير إلى أي عقدة ..

مثال فرضا لدينا اللائحة التالية :

1->2->3->4->5----->3 (العقدة 5 تشير إلى 3 وليس 1)

اعذر جهلى اخى هانى انا كنت اعتقد ان الحلقة تنتهى عند اول عنصر

هل بالإمكان معرفة عدد العقد؟

بمعرفة عدد العقد، نستطيع أن ندخل داخل جملة التكرار ونخرج في حالة أننا كررنا البحث أكبر من عدد العقد!

هناك حل اخر وهو ان تضع عنصر جديد فى النود وتسميه visited وتضعه false كقيمة إبتدائية وعندما تمر على كل عنصر تغير قيمة visited ل true وبذل إذا قمت بالمرور من نفس العنصر مرتين تستطيع ان تتعرف علية ..