ساختمان داده

به وبسایت سامینتک خوش آمدید.

برنامه‌های پایه‌ی ساختمان داده

• استک (Stack)
  پشته یا Stack یک حافظه ی First in – Last out است. یعنی داده ای که زودتر در این حافظه قرار می‌گیرد، دیرتر از همه هم از حافظه خارج می‌شود.
  معمولا برای پشته متدهای زیر تعریف می‌شود:
  متد push: یک داده به انتهای پشته اضافه می‌کند.
  متد pop: آخرین داده در پشته را برمی‌گرداند و سپس از پشته حذف می‌کند.
  متد peek: آخرین داده در پشته را برمی‌گرداند ولی آن را از پشته حذف نمی‌کند.
  متد isEmpty: در صورتی که پشته خالی باشد مقدار true را برمی‌گرداند.
  متد isFull: در صورتی که ظرفیت حافظه ی پشته پر شده باشد مقدار true را برمی‌گرداند.
  متد getMaxSize: حداکثر اندازه‌ی پشته را برمی‌گرداند.
  متد getSize: تعداد اعضای پر در پشته را می‌گرداند.
  لینک پاسخ
• صف (Queue)
  صف یا Queue یک حافظه ی First In – First Out است. یعنی داده ای که زودتر در این حافظه قرار می‌گیرد، زودتر از همه هم از حافظه خارج می‌شود.
  معمولا برای صف متدهای زیر تعریف می‌شود:
  متد insert: یک داده به انتهای صف اضافه می‌کند.
  متد delete: داده ی ابتدای صف را برمی‌گرداند و سپس از صف خارج می‌کند.
  متد peek: داده ی ابتدای صف را برمی‌گرداند ولی آن را از صف خارج نمی‌کند.
  متد isEmpty: در صورتی که صف خالی باشد مقدار true را برمی‌گرداند.
  متد isFull: در صورتی که ظرفیت حافظه ی صف پر شده باشد مقدار true را برمی‌گرداند.
  متد size: تعداد اعضای منتظر در صف را برمی‌گرداند.
  متد maxSize: ظرفیت صف را برمی‌گرداند.
  لینک پاسخ
• لیست پیوندی (Linked List)
  لیست پیوندی نوعی از ساختمان داده برای حافظه است و ذخیره ی داده ها است. اما لیست پیوندی بر خلاف آرایه و … محدودیت مکانی ندارد و هر تعداد داده ای می‌توان در آن قرار داد. لیست پیوندی در اصل از یک گره یا Node به اسم head تشکیل شده است که همان گره خود اشاره گری به یک گره ی دیگر در خود دارد و آن گره هم یک اشاره گر به گره ی دیگر و … و عملا ما لیست یا زنجیری از گره ها را خواهیم داشت که به آن لیست پیوندی می‌گویند 🙂
  معمولا برای لیست پیوندی متدهای زیر ممکن است تعریف شود:
  متد insertFirst: یک داده به ابتدای لیست اضافه می‌کند.
  متد insertLast: یک داده به انتهای لیست اضافه می‌کند.
  متد deleteFirst: داده‌ی ابتدای لیست را برمی‌گرداند و سپس آن گره را از لیست حذف می‌کند.
  متد deleteLast: داده‌ی انتهای لیست را برمی‌گرداند و سپس آن گره را از لیست حذف می‌کند.
  متد peekFirst: داده‌ی ابتدای لیست را برمی‌گرداند ولی آن گره را از لیست حذف نمی‌کند.
  متد peekLast: داده‌ی انتهای لیست را برمی‌گرداند ولی آن گره را از لیست حذف نمی‌کند.
  متد isEmpty: در صورتی که لیست خالی باشد مقدار true را برمی‌گرداند.
  لینک پاسخ
• لیست دو پیوندی:
  لیست دو پیوندی لیستی است که هر نود در آن دو اشاره گر دارد. حالا ممکن است نام آن ها next و back باشد یا next1 و next2 و یا left و right و …
• لیست چند پیوندی:
  لیست چند پیوندی لیستی است که هر نود در آن چند اشاره گر دارد. ممکن است نام آن ها next1 و next2 و … باشد.
