הדרך להפוך למתכנת מיומן ומצליח היא קשה, אבל בהחלט ברת השגה. מבני נתונים הם מרכיב ליבה שכל סטודנט לתכנות חייב לשלוט בו, ורוב הסיכויים שאולי כבר למדת או עבדת עם כמה מבני נתונים בסיסיים כגון מערכים או רשימות.
מראיינים נוטים להעדיף לשאול שאלות הקשורות למבני נתונים, כך שאם אתה מתכונן לראיון עבודה, תצטרך לרענן את הידע שלך במבני הנתונים. המשך לקרוא כאשר אנו מפרטים את מבני הנתונים החשובים ביותר עבור מתכנתים וראיונות עבודה.
רשימות מקושרות הן אחד ממבני הנתונים הבסיסיים ביותר ולעיתים קרובות נקודת המוצא של סטודנטים ברוב הקורסים של מבני נתונים. רשימות מקושרות הן מבני נתונים ליניאריים המאפשרים גישה רציפה לנתונים.
אלמנטים בתוך הרשימה המקושרת מאוחסנים בצמתים בודדים המחוברים (מקושרים) באמצעות מצביעים. אתה יכול לחשוב על רשימה מקושרת כעל שרשרת של צמתים המחוברים זה לזה באמצעות מצביעים שונים.
קָשׁוּר: מבוא לשימוש ברשימות מקושרות ב-Java
לפני שניכנס לפרטים הספציפיים של הסוגים השונים של רשימות מקושרות, חשוב להבין את המבנה והיישום של הצומת הבודד. לכל צומת ברשימה מקושרת יש לפחות מצביע אחד (לצמתי רשימה מקושרת כפולה יש שני מצביעים) המחבר אותו לצומת הבא ברשימה ולפריט הנתונים עצמו.
לכל רשימה מקושרת יש צומת ראש וזנב. לצמתי רשימה מקושרת יחידה יש רק מצביע אחד שמצביע על הצומת הבא בשרשרת. בנוסף למצביע הבא, לצמתי רשימה כפולה יש מצביע נוסף המצביע על הצומת הקודם בשרשרת.
שאלות ראיון הקשורות לרשימות מקושרות סובבות בדרך כלל סביב הכנסה, חיפוש או מחיקה של אלמנט מסוים. הוספה לרשימה מקושרת לוקחת זמן O(1), אך מחיקה וחיפוש עלולים לקחת זמן O(n) במקרה הגרוע. אז רשימות מקושרות אינן אידיאליות.
2. עץ בינארי
עצים בינאריים הם תת-הקבוצה הפופולרית ביותר של מבנה הנתונים של משפחת העצים; אלמנטים בעץ בינארי מסודרים בהיררכיה. סוגים אחרים של עצים כוללים עצי AVL, אדום-שחור, עצי B וכו'. צמתים של העץ הבינארי מכילים את אלמנט הנתונים ושני מצביעים לכל צומת צאצא.
לכל צומת אב בעץ בינארי יכולים להיות לכל היותר שני צמתים צאצאים, וכל צומת צאצא, בתורו, יכול להיות הורה לשני צמתים.
קָשׁוּר: מדריך למתחילים לעצים בינאריים
עץ חיפוש בינארי (BST) מאחסן נתונים בסדר ממוין, כאשר אלמנטים עם ערך מפתח קטן מהאב הצומת מאוחסנים בצד שמאל, ואלמנטים עם ערך מפתח גדול יותר מהצומת האב מאוחסנים ב- ימין.
עצים בינאריים נפוצים בראיונות, כך שאם אתם מתכוננים לראיון, כדאי שתדעו איך לשטח עץ בינארי, לחפש אלמנט ספציפי ועוד.
3. טבלת גיבוב
טבלאות Hash או מפות Hash הן מבנה נתונים יעיל ביותר המאחסן נתונים בפורמט מערך. לכל רכיב נתונים מוקצה ערך אינדקס ייחודי בטבלת hash, המאפשרת חיפוש ומחיקה יעילים.
תהליך הקצאה או מיפוי של מפתחות במפת hash נקרא hashing. ככל שפונקציית הגיבוב יעילה יותר, כך היעילות של טבלת הגיבוב עצמה טובה יותר.
כל טבלת Hash מאחסנת רכיבי נתונים בצמד ערך-אינדקס.
כאשר ערך הוא הנתונים שיש לאחסן, ואינדקס הוא המספר השלם הייחודי המשמש למיפוי האלמנט לטבלה. פונקציות הגיבוב יכולות להיות מאוד מורכבות או פשוטות מאוד, תלוי ביעילות הנדרשת של טבלת הגיבוב ובאופן שבו תפתרו התנגשויות.
התנגשויות מתעוררות לעתים קרובות כאשר פונקציית Hash מייצרת מיפוי זהה עבור אלמנטים שונים; ניתן לפתור התנגשויות במפות חשיש בדרכים שונות, באמצעות כתובת פתוחה או שרשור.
לטבלאות Hash או מפות Hash יש מגוון יישומים שונים, כולל קריפטוגרפיה. הם מבנה הנתונים הבחירה הראשון כאשר נדרשת הכנסה או חיפוש בזמן O(1) קבוע.
4. ערימות
ערימות הן אחד ממבני הנתונים הפשוטים יותר ודי קל לשלוט בהם. מבנה נתונים מחסנית הוא בעצם כל מחסנית מהחיים האמיתיים (תחשוב על ערימה של קופסאות או צלחות) ופועל בצורה LIFO (Last In First Out).
מאפיין LIFO של Stacks אומר שהרכיב שהכנסת אחרון יקבל גישה ראשונה. אתה לא יכול לגשת לאלמנטים מתחת לאלמנט העליון בערימה מבלי להקפיץ את האלמנטים שמעליו.
לערימות יש שתי פעולות עיקריות - דחיפה ופופ. Push משמש להכנסת אלמנט לערימה, ו-Pop מסיר את האלמנט העליון מהערימה.
יש להם גם שפע של יישומים שימושיים, אז זה נפוץ מאוד שמראיינים שואלים שאלות הקשורות ל-stacks. לדעת איך להפוך מחסנית ולהעריך ביטויים זה די חיוני.
5. תורים
תורים דומים ל-stacks אבל פועלים באופן FIFO (First In First Out), כלומר אתה יכול לגשת לאלמנטים שהכנסת קודם לכן. ניתן להמחיש את מבנה נתוני התור ככל תור אמיתי, שבו אנשים ממוקמים על סמך סדר ההגעה שלהם.
פעולת הכנסת תור נקראת enqueue, ומחיקה/הסרה של אלמנט מתחילת התור מכונה ביטול תור.
קָשׁוּר: מדריך למתחילים להבנת תורים ותורים עדיפות
תורי עדיפות הם יישום אינטגרלי של תורים ביישומים חיוניים רבים כגון תזמון CPU. בתור עדיפות, אלמנטים מסודרים לפי העדיפות שלהם ולא לפי סדר ההגעה.
6. ערימות
ערמות הן סוג של עץ בינארי שבו צמתים מסודרים בסדר עולה או יורד. בערימה Min, ערך המפתח של האב שווה או קטן מזה של הילדים שלו, וצומת השורש מכיל את הערך המינימלי של הערימה כולה.
באופן דומה, צומת השורש של Max Heap מכיל את ערך המפתח המרבי של הערימה; עליך לשמור על מאפיין הערימה המינימלית/מקסימלית לאורך הערימה.
קָשׁוּר: ערימות לעומת ערימות: מה מייחד אותם?
לערמות יש שפע של יישומים בשל אופיים היעיל מאוד; בעיקר, תורי עדיפות מיושמים לעתים קרובות דרך ערימות. הם גם מרכיב ליבה באלגוריתמים של heapsort.
למד מבני נתונים
מבני נתונים יכולים להיראות מזעזעים בהתחלה אבל מקדישים מספיק זמן, ותמצא אותם קלים כמו עוגה.
הם חלק חיוני בתכנות, וכמעט כל פרויקט ידרוש ממך להשתמש בהם. לדעת מהו מבנה הנתונים האידיאלי עבור תרחיש נתון הוא קריטי.
אלגוריתמים אלו חיוניים לזרימת העבודה של כל מתכנת.
קרא הבא
- תִכנוּת
- ניתוח נתונים
- טיפים לקידוד
פאהד הוא כותב ב-MakeUseOf וכיום מתמחה במדעי המחשב. ככותב טכנולוגיה נלהב הוא דואג שהוא יישאר מעודכן בטכנולוגיה העדכנית ביותר. הוא מוצא את עצמו מתעניין במיוחד בכדורגל ובטכנולוגיה.
הירשם לניוזלטר שלנו
הצטרף לניוזלטר שלנו לקבלת טיפים טכניים, ביקורות, ספרים אלקטרוניים בחינם ומבצעים בלעדיים!
לחץ כאן כדי להירשם
