چرا یادگیری ساختمان داده‌ها برای هر برنامه‌نویسی ضروری است؟

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

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

الگوریتم چیست؟

یکی از مفاهیم مهمی که ارتباط نزدیکی با ساختمان داده‌ها دارد، الگوریتم است. الگوریتم (Algorithm) به‌معنای یک ترتیب روشن، دقیق، بدون ابهام و قابل اجرای مجموعه دستوراتی است که برای انجام کار و هدفی نوشته می‌شوند. الگوریتم‌ها با هدف حل یک مسئله بر مبنای انجام یکسری کارها نوشته می‌شوند.

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

• گام اول: آغاز.
• گام 2: عدد دلخواه اول را دریافت کن و در متغیری قرار بده. 
• گام 3: عدد دلخواه دوم را دریافت کن و در متغیر دیگری قرار بده.
• گام 4: دو عدد را در یک‌دیگر ضرب کن و خروجی را در متغیر دیگری قرار بده. 
• گام 5: مقدار متغیر خروجی را چاپ کن. 
• گام 6. پایان.

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

چه ساختارهای داده‌ای اهمیت بیشتری در دنیای برنامه‌نویسی دارند؟ 

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

آرایه (Array)

آرایه، اولین و ساده‌ترین ساختمان داده در تمامی زبان‌های برنامه‌نویسی است که بیش از نمونه‌های دیگر استفاده می‌شود. ساختمان داده‌های پرکاربرد مثل پشته و صف انشعاباتی از آرایه‌ها هستند. آرایه‌ها می‌توانند اندازه و ابعاد مختلف داشته باشند. هر عنصر داده با یک مقدار عددی که از صفر شروع می‌شود شناسایی می‌شود. به این مقدار در اصطلاح شاخص (Index) می‌گویند که موقعیت یک عنصر در آرایه را نشان می‌دهد. در بیشتر زبان‌های برنامه‌نویسی شاخص آرایه با مقدار 0 آغاز می‌شود. به‌طور مثال، در شکل ۱، آرایه‌ای با چهار عضو را مشاهده می‌کنید. 

در آرایه شکل ۱، شاخص خانه‌ای که مقدار ۱ دارد برابر با 0 است، خانه‌ای که عدد ۲ دارد، شاخص 1 دارد، خانه‌ای که عدد ۳ دارد شاخص 2 و خانه‌ای که مقدار ۴ را دارد شاخص 3 را دارد. آرایه‌ها به دو نوع آرایه‌های تک‌بعدی و آرایه‌های چند‌بعدی (آرایه‌ای از آرایه‌ها) تقسیم می‌شوند. 

شکل ۱

عملیات اصلی قابل انجام روی آرایه‌ها

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

• اضافه کردن (Insert ): به فرآیند درج یک عنصر در خانه‌ای که شاخص آن مشخص شده اشاره دارد. 
• دریافت (Get): عنصر موجود در خانه‌ای که شاخص آن مشخص شده را باز می‌گرداند.
• حذف (Delete): مقدار خانه‌ای که شاخص آن مشخص شده را حذف می‌کند.
• اندازه (Size): تعداد کل عناصر موجود در آرایه را نشان می‌‌دهد. 

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

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

پشته (Stack)

یکی از پرکاربردترین دکمه‌هایی که همه ما روزی چند مرتبه در برنامه‌ها آن‌را فشار می‌دهیم، دکمه Undo است، اما تنها تعداد کمی از افراد درباره عملکرد این دکمه اطلاعات دقیقی دارند. ایده اصلی پنهان در پس Undo این است که وضعیت قبلی کاری که کاربر انجام داده را در حافظه ذخیره می‌‌کند. البته محدودیتی در ارتباط با تعداد حالت‌هایی که ذخیره می‌شوند وجود دارند، زیرا این فرآیند به‌طور کامل در حافظه اصلی انجام می‌شود و هیچ برنامه‌ای تلاش نمی‌کند بخش بزرگی از حافظه را برای این منظور اشغال کند. این داده‌ها به‌شکلی ذخیره می‌شوند که آخرین داده ذخیره‌شده، اول نمایش داده می‌شود. آرایه‌ها قادر به انجام این‌کار نیستند و بنابراین، مفهومی به‌نام پشته (Stack) ابداع شد. برای آن‌که شناخت بهتری از عملکرد پشته پیدا کنیم بهتر است به یک مثال واقعی اشاره کنیم. فرض کنید، دسته‌ای از کتاب‌ها دارید که روی هم قرار گرفته‌اند. برای برداشتن کتابی که در وسط قرار دارد، ابتدا باید همه کتاب‌هایی که روی کتاب موردنظر قرار دارند را بردارید تا به کتاب‌تان برسید؛ به این فرآیند در دنیای برنامه‌نویسی، «آخرین ورودی اولین خروجی» (LIFO) سرنام Last In First Out گفته می‌شود. در شکل ۲، یک پشته شامل سه مقدار 1، 2 و 3 را مشاهده می‌کنید که مقدار 3 در بالا قرار دارد و در نتیجه اول از عناصر دیگر حذف می‌شود. 

