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

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

שאלה

אנא כתוב מימוש יעיל לפונקציה 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

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

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

תשובה

פסוודו-קוד והסבר

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

#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%

ניתוח סיבוכיות וזיכרון

קל לראות שהסיבוכיות היא $\displaystyle \Theta (n)$:

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

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

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

שאלה

בתכנית מסוימת רוצים לקלוט מספר רב של תווים מהמשתמש ולאחסנם. ביתר פירוט: רוצים לקרוא תו-תו מהמקלדת, עד שנלחץ התו '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.

תשובה

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

א'

כל קריאה לInsert-Back של רשימה מקושרת היא $\displaystyle O(1)$, ולכן סיבוכיות הלולאה היא $\displaystyle \Theta (n)$.

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

ב'

נתבונן באיטרציה ה$\displaystyle i$ של הלולאה 3-12. בהכרח תופעל הלולאה הפנימית 9-10, וסיבוכיותה לינארית ב$\displaystyle i$. זמן הריצה הוא לכן $\displaystyle \sum _{i=1}^{n}[\Theta (i)]=\Theta (n^{2})$.

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

ג'

נתבונן באיטרציה ה$\displaystyle i$ של הלולאה 3-12. הלולאה הפנימית 9-10 תופעל אמ"ם $\displaystyle i$ חזקה של 2, וסיבוכיותה לינארית ב$\displaystyle i$. אם $\displaystyle h$ הוא מספר הפעמים שהופעלה הלולאה הפנימית, אז קל לראות שמתקיים $\displaystyle h=\log(n)\pm O(1)$.

זמן הריצה הוא לכן $\displaystyle \sum _{i=1}^{h}[\Theta (i)]=\sum _{j=1}^{\log(n)\pm O(1)}[\Theta (2^{j})]=\Theta (2^{\log(n)\pm O(1)})=\Theta (n)$.

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