صفحه 1:
صفحه 2:
1
ليست در واقع در دسته ساختمان هاى داده قرار نمى كيرد. اين ساختمان داده براى مديريت
فهرستی از عنصرها به کار می رود که می توانند از هرنوعی مانند عدد صحیح,عدد
اعشاری .رشته و... باشند. این کلاس دارای متدهایی برای حذف و افزودن عنصر دسترسی به
عنصرهای موجود در آن. مرتب کردن عنصرهاء تعیین و تغییر ظرفیت لیست و.. فراهم آورده که
به کارگیری آن را بسیار کاربردی کرده است.
صفحه 3:
ساختمان داده ای بسیار پر کاربرد و در عین حال ساده است که در پیاده سازی بسیاری از برنامه
هاءنقش اساسی دارد. عنصرهای جدید به پایان پشته اضافه شده و از پایان آن نیز حذف می
شوند.
شکل زیر چگونگی عملکرد پشته را نمایش می دهد.
صفحه 4:
pop
[2] 3] s] 2] 9]
push
صفحه 5:
در این ساختمان داده عنصرهای جدید به پایان صف اضافه شده و از آغاز آن حذف می شوند.
JSS زیرعملکرد صف را نمایش می دهد
صفحه 6:
تف ۶۱ ا* ]3 Li]
صفحه 7:
:مجموعه
نوعى ازآرايه هاى انجمنى هستند كه عنصرهاى يكتا را درون خود نكه ميدارند.
أعضاى درون مجموعه به صورت بيش فرض به ترتيب صعودى مرتب مى شوند.مجموعه ها در واقع به كمك درخت هاى
جستجوى دودويى بياده سازى شده اند.
ويزكى هاى اصلى مجموعه ها عبارتند از:
١-مقادير عنصرهاى موجود در آن يكتا هستند و هيج دو عنصرى در مجموعه نمى توانند باهم برابر باشند.
؟-مقدار عنصرهاءخود نقش شناسه را بازى مى كنند.آرايه انجمنى مشابهى به نام نكاشت نيز وجود دارد كه در آن»مقدار
عنصرها از شناسه ها جداهستند.
صفحه 8:
این ساختمان داده مشابه ساختمان داده ی جدول درهم سازی است.با این تفاوت که نگاشت به صورت درونی عمل نمی کند.
دو ویذگی مهم نگاشت عبارت است از:
۱-کلیدهای یکتااهیچ دو عنصری از نگاشت دارای کلید یکسان نیستند.
۲-هرعضو دارای یک کلید و یک داده است.
صفحه 9:
:بردار
کلاسی برای نگهداری مجموعه ای از عنصرهاست.عنصرهای موجود در بردار در حافظه ای
پیوسته ذخیره شده که موجب می شود علاوه بر قلبل پیمایش بودن بردار,قابلیت دسترسی به
عنصرها توسط نمایه وجود داشته باشد
صفحه 10:
*درخت جستجوی دودوبی
درخت جستجوی دودویی از ساختمان داده های کاربردی است که اهمیت وژه ای در الگوریتم های مرتب سازی دارد.
درخت جستجویی دودویی,درختی دودوبی بااین قوانین است:
۱-هرگره ای در درخت دارای یک مقدار یکتا است.
۲-زیردرخت راست و چپ خود درخت جستجوی دودویی هستند.
۳-فرزندان سمت چپ هرگره‌فقط می توانند مقادیر کمتر ازآن گره را داشته باشند.
۴تفوزننان سس راست هركره:فقط مى توانند مقادير بيشتر ازآن كره را داشته باشند.
صفحه 11:
صفحه 12:
:درخت جستجوی دودویی دارای توابع زیراست
۱-جستجوی یک گره در درخت
۲-افزودن یک گره به درخت
۳-حذف یک گره از درخت
بيمايشدرخث4
صفحه 13:
#درخت ای-وی-ال
یک درخت جستجوی دودویی متوازن است.به این معنی که اختلاف ارتفاع زیردرخت چپ و راست هیچ
گره ای از درخت.بیشتر از یک نیست.
درخت ای-وی-ال درمقایسه بادرخت جستجوی دودویی معمولی‌سرعت بیشتری در جستجوی یک گره
دارد زیرا درخت هميشه متوازن است.درعوض هزینه افزودن و حذف یک گره در درخت ای-وی-ال
افزایش می یابد.
صفحه 14:
:هرم
هرم يكى از ساختمان داده هاى مبتنى بر درخت است.
هرم يك درخت كامل است كه داراى يكى از دوقانون زيراست:
۱-مقدار درون هرگره از مقدار درون كره هاى فرزندانش بيشتر است.
۲-مقدار درون هرگره از مقدار درون گره های فرزندانش کمتراست.
اگر هرم دارای قانون نخست باشد.آن هرم بيشینه و اگراز قانون دوم پیروی کند آم هرم را کمینه می نامند.
صفحه 15:
نوعی خاصی از صف است با این تفاوت که عضو سرصف هميشه طبق یک معیار مرتب سازی از
ساير اعضای صف ارزشمندتراست.
این ساختمان داده شباهت بسیاری به هرم داردزیرا درهرزمانی می توان عنصری به آن افزود.
صفحه 16:
#جدول درهم سازی
ساختمان داده ای است که توسط یک تابع درهم سازی.هر کلیدیکتایی را به یک مقدار یکتا نسبت می
دهد.
جدول درهم سازی در واقع از یک بردار یا آرايه اى از داده ها به شكلى كاملا معمولى تشكيل مى شود.
نقش اصلى برعهده تابع درهم سازى است كه يك كليد را به عنوان ورودى دريافت كرده و نمايه اى از آرايه
ها برمی گرداند.تامقدار مربوط به ان کلید درآن نمایه از آراه قرار گیرد.
به یک جدول درهم ساز که دقیقا هرکلیدرا به یک نمایه نسبت دهد.جدول درهم ساز کامل گفته مى
صفحه 17:
کارایی بیشتر روشهای رفع برتورد به تنهایی به تعداد کلیدهای ذتیره شده وابسته نیست؛ بلکه ارتباط تنگاتنگی با
عامل بارگیری جدول دارد. عامل بارگیری برابر است با نسبت تعداد کلیدهای ذتیره شده به طول آرایه:
افزايش عامل باركيرىء احتمال ایجاد برتورد بیشتر و در نتیجه سرعت دسترسی به دادهها کمتر و کمتر ميشود.
كاهش عامل بارگیری افزایش طول آرايه
صفحه 18:
11
LoadFactor=—
0
صفحه 19:
روشهای رفع برخورد
۱- زنجیرسازی
۲- آدرسدهی باز
۳- درهمسازی ترکیبی
۴ درهمسازی رابین هود
۵- درهمسازی فاتته
صفحه 20:
روش رفع برخورد | سرعت دستیایی به دادهها در بدترین ete
زنجیره‌ای O(n)
درهمسازی رابین‌هود O(n)
| درهمسازی فاخته 000
صفحه 21:
#مجموعه های از هم جدا ساختمان داده ی مجموعه های جدا. برای نگهداری عنصرها در قالب
مجموعه های متفاوت است. برای نمونه فرض کنید در برنامهای تعدادی درخت دارید که هریک
شامل چند گره است و در لین برنامه نیازمند به انجام این کارها هستید: ۱- تشخیص درخت مربوط
به هر گره.
۶ ۲- یکسان بودن درخت های مربوط به دو گره.
© ؟- اجتماع دو درتت با يكديكر.
صفحه 22:
* توسط مجموعه های از هم جدا میتوانید به راحتی این کارها را انجام دهید. اساس کار این
ساختمان داده نگهداری درخت در قالب لیست پیوندی یا آرایه ها است.
یکی کاربردهای این ساختمانداده در پياده سازی الگوریتم کروسکال است
* دو عمل اصلی در این ساختمان داده عبارتند از:
# یافتن ريشه ی مربوط به هر عنصر.
اجتماع دو مجموعه؛ برای این منظور ابتدا ريشه های دو مجموعه جستجو شده و سپس یکی
از ریشهها به دیگری متصل ميشود.
صفحه 23: