ساختمان داده و هر آنچه باید درباره آن بدانید

مقدماتی در مورد ساختمان داده
درس ساختمان داده بنیادی ترین درس رشته کامپیوتر و حتی یکی از بنیادی ترین درسهای بسیاری از رشتههای علوم پایه و مهندسی است. هدف درس ساختمان داده بررسی و پژوهش در مورد روشهای گوناگون ذخیره، نگهداری و بازیابی اطلاعات در سیستمهای کامپیوتری است، به گونهای که این اطلاعات بتواند بطور کارامد مورد استفاده قرار گیرد. برای تمامی دانشجویانی که علاقهمند به کارهای پژوهشی یا دادن الگوریتمهای بهینه برای مسائل و چالشهای موجود و یا برنامه نویسی هستند، داشتن دانش ساختمان دادهها و الگوریتمها باعث داشتن یک نگاه ویژه و متفاوت به حل مسائل است، و داشتن این نگاه دانش پژوهان را در آینده کاری و تحصیلی شان نسبت به دیگران متفاوت خواهد کرد. داشتن دانش کافی در مورد درس ساختمان دادهها باعث میشود که دانش پژوهان بتوانند بررسی کنند که آیا راه حلهایی که ارائه میدهند از جوانب گونانونی مانند مرتبه زمانی، میزان حافظه مصرفی، قابلیت توسعه، میزان مصرف توان و ...بهینه هستند یا خیر
آنچه در این صفحه مطالعه خواهید کرد (روی هر یک از موارد زیر کلیک کنید به قسمت مربوطه هدایت می شوید):
3. معرفی ساختمان داه های متداول از جمله آرایه، لیست پیوندی، صف، پشته، درخت و ...
4. مقایسه ساختمان داده های پر کاربرد
5. اصلی ترین موضوعاتی که در ساختمان داده ها بررسی میشود چیست
6. توضیح مراحل حل مسئله در ساختمان داده و طراحی الگوریتم
7. چه روش های مختلفی برای طراحی الگوریتم ها وجود دارد
9. بررسی اجمالی درس ساختمان داده در کنکور ارشد و دکتری کامپیوتر و آی تی
11. دانلود رایگان پی دی اف کتاب های مرجع درس ساختمان داده
12. فصول درس ساختمان داده چیست؟
13. مشاهده فیلم های رایگان آموزش ساختمان داده
14. خرید فیلم های درس و حل تست ساختمان داده و طراحی الگوریتم
15. پرسش و پاسخ (هر سوالی دارید می توانید در قسمت کامنت ها بپرسید)
ساختمان داده چیست:
یک برنامه تشکیل شده از یکسری داده های ورودی، که برنامه ما یک الگوریتمی را روی داده های ورودی اجرا میکند و سپس داده های خروجی برای ما تولید میکند. بعنوان مثال ما برنامه ای داریم که لیست دانشجویان یک کلاس را به آن میدهیم و برنامه ما طبق الگوریتمی که برایش مشخص کرده ایم افرادی که معدل شان بالای 18 است را به ترتیب برای ما مشخص میکند. الگوریتم روی داده ها کار میکند و آنها را پردازش میکند (در واقع الگوریتم ما بر روی داده ها اجرا میشود)، برای اینکه بتوانیم این امکان را برای الگوریتم فراهم کنیم تا راحت تر بتواند دادهها را پردازش بکند باید بتوانیم دادهها را به شکل مناسب ذخیره سازی یا سازماندهی کنیم، درسی که هنر ذخیره سازی مناسب داده ها را به ما یاد میدهد ساختمان داده ها است، در واقع ما در ساختمان داده سعی میکنیم که ساختار دادههای گوناگون با ویژگیهای مختلف را تعریف کنیم.
هدف اصلی درس ساختمان داده و طراحی الگوریتم ارائه مبانی نظری مورد نیاز برای کسب مهارت لازم در حل مسئله (Problem Solving) به کمک کامپیوتر است، یک مهندس کامپیوتر و آی تی و یا فردی که برنامه نویسی میکند در طول تحصیل خود باید توانایی حل مسائل مختلف به کمک زبانهای برنامه نویسی را فرا بگیرد و در واقع باید بتواند برنامههای مناسبی برای حل مسائل مختلف بنویسد.
هر برنامه از دو بخش تشکیل میشود که عبارت اند از:
1) ساختمان داده یا ساختمان داده های در نظر گرفته شده برای الگوریتمهای برنامه مان
2) الگوریتم هایی که روی داده ها اجرا میشوند
ساختمان داده ها برای دریافت دادهها توسط کامپیوتر جهت پیاده سازی و اجرای الگوریتمها مورد استفاده قرار میگیرند، اما الگوریتمها دستورالعملهایی هستند که بر روی دادهها اعمال میشوند.
برنامهای خوب است که هم ساختمان داده مناسبی داشته باید و هم از الگوریتمهای بهینه تری استفاده کند. بعنوان مثال فرض کنید میخواهید برنامهای بنویسید که 50 عدد صحیح از ورودی بگیرد و آنها را مرتب کند و در خروجی نمایش دهد، در این مثال بهترین ساختمان دادهای که میتوانیم استفاده کنیم آرایه است (چون تعداد اعداد ورودی ثابت و مشخص است)، اما برای مرتب کردن این اعداد میتوانیم از الگوریتمهای مختلفی نظیر مرتب سازی حبابی (Bubble Sort)، مرتب سازی درجی (Insertion sort)، مرتب سازی سریع (Quick Sort)، مرتب سازی انتخابی (Selection Sort) و یا دیگر الگوریتمهای مرتب سازی استفاده کرد.
همان طور که گفتیم الگوریتمی که برای یک برنامه نوشته ایم روی داده ها کار میکند و آنها را پردازش میکنند، برای اینکه بتوانیم این امکان را برای الگوریتم فراهم کنیم تا راحت تر بتواند دادهها را پردازش بکند باید بتوانیم دادهها را به شکلی مناسب و مختص آن الگوریتم ذخیره سازی یا سازماندهی کنیم، برخی از ساختمان های داده برای پردازش بهتر و سریعتر داده مناسب است، برخی دیگر برای ذخیرسازی بهتر داده مناسب هستند، برخی از ساختمان داده ها، داده ها را بصورت فشرده تری ذخیره میکند. درس ساختمان داده به ما میآموزد که برای هر الگوریتم و برنامه ای چه ساختمان داده ای مناسب تر است.
ساختمان داده (Data Structure) چگونگی آرایش دادهها در حافظهی کامپیوتر را مشخص میکند. هر ساختمان داده بسته به طراحی و هدفی که دنبال میکند، الگوریتمهای ویژهای به منظور بازیابی، ذخیره سازی و حذف دادهها دارد. طراحی هر ساختمان داده طوری انجام میشود که بتواند نیاز خاصی را برطرف کند، هر ساختمان داده مزایا و معایبی دارد و برنامه نویس با توجه به نیازهای برنامهای که طراحی میکند، میبایست ساختمان دادههای مناسبی را انتخاب کند و با توجه به این انتخاب، کارایی نرم افزار نهایی را تضمین نماید. بنابراین برنامه نویسان باید بر انواع ساختمانهای داده تسلط کافی داشته باشند
نوع داده های اولیه (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’ و ‘ ‘ (فاصله) و ‘%’ و یا هر کاراکتر دیگری را در خودش ذخیره کند
- String : این داده می تواند رشته ای از کاراکترها را در خودش ذخیره کند. برای مثال این مدل داده می تونه رشته های “konkurcomputer” یا “Data Structure” یا “۱۳۵79” را در خودش ذخیره کند
اگر این نوع های داده اولیه را به اشکال مختلف در کنار هم قرار دهیم ساختمان های داده پیچیده تر نظیر آرایه تشکیل میشود. مثلا اگر ما 10 تا عدد Integer را خیلی ساده در کنار هم قرار بدهیم یک بلاک یا یک سازمانی از داده ها تشکیل میشود که به آن آرایه میگویند
ساختمان دادههای متداول
انواع مختلفی از ساختار داده (همان ساختمان داده) وجود دارد که عموماً بر روی انواع داده های ابتدایی ساده تر ساخته شده است
- آرایه (Array)
- لیست پیوندی (Linked List)
- پشته (Stack or Push Down List or Pile)
- صف (Queue)
- درخت های ساده (Binary Tree)
- درخت جستجوی دودویی (Binary Search Tree)
- هرم (Heap)
آرایه
آرایه رایج ترین ساختار ذخیره داده است و اکثر زبانهای برنامه نویسی از آن بهره میبرند. همین طور برخی از مهم ترین ساختمان های داده نظیر لیست، پشته و صف با آرایه قابل طراحی و پیاده سازی هستند. همچنین از آرایه در طراحی بسیاری از الگوریتمها و حل بسیاری از مسائل به عنوان یک Lookup Table استفاده میشود:
تعریف آرایه:
آرایه مجموعهای از دادههایی است که خصوصیات زیر را داشته باشد :
- همگی از یک نوع داده باشند
- در خانههای پیوسته حافظه قرار گیرند
- تمامی این عناصر دادهای با استفاده از آدرس اولین عنصر و Index مربوط به عنصر مورد نظر، بطور مستقیم قابل دسترسی و آدرس دهی باشند
به زبان ریاضی، آرایه یک نگاشت (Mapping) از شاخصها به عناصر دادهای است
انواع آرایه
- آرایه تک بعدی
- آرایه های چند بعدی
در فیلم زیر موارد زیر درس داده شده است:
- بررسی تعداد عناصر، حافظه اشغالی و محاسبه آدرس شروع یک عنصر در آرایه تک بعدی
- بررسی آرایه دو بعدی و محاسبه تعداد عناصر آن
- بررسی انواع نحوه قرار گیری آرایه دو بعدی در حافظه
- بررسی آرایه سه بعدی و محاسبه آدرس شروع یک عنصر در آرایه 3 بعدی
- تدریس ماتریس پایین مثلثی
- حذف یک نود مشخص در لیست یک طرفه
- تدریس ماتریس 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:ARRAYl 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 = (u+1)/2
var l, u : integer;
l = 1;
u = n;
while 1 ≤ 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;
}
لیست پیوندی:
لیست پیوندی: لیست پیوندی ساختمان داده ای است که از یک تعداد نود تشکیل شده که هر نود یک رکورد شامل دیتا و آدرس نود بعدی است که به اصطلاح میگویند نود دارد به نود بعدی اشاره میکند، در لیست پیوندی هر نود میتواند در هر آدرسی از حافظه باشد
در فیلم زیر موارد زیر درس داده شده است:
- تعریف لیست پیوندی یک طرفه
- بررسی مرتبه عملیات درج و حذف در لیست پیوندی
- ساخت یک لیست پیوندی یک طرفه 1000 نوده
- نحوه درج نود در ابتدا لیست یک طرفه
- درج یک نود در لیست یک طرفه پس از یک عنصر مشخص
- حذف یک نود مشخص در لیست یک طرفه
- بررسی لیست پیوندی دو طرفه و درج یک نود بعد از یک نود مشخص
- حذف یک نود از لیست پیوندی دو طرفه
- بررسی لیست حلقوی و درج یک نود در ابتدای لیست حلقوی
- بررسی مسئله جوزف
ساختمان داده لیست پیوندی
کدهای عملیات مهم روی ساختمان داده لیست پیوندی
درج یک عنصر جدید در لیست پیوندی یک طرفه
حذف یک عنصر در لیست پیوندی یک طرفه
تعریف ساختمان داده لیست پیوندی دو طرفه
درج یک عنصر جدید در لیست پیوندی دو طرفه
حذف یک عنصر در لیست پیوندی دو طرفه
درج یک عنصر در لیست پیوندی یک طرفه چرخشی
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 (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;
}
صف
ساختمان داده صف یک لیست مرتب است که عناصر جدید به انتهای آن اضافه میشوند و از ابتدای آن حذف میگردند. ابتدای صف سر صف نامیده میشود. صف برای مدیریت نوبت عناصر از الگوریتم FIFO(First In First Out) استفاده میکند که بر طبق آن هر عنصری که زودتر وارد صف شود زودتر سرویس میگیرد
عملیاتی که روی صف انجام میگیرد
ENQUEUE (Q,X) : اضافه کردن عنصر x به انتهای صف Q
DEQUEUE (Q) : حذف یک عنصر از ابتدای صف Q و بازگرداندن آن عنصر بعنوان خروجی
ساختمان داده صف
کدهای عملیات مهم روی ساختمان داده صف
عملیات ENQUEUE در صف پیاده سازی شده با آرایه خطی
عملیات DEQUEUE در صف پیاده سازی شده با آرایه خطی
عملیات ENQUEUE در پشته پیاده سازی شده با آرایه حلقوی
عملیات DEQUEUE در پشته پیاده سازی شده با آرایه حلقوی
عملیات ENQUEUE در پشته پیاده سازی شده با لیست پیوندی
عملیات DEQUEUE در پشته پیاده سازی شده با لیست پیوندی
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;
}
درخت
ساختمان داده درخت یا به اختصار درخت، نشان دهنده یک ساختار سلسله مراتبی است که در علوم کامپیوتر کاربردهای گستردهای پیدا کرده است. از درخت به منظور آنالیز مدارهای الکترونیکی، بیان رابطههای، سازماندهی دادهها در پایگاه های دادهای و بیان ساختارهای گرامری در کامپایلرها استفاده میشود.
درخت مجموعه ای از عناصر است که گره نام دارند، یکی از این گرهها در جایگاه ریشه درخت قرار گرفته است و سایر گره ها در زیر ریشه قرار دارند. یک گره میتواند حاوی هر دادهای اعم از عدد، حرف، رشته ای از حروف و غیره باشد.
در فیلم زیر موارد زیر درس داده شده است:
- تعریف بازگشتی درخت
- تعریف مفاهیمی نظیر برادر، نوه، جد، نودهای داخلی، برگ، درجه هر نود در درختها
- تعریف مواردی نظیر تعداد لول، شماره سطوح، ارتفاع و عمق در درختها
- ارائه فرمولهایی برای محاسبه ماکزیمم نودها، برگها و نودهای داخلی یک درخت پر
- چگونگی پیمایشهای پیش ترتیب، پس ترتیب، میان ترتیب و سطح ترتیب در درخت
- دخیره درخت در کامپیوتر با استفاده از آرایه
- ذخیره درخت در کامپیوتر با استفاده از لیست پیوندی
ساختمان داده درخت
درخت جستجوی دودویی (BST: Binary Search Tree)
درخت جستجوی دودویی یک درخت دودویی است که میتواند خالی باشد و در صورتی که خالی نباشد باید شرایط زیر را داشته باشد
- هر نود باید دقیقا یک کلید داشته باشد
- کلید همه نودهای زیر درخت سمت چپ هر نود، باید کوچکتر یا مساوی با کلید آن نود باشد
- کلید همه نودهای زیر درخت سمت راست هر نود، باید بزرگتر از کلید آن عنصر باشد
توجه: میتوان تعریف درخت BST را طوری نوشت که نودهایی با کلید مساوی با کلید یک نود، به جای زیر درخت چپ، در زیر درخت راست آن قرار گیرند.
تمامی الگوریتمهای جستجو، درج، حذف، یافتن Minimum، یافتن Maximum، یافتن عنصر بعدی و پیشین یک عنصر مشخص همگی از مرتبه ارتفاع درخت BST هستند
ساختمان داده BST
کدهای عملیات مهم روی ساختمان داده BST
پیاده سازی درخت BST
جستجو در درخت BST
درج در درخت BST
یافتن ماکزیمم در BST
یافتن عنصر بعدی یک عنصر در BST
یافتن عنصر قبلی یک عنصر در 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)
MaxHeap یا Binary MaxHeap درخت کاملی که داخل هر نود آن یک عدد است که آن عدد بزرگتر مساوی فرزندانش است.
ساختمان داده Heap
کدهای عملیات مهم روی ساختمان داده هیپ
درج عنصر در هیپ
حذف رشته در maxheap
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);
}
}
مقایسه ساختمان داده های پر استفاده:
در بررسی ساختمان های داده، همیشه باید به مزایا و معایب آنها در کاربرد مورد نیاز توجه داشت. هر ساختمان داده، مزایایی دارد که آن را برای کاربرد خاصی متمایز میکند. در بحث مزایا و معایب ساختمان های داده معمولا سه عملیات درج، حذف و بازیابی عنصر مد نظر است. در شکل زیر برخی از انواع ساختمان های داده پر کاربرد به همراه مزایا و معایب هر یک از آنها آمده است.
مزایا و معایب برخی از ساختمان داده های پر کاربرد | ||||
---|---|---|---|---|
ردیف | نام ساختمان داده | مزایا | معایب | |
1 | لیست نامرتب پیاده سازی شده با آرایه | درج سریع در انتها لیست | جستجو کند - حذف کند – ایستا بودن ساختمان داده | |
2 | لیست مرتب پیاده سازی شده با آرایه | جستجو سریع تر در مقایسه با مورد بالا | درج کند – حذف کند – ایستا بودن ساختمان داده | |
3 | لیست پیاده سازی شده با لیست پیوندی | درج سریع | جستجو کند - حذف کند – ایستا بودن ساختمان داده | |
4 | پشته | ارائه دسترسی LIFO(Last In First Out) | دسترسی محدود به اولین عنصر درج شده | |
5 | صف | ارائه دسترسی FIFO(First In First Out) | دسترسی محدود به برخی عناصر | |
6 | درخت دودویی جستجو | درج و حذف و جستجو سریع | الگوریتم های عملیات ساختمان داده پیچیده است | |
7 | هرم بیشینه | درج و حذف سریع – دسترسی سریع به بزرگترین عنصر | دسترسی کند به دیگر عناصر |
اصلی ترین موضوعاتی که در مطالعه ساختمانهای داده مطرح میشوند
1) ایستا و پویا (Static and Dynamic)
ایستایی و پویایی ساختمانهای داده، به بحث در مورد حافظه مورد استفادهی آنها اختصاص دارد. میزان فضای مورد نیاز یک ساختمان داده ایستا، از ابتدای پیدایش تا پایان عمر آن ثابت است، بنابراین این ساختمانهای داده نمیتوانند بیش از میزان معینی داده ذخیره کنند. از سویی دیگر ساختمان دادههای پویا همان طور که رشد میکنند (تعداد عناصرشان افزایش مییابد) فضای بیشتری را به خود اختصاص میدهند و هنگامی که کوچک میشوند (عناصرشان حذف میشوند) فضاهای غیر لازم را آزاد مینمایند. ایستایی و پویایی ساختمانهای داده، در بسیاری از موارد به چگونگی پیاده سازی آنها بر میگردد. بعنوان مثال ساختمان داده لیست را میتوان به وسیله آرایه و یا لیست پیوندی طراحی و پیاده سازی کرد که در حالت اول لیست ایستا و در حالت دوم لیست پویا ایجاد میشود
2) صریح و ضمنی (Explicit and Implicit)دو نوع سازماندهی داده در ساختمانهای داده مطرح است. در سازماندهی صریح (Explicit)، از اشاره گرها (Pointer) به منظور ایجاد ارتباط میان عناصر دادهای استفاده میشود، مانند لیستهای پیوندی. در ساختمان دادههای ضمنی روابط ریاضی، میان عناصر وجود دارد و از این روابط به منظور بازیابی آنها استفاده میشود، مانند پیاده سازی هیپ (Heap) یا همان هرم با استفاده از آرایه. ساختمانهای دادهای صریح، نیازمند تخصیص فضایی برای ذخیره سازی اشاره گرها هستند، بنابراین ساختمانهای دادهای ضمنی از لحاظ مصرف حافظه کاراتر هستند
3) زمان و حافظهساختمانهای داده، اغلب میان زمان و حافظه مصرفی تعادل برقرار میکنند، در اکثر مواقع میتوان این قانون را در مقایسه ساختمانهای داده مطرح کرد که : با تخصیص حافظه بیشتر برای ساختمان داده میتوان پیچیدگی زمانی ساختمان داده را بهبود بخشید و سرعت عملیات روی آن ساختمان داده را بالا برد.
بعنوان مثال فرض کنید هدف طراحی ساختمان دادهای باشد که بیان کند در مجموعهای شامل یک میلیون عدد غیرتکراری از بازه [1و 10^9 ] چه اعدادی وجود دارند و چه اعدادی وجود ندارد. برای این منظور دو طراحی میتوان ارائه کرد
- آرایه ای از بیت ها به طول 10^9 در نظر گرفته میشود که 0 یا 1 بودن هر خانه از آرایه نشان دهنده وجود یا عدم وجود عدد متناظر با آن خانه باشد. به شکل زیر توجه کنید.
در صورت اضافه شدن یا حذف یک عنصر از مجموعه عناصر، عملیات لازم برای بروزرسانی این ساختمان داده از مرتبه O(1) خواهد بود، زیرا تنها کافی است مقدار یک بیت در آرایه تغییر کند. همچنین عملیات مورد نیاز برای اطلاع از وجود یا عدم وجود یک عنصر در مجموعه نیز از مرتبه O(1) است.
- از یک درخت متوازن استفاده کنیم و اعداد درون مجموعه مان را در آن قرار دهیم. در این ساختمان داده عملیات درج و حذف یک عنصر و همین طور عملیات مورد نیاز برای اطلاع از وجود یا عدم وجود یک عنصر از مرتبه O(logn) است
در طراحی اول پیچیدگی زمان عملیاتی که برای روی ساختمان داده انجام میشود ایده آل است، ولی مصرف حافظه آن تا حدی زیاد است که استفاده از آن را در بسیاری از کاربردها عملا غیر ممکن میسازد، اما طراحی دوم هر چند از نظر پیچیدگی زمانی عملیاتی که بر روی ساختمان داده انجام میشود کارایی طراحی اول را ندارد ولی از نظر مصرف حافظه مطلوب و قابل پیاده سازی است.
مراحل حل مسئله در ساختمان داده و طراحی الگوریتم:
مراحل مختلف حل یک مسئله و در واقع نوشتن برنامه بصورت زیر است:
- تبدیل مسئله به یک مدل ریاضی (مدل انتزاعی) قابل حل توسط کامپیوتر
- طراحی الگوریتمی برای حل آن مسئله
- انتخاب داده ساختار(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 خواهد شد.
اطلاع از نرخ رشد برخی از توابع رایج به شما در تحلیل پیچیدگی زمانی الگوریتمها کمک میکند
نرخ رشد توابع

برای آنکه بدانید رشد کدام توابع بیشتر است به جدول زیر توجه کنید
nnn |
nn! |
2n! |
22n |
nn |
(n+1)! |
n! |
(log n)n |
en |
n.2n |
2n ≈ 2n-1 |
(3/2)n |
nlog n |
(log n)log n |
(log n)! |
n3 |
7lg n = 7log 2 n = nlog 2 7 ≈ n2.81 |
n2 |
nlog(n) ≈ log(n!) ≈ log(nn) |
n |
√ n log n |
√ n log n |
√ n |
log2 n |
log n |
√ log n |
log(log n) |
1 |
4/n (نرخ رشد منفی) |
2) بررسی ساختمان داده ها
ساختمانهای دادهای مجموعهای از اشیا از نوعی خاص را ذخیره میکنند، این اشیا عناصر ساختمان داده (Element of Data Structure) نام دارند. معمولا عناصر یک ساختمان داده همگی از یک نوع داده (Data Type) هستند. هر ساختمان داده توسط عملیاتی که روی داده هایش میتواند انجام شود و قوانین قرارگیری دادههایش در حافظه تعریف میشود.
عملیات روی هر ساختمان داده را میتوان در دو دسته کلی طبقه بندی کرد:
1) Query ها یا درخواست ها
2) Update ها
Queryها آن دسته از عملیات هستند که تغییری در محتویات ساختمان داده ها ایجاد نمیکنند، مانند جستجوی یک عنصر، شمارش تعداد عناصر موجود در ساختمان داده و ...
Update ها عملیاتی هستند که سبب تغییر در مقدار یا چینش عناصر ساختمان داده میشوند، مانند اضافه کردن یک عنصر جدید، حذف عناصر موجود و ...
کارایی یک ساختمان داده با استفاده از پیچیدگی زمانی عملیاتی که روی آن ساختمان داده انجام میشود مشخص میشود، همچنین میزان حافظه مصرفی یک ساختمان داده نیز ملاکی برای کارایی آن است، البته توجه کنید که کارایی تنها عاملی نیست که در تعیین کیفیت ساختمان داده موثر است و عوامل دیگری نظیر سادگی ساختاری و سادگی در پیاده سازی نیز کیفیت یک ساختمان داده را مشخص میکند
توضیحات کلی درس ساختمان داده:
درس ساختمان داده و طراحی الگوریتم را میتوان مهم ترین و کاربردی ترین درس رشته کامپیوتر و همین طور مهم ترین و تاثیرگذارترین درس در کنکور ارشد کامپیوتر و آی تی و همچنین مهم ترین دروس در کنکور دکتری رشته های نرم افزار، هوش مصنوعی، شبکه و رایانش و فناوری اطلاعات دانست.
اگر قصد ادامه تحصیل در مقطع دکتری رشته کامپیوتر دارید، کسب اطلاعات درباره تعداد سوالات و ضریب دروس در کنکور دکتری کامپیوتر خالی از لطف نیست.
ساختمان داده مجموعه ای از داده ها ، روابط بین آنها و توابع یا عملیاتی است که میتوان روی آنها اعمال نمود.
مطالعات دانشجویان مقطع ارشد و دکتری تا حد زیادی به این دو درس وابسته است، چراکه طراحی الگوریتم و ساختمان داده در تولید مقالات علمی کاربردی فراوان دارند.
درس ساختمان داده رابطه تنگاتنگی با درس طراحی الگوریتم دارد. به شکلی که می توان این دو درس را مکمل یکدیگر دانست. پیش نیاز بسیاری از مطالب طراحی الگوریتم در درس ساختمان داده نهفته است.تست های ساختمان داده و طراحی الگوریتم در آزمون های ارشد و دکتری
در کنکور ارشد آی تی از درس ساختمان داده و طراحی الگوریتم مجموعا 12 تست ضریب 4 ، که 6 تست آن متعلق به درس ساختمان و 6 تست آن متعلق به درس طراحی الگوریتم است مطرح میشود. در کنکور ارشد کامپیوتر هنوز مشخص نیست که در کنکور ارشد کامپیوتر 1400 چند تست از دو درس ساختمان داده و طراحی الگوریتم مطرح میشود ولی حدس ما این است که 7 تست از درس ساختمان داده و 7 تست از طراحی الگوریتم مطرح شود. ضریب درس های ساختمان داده و طراحی الگوریتم در گرایش های هوش مصنوعی، نرم افزار، بیوانفورماتیک، علوم داده، الگوریتم و محاسبات و قرآن کاوی رایانشی 4 و در گرایش های شبکه های کامپیوتری، معماری کامپیوتر و علوم و فناوری شبکه 3 است. برای کسب اطلاعات بیشتر در خصوص دروس کنکور ارشد و ضرایب آن به صفحه دروس مورد آزمون و ضرایب آن در کنکور ارشد مهندسی کامپیوتر مراجعه کنید.
در کنکور دکتری رشته های نرم افزار، هوش مصنوعی و شبکه و رایانش از این دو درس 20 تست با بالاترین ضریب یعنی ضریب 4 مطرح میشود؛ همچنین در کنکور دکتری فناوری اطلاعات 10 تست ساختمان داده و 5 تست طراحی الگوریتم هر دو با ضریب 4 مطرح میشود. این تعداد تست در کنکورهای دکتری و با بالاترین ضریب، یعنی ضریب 4، نشان دهنده اهمیت فوق العاده این دو درس در کنکورهای دکتری است.
با توجه به موارد ذکر شده، ساختمان داده از سه جهت بسیار مهم است؛ از جهت تعداد تستها و ضریبی که در کنکور ارشد مهندسی کامپیوتر و فناوری اطلاعات و همچنین کنکور دکتری کامپیوتر به خود اختصاص میدهد، به جهت درک مناسب درس طراحی الگوریتم و در آخر وابستگی زیاد دنیای پژوهش به این درس
مراجع درس ساختمان داده
اصلی ترین مرجع درس ساختمان داده که در دانشگاههای معتبر دنیا تدریس میشود کتاب Introduction to Algorithms معروف به CLRS است؛ نویسندگان این کتاب Clifford STEIN ،RIVEST ،LEISERSON ،CORMEN هستند. همچنین کتابهای COMPUTER ALGORITHM (نوشته شده توسط Ellis Horowitz، Sartaj Sahn و Sanguthevar Rajasekar)، و کتاب مرجع Data Structures and Algorithm Analysis ( نوشته Clifford A. Shaffer) نیز در برخی از دانشگاههای ایران و جهان تدریس میشوند.
برای صرفه جویی در زمان شما دانشجویان عزیز، این کتابها را در زیر این مطلب برایتان قرار دادهایم تا شما به راحتی بتوانید آن ها را دانلود کنید. البته خواندن کتابهای مرجع را به دانشجویان ترمهای پایینتر توصیه میکنیم نه به دانشجویانی که قصد شرکت در کنکور اشد و دکتری کامپیوتر و آی تی را دارند. دانشجویانی که قصد دارند برای کنکور ارشد و یا دکتری کامپیوتر و آی تی این درس مهم را بخوانند میتوانند از منابعی که در قسمت منابع کنکور ارشد کامپیوتر معرفی شده استفاده کنند.فصلهای درس ساختمان داده و ارتباط آنها با طراحی الگوریتم
در درس ساختمان داده مطالب بسیاری از درس طراحی الگوریتم پوشش داده میشود. فصلهای مرتبه اجرایی کدها و نمادهای مجانبی، روابط بازگشتی، درهم سازی، مرتبسازی، جستجو و ... که در درس ساختمان داده و درس طراحی الگوریتم مشترک است، در این درس گفته خواهد شد، بنابراین با خواندن درس ساختمان داده میتوانید پیش زمینه و دید خوبی برای خواندن درس طراحی الگوریتم پیدا کنید و حتی شاید بتوانید به برخی از سوالات درس الگوریتم نیز پاسخ دهید.
سر فصل مطالبی که در درس ساختمان داده ها وجود دارد عبارت است از:
مرتبه زمانی شبه کدها، رشد توابع، الگوریتمهای بازگشتی، انواع درختها و درختهای ویژه، مرتب سازی، درهم سازی، آرایه و صف و پشته، مجموعه های مجزا
برای مشاهده اهمیت هر فصل و اینکه در سالهای اخیر از هر فصل چه تعداد تست در کنکور مطرح شده میتوانید به صفحات بودجه بندی کنکور ارشد کامپیوتر و بودجه بندی کنکور ارشد فناوری اطلاعات رجوع کنید.
آموزش ساختمان داده
علی رغم اهمیت بسیار زیاد درس ساختمان های داده در رشته های کامپیوتر و آی تی، متاسفانه در دانشگاههای کشور چندین مشکل در ارائه این درس وجود دارد؛ مشکل اول این که سرفصل های اعلامی وزارت علوم برای کنکور به طور کامل توسط دانشگاه ها تدریس نمی شود. از جمله این سرفصل ها می توان به شار، درجه سختی الگوریتم ها و مسائل پی و ان پی، مجموعه های مجزا، درخت قرمز سیاه و بسیاری موارد دیگراشاره کرد. مشکل دوم این که مباحث مورد تدریس در دانشگاه ها به صورت کامل و بصورت 0 تا 100 نیست که همین امر موجب عدم توانایی دانشجویان در پاسخگویی به تست های کنکور می شود. آموزش کامل و 0 تا 100 همراه با بیان ساده در درس ساختمان داده باعث میشود دانشجویان رشته کامپیوتر بطور کامل مفاهیم این درس را متوجه شوند و بتوانند به تستهای کنکور پاسخ دهند.
مجموعه کنکور کامپیوتر جهت تسهیل در امر آموزش درس ساختمان داده ها، فیلم های مربوط به این درس را به صورت کامل برای شما دانشجویان عزیز گردآوری و تدوین نموده است. این فیلم ها را میتوانید براحتی در زیر مشاهده کنید.
فیلم هایی که برای شروع ساختمان نیاز دارید
برای تماشای فیلمهای بیشتر از درس ساختمان داده به لینک رو به رو مراجعه کنید: آموزش ساختمان داده
خرید فیلم های درس ساختمان داده
در فیلم ساختمان داده مطالب بسیار پایهای و از 0 تا 100 و با تمامی جزییات ممکن آموزش داده میشود و دانشجویانی که حتی این درس را پاس نکردهاند یا رشته شان چیز دیگری است کاملا متوجه همه مطالب خواهند شد. دانشجویان عزیز توجه کنند که برای تهیه فیلم های ساختمان داده نیاز به هیچ پیش نیازی ندارند و هر پیش نیازی که نیاز باشد در فیلم های ساختمان داده گفته شده است. بطور کلی دروس پایه رشته کامپیوتر و مورد نیاز همه افرادی که قصد ورود به دنیای کامپیوتر را دارند عبارتند از: ساختمان داده و طراحی الگوریتم، مدار منطقی، معماری کامپیوتر، سیستم عامل و شبکه های کامپیوتری است.
برای کسب اطلاعات بیشتر در مورد فیلم ها و کلاس های آنلاین دروس کنکور ارشد کامپیوتر و آی تی به قسمت کلاسهای کنکور ارشد کامپیوتر مراجعه کنید.
خرید فیلم های حل تست ساختمان داده و طراحی الگوریتم
درس ساختمان داده و طراحی الگوریتم درس حجیمی است و برای به تسلط رسیدن در این درس نیاز است تعداد تست زیادی را حل کنید.
در نکته و تست ساختمان داده و طراحی الگوریتم حدود 420 تست مفهومی کنکور ارشد کامپیوتر و آی تی و علوم کامپیوتر و همین طور کنکور دکتری بطور کامل بررسی شده است. تمامی نکات مطرح شده در کنکور ارشد و دکتری، به طور کامل و با چندین مرحله تکرار در فیلم های نکته و تست بیان شده اند.
توصیه می کنیم مصاحبه های رتبه های برتر کنکور ارشد کامپیوتر و آی تی را مشاهده کنید تا به اهمیت استفاده از فیلم های آموزشی نکته و تست درس ساختمان های داده و طراحی الگوریتم پی ببرید.
خرید فیلم های ساختمان داده و طراحی الگوریتم
ویدیو درس ساختمان داده

