מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/רשימות מקושרות/תרגילים/ניתוח אמורטייזד להכנסת איברים/שאלה

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