ساختمان داده (Data Structure) چیست؟ آموزش صفر تا صد درس ساختمان داده

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

به ساختمان داده «ساختار داده» یا «داده‌ساختار» هم می‌گویند و هر سه نام به همین مفهوم اشاره دارند. ساختمان داده همچنین نام یکی از پایه‌ای‌ترین درس‌های رشتهٔ کامپیوتر است که معمولاً در ترم سوم کارشناسی ارائه می‌شود و در کنکور ارشد و دکتری کامپیوتر و آی‌تی جزو دروس ضریب ۴ است. این صفحه را تیم کنکور کامپیوتر بر پایهٔ تدریس استاد رامین رضوی نوشته است و برای هر ساختمان داده، تعریف، شبه‌کد عملیات مهم و فیلم آموزشی رایگان دارد.

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

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

تخفیف تا دوشنبه، ۲ شهریور

30% 1,800,000 تومان 1,260,000 تومان

رامین رضوی

۶۴ ساعت

خرید دوره

ویدیو نکته و تست ساختمان داده و طراحی الگوریتم

تخفیف تا دوشنبه، ۲ شهریور

30% 1,700,000 تومان 1,190,000 تومان

رامین رضوی

۶۶ ساعت

خرید دوره

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

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

هدف اصلی درس ساختمان داده و طراحی الگوریتم ارائه مبانی نظری مورد نیاز برای کسب مهارت لازم در حل مسئله (Problem Solving) به کمک کامپیوتر است، یک مهندس کامپیوتر و آی تی و یا فردی که برنامه نویسی می‌کند در طول تحصیل خود باید توانایی حل مسائل مختلف به کمک زبان‌های برنامه نویسی را فرا بگیرد و در واقع باید بتواند برنامه‌های مناسبی برای حل مسائل مختلف بنویسد.

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

1. ساختمان داده یا ساختمان داده های در نظر گرفته شده برای الگوریتم‌های برنامه مان
2. الگوریتم هایی که روی داده ها اجرا می‌شوند

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

برنامه‌ای خوب است که هم ساختمان داده مناسبی داشته باشد و هم از الگوریتم‌های بهینه تری استفاده کند. بعنوان مثال فرض کنید می‌خواهید برنامه‌ای بنویسید که 50 عدد صحیح از ورودی بگیرد و آنها را مرتب کند و در خروجی نمایش دهد، در این مثال بهترین ساختمان داده‌ای که می‌توانیم استفاده کنیم آرایه است (چون تعداد اعداد ورودی ثابت و مشخص است)، اما برای مرتب کردن این اعداد می‌توانیم از الگوریتم‌های مختلفی نظیر مرتب سازی حبابی (Bubble Sort)، مرتب سازی درجی (Insertion sort)، مرتب سازی سریع (Quick Sort)، مرتب سازی انتخابی (Selection Sort) و یا دیگر الگوریتم‌های مرتب سازی استفاده کرد.

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

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

نوع دادهٔ انتزاعی (ADT) و ساختمان داده

نوع دادهٔ انتزاعی (Abstract Data Type یا ADT) فقط می‌گوید روی داده‌ها چه عملیاتی انجام می‌شود، و ساختمان داده می‌گوید آن عملیات چگونه پیاده‌سازی شوند. مثلاً «پشته» یک ADT با عملیات Push، Pop و Top است؛ همین پشته را می‌توان با آرایه یا با لیست پیوندی پیاده‌سازی کرد. برنامه‌ای که از پشته استفاده می‌کند لازم نیست بداند پشته درونش چطور ساخته شده؛ این جداسازی، کد را ساده‌تر و قابل تغییرتر می‌کند.

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

یک مثال ساده اهمیت ساختمان داده را نشان می‌دهد. فرض کنید می‌خواهید در میان یک میلیون شمارهٔ دانشجویی بگردید. اگر شماره‌ها در یک آرایهٔ نامرتب باشند، در بدترین حالت باید هر یک میلیون خانه را نگاه کنید. اگر همان داده‌ها در یک درخت جستجوی متوازن باشند، حدود ۲۰ مقایسه کافی است (چون log₂ 1,000,000 ≈ 20)، و در جدول درهم‌سازی به‌طور میانگین فقط چند مقایسه لازم است. داده‌ها همان است؛ فقط شیوهٔ سازمان‌دهی‌شان فرق کرده.

• سرعت: ساختمان دادهٔ درست، مرتبهٔ زمانی عملیات را عوض می‌کند، مثلاً از O(n) به O(log n) یا O(1).
• مصرف حافظه: بعضی ساختارها داده را فشرده‌تر نگه می‌دارند و بعضی برای سرعت، حافظهٔ بیشتری خرج می‌کنند. انتخاب بین این دو یک مصالحهٔ همیشگی است.
• سادگی الگوریتم: بسیاری از الگوریتم‌ها با ساختار مناسب ساده می‌شوند؛ مثلاً BFS با صف و الگوریتم دایجسترا با هیپ.
• مصاحبه و بازار کار: سؤال ساختمان داده و الگوریتم بخش ثابت مصاحبه‌های فنی شرکت‌های نرم‌افزاری است.
• کنکور و پژوهش: ساختمان داده و الگوریتم در کنکور ارشد و دکتری کامپیوتر و آی‌تی ضریب ۴ دارد و پایهٔ بیشتر مقاله‌های پژوهشی کامپیوتر است.

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

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

نوع داده‌های اولیه (Primitive Data Type)

داده ها در نرم افزارهای کامپیوتری یا در زبان‌های برنامه نویسی به شکل اولیه خودشون به شکل داده های اولیه ذخیره می‌شوند. نوع های داده اولیه (Primitive Or Base Data Type) ساده ترین نوع ساختمان داده ها هستند، نمونه ای از نوع های داده اولیه بصورت زیر است:

• Boolean : این نوع داده تنها می تواند دو مقدار true و false را به خودش بگیرد. از این نوع داده معمولا در شرط ها و حلقه ها استفاده می‌شود.
• Integer : یک متغیر از نوع داده Integer متغیری است که برای نگهداری اعداد صحیح که دارای اعشار نمی باشند، استفاده می گردد. نوع داده Integer با اندازه های مختلف رنج متفاوتی از اعداد را می‌تواند در خود ذخیره کند، بعنوان مثال یک Integer علامت دار 8 بیتی (signed 8-bit integer) مقادیر بین بازه -128 تا 127 را نگه می‌دارد و یک Integer بدون علامت 32 بیتی (unsigned long 32-bit integer) مقادیر بین بازه 0 تا 4,294,967,295 را نگه می‌دارد
• Floating-point numbers : نمایش فرمولی (formulaic representation) اعداد حقیقی را در کامپیوتر ذخیره می‌کند.
• Fixed-point numbers : در برخی از زبان های برنامه نویسی استفاده می‌شود و یک عدد حقیقی را به این صورت ذخیره می‌کند که مقدار صحیح اش و مقدار اعشارش جداگانه ذخیره می‌کند
• Character : این نوع داده می تواند کاراکتر های مختلف را در خودش ذخیره کند. این نوع داده معمولا در زبان های برنامه نویسی با کلمه ی char مشخص می‌شود و می تواند کاراکترهایی نظیر ‘A’ و ‘b’ و ‘ ‘ (فاصله) و ‘%’ و یا هر کاراکتر دیگری را در خودش ذخیره کند
• Pointer : اشاره‌گر به‌جای خودِ داده، آدرس یک خانهٔ حافظه را نگه می‌دارد. ساختمان داده‌های پویا مثل لیست پیوندی و درخت با همین اشاره‌گرها عناصر را به هم وصل می‌کنند.
• String : این داده می تواند رشته ای از کاراکترها را در خودش ذخیره کند. برای مثال این مدل داده می تونه رشته های “konkurcomputer” یا “Data Structure” یا “۱۳۵79” را در خودش ذخیره کند

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

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

