תכנות מתקדם ב-Java/מבני נתונים מתקדמים: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Johnny Zoo (שיחה | תרומות)
אין תקציר עריכה
Johnny Zoo (שיחה | תרומות)
שורה 74:
 
המימוש של תורים ומחסניות אינו קבוע. התנאי הוא שכל מימוש חייב ליישם את הממשק שפורט למעלה (הכנסת איבר וכדומה). מימוש נפוץ הוא בעזרת רשימה מקושרת.
 
 
===עצים בינאריים===
שורה 100 ⟵ 99:
 
===טבלת גיבוב===
[[w:he:טבלת גיבוב|טבלת גיבוב]] (Hash Table) היא מבנה נתונים המאפשר הכנסה ושליפה מהירה של נתונים, באופן הדומה למערך: עבור כל נתון (גם נתון שלא נמצא בטבלה) קיים מספר סידורי ידוע, אליו נכניס את הנתון, ואם נרצה לשלוף אותו - נדע ששם הוא צריך להיות. מסיבה זו, לפעמים מכונה טבלת גיבוב גם "מערך אסוציאיטיבי".
חלק קריטי בשימוש בטבלה כזו הוא מציאת הדרך בעזרתה נדע לחשב את אותו מספר סידורי עבור כל נתון. לשם כך, משתמשים בפונקציה מתמטית בשם "[[w:he:פונקציית גיבוב|פונקציית גיבוב]]", שבהינתן קלט מסויים - תדע להמיר אותו למספר.
 
כאן מתעוררת בעייה נוספת: ומה אם שני נתונים שונים יקבלו מספר זהה? את הבעייה הזו אפשר לפתור באחת משתי דרכים:
* '''טבלה פתוחה''' - כאשר אנו מנסים להכניס נתון חדש לטבלה ומגלים שהמקום הרצוי (כלומר, המקום שאת מספרו מצאה פונקציית הגיבוב) כבר תפוס, נמשיך לתאים הבאים עד שנמצא תא פנוי ובו נמקם את הנתון. כאשר נרצה לחפש נתון, נתחיל במקום בטבלה אליו תפנה פונקציית הגיבוב ונבדוק אם האיבר שרצינו למצוא נמצא שם. אם התא תפוס אך האיבר שלנו לא שם - נמשיך הלאה עד שנמצא אותו (או עד שנגיע לתא ריק ונוכל לדעת שהוא לא נמצא).
* '''טבלה סגורה''' - בטבלה סגורה אנו משתמשים ברשימות מקושרות: בכל מקום בטבלה תהייה רשימה מקושרת. כאשר מכניסים איבר חדש, מכניסים אותו לסוף הרשימה (שנמצאת במקום אליו הפנתה אותנו פונקציית הגיבוב). כאשר שולפים איבר, פונים לרשימה שנמצאת במקום הרצוי ועוברים עליה עד שמוצאים את שחיפשנו (או עד שהרשימה נגמרה והאיבר לא נמצא).
כמו תמיד, יש יתרונות וחסרונות בכל אחת מהשיטות האלו.
 
 
===מבנים נוספים===