מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/רשימות מקושרות/תרגילים

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

קביעת כל איברי רשימה מקושרת לערך יחיד[עריכה]

שאלה[עריכה]

אנא כתוב מימוש יעיל לפונקציה List-Set-All(l, v) המקבלת (מצביע ל)רשימה מקושרת l, ערך v, וקובעת את הערכים בכל חוליות הרשימה לv.

תשובה[עריכה]

# Takes a list (l) and a value (v).
# Modifies all the links in the list so that their value is v.
List-Set-All(l, v)
1	lnk = l.front

2	while lnk != Nil
3		lnk.value = v
4		lnk = lnk.next

איחוד רשימות מקושרות[עריכה]

שאלה[עריכה]

אנא כתוב מימוש יעיל לפונקציה List-Union(l1, l2) המקבלת (מצביעים ל)רשימות מקושרות 1l וl2. לאחר הקריאה לפונקציה, על 1l להכיל את איחוד האיברים שהיו בשתי הרשימות לפני הקריאה, ועל l2 להיות ריקה.

תשובה[עריכה]

# Takes two lists (l1, l2).
# Modifies them so that all the links are in the first list (l1),
#	and the second list (l2) is empty.
List-Union(l1, l2)
1	if l1.back != Nil
2		l1.back.next = l2.front
3	if l2.front != Nil
4		l2.front.prev = l1.back

5	l1.back = l2.back
6	l1.size = l1.size + l2.size

7	l2.front = l2.back = Nil
8	l2.size = 0


החלפת הסדר של רשימה מקושרת חד כוונית[עריכה]

שאלה[עריכה]

להלן מבנה אפשרי לרשימה מקושרת חד-כוונית.

הרשימה מורכבת מחוליות. כל חוליה נראית כך:

# A data structure that describes a link which has a value, and can
#	be connected to a following and previous link.
Link
	# The next Link.
1	next
	# The value at this link.
2	value

להלן הפסוודו-קוד לרשימה עצמה:

# A data structure that describes a (doubly-linked) list of values.
List
        # The leftmost link.
1      front
        # The size (number of links).
2      size

(שימו לב שזה כמובן אינו המבנה היחידי האפשרי לרשימה מקושרת חד-כוונית: ייתכנו מימושים אחרים בעלי שדות עם שמות ומשמעויות שונים מעט.)

אנא הצע אלגוריתם בסיבוכיות ובעל דרישת זיכרון קבועה (כלומר, שאינה גדלה עם ), ההופכת את סדר הרשימה (האיבר הראשון ייהפוך להיות האיבר האחרון, האיבר השני ייהפוך להיות האיבר לפני אחרון, וכולי).

תשובה[עריכה]

פסוודו-קוד והסבר[עריכה]

להלן הפסוודו-קוד לפתרון:

#Takes a singly-linked list (l) and reverses it.
Reverse(l)
1	new-front = Nil
	
2	while l.front != Nil
3		nxt = l.front.next
4		l.front.next = new-front
5		new-front = l.front
6		l.front = nxt
		
7	l.front = new-front

נתבונן ברשימה המקושרת בתרשים הבא.

  • שורה 1 מייצרת מצביע new-front המצביע לNil ‏(A)‏. מצביע זה יצביע לרשימות החוליות שכבר הפכו את סדרן.
  • כעת נעבור בלולאה 2-6, כל עוד נותרו איברים אליהם מצביע l.front. בכל איטרציה:
    • שורה 3 מייצרת מצביע nxt המצביע לl.front.next ‏(B)‏.
    • שורה 4 גורמת לl.front.next להצביע לרשימת החוליות שאליה מצביע new-front ‏(C)‏ (בתחילה זו רשימת חוליות ריקה, כמובן).
    • שורה 5 גורמת לnew-front להצביע לl.front ‏(D)‏
    • שורה 6 מקדמת את l.front לחוליה הבאה (E).
    • כלומר, כל איטרציה מעבירה חוליה מתחילת הרשימה לראש רשימת חוליות אליה מצביע new-front‏.‏ (F) מראה זאת בצורה ברורה יותר עבור האיטרציה הראשונה.
  • לאחר סיום הלולאה, שורה 7 עושה את כל מה שנותר: לגרום לl.front להצביע לחוליה הראשונה בnew-front.
100%

ניתוח סיבוכיות וזיכרון[עריכה]

קל לראות שהסיבוכיות היא :

  1. 1 ו7 הן .
  2. 3-6 הן ולכן 2-6 (כי ברור שהלולאה מתבצעת פעמים).

כמו כן השתמשנו בכמות מוגבלת של זכרון (השתמשנו בשני משתני עזר בלבד).