انواع مختلفی از ساختمان داده (همان ساختار داده) وجود دارد که عموماً بر روی انواع داده های ابتدایی ساده تر ساخته شده است، در زیر به بررسی و معرفی انواع ساختمان داده می‌پردازیم:

1. آرایه (Array)
2. لیست پیوندی (Linked List)
3. پشته (Stack or Push Down List or Pile)
4. صف (Queue)
5. درخت (Tree) و درخت دودویی (Binary Tree)
6. درخت جستجوی دودویی (Binary Search Tree)
7. هرم (Heap)
8. جدول درهم‌سازی (Hash Table)
9. گراف (Graph)
10. مجموعه‌های مجزا (Disjoint Set)

دسته‌بندی ساختمان داده‌ها

ساختمان داده‌ها را از چند زاویه دسته‌بندی می‌کنند. دانستن این دسته‌ها کمک می‌کند ویژگی‌های هر ساختار را سریع‌تر به خاطر بسپارید:

• ابتدایی و غیرابتدایی: نوع‌های اولیه مثل int، char و boolean فقط یک مقدار نگه می‌دارند؛ ساختمان داده‌های غیرابتدایی مثل آرایه و درخت از کنار هم گذاشتن آن‌ها ساخته می‌شوند.
• خطی و غیرخطی: در ساختمان دادهٔ خطی هر عنصر حداکثر یک قبلی و یک بعدی دارد و می‌توان همه را در یک پیمایش پشت‌سرهم دید؛ در غیرخطی هر عنصر می‌تواند به چند عنصر وصل باشد.
• ایستا و پویا: اندازهٔ ساختار ایستا (مثل آرایهٔ معمولی) از ابتدا ثابت است؛ ساختار پویا (مثل لیست پیوندی) هنگام اجرا بزرگ و کوچک می‌شود.
• همگن و ناهمگن: در ساختار همگن (مثل آرایه) همهٔ عناصر یک نوع‌اند؛ در ساختار ناهمگن (مثل struct در C یا رکورد) عناصر می‌توانند نوع‌های مختلف داشته باشند.

برای مقایسهٔ دقیق‌تر این دو دسته، مقالهٔ ساختمان داده‌های خطی و غیرخطی را ببینید. جدول درهم‌سازی را معمولاً در هیچ‌کدام از این دو دسته نمی‌گذارند، چون عناصرش بر اساس خروجی تابع درهم‌سازی پخش می‌شوند، نه به ترتیب یا سلسله‌مراتب.

آرایه (Array)

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

تعریف آرایه:

آرایه مجموعه‌ای از داده‌هایی است که خصوصیات زیر را داشته باشد :

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

به زبان ریاضی، آرایه یک نگاشت (Mapping) از شاخص‌ها به عناصر داده‌ای است

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

انواع آرایه

1. آرایه تک بعدی
2. آرایه های چند بعدی

در فیلم زیر موارد زیر درس داده شده است:

1. بررسی تعداد عناصر، حافظه اشغالی و محاسبه آدرس شروع یک عنصر در آرایه تک بعدی
2. بررسی آرایه دو بعدی و محاسبه تعداد عناصر آن
3. بررسی انواع نحوه قرار گیری آرایه دو بعدی در حافظه
4. بررسی آرایه سه بعدی و محاسبه آدرس شروع یک عنصر در آرایه 3 بعدی
5. تدریس ماتریس پایین مثلثی
6. تدریس ماتریس 3 قطری

ساختمان داده آرایه

FindMax (A : integer[n]) : integer
  {
		  var maxIndex : integer ;
		  maxIndex = 1;
		  for i = 2 to n do
			  if A[i] > A[maxIndex] then
					  maxIndex = i;
		  return maxIndex;
  }
  

FindMax (A : integer[n]; ref maxIndex, ref minIndex : integer)
  {
		  maxIndex = 1;
		  minIndex = 1;
		  for i = 2 to n do
		  {
			  if A[i] > A[maxIndex] then
					  maxIndex = i;
			  else if A[i] < A[minIndex] then
					  minIndex = i;
		  }
  }
  

BinarySearch(L:ARRAY; n:integer; K:keyType): integer
  {
		  // L is a sorted list (increasing) of elements
		  // returns index of the matched element, or -1
		  // l= lower bound, u= upper bound, m = (l+u)/2
		  var l, u : integer;
		  l = 1;
		  u = n;
		  while l ≤ u do
		  {
			  m = (l + u) / 2;
			  if L[m] == k then
				  return m;
			  else if L[m] < k then
				  l = m + 1;
			  else
				  u = m - 1;
		  }
		  return -1;
  }
  

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

لیست پیوندی: لیست پیوندی ساختمان داده ای است که از یک تعداد نود تشکیل شده که هر نود یک رکورد شامل دیتا و آدرس نود بعدی است که به اصطلاح می‌گویند نود دارد به نود بعدی اشاره می‌کند، در لیست پیوندی هر نود می‌تواند در هر آدرسی از حافظه باشد. به اولین نود Head می‌گویند. لیست پیوندی سه نوع رایج دارد: یک‌طرفه، دوطرفه (هر نود به قبلی هم اشاره می‌کند) و حلقوی (آخرین نود به اولی برمی‌گردد). برخلاف آرایه، درج و حذف در ابتدای لیست O(1) است ولی دسترسی به عنصر k‌ام O(n) است. آموزش کامل: لیست پیوندی چیست.

در فیلم زیر موارد زیر درس داده شده است:

1. تعریف لیست پیوندی یک طرفه
2. بررسی مرتبه عملیات درج و حذف در لیست پیوندی
3. ساخت یک لیست پیوندی یک طرفه 1000 نوده
4. نحوه درج نود در ابتدا لیست یک طرفه
5. درج یک نود در لیست یک طرفه پس از یک عنصر مشخص
6. حذف یک نود مشخص در لیست یک طرفه
7. بررسی لیست پیوندی دو طرفه و درج یک نود بعد از یک نود مشخص
8. حذف یک نود از لیست پیوندی دو طرفه
9. بررسی لیست حلقوی و درج یک نود در ابتدای لیست حلقوی
10. بررسی مسئله جوزف

ساختمان داده لیست پیوندی

INSERT (ref L: LIST; P: Position; X: ElementType)
  {
		  var q : ^CellType;
		  new(q);
		  q^.Data = x;
		  if p ≠ NULL then
		   {
			  q^.Next = p^.Next;
			  p^.Next = q;
		   }
		   else
		   {
			  q^.Next = L;
			  L = q;
		   }
  }
  

