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

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

سؤال

هالمرة سؤال برمجي :) وله علاقة بال Linked List ..

ماهي أسرع طريقة من أجل معرفة إذا كانت اللائحة المترابطة Linked List عبارة عن لائحة حلقية Circular Linked List أو أنها عبارة عن لائحة خطية Linear Linked List ,

يفضل أيضا أن تكتب كود للتابع :

bool IsCircularLinkedList(NODE *head);

حيث head يعتبر مؤشر لأول اللائحة و NODE تحتوي على مؤشر للعقدة التالية next ...

تعريف Circular Linked List: هو أي لائحة بحيث أن المؤشر next لآخر عقدة يشير إلى عقدة في نفس اللائحة

تعريف Linear Linked List: هو أي لائحة بحيث أن المؤشر next لأخر عقدة يشير إلى null

بعض الأمثلة على circular linked list الموضحة في السؤال:

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

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

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

B)

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

شارك هذا الرد


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

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

  • 0

البحث عن next = null

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

0

شارك هذا الرد


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

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

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

0

شارك هذا الرد


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

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

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

0

شارك هذا الرد


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

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

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

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

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

0

شارك هذا الرد


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

أبو مازن :D

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

0

شارك هذا الرد


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

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

0

شارك هذا الرد


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

السلام عليكم

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

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

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

شارك هذا الرد


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

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

0

شارك هذا الرد


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

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

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

0

شارك هذا الرد


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

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

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

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

0

شارك هذا الرد


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

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

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

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

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

شارك هذا الرد


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

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

 }
}

على ما أعتقد

0

شارك هذا الرد


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

توضيح

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

0x00403000-0xA=0x0042FFF5

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

والسلام

0

شارك هذا الرد


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

أحمد غريب :

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

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

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

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

شارك هذا الرد


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

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

0

شارك هذا الرد


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

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

0

شارك هذا الرد


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

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

0

شارك هذا الرد


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

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

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

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

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0
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;

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

شارك هذا الرد


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

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

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

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

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

0

شارك هذا الرد


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

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

0

شارك هذا الرد


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

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

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

0

شارك هذا الرد


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

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

0

شارك هذا الرد


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

أحمد غريب ، سبقك بهذا الحل أبو مازن .. ولكن لا - لايمكن أن تغير أي شئ في العقدة ..

أبو مازن .. كمان لا - لايمكن معرفة عدد العقد مسبقا .. :)

0

شارك هذا الرد


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

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

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