پاورپوینت لغت نامه و جدول درهم سازی (pptx) 34 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 34 اسلاید
قسمتی از متن PowerPoint (.pptx) :
لغت نامه و جدول درهم سازي Dictionaries and Hash Tables
ساختمان داده ها و الگوريتم
لغت نامه - Dictionary
مجموعه اي از زوج هاي مرتب به صورت:
(key, element)
کليد زوج هاي مرتب متفاوت است
عمليات روي لغت نامه:
get(theKey)
put(theKey, theElement)
remove(theKey)
کاربرد Application
مجموعه دانشجويان اين کلاس
(key, element) = (student name, linear list of assignment and exam scores)
همه کليدها منحصر بفرد هستند
مثال:
پيدا کردن زوج مرتبي که کليد آن ”علي تقي زاده“ باشد
بروز رساني رکوردي که کليد آن ”ايمان معتمدي“ است
بروز رساني معادل حذف رکورد فعلي و سپس اضافه کردن رکورد با تغييرات جديد است
Update(x)
R = get(x) ; // get the record with key X
remove(x) ;
Modify R
Put(x , R)
کليدهاي تکراري در لغت نامه
لغت نامه ممکن است کليد تکراري داشته باشد
همانند کلمات تکراري يک لغت نامه
روان : روح، جان
روان: رونده ، جاري
روان: اسم خاص (اسم شهر)
روان: اسم خاص (اسم شخص)
مي توان ركوردهاي هم كليد را با يك ليست نشان داد
نمايش لغت نامه با يک ليست خطي
L = (e0, e1, e2, e3, …, en-1)
Each ei is a pair (key, element).
5-pair dictionary D = (a, b, c, d, e).
a = (aKey, aElement), b = (bKey, bElement), etc.
مي توان از آرايه يا ليست پيوندي استفاده کرد
نمايش با آرايه
get(theKey)
O(size) time
put(theKey, theElement)
O(size) براي تشخيص دادن کليد تکراري و , O(1) براي افزودن کليد به سمت راست آرايه.
remove(theKey)
O(size) time.
آرايه مرتب
اعضا بر اساس کليد به صورت صعودي مرتب شده اند
get(theKey)
O(log size) time
put(theKey, theElement)
O(log size) براي يافتن کليد تکراري, O(size) براي افزودن کليد در محل مناسب
remove(theKey)
O(size) time.
زنجيره نامرتب
get(theKey)
O(size) time
put(theKey, theElement)
O(size) براي تشخيص دادن کليد تکراري و , O(1) براي افزودن کليد به سمت راست آرايه.
remove(theKey)
O(size) time.
