پاورپوینت لغت نامه و جدول درهم سازي (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.