מבני נתונים לבגרות - הסבר מלא

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

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

מחסנית (Stack) - LIFO

מחסנית פועלת לפי עקרון LIFO (Last In, First Out): האיבר האחרון שהוכנס הוא הראשון שיוצא, כמו ערימת צלחות. הממשק הבסיסי:

• push(x) - הכנסת איבר לראש המחסנית.
• pop() - הוצאת האיבר העליון והחזרתו.
• top() - הצצה לאיבר העליון בלי להוציאו.
• isEmpty() - בדיקה אם המחסנית ריקה.

מתי מחסנית מתאימה? כשצריך להפוך סדר או "לזכור" משהו ולחזור אליו בסדר הפוך - למשל בדיקת איזון סוגריים או היפוך סדר של רצף.

תור (Queue) - FIFO

תור פועל לפי עקרון FIFO (First In, First Out): מי שנכנס ראשון יוצא ראשון, בדיוק כמו תור בקופה. הממשק:

• insert(x) - הכנסת איבר לסוף התור.
• remove() - הוצאת האיבר הראשון והחזרתו.
• isEmpty() - בדיקה אם התור ריק.

תור מתאים כשרוצים לשמר את סדר ההגעה של הנתונים. שאלות מאתגרות לעיתים משלבות תור ומחסנית באותה שאלה, כדי לבחון אם הבנתם את ההבדל בין FIFO ל-LIFO.

רשימה מקושרת (Linked List)

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

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

עצים בינאריים (Binary Trees)

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

• סריקות העץ: preorder, inorder ו-postorder.
• חישוב תכונות: גובה, מספר עלים, סכום ערכים.
• עץ חיפוש בינארי: חיפוש והוספה לפי החוקיות שבה הערכים מסודרים.

מימוש מבני נתונים

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

איך לתרגל את כל זה

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