DELETE (ref L: LIST; P: Position;)
  {
		   var q : Position;
		   q = L;
		   if p ≠ L then
		  {
			  while q^.Next ≠ p do
				  q = q^.Next;
				  q^.Next = p^.Next;
				  dispose (p);
				  p = q^.Next;
		  }
		  else
		  {
			  L = L^.Next;
			  dispose(p);
			  p = L;
		  }
  }
  

Type CellType = Record
  {
		Data : ElementType;
		Next,Prev : ^CellType;
  }
  Type LIST = ^CellType;
  Type Position = ^CellType;
  Const NULL = 0;
  

INSERT (ref L: LIST; P: Position; X: ElementType)
  {
		  var q : ^CellType;
		  new(q);
		  q^.Data = x;
		  if p ≠ NULL then
		   {
			  q^.Next = p^.Next;
			  q^.Prev = p;
			  if p^.Next ≠ NULL then
				  p^.Next^.Prev = q;
			  p^.Next = q;
		   }
		   else
		   {
			  q^.Next = L;
			  L^.Prev = q;
			  q^.Prev = NULL;
			  L = q;
		   }
  }
  

DELETE (ref L: LIST; ref P: Position;)
  {
		  var q : Position;
		  q = p^.Next;
		  if p ≠ L then
		  {
				  p^.Prev^.Next = p^.Next;
				  if p^.Next ≠ NULL then
					  p^.Next^.Prev = p^.prev;
		  }
		  else
		  {
			  L = L^.Next;
			  L^.Prev = NULL;
		  }
		  dispose(p);
		  p = q;
  }
  

AddLast (ref L: LIST; X: ElementType)
  {
		  var q : Position;
		  new(q);
		  q^.Data = x;
		  if L == NULL then
		   {
			  q^.Next = q;
			  L = q;
		   }
		   else
		   {
			  q^.Next = L^.Next;
			  L^.Next = q;
			  L = q;
		   }
  }
  

پشته (Stack)

ساختمان داده پشته مجموعه‌ای پویا از داده‌ها است که هنگام حذف عنصر از این مجموعه، آخرین عنصر اضافه شده به مجموعه از آن حذف می‌شود، اصطلاحا به این روش حذف داده های LIFO (Last In First Out) یا LCFS(Last Come First Serve) گفته می‌شود. بنابراین پشته ترتیب خروج عناصر را کنترل می‌کند. در نتیجه برای دسترسی به یک عنصر، ابتدا باید عناصری را که پس از آن به پشته وارد شده‌اند از پشته خارج کرد. بشقاب‌هایی را تصور کنید که روی هم چیده شده‌اند: همیشه بشقاب بالایی را برمی‌دارید.

عملیات اصلی پشته Push (افزودن به بالا)، Pop (برداشتن از بالا) و Top یا Peek (دیدن عنصر بالا) است و هر سه O(1) هستند. کاربردهای مهم پشته: پشتهٔ فراخوانی توابع (Call Stack) و اجرای توابع بازگشتی، دکمهٔ Undo در ویرایشگرها، بررسی توازن پرانتزها و تبدیل و ارزیابی عبارت‌های میانوندی و پسوندی. آموزش کامل: پشته چیست و کاربردهای آن.

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

PUSH (ref S : STACK; X : ElementType)
  {
	  if S.TOP == MAX then
		  Error ("Overflow");
	  S.Elements[TOP+1] = X;
	  S.TOP++;
  }
  

POP (ref S : STACK) : ElementType 
  {
	  if S.TOP == 0 then
		  Error ("Underflow");
	  X = S.Elements[S.TOP];
	  S.TOP--;
	  return X;
  }
  

صف (Queue)

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

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

عملیاتی که روی صف انجام می‌گیرد

ENQUEUE (Q,X) : اضافه کردن عنصر x به انتهای صف Q

DEQUEUE (Q) : حذف یک عنصر از ابتدای صف Q و بازگرداندن آن عنصر بعنوان خروجی

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

ENQUEUE (ref Q : QUEUE; X : ElementType)
  {
	  if Q.Rear == MAX then
		  Error ("Overflow");
	  Q.Elements[Q.Rear] = X;
	  Q.Rear++;
  }
  

DEQUEUE (ref Q : QUEUE) : ElementType
  {
	  if EMPTY(Q) then
		  Error ("Underflow");
	  Q.Front++;
	  return Q.Elements[Q.Front-1];
  }
  

ENQUEUE (ref Q : QUEUE; X : ElementType)
  {
	  if SIZE(Q) == MAX-1 then
		  Error ("Overflow");
	  Q.Elements[Q.Rear] = X;
	  Q.Rear = (Q.Rear mod MAX)+1;
  }
  

DEQUEUE (ref Q : QUEUE) : ElementType
  {
	  if EMPTY(Q) then
		  Error ("Underflow");
	  X = Q.Elements[Q.Front];
	  Q.Front = (Q.Front mod MAX)+1;
	  Return X;
  }
  

ENQUEUE (ref Q : QUEUE; X : ElementType)
  {
	  if Q.Rear == NULL then
	  {
		  new(Q.Rear);
		  Q.Rear^.Data = X;
		  Q.Rear^.Next = NUll;
		  Q.Front = Q.Rear;
	  }
	  else
	  {
	  var P : Position;
	  new(p);
	  P^.Data = X;
	  P^.Next = Null;
	  Q.Rear^.Next = P;
	  Q.Rear = P;
	  }
	  Q.Size++;	
  }
  

DEQUEUE (ref Q : QUEUE) : ElementType
  {
	  if Q.Front == NULL then
		  Error ("Underflow");
	  var X : ElementType;
	  X = Q.Front^.Data;
	  var P : Position;
	  P = Q.Front;
	  Q.Front = Q.Front^.Next;
	  dispose(p);
	  Q.Size--;
	  Return X;
  }
  

درخت (Tree)

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

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

چند اصطلاح پایه: گرهٔ بالایی ریشه، گره‌های بدون فرزند برگ، و طولانی‌ترین مسیر از ریشه تا یک برگ ارتفاع درخت است. در درخت دودویی هر گره حداکثر دو فرزند (چپ و راست) دارد. درخت‌های مهم دیگری که در درس ساختمان داده و کنکور می‌آیند: درخت AVL و درخت قرمز-سیاه (درخت‌های جستجوی متوازن با ارتفاع O(log n))، B-Tree (پایهٔ ایندکس پایگاه‌داده و فایل‌سیستم‌ها) و درخت پیشوندی یا Trie (برای جست‌وجوی رشته‌ها و تکمیل خودکار). آموزش‌های کامل‌تر: درخت در ساختمان داده، درخت دودویی و پیمایش درخت.

در فیلم زیر موارد زیر درس داده شده است:

1. تعریف بازگشتی درخت
2. تعریف مفاهیمی نظیر برادر، نوه، جد، نودهای داخلی، برگ، درجه هر نود در درخت‌ها
3. تعریف مواردی نظیر تعداد لول، شماره سطوح، ارتفاع و عمق در درخت‌ها
4. ارائه فرمول‌هایی برای محاسبه ماکزیمم نودها، برگ‌ها و نودهای داخلی یک درخت پر
5. چگونگی پیمایش‌های پیش ترتیب، پس ترتیب، میان ترتیب و سطح ترتیب در درخت
6. ذخیره درخت در کامپیوتر با استفاده از آرایه
7. ذخیره درخت در کامپیوتر با استفاده از لیست پیوندی

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

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

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

