جلسه سیزدهم(ارسال آرایه به توابع و جستجو و مرتب نمودن آن)
ارسال آرايه ها به توابع
برای ارسال يک آرايه به عنوان آرگومان به يک تابع ، کافيست نام آرايه را بدون علامت براکت ([]) به کار ببريد . به عنوان مثال اگر آرايه ای با نام x به صورت زير تعريف شده باشد :
int x[24];
برای ارسال آن به تابع modifyArray کافيست تابع را به صورت زير:
modifyArray(x,24);
فراخوانی کنيد . دستور فوق آرايه و طول آن را به تابع modifyArray ارسال می کند . معمولاً هنگامی که آرايه ای را به تابعی ارسال می کنند ، طول آرايه را نيز همراه آرايه به عنوان يک آرگومان جداگانه به تابع می فرستند.
++C آرايه ها را با شيوه شبيه سازی شده ارسال آرگومان ها با ارجاع به تابع ارسال می نمايد ، لذا تابع فراخوانی شده مقدار عناصر آرايه ارسالی را می تواند تغيير دهد . هنگامی که نام تابع را به عنوان آرگومان تابع به کار می بريم ، آدرس خانه حافظه اولين عنصر آرايه به تابع ارسال می شود لذا تابع می داند که عناصر آرايه در کجای حافظه قرار گرفته اند . بنابراين هنگامی که تابع فراخوانی شده عناصر آرايه را تغيير می دهد ، اين تغييرات روی عناصر آرايه اصلی که به تابع ارسال شده است ، انجام می پذيرد .
نکته : توجه داشته باشيد که عناصر آرايه را به صورت جداگانه همانند ارسال متغيرها و يا مقادير عددی به تابع ارسال کرد . در اين صورت تغيير بر روی آرگومان ارسالی ، تأثيری بر روی عنصر آرايه نخواهد داشت . در حقيقت اين شيوه ، همان ارسال با مقدار می باشد .
برای اينکه تابعی قادر به دريافت يک آرايه به عنوان ورودی باشد ، هنگام تعريف تابع در ليست آرگومانهای آن ، اين مطلب بايد مشخص گردد . به عنوان مثال تعريف تابع modifyArray را به صورت زير می توان نوشت :
void modifyArray (int b[] ,int array size)
دستور فوق مشخص می کند که تابع modifyArray قادر به دريافت آدرس آرايه ای از اعداد صحيح توسط آرگومان b و تعداد عناصر آرايه توسط آرگومان arraySize می باشد . ضمناً تعداد عناصر آرايه را لازم نيست بين براکت ها ([]) بنويسيد ، اگر اين کار نيز صورت پذيرد ، کامپايلر آن را ناديده می گيرد . توجه داشته باشيد که پيش تعريف تابع فوق را به صورت زير بنويسيد :
void modifyArray (int [] , int);
برنامه زير نحوه ارسال يک آرايه را به تابع و تفاوت ارسال يک عنصر آرايه به تابع و ارسال کل آرايه به تابع را نشان می دهد .
#include
void modifyArray( int [], int );
void modifyElement( int );
void main()
{
const int arraySize = 5;
int a[ arraySize ] = { 0, 1, 2, 3, 4 };
cout<<"Effects of passing entire array by reference:"
<<"\n\nThe values of the original array are:\n";
// output original array
for ( int i = 0; i < arraySize; i++ )
cout << "\t"<< a[ i ];
cout << endl;
// pass array a to modifyArray by reference
modifyArray( a, arraySize );
cout << "The values of the modified array are:\n";
// output modified array
for ( int j = 0; j < arraySize; j++ )
cout << "\t" << a[ j ];
// output value of a[ 3 ]
cout<<"\n\n\n"
<<"Effects of passing array element by value:"
<<"\n\nThe value of a[3] is " << a[ 3 ] << '\n';
// pass array element a[ 3 ] by value
modifyElement( a[ 3 ] );
// output value of a[ 3 ]
cout << "The value of a[3] is " << a[ 3 ] << endl;
}
// in function modifyArray, "b" points to
// the original array "a" in memory
void modifyArray( int b[], int sizeOfArray )
{
// multiply each array element by 2
for ( int k = 0; k < sizeOfArray; k++ )
b[ k ] *= 2;
}
// in function modifyElement, "e" is a local copy of
// array element a[ 3 ] passed from main
void modifyElement( int e )
{
// multiply parameter by 2
cout << "Value in modifyElement is "
<< ( e *= 2 ) << endl;
}
خروجی برنامه فوق به صورت زير می باشد :
Effects of passing entire array by reference:
The values of the original array are:
0 1 2 3 4
The values of the modified array are:
0 2 4 6 8
Effects of passing array element by value:
The value of a[3] is 6
Value in modifyElement is 12
The value of a[3] is 6
در برنامه فوق ، تابع modifyArray مقدار عناصر آرايه a را که به آن فرستاده شده است دو برابر می کند . تابع modifyElement مقدار آرگومان دريافتی را دو برابر کرده و در خروجی چاپ می کند ولی تأثيری در نسخه اصلی عنصر آرايه نداشته و تغييری در مقدار آن ايجاد نمی کند .
بعضی مواقع ممکن است بخواهيد که تابعی ، اجازه تغيير عناصر آرايه ای که به آن فرستاده شده است را نداشته باشد . برای اين کار هنگام تعريف تابع کافی است از کلمه const قبل از آرگومان مربوط به آن آرايه استفاده کنيد ، در چنين حالتی اگر داخل تابع قصد تغيير مقدار عناصر آرايه را داشته باشيد با يک پيغام خطای کامپايلر مواجه می شويد و کامپايلر اجازه اين کار را به شما نمی دهد . به برنامه زير توجه کنيد :
#include
void tryToModifyArray( const int [] );
void main()
{
int a[] = { 10, 20, 30 };
tryToModifyArray( a );
cout << a[0] <<' '<< a[1] <<' '<< a[2] <<'\n';
}
// In function tryToModifyArray, "b" cannot be used
// to modify the original array "a" in main.
void tryToModifyArray( const int b[] )
{
b[ 0 ] /= 2; // error
b[ 1 ] /= 2; // error
b[ 2 ] /= 2; // error
}
هنگام کامپايل کردن برنامه فوق با پيغام های خطای زير مواجه خواهيد شد ، چون در تابع قصد تغيير عناصر آرايه ای را که به صورت ثابت به تابع ارسال شده بود ، داشتيم .
Error in line 19: Cannot modify a const object
Error in line 20: Cannot modify a const object
Error in line 21: Cannot modify a const object
مرتب کردن آرايه ها
مرتب کردن اطلاعات چه به صورت صعودی يا نزولی ، يکی از مهمترين وظايف کامپيوتر می باشد . به عنوان مثال تعيين رتبه دانش آموزان يک مدرسه بر اساس معدل ، تعيين رتبه شرکت کنندگان در کنکور ، مرتب کردن شماره تلفن ها بر اساس نام صاحب تلفن را می توان نام برد . برای آشنايی با شيوه مرتب کردن ، ليست اعداد زير را در نظر بگيريد :
2 , 5 , 4 , 3 , 6 , 1
برای مرتب کردن ليست اعداد فوق از کوچک به بزرگ آنها را در آرايه ای قرار می دهيم :
int a[] = { 2 , 5 , 4 , 3 , 6 , 1};
حال کافی است آرايه a را به صورت صعودی مرتب کنيم . برای انجام اين کار از روشی به نام مرتب کردن حبابی استفاده می کنيم . اين تکنيک به دليل اينکه مقادير کوچکتر همانند حبابی در آب به سمت بالا حرکت می کنند ، مرتب کردن حبابی گفته می شود . برای مرتب کردن آرايه چندين بار بايد روی آرايه حرکت کنيم و در هر بار حرکت عناصر دو به دو با هم مقايسه می شوند ، و در صورتی که به صورت نزولی قرار داشته باشند مقاديرشان جابه جا می گردد و در غير اين صورت به همان ترتيب باقی می مانند .
برنامه زير ليست اعداد ذکر شده را به شيوه مرتب کردن حبابی ، از کوچک به بزرگ مرتب می کند .
#include
void showArray(const int [] , int);
void main()
{
const int arraySize = 6;
int a[ arraySize ] = { 2, 5, 4, 3, 6 ,1};
int hold;
cout << "Data items in original order\n";
showArray(a,arraySize);
for ( int i = 0; i < arraySize - 1 ; i++ )
for ( int j = 0; j < arraySize - 1; j++ )
if ( a[ j ] > a[ j + 1 ] ) {
hold = a[ j ];
a[ j ] = a[ j + 1 ];
a[ j + 1 ] = hold;
}
cout << "\nData items in ascending order\n";
showArray(a,arraySize);
}
void showArray( const int array[] ,int arraySize)
{
for (int c=0; c
cout << array[c] << " ";
cout << endl;
}
خروجی برنامه فوق به صورت زير می باشد :
Data items in original order
2 5 4 3 6 1
Data items in ascending order
1 2 3 4 5 6
جستجو در آرايه ها
عمل جستجو يکی از مهمترين وظايف برنامه های کامپيوتری می باشد . به عنوان مثال دفتر تلفنی را در نظر بگيريد که به دنبال نام فردی در آن می گرديم و يا جستجوی نام يک دانشجو در ليست دانشجويان کلاس . در اين مبحث دو روش جستجو را مورد بررسی قرار می دهيم . يک روش جستجوی خطی است که معمولاً در آرايه های نا مرتب مورد استفاده قرار می گيرد و روش ديگر جستجوی دو دويی می باشد که در آرايه های مرتب از اين شيوه می توانيم استفاده کنيم .
در روش جستجوی خطی ، عنصر مورد جستجو با هر يک از عناصر آرايه مقايسه می شود ، چنانچه دو عنصر برابر بودند ، عمل جستجو به پايان می رسد و انديس عنصر برگردانده می شود و گرنه مقايسه با عنصر بعدی آرايه انجام می پذيرد . از آنجا که عناصر آرايه نا مرتب می باشند عنصر مورد جستجو در هر کجای آرايه می تواند باشد لذا عمل مقايسه تا يافتن عنصر مورد نظر و يا رسيدن به انتهای آرايه يعنی جستجو در همه عناصر آرايه ادامه می يابد . برنامه زير نمونه ای از جستجوی خطی در آرايه می باشد :
#include
int linearSearch(const int [], int, int );
void main()
{
const int arraySize = 7;
int a[ arraySize ]={2,6,4,3,12,10,5};
int searchKey;
cout << "Enter integer search key: ";
cin >> searchKey;
int element=linearSearch(a, searchKey, arraySize);
if ( element != -1 )
cout << "Found value in element "
<< element << endl;
else
cout << "Value not found" << endl;
}
int linearSearch( const int array[],
int key, int sizeOfArray )
{
for ( int j = 0; j < sizeOfArray; j++ )
if ( array[ j ] == key )
return j;
return -1;
}
خروجی برنامه فوق به صورت زير می باشد :
Enter integer search key: 12
Found value in element 4
Enter integer search key: 20
Value not found
روش جستجوی دو دويی در آرايه های مرتب شده قابل استفاده می باشد و از سرعت بالايی برخوردار می باشد . در اين الگوريتم ، در هر بار مقايسه ، نيمی از عناصر آرايه حذف می شوند . الگوريتم عنصر ميانی آرايه را می يابد و آن را با عنصر مورد جستجو، مقايسه می کند . اگر برابر بودند ، جستجو به پايان رسيده و انديس عنصر برگردانده می شود ، در غير اين صورت عمل جستجو روی نيمی از عناصر انجام می گيرد . اگر عنصر مورد جستجو کوچکتر از عنصر ميانی باشد ، جستجو روی نيمه اول آرايه صورت می پذيرد ، در غير اين صورت نيمه دوم آرايه جستجو می شود . اين جستجوی جديد روی زير آرايه طبق الگوريتم جستجو روی آرايه اصلی انجام می شود يعنی عنصر ميانی زير آرايه يافته می شود و با عنصر مورد جستجو مقايسه می گردد ، اگر برابر نباشند زير آرايه مجدداً نصف می شود و در هر بار جستجو زير آرايه ها کوچکتر می گردند . عمل جستجو تا يافتن عنصر مورد نظر( يعنی برابر بودن عنصر مورد جستجو با عنصر ميانی يکی از زير آرايه ها ) و يا نيافتن عنصر مورد نظر ( برابر نبودن عنصر مورد جستجو با عنصر زير آرايه ای شامل تنها يک عنصر ) ادامه می يابد . برنامه زير نمونه ای از جستجوی دو دويی در آرايه مرتب می باشد .
#include
int binarySearch( const int [], int, int);
void main()
{
const int arraySize = 15;
int a[ arraySize ]={0,2,4,6,8,10,12,14,
16,18,20,22,24,26,28};
int key;
cout << "Enter a number between 0 and 28: ";
cin >> key;
int result =
binarySearch( a, arraySize, key);
if ( result != -1 )
cout << '\n' << key << " found in array element "
<< result << endl;
else
cout << '\n' << key << " not found" << endl;
}
int binarySearch( const int b[],
int arraySize ,
int searchKey )
{
int middle,low=0,high=arraySize - 1;
while ( low <= high )
{
middle = ( low + high ) / 2;
if ( searchKey < b[ middle ] )
high = middle - 1;
else
if ( searchKey > b[ middle ] )
low = middle + 1;
else return middle;
}
return -1;
}
خروجی برنامه فوق به صورت زير می باشد :
Enter a number between 0 and 28: 8
8 found in array element 4
Enter a number between 0 and 28: 25
25 not found