معرفی درس ساختمان داده رشته کامپیوتر

ساختمان داده چیست:‌

یک برنامه تشکیل شده از یکسری داده های ورودی، که برنامه ما یک الگوریتمی را روی داده های ورودی اجرا می‌کند و سپس داده های خروجی برای ما تولید می‌کند. بعنوان مثال ما برنامه ای داریم که لیست دانشجویان یک کلاس را به آن می‌دهیم و برنامه ما طبق الگوریتمی که برایش مشخص کرده ایم افرادی که معدل شان بالای 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 را خیلی ساده در کنار هم قرار بدهیم یک بلاک یا یک سازمانی از داده ها تشکیل می‌شود که به آن آرایه می‌گویند

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

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

1. آرایه (Array)
2. لیست پیوندی (Linked List)
3. پشته (Stack or Push Down List or Pile)
4. صف (Queue)
5. درخت های ساده (Binary Tree)
6. درخت جستجوی دودویی (Binary Search Tree)
7. هرم (Heap)

آرایه

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

تعریف آرایه:

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

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

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

انواع آرایه

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

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

1. بررسی تعداد عناصر، حافظه اشغالی و محاسبه آدرس شروع یک عنصر در آرایه تک بعدی
2. بررسی آرایه دو بعدی و محاسبه تعداد عناصر آن
3. بررسی انواع نحوه قرار گیری آرایه دو بعدی در حافظه
4. بررسی آرایه سه بعدی و محاسبه آدرس شروع یک عنصر در آرایه 3 بعدی
5. تدریس ماتریس پایین مثلثی
6. حذف یک نود مشخص در لیست یک طرفه
7. تدریس ماتریس 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;
}

لیست پیوندی:‌

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

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

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 (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 (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;
}

درخت

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

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

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

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

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

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

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

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

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

تمامی الگوریتم‌های جستجو، درج، حذف، یافتن Minimum، یافتن Maximum، یافتن عنصر بعدی و پیشین یک عنصر مشخص همگی از مرتبه ارتفاع درخت 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

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

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) ایستا و پویا (Static and Dynamic)

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

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

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

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

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

در صورت اضافه شدن یا حذف یک عنصر از مجموعه عناصر، عملیات لازم برای بروزرسانی این ساختمان داده از مرتبه 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 ها عملیاتی هستند که سبب تغییر در مقدار یا چینش عناصر ساختمان داده می‌شوند، مانند اضافه کردن یک عنصر جدید، حذف عناصر موجود و ...
کارایی یک ساختمان داده با استفاده از پیچیدگی زمانی عملیاتی که روی آن ساختمان داده انجام می‌شود مشخص می‌شود، همچنین میزان حافظه مصرفی یک ساختمان داده نیز ملاکی برای کارایی آن است، البته توجه کنید که کارایی تنها عاملی نیست که در تعیین کیفیت ساختمان داده موثر است و عوامل دیگری نظیر سادگی ساختاری و سادگی در پیاده سازی نیز کیفیت یک ساختمان داده را مشخص می‌کند

توضیحات کلی درس ساختمان داده:‌

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

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

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

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

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

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

در کنکور دکتری رشته های نرم افزار، هوش مصنوعی و شبکه و رایانش از این دو درس 20 تست با بالاترین ضریب یعنی ضریب 4 مطرح می‌شود؛ همچنین در کنکور دکتری فناوری اطلاعات 10 تست ساختمان داده و 5 تست طراحی الگوریتم هر دو با ضریب 4 مطرح می‌شود. این تعداد تست در کنکورهای دکتری و با بالاترین ضریب، یعنی ضریب 4، نشان دهنده اهمیت فوق العاده این دو درس در کنکورهای دکتری است.

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

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

دانلود کتاب shaffer

دانلود کتاب CLRS

دانلود حل مسائل CLRS

دانلود کتاب Horowitz

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

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

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

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

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

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

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

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

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

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

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

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

نکته و تست ساختمان داده جلسه 1 قسمت 1

نکته و تست ساختمان داده جلسه 1 قسمت 2

نکته و تست ساختمان داده جلسه 1 قسمت 3

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

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

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

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

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

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

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

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

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

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

مدرس: رامین رضوی

 

 

طول دوره: ۶۴ ساعت

زمان برگزاری: این کلاس برگزار شده است

۲5۰,۰۰۰ تومان برای بررسی تخفیف به سایت کافه تدریس مراجعه شود

مشاهده و ثبت نام

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

مدرس: رامین رضوی

 

 

طول دوره: ۴۰ ساعت

زمان برگزاری: این کلاس برگزار شده است

۱8۰,۰۰۰تومان برای بررسی تخفیف به سایت کافه تدریس مراجعه شود

مشاهده و ثبت نام

 

 

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

مدرس: رامین رضوی

 

 

طول دوره: ۶۶ ساعت

زمان برگزاری: این کلاس برگزار شده است

۲۸۰,۰۰۰ تومان برای بررسی تخفیف به سایت کافه تدریس مراجعه شود

مشاهده و ثبت نام