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

طب لو عندى linked list زى دى مثلا

7 6 5 4 3 2 1

وال7 الNext بتاعها بيشاور على ال4

يبقى الحل كذلك

Slow = 1 and fast = 3

slow = 2 and fast = 5

slow = 3 and fast = 7

ثم

slow = 4 and fast = 5

إزاى بيقى تم عملية التطابق ياريت التوضيح هل التطابق أن الslow = fast = Node->DAta or wat???

ياأحمد :D انا فاهم عليك .. عملية المورو الأولى لا غبار عليها ولكن انا كلامي على عملية ارجاع المؤشر next في كل عقدة إلى حالته السابقة فلا أرى أنها ممكن من غير استخدام ذاكرة اضافية ..

إذا أخد من الأخوى فهم حل أحمد يوضحلي ..

إنج علام... أكمل السلسلة ...

slow = 5 fast = 7

slow = 6 fast = 5

slow=7 fast=7

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

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

eng_3llam طيب حاول كالتالي :

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

initial case:

fast = 1

slow = 1

moving:

fast = 3

slow = 2

fast = 5

slow = 3

fast = 7

slow = 4

fast = 5

slow = 5

لاحظ كيف اشار fast و slow على نفس العقدة .. تتم عملية التطابق باستخدام قيمة المؤشرات اي المؤشر fast ينطبق على المؤشر slow ..

أفكر بإيجاد صيغة للتطابق الآن !!

بالنسبة للحلقة الكاملة "آخر عنصر يشير لأول عنصر في القائمة"

التطابق في حل هاني سيحدث في حال عداد بسرعتين , وعداد بسرعة واحدة بعد n مرة دائما "حيث n عدد العقد !! "

لو زدت سرعة العداد الأول إلى 3 سيحدث التطابق أيضا بعد n مرة ,,

لكن لتقليل لاعدد الذي يجب أن يحدث فيه التطابق , نغير سرعة العدادين :

أحمد:

اقتباس

وكل ما عليك عملة هو ان تبداء من اخر عنصر وتقلب المؤشرات

أحب أن أرى هذا الكود الذي يقوم بعمل هذا القلب :unsure: :unsure: :unsure: .. مسئلتك تحولت إلى السؤال التالي :

نحن الآن نقف في آخر linked list كيف سوف نصل إلى أولها .. طبعا هذا الأمر مستحيل في single linked list .. <_<

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

هيثم ولا هارون مو مهم :D .. انظر الtracing الذي وضعته فn = 7 ولكن وجدنا النتيجة بعد 4 تكرارات فقط ..

أحمد:: انظر هذا المثال:

(p) will always point to the node after the two nodes we are flipping

1->2->3
    ^--|

1<-2  p = 3

1<-2<-3  p = 2

1  2<-3  p = 1 (ok we reached the head, cool! it's circular then)
    |--^

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

غداّ إن شاء الله اكتب خوارزمية لان الوقت متاخر الان ولدى عمل الله وحده يعلم كم انا متورط, دعوتكم,,,

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

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

محاولة بإستخدام طريقة المؤشرين التي تم شرحها

node *p_slow
node *p_fast

while (p_fast && (p_slow != p_fast)) {
	p_slow = p_slow->next;
	p_fast = p_fast->next;

	if (p_fast)
  p_fast = p_fast->next;
	else
  break;
}

if (!P_fast)
	printf("not circular.\n");
else
	printf("circular.\n");

circular bool;
node *x=NULL;

node *current=&head;

node *y=&head.next;
while (y!=null  && y!=head) {
current.next = x;
x=current;
current=y;
y=y.next;
}
if(y) {
circular=true;
cout << "Circular list found<< endl;
}
else{
circular=false;
cout << "Noncircular list found<< endl;


while (x!=null  && x!=head) {
current.next = y;
y=current;
current=x;
x=x.next;
}

هذه هى الخوارزمية ارجو ان تكون واضحه ....

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

ib_doom .. نعم هذا الكود يقضي بالغرض ولكن سقط سهوا اسناد p_slow و p_fast إلى قيمة أولية وهي head ..

اخي أحمد شكرا على مشاركتك وكتابتك للخوارزمية :)

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

1- طريقتك تعمل فقط إذا كان thread واحد يستخدم السلسلة .. لأنه بما أنك تعكس السلسلة كلها فهذا يؤدي إلى قرائات خاطئة في threads اخرى

2- طريقتك هي O(N) لكن فعليا تحتوي على العديد من نسخ مؤشرات (في المنطقة الخطية من اللائحة الحلقية سوف تمر عليها 4 مرات). وتحتوي على حلقتين ، فعليا هي أبطأ بثلاث مرات على الأقل من الطريقة الأولى

:rolleyes: شكرا للجميع على التجاوب مع هذه الحلقة من شغل مخك :lol: .. تشغيل المخ كان تمام هون ;)

الحلقة الجاية عمأكتبها هلأ .. B)