الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب آموزش ساختمان داده‌ها نوشته‌ها با برچسب آموزش ساختمان داده‌ها - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

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

»

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

در ادامه با انواع این نوع ساختمان داده‌ها در زبان برنامه‌نویسی ++C نسخه‌ی C++11 آشنا می‌شویم. با توجه به گسترده بودن این بحث، جزئیات بیشتر هر کلاس را در «پیوندها برای مطالعه‌ی بیشتر» بخوانید.

ادامه ...

درخت دودویی (Binary Tree)

درختی است که هر گره آن دارای حداکثر دو گره فرزند است که به آنها فرزند راست و چپ گره گفته می‌شود. به همین ترتیب زیردرختی که فرزند راست در رأس آن قرار دارد زیردرخت راست و زیردرختی که فرزند چپ در رأس آن قرار دارد زیردرخت چپ گره نامیده می‌شوند.

  

درخت دودویی

  

درخت جستجوی دودویی (Binary Search Tree - BST)

درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:

ادامه ...

صف اولویت‌دار (یا صف اولویتی - Priority Queue) از جمله ساختمان داده‌های بسیار پرکاربرد است. در صف عادی از تکنیک FIFO - مخفف First In First Out - استفاده می‌شود. در این تکنیک، مثل یک صف نانوایی، داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده‌ی ورودی، اولین داده‌ی خروجی نیز خواهد بود. اما در صف اولویت‌دار برای هر داده، اولویتی - نه لزوما منحصربفرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم عامل کامپیوتر هم برای مدیریت پردازش‌ها از صف‌های اولویت‌دار استفاده می‌کند.

ادامه ...

درخت دودویی کامل

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

  

به یک مثال دقت کنید:

  

درخت هیپ یا هرم یا کپه

  

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

ادامه ...

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

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

ادامه ...

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

به قطعه کد زیر توجه کنید:

  

int **table;
cin >> n;
table = new int*[n];
int i, j;
for (i = 1 ; i <= n ; i++){
  table[i - 1] = new int[i];
  for (j = 1 ; j <= i ; j++)
    table[i - 1][j - 1] = i * j;
}
10 .
11 .
12 .
13 for (i = 0 ; i < n ; i ++)
14   delete[] table[i];
15 delete[] table;
16   

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

ادامه ...

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

  

type name[number of elements];

  

که در آن type یکی از انواع داده‌های استاندارد ++C، ساختمان و یا کلاس است. number of elements هم تعداد اعضا یا عناصر آرایه را مشخص می‌کند که باید عدد ثابتی باشد. مثلا عبارت زیر یک آرایه‌ی 10 عضوی از اعداد اعشاری به نام arr تعریف می‌کند:

ادامه ...

الگوریتمستان در تلگرام

   

 

پیوند کوتاه:
»  دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد
ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
»  مستندات دوره‌ی آمادگی مسابقات برنامه‌نویسی دانشگاه استنفورد
مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
»  کتاب الکترونیکی ساختمان داده‌ها
معرفی کتاب آموزش الکترونیکی رایگان «ساختمان داده‌ها» به زبان فارسی با قابلیت دانلود
برچسب‌ها
#آمادگی المپیاد کامپیوتر #آموزش الگوریتم #الگوریتم‌های مرتب‌سازی #نکات برنامه‌نویسی #پیمایش گراف #درخت‌ها #الگوریتم‌های بازگشتی #الگوریتم‌های گراف #سوالات مسابقات برنامه‌نویسی بیان #جستجوی اول عمق #نمونه سوالات مسابقه برنامه‌نویسی #محاسبات ریاضی #الگوریتم فلوید-وارشال #کتاب مسابقات برنامه‌نویسی #گراف #کتاب الکترونیکی #الگوریتم‌های برنامه‌نویسی پویا #نمونه سوال مسابقه ACM #حل سوالات ACM-ICPC #ترجمه‌ی فارسی سوالات UVa Online Judge #مسئله‌های برنامه‌نویسی #درخت پوشا #نمونه سوال فارسی مسابقات ACM #مسابقات برنامه‌نویسی ACM #برنامه‌نویسی ++C #الگوریتم دایکسترا #الگوریتم #تمرین مسابقه‌ی برنامه‌نویسی ای‌سی‌ام #آمادگی مسابقه ACM #ماتریس #صف #مسئله‌های الگوریتمی #آموزش برنامه‌نویسی ++C #الگوریتم‌های حریصانه #منبع آموزشی #آموزش طراحی الگوریتم #حل سوالات Timus Online Judge #آموزش ساختمان داده‌ها #تمرین مسابقه برنامه‌نویسی #برنامه‌نویسی #ترجمه‌ی فارسی سوالات ACM #معرفی وب‌سایت #مسأله‌های برنامه‌نویسی #کتابخانه قالب استاندارد ++C #الگوریتم‌های عقبگرد #سوالات UVa Online Judge #مسأله‌های الگوریتمی #الگوریتم‌های تقسیم و غلبه #وبلاگ #ترجمه فارسی سوالات کتاب Programming Challenges #سوالات برنامه‌نویسی #مسابقه برنامه‌نویسی #سوالات چالشی برنامه‌نویسی #حل سوالات مسابقات برنامه‌نویسی #مسئله‌ی کوله‌پشتی #نمونه سوال فارسی مسابقات برنامه‌نویسی #مسابقات برنامه‌نویسی #کتاب الگوریتم #نمونه سوال فارسی مسابقه‌ی ACM #سوالات مسابقات ACM-ICPC #الگوریتم‌های کوتاهترین مسیر #تمرین المپیاد کامپیوتر #تکنیک‌های طراحی الگوریتم #ویدئوی آموزشی #ترجمه‌ی فارسی سوالات برنامه‌نویسی #جستجوی اول سطح #آمادگی مسابقه برنامه‌نویسی #تمرین طراحی الگوریتم #ساختمان داده #دانلود کتاب #الگوریتم‌های مسیریابی #مسابقه برنامه نویسی #حل سوالات UVa Online Judge #حل مسئله‌‌ی الگوریتمی