عیدی

ساختمان داده (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) را پیاده‌سازی می‌کند. یک مثال جهان واقعی مناسب از صف، افرادی هستند که در صف مقابل باجه بلیط ایستاده‌اند. اگر یک فرد جدید اضافه شود، به انتهای صف می‌رود و فردی که در ابتدای صف ایستاده اولین نفری است که بلیط دریافت کرده و بنابراین صف را ترک می‌کند. در تصویر زیر صفی شامل ۴ عنصر داده (۱، ۲، ۳ و ۴) نشان داده شده که در آن ۱ در بالای صف قرار دارد و بنابراین اولین عنصری است که حذف می‌شود.

صف

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

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

Dequeue(): بازگرداندن اولین عنصر صف (عنصر جلوی صف) و حذف آن

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

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

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

  • پشته را با استفاده از صف پیاده‌سازی کنید.
  • اولین k عنصر از یک صف را معکوس کنید.
  • اعداد دودویی از ۱ تا n را با استفاده از صف تولید کنید.

لیست پیوندی

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

همچنین، یک اشاره‌گر راس (Head) وجود دارد که به اولین عنصر از لیست پیوندی اشاره می‌کند و اگر لیست خالی باشد به تهی (Null) یا هیچ مقدار اشاره میکند. لیست‌های پیوندی برای پیاده‌سازی سیستم فایل‌ها (file systems)، جدول‌های درهم‌سازی (hash table) و لیست‌های مجاورت (فهرست همسایگی | adjacency lists) مورد استفاده قرار می‌گیرد. در ادامه تصویری از ساختار داخلی یک لیست پیوندی ارائه شده است.

لیست پیوندی

انواع لیست پیوندی عبارتند از:

  • لیست تک پیوندی (یک طرفه)
  • لیست دو پیوندی (دو طرفه)

عملیات پایه‌ای در لیست پیوندی

InsertAtEnd: یک عنصر داده شده را در انتهای لیست پیوندی درج می‌کند.

Delete : یک عنصر داده شد را از لیست پیوندی حذف می‌کند.

DeleteAtHead : اولین عنصر از لیست پیوندی را حذف می‌کند.

Search : یک عنصر داده شده را از لیست پیوندی حذف می‌کند.

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

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

  • یک لیست پیوندی را معکوس کنید.
  • حلقه را در لیست پیوندی شناسایی کنید.
  • Nاُمین گره از پایان را از یک لیست پیوندی بازگردانید.
  • مقادیر تکراری را از لیست پیوندی حذف کنید.

گراف‌ها

گراف مجموعه‌ای از گره‌ها است که به صورت یک شبکه به یکدیگر متصل شده‌اند. به گره‌ها، راس (vertices) نیز گفته می‌شود. یک جفت (x,y) یال نامیده می‌شود و نشانگر آن است که راس x به راس y متصل شده. یک یال ممکن است شامل وزن/هزینه باشد و نشان دهد چه هزینه‌ای برای رفتن از راس x به y وجود دارد.

گراف

انواع گراف‌ها

  • گراف‌های بدون جهت
  • گراف‌های جهت‌دار

در زبان‌های برنامه‌نویسی گراف‌ها معمولا در یکی از دو قالب زیر نمایش داده می‌شوند:

  • ماتریس مجاورت (ماتریس همسایگی | Adjacency Matrix)
  • لیست مجاورت (فهرست همسایگی | Adjacency List)

الگوریتم‌های متداول پیمایش گراف

  • الگوریتم جست‌و‌جوی اول سطح (Breadth First Search)
  • الگوریتم جست‌و‌جوی عمق اول (Depth First Search)

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

  • جست‌و‌جوی اول سطح و اول عمق را پیاده‌سازی کنید.
  • بررسی کنید که یک گراف درخت هست یا خیر.
  • تعداد یال‌ها در گراف را محاسبه کنید.
  • کوتاه‌ترین مسیر بین دو راس را بیابید.

درخت

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

درخت

انواع درخت

انواع درخت‌ها عبارتند از:

  • درخت N-ary
  • درخت متوازن (Balanced Tree)
  • درخت دودویی (Binary Tree)
  • درخت جست‌و‌جوی دودویی (Binary Search Tree)
  • درخت ای‌وی‌ال (درخت با ارتفاع متوازن | AVL Tree)
  • درخت سرخ – سیاه (Red Black Tree)
  • درخت ۲-۳

از میان انواع درخت‌های بیان شده در بالا، درخت دودویی و درخت جست‌و‌جوی دودویی پر استفاده‌ترین نوع درختان هستند.

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

  • ارتفاع درخت دودویی را محاسبه کنید.
  • Kاُمین مقدار بیشینه در درخت جست‌و‌جوی دودویی را پیدا کنید.
  • گره‌هایی با فاصله «k» از ریشه را پیدا کنید.
  • اجداد یک گره داده شده در درخت دودویی را پیدا کنید.

درخت پیشوندی

Trie که به آن درخت پیشوندی (Prefix Tree) نیز می‌گویند، یک ساختار درخت مانند است که برای حل مسائل مرتبط با رشته‌ها (Strings) بسیار موثر است. این ساختمان داده امکان بازیابی سریع را فراهم می‌کند و اغلب برای جست‌و‌جوی کلمات در دیکشنری، پیشنهاد خودکار در موتورهای جست‌و‌جو و حتی مسیریابی IP یا  IP routing مورد استفاده قرار می‌گیرد. در ادامه تصویری از چگونگی ذخیره‌سازی سه کلمه «thus» ،«top» و «their» در درخت پیشوندی نمایش داده شده است.

درخت پیشوندی

کلمات به صورت بالا به پایین در درخت پیشوندی ذخیره شده‌اند و گره‌های سبز رنگ s ،p و r نشانگر حروف پایانی در واژگان thus ،top و their هستند.

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

  • تعداد کل کلمات در درخت پیشوندی را محاسبه کنید.
  • همه کلمات ذخیره شده در درخت پیشوندی را چاپ کنید.
  • عناصر یک آرایه را با استفاده از درخت پیشوندی مرتب‌سازی کنید.
  • کلمات را از یک دیکشنری با استفاده از درخت پیشوندی فرم‌دهی کنید.
  • یک دیکشنری T9 بسازید.

جدول درهم‌سازی

درهم‌سازی (Hashing) فرآیند مورد استفاده برای شناسایی اشیا و ذخیره‌سازی هر شی در اندیس‌های یکتا از پیش محاسبه شده است که به آن‌ها «کلید» (key) گفته می‌شود. بنابراین، شی به شکل جفت کلید-مقدار (key-value) و مجموعه‌ای از چنین آیتم‌هایی که به آن دیکشنری گفته می‌شود ذخیره‌سازی می‌شود. هر شی با استفاده از آن کلید قابل جست‌و‌جو است. ساختمان داده‌های متفاوتی بر پایه درهم‌سازی وجود دارند، اما پر استفاده‌ترین آن‌ها جدول درهم‌سازی است. جدول درهم‌سازی معمولا با استفاده از آرایه‌ها پیاده‌سازی می‌شود.

کارایی ساختمان داده درهم‌سازی بستگی به سه فاکتور زیر دارد:

  • تابع درهم‌سازی (hash function)
  • اندازه جدول درهم‌سازی
  • روش مدیریت تصادم (Collision Handling Method)

در تصویر زیر چگونگی نگاشت درهم‌سازی در یک آرایه نمایش داده شده است. اندیس این آرایه از طریق یک تابع درهم‌سازی محاسبه می‌شود.

جدول درهم‌سازی

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

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

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

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

^^

آیا این مطلب برای شما مفید بود؟