معرفی درس ساختمان داده (data structure)
درس ساختمان داده اساسی ترین درس رشته کامپیوتر و می توان گفت در رشته هایی همانند علوم پایه و مهندسی هم این درس بنیادی است. هدف از درس ساختمان داده ها تحقیق و بررسی در مورد روش های گوناگون بازیابی، ذخیره، نگهداری اطلاعات در کامپیوتر است. این درس در جهت استفاده کار آمد از اطلاعات مورد استفاده قرار می گیرد. از یک دید میتوان گفت دانشجویانی که به کارهای پژوهشی یا طراحی الگوریتم و یا چالشهای موجود در برنامه نویسی علاقه دارند، ساختمان داده و طراحی الگوریتم باعث داشتن یک نگاه ویژه به به حل مسائل می شود. داشتن دید حل مسئله دانشجویان را متمایز از هم می سازد.
با مطالعه درس ساختمان داده خواهید فهیمد که آیا راه حل مسائل از جوانب گوناگون مانند مرتبه زمانی، میزان مصرف حافظه، میزان مصرف توان، قابلیت توسعه و جوانب دیگر آیا بهینه هستند؟
سرفصل‌های ساختمان داده
فصل اول: الگوریتم ها
- تعریف الگوریتم
- تفاوت الگوریتم و برنامه
- تحلیل برنامه ها
- حالت های ورودی
- تحلیل پیچیدگی زمانی مرتب سازی درجی
- نمایش بی اهمیت بودن ضرایب
- نماد های مجانبی
- تابع بازگشتی
- مرتبه زمانی توابع بازگشتی
- حل معادلات بازگشتی (روش جایگذاری، درخت بازگشت، تغییر متغیر با معادله شاخص _معادلات بازگشتی خطی همگن و غیر همگن، قضیه اصلی یا master theorem)
فصل دوم: آرایه ها
- تعریف آرایه
- ذخیره سازی آرایه
- ماتریس ها (ماتریس بالا مثلثی، ماتریس پایین مثلثی، ماتریس اسپارس)
- ترانهاده ماتریس اسپارس
- ضرب ماتریس ها (محاسبه بهینه ترین تعداد ضرب در ضرب ماتریس ها)
فصل سوم: پشته و صف
- تعریف پشته
- پیاده سازی پشته ( توابع push , pop)
- پشته دوگانه
- تعریف عبارات محاسباتی (میانوندی – پسوندی – پیشوندی)
- الگوریتم محاسبه مقدار عبارت پسوندی
- تبدیل عبارات میانوندی به پسوندی (با پرانتزگذاری)
- تبدیل عبارات میانوندی به پیشوندی (با پرانتزگذاری)
- تبدیل عبارات میانوندی به پسوندی (با پشته)
- تبدیل عبارات میانوندی به پیشوندی (با پشته)
- تبدیل عبارات پسوندی به میانوندی (با پرانتزگذاری)
- تبدیل عبارات پیشوندی به میانوندی (با پرانتزگذاری)
- تبدیل عبارات پسوندی به میانوندی (با پشته)
- تبدیل عبارات پیشوندی به میانوندی (با پشته)
- تبدیل عبارت پسوندی به پیشوندی و برعکس
- تعریف صف خطی
- پیاده سازی صف خطی
- تابع درج به صف خطی
- تابع حذف از صف خطی
- تعریف صف حلقوی
- تابع درج به صف حلقوی
- تابع حذف از صف حلقوی
فصل چهارم: لیست پیوندی
- تعریف لیست پیوندی
- پیاده سازی لیست پیوندی
- اعمال اصلی لیست پیوندی (جستجو، درج در ابتدا، درج بعد از یک عنصر خاص، درج قبل از یک عنصر خاص، حذف، معکوس کردن لیست پیوندی، مرتب سازی حبابی لیست پیوندی)
- تعریف لیست پیوندی حلقوی
- جستجو در لیست پیوندی حلقوی
- اعمال اصلی برای لیست پیوندی حلقوی
- بررسی توابع اصلی لیست پیوندی برای حالت های مختلفfirst
- تعریف لیست پیوندی دوطرفه
- حذف از لیست پیوندی دوطرفه
- درج به لیست پیوندی دوطرفه
- پیاده سازی پشته و صف با لیست پیوندی (توابع push و pop برای پشته و insert و delete برای صف)
فصل پنجم: درخت ها
- تعاریف اولیه
- نمایش درخت ها (لیست پیوندی، فرزند چپ – همزاد راست، درخت درجه دو)
- درخت های دودویی( تعاریف اولیه، نمایش با آرایه، نمایش با لیست پیوندی، پیمایش درخت دودویی ( پیش ترتیب – پس ترتیب – میان ترتیب )، درخت عبارت، به دست آوردن درخت از روی پیمایش ها)
- الگوریتم هایی برای درخت دودویی: کپی کردن درخت، ارتفاع درخت، معکوس کردن درخت، محاسبه تعداد برگ های درخت، محاسبه تعداد گره های درخت
- Heap درخت ( تعاریف اولیه، پیاده سازی، درج و حذف و جستجو در Heap، محاسبه تعداد اعداد بزرگتر از یک عدد خاص در Heap )
- درخت جستجوی دودویی (تعاریف اولیه، درج و حذف و جستجو در BST، ارتفاع درخت BST)
- AVL درخت (تعاریف اولیه، درج و حذف در AVL، انواع چرخش در AVL)
- جنگل ها
- تبدیل جنگل به درخت دودویی
فصل ششم: گراف ها
- تعاریف اولیه
- روش های نمایش گراف ها
- پیمایش گراف ها ( BST – DFS )
- درخت پوشا
- درخت پوشای کمینه
- الگوریتم راشال
- الگوریتم پرایم
فصل هفتم: مرتب سازی
- تعاریف اولیه
- مرتب سازی درجی
- مرتب سازی حبابی
- مرتب سازی انتخابی
- مرتب سازی سریع
- مرتب سازی شمارشی
دلیل اهمیت یادگیری ساختمان داده‌ها
- بهینه‌سازی عملیات: استفاده از ساختمان داده‌های مناسب به ما کمک می‌کند تا عملیات مختلف را به طور بهینه‌تر و با زمان اجرای کمتر انجام دهیم. این امر برای برنامه‌هایی که با حجم بزرگی از داده سروکار دارند و کارایی مهم است.
- حافظه‌ی بهتر: استفاده از ساختمان داده‌های مناسب می‌تواند کمک کند تا حافظه مورد نیاز برنامه کاهش یابد. این امر مخصوصاً برای سیستم‌هایی که با محدودیت‌های حافظه روبرو هستند مهم است.
- راهنمایی در طراحی الگوریتم: یادگیری ساختمان داده‌ها به ما در طراحی بهتر الگوریتم‌ها کمک می‌کند. انتخاب ساختمان داده صحیح می‌تواند منجر به الگوریتم‌های بهتر و کارآمدتر شود.
ارتباط بین درس ساختمان داده و طراحی الگوریتم
دروس ساختمان داده و طراحی الگوریتم بسیار نزدیک هستند و ارتباط مستقیمی با هم دارند. بسیاری از اساتید دانشگاه بحث ها همانند رشد توابع، مرتبه زمانی و شبه کدها ، الگوریتم های بازگشتی و مرتب سازی در هر دو دوره تدریس میشوند. .
به طور کلی میتوان گفت که درس ساختمان داده پیش نیاز درس طراحی الگوریتم می باشد بنابراین مطالعه درس ساختمان داده قبل از درس طراحی الگوریتم موجب یادگیری راحت تر این دروس می شود.
کاربردهای ساختمان داده
ساختمان داده‌ها در بسیاری از زمینه‌ها و کاربردهای مختلف استفاده میشوند، از جمله:
- برنامه‌نویسی و توسعه نرم‌افزار
- پایگاه‌داده‌ها و سیستم‌های مدیریت داده
- شبکه‌های اجتمی، اینترنت و طراحی پروتکل‌ها
- الگوریتم‌ها و هوش مصنوعی
- سیستم‌های عامل و مدیریت حافظه
- گرافیک کامپیوتری و شبیه‌سازی‌ها
- بهینه‌سازی و بهینه‌سازی مسائل
- تحلیل الگوریتم‌ها و پیچیدگی زمانی