השוואה בין הכנסת איברים לרשימה מקושרת ומערך[עריכה]

שאלה[עריכה]

בתכנית מסוימת רוצים לקלוט מספר רב של תווים מהמשתמש ולאחסנם. ביתר פירוט: רוצים לקרוא תו-תו מהמקלדת, עד שנלחץ התו 'q', ולשמור כל תו במבנה נתונים כלשהו. הבעיה היא שמספר התווים אינו ידוע מראש.

שלוש אפשרויות נבחנות. עבור כל אחד מהפתרונות, אנא אנא מצא את סדר הגדילה שלו, והסבר במילים מתי תשתמש בו (אם בכלל).

א'[עריכה]

שימוש ברשימה מקושרת:

1	l = Make-List()
	
2	do
3		c = Read()
4		if c != 'q'
5			Insert-Back(l, c)
6	while c != 'q'

הקוד פשוט למדי. 1 מייצרת רשימה מקושרת. הלולאה 2-6 קוראת תווים כל עוד לא נלחץ 'q', ומכניסה תווים (למעט 'q') לסוף הרשימה.


ב'[עריכה]

שימוש במערך גדל ב1:

1	A = Make-Array(1)
2	used = 0
	
3	do
4		c = Read()
5		if c != 'q'
6			A[++used] = c
			
7			if used == Length(A)
8				Tmp = Make-Array(used + 1)
				
9				for j in [1, ..., used]
10					Tmp[j] = A[j]
	
11				A = Tmp
12	while c != 'q'

1 מייצרת מערך בגודל 1.‏ 2 מאתחלת משתנה used, המתאר כמה איברים בשימוש בְמערך A,‏ ל1.‏ 3-12 קוראת תווים כל עוד לא נלחץ 'q', ומכניסה תווים (למעט 'q') לסוף המערך. 7-11 מטפלות במקרה בו נגמר המקום במערך A.‏ 8 מייצרת מערך חדש Tmp, שארכו גדול ב1 מזה של A.‏ 9-10 מעתיקות את האיברים למערך החדש. 11 משימה את המערך החדש לA במקום הקודם. ביציאה מהלולאה, A[1, ..., used] יחזיק את האיברים שנקלטו.

ג'[עריכה]

שימוש במערך גדל פי 2:

1	A = Make-Array(1)
2	used = 0
	
3	do
4		c = Read()
5		if c != 'q'
6			A[++used] = c
			
7			if used == Length(A)
8				Tmp = Make-Array(used * 2)
				
9				for j in [1, ..., used]
10					Tmp[j] = A[j]
	
11				A = Tmp
12	while c != 'q'

שים לב להבדל בין פתרון זה לפתרון הקודם. 8 אינה מגדילה את המערך החדש ב1 כמקודם, אלא פי 2.

תשובה[עריכה]

נניח שמספר האיברים בקלט הוא .

א'[עריכה]

כל קריאה לInsert-Back של רשימה מקושרת היא , ולכן סיבוכיות הלולאה היא .

פתרון זה יעיל הן בזמן הריצה והן בזכרון מבחינת סדרי גדילה, מפני שהן זמן הריצה והן דרישת הזכרון לינאריים במספר האיברים. עם זאת, קבועי זמן הריצה ודרישת הזכרון גבוהים למדי. לדוגמה, בגלל המצביעים בחוליות הרשימה המקושרת, כמות הזכרון שתדרש עבור עבור שמירת כל תו תהיה לפחות פי שלושה מכמות הזכרון המינימלית לשמירת תו.

ב'[עריכה]

נתבונן באיטרציה ה של הלולאה 3-12. בהכרח תופעל הלולאה הפנימית 9-10, וסיבוכיותה לינארית ב. זמן הריצה הוא לכן .

הפתרון אינו יעיל מבחינת זמן ריצה, אך הוא חסכוני מאד (בצורה קיצונית, אפילו) בדרישת הזכרון שלו.

ג'[עריכה]

נתבונן באיטרציה ה של הלולאה 3-12. הלולאה הפנימית 9-10 תופעל אמ"ם חזקה של 2, וסיבוכיותה לינארית ב. אם הוא מספר הפעמים שהופעלה הלולאה הפנימית, אז קל לראות שמתקיים .

זמן הריצה הוא לכן .

הפתרון יעיל מבחינת זמן הריצה הכולל, וסביר מבחינת דרישת הזכרון שלו (הנמצאת בין אלו של שני הפתרונות הקודמים). נשים לב שלמרות שזמן הריצה הכולל הוא לינארי (כבפתרון 1), זמן הריצה של איטרציה בודדת אינו (בנגוד לפתרון 1). המשתמש עלול להמתין זמן רב לפני מספר הקשות אם פתרון זה בשימוש.