Linear Search Algorithm

#116 أغسطس 2008 في 00:19 صاحب الموضوع

السلام عليكم و رحمة الله بركاته ,,,,,

اتمنى ان تكونوا اخوتى فى خير حال

Linear Search Algorithm

==================

البيانات غالبا تخزن فى شكل تتابعى مثل المصفوفات. لذلك فأن ابسط طريقة للبحث داخل مصفوفة هى مقارنة معلومة ما بجميع عناصر المصفوفة بداية من اولها حتى اخر عنصر فيها.

هذه الطريقة تسمى البحث الخطى Linear Search.

فى البحث الخطى (لا اعرف ان كانت الترجمة صحيحة ام لا) يتم مقارنة مفتاح البحث Search Key (الهدف المقصود البحث عنه) بكل عنصر فى المصفوفة.

البحث الخطى يبدأ دائما بأول subscript فى المصفوفة و يقارنه بـمفتاح البحث المدخل من قبل المستخدم

فاذا وجده يساوى لقيـــمة مفتاح البحث فأن دالة البحث تُرجع مكان هذا المفتاح فى المصفوفة.

مثال: اذا ادخل المستخدم قيمة 17 للبحث عنها داخل المصفوفة , فإن البرنامج يبدأ هكذا ,,,,

مقارنة مفتاح البحث بــ Index رقم 0 فى المصفوفة يُرجع رقم 0 ( هذا هو مكان مفتاح البحث)

و اذا لم يجده ينتقل على Index رقم 1 فاذا وجده يٌرجع قيمة واحد و اذا لم يجده ينتقل الى Index رقم 2

و هكذا حتى يجد هدفه فى المصفوفة .

هذا هو مخطط flowchart لعمل الدالة linearsearch

كود الدالة linearsearch

=cpp>

	//Linear Search Function	int linearsearch(int a[],int key,int size) //search function	{	    for (int i=0; i < size; i++) //loop to pass over all data in the array to find the sear	        ch key	    {	        if (a == key)	            return i; //return position of search key	    }	    return -1; //return -1 to tell the user that search key isn't found	}

شرح الكود :

هذه دالة Function اسميناها linearsearch و لها ثلاث parameters و هما مصفوفة للبحث داخله ثم قيمة مفتاح البحث ثم حجم المصفوفة .

بعدها انشاءنا loop حلقة دوارة لتدور على كل بيانات المصفوفة و تقارنها بمفتاح البحث .

فاذا وجدت احد subscripts داخل المصفوفة مساوِ لقيمة مفتاح البحث فأنها تُرجع قيمة هذا subscript

و اذا لم تجده ترجع -1 )لا يجوز ان ترجع هذه الدالة صفر 0 لأن اول عنصر فى المصفوفة index الخاص به = 0)

نأتى الان الى كود الدالة الرئيسية فى برنامجنا و هى الدالة التى لا نستطيع الاستغناء عنها :D main( )

	//Linear Search Algorithm	//main() function	#include <iostream>	using namespace std;	int linearsearch(int[], int, int); //function prototype	int main()	{	    int const SIZE = 100; //Defining constant for sizing array	    int a[SIZE];	    int key ; //varaible needed to recieve user input for search key	    for (int i = 0; i < SIZE; i++) //Loop to fill the array with data	    {	        a= (i * 3)+5;	    }	    cout << "Enter integer: ";	    cin >> key;	    int element = linearsearch(a,key,SIZE); //variable which holds the element number of search	    key	    if (element != -1) //if element = -1 then out of array	        cout << "The integer is element no." << element << endl;	    else	        cout << "Value not found"<<endl;	    system("pause");	    return 0;	}

شرح الكود:

السطر 6: قمنا بتعريف function prototype ليستخدمها المترجم فى تعريف الدالة

السطر9: تعريف ثابت قيمته = حجم المصفوفة

السطر 10: تعريف المصفوفة و حجمها يساوى حجم الثابت SIZE

السطر 13 --< 16: تعريف حلقة دوارة loop لملئ المصفوفة ببعض البيانات (للتجربة)

