Posts Tagged ‘מבני נתונים’

מבני נתונים בתכנות – חלק א', מערך ורשימה מקושרת

הקדמה

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

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

מערך -Array

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

אז מהוא למעשה מערך? ברשותכם אשתמש בתמונה להמחשה הלקוחה מהmanual הרשמי לJAVA:

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

מיון מערך

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

מחיקת ערכים וחיפוש

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

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

מערכים רב ממדיים

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

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

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

רשימה מקושרת -Linked List

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

פה אני אסקור את מבנה הנתונים שפותר כמה מהבעיות האלו, הרשימה המקושרת, Linked List. הרשימה המקושרת היא ככל הנראה מבנה הנתונים השני בשכיחותו אחרי המערך. הרשימה המקושרת היא מבנה נתונים מבוסס מצביעים, או כפי שבשפות ללא מצביעים (C# או JAVA למשל) אוהבים לקרוא לזה, הפניות. כל עצם ברשימה כולל שני נתונים, את הinfo, כלומר המידע שיש לאותו איבר, שיכול להיות מכל סוג, מספר שלם, מחרוזת או עצם שיצרתם בעצמכם, והנתון השני הוא המצביע או ההפניה לבאיבר הבא בתור. כל איבר כזה ברשימה מכונה בדר"כ Node, כאשר למעשה הרשימה עצמה מהווה בסה"כ מצביע לNode הראשון ברשימה, ומשם זה כבר ממשיך לבד. הרשימה מסתיימת בכך שההפניה לאיבר הבא בעצם האחרון בעצם מפנה לnull. התרשים הבא מסביר את הכוונה היטב:

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

סוגי רשימות נוספים

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

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

הוספה והסרה של איברים ברשימה

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

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

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

מיון וחיפוש

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

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

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

לסיכום יתרונות וחסרונות רשימה מקושרת

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

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

סוף חלק א'

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