ساختمان داده و هر آنچه باید در مورد آن بدانید

به عنوان یکی از مهمترین دروس رشته مهندسی کامپیوتر، هدف درس ساختمان داده ها پژوهش در مورد روش‌های گوناگون ذخیره، نگهداری و بازیابی اطلاعات در سیستم‌های کامپیوتری است، به گونه‌ای که این اطلاعات بتواند بطور کارامد مورد استفاده قرار گیرد. ساختمان‌های داده‌ برای دریافت داده‌ها توسط کامپیوتر جهت پیاده سازی و اجرای الگوریتم‌ها مورد استفاده قرار می‌گیرند، اما الگوریتم‌ها دستورالعمل‌هایی هستند که بر روی داده‌ها اعمال می‌شوند. هر ساختمان داده بسته به طراحی و هدفی که دنبال می‌کند چگونگی آرایش داده‌ها در حافظه‌ی کامپیوتر را با مدل خاصی مشخص می‌کند. طراحی هر ساختمان داده به گونه‌ای انجام می‌شود که بتواند نیاز خاصی را برطرف کند و برنامه نویس با توجه به نیازهای برنامه‌ای که طراحی می‌کند، می‌بایست ساختمان داده‌های مناسب خودش را انتخاب کند.

حال داده های ورودی به کامپیوتر توسط پردازنده و تحت فرمان “واحد کنترل” از حافظه دریافت شده و پس از اجرای الگوریتم های مورد نظر روی آن ها، نتایج روی حافظه ذخیره می‌شوند و یا به دستگاه های خارجی مانند مانیتور منتقل می‌شوند.

حافظه و دستگاه های ورودی و خروجی ترتیب انجام کارها را نمی‌دانند و این واحد کنترل است که با توجه به دستوری که می‌خواهد اجرا شود، ترتیب کارهایی که این واحد ها باید انجام دهند را در هر پالس ساعت با ارسال سیگنال‌هایی به نام Command مشخص می‌کند. به چگونگی کارکرد، طراحی و ساخت اجزای کامپیوتر معماری کامپیوتر گفته می شود.

برنامه‌ای خوب است که هم ساختمان داده مناسبی داشته باید و هم الگوریتم‌ خوبی برای آن نوشته شود. در درس ساختمان داده انواع ساختمان داده ها و اینکه برای هر الگوریتم چه ساختمان داده ای بهتر است آموزش داده می‌شود و در درس طراحی الگوریتم دانشجویان آموزش می بینند که چگونه راه حل های بهینه برای حل مسائل پیدا کنند. یکی از بزرگترین دغدغه هایی که درس طراحی الگوریتم سعی در پاسخ به آن دارد، آموزش بدست آوردن راه حل های سریع، بهینه و عملی برای مسائل گوناگون است. در ادامه به معرفی ساختمان داده هایی پرداخته‌ایم که برنامه نویسان از آنها زیاد استفاده می‌کنند

ساختمان های داده ابتدایی

Boolean 

Integer 

Floating-point numbers

Fixed-point numbers

Character 

String 

برای کسب اطلاعات بیشتر درباره هریک از انواع داده های ابتدایی، به سایت کنکور کامپیوتر مراجعه کنید.

ساختارهایی از داده وجود دارند که روی انواع داده های ابتدایی ساخته می شوند. از جمله ساختمان داده های پرکاربرد می توان به موارد زیر اشاره کرد:

1. آرایه (Array)
2. لیست پیوندی (Linked List)
3. پشته (Stack or Push Down List or Pile)
4. صف (Queue)
5. درخت های ساده (Binary Tree)
6. درخت جستجوی دودویی (Binary Search Tree)

آرایه

به عنوان مهمترین ساختار ذخیره داده، اکثر برنامه نویس ها از آرایه بهره می برند. آرایه مجموعه‌ای از داده‌هایی است که خصوصیات زیر را داشته باشد :

• همگی از یک نوع داده باشند
• در خانه‌های پیوسته حافظه قرار گیرند

دو نوع آرایه داریم:

1. آرایه تک بعدی
2. آرایه های چند بعدی

 لیست پیوندی

ساختمان داده ای که از تعدادی نود تشکیل شده است در حالی که هر نود در برگیرنده دیتا و آدرس نود بعدی است.

پشته

پشته مجموعه ای پویا از داده ها است که هنگام حذف عنصر از این مجموعه، آخرین عنصر اضافه شده به مجموعه از آن حذف می‌شود. اصطلاحا به این روش حذف داده های LIFO (Last In First Out) گفته می‌شود. بنابراین پشته ترتیب خروج عناصر را کنترل می‌کند. در نتیجه برای دسترسی به یک عنصر، ابتدا باید عناصری را که پس از آن به پشته وارد شده‌اند از پشته خارج کرد.

صف

