מאגר טיפים להוראת עיצוב תכנה

עבודה ישירה עם מצביעים

דורון זוהר ואיריס ברגורי, אהל שם, רמת גן

 

בטיפוס הנתונים רשימה העבודה עם הייצוג בסביבת העבודה עם מצביעים קשה מאוד לתלמידים.

הדוגמא הבאה דורשת מן התלמידים לעבוד ישירות עם מצביעים ולהתעלם מהערך.

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

 

נממש תור ע"י רשימה מעגלית q חד-כיוונית עם עוגן המצביע לאחד מאיברי הרשימה.

למשל, תור בן 5 איברים יראה כך:

 

ידוע שפעולת  queue-remove(q)  מומשה ע"י הפקודה:

q.anchor ^ next ^ next := q.anchor ^ next ^ . next ^ next

 

א.       מה ערכו של האיבר בראש התור? מה ערכו של האיבר בסוף התור?

ב.       מה מבצעת הפרוצדורה הבאה: (לא איך, מה!)

procedure Who-am-I (q:                       ; x:                   );

{הפעולה מקבלת כפרמטר      מטיפוס                             ו-      מטיפוס                                          }

{                                                                      ו }

begin

   new(p);

   p^.info := x;

   if queue-empty(q) then q.anchor: = p

      else  p^.next := q.anchor^.next^.next ;

   q.anchor^.next^.next := p ;

   q.anchor^.next := q.anchor^.next^.next ;

end;

ג.        מהו אורך הקלט לפיו תמדד סיבוכיות זמן הריצה של הפרוצדורה?                    
מהי סיבוכיות זמן הריצה של הפרוצדורה?              
נמק!                                                                 

ד.       נגדיר תור ישראלי כתור שבו איברים יכולים להיכנס גם לראש התור.
כתוב פרוצדורה בשם 
insert-head (q, x)  המקבלת את התור q ומספר שלם  x ומכניסה את  x  לראש התור.
מהי סיבוכיות זמן הריצה של הפרוצדורה?

ה.      נגדיר תור פולני כתור שבו איברים יכולים לצאת גם מסוף התור. (נמאס לחכות)
כתוב פרוצדורה בשם 
remove-tail (q)  המקבלת את התור q ומוציאה את האיבר שנמצא בסוף התור.

       מהי סיבוכיות זמן הריצה של הפרוצדורה?

 

טיפ נוסף:

לצורך עבודה יעילה ברשימות נוסיף לממשק רשימה את הפעולה

הוצא-אחרי-מרשימה  (list:list-type; pos:pos-type)

הפעולה מוציאה מהרשימה list את האיבר שאחרי האיבר שבמקום  pos.

הפעולה אינה דורשת שימוש ב- קודם-ברשימה(list:list-type; pos:pos-type)

ועל כן אינה אורכת O(n) כי אם  O(1)

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

 

לאתר עיצוב תכנה

למאגר טיפים בעיצוב תכנה

חזרה