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

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

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

لو كان الlinked list is circular closed ممكن أعمل check على الprevious بتاع الhead لو كان بNull يبقى الlinkedlist دى مش

closed circular

إذن لايمكن أن نكتب في أي عقدة أي شيء إضافي , ولايمكن أن نستخدم linklist أخرى للبحث السريع , ولايمكن إستخدام مصفوفة في الذاكرة , عدد العقد غير معروف , لايوجد prev , العقدة الأخيرة غير معروفة ,

الموضوع تماما كالبحث عن عدد مكرر في السلسلة التالية مثلا :

3 5 6 2 55 77 99 234 433 111 6

سنجد أن ال 6 مكررة , لكن المشكلة أن البحث في إتجاه واحد فقط ,, ولايمكن العودة للوراء بسهولة ,,

===========

أو أن نعرف العقدة الأخيرة ...

هيثم ، أعتقد أنك تقصد بهذه الأرقام انها مؤشرات في الذاكرة .. ليس من السهل أن تجعل المقارنة التي تحدثت عليها بتعقيد خطي ..

eng_3llam .. لا تنسى أن العقدة الأخيرة قد تشير إلى أي عقدة في اللائحة وليس شرط العقدة الأولى .....

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

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

فبذلك سنبحث عن شيئين في نفس الوقت ,,

طيب خذ هذه .....

نستخدم طريقة فصل العقد من بعضها وبعد ذلك نربطها عندما ننتهي!

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

نغير إتجاه المؤشر حيث نجعل كل مؤشر يوشر إلى ما قبلة وفى الاخير إما ان نصل إلى مؤشر يؤشر لnull وإما نصل إلى مؤشر head مرة اخرى ..

طيب هي مساعدة ..

لو عندك عدائين بيركضو في حلقة مغلقة وأحدهما أسرع من الآخر ماذا يحصل؟

:P

ممكن أبحث عن طريق الnull كما قال الاخ هيثم عن طريق إستخدام الbinary search

