תכנות — שיעור 138 14/February/2011    

Hash Functions

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

Hash Tables

תרגילים

1. השלם תרגילים קודמים
2. כתוב תכנית hash-pdb-v1 שמקימת את הדרישות הבאות:
   • מממשת טבלת Hash עם פונקצית אתחול שמקבלת את גודל הטבלה כפרמטר. הכניסות בטבלה יהיו התחלות של רשימות מקושרות כפול.
   • האברים ברשימה יכילו בנוסף למצביעים
     prev, next
     מידע של: שם, מזהה-מספרי ומשקל כמו ב person.h שהוגדר בתכנית המקושרת בסכום עבר .
   • התכנית תוכל לקרוא נתונים מקובץ. לדוגמא הקובץ persons.db שמקושר בסכום עבר ולהכניס אותם לטבלה.
   • המפתח לפונקצית ה-hash יהיה השם (מחרוזת).
   • לצרכי בדיקה, תהינה
     • פונקצית הדפסה של הטבלה כך שכל כניסה לטבלה והרשימה המקושרת שלה תודפס לחוד.
     • פונקצית סטטיסטיקה של תפוסה, מקומות ריקים וארך רשימה מכסימלי.
   • התכנית תקבל את הפרמטרים שיקבעו
     • שם קובץ הנתונים ללא ברירת מחדל.
     • מספר מירבי של נתונים לקריאה. ברירת המחדל, לקרוא את כל הקובץ.
     • גודל הטבלה, ברירת מחדל 1543.
     • האם להדפיס סטטיסטיקה, ברירת מחדל: לא.
     • האם להדפיס את הטבלה, ברירת מחדל: לא.
בדוגמת ההרצה שתשלח, יהיו שורת הפקודה במדויק, עם קריאה של 10 רשומות נתונים לטבלת-hash בגודל 7, עם הדפסת טבלה, והדפסת סטטיסטיקה.
אפשר לממש את התכנית בקובץ .c אחד ולשלוח אותו. אבל אפשר ורצוי לפצל, במקרה כזה יש להוסיף Makefile שיאפשר לבנות את התכנית, ולארוז את קבצי המקור בקובץ .tar.gz. בכל מקרה, נא לשלוח קבץ אחד בלבד.