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

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

دوره آموزش ساختمان داده

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

سرفصل‌های دوره آموزش ساختمان داده

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

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

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

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

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

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

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

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

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

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

انواع ساختمان داده

انواع مختلف ساختمان داده وجود دارد که عبارت‌اند از:

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

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

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

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

• سیستم‌عامل
• گرافیک
• طراحی کامپیوتر
• بلاک چین
• ژنتیک
• پردازش تصویر
• هوش مصنوعی
• شبیه‌سازی و غیره

انواع ساختارهای داده

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

آرایه‌ها

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

ویژگی‌های یک آرایه

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

• آرایه‌ها از ساختمان داده مبتنی بر اندیس استفاده می‌کنند که به شناسایی آسان هر یک از عناصر آرایه با استفاده از اندیس کمک می‌کند.
• اگر کاربر بخواهد چندین مقدار از یک نوع داده را ذخیره کند، می‌توان از آرایه به‌طور موثر استفاده کرد.
• آرایه همچنین می‌تواند با ذخیره‌سازی داده‌ها در یک آرایه دوبعدی، ساختارهای داده پیچیده را مدیریت کند.
• آرایه همچنین برای پیاده‌سازی سایر ساختارهای داده مانند Stacks ،Queues ،Heaps ،Hash جداول و غیره استفاده می‌شود.
• فرآیند حذف و جستجو در آرایه را می‌توان بسیار آسان انجام داد.

در دوره آموزش ساختمان داده ما به‌صورت کامل با این ساختار داده آشنا خواهیم شد.

کاربردهای آرایه:

کاربردهای مختلف آرایه به شرح زیر است:

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

لیست پیوندی

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

ویژگی‌های لیست پیوندی

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

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

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

کاربردهای لیست پیوندی

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

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

پشته

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

ویژگی‌های پشته

پشته دارای ویژگی‌های مختلفی است که به شرح زیر است:

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

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

کاربردهای Stack

کاربردهای مختلف Stack به شرح موارد زیر است:

• ساختمان داده پشته‌ای در ارزیابی و تبدیل عبارات حسابی استفاده می‌شود.
• Stack در Recursion استفاده می‌شود.
• هنگام معکوس کردن رشته، از پشته استفاده می‌شود.
• Stack در مدیریت حافظه استفاده می‌شود.
• برای پردازش فراخوانی تابع استفاده می‌شود.
• پشته برای تبدیل عبارات از infix به postfix استفاده می‌شود.
• پشته برای انجام عملیات خنثی‌سازی و همچنین انجام مجدد عملیات در پردازشگرهای کلمه استفاده می‌شود.
• پشته در ماشین‌های مجازی مانند JVM استفاده می‌شود.
• پشته در عملیات بازگشتی استفاده می‌شود.
• و بسیاری دیگر از کاربردهای مختلف.

 صف

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

ویژگی‌های صف در ساختمان داده

صف دارای ویژگی‌های مختلفی است که به شرح زیر است:

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

کاربردهای صف

کاربردهای مختلف Queue به شرح زیر است:

• صف برای مدیریت ترافیک وب‌سایت استفاده می‌شود.
• صف به حفظ لیست پخش در پخش‌کننده‌های رسانه کمک می‌کند.
• از صف در سیستم‌عامل ها برای مدیریت وقفه‌ها استفاده می‌شود.
• صف به ارائه درخواست‌ها در یک منبع مشترک مانند چاپگر، زمان‌بندی وظایف CPU و غیره کمک می‌کند.
• در انتقال ناهم‌زمان داده‌ها برای مثال استفاده می‌شود.
• صف‌ها برای زمان‌بندی کار در سیستم‌عامل استفاده می‌شوند.
• برای ارسال ایمیل صف از ساختمان داده استفاده می‌شود.

درخت دودویی

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

درخت جستجوی دودویی

درخت جستجوی دودویی نوعی درخت باینری است که دارای ویژگی‌های اضافی است:

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

درخت باینری که دارای ویژگی‌های زیر باشد به درخت جستجوی دودویی (BST) معروف است.

ویژگی‌های درخت

درخت دارای ویژگی‌های مختلفی است که به شرح زیر است:

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

کاربردهای درخت

کاربردهای مختلف Tree به شرح موارد زیر است:

• Heap نوعی ساختمان داده درختی است که با استفاده از آرایه‌ها پیاده‌سازی می‌شود و برای اجرای صف‌های اولویت استفاده می‌شود.
• B-Tree و B+ Tree برای پیاده‌سازی نمایه‌سازی در پایگاه‌های داده استفاده می‌شوند.
• Syntax Tree به اسکن، تجزیه، تولید کد و ارزیابی عبارات حسابی در طراحی کامپایلر کمک می‌کند.
• درختان پوشا در روترها در شبکه‌های کامپیوتری استفاده می‌شوند.
• و بسیاری از موارد دیگر

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

ساختمان داده هیپ Heap

Heap نوعی ساختمان داده ویژه مبتنی بر درخت به‌حساب می‌آید که در آن درخت نوعی درخت باینری کامل است. به‌طورکلی، Heaps می‌تواند دو نوع باشد:

1. Max-Heap: در یک Max-Heap، کلید موجود در گره ریشه باید در بین کلیدهای موجود در همه فرزندان آن بیشترین باشد. همان ویژگی باید به‌صورت بازگشتی برای همه زیر درخت‌های آن درخت دودویی صادق باشد.

2. Min-Heap: در Min-Heap، کلید موجود در گره ریشه باید در بین کلیدهای موجود در همه فرزندان آن حداقل باشد. همان ویژگی باید به‌صورت بازگشتی برای همه زیردرخت‌های آن درخت دودویی صادق باشد.

ساختمان داده‌ هشینگ

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

ماتریس

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

گراف

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

ویژگی‌های گراف

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

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

کاربردهای گراف

کاربردهای مختلف گراف به شرح زیر است:

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

الگوریتم‌های مرتب‌سازی در ساختمان داده

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

• مرتب‌سازی درجی
• مرتب‌سازی انتخابی
• مرتب‌سازی حبابی
• مرتب‌سازی ادغامی
• مرتب‌سازی سریع

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

دوره‌های مرتبط:

• آموزش مقدماتی زبان برنامه نویسی r
• آموزش طراحی الگوریتم
• آموزش شناسایی آماری الگو