السطر 19: تعريف متغير element ليحمل القيمة التى ترجعها دالة البحث linearsearch

السطر 20 --< 26 : جملة If للتأكد من القيمة التى ترجعها الدالة

اذا كانت -1 فهذا يعنى ان مفتاح البحث لم يتم العثور عليه

اذا كانت i (قيمة Index الذى يحتوى على مفتاح البحث) يتم عرض قيمته على الشاشة

=================================

الى هنا انتهى الشرح .... ارجو ان اكون قد وفقنى الله فى عرض هذه الخوارزمية.

اى استفسارات يرجى وضعها و مناقشتها معا مع خبراء C++ فى هذا المنتدى الرائع.

ملحوظة: كود البرنامج كاملا مرفق.

السلام عليكم و رحمة الله و بركاته

تعديل : اعادة رفع المرفقات=cpp>

linearsearch.rar

تم تعديل هذه المشاركة بواسطة مصطفى 36a2 في 7 فبراير 2014 في 22:58

من مواضيعى :

[درس] الرسم ثنائى الأبعاد فى Qt

#216 أغسطس 2008 في 01:47

شكرا لك أخي عمر على هذا الموضوع الجميل

ولإعطاء الموضوع أكثر فائدة سوف أضع كود للبحث من خلال المكتبة algorithm للدالة Find التي تعود بؤشر للعنصر المشار إليه

#include <iostream>
 #include <algorithm>
 using namespace std;

 int main()
 {
 int number[]={1,5,8,10,85,100,89};
 int a;

 cout << "Enter the numbern";
 cin >> a;
 int* num=find(number,number+7,a);
 cout << "The number int" << (num-number) << endl;

 return 0;

 }

شكرا لك مرة أخرى أخ عمر

ويعطيك العافية

تحياااااتي

للصداقة البرمجية

pro-vb6@hotmail.com

#316 أغسطس 2008 في 18:41

وهذه دالة sHowManyTimes

هذه الدالة تقوم باخبارك كم مره تكرر العدد .

انسخ الكود

int sHowManyTimes(int a[],int key,int size)
{
int n(0);
for(int i=0; i< size ;i++) // loop
{
if(a[i]==key) // compare
++n; // keep the number of times
}
return n; // return value
}

العمل على الداالة

انسخ الكود

#include <iostream>
using namespace std;
int sHowManyTimes(int[],int ,int )
int main()
{
int number[]={1,2,3,4,5,6};
int x,hmt(0);
int size=6;
cout << "Enter The number ";
cin >> x;
hmt=sHowManyTimes(number,x,size);
if(hmt>0)
{
cout<<"there are "<<hmt;
}
else cout<<"sorry,Not found";
cout<<endl;
system("PAUSE");
return 0;
}

سبحان الله , الله اكبر , ولله الحمد

#416 أغسطس 2008 في 19:33

اقتباس
ممكن طلب من اخى ابو فهيد : ممكن شرح لعمل الدالة find ؟؟ و ايضا parameters الخاصة بها ؟؟

غالي والطلب رخيص ياخيو ,,,

تستخدم خوارزمية Find() للبحث عن قيمة محدد وتعود بؤشر للعنصر, وتأخذ الدالة Find() ثلاث وسائط :

1- الأول : المصفوفة التي فيها القيمة التي سوف تبحث عنها

2-الثاني: العنصر الأقصى للبحث بمعنى إلى اي عنصر سوف يستمر البحث

3-الثالث: القيمة الذي تبحث عنه

int number[]={1,5,8,10,85,100,89};

عند بحثك عن القيمة 10 في المصفوفة مثلا

سوف يعيد بمؤشر لموقع القيمة وهي العنصر 3

ملاحظة : يجب تضمين المكتبة algorithm لتتمكن من إستخدام الدالة Find()

أتمنى من الجميع إذا رأيتم أي خطأ مني في الشرح أرجو تصحيحه وذلك لأني مبتدأ في اللغة

هذا والله أعلم ,,,

يعيطكم العافية,,

تحيااااتي ,,,

للصداقة البرمجية

pro-vb6@hotmail.com

Linear Search Algorithm

مواضيع مشابهة