1. هر نود باید دقیقا یک کلید داشته باشد
2. کلید همه نودهای زیر درخت سمت چپ هر نود، باید کوچکتر یا مساوی با کلید آن نود باشد
3. کلید همه نودهای زیر درخت سمت راست هر نود، باید بزرگتر از کلید آن عنصر باشد

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

تمامی الگوریتم‌های جستجو، درج، حذف، یافتن Minimum، یافتن Maximum، یافتن عنصر بعدی و پیشین یک عنصر مشخص همگی از مرتبه ارتفاع درخت BST هستند. ارتفاع BST در حالت میانگین O(log n) است، ولی اگر عناصر مرتب‌شده درج شوند درخت به یک زنجیره تبدیل می‌شود و ارتفاع به O(n) می‌رسد؛ درخت‌های متوازن مثل AVL برای جلوگیری از همین مشکل ساخته شده‌اند. آموزش کامل: درخت جستجوی دودویی.

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

Type BST = Record
  {
	  Key : KeyType;
	  Data : DataType;
	  LC : ^BST;
	  RC : ^BST;
  }
  

SEARCH (T : BST; K : KeyType) : NodeType 
  {
	  if T == NULL then
		  return NULL;
	  if K == T^.Key then
		  return T;
	  if K <
   T^.Key then
		  return SEARCH(T^.LC,K);
	  else
		  return SEARCH(T^.RC,K);
  }
  

INSERT (ref T : BST; K : KeyType; X : DataType) 
  {
	  if T == NULL then
	  {
		  new(T);
		  T^.Key = K;
		  T^.Data = X;
		  T^.LC = T^.RC = NULL;
	  }

	  else
	  {
		  if K <
   T^.Key then
			  INSERT( T^.LC, K, X);
		  else
			  INSERT( T^.RC, K, x);
	  }

  }
  

MAXIMUM (T : BST) : NodeType 
  {
	  if T == NULL then
		  return NULL;
	  if T^.RC == NULL then
		  return T;
	  else
		  return MAXIMUM(T^.RC);
  }
  

SUCCESSOR ( T : BST; Node : NodeType) : NodeType 
  {
	  var Parent : NodeType;
	  if Node^.RC ≠ NULL then
		  return MINIMUM(Node^.RC);
	  Parent = PARENT( T, Node);
	  while Parent ≠ NULL and Node == Parent^.RC do
	  {
	  Node = Parent;
	  Parent = PARENT( T, Parent);
	  }
	  return Parent;
  }
  

PREDECESSOR ( T : BST; Node : NodeType) : NodeType 
  {
	  var Parent : NodeType;
	  if Node^.LC ≠ NULL then
		  return MAXIMUM(Node^.LC);
	  Parent = PARENT( T, Node);
	  while Parent ≠ NULL and Node == Parent^.LC do
	  {
		  Node = Parent;
		  Parent = PARENT( T, Parent);
	  }
	  return Parent;
  }
  

درخت هیپ یا هرم (Heap)

هیپ دودویی (Binary Heap) یک درخت دودویی کامل است که خاصیت هیپ را دارد: در MaxHeap کلید هر گره بزرگ‌تر یا مساوی کلید فرزندانش است (پس بزرگ‌ترین عنصر همیشه در ریشه است) و در MinHeap برعکس، کلید هر گره کوچک‌تر یا مساوی فرزندانش است.

چون هیپ درخت کامل است، آن را بدون اشاره‌گر و با یک آرایه پیاده‌سازی می‌کنند: اگر گره در خانهٔ i باشد، پدرش در خانهٔ ⌊i/2⌋ و فرزندانش در خانه‌های 2i و 2i+1 هستند. به همین دلیل یافتن بیشینه O(1)، و درج و حذف ریشه O(log n) است و ساختن هیپ از n عنصر با روش Build-Heap در O(n) انجام می‌شود. مهم‌ترین کاربرد هیپ، پیاده‌سازی صف اولویت و الگوریتم مرتب‌سازی هرمی (Heap Sort) است. برای توضیح کامل به مقاله درخت هیپ در ساختمان داده مراجعه کنید.

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

ENQUEUE-HEAP (ref H : HEAP; X : ElementType)
  {
	  H.NOE++;
	  H.Elements[H.NOE] = X;
	  BUBBLE-UP( H, H.NOE);
  }
  BUBBLE-UP(ref H : HEAP; i : integer)
  {
	  // Check if it has reached the root
	  if i ≤ 1 then
		  return;
	  // Swap if node i is greater than its parent
	  if H.Elements[i] > H.Elements[i/2] then
		  {
		  Swap ( H.Elements[i], H.Elements[i/2] );
		  // Call bubble up for parent node
		  BUBBLE-UP ( H, i/2);
		  }


  }
  

DEQUEUE-HEAP (ref H : HEAP) : ElementType
  {
	  var maximum : ElementType;
	  maximum = H.Elements[1];
	  H.Elements[1] = H.Elements[H.NOE];
	  H.NOE--;
	  SIFT-DOWN( H, 1);
	  return maximum;
  }
  SIFT-DOWN(ref H : HEAP; i : integer)
  {
	  var largest : integer;
	  largest = i;
	  if 2*i ≤ H.NOE and H.Elements[largest] <
   H.Elements[2*i] then
		  largest = 2*i;
	  if 2*i+1 ≤ H.NOE and H.Elements[largest] <
   H.Elements[2*i+1] then
		  largest = 2*i+1;
	  if i ≠ largest then
		  {
		  Swap ( H.Elements[i], H.Elements[largest] );
		  SIFT-DOWN ( H, largest);
		  }


  }
  

جدول درهم‌سازی (Hash Table)

جدول درهم‌سازی یا جدول هش، داده‌ها را به‌صورت جفت کلید و مقدار نگه می‌دارد و جست‌وجو، درج و حذف را به‌طور میانگین در زمان ثابت O(1) انجام می‌دهد. ایدهٔ اصلی ساده است: یک تابع درهم‌سازی h(k) کلید را به شمارهٔ یکی از m خانهٔ یک آرایه تبدیل می‌کند و داده در همان خانه ذخیره می‌شود.

مثال: با m = 10 و تابع h(k) = k mod 10، کلید 15 به خانهٔ 5 می‌رود. حالا اگر کلید 25 را درج کنیم، آن هم به خانهٔ 5 می‌رود. به این وضعیت برخورد (Collision) می‌گویند و هر جدول درهم‌سازی باید راهی برای حلش داشته باشد:

• زنجیره‌سازی (Chaining): هر خانهٔ جدول یک لیست پیوندی است و همهٔ کلیدهایی که به آن خانه می‌رسند در همان لیست قرار می‌گیرند.
• آدرس‌دهی باز (Open Addressing): همهٔ کلیدها در خود آرایه می‌مانند و در صورت برخورد، خانهٔ خالی دیگری با کاوش خطی، کاوش درجه‌دو یا درهم‌سازی دوگانه پیدا می‌شود. در برخی منابع فارسی به این روش «درهم‌سازی بسته» هم می‌گویند.

