מבני נתונים ומבוא לאלגוריתמים

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

מבוא למבני נתונים לינאריים

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

מערכים (Arrays)

הכרות עם מערכים

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

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

יתרונות:
- גישה ישירה (Random Access): גישה לאיבר כלשהו במערך מתבצעת בזמן קבוע (O(1)), ללא תלות בגודל המערך, באמצעות חישוב כתובת הזיכרון שלו.
- יעילות בזיכרון: אין תקורה של מצביעים (כמו ברשימות מקושרות).
- עקרונות זיכרון מטמון: בשל רציפות הזיכרון, מערכים מנצלים היטב את זיכרון המטמון (cache) של המעבד, מה שמשפר את הביצועים.
חסרונות:
- גודל קבוע: גודל המערך נקבע בזמן יצירתו ואינו ניתן לשינוי בקלות. שינוי גודל דורש הקצאה מחדש והעתקת כל האיברים, פעולה יקרה (O(N)).
- הכנסה והסרה: הכנסת איבר או הסרתו באמצע המערך דורשת הזזה של כל האיברים שאחריו, פעולה בעלת מורכבות זמן O(N).

רשימות מקושרות (Linked Lists)

הכרות עם רשימות מקושרות

רשימה מקושרת (Linked List): מבנה נתונים לינארי המורכב מסדרה של "צמתים" (Nodes), כאשר כל צומת מכיל נתון ומצביע (או קישור) לצומת הבא ברשימה.

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

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

מחסניות (Stacks) ותורים (Queues)

מחסניות ותורים הם מבני נתונים מופשטים (ADTs - Abstract Data Types) המגדירים סט פעולות על אוסף של איברים, אך אינם מכתיבים את אופן המימוש הפנימי. ניתן לממש אותם באמצעות מערכים או רשימות מקושרות, כאשר לכל מימוש יתרונות וחסרונות משלו.

מחסנית (Stack)

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

ניתן לדמיין מחסנית כערימת צלחות: הצלחת האחרונה שהונחה היא הראשונה שתילקח.

פעולות עיקריות:
- Push(item): מוסיף איבר לראש המחסנית.
- Pop(): מסיר ומחזיר את האיבר שבראש המחסנית.
- Peek(): מחזיר את האיבר שבראש המחסנית מבלי להסירו.
- IsEmpty(): בודק אם המחסנית ריקה.
יישומים: ניהול קריאות לפונקציות (Call Stack), מנגנוני "בטל" (Undo), הערכת ביטויים אלגבריים, בדיקת סוגריים.

תור (Queue)

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

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

פעולות עיקריות:
- Enqueue(item): מוסיף איבר לסוף התור.
- Dequeue(): מסיר ומחזיר את האיבר שבראש התור.
- Peek(): מחזיר את האיבר שבראש התור מבלי להסירו.
- IsEmpty(): בודק אם התור ריק.
יישומים: ניהול משימות במערכות הפעלה (Task Scheduling), תורי הדפסה, תורי הודעות, אלגוריתם חיפוש לרוחב (BFS).

בחירת מימוש למחסניות ותורים: מערך מול רשימה מקושרת: נושא זה קריטי לבחינה ומשקף הבנה עמוקה של מבני הנתונים. השאלה הנפוצה היא מתי לבחור במימוש מבוסס מערך ומתי ברשימה מקושרת. הדגש הוא על ניתוח מורכבות זמן ומקום של הפעולות העיקריות (Push/Pop, Enqueue/Dequeue) בכל אחד מהמימושים, תוך התחשבות במגבלות המערכת (לדוגמה, זיכרון קבוע מראש מול גודל דינמי).

שאלות לדיון

הסבירו מתי תעדיפו להשתמש במערך על פני רשימה מקושרת, ומתי ההפך. תנו דוגמאות קונקרטיות ממערכות צבאיות או אזרחיות.
כיצד הייתם מממשים מחסנית (Stack) באמצעות מערך? מהן מגבלות הגישה? ומהי מורכבות הזמן של פעולות Push ו-Pop במימוש זה?
תארו מצב בו תור (Queue) עשוי להיות מבנה הנתונים המתאים ביותר לניהול משימות במערכת זמן אמת. נמקו את בחירתכם תוך התייחסות לעקרון הפעולה של התור.
השוו בין מורכבות הזמן והמקום של מימוש תור באמצעות מערך "מעגלי" לבין מימוש באמצעות רשימה מקושרת. מתי כל אחד מהם עדיף?

נקודות לתשובת מודל

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

העדפה למערך:
- כאשר גודל הנתונים ידוע מראש או משתנה לעיתים רחוקות.
- כאשר נדרשת גישה מהירה לאיברים לפי אינדקס (O(1)).
- כאשר יעילות בזיכרון ותמיכה ב-cache memory חשובות.
- דוגמאות: טבלת ניתוב קבועה במערכת תקשורת, מאגר נתונים קטן וסטטי של חיישנים, רשימת קודים סודיים באורך קבוע.
העדפה לרשימה מקושרת:
- כאשר גודל הנתונים משתנה לעיתים קרובות ואינו ידוע מראש.
- כאשר נדרשות פעולות הכנסה והסרה תכופות ויעילות (O(1) לאחר איתור).
- כאשר אין צורך בגישה ישירה לאיברים לפי אינדקס.
- דוגמאות: רשימת משימות דינמית במערכת הפעלה, יומן אירועים (Log) שגדל ללא הגבלה, רשימת כלי רכב במעקב שמיקומם משתנה תדיר.
השוואה ונימוק: הדגשת ה-trade-offs בין מורכבות זמן (לפעולות שונות) למורכבות מקום, והתאמתם לדרישות המערכת הספציפית.

מצאתם טעות או שחסר משהו?