טוען...
טוען...
שימו לב
בכל שאלה שנדרש בה מימוש אפשר להשתמש בפעולות של המחלקות: תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם משתמשים בפעולות נוספות, יש לממש אותן.
בשרשרת חוליות, "העברה מעגלית של n חוליות" היא העברת n החוליות האחרונות לתחילת השרשרת (בלי לשנות את סדר הופעתן).
✎ בדוגמה שלפניך בעבור
n = 2מעבירים את שתי החוליות האחרונות לתחילת השרשרת.
שרשרת החוליות לפני ההעברה
lst -> 5 -> 1 -> 2 -> 8 -> 4 -> null שרשרת החוליות לאחר ההעברה
lst -> 8 -> 4 -> 5 -> 1 -> 2 -> null
כתבו פעולה חיצונית ששמה move המקבלת שרשרת חוליות — lst מטיפוס שלם ומספר n מטיפוס שלם. הפעולה תחזיר את שרשרת החוליות לאחר "העברה מעגלית של n חוליות".
הניחו ש־n ≥ 0 ומספר החוליות בשרשרת גדול מ־n.
מהי סיבוכיות זמן הריצה של הפעולה שכתבתם בסעיף א? נמקו.
שימו לב
בכל שאלה שנדרש בה מימוש אפשר להשתמש בפעולות של המחלקות: תור, מחסנית, עץ בינרי וחוליה, בלי לממש אותן. אם משתמשים בפעולות נוספות, יש לממש אותן.
בשרשרת חוליות, "העברה מעגלית של n חוליות" היא העברת n החוליות האחרונות לתחילת השרשרת (בלי לשנות את סדר הופעתן).
✎ בדוגמה שלפניך בעבור
n = 2מעבירים את שתי החוליות האחרונות לתחילת השרשרת.
שרשרת החוליות לפני ההעברה
lst -> 5 -> 1 -> 2 -> 8 -> 4 -> null שרשרת החוליות לאחר ההעברה
lst -> 8 -> 4 -> 5 -> 1 -> 2 -> null
כתבו פעולה חיצונית ששמה move המקבלת שרשרת חוליות — lst מטיפוס שלם ומספר n מטיפוס שלם. הפעולה תחזיר את שרשרת החוליות לאחר "העברה מעגלית של n חוליות".
הניחו ש־n ≥ 0 ומספר החוליות בשרשרת גדול מ־n.
מהי סיבוכיות זמן הריצה של הפעולה שכתבתם בסעיף א? נמקו.