کارایی جدول به ضریب بار α = n/m (نسبت تعداد کلیدها به تعداد خانه‌ها) بستگی دارد. با زنجیره‌سازی و یک تابع درهم‌سازی خوب، زمان میانگین جست‌وجو Θ(1 + α) است؛ ولی اگر همهٔ کلیدها در یک خانه جمع شوند، بدترین حالت O(n) می‌شود. محاسبهٔ تعداد کاوش در جست‌وجوی موفق و ناموفق از سؤال‌های پرتکرار این فصل در کنکور است.

کاربردها: dict و set در پایتون و HashMap در جاوا، حافظهٔ نهان (Cache)، جدول نمادها در کامپایلر و ایندکس‌های درهم‌سازی در پایگاه‌داده. آموزش کامل: جدول درهم‌سازی (Hash Table) چیست.

گراف (Graph)

گراف G = (V, E) از مجموعه‌ای از رأس‌ها (V) و یال‌ها (E) تشکیل شده که هر یال دو رأس را به هم وصل می‌کند. گراف عمومی‌ترین ساختمان دادهٔ غیرخطی است؛ درخت در واقع حالت خاصی از گراف است: گرافی همبند و بدون دور که n رأس و n−1 یال دارد.

• جهت‌دار و بی‌جهت: در گراف جهت‌دار یال (u, v) فقط از u به v می‌رود، مثل دنبال‌کردن در اینستاگرام؛ در گراف بی‌جهت رابطه دوطرفه است، مثل دوستی.
• وزن‌دار و بی‌وزن: در گراف وزن‌دار هر یال عددی مثل فاصله یا هزینه دارد، مثل جاده‌های نقشه.

دو روش اصلی برای ذخیرهٔ گراف در حافظه وجود دارد:

دو پیمایش پایهٔ گراف، جست‌وجوی اول سطح (BFS) که با صف کار می‌کند و جست‌وجوی اول عمق (DFS) که با پشته یا بازگشت کار می‌کند، هر دو با لیست مجاورت در O(V + E) اجرا می‌شوند. الگوریتم‌های مهم گراف مثل دایجسترا (کوتاه‌ترین مسیر) و کراسکال و پریم (درخت پوشای کمینه) بیشتر در درس طراحی الگوریتم بررسی می‌شوند. کاربردها: مسیریابی در نقشه‌ها، شبکه‌های اجتماعی، شبکه‌های کامپیوتری و ترتیب وابستگی کارها (مرتب‌سازی توپولوژیک).

آموزش‌های کامل‌تر: آموزش کامل گراف، الگوریتم BFS، الگوریتم DFS، الگوریتم دایجسترا و درخت پوشای کمینه.

مجموعه‌های مجزا (Disjoint Set یا Union-Find)

این ساختمان داده گروهی از مجموعه‌های بدون اشتراک را نگه می‌دارد و سه عملیات دارد: MAKE-SET (ساختن مجموعهٔ تک‌عضوی)، FIND-SET (پیدا کردن نمایندهٔ مجموعهٔ یک عنصر) و UNION (ادغام دو مجموعه). اگر هر مجموعه را یک درخت بگیریم و از دو ترفند ادغام بر اساس رتبه و فشرده‌سازی مسیر استفاده کنیم، هزینهٔ سرشکن هر عملیات تقریباً ثابت است (O(α(n)) که α تابع معکوس آکرمان است). مهم‌ترین کاربرد آن در الگوریتم کراسکال برای تشخیص دور است. مجموعه‌های مجزا از سرفصل‌های کنکور است که در بسیاری از دانشگاه‌ها کامل تدریس نمی‌شود.

جدول مرتبهٔ زمانی عملیات در ساختمان داده‌ها (Big-O)

نماد O بزرگ حد بالای رشد تعداد عملیات را بر حسب اندازهٔ ورودی n نشان می‌دهد؛ مثلاً O(n) یعنی با دو برابر شدن داده، زمان حداکثر حدود دو برابر می‌شود. جدول زیر مرتبهٔ عملیات اصلی را برای ساختمان داده‌های این صفحه کنار هم گذاشته است. اگر فقط یک جدول از این صفحه را حفظ می‌کنید، همین باشد:

برای آشنایی دقیق با نمادهای مجانبی (O، Ω و Θ) و روش محاسبهٔ مرتبهٔ کد، مقالهٔ پیچیدگی زمانی الگوریتم را بخوانید.

مقایسه مزایا و معایب ساختمان داده های پر استفاده

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

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

ساختمان داده‌ها فقط مفهوم کلاسی نیستند؛ تقریباً هر نرم‌افزاری که هر روز استفاده می‌کنید روی آن‌ها ساخته شده است:

برای مثال‌های بیشتر، مقالهٔ کاربرد ساختمان داده را ببینید.

ساختمان داده در پایتون، جاوا و ++C

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

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

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

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

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

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

پیش‌نیاز درس ساختمان داده

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

درس ساختمان داده چه پیش‌نیازهایی در دانشگاه دارد؟

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

درس ساختمان داده پیش‌نیاز چه درس‌هایی در دانشگاه است؟

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

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

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

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

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

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

نقشهٔ راه یادگیری ساختمان داده (به چه ترتیبی بخوانیم؟)

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

1. پیش‌نیازها: یک زبان برنامه‌نویسی (حلقه، تابع، بازگشت، اشاره‌گر) و مباحث پایهٔ ریاضیات گسسته.
2. مرتبهٔ زمانی و رشد توابع: نمادهای O، Ω و Θ و محاسبهٔ مرتبهٔ قطعه‌کدها.
3. روابط بازگشتی: درخت بازگشت و قضیهٔ اصلی (Master).
4. آرایه و ماتریس‌های خاص، سپس لیست پیوندی.
5. پشته و صف و کاربردهایشان.
6. درخت‌ها: درخت دودویی، پیمایش‌ها، BST و سپس هیپ.
7. درخت‌های متوازن: AVL، قرمز-سیاه و B-Tree.
8. درهم‌سازی: زنجیره‌سازی، آدرس‌دهی باز و تحلیل تعداد کاوش.
9. مرتب‌سازی و جست‌وجو: مرتب‌سازی‌های مقایسه‌ای و خطی.
10. گراف و مجموعه‌های مجزا، که پل ورود به درس طراحی الگوریتم است.
11. حل تست: بعد از هر فصل، تست‌های کنکورهای سال‌های قبل همان فصل را حل کنید.

سرفصل رسمی درس را در صفحهٔ سرفصل درس ساختمان داده‌ها و الگوریتم‌ها ببینید و برای تمرین از نمونه سوالات ساختمان داده و جزوهٔ ساختمان داده استفاده کنید.

مراجع درس ساختمان داده

اصلی ترین مرجع درس ساختمان داده که در دانشگاه‌‌های معتبر دنیا تدریس می‌شود کتاب Introduction to Algorithms معروف به CLRS است؛ نویسندگان این کتاب Clifford STEIN ،RIVEST ،LEISERSON ،CORMEN هستند. همچنین کتاب‌های COMPUTER ALGORITHM (نوشته شده توسط Ellis Horowitz، Sartaj Sahni و Sanguthevar Rajasekar)، و کتاب مرجع Data Structures and Algorithm Analysis ( نوشته Clifford A. Shaffer) نیز در برخی از دانشگاه‌های ایران و جهان تدریس می‌شوند.

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

