پاورپوینت ساختمان داده ها (pptx) 22 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 22 اسلاید
قسمتی از متن PowerPoint (.pptx) :
Data Structures ساختمان داده ها
Grading
کتاب:
ساختمان داده ها به زبان C++
نوشته: هورویتز- ساهنی – مهتا
ترجمه: امیر علیخان زاده
انتشارات خراسان
نمره:
تمرین: 15%
برنامه نويسي: 15%
میان ترم: 35%
پایان ترم: 35%
Cautions
کپی کردن از روی تمرین دیگران با نمره صفر (هم برای کپی کننده و هم برای کسی که حل تمرین را در اختیار دیگران قرار دهد) مواجه خواهد شد.
گروههای بیش از دو نفر مجاز نیستند.
خطای گروههای سه نفره در 1.5 ضرب خواهد شد.
مثال: اگر درصد پاسخ صحیح 80 درصد باشد، نمره گروه سه نفره فرضی برابر 70 خواهد بود.
Outline
Recursion
Algorithm complexity
Arrays vs. Linked List
Stacks
Queues
Trees
Binary trees, heaps, search trees,
Graphs
Spanning tree, minimum spanning tree, shortest path tree,
Sorting
Quick sort, Insertion sort, heap sort, merge sort, radix sort
Hashing
بازگشت
Recursion: Definition
تابعي که براي حل مساله، از خودش براي حل يک نسخه کوچکتر از همان مساله استفاده مي کند.
نيازمند شرط پايان است: حالتي که ديگر به بازگشت نيازي نداريم
Factorial Recursion
Factorial: n! = n * (n-1)!
شرط خاتمه => 0! = 1
مساله کوچکتر => Solving (n-1)!
Implementation:
long factorial(long inputValue)
{
if (inputValue == 0) return 1;
else return inputValue * factorial(inputValue - 1);
}
Searching
مي خواهيم ببينيم که ورودي در ليست مرتب داده شده است يا نه؟
8 in [1, 2, 8, 10, 15, 32, 63, 64]?
33 in [1, 2, 8, 10, 15, 32, 63, 64]?
------------------------------------------------------
int index = 0;
while (index < listSize)
{
if (list[index] == input) return index;
index++;
}
return –1;
Searching
راه حل بهتر؟
از اين واقعيت که ليست مرتب است استفاده کنيد.
هر بار مساله را نصف مي کنيم
با عنصر وسطي مقايسه مي کنيم.
اگر بزرگتر بود، مقدار مورد نظر ما در سمت راست عنصر وسط قرار دارد.
اگر کوچکتر بود، مقدار مورد نظر ما در سمت چپ عنصر وسط قرار دارد.
اگر مساوي بود، عنصر مورد نظر پيدا شده است.