در این پست به شما انواع روش های جستجو آموزش داده می شود. سپس طریقه نوشتن برنامه برای این روش ها کاملا شرح داده خواهد شود و در انتها با دادن نمونه تست ها مربوط به این بخش مطلب به پایان خواهد رسید . برای مطالعه این متن به ادامه مطلب مراجعه کنید .
-------------------------------------------------------
روشهای جستجو:
تعریف لیست:
لیست از تعدادی داده تشکیل شده است که با یکدیگر در خاصیتی مشترک هستندو تعریف لیست بسیار شبیه تعریف مجموعه در ریاضی است با این تفاوت که:
- در مجموعه(Set) عضو تکراری وجود ندارد اما در لیست ممکن است داده تکراری وجود داشته باشد
- در مجموعه ترتیب اعضا اهمیت ندارد اما در لیست ترتیب داده ها اهمیت دارد
سئوال) آیا نمرات درس پاسکال می تواند مجموعه باشد؟ اگر نمره تکراری در آنها نباشد می تواند مجموعه باشد
سئوال) آیا لیست روبرو می تواند مجموعه باشد؟ {2 , 7 , 8 , 3 , 2 , 4} خیر زیرا عضوتکراری دارد
نکته) یک مجموعه می تواند حتما لیست باشد اما یک لیست همیشه یک مجموعه نمی تواند باشد.
نکته)داده های موجود در یک لیست می تواند از چند نوع داده متفاوت باشد مثلا { ali , 14 , 15.5 , 18}
دقت شود که داده های یک لیست در خاصیتی باید مشترک باشند
نکته) رکورد و آرایه می توانند یک لیست باشند.
ALI 'A' 8.5 5 8 9 13 6 14 19 25 5
جستجودر لیست:
در مواردی می خواهیم یک داده خاصی را در یک لیست پیدا کنیم به این داده کلید می گویند. انواع روش های جستجو در لیست ها وجود دارد که 2 مورد آن بحث خواهد شد.
روش جستجوی خطی(ترتیبی)
در این روش کلید( داده ایی که قرار است جستجو شود) با اولین دادة لیست مقایسه می شود اگر پیدا شد کار به پایان می رسد در غیر این صورت با دومین دادة لیست مقایسه می شود و این کار تا پایان لیست ادامه می یابد.
مثال) اگر کلید 12 باشد در لیست زیر چند عمل مقایسه انجام می شود تا کلید پیدا شود؟ ( به روش خطی)
2 12 17 19 12 7 11 14 13 10
نکته) اگر در لیست چند مورد از کلید باشد به روش خطی جستجو کنیم اولین کلید را پیدا می کند و اندیس (فیلد) لیست را برمی گرداند و کار جستجو تمام می شود. در مثال بالا دو عدد 12 وجود دارد اما اولین 12 که در خانه ششم است پیدا می شود و کار تمام می شود.
نکته) در این روش جستجوی خطی لازم نیست که لیست ما مرتب شده باشد یعنی داده ها در لیست صعودی یا نزولی باشند.
Var A: Array[1..100] of integer; Key , F:integer; B:Boolean; Begin For F:=1 to 100 do Readln( A[F]); Readln(Key); B:=False; For F:=1 to 100 do IF A[F] = Key then Begin B:=True; Break; End; If B=False then Writeln(' Not Found ') Else Wrietln(' Find ' , F); End.
نکته) در بهترین حالت جستجوی خطی عمل مقایسه یکبار انجام می شود.
در بدترین حالت جستجوی خطی به تعداد خانه های لیست عمل مقایسه انجام
می شود.
بنابراین اگر لیست N تا عنصر داشته باشد N عمل مقایسه انجام می شود.
در حالت متوسط N/2 عمل مقایسه انجام می شود.
سئوال) اگر لیستی دارای 20 عنصر باشد در روش جستجوی خطی در بدترین و
متوسط چند عمل مقایسه انجام می شود؟
نکته) در روش جستجوی خطی لیست می تواند نامرتب باشد. ولی تعداد مقایسه ها
زیاد است و جستجو به کندی صورت می گیرد.
روش جستجوی دودویی ( باینری):
در این روش باید لیست از قبل مرتب باشد. پس این روش مخصوص لیست هایی
است که از قبل مرتب( صعودی یا نزولی) شده اند.
فرض کنید که یک آرایه مرتب صعودی (از کوچک به بزرگ) داریم و می خواهیم کلیدی را در آن به روش باینری جستجو کنیم:
آرایه را از وسط نصف می کنیم و کلید را با عنصر وسط آرایه مقایسه می کنیم که سه حالت ممکن است رخ دهد:
الف) کلید از عنصر وسط بزرگتر باشد( Key > A[C]) : در این حالت با توجه به اینکه لیست مرتب (صعودی) است حتما کلید در نیمه سمت راست است و ما باید نیمه سمت راست را جستجو کنیم و نیمه سمت چپ را جستجو نخواهیم کرد.
نیمه سمت راست | وسط | نیمه سمت چپ |
ب) کلید از عنصر وسط لیست کوچکتر است: در این حالت با توجه به اینکه لیست به صورت صعودی مرتب است حتما کلید در نیمه سمت چپ است و باید نیمه سمت چپ را باید جستجو کرد و نیمه سمت را جستجو نخواهیم کرد.
ج) در بهترین حالت کلید مساوی عنصر وسط لیست باشد. در این حالت کلید پیدا شده است و عمل جستجو متوقف می شود.
اگر هر کدام از حالت های الف یا ب رخ دهد عمل جستجو را در نیمه سمت چپ یا راست ادامه می دهیم. به عبارت دیگر نیمه سمت چپ یا نیمه سمت راست را دوباره از وسط نصف می کنیم و دوباره عمل بالا را روی آن انجام می دهیم.
Var A:array[1..20] of integer; J, Key , C , E , S : integer; F:Boolean; Begin For J:= 1 to 20 do Readln( A[ J ] ) ; Sort(A); { یک زیربرنامه جهت مرتب سازی } S:=1 ; E : =20; Readln(Key); F:=False; While (S< E) and ( Not F) Do Begin C:= ( S+E) Div 2; IF A[ C] < Key then S:=C+1 Ese IF A[C] > Key then E:=C-1 Else IF A[C]=Key then F:=True; End; IF F=False then Writeln(' Not Found') Else Writeln(' Find in index' , C); End.
نکته) در بهترین حالت جستجوی دودویی یک عمل مقایسه انجام
می شود و در بدترین حالت جستجوی دودویی یک لیستی که دارای
N عنصر باشد تعداد عمل جستجو [ Log2(N)] +1 است.
مثال) لیستی دارای 18 عنصر است در بدترین حالت و بهترین حالت
جستجوی یک کلید به روش دودویی و خطی چند عمل مقایسه انجام
می شود؟
نکته) جستجوی اطلاعات غیر عددی( رشته یا کاراکتر) دقیقا مانند اطلاعات
عددی است.
نکته) معمولا در حالتهایی که تعداد عناصر لیست زیاد باشد جستجوی
دودویی بسیار بهتر عمل می کند.
سئوال) در جه حالتی جستجوی خطی از جستجوی دودویی سریعتر است؟
سئوال) در روش جستجوی باینری اگر کلید در لیست نباشد چگونه متوجه می شویم که کلید در لیست نیست؟
سئوال) اگر عضو تکراری در لیست باشد و به روش باینری جستجو کنیم کدام عضو پیدا خواهد شد؟
سئوال)آرایه روبرو را برای کلید 34 به دو روش خطی و باینری جستجو کنید و تعداد مقایسه ها را در هر دو روش بدست آورید؟
20 | 9 | 13 | 34 | 38 | 2 | 12 | 21 | 34 | 19 | 17 | 32 | 15 | 8 |
روشهای مرتب سازی لیست:
مرتب سازی: منظور از مرتب سازی داده ها تغییر دادن موقعیت آنها در یک لیست است تا داده ها در لیست به طور منظم صعودی یا نزولی قرار گیرند.
صعودی ç از کمتر به بیشتر 2 , 7 , 8 ,9 15 , 18
نزولی ç از بیشتر به کمتر 18 , 15 , 9 , 8 , 7 , 2
درهمه مثالهای زیر فرض شده است که می خواهیم لیست را صعودی کنیم.
روش مرتب سازی حبابی: Bubble Sort
مرحله یا گذر 1) در این روش اولین عدد لیست با دومین عدد لیست مقایسه می شود و اگر ترتیب آنها درست نبود جای آنها را عوض می کنیم.( یعنی اینکه عدد اولی از دومی بزرگتر باشد)
سپس عدد دومی را با عدد سومی مقایسه می کنیم و اگر ترتیب آنها درست نبود جای آنها را عوض می کنیم. و این کار را تا انتهای لیست( فرض بر این است که N تا سلول دارد) ادامه می دهیم. عدد بزرگتر به خانه N ام می رود( مانندیک حباب)
مرحله 2) دوباره از خانه اول شروع می کنیم و خانه اول را با خانه دوم مقایسه می کنیم و اگر ترتیب آنها درست نبود جای آنها را عوض می کنیم و سپس عدد دوم وعدد سوم مقایسه می شوند و ......... و این کارتا خانه N-1 ادامه پیدا می کند
مرحله سوم) مرحله سوم نیز مانند مرحله دوم است با این تفاوت که تا خانه N-2 انجام می شود.
اگر لیست داری N تا سلول باشد N-1 مرحله خواهیم داشت. (مثال صفحه 119 کتاب)
9 13 17 10 18 12
مثال) آرایه روبرو را به روش حبابی مرتب صعودی کنید؟
6 5 4 3 2 1 9 13 17 10 18 12 9 13 17 10 18 12 9 13 17 18 10 12 9 13 18 17 10 12 9 18 13 17 10 12 18 9 13 17 10 12 مرحله 1 : 5 عمل مقایسه و چهار جابجایی رخ داده است. 6 5 4 3 2 1 18 9 13 17 10 12 18 9 13 17 12 10 18 9 13 17 12 10 18 9 17 13 12 10 18 17 9 13 12 10 مرحله 2 : چهار عمل مقایسه و سه جابجایی رخ داده است. 6 5 4 3 2 1 18 17 9 13 12 10 18 17 9 13 12 10 18 17 9 13 12 10 18 17 13 9 12 10 مرحله 3 : سه عمل مقایسه و یک عمل جابجایی رخ داده است 6 5 4 3 2 1 18 17 13 9 12 10 18 17 13 9 12 10 18 17 13 12 9 10 مرحله 4 : دو عمل مقایسه و یک جابجایی رخ داده است.
6 5 4 3 2 1 18 17 13 12 9 10 18 17 13 12