دانلود کتاب های مرجع درس ساختمان داده

دانلود کتاب ساختمان داده کورمن

دانلود کتاب Made Easy: Data structure book PDF

دانلود کتاب ساختمان داده clrs

حل مسائل کتاب clrs

ساختمان داده با پایتون

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

کتاب ساختمان داده در جاوا

کتاب ساختمان داده ها در جاوا

ساختمان داده در جاوا

کتاب ساختمان داده با c++

اصلی ترین موضوعاتی که در مطالعه ساختمان‌های داده مطرح می‌شوند

1) ایستا و پویا (Static and Dynamic)

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

2) صریح و ضمنی (Explicit and Implicit)

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

3) زمان و حافظه

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

بعنوان مثال فرض کنید هدف طراحی ساختمان داده‌ای باشد که بیان کند در مجموعه‌ای شامل یک میلیون عدد غیرتکراری از بازه [1و 10^9 ] چه اعدادی وجود دارند و چه اعدادی وجود ندارد. برای این منظور دو طراحی می‌توان ارائه کرد

1. آرایه ای از بیت ها به طول 10^9 در نظر گرفته می‌شود که 0 یا 1 بودن هر خانه از آرایه نشان دهنده وجود یا عدم وجود عدد متناظر با آن خانه باشد. به شکل زیر توجه کنید.
   0        1        2        3        4        ...        10⁹

   در صورت اضافه شدن یا حذف یک عنصر از مجموعه عناصر، عملیات لازم برای بروزرسانی این ساختمان داده از مرتبه O(1) خواهد بود، زیرا تنها کافی است مقدار یک بیت در آرایه تغییر کند. همچنین عملیات مورد نیاز برای اطلاع از وجود یا عدم وجود یک عنصر در مجموعه نیز از مرتبه O(1) است.

2. از یک درخت متوازن استفاده کنیم و اعداد درون مجموعه مان را در آن قرار دهیم. در این ساختمان داده عملیات درج و حذف یک عنصر و همین طور عملیات مورد نیاز برای اطلاع از وجود یا عدم وجود یک عنصر از مرتبه O(logn) است

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

مراحل حل مسئله در ساختمان داده و طراحی الگوریتم

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

1. تبدیل مسئله به یک مدل ریاضی (مدل انتزاعی) قابل حل توسط کامپیوتر
2. طراحی الگوریتمی برای حل آن مسئله
3. انتخاب داده ساختار(Data Structure) مناسب برای الگوریتمی که ارائه داده‌ایم، برای ذخیره و دستکاری داده های مسئله

نمودار مراحل حل مسئله

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

روش های طراحی الگوریتم

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

1. روش‌های مبتنی بر استقرا

   o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی می‌شوند عبارت اند از: مسئله ستاره مشهور، مسئله محاسبه درست اعداد فیبوناچی، مسئله کوچکترین دایره محیطی

2. تقسیم و حل (یا تقسیم و غلبه، Divide-and-conquer)

   در این روش مسائل را به مسئله‌های کوچکتر تبدیل می‌کنیم، سپس مسئله‌های کوچکتر را حل می‌کنیم و بعد حل‌ این‌ها را با هم ادغام می‌کنیم تا حل مسئله اصلی بدست آید

   o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی می‌شوند عبارت اند از: مسئله ضرب چند جمله‌ای ها، مسئله ضرب ماتریس‌ها (استراسن)، مسئله محاسبه تعداد وارونگی‌ها، مسئله تورنومنت

3. برنامه نویسی پویا (Dynamic Programing)

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

   o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی می‌شوند عبارت اند از: مسئله کوله پشتی، مسئله برش چوب، مسئله ضرب ماتریس‌ها، مسئله درخت دودویی جستجوی کمینه، مسئله یافتن بزرگترین زیردنباله مشترک یا همان Longest common subsequence problem(LCS)

4. حریصانه (Greedy)

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

   o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی می‌شوند عبارت اند از: مسئله خرد کردن سکه، مسئله کد هافمن، مسئله زمان بندی task ها روی پردازنده

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

1. چگونگی تحلیل الگوریتم
2. بررسی ساختمان داده‌ها

1) تحلیل الگوریتم ها