شکل 2

عملیات اصلی قابل انجام روی پشته

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

• Push : به فرآیند اضافه کردن یک عنصر به بالای پشته، پوش گفته می‌شود.
• Pop : به فرآیند حذف عنصری از بالای پشته، پاپ گفته می‌شود. در فرآیند حذف عنصر، مقدار آن بازگردانده می‌شود؛ به‌بیان دیگر، عنصر از پشته حذف می‌شود و به‌عنوان مقدار برگشتی قابل دستیابی است. 
• IsEmpty: وضعیت پشته را به‌لحاظ خالی یا پر بودن بررسی می‌کند. اگر پشته خالی باشد مقدار صحیح (True) را بر می‌گرداند. 
• Top: عنصر بالایی از پشته را باز می‌گرداند، بدون آن‌که عنصر از پشته حذف شود. 

همانند آرایه‌ها پرسش‌هایی نیز در ارتباط با پشته‌ها از برنامه‌نویسان پرسیده می‌شود که از مهم‌ترین آن‌ها به موارد زیر باید اشاره کرد: 

•  چگونه عبارت پسوندی را با استفاده از پشته بررسی کنیم؟
•  چگونه مقادیر موجود در یک پشته را مرتب‌سازی کنیم؟ 
•  در مبحث پشته چگونه توازن پرانتزهای یک عبارت را بررسی می‌کنید؟

صف (Queue)

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

شکل 3

عملیات اصلی قابل اجرا روی صف

• اضافه‌کردن (Enqueue): به اضافه کردن عنصر به انتهای صف اشاره دارد. 
• حذف (Dequeue): اولین عنصر صف را حذف و به‌عنوان مقدار بازگشتی ارسال می‌کند. 
• isEmpty: اگر هیچ عنصری در صف وجود نداشته باشد، مقدار صحیح (True) را بر می‌گرداند.
• Top: اولین عنصر صف را بر می‌گرداند، اما در این‌جا برعکس پشته هیچ عنصری حذف نمی‌شود. 

در ارتباط با صف نیز پرسش‌هایی مطرح است که از مهم‌ترین آن‌ها به موارد زیر باید اشاره کرد: 

• اگر در نظر داشته باشیم پشته را با استفاده از صف پیاده‌سازی کنیم چگونه این‌کار را انجام دهیم؟ 
•  چگونه k عنصر اول از یک صف را باید معکوس کنیم؟
•  چگونه اعداد باینری از 1 تا n را از طریق صف ایجاد کنیم؟

لیست پیوندی (Linked List)

لیست پیوندی یکی از مهم‌ترین ساختمان داده‌های خطی مهم است که اگر تصمیم به یادگیری زبان‌هایی مثل سی‌پلاس‌پلاس دارید، باید اطلاعات کاملا دقیقی در ارتباط با آن کسب کنید. لیست‌های پیوندی در ظاهر شباهت زیادی به آرایه‌ها دارند، اما در مباحثی مثل تخصیص حافظه، ساختار داخلی که بر مبنای آن ساخته می‌شوند و عملیات اصلی مثل اضافه و حذف کردن تفاوت‌های زیادی با آرایه‌ها دارند. یک لیست پیوندی، زنجیره‌ای از گره‌ها (Nodes) را شکل می‌دهد که هر گره دو نوع اطلاعات را نگه‌داری می‌کند. نوع اول اطلاعات واقعی مثل مقادیر هستند و نوع دوم اشاره‌گری است که به گره بعدی در زنجیره اشاره دارد. در لیست‌های پیوندی، یک اشاره‌گر سر (Head) وجود دارد که به آن رأس گفته می‌شود و به اولین عنصر لیست پیوندی اشاره دارد. اگر لیست خالی باشد گره رأس به تهی (Null) اشاره می‌کند. لیست‌های پیوندی برای پیاده‌سازی سیستم فایل‌ها، جداول درهم‌ساز و لیست‌های همسایگی استفاده می‌شوند. در شکل ۴، ساختار یک لیست پیوندی را مشاهده می‌کنید.

شکل 4

همان‌گونه که اشاره کردیم، لیست‌های پیوندی یکی از مهم‌ترین مفاهیم ساختمان داده‌ها در زبان‌هایی مثل سی‌پلاس‌پلاس هستند و بنابراین یادگیری آن‌ها ضروری است. در واقع، اگر به دنیای برنامه‌نویسی سی‌پلاس‌پلاس وارد شوید، بدون شک با انواع مختلف لیست‌های پیوندی کار می‌کنید. لیست‌های پیوندی به انواع مختلفی مثل لیست تک‌پیوندی (یک‌طرفه)، لیست دوپیوندی (دو‌طرفه) و لیست‌های حلقوی تقسیم می‌شوند که در این میان پیاده‌سازی لیست‌های حلقوی و به‌ویژه حلقوی دوطرفه که ترکیبی از لیست پیوندی دوطرفه و حلقوی است پیچیده‌تر از نمونه‌های دیگر است و حتما باید ابتدا الگوریتمی برای پیاده‌سازی آن‌ها تعریف کنید و بعد کدنویسی را انجام دهید؛ در غیر این‌صورت در پیاده‌سازی با مشکل روبرو می‌شوید. 

