ساختمان داده (Data Structure) — راهنمای جامع و کاربردی

آشنایی با «ساختمان داده‌ها» (Data Structures) از جمله نیازهای دانشمندان داده، مهندسان داده، داده‌کاوها، کارشناسان یادگیری ماشین و برنامه‌نویس‌ها محسوب می‌شود. مهندسین نرم‌افزار بیش از ۴۰ سال است که با انواع ساختارهای داده سر و کار دارند، از این رو در اغلب مسائل موجود در داده‌کاوی، یادگیری ماشین و برنامه‌نویسی نیاز به داشتن درک عمیقی از ساختمان داده‌ها وجود دارد. اهمیت این مبحث تا حدی است که در بسیاری از مصاحبه‌های استخدام پرسش‌هایی پیرامون آن مطرح می‌شود. بنابراین در این مطلب، به موضوع ساختمان داده‌ها پرداخته شده است. سرفصل‌های مورد بررسی در این مطلب در ادامه آمده‌اند.

• ساختمان داده چیست؟
• چرا به ساختمان داده نیاز است؟
• ساختارهای داده متداول کدامند؟

ساختمان داده چیست؟

به بیان ساده، «ساختمان داده» (Data Structure) ظرفی است که داده‌ها در آن در یک قالب خاص ذخیره‌سازی می‌شوند. این «قالب» به ساختمان داده‌ها این امکان را می‌دهد که در برخی از عملیات کارآمد و در برخی دیگر ناکارآمد باشند. در یک مساله جاری باید ساختمان داده‌ای انتخاب شود که بهینه‌ترین حالت ممکن است.

فیلم آموزش ساختمان داده ها – جامع و با نکات مهم در فرادرس

کلیک کنید

چرا به ساختمان داده نیاز است؟

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

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

ساختارهای داده متداول کدامند؟

در ادامه لیستی از متداول‌ترین ساختمان داده‌ها ارائه می‌شود. سپس تک تک این موارد مورد بررسی قرار می‌گیرند.

فیلم آموزش رایگان ساختمان داده ها – سریع و آسان در ۱۲۰ دقیقه در فرادرس

کلیک کنید

• آرایه (Array)
• پشته (Stack)
• صف (Queue)
• لیست پیوندی (Linked List)
• درخت (Tree)
• گراف (Graph)
• درخت پیشوندی (Trie) (این ساختمان داده نوعی درخت است. اما به دلیل تفاوت های آن با درخت، با عنوان مجزا نامیده می‌شود).
• جدول درهم‌سازی (Hash Table)

آرایه

آرایه، ساده‌ترین و پراستفاده‌ترین ساختمان داده است. دیگر ساختمان داده‌ها مانند پشته و صف از آرایه مشتق شده‌اند. در تصویر زیر یک آرایه با سایز چهار شامل عناصر ۱، ۲، ۳ و ۴ قابل مشاهده است.

فیلم آموزش آرایه در ساختمان داده ها (مرور – تست کنکور ارشد) (رایگان) در فرادرس

کلیک کنید

به هر عنصر داده یک مقدار عددی مثبت (منظور اعداد صحیح غیر منفی شامل صفر است) تخصیص داده می‌شود که اندیس (Index) نام دارد و موقعیت آن عنصر را در آرایه نشان می‌دهد. در اغلب زبان‌های برنامه‌نویسی اندیس آرایه از عدد ۰ تعریف شده است.

در آرایه مشاهده شده در بالا، اندیس خانه‌ای که مقدار ۱ در آن قرار دارد برابر با ۰، خانه حاوی عدد دو دارای اندیس ۱، خانه با مقدار ۳ دارای اندیس ۲ و خانه با مقدار ۴ دارای اندیس ۳ است. به طور کلی دو نوع آرایه وجود دارد که در ادامه بیان شده‌اند.

• آرایه یک بُعدی (مانند آنچه در بالا نشان داده شده)
• آرایه چند بُعدی (آرایه در آرایه)

عملیات پایه‌ای روی آرایه‌ها

درج (Insert ): درج یک عنصر در اندیس داده شده (در خانه‌ای که اندیس آن داده شده است).

