יום שישי, 6 בספטמבר 2013













1
מרכז המורים הארצי
פורום מורי מדעי המחשב בחט"ב
נספח – ממשקים - #C
ממשק החוליה של שלמים IntNode
המחלקה מגדירה חוליה של שלם
הפעולה בונה חוליה. הערך של החוליה הוא x, ואין
לה חוליה עוקבת
IntNode (int x)
הפעולה בונה חוליה. הערך של החוליה
הוא xוהחוליה העוקבת לה היא next. ערכו
של nextיכול להיות null
IntNode (int x ,IntNode next)
הפעולה מחזירה את הערך של החוליה ()int GetInfo
הפעולה מחזירה את החוליה העוקבת. אם אין חוליה
עוקבת, הפעולה מחזירה null
IntNode GetNext()
הפעולה משנה את הערך השמור בחוליה ל-void SetInfo (int x) x
הפעולה משנה את החוליה העוקבת ל-next. ערכו
של next יכול להיות null
void SetNext Int(Node next)
הפעולה מחזירה מחרוזת המתארת את החוליה ()string ToString
ממשק החוליה הגנרית <Node<T
המחלקה מגדירה חוליה גנרית שבה ערך מטיפוס T והפניה לחוליה העוקבת.
הפעולה בונה חוליה. הערך של החוליה הוא x, ואין
לה חוליה עוקבת
Node (T x)
הפעולה בונה חוליה. הערך של החוליה
הוא xוהחוליה העוקבת לה היא next. ערכו
של nextיכול להיות null
Node (T x, Node<T> next)
הפעולה מחזירה את הערך של החוליה ()T GetInfo
הפעולה מחזירה את החוליה העוקבת. אם אין חוליה
עוקבת, הפעולה מחזירה null
Node<T> GetNext()
הפעולה משנה את הערך השמור בחוליה ל-void SetInfo (T x) x
הפעולה משנה את החוליה העוקבת ל-next. ערכו
של next יכול להיות null
void SetNext (Node<T> next)
הפעולה מחזירה מחרוזת המתארת את החוליה ()string ToString
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה Node המופיעה בפרק 7 – ייצוג אוספים )ראו סעיף
ב.5.(.
כל הפעולות מתבצעות בסדר גודל קבוע, (O(1.2
ממשק המחלקה מחסנית <Stack<T
המחלקה מגדירה טיפוס אוסף בעל פרוטוקול LIFO להכנסה והוצאה של ערכים.
הפעולה בונה מחסנית ריקה ()Stack
הפעולה מחזירה `אמת` אם המחסנית הנוכחית ריקה, `שקר` אחרת ()bool IsEmpty
הפעולה מכניסה את הערך x לראש המחסנית הנוכחית )דחיפה( (void Push (T x
הפעולה מוציאה את הערך שבראש המחסנית הנוכחית ומחזירה
אותו )שליפה(.
הנחה: המחסנית הנוכחית אינה ריקה
T Pop()
הפעולה מחזירה את הערך שבראש המחסנית הנוכחית מבלי להוציאו.
הנחה: המחסנית הנוכחית אינה ריקה
T Top()
הפעולה מחזירה תיאור של המחסנית, כסדרה של ערכים, במבנה הזה
)x1 הוא האיבר שבראש המחסנית(:
[x1, x2, …, xn]
string ToString()
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה Stack המופיעה בפרק 8 – מחסנית ותור. המחלקה
מיוצגת בעזרת שרשרת חוליות )ראו סעיף ה.3.(.
כל הפעולות מתבצעות בסדר גודל קבוע, (O(1, למעט הפעולה ()ToString המתבצעת
בסדר גודל לינארי.
ממשק המחלקה תור <Queue<T
המחלקה מגדירה טיפוס אוסף עם פרוטוקול FIFO להכנסה והוצאה של ערכים.
הפעולה בונה תור ריק ()Queue
הפעולה מחזירה `אמת` אם התור הנוכחי ריק, ו`שקר` אחרת ()bool IsEmpty
הפעולה מכניסה את הערך x לסוף התור הנוכחי (void Insert (Tx
הפעולה מוציאה את הערך שבראש התור הנוכחי ומחזירה
אותו.
הנחה: התור הנוכחי אינו ריק
T Remove()
הפעולה מחזירה את ערכו של האיבר שבראש התור מבלי
להוציאו.
הנחה: התור הנוכחי אינו ריק
T Head()
הפעולה מחזירה מחרוזת המתארת את התור כסדרה של
ערכים, במבנה הזה )x1 הוא האיבר שבראש התור(:
[x1, x2, …, xn]
string ToString()
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה Queue המופיעה בפרק 8 – מחסנית ותור.
המחלקה מיוצגת בעזרת שרשרת חוליות והפניה לזנב התור )ראו סעיף ט.2.(.
כל הפעולות מתבצעות בסדר גודל קבוע, (O(1, למעט הפעולה ()ToString המתבצעת
בסדר גודל לינארי.3
ממשק המחלקה רשימה <List<T
המחלקה מגדירה אוסף סדרתי-לינארי, שהגישה אל ערכיו מתבצעת בכל מקום באוסף.
הפעולה בונה רשימה ריקה ()List
הפעולה מחזירה `אמת` אם הרשימה הנוכחית ריקה,
ו`שקר` אחרת
bool IsEmpty()
הפעולה מחזירה את המקום של החוליה הראשונה
ברשימה הנוכחית. אם הרשימה ריקה, הפעולה
מחזירה null
Node<T> GetFirst()
הפעולה מכניסה לרשימה הנוכחית את הערך xמקום
אחד אחרי המקום pos.
אם pos הוא x ,null יוכנס למקום הראשון ברשימה.
הפעולה מחזירה את המקום של החוליה החדשה
שהוכנסה.
הנחה: pos הוא מקום ברשימה הנוכחית או null
Node<T> Insert (Node<T> pos, T x)
הפעולה מוציאה מהרשימה הנוכחית את האיבר הנמצא
במקום pos, ומחזירה את המקום העוקב ל-pos. אם
הוצא האיבר האחרון – יוחזרnull.
הנחה: pos הוא מקום ברשימה הנוכחית ואינוnull.
Node<T> Remove (Node<T> pos)
הפעולה מחזירה תיאור של הרשימה, כסדרה של
ערכים, במבנה הזה )x1 הוא האיבר הראשון
ברשימה(:
[x1, x2, …, xn]
string ToString()
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה List המופיעה בפרק 9 – רשימה. המחלקה מיוצגת
בעזרת שרשרת חוליות )ראו סעיף ד(.
כל הפעולות מתבצעות בסדר גודל קבוע, (O(1, למעט הפעולות ()ToString ו-
(...)Remove המתבצעות בסדר גודל (O(n.
ממשק המחלקה חוליה בינרית<BinTreeNode<T
המחלקה מגדירה חוליה בינרית שבה ערך מטיפוס T ושתי הפניות לחוליות בינריות.
הפעולה בונה חוליה בינרית. ערך החוליה
הוא x וערך שתי ההפניות שלה הוא null
BinTreeNode (T x)
הפעולה בונה חוליה בינרית שערכה יהיה x.
left ו-right הן )הפניות אל( הילד השמאלי והימני
שלה. ערכי ההפניות יכולים להיות null
BinTreeNode (BinTreeNode<T> left,
T x, BinTreeNode<T>
right)
הפעולה מחזירה את הערך של החוליה ()T GetInfo4
הפעולה משנה את הערך השמור בחוליה ל-void SetInfo (Tx) x
הפעולה מחזירה את הילד השמאלי של החוליה. אם
אין ילד שמאלי הפעולה מחזירה null
BinTreeNode<T> GetLeft()
הפעולה מחזירה את הילד הימני של החוליה. אם אין
ילד ימני הפעולה מחזירה null
BinTreeNode<T> GetRight()
הפעולה מחליפה את הילד השמאלי בחוליה void SetLeft (BinTreeNode<T> left) left
הפעולה מחליפה את הילד הימני בחוליה void SetRight (BinTreeNode<T> right
right)
הפעולה מחזירה מחרוזת המתארת את הערך השמור
בחוליה
string ToString()
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה BinTreeNode המופיעה בפרק 01 – עץ בינרי
)ראו סעיף ג.2.(.
כל הפעולות מתבצעות בסדר גודל קבוע, (O(1.
ממשק המחלקה מפה <Map<V
המחלקה מגדירה אוסף דינמי הממפה מפתחות וערכים. המפתחות במפה יהיו מטיפוס
מחרוזת בעוד הערכים יהיו גנריים.
הפעולה בונה מפה ריקה ()Map
הפעולה מחזירה `אמת` אם המפתח key קיים במפה
הנוכחית ו-`שקר` אחרת
bool ContainsKey (string key)
הפעולה מחזירה את הערך הקשור למפתח key.הנחה:
המפתח קיים במפה
V GetValue (string key)
הפעולה מוסיפה למפה הנוכחית את המפתח keyואת
הערך value הקשור אליו. אם המפתח keyקיים במפה,
הפעולה מעדכנת את הערך הקשור אליו
בערך value שהתקבל
void Insert (string key, V value)
הפעולה מוציאה מהמפה הנוכחית את המפתח keyואת
הערך הקשור אליו. הפעולה מחזירה את הערך הקשור
למפתח שהוצא מהמפה.
הנחה: המפתח קיים במפה
V Remove (string key)
הפעולה מחזירה את אוסף המפתחות שקיימים במפה
הנוכחית ממוין בסדר אלפביתי עולה. אם המפה ריקה,
יוחזר מערך בגודל אפס
string[] GetAllKeys()
הפעולה מחזירה מחרוזת המתארת את המפה כך:
[key1:value1, key2:value2, key3:value3,…]
string ToString()
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה Map המופיעה בפרק 00 – מפה. המחלקה מיוצגת
בעזרת עץ-חיפוש-בינרי )ראו סעיף ד.3.(.
Map() O(1)
הממוצע במקרה O(log n)
(O(n במקרה הגרוע
bool ContainsKey (string key)
V GetValue (string key) הממוצע במקרה O(log n)5
(O(n במקרה הגרוע
הממוצע במקרה O(log n)
(O(n במקרה הגרוע
void Insert (string key, V value)
הממוצע במקרה O(log n)
(O(n במקרה הגרוע
V Remove (string key)
string[] GetAllKeys() O(n)
string ToString() O(n)
להשתלמויות במערכת ניהול המקצוע והצבת בוחנים
פרסום השתלמויות חדשות עבר למערכת הצבת הבוחנים וניהול המקצוע

אין תגובות:

הוסף רשומת תגובה