• درخت: نوعی لیست چند پیوندی است که چند اشاره گر دارد. در درخت هیچ وقت دو اشاره گر به یک نود را نداریم.
• درخت باینری: نوعی لیست دو پیوندی است که دو اشاره گر left و right را دارد. در درخت هیچ وقت دو اشاره گر به یک نود را نداریم.
• مرتب سازی درجی (Insertion Sort)
  
• مرتب سازی ادغامی (Merge Sort)
• مرتب سازی انتخابی (Selection Sort)
  
• مرتب سازی سریع (Quick Sort)
  

  تمرین‌های ساختمان داده

  ۱- تابعی به صورت بازگشتی بنویسید که دو عدد x و y را با هم جمع کند.

  ۲- تابعی به صورت بازگشتی بنویسید که دو عدد x و y را در هم ضرب کند.

  ۳- تابعی به صورت بازگشتی بنویسید که مینیمم اعضای یک آرایه را برگرداند.

  ۴- تابعی به صورت بازگشتی بنویسید که مجموع اعداد ۱ تا n را برگرداند.

  ۵- تابعی به صورت بازگشتی بنویسید که مجموع اعضای یک آرایه را محاسبه کند و برگرداند.

  ۶- تابعی بنویسید که بزرگ‌ترین مقسوم علیه مشترک (ب م م) دو عدد را محاسبه کند و برگرداند. تابع را هم به صورت صریح و هم بازگشتی بنویسید. پیچیدگی زمانی و big O را در هر دو حالت پیدا کنید.

  ۷- تابعی بازگشتی بنویسید که محتوای یک آرایه را خوانده و به صورت برعکس چاپ کند.

  ۸- مسئله ی برج هانوی را به کمک استک و به صورت صریح حل کنید. (اختیاری)

  ۹- به کمک استک یک ماشین حساب طراحی کنید که عبارت های شامل عملگرهای + و – و * و / و پرانتز را محاسبه و چاپ کند.

  ۱۰- به کمک لیست پیوندی برنامه ای بنویسید که بتواند اعداد بسیار بزرگ (مثلا یک میلیون رقمی) را بر اعداد کوچک integer (مثلا چهار رقمی) تقسیم کند.

  ۱۱- لیست پیوندی را برای ماشین پیاده کنید. قابلیت اضافه کردن ماشین و حذف کردن ماشین بر اساس کد ماشین و نمایش ماشین هایی با ویژگی هایی خاص و … را به برنامه اضافه کنید.

  ۱۲- برنامه‌ای بنویسید که قابلیت‌های زیر را داشته باشد:
  الف) داده هایی از ورودی دریافت و در آرایه ای ذخیره کند.
  ب) الگوریتم Insertion Sort را روی داده ها پیاده کند و مرحله به مرحله داده ها را چاپ کند.
  ج) الگوریتم Quick Sort را روی داده ها پیاده کند و مرحله به مرحله داده ها را چاپ کند.
  د) الگوریتم Merge Sort را روی داده ها پیاده کند و مرحله به مرحله داده ها را چاپ کند.
  ه) الگوریتم Selection Sort را روی داده ها پیاده کند و مرحله به مرحله داده ها را چاپ کند.
  *برنامه را طوری بنویسید که کاربر بتواند یکی از گزینه های بالا را انتخاب کند و هربار که کار برنامه تمام شد دوباره برنامه گزینه های بالا را پیش روی کاربر قرار دهد.

  ۱۳- برنامه‌ای بنویسید که اطلاعات تعدادی دانشجو از قبیل نام و نام خانوادگی و شماره‌ی دانشجویی را از ورودی خوانده و آن ها را در یک درخت باینری سرچ ذخیره کند. این برنامه باید قابلیت های زیر را داشته باشد:
  ۱. حذف یک دانشجوی خاص بر حسب شماره‌ی دانشجویی
  ۲. چاپ اطلاعات دانشجویان
  ۳. اضافه کردن اطلاعات یک دانشجوی جدید