دانلود پاورپوینت با موضوع ساختمان داده ها،
در قالب ppt و در 20 اسلاید، قابل ویرایش.
بخشی از متن پاورپوینت:
جدول درهم سازی
آیا راه بهتری برای ذخیره ی عناصر یک مجموعه وجود دارد؟
تاکنون لیست مرتب و درخت جستجوی دودویی را دیده ایم.
جدول درهم سازی:
از یک تابع ریاضی به اسم تابع درهم سازی استفاده می کند.
در هنگام دسترسی یا ذخیره ی داده ها ممکن است با برخورد مواجه شویم.
پیچیدگی
پیاده سازی آن تا حدودی مشکل است.
انگیزه ی استفاده از درهم سازی
ما مجبوریم که تعدادی رکورد را ذخیره و اعمال زیر را انجام دهیم:
اضافه کردن یک رکورد جدید.
حذف یک رکورد موجود.
جستجوی یک رکورد.
دنبال راهی هستیم که این کارها را بهتر انجام دهیم.
تا کنون چه راه حلهایی را دیده‌ایم؟
آرایه ی نامرتب
استفاده از یک آرایه ی نامرتب برای ذخیره کردن اطلاعات.
اضافه کردن
خیلی سریع است. (O(1)) چون که می توانیم رکورد را به عنوان آخرین عنصر ذخیره کنیم.
حذف یک عنصر
کند است چون باید عنصر را پیدا کنیم. O(n)
جستجو:
جستجوی ترتیبی کند است. O(n)
آرایه ی مرتب
هنگام اضافه کردن عناصر ترتیب آنها را به هم نمی‌زنیم.
الحاق
کند است چون باید جای عنصر پیدا کنیم. O(n)
حذف
بعد از حذف یک جای خالی باقی می ماند که باید با جابجایی حل شود. لذا کند است. O(n)
جستجو
جستجوی دودویی سریع است. O(logn)
لیست پیوندی نامرتب
عناصر را در یک لیست پیوندی ذخیره می کنیم.
الحاق
سریع است. می توانیم داده را هر جا که خواستیم اضافه کنیم. O(1)
حذف
حذف خود عنصر سریع است اما پیدا کردن آن کند است. O(n)
جستجو
چون جستجو ترتیبی است کند است. O(n)
لیست پیوندی مرتب
عناصر را در یک لیست پیوندی مرتب ذخیره می کنیم.
الحاق
کند است. باید جای نود را پیدا کنیم. O(n)
حذف
حذف خود عنصر سریع است اما پیدا کردن آن کند است. O(n)
جستجو
چون جستجو ترتیبی است کند است. O(n)
درخت جستجوی دودویی
عناصر را در یک درخت جستجوی دودویی ذخیره می کنیم.
الحاق
سریع است. با ارتفاع درخت متناسب است. O(logn)
حذف
سریع است. با ارتفاع درخت متناسب است. O(logn)
جستجو
سریع است. با ارتفاع درخت متناسب است. O(logn)
استفاده از آرایه به عنوان جدول
استفاده از آرایه به عنوان جدول
استفاده از آرایه به عنوان جدول
رکوردها را در یک آرایه ی بزرگ ذخیره کنید و از ایندکس به عنوان کلید استفاده کنید.
الحاق خیلی سریع است. O(1)
حذف خیلی سریع است. O(1)
جستجو خیلی سریع است. O(1)
اما اتلاف حافظه خیلی زیاد است.
باید راهی پیدا کنیم که از حافظه بهتر استفاده کنیم.
دانلود فایل”پاورپوینت ساختمان داده ها”
