ش | ی | د | س | چ | پ | ج |
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 |
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : powerpoint (..ppt) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 14 اسلاید
قسمتی از متن powerpoint (..ppt) :
بنام خدا
File Structure
بازیابی سریع داده ها – مرتب ساز ی (Finding data quickly – Sorting)
روشها ی بازیابی سریع داده ها چگونه میباشند؟
یادآور ی جستجوی دودویی ( Binary Searching )؟
مقایسه با جست وجوی سری( sequential )؟
محدودیت ها یا معایب جست و جوی دودویی کدامند ؟
مرتب سازی کلیدها ( key sorting ) چگونه است؟
روش Indexing چیست؟
مزایای Indexing کدامند؟
File Structure
بازیابی سریع داده ها
روشها ی بازیابی سریع داده ها چگونه میباشند؟
یادآور ی جستجوی دودویی ( Binary Searching )؟
مثال:
یک فایل با رکورد های به طول ثابت را در نظر میگیریم.
فرض کنیم که در جست و جوی رکوردی با مقدار کلیدی مشخصی میباشیم.
حالت اول: اگر فایل مرتب ن شده باشد :
بایستی رکورد ها ی آنرا یک به یک خوانده و کلید آنها را با مقدار مورد نظر مقایسه کنیم .
این کار ممکن است به خواندن کلیه رکورد ها منتهی شود. (چرا؟)
حالت دوم: اگر فایل بر حسب کلید مورد نظر مرتب شده باشد :
روش بهینه همان جست و جوی دودویی میباشد . (چرا؟)
الگوریتم آن در شکل 13-6 کتاب موجود است. ( با اشتباه چاپ ی ! )
File Structure
بازیابی سریع داده ها
یادآور ی الگوریتم جستجوی دودویی :
int BinarySearch
(FixedRecordFile & File, RecType & obj, KeyType & key)
{
int low = 0; int high = file.NumRecs()-1;
While (low
{
int guess = (high + low) / 2;
file.ReadByRRN (obj, guess);
if (obj.Key() == key) return 1;
if (obj.Key()
else high = guess - 1;
}
return 0;
}
low
RRN
high
0
1
3
n
....
....
File Structure
بازیابی سریع داده ها
مقایسه با جست وجوی سری( sequential )؟
مثال:
جستجو ی کلید در یک فایل با تعداد 2000 = n رکورد .
حالت اول: جست و جوی سری :
تعداد ماکزیمم رکورد های خوانده شده برابر با تعداد کل رکورد ها خواهد بود.
ممکن است تا 2000 رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود ، تعداد خواندن رکورد نیز دوبل خواهد شد . (چرا؟)
حالت دوم: جست و جوی دودویی :
تعداد ماکزیمم رکورد های خونده شده برابر با 1+log(n) خواهد بود.
ممکن است تا 1+log(2000) یعنی 11 رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود ، فقط یک خواندن رکورد اضافه می گردد.
برا ی جست و جوی دودویی بای ستی طول رکورد ها ثابت باشد. (چرا؟)