ساختمان داده چیست؟ آموزش ساختمان داده به زبان ساده

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

جشنواره کوله‌پشتی کافه‌تدریس

30% 730,000 تومان 511,000 تومان

رامین رضوی

۶۴ ساعت

خرید دوره

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

جشنواره کوله‌پشتی کافه‌تدریس

25% 650,000 تومان 487,500 تومان

رامین رضوی

۶۶ ساعت

خرید دوره

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

اصلی ترین مرجع درس ساختمان داده که در دانشگاه‌‌های معتبر دنیا تدریس می‌شود کتاب 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) نیز در برخی از دانشگاه‌های ایران و جهان تدریس می‌شوند.

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

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

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

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

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

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

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

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

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

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

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

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

نوع داده های اولیه (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] \lt 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] \lt 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

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 \lt
   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 \lt
   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] \lt
   H.Elements[2*i] then
		  largest = 2*i;
	  if 2*i+1 ≤ H.NOE and H.Elements[largest] \lt
   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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

نمایش بیشتر

نمایش کمتر

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

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

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

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

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

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

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

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

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

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

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

رامین رضوی

RAMIN RAZAVI

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

 

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

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

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

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

جشنواره کوله‌پشتی کافه‌تدریس

30% 730,000 تومان 511,000 تومان

رامین رضوی

۶۴ ساعت

خرید دوره

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

جشنواره کوله‌پشتی کافه‌تدریس

25% 650,000 تومان 487,500 تومان

رامین رضوی

۶۶ ساعت

خرید دوره

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

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

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

منابع و مراجع

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

سوالات متداول

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

ساجده فدائی

کیان انواری

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

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

معین منعمی

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

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

بهمن قائدی

مهدی مزارعی

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

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

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

Amir hossein

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

emelkabi

آرش آریا

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

علیرضا ملکی

علی فتحی وافق

غزل موسوی

mitra joodaki

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

سجاد محمدنیا

یاسمین

بهنام پروین

مرتضی آشوری

انوش مه جبین

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

سعید راصدی

مهدی فرح روز

یوسف عباسی

پوریا پلنگ زا

مهدی حسنی

احمد بنائیان

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

پریسا محمودی

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

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

کوثرکلهری

zahra mansouri

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

محیا اشرفی

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

حسین پری نور

sadra

پریسا نکوگل

محسن سروری

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

علی بابایی

hadi saadati

علی اله وردی

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

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

اشکان پارسایی

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

هانیه طالبی

ندا نوروزی

اسما سهرابی

فرح رضایی

حامد ترابی

Ali.Hp

مجید جنگی زهی

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

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

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

khajevandi

سیدمحمدمهدی

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

نگین دبیران

مرتضی حاجی آبادی

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

امیر سعادت

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

dorsa sadat zarrabi

الینا اشرف پور

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

محبوبه طالبی

مطالب مرتبط

همه مقالات

فیلم‌های آموزشی طراحی الگوریتم

معرفی کامل نظریه گراف (Graph Theory)

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

برنامه نویسی شی گرا چیست؟ شی گرایی چیست؟