مقالات و جزوه های درسی رشته کامپیوتر

5- ارسال آرايه به تابع‌

كد float a[]; كه آرايه a را اعلان مي‌كند دو چيز را به كامپايلر مي‌گويد:

1- اين که نام آرايه a است

2- عناصر آرايه از نوع float هستند.

 سمبل a نشاني حافظۀ آرايه را ذخيره مي‌کند. لازم نيست تعداد عناصر آرايه به کامپايلر گفته شود زيرا از روي نشاني موجود در a مي‌توان عناصر را بازيابي نمود. به همين طريق مي‌توان يک آرايه را به تابع ارسال کرد. يعني فقط نوع آرايه و نشاني حافظۀ آن به عنوان پارامتر به تابع فرستاده مي‌شود.

 

مثال‌ 9-6 ارسال آرايه به تابعي كه مجموع عناصر آرايه را برمي‌گرداند

int sum(int[],int);

int main()

{ int a[] = { 11, 33, 55, 77 };

 int size = sizeof(a)/sizeof(int);

 cout << "sum(a,size) = " << sum(a,size) << endl;}

int sum(int a[], int n)

{ int sum=0;

 for (int i=0; i

 sum += a[i];

 return sum;

}

فهرست پارامتر تابع فوق به شکل (int a[], int n) است‌ به اين معنا که اين تابع يک آرايه از نوع int و يک متغير از نوع int دريافت مي‌کند.

به اعلان اين تابع در بالاي تابع main() نگاه کنيد. نام پارامترها حذف شده است.

هنگام فراخواني تابع نيز از عبارت sum(a,size) استفاده شده که فقط نام آرايه به تابع ارسال شده.

نام آرايه در حقيقت نشاني اولين عنصر آرايه است (يعني a[0])

تابع از اين نشاني براي دستيابي به عناصر آرايه استفاده مي‌کند. همچنين تابع مي‌تواند با استفاده از اين نشاني، محتويات عناصر آرايه را دست‌کاري کند.

پس ارسال آرايه به تابع شبيه ارسال متغير به طريق ارجاع است. به مثال بعدي دقت کنيد.

 

مثال‌ 10-6 توابع ورودي و خروجي براي يک آرايه
در اين برنامه از تابع read() استفاده مي‌شود تا مقاديري به داخل آرايه وارد شود. سپس با استفاده از تابع print() مقادير داخل آرايه چاپ مي‌شوند:

 

void read(int[],int&;)

void print(int[],int);

int main()

{ const int MAXSIZE=100;

 int a[MAXSIZE]={0}, size;

 read(a,size);

 cout << "The array has " << size << " elements: ";

 print(a,size);

}

خروجی:

 

Enter integers. Terminate with 0:

a[0]: 11

a[1]: 22

a[2]: 33

a[3]: 44

a[4]: 0

The array has 4 elements: 11 22 33 44

 

 

void read(int a[], int& n)

{ cout << "Enter integers. Terminate with 0:\n";

 n = 0;

 do

 { cout << "a[" << n << "]: ";

 cin >> a[n];

 { while (a[n++] !=0 && n < MAXSIZE);

 --n; // don't count the 0

}

 

void print(int a[], int n)

{ for (int i=0; i

 cout << a[i] << " ";

}

 

چون n يك متغير است، براي اين که تابع read() بتواند مقدار آن را تغيير دهد اين متغير بايد به شکل ارجاع ارسال شود.

 همچنين براي اين که تابع مذکور بتواند مقادير داخل آرايه a را تغيير دهد، آرايه نيز بايد به طريق ارجاع ارسال شود، اما ارجاع آرايه‌ها کمي متفاوت است.

 

در C++ توابع قادر نيستند تعداد عناصر آرايۀ ارسالي را تشخيص دهند. بنابراين به منظور ارسال آرايه‌ها به تابع از سه مشخصه استفاده مي‌شود:

 

1 – آدرس اولين خانۀ آرايه

2 – تعداد عناصر آرايه 

3 – نوع عناصر آرايه

 

تابع با استفاده از اين سه عنصر مي‌تواند به تک تک اعضاي آرايه دستيابي کند.

 

آدرس اولين خانۀ آرايه، همان نام آرايه است.

 پس وقتي نام آرايه را به تابع بفرستيم آدرس اولين خانه را به تابع فرستاده‌ايم.

نوع آرايه نيز در تعريف تابع اعلان مي‌شود.

 بنابراين با اين دو مقدار، تابع مي‌تواند به آرايه دسترسي داشته باشد.

 

مثال‌ 11-6 آدرس اولين خانۀ آرايه و مقدار درون آن

برنامۀ زير، آدرس ذخيره شده در نام آرايه و مقدار موجود در آن خانه را چاپ مي‌کند:

int main()

{ int a[] = { 22, 44, 66, 88 };

 cout << "a = " << a << endl; // the address of a[0]

 cout << "a[0] = " << a[0]; // the value of a[0]

}

خروجی:

a = 0x0064fdec

a[0] = 22

 

اين برنامه تلاش مي‌کند که به طور مستقيم مقدار a را چاپ کند. نتيجۀ چاپ a اين است که يک آدرس به شکل شانزده دهي چاپ مي‌شود. اين همان آدرس اولين خانۀ آرايه است. يعني درون نام a آدرس اولين عنصر آرايه قرار گرفته. خروجي نيز نشان مي‌دهد که a آدرس اولين عنصر را دارد و a[0] مقدار اولين عنصر را.

 

6- الگوريتم جستجوي خطي

آرايه‌ها بيشتر براي پردازش يک زنجيره از داده‌ها به کار مي‌روند.

 اغلب لازم است که بررسي شود آيا يک مقدار خاص درون يک آرايه موجود است يا خير. ساده‌ترين راه اين است که از اولين عنصر آرايه شروع کنيم و يکي يکي همۀ عناصر آرايه را جستجو نماييم تا بفهميم که مقدار مورد نظر در کدام عنصر قرار گرفته. به اين روش «جستجوي خطي» مي‌گويند.

 

مثال‌ 12-6 جستجوي خطي

برنامۀ زير تابعي را آزمايش مي‌کند که در اين تابع از روش جستجوي خطي براي يافتن يک مقدار خاص استفاده شده:

int index(int,int[],int);

int main()

{ int a[] = { 22, 44, 66, 88, 44, 66, 55};

 cout << "index(44,a,7) = " << index(44,a,7) << endl;

 cout << "index(50,a,7) = " << index(50,a,7) << endl;

}

int index(int x, int a[], int n)

{ for (int i=0; i

 if (a[i] == x) return i;

 return n; // x not found

}

خروجی:

index(44,a,7) = 1

index(40,a,7) = 7

 

تابع index() سه پارامتر دارد:

1.  پارامتر x مقداري است که قرار است جستجو شود،
2. پارامتر a آرايه‌اي است که بايد در آن جستجو صورت گيرد
3.  و پارامتر n هم ايندکس عنصري است که مقدار مورد نظر در آن پيدا شده است.

 در اين تابع با استفاده از حلقۀ for عناصر آرايه a   پيمايش شده و مقدار هر عنصر با x  مقايسه مي‌شود. اگر اين مقدار با x برابر باشد، ايندکس آن عنصر بازگردانده شده و تابع خاتمه مي‌يابد.

 

اگر مقدار x در هيچ يک از عناصر آرايه موجود نباشد، مقداري خارج از ايندکس آرايه بازگردانده مي‌شود که به اين معناست که مقدار x در آرايۀ a موجود نيست.

 در اولين اجراي آزمايشي، مشخص شده که مقدار 44 در a[1] واقع است و در اجراي آزمايشي دوم مشخص شده که مقدار 40 در آرايۀ a موجود نيست (يعني مقدار 44 در a[7] واقع است و از آن‌جا که آرايۀ a فقط تا a[6] عنصر دارد، مقدار 7 نشان مي‌دهد که 40 در آرايه موجود نيست).

7- مرتب‌سازي حبابي

«مرتب‌سازي حبابي» يکي از ساده‌ترين الگوريتم‌هاي مرتب‌سازي است.

 در اين روش، آرايه چندين مرتبه پويش مي‌شود و در هر مرتبه بزرگ‌ترين عنصر موجود به سمت بالا هدايت مي‌شود و سپس محدودۀ مرتب‌سازي براي مرتبۀ بعدي يکي کاسته مي‌شود.

 در پايان همۀ پويش‌ها، آرايه مرتب شده است.

طريقۀ يافتن بزرگ‌ترين عنصر و انتقال آن به بالاي عناصر ديگر به اين شکل است

1. اولين عنصر آرايه با عنصر دوم مقايسه مي‌شود.
2.  اگر عنصر اول بزرگ‌تر بود، جاي اين دو با هم عوض مي‌شود.
3.  سپس عنصر دوم با عنصر سوم مقايسه مي‌شود.
4.  اگر عنصر دوم بزرگ‌تر بود، جاي اين دو با هم عوض مي‌شود

 و به همين ترتيب مقايسه و جابجايي زوج‌هاي همسايه ادامه مي‌يابد تا وقتي به انتهاي آرايه رسيديم، بزرگ‌ترين عضو آرايه در خانۀ انتهايي قرار خواهد گرفت.

در اين حالت محدودۀ جستجو يکي کاسته مي‌شود

 و دوباره زوج‌هاي کناري يکي يکي مقايسه مي‌شوند تا عدد بزرگ‌تر بعدي به مکان بالاي محدوده منتقل شود. اين پويش ادامه مي‌يابد تا اين که وقتي محدوده جستجو به عنصر اول محدود شد، آرايه مرتب شده است.

 

مثال‌ 13-6 مرتب‌سازي

برنامۀ زير تابعي را آزمايش مي‌کند که اين تابع با استفاده از مرتب‌سازي حبابي يک آرايه را مرتب مي‌نمايد:

void print(float[],int);

void sort(float[],int);

int main()

{float a[]={55.5,22.2,99.9,66.6,44.4,88.8,33.3, 77.7};

 print(a,8);

 sort(a,8);

 print(a,8);

}

خروجی:

55.5, 22.2, 99.9, 66.6, 44.4, 88.8, 33.3, 77.7

22.2, 33.3, 44.4, 55.5, 66.6, 77.7, 88.8, 99.9

 

 

void sort(float a[], int n)

{ // bubble sort:

 for (int i=1; i

 // bubble up max{a[0..n-i]}:

 for (int j=0; j

 if (a[j] > a[j+1]) swap (a[j],a[j+1]);

 //INVARIANT: a[n-1-i..n-1] is sorted

}

 

 

تابع sort() از دو حلقۀ تودرتو استفاده مي‌كند.

1- حلقه for داخلي زوج‌هاي همسايه را با هم مقايسه مي‌كند و اگر آن‌ها خارج از ترتيب باشند، جاي آن دو را با هم عوض مي‌کند.

وقتي for داخلي به پايان رسيد، بزرگ‌ترين عنصر موجود در محدودۀ فعلي به انتهاي آن هدايت شده است.

 2-سپس حلقۀ for بيروني محدودۀ جستجو را يکي کم مي‌کند و دوباره for داخلي را راه مي‌اندازد تا بزرگ‌ترين عنصر بعدي به سمت بالاي آرايه هدايت شود.