?????

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

  static Node last=null;
	static boolean flag=false;
	public static void separate(Node n){
  Node node=n.next;
  if(node==null){
 	 last = n;
 	 return;
  }
  n.next=null;
  separate(node);
  n.next=node;
  if(last==n)flag= true;
//  System.out.println ((node.next==null));
  return;

طرقة جميلة اخى هانى نبداء بمؤشر وبعد ان نمر على عدد من العناصر نبداء بمؤشر اخر وإذا إلتقى المؤشران معنى ذلك ان هناك حلقة, وللتاكد من لقائهما نقوم بقفزتين للمؤشر الاول مقابل قفزة للمؤشر الثانى,,,,

ولكن الحل الذى كتبته اخر مرة اتعتقد انه اسرع, يعنى عكس المؤشرات حتى تصل إلى null او تصل إلى head :::

أبو مازن :

اقتباس

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

كيف ستعيد ترتيبها من جديد بما أنك ضيعت عناوين next الخاصة بها ؟

==========

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

أو أني لم أفهم ال hint !!

أبومازن .. circular linked list لا تحتوي على مؤشر null ابدا في اي عقدة كانت ..

أحمد غريب .. حلك الأول يعتمد على عقدة ال head وانا كما قلت ليس من الشرط أن نرجع إلى ال head في مثالي .. أيضا لا أحبذ طرريقة تغيير بنية اللائحة المترابطة .. بالنسبة لحلك الثاني فهو صحيح :D .. فنقوم باستخدام مؤشرين واحد اسرع من الآخر بقفزتين .. في حالة linear linked list فسوف نحصل على null في الcircular linked list فسوف ينطبق المؤشران على بعضهما ..

أي متبرع يكتب لنا اللكود :D

هارون الشفرة أمامك...

لاحظ أني استخدمت دالة تنادي نفسها..

لاحظ أني بعد أن أفصل العقد، أحصل على آخر عقدة،، بعد ذلك أعيد تركيب العقد مع مقارنة آخر وصلة مع كل الوصلات!!

وبهذا أحصل على النتيجة!!

وهذا البرنامج التجريبي الكامل!

class Node{
	Node next;
	public String toString(){
  return ("node\t"+((next==null)?null:next.toString()));
	}
}
public class LinkedTest{
	public static void main(String[]args){
  Node n=getNode();
  separate(n);
  System.out.println (flag);
//  System.out.println (n);
  
	}
	public static boolean test(Node n){
  return true;
	}
	static Node last=null;
	static boolean flag=false;
	public static void separate(Node n){
  Node node=n.next;
  if(node==null){
 	 last = n; //I got the last Node!!!!!!!!!!!!!!!!
 	 return;
  }
  n.next=null;//Setting the next node to be null!!
  separate(node);
  n.next=node;//Setting the next node to be what it use to be!!
  if(last==n)flag= true;
//  System.out.println ((node.next==null));
  return;
	}
	public static Node getNode(){
  Node first=new Node();
  Node n=first;
  n.next=new Node();
  n=n.next;
  n.next=new Node();
  n=n.next;
  n.next=new Node();
  n=n.next;
  n.next=new Node();
  n=n.next;
  n.next=new Node();
  n=n.next;
  n.next=new Node();
  n=n.next;
  n.next=first.next.next;
  
  return first;  
  
	}
}

طب ما بردة حل الاخ أحمد غريب سيؤدى الى الBig Oh =n ودة إستهلاك للرام بما إنها فيها iteration ؟؟

طب ما الbinary search فية iteration بس الBig Oh ممكن يكون log n base 2

لن تتغير بنية اللائحة يمكنك إعادتها كما كانت بنفس الطريقة والوقت لن يتغير لانهما حلقتين منفصلتين يعنى O(N)....

شباب بس معليش يعني ,, أحمد أو هاني , أو أي شخص آخر يوضح موضوع القفزة والقفزتين ؟؟

ومالمشكلة لو بحثنا عن عنوان فليكن للعقدة الخامسة وكان , 0x5673fa مثلا ومررنا على كل ال next وقارناها بهذا العنوان أو ب null

if (node.->next == 0x5673fa )
cout << "circular";
if (node->next==NULL)
cout << "leaner";

//else we will move next and keep searching !!

========

الشيء الثاني السؤال لأحمد غريب وأبومازن , بما أننا لانستطيع كتابة بايتات إضافية على بنية Linklist فكيف يمكن إعادة ترتيبها كما كانت ؟ وبدون أن نكتب أي شيء إضافي على الذاكرة كما وضح هاني ؟ لأنها ستضر بالمحتوى الخاص بالمستخدم إن تغيرت ,,,

أخي هارون،، الشفرة أمامك،، لاحظ أني استعملت (دالة تنادي نفسها):

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

 public static void separate(Node n){
 Node node=n.next; // I am saving the next node temporarily. أحفظ العقدة التالية مؤقتا!
 if(node==null){
  last = n; //I got the last Node!!!!!!!!!!!!!!!!// وجدت آخر عقدة!!
  return;
 }
 n.next=null;//Setting the next node to be null!!//نفصل العقدة ، ولا ننسى أننا خزناها مؤقتا!!
// نبحث في الوصلة التالية separate(node);
 n.next=node;//Setting the next node to be what it use to be!!// الآن نرجع العقدة إلى صاحبتها
 if(last==n)flag= true;
//  System.out.println ((node.next==null));
 return;
}

أها أبو مازن فهمت عليك الآن .. حلك صح بس فرضا كانت اللائحة عبارة عن 100000 الف عقدة .. فماذا سوف يحدث للكود تبعك .. سوف تستخدم على الأقل 100000 تعادوية وهذا استهلاك كبير للذاكر بالاضافة إلى أنه قد يؤدي إلى stack overflow .. لكن بشكل عام هي طريقة صحيحة وذكية ولكن تعقيدها في الذاكرة خطي وليس ثابت O(1)

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

هيثم .. نعم نريد أن نرى إذا وصلنا إلى نفس العنوان ولكن هذا العنوان ليس ثابت بل متحرك لأنه لا يمكنك معرفة اين سوف تثبت هذا العنوان .. لذلك قلت أنه يمكن عن طريق استخدام مؤشرين نحرك احدهما بضعف سرعة الآخر ..

eng_3llam .. ليس من حسن الأداء تطبيق binary search على linked list لأنه لا يمكن الوصول إلى العقد باستخدام index ..

هيثم انا أقصد هكذا :

Node* pSlow = head;
Node* pFast = head;

// when u want to move the pointers you do
pSlow = pSlow->next;
pFast = pFast->Next->Next;

طبعا الكود السابق ليس صحيح ولا كامل فقد تكون pFast->Next == null ..

صعب اوضح ما اقصد ولكن فكر فيها وحاول تعمل امثلة وسوف تلاحظ ان طريقتى لا غبار عليها, عندما تعكس الموشر إما ان تصل إلى null وفى هذه الحالة عكست السلسلة بالكامل ويمكنك إعادتها بنفس الطريقة حيث تبداء من اخر عنصر حتى تصل إلى head::

,وإما ان هناك حلقة وفى هذه الحالة لن تعكس إلا الحلقة ويمكنك ان تبداء من head وسوف يتم عكس الحلقة لتعيدها كما كانت... انا فكرت فى الموضوع وجربت بعض الامثل ومتاكد من ما اقول ...

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

فكرة السباق فكرة جميلة وسريعة،

عدد التكرار ليس بالضرورة أن يصل إلى عدد العقد!

لو كانت عدد العقد تساوي 10 وهي حلقية بالكامل، فجملة التكرار ستتكرر 5 مرات فقط !

بارك الله فيك!

----

فكرتي ستضطر إلى التكرار بعدد العقد بالكامل،، فلو كانت العقد تساوي 10 للزم التكرار 10 مرات!

أحمد .. لما تقلب الاتجاهات كلها بالعكس و أنت الآن واقف في ال head وتأكدت أن اللائحة عبارة عن circular ، وعلى الأغلب لديك مؤشر يشر إلى head ومؤشر يشير إلى ماقبل ال head .. الآن.. كيف سوف تستطيع الوصول إلى المؤشر ماقبل قبل ال head والذي قبله والذي قبله إن كان كل المؤشرات قد انعكست بالأساس ..

وربما لو أردت زيادة السرعة،، أضف متسابقا جديدا أو متسابقين بسرعات مختلفة!

لديك ثلاث مؤشرات احتياطية المؤشر الاول يؤشر إلى head والثانى إلى head.next والثالث إلى head.next.next والان يمكن ان تلغنى الموشر head.next وتجعل المؤشر head.next.next يوشر لhead.next وبعد ذلك تحرك الثلاث مؤشرات خطوة إلى الامام وهكذا إلى ان تصل إما ل null او تصل لhead مرة اخرى ... يعنى العملية عايزلها رسم بيانى للتوضيح بس انا عندى ضيق وقت شنيع للاسف.... ارجوكم حاولو تفهمونى ...