מבני נתונים
מבנה
נתונים זהו שם כולל לשיטות שמירת אוסף נתונים שנרצה נגישות אליהם על מחשב. העיקרון העומד מאחורי מבני נתונים הוא יצירת מסגרת מסודרת שתכיל את כל הנתונים הרצויים, ושיטת שליפה נוחה של הנתונים. המבנה ושיטת השליפה יתאימו לסוג המידע, כמות הנתונים ואופן העבודה איתם. כך למשל, שימוש במבנה נתונים לשמירת ספר וטלפונים יהיה שונה משימוש במבנה נתונים לשמירת לוח זמנים יומי של שדה תעופה. לספר טלפונים דרוש הכנסת נתונים רבים, שנשארים יחסית קבועים, ויכולת חיפוש מהירה בין כמות גדולה של נתונים, ועל פי קריטריונים שונים. לעומת זאת, בלוח זמנים יש כמות קטנה של
מידע, אותו יש צורך לשנות בפרקי זמן קצרים (מחיקת טיסות שנחתו, הוספת טיסות חדשות, עדכון איחורים וכו'). קיימים מספר רב של
מבנה נתונים, אשר לכל אחד היתרונות והחסרונות שלו, ולכל אחד ייעוד אחר. המבנים עליהם אעבור כאן: מערכים, תורים, מחסניות, ועצים.
מערכים: אלה הם מבני נתונים פשוטים יחסית, אשר בנויים כטבלאות. כל נתון בעצם ירשם בתא מסוים במערך וישויך אליו מספר התא. גישה לנתון תתבצע על ידי בקשה לקבלת המידע בתא מספר X.
מערך יכול להיות חד-מימדי, דו-מימדי או יותר, כאשר הכוונה במימד היא שיטת המספור של כל תא. למשל, במערך חד-מימדי, כל תא מקבל מספר. במערך דו-מימדי, כל תא מקבל מספר טור ומספר שורה (כמו טבלה). במערך תלת-מימדי יוסף גם "עומק" לטבלה, וכך הלאה.
יתרונות: מבנה מאוד פשוט, כאשר לכל נתון יש מקום מאוד ברור בטבלה, וניתן לגשת לכל נתון פשוט על ידי ידיעה באיזה מספר תא הוא נמצא. הרחבה של המערך להוספת נתונים חדשים היא פשוטה יחסית.
חסרונות: המבנה לא מסודר בצורה טובה, ולכן לא בנוי לחיפושים. אם מספר התא של המידע הרצוי אינו ידוע, לרוב יש לבצע חיפוש על כל המערך עד שהערך נמצא – דבר שהוא מאוד בעייתי כשמדובר בכמות גדולה מאוד של נתונים. בנוסף, הוספת נתונים לאמצע המערך, או מחיקת נתונים דורש התעסקות רבה וגורר שינוי בחלק גדול מהמערך.
תורים: מבני נתונים אשר, כשמם, בנויים בצורת
תור, ומיועד לפעולות מאוד ספציפיות. לכל נתון יש מקום בתור, לפי זמן הכנסתו לתור, ושליפת הנתונים נעשית בצורת "FIFO" – first in, first out (הראשון שמוכנס הוא הראשון שיוצא). זהו מבנה שמיועד לשמור על אוסף סדור של נתונים, כמו למשל רשימת משימות למחשב – במחשב יבצע משימות בזו אחר זו, על פי הסדר שהן הוכנסו לו לתור המשימות, וכל משימה חדשה תתווסף לסוף התור ותחכה לביצוע.
יתרונות: הכנסת נתונים והוצאת נתונים פשוטה, וקל מאוד לתחזוקה.
חסרונות: בדומה למערך, המבנה לא בנוי לחיפושים מורכבים. בנוסף, יותר מסובך לגשת לנתונים שלא לפי הסדר המוגדר שלהם.
מחסניות: מבנה נתונים זה, בדומה לתור, גם כן מיועד למטרות מאוד ספציפיות. אך בניגוד לתור, עובד בשיטת "FILO" – first in, last out (האחרון שמוכנס הוא הראשון שיוצא), בדומה למחסנית של אקדח. ממלאים את המחסנית בנתונים, כאשר הנתון האחרון שהוכנס נמצא "למעלה", והוא זה שנגיש לך. דוגמא לשימוש במחסנית היא במעבד תמלילים, כאשר משתמשים בפקודת "בטל". כל אות שמוקלדת נכנסת למחסנית של מעבד תמלילים, וכאשר לוחצים ctrl+z (בטל), הפעולה האחרונה שעשית מתבטלת ונזרקת מהמחסנית. לחיצה נוספת על בטל, תעיף מהמחסנית את האות שהוקלדה לפני כן, וכך הלאה עד שהמחסנית מתרוקנת מנתונים. למחסנית אותן יתרונות וחסרונות כמו לתור.
עצים: כפי שניתן לראות, שמותיהם של מבני נתונים הינם מאוד ציוריים. מבנה נתונים מסוג
עץ, הינו מבנה שבו הנתונים נשמרים כמו עלים שמחוברים לענפים של העץ. כדי למצוא על מסוים, עלייך רק לדעת אלו ענפים מובילים אליו. מבנה של עץ הינו מאוד יעיל כאשר רוצים לסדר נתונים בצורה שיעילה לחיפוש. מתחילים מגזע העץ (אשר בדרך כלל נקרא "שורש"), וכל פיצול של ענף מוביל לקבוצה מסוימת של נתונים. כך ממשיכים לאורך כל הפיצולים והענפים, עד שמגיעים לעלה הרצוי. דוגמא לשימוש בעץ הוא
רשימה שמית. כאשר רוצים למצוא אדם ברשימה בשם "אורן", מתחילים לחפש בפיצול של האות א'. תחת האות א' ממשיכים לפיצול של האות ו', וכך עד שמגיעים ל-"א' – ו' – ר'". כעת יהיו מספר פיצולים נוספים (למשל לשמות שמתחילים ב-אורל), אך על הענף "אור" יהיו גם העלים "אורי", "אורן", ו-"אורה".
יתרונות: מבנה מסודר שמאוד נוח לחיפושים היררכיים.
חסרונות: עצים מאוד עמוקים (הרבה תתי קבוצות ומעט עלים) ידרשו זמן רב לחיפוש, וחייבים לסרוק את כל המסלול בעץ עד לנתון הרצוי, גם אם יודעים את מקומו המדויק. בנוסף, הבנייה והתחזוקה של מבנה כזה מאוכל הכנסת נתון חדש יש לבצע חיפוש של מיקומו בעץ, ולהכניסו בלי הריסת הסדר הקיים) קיימים מבני נתונים נוספים, כגון טבלאות HASH, רשימות, גרפים ועוד, כאשר בחירת מבנה הנתונים המתאים נעשית, כפי שנאמר, על פי כמות הנתונים ואופן העבודה איתם.
סקירות נוספות אודות מבני נתונים