عملیات اصلی قابل اجرا روی لیست پیوندی

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

• InsertAtEnd: مقداری را به انتهای لیست پیوندی اضافه می‌کند. 
• Delete : یک عنصر داده‌ای را از لیست پیوندی حذف می‌کند.
• DeleteAtHead : اولین عنصر لیست پیوندی که رأس نام دارد را حذف می‌کند.
• isEmpty: در صورت خالی بودن، مقدار صحیح (True) را برمی‌گرداند. 

از مهم‌ترین پرسش‌های مطرح در ارتباط با لیست‌های پیوندی به موارد زیر باید اشاره کرد:

•  چگونه یک لیست پیوندی را معکوس کنیم؟
•  چگونه وجود حلقه در لیست پیوندی را باید شناسایی کنیم؟
•  چگونه باید n‌امین گره از پایان را از یک لیست پیوندی برگردانیم؟
•  چگونه مقادیر تکراری را باید از یک لیست پیوندی حذف کنیم؟

گراف‌ها (Graphs)

گراف شبکه‌ای از گره‌های متصل به یک‌دیگر است که متشکل از یک جفت (x,y) هستند که یال نام دارند و ارتباط رأس x با رأس y را برقرار می‌کنند. به‌طور معمول، یک یال، وزن یا هزینه دارد که نشان می‌دهد چه هزینه‌ای برای رفتن از رأس x به y وجود دارد. محاسبه این هزینه در حوزه‌هایی مثل شبکه که قرار است بسته‌های اطلاعاتی در کوتاه‌ترین زمان از مقصد به مبدا برسد اهمیت دارد. شکل ۵، چند نمونه از گراف‌ها را نشان می‌دهد. 

گراف‌ها مشابه لیست‌های پیوندی انواع مختلفی مثل گراف‌های بدون جهت و گراف‌های جهت‌دار دارند. در زبان‌های برنامه‌نویسی، گراف‌ها در قالب ماتریس همسایگی یا لیست همسایگی نشان داده می‌شوند و از طریق الگوریتم‌های محبوبی مثل الگوریتم «جست‌و‌جوی اول سطح» (Breadth First Search) و الگوریتم «جست‌و‌جوی عمق اول» (Depth  First Search) پیمایش می‌شوند. 

شکل 5

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

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

درخت (Tree) 

درخت یکی از کاربردی‌ترین ساختمان‌های داده‌ است که کاربردهای مختلفی دارد. به‌طور مثال، بازی‌های محبوبی مثل شطرنج بر مبنای درخت‌ها پیاده‌سازی می‌شوند و جالب آن‌که تخمین پیچیدگی درخت از خود پیاده‌سازی آن مهم‌تر است. درخت، سلسله‌ مراتبی از رأس‌ها (گره‌ها) و یال‌های متصل به یک‌دیگر است. درخت‌ها عملکردی شبیه به گراف‌ها دارند، اما یکسان نیستند. درخت‌ها فاقد دور یا حلقه (Cycle) هستند، در حالی‌که گراف‌ها می‌توانند دارای دور باشند. درخت‌ها بیشتر در مباحث مرتبط با الگوریتم‌های هوشمند و پروژه‌هایی که ساختار پیچیده‌ای دارند استفاده می‌شوند. در شکل ۶، یک درخت ساده را مشاهده می‌کنید. درخت‌ها مشابه دیگر ساختمان داده‌ها به انواع مختلفی تقسیم می‌شوند که از مهم‌ترین آن‌ها باید به درخت متوازن یا متعادل‌شده، درخت باینری، درخت جست‌و‌جوی دودویی، درخت با ارتفاع متوازن، درخت سرخ‌سیاه و درخت ۲-۳ اشاره کرد. با این‌حال، امروزه درخت دودویی و درخت جست‌و‌جوی دودویی کاربرد گسترده‌ای در حوزه توسعه نرم‌افزارها دارند. 

از پرسش‌های ممکن مرتبط با درخت‌ها باید به موارد زیر اشاره کرد: 

• چگونه ارتفاع درخت دودویی را محاسبه کنیم؟
•  چگونه مقدار بیشینه در یک درخت جست‌و‌جوی باینری را پیدا می‌کنید؟
•  چگونه گره‌هایی که k فاصه از ریشه دارند را پیاده می‌کنید؟
•  چگونه والدهای یک گره در درخت باینری را پیدا می‌کنید؟

شکل 6

درخت پیشوندی (Prefix Tree)

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

شکل 7

از پرسش‌های مهم در ارتباط با درخت‌های پیشوندی به موارد زیر باید اشاره کرد:

•  چگونه تعداد کل کلمات در درخت پیشوندی را محاسبه کنیم؟
• چگونه به کلمات ذخیره‌شده در درخت پیشوندی دسترسی پیدا کنیم؟ 
•  چگونه  کلمات یک لغت‌نامه را بر مبنای درخت پیشوندی قالب‌بندی می‌کنید؟

کلام آخر

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