معمولا الگوریتم‌های زیادی برای حل یک مساله خاص وجود دارند که باید مناسب‌ ترین و کارا ترین آن‌ها انتخاب شود، حال کارایی یک الگوریتم از جهات متفاوتی از جمله زمان اجرا، حافظه مصرفی، تعداد عملیات ورودی و خروجی، پهنای باند مصرفی و غیره قابل بررسی است، در حال حاضر در اکثر مواقع، ملاک اصلی در انتخاب الگوریتم‌ها، مدت زمان اجرای آن‌ها است.
در اوایل پیدایش کامپیوترها که کامپیوترها حافظه بسیار کمی داشتند، برای نرم افزارها محدودیت حافظه وجود داشت و گاها الگوریتم‌هایی با سرعت‌های پایین تر و زمان اجراهای بالاتر، تنها به دلیل اینکه حافظه کمتری مصرف می‌کردند بر الگوریتم‌های سریعتری که حافظه بیشتری مصرف می‎کردند ارجحیت داشتند. اما امروزه با پیشرفت قابل توجه تکنولوژی حافظه و قیمت پایین سخت افزار، این محدودیت چندان مطرح نیست. این حقیقت باعث شده تا در بررسی کارایی الگوریتم‌ها توجه چندانی به حافظه مصرفی آنها نشود و تحلیل حافظه مصرفی الگوریتم‌ها جایگاه خود را در طراحی الگوریتم‌ها از دست بدهد
. اما اگر بخواهیم الگوریتم‌ها را از جنبه حافظه مصرفی بررسی کنیم، الگوریتم‌ها به دو دسته درجا (In-Place) و غیردرجا یا برون جا (Out-Place) تقسیم می‌شوند. الگوریتم‌های Out-Place به الگوریتم‌هایی گفته می‌شود که حداکثر اندازه حافظه‌ی کمکی مورد نیاز آن‌ها برای اجرا وابسته به اندازه داده‌های ورودی باشد و این حافظه با افزایش اندازه ورودی افزایش می‌یابد، بعنوان مثال اگر یک الگوریتم برای مرتب کردن 100 عدد ورودی به یک آرایه‌ای کمکی با اندازه 100 خانه نیازمند است، برای مرتب کردن 200 عدد ورودی به یک آرایه کمکی با اندازه 200 خانه نیازمند است.
الگوریتم‌های In-Place برای اجرا نیاز به میزان ثابتی حافظه کمکی دارند و اندازه حافظه کمکی این الگوریتم‌ها با افزایش تعداد داده‌های ورودی تغییری نمی‌کند و همواره ثابت است. بنابراین الگوریتم‌های درجا از نظر مصرف حافظه کارایی بیشتری دارند
گفتیم که در اکثر مواقع، ملاک اصلی در انتخاب الگوریتم‌ها، مدت زمان اجرای آن‌ها است. حال باید مشخص کنیم که منظور از مدت زمان اجرای الگوریتم‌ها چیست. زمان در اینجا به معنای تعداد ثانیه‌ای که طول می‌کشد که الگوریتم اجرا شود نیست، بلکه منظور تقریبی است از تعداد عملیاتی که یک الگوریتم در هنگام اجرا انجام می‌دهد و چون تعداد عملیاتی که یک الگوریتم برای اجرا شدن‌اش انجام می‌دهد رابطه مستقیم با زمان اجرای آن دارد از واژه مدت زمان استفاده می‌شود.
محاسبه تعداد ثانیه‌هایی که یک الگوریتم برای اجرا شدن روی یک کامپیوتر نیاز دارد فایده ای ندارد، زیرا مدت زمان اجرای یک الگوریتم روی یک کامپیوتر به عوامل مختلفی نظیر معماری پردازنده آن کامپیوتر، نوع کامپایلر، چگونگی پیاده سازی الگوریتم، سرعت پردازنده آن کامپیوتر و بسیاری از موارد دیگر بستگی دارد، تمامی این موارد از یک کامپیوتر به کامپیوتر دیگر می‌تواند متفاوت باشد، در حالیکه ما نیازمند معیاری هستیم که مستقل از جزئیات سخت افزاری و نرم افزاری کامپیوتر اجرا کننده الگوریتم باشد، با داشتن چنین معیاری می‌توانیم کارایی الگوریتم‌ها از نظر مدت زمان اجرا را، مستقل از عوامل مذکور با هم مقایسه کنیم
تعداد واقعی عملیات انجام شده به ازای اندازه ثابت ورودی هر چند بر روی یک کامپیوتر خاص و در شرایط خاص قابل محاسبه است ولی کمک چندانی به تحلیل نمی‌کند، زیرا حجم داده‌های ورودی در کاربردهای واقعی همواره متغیر است، بنابراین در تحلیل زمان اجرای الگوریتم‌ها معادله‌ای (تابعی) نیاز است که تعداد عملیاتی که یک الگوریتم انجام می‌دهد را بر حسب اندازه ورودی (مثلا n) بیان کند. حال محاسبه این تابع کاری دشوار و در مواقعی غیر ممکن است به همین علت برای مقایسه الگوریتم‌ها از نظر زمان اجرا از معیاری به نام نرخ رشد توابع استفاده می‌کنند، نرخ رشد میزان افزایش تعداد عملیات یک الگوریتم بر اثر افزایش اندازه ورودی را نشان می‌دهد بنابراین اگر نرخ رشد تابع A بیشتر از نرخ رشد تابع B باشد، با افزایش اندازه ورودی این توابع رشد تابع A سریعتر از B بوده و در نهایت تعداد دستورات انجام شده توسط الگوریتم A بیشتر از الگوریتم B خواهد شد.
اطلاع از نرخ رشد برخی از توابع رایج به شما در تحلیل پیچیدگی زمانی الگوریتم‌ها کمک می‌کند

نرخ رشد برخی از توابع در ساختمان داده و طراحی الگوریتم

برای آنکه بدانید رشد کدام توابع بیشتر است به جدول زیر توجه کنید

2) بررسی ساختمان داده ها

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

عملیات روی هر ساختمان داده را می‌توان در دو دسته کلی طبقه بندی کرد:

1. Query ها یا درخواست ها
2. Update ها

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

Update ها عملیاتی هستند که سبب تغییر در مقدار یا چینش عناصر ساختمان داده می‌شوند، مانند اضافه کردن یک عنصر جدید، حذف عناصر موجود و ...

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

اهمیت درس ساختمان داده در دانشگاه و پژوهش

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

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

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

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

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

ساختمان داده در کنکور ارشد و دکتری کامپیوتر و آی تی (۱۴۰۶)

از کنکور ۱۴۰۶، سازمان سنجش برای هر دو مجموعهٔ «مهندسی و علم کامپیوتر» (کد ۱۲۷۷) و «مهندسی فناوری اطلاعات» (کد ۱۲۷۶) فقط یک کد ضریب تعریف کرده است؛ یعنی ضریب دروس در همهٔ گرایش‌ها یکسان است: زبان عمومی و تخصصی ضریب ۱، مجموعهٔ ریاضیات ضریب ۲ و مجموعهٔ دروس تخصصی ضریب ۴. درس «داده‌ساختارها و الگوریتم‌ها» در هر دو مجموعه جزو دروس تخصصی با ضریب ۴ است. پس تقسیم‌بندی قدیمی «ضریب ۳ در گرایش‌های شبکه و معماری و ضریب ۴ در بقیه» دیگر اعتبار ندارد.

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

در کنکور دکتری ۱۴۰۶ هم مجموعه‌های «مهندسی و علم کامپیوتر» (۲۳۵۴) و «مهندسی فناوری اطلاعات» (۲۳۵۸) همان دروس ارشد را دارند و داده‌ساختارها و الگوریتم‌ها در هر دو جزو دروس تخصصی ضریب ۴ است.

نکتهٔ مهم برای کسانی که با فیلم یا جزوهٔ سال‌های قبل می‌خوانند: محتوای درس ساختمان داده عوض نشده است و آرایه، درخت، هیپ یا درهم‌سازی همان مفاهیم همیشگی‌اند. آنچه بین سال‌ها تغییر می‌کند فقط فهرست دروس امتحانی است، و ساختمان داده و الگوریتم در کنکور ۱۴۰۶ همچنان جزو مهم‌ترین دروس ضریب ۴ است.

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

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

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

فیلم معرفی و بررسی درس ساختمان داده

در فیلم زیر که در خصوص تحلیل و بررسی درس ساختمان داده رشته کامپیوتر پرداختیم، در این فیلم توضیح داده شده که فیلم درس ساختمان داده برای چه افرادی مناسب است و همین طور در خصوص فصول مختلف درس ساختمان داده و اهمیت هر کدام از فصول صحبت شده است.

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

فیلم ساختمان داده جلسه 1

فیلم ساختمان داده جلسه 2

فیلم ساختمان داده جلسه 3

فیلم ساختمان داده جلسه 4

فیلم ساختمان داده جلسه 5

فیلم ساختمان داده جلسه 6

فیلم ساختمان داده جلسه 7

فیلم ساختمان داده جلسه 8

حل تست ساختمان و الگوریتم جلسه 1

حل تست ساختمان و الگوریتم جلسه 2

حل تست ساختمان و الگوریتم جلسه 3

ساختمان داده و طراحی الگوریتم کامپیوتر 1403

ساختمان داده و طراحی الگوریتم آیتی 1403

حل تست ساختمان و الگوریتم جلسه 4

انواع پیمایش‌های درخت

نحوه ساخت درخت BST

آموزش درخت B-Tree

بررسی مرتبه ساخت هیپ

آموزش مرتب سازی سریع

آموزش شبکه شار

حل سوالات ساختمان ارشد کامپیوتر 99

حل ساختمان ارشد 95 بخش 1

حل ساختمان ارشد 95 بخش 2

نمایش بیشتر

نمایش کمتر

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

نظر برخی از رتبه های برتر کنکور ارشد کامپیوتر و آی تی در مورد کیفیت فیلم‌ها

نظر رتبه 1 کنکور ارشد کامپیوتر 1403

