در فیلم زیر که در خصوص تحلیل و بررسی درس ساختمان داده رشته کامپیوتر پرداختیم، در این فیلم توضیح داده شده که فیلم درس ساختمان داده برای چه افرادی مناسب است و همین طور در خصوص فصول مختلف درس ساختمان داده و اهمیت هر کدام از فصول ساختمان دادهساختمان داده چیستساختمان داده واقعا چیست؟ این صفحه عالی توضیح داده که ساختمان داده چیست و گفته چرا باید ساختمان دادهها را یاد بگیریم؟ و انواع و عملیات روی ساختمان داده را گفته صحبت شده است.
در ادامه این مقاله فیلم های رایگان ساختمان داده که به آنها نیاز دارید نیز در اختیارتان قرار گرفته است.
فیلم های رایگان ساختمان داده که به آنها نیاز دارید
در حال حاضر فیلم آموزش مدار منطقی استاد رضوی پرطرفدارترین و پرفروشترین فیلم آموزشی مدار منطقی کشور است و هر سال اکثر دانشجویان کامپیوتر کشور این فیلم را تهیه میکنند.
فیلم ساختمان داده جلسه 1
فیلم ساختمان داده جلسه 1
فیلم ساختمان داده جلسه 2
فیلم ساختمان داده جلسه 3
فیلم ساختمان داده جلسه 4
فیلم ساختمان داده جلسه 5
فیلم ساختمان داده جلسه 6
فیلم ساختمان داده جلسه 7
فیلم ساختمان داده جلسه 8
حل تست ساختمان و الگوریتم جلسه 1
حل تست ساختمان و الگوریتم جلسه 2
حل تست ساختمان و الگوریتم جلسه 3
حل تست ساختمان و الگوریتم جلسه 4
انواع پیمایشهای درخت
نحوه ساخت درخت BST
آموزش درخت B-Tree
بررسی مرتبه ساخت هیپ
آموزش مرتب سازی سریع
آموزش شبکه شار
حل سوالات ساختمان ارشد کامپیوتر 99
حل ساختمان ارشد 95 بخش 1
حل ساختمان ارشد 95 بخش 2
درس ساختمان داده بنیادی ترین درس رشته کامپیوتر و حتی یکی از بنیادی ترین درسهای بسیاری از رشتههای علوم پایه و مهندسی است. هدف درس ساختمان داده بررسی و پژوهش در مورد روشهای گوناگون ذخیره، نگهداری و بازیابی اطلاعات در سیستمهای کامپیوتری است، به گونهای که این اطلاعات بتواند بطور کارامد مورد استفاده قرار گیرد.
خرید فیلم های کامل ساختمان داده
برای مشاهده سرفصل هر یک از فیلم های درس و حل سوال و تست ساختمان داده و همین طور مشاهده فیلم نظر دانشجویان در خصوص فیلمهای ساختمان داده به انتهای همین صفحه مراجعه کنید.
ویدیو درس ساختمان داده
فشفشههای کافهتدریس تا ۲۳ آبان
30%ویدیو نکته و تست ساختمان داده و طراحی الگوریتم
فشفشههای کافهتدریس تا ۲۳ آبان
30%برای تمامی دانشجویانی که علاقهمند به کارهای پژوهشی یا دادن الگوریتمهای بهینه برای مسائل و چالشهای موجود و یا برنامه نویسی هستند، داشتن دانش ساختمان دادهها و الگوریتمها باعث داشتن یک نگاه ویژه و متفاوت به حل مسائل است، و داشتن این نگاه دانش پژوهان را در آینده کاری و تحصیلی شان نسبت به دیگران متفاوت خواهد کرد. داشتن دانش کافی در مورد درس ساختمان دادهها باعث میشود که دانش پژوهان بتوانند بررسی کنند که آیا راه حلهایی که ارائه میدهند از جوانب گونانونی مانند مرتبه زمانی، میزان حافظه مصرفی، قابلیت توسعه، میزان مصرف توان و ...بهینه هستند یا خیر
ساختمان داده چیست
یک برنامه تشکیل شده از یکسری داده های ورودی، که برنامه ما یک الگوریتمی را روی داده های ورودی اجرا میکند و سپس داده های خروجی برای ما تولید میکند. بعنوان مثال ما برنامه ای داریم که لیست دانشجویان یک کلاس را به آن میدهیم و برنامه ما طبق الگوریتمی که برایش مشخص کرده ایم افرادی که معدل شان بالای 18 است را به ترتیب برای ما مشخص میکند. الگوریتم روی داده ها کار میکند و آنها را پردازش میکند (در واقع الگوریتم ما بر روی داده ها اجرا میشود)، برای اینکه بتوانیم این امکان را برای الگوریتم فراهم کنیم تا راحت تر بتواند دادهها را پردازش بکند باید بتوانیم دادهها را به شکل مناسب ذخیره سازی یا سازماندهی کنیم، درسی که هنر ذخیره سازی مناسب داده ها را به ما یاد میدهد ساختمان داده ها است، در واقع ما در ساختمان داده سعی میکنیم که ساختار دادههای گوناگون با ویژگیهای مختلف را تعریف کنیم.
آنچه که مهندس آی تی را از مهندس نرم افزار یا سخت افزار متمایز میکند، مهارتهای ویژه مهندسین رشته فناوری اطلاعات است. از جمله این مهارتها می توان به توانایی مهندسین آی تی جهت بروز رسانی سیستم های انتقال داده و اطلاعات و تکنولوژی ها و فناوری های یک سازمان اشاره کرد.
هدف اصلی درس ساختمان داده و طراحی الگوریتم ارائه مبانی نظری مورد نیاز برای کسب مهارت لازم در حل مسئله (Problem Solving) به کمک کامپیوتر است، یک مهندس کامپیوتر و آی تی و یا فردی که برنامه نویسی میکند در طول تحصیل خود باید توانایی حل مسائل مختلف به کمک زبانهای برنامه نویسی را فرا بگیرد و در واقع باید بتواند برنامههای مناسبی برای حل مسائل مختلف بنویسد.
هر برنامه از دو بخش تشکیل میشود که عبارت اند از:
- ساختمان داده یا ساختمان داده های در نظر گرفته شده برای الگوریتمهای برنامه مان
- الگوریتم هایی که روی داده ها اجرا میشوند
ساختمان داده ها برای دریافت دادهها توسط کامپیوتر جهت پیاده سازی و اجرای الگوریتمها مورد استفاده قرار میگیرند، اما الگوریتمها دستورالعملهایی هستند که بر روی دادهها اعمال میشوند.
برنامهای خوب است که هم ساختمان داده مناسبی داشته باید و هم از الگوریتمهای بهینه تری استفاده کند. بعنوان مثال فرض کنید میخواهید برنامهای بنویسید که 50 عدد صحیح از ورودی بگیرد و آنها را مرتب کند و در خروجی نمایش دهد، در این مثال بهترین ساختمان دادهای که میتوانیم استفاده کنیم آرایه است (چون تعداد اعداد ورودی ثابت و مشخص است)، اما برای مرتب کردن این اعداد میتوانیم از الگوریتمهای مختلفی نظیر مرتب سازی حبابی (Bubble Sort)، مرتب سازی درجی (Insertion sort)، مرتب سازی سریع (Quick Sort)، مرتب سازی انتخابی (Selection Sort) و یا دیگر الگوریتمهای مرتب سازی استفاده کرد.
همان طور که گفتیم الگوریتمی که برای یک برنامه نوشته ایم روی داده ها کار میکند و آنها را پردازش میکنند، برای اینکه بتوانیم این امکان را برای الگوریتم فراهم کنیم تا راحت تر بتواند دادهها را پردازش بکند باید بتوانیم دادهها را به شکلی مناسب و مختص آن الگوریتم ذخیره سازی یا سازماندهی کنیم، برخی از ساختمان های داده برای پردازش بهتر و سریعتر داده مناسب است، برخی دیگر برای ذخیرسازی بهتر داده مناسب هستند، برخی از ساختمان داده ها، داده ها را بصورت فشرده تری ذخیره میکند. درس ساختمان داده به ما میآموزد که برای هر الگوریتم و برنامه ای چه ساختمان داده ای مناسب تر است. در مقاله الگوریتم چیستالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد، سعی شده که مفاهیم الگوریتم به زبانی ساده و روان توضیح داده شود و شما میتوانید با مشاهده مثالهای فراوانی که در این مقاله آمده است؛ به تفاوت میان ساختمان داده ها و الگوریتم ها پی ببرید.
ساختمان داده (Data Structure) چگونگی آرایش دادهها در حافظهی کامپیوتر را مشخص میکند. هر ساختمان داده بسته به طراحی و هدفی که دنبال میکند، الگوریتمهای ویژهای به منظور بازیابی، ذخیره سازی و حذف دادهها دارد. طراحی هر ساختمان داده طوری انجام میشود که بتواند نیاز خاصی را برطرف کند، هر ساختمان داده مزایا و معایبی دارد و برنامه نویس با توجه به نیازهای برنامهای که طراحی میکند، میبایست ساختمان دادههای مناسبی را انتخاب کند و با توجه به این انتخاب، کارایی نرم افزار نهایی را تضمین نماید. بنابراین برنامه نویسان باید بر انواع ساختمانهای داده تسلط کافی داشته باشند
درس ساختمان داده
درس ساختمان داده یکی از دروس مهم و پایهای رشته مهندسی کامپیوتر است، بطوریکه پیشنیاز دروس مختلفی از رشته کامپیوتر به حساب می آید و به طور معمول در ترم 3 مقطع کارشناسی گذرانده میشود. این درس با توجه به اهمیتی که دارد بعنوان یکی از منابع کنکور ارشد مهندسی کامپیوتر محسوب شده و ضریب بالایی دارد.
ممکن است این درس به نسبت سایر دروس سخت تر به نظر برسد و نیاز به زمان بیشتری برای درک و فهم مطالب داشته باشد اما با یک تسلط نسبی میتوانید در آزمون کارشناسی ارشد و دکتری درصد خوبی را کسب کنید. با مطالعه کارنامه های کنکور ارشد کامپیوتر و IT ، متوجه خواهید شد که این درس در آزمون کارشناسی ارشد تا چه میزان تاثیرگذار بوده و میتواند شانس قبولی شما در بهترین دانشگاههای ایران را بالا ببرد.
علاوه بر همه این موارد، هر مهندس کامپیوتر در روز مصاحبه استخدامیِ بسیاری از غولهای بزرگ فناوری مانند گوگل، آمازون، مایکروسافت و خیلی از کمپانیهای نامدارد دیگر، حتما با سوالاتی در خصوص درس ساختمان مواجه خواهد شد و این نشان از اهمیت درس ساختمان داده در آینده شغلی دانشجویان کامپیوتر دارد.
پیشنیاز درس ساختمان داده
هدف از آموزش درس ساختمان داده این است که دانشجویان با روشهای گوناگون ذخیره، نگهداری و بازیابی اطلاعات در کامپیوتر آشنا شوند و بتوانند از اطلاعات ذخیره شده استفاده کارآمدتری داشته باشند. با مطالعه درس ساختمان داده متوجه خواهید شد که آیا راه حل مسئله شما از لحاظ مرتبه زمانی، میزان مصرف حافظه، میزان مصرف توان و خیلی از جوانب دیگر بهینه عمل خواهد کرد یا خیر؟ شاید مطالعه همزمان دروسی همچون معماری کامپیوتر و ریاضیات بتواند در درک و فهم آسانتر مطالب درس ساختمان داده به شما کمک کند. آشنایی با قطعات کامپیوتر و انواع حافظهها در درس معماری کامپیوتر آموزش جامع معماری کامپیوتر در مهندسی کامپیوتر، معماری کامپیوتر مجموعهای از قوانین و روشهایی است که به چگونگی طراحی، کارکرد، سازماندهی و پیاده سازی (ساخت) سیستمهای کامپیوتری میپردازد، در این صفحه به بررسی و آموزش کامل معماری کامپیوتر پرداخته شده است موجب میشود دید بهتری نسبت به کارکرد انواع ساختمان داده داشته باشید و درک مطالب تئوری مطرح شده برایتان قابل فهمتر به نظر آید. بطور کلی تسلط بر دروس ریاضی برای یک مهندس کامپیوتر جزو ضروریات محسوب شده و ردپای آن را در تمامی دروس کامپیوتر به ویژه درس ساختمان داده نیز میتوان پیدا کرد. (لازم به ذکر است که دروس معماری کامپیوتر و ریاضیات به عنوان پیشنیاز این درس نیستند و علاقه مندان میتوانند برای تسریع پیشرفت خود، دروس نام برده شده را مطالعه کنند).
درس ساختمان داده چه پیشنیازهایی در دانشگاه دارد؟
براساس چارت زیر، گذراندن درس ریاضیات گسسته جزو شروط اخذ درس ساختمان داده به حساب میآید. علاوه بر آن درس برنامهسازی پیشرفته بعنوان یک درس هم نیاز تلقی شده و این بدان معناست که میتوان این درس را به صورت همزمان با درس ساختمان داده اخذ کرد.
درس ساختمان داده پیشنیاز چه درسهایی در دانشگاه است؟
همانطور که در بالا گفتیم، درس ساختمان داده بعنوان یکی از پایهای ترین دروس مهندسی کامپیوتر است و پیشنیاز دروسی همچون هوش مصنوعی (سه واحدی)، طراحی کامپایلرها (سه واحدی) و طراحی پایگاه داده ها (سه واحدی) به حساب میآید. تمامی این دروس از اهمیت بالایی برخوردار هستند و بنابراین تسلط کافی بر درس ساختمان داده زمینه ساز موفقیت شما در دروسی همچون هوش مصنوعی است که امروزه یکی از پرطرفدارترین گرایشهای ارشد مهندسی کامپیوتر محسوب میشود و برای آشنایی بیشتر با این گرایش میتوانید به مقاله رشته هوش مصنوعی دانشگاه شریفموشکافی رشته هوش مصنوعی دانشگاه شریف توسط رتبه 1 کنکوردانشگاه صنعتی شریف، یکی از بهترین دانشگاههای مهندسی ایران است که اکثر دانشجویان و اساتید نخبه در این دانشگاه مشغول هستند. در این مقاله سعی شده رشته هوش مصنوعی دانشگاه صنعتی شریف از همه جوانب بررسی شود. مراجعه فرمایید.
فصلهای درس ساختمان داده و ارتباط آنها با طراحی الگوریتم
در درس ساختمان داده مطالب بسیاری از درس طراحی الگوریتم پوشش داده میشود. فصلهای مرتبه اجرایی کدها و نمادهای مجانبی، روابط بازگشتی، درهم سازی، مرتبسازی، جستجو و ... که در درس ساختمان داده و درس طراحی الگوریتم مشترک است، در این درس گفته خواهد شد، بنابراین با خواندن درس ساختمان داده میتوانید پیش زمینه و دید خوبی برای خواندن درس طراحی الگوریتم پیدا کنید و حتی شاید بتوانید به برخی از سوالات درس الگوریتم نیز پاسخ دهید.
سر فصل مطالبی که در درس ساختمان داده ها وجود دارد عبارت است از:
مرتبه زمانی شبه کدها، رشد توابع، الگوریتمهای بازگشتی، انواع درختها و درختهای ویژه، مرتب سازی، درهم سازی، آرایه و صف و پشته، مجموعه های مجزا
برای مشاهده اهمیت هر فصل و اینکه در سالهای اخیر از هر فصل چه تعداد تست در کنکور مطرح شده میتوانید به صفحات بودجه بندی کنکور ارشد کامپیوتر و بودجه بندی کنکور ارشد فناوری اطلاعات رجوع کنید.
- تابع رشد
- رابطههای بازگشتی و روشهای حل آنها
- حدس و استقرا، تکرار با جایگذاری و استفاده از قضیه اصلی (Master theorem)
- اعمال مختلف بر روی لیستها
- پیاده سازی مسئلههای مختلف با لیستها
- درخت عبارت، تبدیل نگارشهای مختلف یک عبارت ریاضی
- داده ساختار ترای
- درخت دودویی جستجو
- صف اولویت و هرم کمینه و بیشینه
- مرتب سازی هرمی
- مرتب سازی سریع
- مرتب سازی با تعداد مقایسههای بهینه
- مرتب سازی خطی : شمارشی، مبنایی و سطلی
- درهم سازی سراسری
- درهم سازی باز
- درهم سازی کامل
- درخت های قرمز و سیاه، درخت بی، درخت AVL، درخت Deap، درخت min-max heap
مراجع درس ساختمان داده
اصلی ترین مرجع درس ساختمان داده که در دانشگاههای معتبر دنیا تدریس میشود کتاب 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) نیز در برخی از دانشگاههای ایران و جهان تدریس میشوند.
برای صرفه جویی در زمان شما دانشجویان عزیز، این کتابها را در زیر این مطلب برایتان قرار دادهایم تا شما به راحتی بتوانید آن ها را دانلود کنید. البته خواندن کتابهای مرجع را به دانشجویان ترمهای پایینتر توصیه میکنیم نه به دانشجویانی که قصد شرکت در کنکور اشد و دکتری کامپیوتر و آی تی را دارند. دانشجویانی که قصد دارند برای کنکور ارشد و یا دکتری کامپیوتر و آی تی این درس مهم را بخوانند میتوانند از منابعی که در قسمت منابع کنکور ارشد کامپیوتر معرفی شده استفاده کنند.
دانلود کتاب های مرجع درس ساختمان داده
نوع داده های اولیه (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] \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; }
لیست پیوندی:
لیست پیوندی: لیست پیوندی ساختمان داده ای است که از یک تعداد نود تشکیل شده که هر نود یک رکورد شامل دیتا و آدرس نود بعدی است که به اصطلاح میگویند نود دارد به نود بعدی اشاره میکند، در لیست پیوندی هر نود میتواند در هر آدرسی از حافظه باشد
در فیلم زیر موارد زیر درس داده شده است:
- تعریف لیست پیوندی یک طرفه
- بررسی مرتبه عملیات درج و حذف در لیست پیوندی
- ساخت یک لیست پیوندی یک طرفه 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 \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
کدهای عملیات مهم روی ساختمان داده هیپ
درج عنصر در هیپ
حذف رشته در 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] \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 | لیست نامرتب پیاده سازی شده با آرایه | درج سریع در انتها لیست | جستجو کند - حذف کند – ایستا بودن ساختمان داده | |
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 بودن هر خانه از آرایه نشان دهنده وجود یا عدم وجود عدد متناظر با آن خانه باشد. به شکل زیر توجه کنید. 0 1 2 3 4 ... 109
در صورت اضافه شدن یا حذف یک عنصر از مجموعه عناصر، عملیات لازم برای بروزرسانی این ساختمان داده از مرتبه O(1) خواهد بود، زیرا تنها کافی است مقدار یک بیت در آرایه تغییر کند. همچنین عملیات مورد نیاز برای اطلاع از وجود یا عدم وجود یک عنصر در مجموعه نیز از مرتبه O(1) است.
- از یک درخت متوازن استفاده کنیم و اعداد درون مجموعه مان را در آن قرار دهیم. در این ساختمان داده عملیات درج و حذف یک عنصر و همین طور عملیات مورد نیاز برای اطلاع از وجود یا عدم وجود یک عنصر از مرتبه O(logn) است
در طراحی اول پیچیدگی زمان عملیاتی که برای روی ساختمان داده انجام میشود ایده آل است، ولی مصرف حافظه آن تا حدی زیاد است که استفاده از آن را در بسیاری از کاربردها عملا غیر ممکن میسازد، اما طراحی دوم هر چند از نظر پیچیدگی زمانی عملیاتی که بر روی ساختمان داده انجام میشود کارایی طراحی اول را ندارد ولی از نظر مصرف حافظه مطلوب و قابل پیاده سازی است.
مراحل حل مسئله در ساختمان داده و طراحی الگوریتم:
مراحل مختلف حل یک مسئله و در واقع نوشتن برنامه بصورت زیر است:
- تبدیل مسئله به یک مدل ریاضی (مدل انتزاعی) قابل حل توسط کامپیوتر
- طراحی الگوریتمی برای حل آن مسئله
- انتخاب داده ساختار(Data Structure) مناسب برای الگوریتمی که ارائه دادهایم، برای ذخیره و دستکاری داده های مسئله
مراحل حل مسئله در ساختمان داده و طراحی الگوریتم
تحلیل الگوریتم طراحی شده با توجه به داده ساختار انتخابی از نظر زمان اجرا و حافظه مصرفی برای اندازههای مختلف ورودیاگر نتایج تحلیل راضی کننده نباشد، لازم است به مرحله 2 برگردیم و مراحل طراحی الگوریتم و انتخاب داده ساختار مورد نیاز را تکرار کنیم. پس از نهایی شدن الگوریتم میتوانید با استفاده از یک زبان برنامه نویسی الگوریتم را پیاده سازی کنیم و برنامه اش را بنویسیم (کد زنی کنیم)
روش های مختلفی که برای طراحی الگوریتم ها وجود دارد:
الگوریتمها را با استفاده از روشهای مختلفی میتوان طراحی کرد که از جمله آنها میتوان به موارد زیر اشاره کرد:
- روشهای مبتنی بر استقرا
o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی میشوند عبارت اند از: مسئله ستاره مشهور، مسئله محاسبه درست اعداد فیبوناچی، مسئله کوچکترین دایره محیلی
- تقسیم و حل (یا تقسیم و غلبه، Divide-and-conquer)
در این روش مسائل را به مسئلههای کوچکتر تبدیل میکنیم، سپس مسئلههای کوچکتر را حل میکنیم و بعد حل اینها را با هم ادغام میکنیم تا حل مسئله اصلی بدست آید
o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی میشوند عبارت اند از: مسئله ضرب چند جملهای ها، مسئله ضرب ماتریسها (استراسن)، مسئله محاسبه تعداد وارونگیها، مسئله تورنومنت
- برنامه نویسی پویا (Dynamic Programing)
در حل برخی از مسائل با روش تقسیم و حل مجبور میشویم برخی از زیر مسائل را بارها حل کنیم، برای اجتناب از این موضوع این مسائل را به جای آنکه مانند تقسیم و غلبه از بالا به پایین حل کنیم از پایین به بالا حل میکنیم
o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی میشوند عبارت اند از: مسئله کوله پشتی، مسئله برش چوب، مسئله ضرب ماتریسها، مسئله درخت دودویی جستجوی کمینه، مسئله یافتن بزرگترین زیردنباله مشترک یا همان Longest common subsequence problem(LCS)
- حریصانه (Greedy)
ر این الگوریتمها یک مجموعه ورودی وجود دارد که هر بار طبق معیار خاصی یک عضو را انتخاب میکنند، در روش حریصانه رسیدن به هدف در هر گام مستقل از گام قبلی و بعدی است. یعنی در هر مرحله برای رسیدن به هدف نهایی، مستقل از این که در مراحل قبلی چه انتخابهایی صورت گرفته و انتخاب فعلی ممکن است چه انتخابهایی در پی داشته باشد، انتخابی که در ظاهر بهترین انتخاب ممکن است صورت میپذیرد. به همین دلیل است که به این روش، روش حریصانه گفته میشود
o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی میشوند عبارت اند از: مسئله خرد کردن سکه، مسئله کد هافمن، مسئله زمان بندی task ها روی پردازنده
گفتیم برنامهای خوب است که هم ساختمان داده مناسبی داشته باید و هم از الگوریتمهای بهینه تری استفاده کند، بنابراین در اینجا به بررسی دو مورد زیر میپردازیم:
- چگونگی تحلیل الگوریتم
- بررسی ساختمان دادهها
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) هستند. هر ساختمان داده توسط عملیاتی که روی داده هایش میتواند انجام شود و قوانین قرارگیری دادههایش در حافظه تعریف میشود.
عملیات روی هر ساختمان داده را میتوان در دو دسته کلی طبقه بندی کرد:
- Query ها یا درخواست ها
- Update ها
Queryها آن دسته از عملیات هستند که تغییری در محتویات ساختمان داده ها ایجاد نمیکنند، مانند جستجوی یک عنصر، شمارش تعداد عناصر موجود در ساختمان داده و ...
Update ها عملیاتی هستند که سبب تغییر در مقدار یا چینش عناصر ساختمان داده میشوند، مانند اضافه کردن یک عنصر جدید، حذف عناصر موجود و ...
کارایی یک ساختمان داده با استفاده از پیچیدگی زمانی عملیاتی که روی آن ساختمان داده انجام میشود مشخص میشود، همچنین میزان حافظه مصرفی یک ساختمان داده نیز ملاکی برای کارایی آن است، البته توجه کنید که کارایی تنها عاملی نیست که در تعیین کیفیت ساختمان داده موثر است و عوامل دیگری نظیر سادگی ساختاری و سادگی در پیاده سازی نیز کیفیت یک ساختمان داده را مشخص میکند
توضیحات کلی درس ساختمان داده:
درس ساختمان داده و طراحی الگوریتم را میتوان مهم ترین و کاربردی ترین درس رشته کامپیوتر و همین طور مهم ترین و تاثیرگذارترین درس در کنکور ارشد کامپیوتر و آی تی و همچنین مهم ترین دروس در کنکور دکتری رشته های نرم افزار، هوش مصنوعی، شبکه و رایانش و فناوری اطلاعات دانست.
اگر قصد ادامه تحصیل در مقطع دکتری رشته کامپیوتر دارید، کسب اطلاعات درباره تعداد سوالات و ضریب دروس در کنکور دکتری کامپیوتر خالی از لطف نیست.
ساختمان داده مجموعه ای از داده ها ، روابط بین آنها و توابع یا عملیاتی است که میتوان روی آنها اعمال نمود.
مطالعات دانشجویان مقطع ارشد و دکتری تا حد زیادی به این دو درس وابسته است، چراکه طراحی الگوریتم و ساختمان داده در تولید مقالات علمی کاربردی فراوان دارند.
درس ساختمان داده رابطه تنگاتنگی با درس طراحی الگوریتم دارد. به شکلی که می توان این دو درس را مکمل یکدیگر دانست. پیش نیاز بسیاری از مطالب طراحی الگوریتم در درس ساختمان داده نهفته است.
تست های ساختمان داده و طراحی الگوریتم در آزمون های ارشد و دکتری
در کنکور ارشد آی تی از درس ساختمان داده و طراحی الگوریتم مجموعا 12 تست ضریب 4 ، که 6 تست آن متعلق به درس ساختمان و 6 تست آن متعلق به درس طراحی الگوریتم است مطرح میشود. در کنکور ارشد کامپیوتر هنوز مشخص نیست که در کنکور ارشد کامپیوتر 1400 چند تست از دو درس ساختمان داده و طراحی الگوریتم مطرح میشود ولی حدس ما این است که 7 تست از درس ساختمان داده و 7 تست از طراحی الگوریتم مطرح شود. ضریب درس های ساختمان داده و طراحی الگوریتم در گرایش های هوش مصنوعی، نرم افزار، بیوانفورماتیک، علوم داده، الگوریتم و محاسبات و قرآن کاوی رایانشی 4 و در گرایش های شبکه های کامپیوتری، معماری کامپیوتر و علوم و فناوری شبکه 3 است. برای کسب اطلاعات بیشتر در خصوص دروس کنکور ارشد و ضرایب آن به صفحه دروس مورد آزمون و ضرایب آن در کنکور ارشد مهندسی کامپیوتر مراجعه کنید.
در کنکور دکتری رشته های نرم افزار، هوش مصنوعی و شبکه و رایانش از این دو درس 20 تست با بالاترین ضریب یعنی ضریب 4 مطرح میشود؛ همچنین در کنکور دکتری فناوری اطلاعات 10 تست ساختمان داده و 5 تست طراحی الگوریتم هر دو با ضریب 4 مطرح میشود. این تعداد تست در کنکورهای دکتری و با بالاترین ضریب، یعنی ضریب 4، نشان دهنده اهمیت فوق العاده این دو درس در کنکورهای دکتری است.
با توجه به موارد ذکر شده، ساختمان داده از سه جهت بسیار مهم است؛ از جهت تعداد تستها و ضریبی که در کنکور ارشد مهندسی کامپیوتر و فناوری اطلاعات و همچنین کنکور دکتری کامپیوتر به خود اختصاص میدهد، به جهت درک مناسب درس طراحی الگوریتم و در آخر وابستگی زیاد دنیای پژوهش به این درس
فیلم های آموزشی ساختمان داده
علی رغم اهمیت بسیار زیاد درس ساختمان های داده در رشته های کامپیوتر و آی تی، متاسفانه در دانشگاههای کشور چندین مشکل در ارائه این درس وجود دارد؛ مشکل اول این که سرفصل های اعلامی وزارت علوم برای کنکور به طور کامل توسط دانشگاه ها تدریس نمی شود. از جمله این سرفصل ها می توان به شار، درجه سختی الگوریتم ها و مسائل پی و ان پی، مجموعه های مجزا، درخت قرمز سیاه و بسیاری موارد دیگراشاره کرد. مشکل دوم این که مباحث مورد تدریس در دانشگاه ها به صورت کامل و بصورت 0 تا 100 نیست که همین امر موجب عدم توانایی دانشجویان در پاسخگویی به تست های کنکور می شود. آموزش کامل و 0 تا 100 همراه با بیان ساده در درس ساختمان داده باعث میشود دانشجویان رشته کامپیوتر بطور کامل مفاهیم این درس را متوجه شوند و بتوانند به تستهای کنکور پاسخ دهند.
مجموعه کنکور کامپیوتر جهت تسهیل در امر آموزش درس ساختمان داده ها، فیلم های مربوط به این درس را به صورت کامل برای شما دانشجویان عزیز گردآوری و تدوین نموده است. این فیلم ها را میتوانید براحتی در زیر مشاهده کنید.
فیلم هایی که برای شروع ساختمان نیاز دارید
فیلم ساختمان داده جلسه 1
فیلم ساختمان داده جلسه 1
فیلم ساختمان داده جلسه 2
فیلم ساختمان داده جلسه 3
فیلم ساختمان داده جلسه 4
فیلم ساختمان داده جلسه 5
فیلم ساختمان داده جلسه 6
فیلم ساختمان داده جلسه 7
فیلم ساختمان داده جلسه 8
حل تست ساختمان و الگوریتم جلسه 1
حل تست ساختمان و الگوریتم جلسه 2
حل تست ساختمان و الگوریتم جلسه 3
حل تست ساختمان و الگوریتم جلسه 4
انواع پیمایشهای درخت
نحوه ساخت درخت BST
آموزش درخت B-Tree
بررسی مرتبه ساخت هیپ
آموزش مرتب سازی سریع
آموزش شبکه شار
حل سوالات ساختمان ارشد کامپیوتر 99
حل ساختمان ارشد 95 بخش 1
حل ساختمان ارشد 95 بخش 2
برای تماشای فیلمهای بیشتر از درس ساختمان داده به لینک رو به رو مراجعه کنید: آموزش ساختمان داده
نظر برخی از رتبه های برتر کنکور ارشد کامپیوتر و آی تی در مورد کیفیت فیلمها
نظر رتبه 1 کنکور
نظر رتبه 2: خیلی کامل بودند
نظر رتبه 6 کنکور ارشد کامپیوتر
نظر رتبه 6 کنکور 1400
فیلم ها خیلی قابل فهم و روان است
رتبه 9 :فیلم ها بی نقص بود
از پایه ضعیف تا شریف
نظر رتبه 2 کنکور ارشد
نطر رتبه 10: کیفیت تدریس استاد رضوی خیلی خوبه
نظر رتبه 16: کیفیت تدریس خیلی عالی بود
جزوه کامل و ویدیوهای خیلی خوب
نحوه انتقال دانش استاد رضوی بینظیر است
ویدیوها خیلی جامع و کامل بودند
واقعا تدریس اساتید عالی بودند
نظر رتبه 8 کنکور 1400
نظر رتبه 2: معماری کامپیوتر و منطقی 100 زدم
نظر رتبه 13 کنکور ارشد کامپیوتر 1401
نظر رتبه 19: تدریس و فن بیان عالی است
نظر رتبه 12 کنکور ارشد کامپیوتر 1401
نظر رتبه 24: خیلی کامل و جامع است
فیلمها بی نظیر بود
نظر رتبه 45: کیفیت فیلم ها خوب بودن
همه دروس عالی تدریس شده بودند
نیار نیست کتاب تهیه کنید
فیلم ها با بیان شیوا و بدون ابهام بود
کیفیت بالا و هزینه مناسب
نظر رتبه 11 کنکور 1400
فیلمها بینیازم کرد
تدریس زیبا و بیان شیوا
فیلم درس و تست کافیست
فیلم های استاد رضوی از همه نظر عالی بودند
کیفیت و نحوه تدریس و قدرت بیان اساتید از همه نظر خوب بود
خیلی راضی بودم درسها خیلی عمیق تدریس میشد
از همه دروس خیلی راضی بودم
نظر پارسا شریعت
ویدیوها از نظر کیفیت عالی بودند
نظر رتبه 43 کنکور
از دروس استاد رضوی خیلی راضی بودم
نظر پیمان هاشمی
نظر رتبه 40 کنکور
تدریس از 0 تا 100
فیلم شما را جلو میاندازد
نظر رتبه 50 کنکور 1400
نظر رتبه 67 کنکور 1400
نظر ریحانه حسین زاده
نظر مرتضی اکبری
نظر رتبه 113 کنکور 1400
تاثیر منابع خوب
نظر سامان حسینی
تفاوت منابع مناسب
نظر رتبه 32 کنکور 1400
کیفیت بالا تدریس
نظر شیوا رضازاد
از روی مراجع نخوانید
فیلم ها خیلی مفهومی بودند
همه درس ها فوق العاده بود
از صفر تا صد و کامل هستند
آشنایی با استاد رضوی و کافه تدریس معجزه بود
فیلم ها جامع بودند
کل منابع من از کافه تدریس یا کنکور کامپیوتر بود
دروس واقعا فوق العاده بودند
درسها کامل و روان است
فیلم ها خیلی دقیق و جامع و کامل بودند
ویدیوها بسیار قابل فهم بودند
مطالبی که پوشش داده شده بود واقعا کامل بود
تدریس بسیار شیوا و روان و بدون ابهام
با پایه ضعیف هم فیلم ها را متوجه می شوید
فیلم ها خیلی به من کمک کرد
همه دروس را از کافه تدریس گرفتم
ویدیوهاشون خیلی به من کمک کرد
معرفی دوره ساختمان داده (درس+حل تست)
درس ساختمان داده بنیادی ترین درس رشته کامپیوتر و حتی یکی از بنیادی ترین درسهای بسیاری رشتههای علوم پایه و مهندسی است. اهمیت این درس از این حیث است که این درس نه تنها در کنکور ارشد کامپیوتر و آی تی و همچنین کنکور دکتری کامپیوتر تعداد تست بالایی را به خودش اختصاص داده بلکه این درس مهم ترین تاثیر را در آینده پژوهشی دانشجویان چه در ارشد و چه در دکتری و چه پس از آن نیز خواهد داشت، شما هیچ مقاله ای را در دنیای کامپیوتر پیدا نمیکنید که الگوریتمی در آن ارائه نشده باشد و با توجه به این کار دانشجویان ارشد و دکتری نیز همین پژوهش و مقاله دادن است برای فردی که میخواهد در این راه قدم بگذارد و در این راه موفق باشد بسیار مهم است که روی درس ساختمان داده و طراحی الگوریتم مسلط باشد.
متاسفانه در اکثر دانشگاههای کشور چندین مشکل در ارائه این درس وجود دارد
- مشکل اول این است که در دانشگاهها سر فصلی که وزارت علوم برای کنکور اعلام کرده بطور کامل تدریس داده نمیشود و یا اگر درس داده میشود بصورت روان و به نحوی که همه دانشجویان به سادگی متوجه شوند درس داده نمیشود، که اتفاقا اکثر سوالات نیز از همین مباحث است.
- مشکل دوم این است همان مباحثی هم که تدریس میشود بصورت 0 تا 100 و با جزییات زیاد و بصورت کنکوری تدریس داده نمیشود و بنابراین دانشجویان توانایی حل تستهای کنکور را پیدا نمیکنند.
از نگاه دانشجویان، قدرت بیان فوق العاده استاد رضوی و پوشش ۱۰۰ درصدی تمامی سرفصلها، نکات و تستها، ویدیوهای درس ساختمان داده را به بهترین ویدیو آموزشی کشور در درس ساختمان تبدیل کرده است. در حال حاضر فیلم آموزش ساختمان داده استاد رضوی پرطرفدارترین و پرفروشترین فیلم اموزشی ساختمان داده کشور است و هر سال بیش از ۶۰۰۰ نفر این فیلم را تهیه میکنند، آموزش ساختمان داده به زبان ساده و صفر تا صد دلیل محبوبیت آموزش ساختمان است.
در فیلمهای ساختمان داده تهیه شده بر خلاف فیلمهای مشابه این فرض در نظر گرفته نشده که دانشجویان باید یکسری از مطالب را از قبل بلد باشند و همه چی از صفر توضیح داده شده است، به همین علت، تمامی دانشجویان با هر پایه و سطحی که دارند میتوانند از این فیلم بیشترین بهره را ببرند، حتی دانشجویانی که رشته لیسانس شان کامپیوتر نبوده است براحتی میتوانند از این فیلم استفاده کنند و درس ساختمان داده را بصورت عمیق و مفهومی فرا گیرند.
دانشجویان عزیز توجه کنند که برای تهیه فیلم های ساختمان داده نیاز به هیچ پیش نیازی ندارند و هر پیش نیازی که نیاز باشد در فیلم های ساختمان داده گفته شده است.
درس ساختمان داده و طراحی الگوریتم درس حجیمی است و برای به تسلط رسیدن در این درس نیاز است ابتدا این درس را بصورت مفهومی و عمیق مطالعه کنید و سپس تعداد تست زیادی را حل کنید. در نکته و تست ساختمان داده و طراحی الگوریتم حدود 430 تست مفهومی کنکور ارشد کامپیوتر و آی تی و علوم کامپیوتر و همین طور کنکور دکتری بطور کامل بررسی شده است. تمامی نکات مطرح شده در کنکور ارشد و دکتری، به طور کامل و با چندین مرحله تکرار در فیلم های نکته و تست بیان شده اند.
توصیه می کنیم مصاحبه های رتبه های برتر کنکور ارشد کامپیوتر و آی تی را مشاهده کنید تا به اهمیت استفاده از فیلم های آموزشی نکته و تست درس ساختمان های داده و طراحی الگوریتم پی ببرید.
رامین رضوی
RAMIN RAZAVI
ایشان تا قبل از سال 94 بصورت حضوری در شهر تهران و بصورت پروازی در شهرهای مشهد، شیراز، اصفهان، گرگان و ... برای کنکور مقطع ارشد و دکتری تدریس میکردهاند، سپس در سال 94 با توجه به درخواستهای مکررِ شهرهای دیگر برای برگزاری کلاسهای آمادگی کنکور ارشد و دکتری تصمیم گرفت در جهت رفع کمبود امکانات آموزشی در شهرهای کوچک، برای اولین بار در کشور اقدام به برگزاری دورههای آموزشی آنلاین کند که ماحصل آن برقراری عدالت آموزشی طی این سالها و شرکت بیش از 24000 دانشپژوه در کلاسهای آنلاین ایشان و برگزاری 267 دوره آنلاین توسط ایشان بوده است.
در حال حاضر بیش از 90 درصد از رتبههای برتر کنکور ارشد کامپیوتر و آیتی هر سال از دانشجویان استاد رضوی هستند که این درصد موفقیت نه تنها در رشته کامپیوتر بلکه در هیچ رشته دیگری وجود نداشته است.
سرفصلهای دوره ساختمان داده و الگوریتم
برای درس ساختمان داده دو فیلم زیر وجود دارد:
- فیلم درس ساختمان داده
- فیلم حل تست سوالات ساختمان داده و الگوریتم
ویدیو درس ساختمان داده
فشفشههای کافهتدریس تا ۲۳ آبان
30%ویدیو نکته و تست ساختمان داده و طراحی الگوریتم
فشفشههای کافهتدریس تا ۲۳ آبان
30%در زیر سرفصلهای دوره درس و حل تست ساختمان داده با جزئیات آورده شده است و مشخص شده است که فیلم آموزش ساختمان داده و همین طور حل تست ساختمان داده و الگوریتم چند جلسه است و هر جلسه چند ساعت است و شامل چه بخشها و مباحثی است:
بخش 1
2:30'زمان اجرای یک قطعه کد - گامشماری - خواص سیگما - تصاعد حسابی
بخش 1
1:15'تعداد تکرار جمله اصلی - به دست آوردن مرتبه قطعه کدها
بخش 2
1:30'ادامه مثالها
بخش 1
1:35'رشد توابع - بررسی رشد توابع با حد
بخش 2
1:00'ادامه مثالهای رشد توابع - نکاتی در رابطه با log
بخش 1
1:05'ادامه مثالهای رشد توابع - بررسی تابع log n! - بررسی رشد توابع با استفاده از log
بخش 2
1:15'ادامه مثالهای رشد توابع - بررسی تابع (log n)! - بررسی تابع log* n
بخش 3
00:40'معرفی نمادهای مجانبی
بخش 1
1:30'ادامه مثالهای نمادهای مجانبی - بررسی رشد در توابع سینوسی
بخش 2
00:50'ادامه مثالهای نمادهای مجانبی - خواص نمادها
بخش 1
1:20'شروع فصل بازگشتیها - درخت بازگشت - تعداد فراخوانیهای یک رابطه بازگشتی
بخش 2
1:20'ادامه مثالهای روابط بازگشتی و درخت بازگشت - حل روابط بازگشتی به وسیله جایگذاری
بخش 3
00:20'جایگذاری پایین به بالا - جایگذاری بالا به پایین
بخش 1
1:20'ادامه مثالها - زمان اجرای یک رابطه بازگشتی و مرتبه زمانی یک رابطه بازگشتی - کرانیابی
بخش 2
1:10'ادامه مثالها (رابطه بازگشتی جمع 1 تا n، رابطه بازگشتی سری هارمونیک - رابطه بازگشتی خارج قسمت m به n - رابطه بازگشتی باقیمانده m به n)
بخش 3
00:25'رابطه بازگشتی ترکیب
بخش 1
1:35'برج هانوی - قضیه Master
بخش 2
1:35'ادامه مثالهای قضیه Master - رسم درخت بازگشت - به دست آوردن مرتبه روابط بازگشتی با درخت بازگشت
بخش 1
2:05'ادامه مثالهای درخت بازگشت - قضیه بمب اتم
بخش 1
1:30'شروع فصل درخت - تعریف درخت ریشهدار - تعاریف اولیه (برادر - نوه - جد - درجه یک نود - درجه درخت - برگ - نود داخلی - تعداد سطوح - شماره سطح - ارتفاع درخت - ارتفاع نود - عمق نود) - درخت دودویی
بخش 2
1:30'تعداد درختهای دودویی با n نود - درخت دودویی کامل
بخش 1
1:25'انواع پیمایشها روی درخت (پیمایشهای سطحی، پیمایشهای عمقی) - رسم درخت با داشتن پیمایشها
بخش 2
2:00'رسم درخت با داشتن پیمایشها - درخت عمومی - پیمایشهای درخت عمومی
بخش 1
1:30'شیوههای ذخیره درخت در کامپیوتر (آرایه ، لیست پیوندی)
بخش 2
1:40'پیادهسازی برخی الگوریتمهای روی درخت - رسم درخت با داشتن پیمایش PreOrder ( 2 روش ) - درخت جستجوی دودویی (BST) - الگوریتمهای پایه در BST
بخش 1
1:20'درج در BST - مرتبه ساخت BST ( 2 روش ) - یافتن Min و Max-Successor و Predeccessor
بخش 2
1:15'الگوریتم یافتن Succ و Pred - درخت BST متوازن ( AVL ) - شروع دوران (Rotate)
بخش 1
1:30'ادامه دوران - ساختAVL - تعریف هرم یا Heap
بخش 2
1:35'بررسی مرتبه یافتن Min و Max در Maxheap و در Minheap - درج در Maxheap – Maxheapify (Sift down) - ساخت Heap (2روش)
بخش 1
1:45'به دست آوردن مرتبه ساخت Heap - حذف ماکزیمم از Maxheap - ادغام 2 هیپ (3روش) - تعریف صف اولویت
بخش 2
1:05'بهترین روش ساخت صف اولویت - Deap یا Double Heap - پیدا کردن نظیر یک نود در Deap - مرتبه یافتن Min و Max در Deap - حذف Min از Deap
بخش 3
00:05'ادامه حذف Min از Deap
بخش 2
1:40'درخت B-tree (Balanced tree) - مرتبه جستجو در B-tree - درخت قرمز سیاه و نکات آن
بخش 1
1:30'درخت MinMaxHeap - درج در MinMaxHeap - درخت 4-3-2 و خواص آن - درج در درخت 4-3-2
بخش 1
00:45'شروع فصل مرتبسازی - دستهبندی الگوریتمهای مرتبسازی - مرتبسازی انتخابی (Selection Sort)
بخش 2
1:35'شروع فصل مرتبسازی - دستهبندی الگوریتمهای مرتبسازی - مرتبسازی انتخابی (Selection Sort)
بخش 3
1:45'ادامه مرتبسازی درجی - مرتبسازی سریع (Quick Sort) - partion در مرتبسازی سریع چه میکند ؟ - 2 مدل بررسی Partion - تحلیل زمان اجرای مرتبسازی سریع
بخش 4
1:15'تحلیل حالت متوسط مرتبسازی سریع - مرتبسازی ادغامی (Merg Sort) – تعداد مقایسه ها در مرتب سازی ادغامی - نحوه کار Merg Sort
بخش 1
1:15'رابطه بازگشتی تعداد مقایسهها در مرتب سازی ادغامی - مقایسه کلی روشهای مرتبسازی مبتنی بر مقایسه - درخت تصمیم چیست؟ - کاربرد درخت تصمیم
بخش 2
1:15'شروع روشهای مرتبسازی غیر مقایسهایی - مرتبسازی شمارشی و مرتبه آن - مرتبسازی مبنایی
بخش 3
1:40'چند مثال ازمرتبسازی مبنایی - مرتبسازی سطلی و مرتبه آن - روشهای جستجو (جستجوی خطی و جستجوی دودویی)
بخش 4
1:30'رابطه بازگشتی تعداد مقایسات در جستجوی دودویی - شروع درهمسازی - جدول درهم (Hash Table) - تعریف Hashing - انواع جدول درهم - درهمسازی باز یا آدرسدهی بسته یا زنجیرهسازی - متوسط زمان درج و حذف و جستجو در درهمسازی باز
بخش 5
1:20'متوسط زمان جستجو در روش آدرسدهی بسته - آدرسدهی باز یا درهمسازی بسته - روشهای پیدا کردن جای خالی در جدول درهم - کاوش خطی
بخش 6
1:05'کاوش مربعی - کاوش دوبل - درهمسازی یکنواخت - ضریب بارگذاری (load factor) - بررسی احتمال برخورد دو عنصر در جدول درهم
بخش 7
1:30'آرایه - آرایه 2 بعدی - آرایه 3 بعدی - نحوه قرارگیری آرایهها در حافظه
بخش 8
1:40'لیست پیوندی - مثالها و نکات لیست پیوندی - درج یک نود در لیست پیوندی
بخش 9
1:10'لیست پیوندی دو طرفه - مرتبه درج و حذف در لیست دو طرفه - مسئله جوزف
بخش 10
1:40'ادامه مسئله جوزف - پشته - پیادهسازی پشته با آرایه - ساخت پشته با لیست پیوندی - صف - ساخت صف با آرایه - صف حلقوی - ساخت صف با لیست پیوندی
بخش 1
1:30'چگونگی حل روابط بازگشتی - حل روابط بازگشتی خطی، همگن و ضریب ثابت - فرمت ریشه اعداد مختلط
بخش 2
1:25'حل روابط بازگشتی خطی، ناهمگن و ضریب ثابت
بخش 3
1:30'مثالهایی از حل انواع روابط بازگشتی - نوشتن رابطه بازگشتی برای برخی مسائل
بخش 4
1:30'نوشتن رابطه بازگشتی برای برخی مسائل
بخش 1
00:50'به دست آوردن مرتبه زمانی قطعه کدها
بخش 2
1:05'به دست آوردن مرتبه زمانی قطعه کدها
بخش 3
1:30'به دست آوردن مرتبه زمانی قطعه کدها - گام شماری
بخش 4
1:50'زمان اجرای یک الگوربتم - نمادهای مجانبی - مقایسه رشد توابع
بخش 5
2:15'نمادهای مجانبی - مقایسه رشد توابع
بخش 1
1:40'شروع فصل روابط بازگشتی - به دست آوردن مرتبه زمانی توابع بازگشتی - درخت بازگشت
بخش 2
1:45'به دست آوردن مرتبه زمانی توابع بازگشتی - درخت بازگشت
بخش 3
2:05'به دست آوردن مرتبه زمانی و حل توابع بازگشتی - درخت بازگشت - مساله برج هانوی
بخش 4
1:45'مساله برج هانوی - به دست آوردن مرتبه زمانی و حل توابع بازگشتی
بخش 1
1:40'به دست آوردن مرتبه زمانی و حل توابع بازگشتی - درخت بازگشت
بخش 2
1:25'به دست آوردن مرتبه زمانی و حل توابع بازگشتی
بخش 3
2:00'شروع فصل درخت - انواع پیمایشهای روی درخت - پیادهسازی روالهای بازگشتی روی درخت - رسم درخت با داشتن پیمایشها
بخش 4
1:30'انواع پیمایشهای روی درخت - پیادهسازی روالهای بازگشتی روی درخت - بررسی ارتفاع درخت دودویی
بخش 1
2:15'انواع پیمایشهای روی درخت - پیادهسازی روالهای بازگشتی روی درخت - هرم بیشینه - یافتن مرتبه یک نود
بخش 2
2:00'انواع پیمایشهای روی درخت - کمینه و بیشینه ارتفاع B-tree - AVL - درخت دودویی کامل - دنباله جستجو
بخش 3
2:05'انواع پیمایشهای روی درخت - ادغام 2 هیپ - درخت قرمز سیاه
بخش 4
1:35'هرم - Treap - درج در Treap - دوران
بخش 1
2:05'درخت قرمز سیاه - بررسی ارتفاع درخت دودویی
بخش 2
1:50'پیمایش روی درخت - یافتن Pred و Succ - رسم درخت با داشتن پیمایشها
بخش 3
00:55'AVL - MaxHeap - هزینه ادغام تعدادی لیست مرتب (2روش) - انتخاب داده ساختار مناسب برای انجام یک عملیات
بخش 4
1:05'بررسی پیمایش Postfix - انتخاب داده ساختار مناسب برای انجام یک عملیات
بخش 5
1:50'فرمول بازگشتی تعداد درختهای دودویی با n نود - درج در AVL
بخش 1
1:20'شروع مرتبسازی - مرتبه یافتن k امین مینیمم، k امین ماکزیمم، میانه - بررسی نامساوی مثلثی در یک مجموعه از اعداد - تعداد مقایسات برای یافتن میانه
بخش 2
00:45'ادغام k لیست مرتب - بررسی مرتبه مرتبسازی سریع
بخش 3
1:05'آرایه k مرتب - مرتبسازی سریع
بخش 4
1:55'آرایه k مرتب - الگوریتم مرتبسازی خستهکننده
بخش 5
1:20'سورتهای سه مرحلهایی - قضیهی 0 و 1
بخش 1
1:05'دنباله ی زیگراگی
بخش 2
1:15'تعداد وارونگی های یک آرایه n عنصری - روش تورنومنت - به دست آوردن مرتبه الگوریتم بازگشتی با روش کران یابی و بمب اتم – محاسبه تعداد مقایسات برای یافتن nامین ماکزیمم یا مینیمم
بخش 3
1:05'آرایه صعود نزول ( اره ایی ) - وارونگی نسبت به صعودی بودن
بخش 4
1:50'محاسبه تعداد وارونگی با استفاده از مرتبسازی درجی و مرتبسازی ادغامی - مرتب سازی k عدد مجزا - pancake Sort - Randomized-Quicksort - مرتبسازی مبنایی - ماتریس یانگ
بخش 1
1:20'شروع درهمسازی - درهمسازی باز با وارسی خطی - ترتیب درج عناصر در جدول - محاسبه میانگین تعداد برخوردهای دو عنصر در جدول
بخش 2
1:20'متوسط تعداد مقایسهها در جستجوی موفق و ناموفق - یافتن مینیمم در آرایه مرتب حلقوی
بخش 3
00:55'مرتبه یافتن بزرگترین زیر دنبالهی یک رشته
بخش 4
1:00'شروع آنالیز استهلاکی - پیادهسازی صف با استفاده از 2 پشته - محاسبه هزینه سرشکنی
بخش 1
1:45'محاسبه هزینه سرشکنی در مسائل - بررسی شمارنده k بیتی - بررسی الگوریتم استراسن
بخش 2
00:40'مرتبه زمانی محاسبه k امین عدد فیبوناچی - محاسبه هزینه جمع دو عدد، بهترین و بدترین حالت
بخش 3
00:40'محاسبه هزینه سرشکنی درج و حذف در جدول درهمساز پویا
بخش 1
1:15'ادامه محاسبه هزینه استهلاکی در مسائل - شروع گراف - DAG - جستجوی عمق اول (DFS) - ترتیب توپولوژیکی در گراف
بخش 2
1:10'بررسی انواع یالها در DFS و BFS - الگوریتم تشخیص بدون دور بودن گراف جهتدار - درخت پوشای کمینه
بخش 3
1:15'الگوریتمهای یافتن درخت پوشای کمینه - زمان ملاقات گرهها در DFS - الگوریتم یافتن همهی طولانیترین مسیرها از یک راس داده شده - بررسی انواع یالها در DFS و BFS
بخش 4
1:10'مرتبه یافتن قطر گراف - بررسی گذر و مدار اویلری - الگوریتم تشخیص همبندی در گراف
بخش 5
1:15'مقایسه الگوریتم های Prim و Kruskal - درخت فراگیر گلوگاه - دومین زیر درخت فراگیر کمینه
بخش 6
1:30'یافتن کوتاهترین مسیرها در گراف - تعریف برش و یالهای برش - قدرت یک درخت پوشا
بخش 7
1:00'ترتیب انتخاب یالها در Prim و Kruskal - نکاتی در مورد درخت پوشا کمینه
بخش 1
1:05'مرتبه محاسبه درخت پوشای بیشینه - بررسی سیکل و مسیر همیلتونی - به دست آوردن تعداد سیکلهای ساده در گراف مسطح - الگوریتم فلوید
بخش 2
1:15'درخت کوتاهترین مسیر - مرتبه بررسی دو بخشی بودن گراف - مرتبه یافتن تعداد اجزای همبند در گراف
بخش 3
00:30'الگوریتم بلمن فورد - مولفه متصل قوی درگراف
بخش 1
1:10'قضیه Master - محاسبه هزینه استهلاکی برای یک داده ساختار - پیاده سازی صف با دو پشته - مرتب سازی مبنایی
بخش 2
1:40'محاسبه هزینه استهلاکی برای یک داده ساختار - بررسی partition در مرتب سازی سریع - درهمسازی بسته - درج در لیست پیوندی - درخت هافمن
بخش 3
1:45'استفاده از الگوریتم Cutrod - تعداد فراخوانیها در یک رویه بازگشتی - تعداد عناصر و شرط پر بودن صف - مقایسه رشد توابع - مرتبسازی لیست پیوندی دو سویه - به دست آورن مرتبه برخی توابع بازگشتی خاص - کوله پشتی 0 و 1
بخش 4
1:30'محاسبه بزرگترین زیر دنبالهی صعودی - درخت Trie - هرم کمینه - محاسبه مرتبه تابع بازگشتی با تغییر متغیر
بخش 1
1:50'مقایسه رشد یکسری توابع خاص ( log n! , (logn)! , n ^ lglg n , n^n , lgn ^ lgn , lg* n , … ) - نمادهای مجانبی
بخش 1
1:25'تبدیل درخت عمومی به درخت دودویی معادل و پیمایش روی آن - بررسی هزینه جستوجوی ناموفق در درهمسازی باز و درهمسازی بسته - وزن کوتاهترین از راس i به راس j در صورت عبور از k یال
بخش 2
1:35'الگوریتم حریصانه اجرای پردازهها روی یک پردازنده - رابطه بازگشتی ساخت درخت دودویی جستجو - مسئله ژوزف - روش تقسیم و غلبه در محاسبه حاصلضرب دو عدد n بیتی
بخش 3
1:25'پیدا کردن زیر دنباله متوالی با حاصل ضرب بیشینه - بررسی ارتفاع درخت هافمن - الگوریتم خرد کردن پول با روش حریصانه - الگوریتمهای یافتن کوتاهترین مسیر بین راس i و j
بخش 1
1:20'مقایسه رشد توابع - بررسی نمادهای مجانبی - مرتبه زمانی قطعه کدها
بخش 2
00:50'مقایسه رشد توابع - مرتبه زمانی قطعه کدها - محاسبه طولcall stack برنامه - بررسی دقیق نمادهای مجانبی در یک مساله
بخش 3
1:40'مقایسه رشد توابع - مرتبه زمانی قطعه کدها - تعداد تکرار جمله اصلی
بخش 1
1:10'محاسبه مرتبه برخی روابط بازگشتی خاص - رابطه بازگشتی عدد nام کاتالان
بخش 2
1:20'محاسبه مرتبه برخی روابط بازگشتی خاص - روش نردبانی در محاسبه ب.م.م
بخش 3
1:15'نکاتی در رابطه با قضیه Master - محاسبه مرتبه برخی روابط بازگشتی خاص
بخش 1
00:40'انواع درخت (درخت متوازن، درخت کاملا متوازن، درخت کامل kتایی، درخت تکمیل، درخت پر)
بخش 2
00:35'تعداد درختهای دودویی متوازن با ارتفاع h
بخش 3
1:35'درخت 2 - کامل - تعداد حالات پرانتز گذاری عبارات ریاضی - بررسی هزینه حذف و درج و Find Closest در: لیست پیوندی مرتب یکطرفه، لیست پیوندی مرتب دو طرفه و لیست مرتب (آرایه)
بخش 4
1:50'کمینه ارتفاع درخت قرمز - سیاه - الگوریتمهای یافتن Pred و Succ - به دست آوردن مرتبه در AVL - درخت مرتبه آماری - درج و حذف در درخت قرمز - سیاه
بخش 1
1:20'ساخت Treap - حذف یک عنصر از هرم کمینه
بخش 2
1:20'رابطه بازگشتی حداقل تعداد گره برای ساخت AVL با ارتفاع h - رابطه بازگشتی میانگین ارتفاع درخت BST با n عنصر - تبدیل پیمایشهای درخت به یکدیگر
بخش 3
2:20'محاسبه حداکثر تعداد نابهجاییها در هرم کمینه متوازن - توضیح کامل B-Tree ( توضیح 2 نحوه ی پیادهسازی، چگونگی حذف یک عنصر، چگونگی درج یک عنصر).
بخش 1
1:25'هزینه جستجوی یک عدد در B-Tree - بررسی پیمایش PreOrder
بخش 2
1:40'بررسی داده ساختار Deap - ادغام 2 آرایه مرتب - رابطه بازگشتی تعداد درختهای جستجوی دودویی با n عنصر (کاتالان) - MinMaxHeap - هزینه بررسی اینکه آیا BST داده شده ،AVL است.
بخش 3
00:35'ادغام 3 آرایه مرتب و ساخت BST متوازن - بررسی پیمایشهای درخت - رابطه بازگشتی حداقل تعداد گره برای ساخت AVL با ارتفاع h.
بخش 1
2:25'شبکه شار
پی دی اف درس ساختمان داده
هر یک از فیلمهای درس یا حل تست ساختمان داده را تهیه کنید در داشبورد پی دی اف مربوط به آن دوره نیز قرار میگیرد و دانشجویان براحتی میتوانند جزوات را پرینت و هنگام تماشای فیلمهای درس و حل تست ساختمان داده از جزوات خط ببرند و مطالب مهم را هایلایت کنند و در صورت نیاز برای خودتان در کنار جزوات یاداشت برداری کنید.
منابع و مراجع
- https://www.geeksforgeeks.org/data-structures/
- https://searchsqlserver.techtarget.com/definition/data-structure
- https://www.programiz.com/dsa
- 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 کنکور ارشد و دکتری کامپیوتر و آی تی شوید، بنابراین افرادی در کنکور ارشد و دکتری کامپیوتر موفق میشوند که بسیار عمیق و مفهومی مطالعه کرده باشند، به همین علت در فیلم های تولید شده مطالب بسیار عمیق و مفهومی گفته شده است و بنابراین همه دانشجویان میتوانند از این فیلم ها استفاده کنند، چه دانشجویانی که کنکور دارند و چه دانشجویانی که در ترم های پایین تر هستند و حتی هنوز این دروس را پاس نکرده اند