פורסם 2006 בנובמבר 2719 שנים במסגרת הקורס באוניברסיטה נתנו לנו את השאלה הזאת:יש לשמור קבוצה דינמית של איברים, כאשר כל איבר מכיל :שם, מספר זהות ופרטים נוספים.יש לתמוך בפעולות הבאות: הכנסה, מחיקה לפי מספר זהות, חיפוש לפי שם.תאר מבנה נתונים יעיל למימוש הפעולות הללו.חשבתי על שימוש ב-MAP, אבל MAP ממיין ומכניס איברים לפי מפתח אחד שבוצע עליו HASHCODE.השאלה שלי היא האם יש מבנה דומה לMAP שיכול למיין לפי 2 מפתחות?תודה מראש,אביעד
פורסם 2006 בנובמבר 2719 שנים יש לך טעות. Map, כ- ADT - לא ממיין. הוא רק מאפשר שליפות לפי מפתח.אתה יכול להחזיק שני Maps. באחד ה- key זה השם, ובשני ה- key זה מספר ת"ז.בהכנסה - אתה מכניס לשני ה- maps.במחיקה - אתה מחפש ב- map השני, מוצא את השם, מחפש אותו ב- map הראשון, ומוחק את שניהם.
פורסם 2006 בנובמבר 2719 שנים אתה יכול להשתמש בשני map-ים, אחד עם ת.ז כמפתחות ואחד עם השם כמפתח. כשאתה מבצע הכנסה אתה מכניס את האובייקט לשני ה הmap-ים.עריכה: בדיוק כשהגבתי גם Boomerang הציע את אותו הפתרון.
פורסם 2006 בנובמבר 2719 שנים מחבר נכון, התכוונתי מאפשר שליפות לפי מפתח ולא מיון. טעות שלי.הבנתי את הרעיון שלכם, ואני אראה איך אני מממש אותו.בכל מקרה, הסיבוכיות נשארת (O(1 נכון?
פורסם 2006 בנובמבר 2719 שנים בכל מקרה, הסיבוכיות נשארת (O(1 נכון?כן, בתנאי שחישוב ה- Hash הוא (O(1 ומספר ה- hash collisions שלך חסום ע"י קבוע.
פורסם 2006 בנובמבר 2719 שנים מחבר חישוב ההאש יהיה ללא תלות במספר האיברים,hash collisions - לא זוכר שנתקלתי במושג הזה, תוכל לפרט קצת?
פורסם 2006 בנובמבר 2719 שנים מדובר באיברים שמתמפים לאותו מס' (תא) ע"י פונקצית ההאש.התנגשויות נפתרות ע"י עץ אדום שחור בתאים שמחזיר ערך בזמן logN
פורסם 2006 בנובמבר 2719 שנים מחבר תודה רבה לכם על העזרה,אני יותר מאוחר אתחיל לממש את זה ואם יהיו לי בעיות אני אתיעץ איתכם.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.