نظر رتبه 1 کنکور ارشد کامپیوتر 1403

نظر رتبه 1 کنکور ارشد کامپیوتر و آیتی 1404

نظر رتبه 1 کنکور ارشد کامپیوتر 1403

نظر رتبه 1 کنکور ارشد کامپیوتر

نظر رتبه 2 کنکور ارشد کامپیوتر

نظر رتبه 2 کنکور ارشد

نظر رتبه 6 کنکور ارشد کامپیوتر

نظر رتبه 6 کنکور 1400

نظر رتبه 68 کنکور ارشد کامپیوتر 1403

نظر رتبه 68 کنکور ارشد آیتی 1403

فیلم ها خیلی قابل فهم و روان است

رتبه 9 :فیلم ها بی نقص بود

از پایه ضعیف تا شریف

نطر رتبه 10: کیفیت تدریس استاد رضوی خیلی خوبه

نظر رتبه 16: کیفیت تدریس خیلی عالی بود

جزوه کامل و ویدیوهای خیلی خوب

نحوه انتقال دانش استاد رضوی بینظیر است

ویدیوها خیلی جامع و کامل بودند

واقعا تدریس اساتید عالی بودند

نظر رتبه 8 کنکور 1400

نظر رتبه 2: معماری کامپیوتر و منطقی 100 زدم

نظر رتبه 13 کنکور ارشد کامپیوتر 1401

نظر رتبه 19: تدریس و فن بیان عالی است

نظر رتبه 12 کنکور ارشد کامپیوتر 1401

نظر رتبه 24: خیلی کامل و جامع است

فیلم‌ها بی نظیر بود

نظر رتبه 45: کیفیت فیلم ها خوب بودن

همه دروس عالی تدریس شده بودند

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

فیلم ها با بیان شیوا و بدون ابهام بود

کیفیت بالا و هزینه مناسب

نظر رتبه 11 کنکور 1400

فیلم‌ها بی‌نیازم کرد

تدریس زیبا و بیان شیوا

فیلم‌ درس و تست کافیست

فیلم های استاد رضوی از همه نظر عالی بودند

کیفیت و نحوه تدریس و قدرت بیان اساتید از همه نظر خوب بود

خیلی راضی بودم درسها خیلی عمیق تدریس میشد

از همه دروس خیلی راضی بودم

نظر پارسا شریعت

ویدیوها از نظر کیفیت عالی بودند

نظر رتبه 43 کنکور

از دروس استاد رضوی خیلی راضی بودم

نظر پیمان هاشمی

نظر رتبه 40 کنکور

تدریس از 0 تا 100

فیلم شما را جلو می‌اندازد

نظر رتبه 50 کنکور 1400

نظر رتبه 67 کنکور 1400

نظر ریحانه حسین زاده

نظر مرتضی اکبری

نظر رتبه 113 کنکور 1400

تاثیر منابع خوب

نظر سامان حسینی

تفاوت منابع مناسب

نظر رتبه 32 کنکور 1400

کیفیت بالا تدریس

نظر شیوا رضازاد

از روی مراجع نخوانید

فیلم ها خیلی مفهومی بودند

همه درس ها فوق العاده بود

از صفر تا صد و کامل هستند

آشنایی با استاد رضوی و کافه تدریس معجزه بود

فیلم ها جامع بودند

کل منابع من از کافه تدریس یا کنکور کامپیوتر بود

دروس واقعا فوق العاده بودند

درس‌ها کامل و روان است

فیلم ها خیلی دقیق و جامع و کامل بودند

ویدیوها بسیار قابل فهم بودند

مطالبی که پوشش داده شده بود واقعا کامل بود

تدریس بسیار شیوا و روان و بدون ابهام

با پایه ضعیف هم فیلم ها را متوجه می شوید

فیلم ها خیلی به من کمک کرد

همه دروس را از کافه تدریس گرفتم

ویدیوهاشون خیلی به من کمک کرد

نمایش بیشتر

نمایش کمتر

معرفی دوره ساختمان داده (درس+حل تست)

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

متاسفانه در اکثر دانشگاه‌های کشور چندین مشکل در ارائه این درس وجود دارد

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

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

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

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

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

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

رامین رضوی

RAMIN RAZAVI

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

 

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

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

1. فیلم درس ساختمان داده
2. فیلم حل تست سوالات ساختمان داده و الگوریتم

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

تخفیف تا دوشنبه، ۲ شهریور

30% 1,800,000 تومان 1,260,000 تومان

رامین رضوی

۶۴ ساعت

خرید دوره

ویدیو نکته و تست ساختمان داده و طراحی الگوریتم

تخفیف تا دوشنبه، ۲ شهریور

30% 1,700,000 تومان 1,190,000 تومان

رامین رضوی

۶۶ ساعت

خرید دوره

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

پی دی اف درس ساختمان داده

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

منابع و مراجع

1. https://www.geeksforgeeks.org/data-structures/
2. https://searchsqlserver.techtarget.com/definition/data-structure
3. https://www.programiz.com/dsa
4. https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42

فیلم‌های رایگان

سوالات متداول درباره ساختمان داده

34611 نفر تاکنون در دوره‌های آموزشی کنکور کامپیوتر شرکت کرده‌اند.

ساجده فدائی

کیان انواری

علیرضا بهدوست

احسان داستانی

معین منعمی

علیرضا حسن زاده باقی

سعيد نوروزيان

بهمن قائدی

مهدی مزارعی

سینا مهرآبادی

محمد امین شنابی

سارا مختاری همامی

Amir hossein

محمد مهدی باقی سعدی

emelkabi

آرش آریا

محمد چاروسایی

علیرضا ملکی

علی فتحی وافق

غزل موسوی

mitra joodaki

امیرحسین پژوهان

سجاد محمدنیا

یاسمین

بهنام پروین

انوش مه جبین

علیرضا حسن نیا

سعید راصدی

مهدی فرح روز

یوسف عباسی

مهدی حسنی

احمد بنائیان

فاطمه سادات لطفی فاطمی

پریسا محمودی

محمد رضا کمالی

امیرحسین بلکامه

zahra mansouri

امیر ارسلان ساختیانچی

تست نام منحصربفرد

سیدمحمدمهدی

نگین دبیران

پریسا نکوگل

فاطمه ابراهیم زاده نامور

نازنین ایلخانی

حسین پری نور

سمیه نعمتی زاد

sadra

محسن سروری

فاطمه اکبرنژاد

علی بابایی

علی اله وردی

محیا اشرفی

فاطمه دارپرنیا

مسعود علی اصغری

مجید محمددوست

هانیه طالبی

ندا نوروزی

اسما سهرابی

فرح رضایی

محمدامین حکیمی پور

حامد ترابی

Ali.Hp

مجید جنگی زهی

فرزانه مصطفی پور

محمدهادی قاسمی

امیر سعادت

پیمان بهادرانی

مطالب مرتبط

همه مقالات

ساده ترین زبان برنامه نویسی چیست؟ زبان های ساده برای شروع

برنامه نویسی پویا چیست، برنامه نویسی پویا در طراحی الگوریتم

معرفی انواع الگوریتم‌ ها

الگوریتم اقلیدسی (Euclidean Algorithm)