ویدیو درس طراحی الگوریتم

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

منابع و مراجع
https://www.geeksforgeeks.org/data-structures/
https://searchsqlserver.techtarget.com/definition/data-structure
https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42
ساختمان داده چیست؟
درس ساختمان داده بررسی و پژوهش در مورد روشهای گوناگون ذخیره، نگهداری و بازیابی اطلاعات در سیستمهای کامپیوتری به گونهای که این اطلاعات بتواند بطور کارامد مورد استفاده قرار گیرد میپردازد. برای تمامی دانشجویانی که علاقهمند به کارهای پژوهشی و یا دادن الگوریتمهای بهینه برای مسائل و چالشهای موجود و یا برنامه نویسی هستند، داشتن دانش ساختمان دادهها و الگوریتمها به آنها یک نگاه ویژه و متفاوت برای حل مسائل میدهد. داشتن دانش کافی در مورد درس ساختمان دادهها باعث میشود که دانش پژوهان بتوانند بررسی کنند که آیا راه حلهایی که ارائه میدهند از جوانب گونانونی مانند مرتبه زمانی، میزان حافظه مصرفی، قابلیت توسعه، میزان مصرف توان و ...بهینه هستند یا خیر
درس ساختمان داده دارای چه سر فصل هایی است؟
سر فصل مطالبی که در این درس وجود دارد عبارت است از: بدست آوردن مرتبه زمانی شبه کدها، بررسی رشد توابع گوناگون، بررسی الگوریتمها و توابع بازگشتی، درختها، درختهای ویژه، مرتب سازی، درهم سازی، آرایه، صف، پشته و مجموعه های مجزا
مرجع اصلی درس ساختمان داده چیست؟
از سال 90 به بعد مرجع اصلی این درس در دانشگاه های کشور و همین طور کنکور ارشد کامپیوتر کتاب CLRS است، همچنین کتاب هرویتز هم یکی از منابع دیگر ساختمان داده است. تمامی مراجع درس ساختمان داده را بصورت رایگان میتوانید از قسمت دانلود رایگان کتاب های مرجع سایت کنکور کامپیوتر دانلود کنید
آیا فیلم های آموزش ساختمان داده به زبان ساده است؟
در فیلم های ساختمان داده تدریس از پایه و از 0 تا 100 داده شده است، و برای تماشا این فیلم ها نیاز به هیچ پیش نیازی نخواهد داشت و تمامی مطالب به ساده ترین روش ممکن تدریس شده است. نمونه این فیلم ها را میتوانید در صفحه فیلم های آموزشی سایت کنکور کامپیوتر مشاهده کنید
آيا همراه فیلم های آموزشی ساختمان داده استاد رضوی جزوه وجود دارد؟
بله، به تمام افرادی که فیلم های استاد رضوی را تهیه میکنند جزوات درس بصورت پی دی اف تمام رنگی، داده میشود که دانشجویان میتوانند بر روی لب تاپ از اینها استفاده کنند و یا این که پی دی اف ها را پرینت بگیرند
در کنکور ارشد کامپیوتر چند تست از درس ساختمان داده مطرح میشود؟
با توجه به تغییرات به وجود آمده در کنکور ارشد کامپیوتر هنوز مشخص نیست که چند تست از درس ساختمان داده و طراحی الگوریتم در کنکور ارشد کامپیوتر امسال مطرح میشود ولی حدس تیم کنکور کامپیوتر این است که 7 تست از درس ساختمان داده و 7 تست از درس طراحی الگوریتم در کنکور امسال مطرح شود
ضریب درس ساختمان داده و طراحی الگوریتم در گرایش های مختلف کنکور ارشد کامپیوتر چند است؟
ضریب مجموعه دروس ساختمان داده، طراحی الگوریتم و هوش مصنوعی در گرایش های مختلف متفاوت است، ضریب این مجموعه درس در گرایش های شبکه های کامپیوتری، رایانش امن، معماری کامپیوتر و علوم و فناوری شبکه 3، و در گرایش های هوش مصنوعی، نرم افزار، بیوانفورماتیک علوم داده، الگوریتم و محاسبات و قرآن کاوی رایانشی 4 است.
در کنکور ارشد آی تی از درس ساختمان داده و طراحی الگوریتم چند تست مطرح میشود و ضریب این درس چند است؟
دروس ساختمان داده و طراحی الگوریتم از دروس مشترک و ضریب 4 کنکور ارشد فناوری اطلاعات است و 12 سوال از این دو درس در کنکور ارشد آی تی مطرح میشود
آیا در کنار فیلم ها نیازی به مطالعه کتاب وجود دارد؟
در دروسی که مربوط به تدریس استاد رضوی است اگر فیلم درس و نکته و تست را تماشا کنید نیازی به مطالعه هیچ کتاب دیگری در کنار اینها نخواهید داشت، اما در دروس دیگر اگر فیلم تهیه میکنید بهتر است که برای تست زنی کتابی نیز در کنار فیلم ها داشته باشید البته اگر هم کتاب تهیه نکنید مشکل خاصی پیش نمیآید . داشتن کتاب بطور کلی خوب است
از چه زمانی میتوان دیدن این فیلم ها را شروع کرد؟
به علت اینکه ساختمان داده از جمله مهم ترین دروس رشته کامپیوتر است به دانشجویان رشته کامپیوتر توصیه میشود که از ترم های اول این فیلم ها را مشاهده کنند، در این فیلم ها مطالب بسیار مفهومی و عمقی و از 0 تا 100 تدریس شده است که این موضوع باعث میشود که پایه دانشجویان در همان ترم های ابتدایی بسیار قوی شود که این مورد به یادگیری سایر دروس نیز کمک میکند. توجه کنید که این فیلم ها کنکوری نیستند و بطور کلی واژه کنکوری واژه است که برای کنکور سراسری لیسانس مناسب است، در کنکور ارشد و دکتری کامپیوتر و آی تی، سوالات، بسیار مفهومی و عمیق مطرح میشوند به همین علت برای کسب یک رتبه خوب در کنکور ارشد و دکتری کامپیوتر و آی تی نیاز نیست مانند کنکور سراسری درصدهای خیلی بالایی را کسب کنید و اگر شما بتوانید به 50 درصد سوالات هر درس پاسخ دهید میتوانید رتبه 1 کنکور ارشد و دکتری کامپیوتر و آی تی شوید، بنابراین افرادی در کنکور ارشد و دکتری کامپیوتر موفق میشوند که بسیار عمیق و مفهومی مطالعه کرده باشند، به همین علت در فیلم های تولید شده مطالب بسیار عمیق و مفهومی گفته شده است و بنابراین همه دانشجویان میتوانند از این فیلم ها استفاده کنند، چه دانشجویانی که کنکور دارند و چه دانشجویانی که در ترم های پایین تر هستند و حتی هنوز این دروس را پاس نکرده اند