ساختمان داده صف یک لیست است که عناصر جدید به انتهای صف اضافه  می‌شوند و در هنگام حذف، عناصر از ابتدای صف حذف می شوند. ساختمان داده صف برای مدیریت نوبت عناصر از الگوریتم FIFO(First In First Out)  استفاده می‌کند که بر طبق آن هر عنصری که زودتر وارد صف شود زودتر سرویس می‌گیرد

عملیات اصلی که روی صف انجام می‌گیرد

ENQUEUE (Q,X) : اضافه کردن عنصر x به انتهای صف Q

DEQUEUE (Q) : حذف یک عنصر از ابتدای صف Q و بازگرداندن آن عنصر بعنوان خروجی

درخت 

مجموعه ای از عناصر که گره نام دارند را درخت می نامند. یکی از این گره ها در جایگاه ریشه درخت و سایر گره ها در زیر ریشه قرار دارند. از درخت به منظور آنالیز  مدارهای الکترونیکی، بیان رابطه‌ها، سازماندهی داده‌ها در پایگاه های داده‌ای و بیان ساختارهای گرامری در کامپایلرها استفاده می‌شود.

درخت جستجوی دودویی (BST: Binary Search Tree)

درختی است که در درون هر نودش یک عدد وجود دارد و اعداد همگی متمایزاند، در این درخت هر نودی از تمامی نودهای زیر درخت چپ اش بزرگتر و از تمامی نودهای زیر درخت راست اش کوچکتر است

مقایسه ساختمان های داده

انواع ساختمان های داده دارای معایب و مزایایی هستند که در این بحث معمولا سه عملیات درج، حذف و بازیابی عنصر مد نظر قرار می گیرند. برای کسب اطلاعات بیشتر در این زمینه، مطالعه بحث ساختمان داده در سایت کنکور کامپیوتر خالی از لطف نیست.

بنا بر ارتباط تنگاتنگ ساختمان های داده و طراحی الگوریتم و از آنجایی که داده های خروجی، حاصل اجرای الگوریتمی خاص روی داده های ورودی هستند، مراحل حل مساله و طراحی الگوریتم به صورت زیر خواهد بود:

1.  تبدیل مسئله به یک مدل ریاضی که توسط کامپیوتر قابل حل باشد
2. طرح یک الگوریتم برای حل آن مسئله
3. انتخاب ساختمان داده مناسب برای الگوریتمی که طرح کرده ایم

از آن جا که برنامه خوب برنامه ای است که هم ساختمان داده مناسبی داشته باید و هم از الگوریتم‌های بهینه تری استفاده کند، در اینجا به بررسی دو مورد زیر می‌پردازیم:

1. چگونگی تحلیل الگوریتم
2. بررسی ساختمان داده‌ها

تحلیل الگوریتم ها

در تحلیل الگوریتم ها، از آنجا که تعداد عملیات هر الگوریتم برای اجرا شدن رابطه مستقیمی با زمان اجرای آن دارد و با در نظر گرفتن این که زمان اجرا وابسته به معیارهای متفاوتی نظیر پردازنده کامپیوتر، نوع کامپایلر، سرعت پردازنده، چگونگی پیاده سازی الگوریتم و بسیاری موادر دیگر است، با در دست داشتن معیاری مشخص می توانیم کارایی الگوریتم‌ها از نظر مدت زمان اجرا را، مستقل از عوامل مذکور با هم مقایسه کنیم.

از آنجا که حجم داده های ورودی همواره متغیر است، در تحلیل زمان اجرای الگوریتم‌ها تابعی‌ نیاز است که تعداد عملیات انجام شده توسط یک الگوریتم را بر حسب اندازه ورودی بیان کند. حال محاسبه این تابع کاری دشوار و در مواقعی غیر ممکن است؛ به همین علت برای مقایسه الگوریتم‌ها از معیاری به نام نرخ رشد توابع استفاده می‌کنند.

 نرخ رشد میزان افرایش تعداد عملیات یک الگوریتم بر اثر افزایش اندازه ورودی را نشان می‌دهد.

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

عملیات روی هر ساختمان داده را می‌توان در دو دسته کلی طبقه بندی کرد:
1) Query ها یا درخواست ها

2) Update ها

Queryها آن دسته از عملیات هستند که تغییری در محتویات ساختمان داده ها ایجاد نمی‌کنند، مانند جستجوی یک عنصر، شمارش تعداد عناصر موجود در ساختمان داده و …
Update ها عملیاتی هستند که سبب تغییر در مقدار یا چینش عناصر ساختمان داده می‌شوند، مانند اضافه کردن یک عنصر جدید، حذف عناصر موجود و …

حال که با تعاریف مربوط به ساختمان داده ها و طراحی الگوریتم ها آشنا شده و به اهمیت و کارایی این درس در رشته مهندسی کامپیوتر پی برده اید، پیشنهاد می کنیم در صورتی که تمایل به ارتقای سطح علمی خود در این درس دارید، از فیلم های آموزش ساختمان داده ها غافل نشوید.