دریافت (Get): عنصر موجود در اندیس داده شده را باز می‌گرداند (عنصر موجود در خانه‌ای که اندیس آن داده شده است).

حذف (Delete): حذف یک عنصر در اندیس داده شده (حذف مقدار موجود در خانه‌ای که اندیس آن داده شده است).

اندازه (Size): دریافت تعداد کل عناصر موجود در آرایه (در مثال بالا تعداد کل عناصر آرایه ۴ است).

پرسش‌های متداول پیرامون آرایه در مصاحبه‌های استخدام

• دومین عنصر کمینه در آرایه را پیدا کنید.
• اولین عدد صحیح غیر تکراری در آرایه را پیدا کنید.
• دو آرایه مرتب شده را ادغام کنید.
• مقادیر مثبت و منفی در یک آرایه را مجددا مرتب کنید.

پشته

اغلب افراد با دکمه Undo که تقریبا در کلیه نرم‌افزارها وجود دارد آشنایی دارند. اما اکثر افراد از ساز و کار این دکمه بی‌خبر هستند. ایده اصلی نهفته در پس Undo این چنین است که حالت (وضعیت) قبلی کار کاربر در حافظه ذخیره می‌شود (که محدود به تعداد مشخصی است). این داده‌ها به صورتی ذخیره می‌شوند که آخرین داده ذخیره شده اول نمایش داده می‌شود. این کار با استفاده از آرایه قابل انجام نیست. در اینجا است که نیاز به «پشته» (Stack) مطرح می‌شود.

فیلم آموزش ساختمان داده ها – جامع و با نکات مهم در فرادرس

کلیک کنید

یک مثال جهان واقعی از پشته، دسته‌ای از کتاب‌ها هستند که به صورت عمودی روی هم قرار گرفته‌اند. به منظور برداشتن کتابی که در وسط قرار دارد، نیاز به حذف همه کتاب‌هایی که روی آن قرار دارند است. این چگونگی کارکرد روش «آخرین ورودی اولین خروجی» (LIFO | Last In First Out) است. در زیر، تصویر یک پشته شامل سه عنصر داده (۱، ۲ و ۳) قابل مشاهده است که در آن، ۳ در بالا قرار دارد و ابتدا حذف خواهد شد.

عملیات پایه‌ای پشته

Push  (برای گذاشتن داده): قرار دادن یک عنصر در بالا

Pop  (برای برداشتن داده با حذف آن داده): عنصر بالایی (Top) را پس از حذف از پشته باز می‌گرداند.

isEmpty (بررسی خالی بودن پشته): مقدار صحیح (true) را در صورت خالی بودن پشته باز می‌گرداند.

Top (برای برداشتن داده بدون حذف آن): عنصر بالایی را بدون حذف از پشته باز می‌گرداند.

پرسش‌های متداول پیرامون پشته در مصاحبه‌های استخدام

• عبارت پسوندی (postfix expression) را با استفاده از پشته ارزیابی کنید.
• مقادیر موجود در یک پشته را مرتب کنید.
• توازن پرانتزهای یک عبارت را بررسی کنید.

صف

مشابه با پشته، «صف» (Queue) دیگر ساختار داده خطی است که عناصر را به طور ترتیبی ذخیره می‌کند. تنها تفاوت قابل توجه بین پشته و صف آن است که به جای استفاده از روش آخرین ورودی اولین خروجی، صف روش «اولین ورودی اولین خروجی» (FIFO | First in First Out) را پیاده‌سازی می‌کند.

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

یک مثال جهان واقعی مناسب از صف، افرادی هستند که در صف مقابل باجه بلیط ایستاده‌اند. اگر یک فرد جدید اضافه شود، به انتهای صف می‌رود و فردی که در ابتدای صف ایستاده اولین نفری است که بلیط دریافت کرده و بنابراین صف را ترک می‌کند. در تصویر زیر صفی شامل ۴ عنصر داده (۱، ۲، ۳ و ۴) نشان داده شده که در آن ۱ در بالای صف قرار دارد و بنابراین اولین عنصری است که حذف می‌شود.

عملیات پایه‌ای در صف

Enqueue(): افزودن عنصر به انتهای صف