در برنامه‌هایی که داده‌های فراوانی رو پردازش می‌کنن استفاده از متغیرهای معمولی کار عاقلانه‌ای نیست چون در بسیاری از این برنامه‌ها پردازش دسته‌ای صورت می‌گیره به این معنی که مجموعه‌ای از داده‌های مرتبط با هم در حافظه قرار داده میشه و پس از پردازش، کل این مجموعه از حافظه خارج میشه و مجموعه بعدی در حافظه بارگذاری میشه.

اگه قرار باشه برای این کار از متغیرهای معمولی استفاده بشه بیشتر وقت برنامه‌نویس صرف پر و خالی کردن انبوهی از متغیرها میشه. به همین دلیل در بیشتر زبان‌های برنامه‌نویسی آرایه‌ها تدارک دیده شدن. آرایه رو می‌تونیم متغیری تصور کنیم که یک اسم داره ولی چندین مقدار رو به طور هم‌زمان نگهداری میکنه.

یک آرایه، یك زنجیره از متغیرهایی هست كه همه از یك نوع هستن. به این متغیرها اعضای آرایه میگن. هر عضو آرایه با یک شماره مشخص میشه که به این شماره ایندکس index  یا زیرنویس میگن. عناصر یک آرایه در خانه‌های پشت سر هم در حافظه ذخیره میشن. به این ترتیب آرایه رو می‌تونیم بخشی از حافظه تصور کنیم که این بخش خود به قسمت‌های مساوی تقسیم شدن و هر قسمت به یک عنصر تعلق دارد. شکل زیر آرایه a که پنج عنصر دارد رو نشان میده. عنصر a[0] حاوی مقدار 17.5 و عنصر a[1] حاوی 19.0 و عنصر a[4] حاوی مقدار 18.0 هست.

پردازش‌ آرایه ها

آرایه ها رو می‌تونیم مثل متغیرهای معمولی تعریف و استفاده کنیم. با این تفاوت که آرایه یک متغیر مرکب هست و برای دستیابی به هر یک از خانه‌های آن باید از ایندکس استفاده کنیم.

مثال: دستیابی مستقیم به عناصر آرایه  برنامه ساده زیر یک آرایه سه عنصری رو تعریف می‌کنه و سپس مقادیری رو در آن قرار میده و سرانجام این مقادیر رو چاپ می‌کنه:

#include <iostream>

using namespace std;

int main()

{

int a[3];

a[2] = 55;

a[0] = 11;

a[1] = 33;

cout << “a[0] = ” << a[0] << endl;

cout << “a[1] = ” << a[1] << endl;

cout << “a[2] = ” << a[2] << endl;

}

ساختار یا نحو کلی برای اعلان آرایه به این شکل هست:

type array_name[array_size];

عبارت type نوع عناصر آرایه رو مشخص می‌کنه.  array_name   نام آرایه هست. array_size   تعداد عناصر آرایه رو نشان میده. این مقدار باید یک عدد ثابت صحیح باشد و حتما باید داخل کروشه [] قرار بگیره.

مقداردهی آرایه ها

در C++ می‌تونیم یک آرایه رو با استفاده از فهرست مقداردهی، اعلان و مقدارگذاری کنیم:

float a[] = {22.2,44.4,66.6};

به این ترتیب مقادیر داخل فهرست به همان ترتیبی که چیده شدن درون عناصر آرایه قرار می‌گیرن. اندازه آرایه هم برابر با تعداد عناصر موجود در فهرست هست. پس همین خط مختصر، آرایه‌ای از نوع float و با نام a و با تعداد سه عنصر اعلان میکنه و هر سه عنصر رو با مقدارهای درون فهرست، مقداردهی میکنه.

مثال‌ : مقداردهی آرايه با استفاده از فهرست مقداردهی برنامه زير، آرايه a رو مقداردهی و سپس مقدار هر عنصر رو چاپ میكنه:

int main()

{ float a[] = { 22.2, 44.4, 66.6 };

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

for (int i=0; i<size; i++)

cout << “\ta[” << i << “] = ” << a[i] << endl;

}

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

float a[7] = { 55.5, 66.6, 77.7 };

تعداد مقادير موجود در فهرست مقداردهی نبايد از تعداد عناصر آرايه بيشتر باشه:

float a[3] = { 22.2, 44.4, 66.6, 88.8 }; // ERROR: too many values!

يك‌ آرايه‌ رو میتوانيم به طور کامل با صفر مقداردهی اوليه کنيم. برای مثال سه اعلان زير با هم برابرن:

float a[ ] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };

float a[9] = { 0, 0 };

float a[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };

اما به اين معنی نيست که از فهرست مقداردهی استفاده نشه. درست مثل يک متغير معمولی، اگر يک آرايه مقداردهی اوليه نشه، عناصر اون حاوی مقادير زباله میشه.

مثال‌: يك آرايه مقداردهی نشده برنامه زير، آرايه a رو اعلان می‌کنه ولی مقداردهی نمی‌كنه. با وجود اين، مقادير موجود در اون رو چاپ می‌كنه:

int main()

{ const int SIZE=4; // defines the size N for 4 elements

float a[SIZE]; // declares the array’s elements as float

for (int i=0; i<SIZE; i++)

cout << “\ta[” << i << “] = ” << a[i] << endl;

}

آرايه‌ها رو می‌تونیم با استفاده از عملگر جايگزينی مقداردهی کنیم اما نمی‌تونیم مقدار اون‌ها رو به هم دیگه تخصيص بدیم:

float a[7] = { 22.2, 44.4, 66.6 };

float b[7] = { 33.3, 55.5, 77.7 };

b = a; // ERROR: arrays cannot be assigned!

همچنين‌ نمی‌توانيم‌ يك‌ آرايه رو به طور مستقيم برای مقداردهی به آرایه ديگره استفاده كنيم‌:

float a[7] = { 22.2, 44.4, 66.6 };

float b[7] = a; // ERROR: arrays cannot be used as nitializers!

ايندكس بيرون از حدود آرايه‌

در بعضی از زبان‌های برنامه‌نويسيی، ايندکس آرايه نمی‌تونه از محدوده تعريف شده برای اون بيشتر باشه. برای مثال در پاسکال اگر آرايه a با تعداد پنج عنصر تعريف شده باشه و آنگاه a[7] دستيابی بشه، برنامه از کار می افته. اين سيستم حفاظتی در    C++ وجود نداره. مثال بعدی نشان میده که ايندکس يک آرايه هنگام دستيابی میتونه بيشتر از عناصر تعريف شده برای آن باشه و باز هم بدون اين که خطایی گرفته بشه، برنامه ادامه پبدا کنه.

مثال‌ : تجاوز ايندکس آرايه از محدوده تعريف شده برای آن برنامه زير يک خطای زمان اجرا داره؛ به بخشی از حافظه دستيابی میکنه که از محدوده آرايه بيرون هست:

in main()

{ const int SIZE=4;

float a[SIZE} = { 33.3, 44.4, 55.5, 66.6 };

for (int i=0; i<7; i++) //ERROR: index is out of bounds!

cout << “\ta[” << i << “] = ” << a[i] << endl;

}

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

مثال‌ : اثر همسايگی

برنامه زير از ايندکس خارج از محدوده استفاده می‌کنه و اين باعث میشه که مقدار يک متغير به طور ناخواسته تغيير کنه:

int main()

{ const int SIZE=4;

float a[] = { 22.2, 44.4, 66.6 };

float x=11.1;

cout << “x = ” << x << endl;

a[3] = 88.8; // ERROR: index is out of bounds!

cout << “x = ” << x << endl;

}

متغير x بعد از آرايه a اعلان‌ شده، پس يک سلول چهاربايتی بلافاصله بعد از دوازده بايت آرايه به آن تخصيص داده میشه. بنابراين وقتی برنامه تلاش می‌کنه مقدار 88.8 را در a[3] قرار بده که جزو آرايه نيست اين مقدار به شکل ناخواسته در x قرار می‌گيره.

اين خطا يکی از وحشت‌ناک‌ترين خطاهای زمان اجرا هست چون ممکنه اصلا نتونيم منبع خطا رو کشف کنيم. حتي ممکن هست به اين روش داده‌های برنامه‌های ديگه که در حال کارند رو خراب کنيم و اين باعث ايجاد اختلال در کل سيستم بشه. به اين خطا اثر همسايگی میگن. اين وظيفه برنامه‌نويس هست که تضمين کنه ايندکس آرايه هیچ وقت از محدوده اون خارج نشه.

مثال بعدی نوع ديگه از خطای زمان اجرا رو نشان میده: وقتی ايندکس آرايه بيش از حد بزرگ باشه.

مثال‌: ايجاد استثنای مديريت نشده

برنامه زير از كار می افته چون ايندكس آرايه خيلي بزرگ هست:

int main()

{ const int SIZE=4;

float a[] = { 22.2, 44.4, 66.6 };

float x=11.1;

cout << “x = ” << x << endl;

a[3333] =88.8;//ERROR: index is out of bounds!

cout << “x = ” << x << endl;

}

وقتي اين برنامه روی رايانه‌ای با سيستم عامل ويندوز اجرا بشه، يک صفحه هشدار که در شکل نشان داده شده روی صفحه ظاهر می‌شه.

اين پنجره میگه که برنامه تلاش داره به نشانی  0040108e از حافظه دستيابی پیدا کنه. اين مکان خارج از حافظه تخصيصی هست که برای اين برنامه گذاشته شده، بنابراين سيستم عامل برنامه رو متوقف می‌کنه.

پردازش‌گر استثنا

خطایی که در مثال بيان شده يک استثنای مديريت نشده ناميده میشه چون کدی وجود نداره که به اين استثنا پاسخ بده. در  ++C می‌تونيم کدهایی به برنامه اضافه کنيم که هنگام رخ دادن حالت‌های استثنا، از توقف برنامه جلوگيری کنه. به اين کدها پردازش‌گر استثنا میگن.

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

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

• نام آرايه a هست.
• عناصر آرايه از نوع float هستن.

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

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

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<n; i++)

sum += a[i];

return sum;

}

فهرست پارامتر تابع فوق به شکل (int a[], int n) هست‌ به اين معنا که اين تابع يک آرايه از نوع int و يک متغير از نوع int دريافت میکنه. به اعلان اين تابع در بالای تابع ()main نگاه کنيد. نام پارامترها حذف شده. هنگام فراخوانی تابع نيز از عبارت  sum(a,size)  استفاده شده که فقط نام آرايه به تابع ارسال بشه. نام آرايه در حقيقت نشانی اولين عنصر آرايه است يعني  a[0] .

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

مثال‌ : توابع ورودی و خروجی برای يک آرايه
در اين برنامه از تابع ()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);

}

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<n; i++)

cout << a[i] << ” “;

}

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

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

1. آدرس اولين خانه‌ی آرايه
2. تعداد عناصر آرايه
3. نوع عناصر آرايه

تابع با استفاده از اين سه عنصر می‌تونه به تک تک اعضای آرايه دستيابی پیدا کنه. آدرس اولين خانه‌ی آرايه، همان نام آرايه هست. پس وقتی نام آرايه رو به تابع بفرستيم آدرس اولين خانه رو به تابع فرستاده‌ايم. نوع آرايه هم در تعريف تابع اعلان میشه. بنابراين با اين دو مقدار، تابع می‌تونه به آرايه دسترسی داشته باشه.

مثال‌: آدرس اولين خانه آرايه و مقدار درون آن:

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

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 رو چاپ کنه. نتيجه‌ی چاپ a اين هست که يک آدرس به شکل شانزده‌دهی چاپ میشه. اين همان آدرس اولين خانه آرايه هست. يعنی داخل نام a آدرس اولين عنصر آرايه قرار گرفته. خروجی هم نشان میده که a آدرس اولين عنصر رو و a[0] مقدار اولين عنصر رو داره.

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

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

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

مثال: جستجوی خطی:

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

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<n; i++)

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

return n; // x not found

}

تابع ()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 در آرايه موجود نيست.

 مرتب‌سازی حبابی

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

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

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

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

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

مثال‌:  مرتب‌سازی

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

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);

}

void sort(float a[], int n)

{ // bubble sort:

for (int i=1; i<n; i++)

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

for (int j=0; j<n-i; j++)

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

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

}

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

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

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

الگوريتم جستجوی دودویی

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

و در اخر محدوده‌ی جستجو به يک عنصر محدود میشه که يا آن عنصر با مورد جستجو برابر هست و عنصر مورد نظر پیدا میشه يا اين که آن عنصر با مورد جستجو برابر نيست و عنصر مورد نظر داخل آرايه وجود نداره. اين روش پيچيده‌تر از روش جستجوی خطی هست ولی این روش مارو سریع تر به جواب میرسونه.

مثال‌: جستجوی دودویی

برنامه آزمون زير با برنامه‌ی آزمون مثال يکی هست اما تابعی که آمده از روش جستجوی دودویی برای يافتن مقدار درون آرايه استفاده می‌کنه:

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

int main()

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

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

cout << “index(60,a,7) = ” << index(60,a,7) << endl;

}

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

{ // PRECONDITION: a[0] <= a[1] <= … <= a[n-1];

// binary search:

int lo=0, hi=n-1, i;

while (lo <= hi)

{ i = (lo + hi)/2; // the average of lo and hi

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

if (a[i] < x) lo = i+1; // continue search in a[i+1..hi]

else hi = i-1; // continue search in a[0..i-1]

}

return n; // x was not found in a[0..n-1]

}

برای اين که بفهميم تابع چطور کار می‌کنه، فراخوانی index(44,a,7) رو دنبال می‌کنيم. وقتی حلقه شروع میشه، x=44 و n=7 و lo=0 و hi=6 هست. ابتدا i مقدار 3 =2/(6+0) رو می‌گيره. پس عنصر a[i] عنصر وسط آرایه‌ی a[0..6] هست. مقدار a[3] برابر با 55 هست که از مقدار x بزرگ‌تر هست. پس x در نيمه‌ی بالایی نيست و جستجو در نيمه پايينی ادامهپیدا میکنه. از این جهت  hi  با i-1 يعنی 2 مقداردهی میشه و حلقه تکرار میشه.

حالا hi=2 و lo=0 هست و دوباره عنصر وسط آرايه a[0..2] يعني a[1] با x مقايسه می‌شود .  a[1] برابر با 33 هست که کوچک‌تر از x هست. پس اين دفعه lo برابر با  i+1  يعنی 2 میشه. در سومين دور حلقه، hi=2 و lo=2 هست. پس عنصر وسط آرايه a[2..2] که همان a[2] هست با x مقايسه میشه.  a[2] برابر با 44 هست که با x برابر هست. پس مقدار 2 بازگشت داده میشه؛ يعنی‌ x مورد نظر در a[2] موجود هست.

حال فراخوانی index(60,a,7) رو دنبال می‌کنيم. وقتی حلقه شروع میشه، x=60 و n=7 و lo=0 و hi=6 هست. عنصر وسط آرایه a[0..6] عنصر a[3]=55 هست که از x کوچک‌تر هست. پس lo برابر با i+1=4 میشه و حلقه دوباره تکرار میشه. اين دفعه hi=6 و lo=4 هست . عنصر وسط آرايه a[4..6] عنصر a[5]=77 هست که بزرگ‌تر از x میشه. پس hi به i-1=4 تغيير میکنه و دوباره حلقه تکرار میشه. اين بار hi=4 و lo=4 هست و عنصر وسط آرايه a[4..4] عنصر a[4]=66 هست که بزرگ‌تر از  x  میشه‌. از این جهت hi به i-1=3 کاهش پیدا میکنه.

اما شرط حلقه غلط میشه چون hi<lo هست. پس تابع مقدار 7 رو برمی‌گردون يعنی عنصر مورد نظر در آرايه موجود نيست. داخل این تابع هر بار که حلقه تکرار بشه، محدوده جستجو 50% کوچک‌تر میشه. داخل آرايه n عنصری، روش جستجوی دودویی حداکثر به مقايسه نياز داره تا به پاسخ برسه. داخل روش جستجوی خطی به n مقايسه نياز هست.

تفاوت‌های جستجوی دودویی و خطی

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

مثال‌: مشخص كردن اين كه آيا آرايه مرتب هست يا نه. برنامه زير يک تابع بولی رو آزمايش می‌کنه. اين تابع مشخص میکنه که آيا آرايه داده شده غير نزولی هست يا نه:

bool isNondecreasing(int a[], int n);

int main()

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

cout<<“isNondecreasing(a,4) = ” << isNondecreasing(a,4)<< endl;

cout<<“isNondecreasing(a,7) = ” << isNondecreasing(a,7) << endl;

}

bool isNondecreasing(int a[], int n)

{ // returns true iff a[0] <= a[1] <= … <= a[n-1]:

for (int i=1; i<n; i++)

if (a[i]<a[i-1]) return false;

return true;

}

اين تابع يک بار کل آرايه رو پيمايش کرده و زوج‌های a[i-1] و a[i] رو مقايسه می‌کنه. اگر زوجی پیدا بشه که داخلش  a[i]<a[i-1] باشه، مقدار false رو بر می‌گردونه به اين معنی که آرايه مرتب نيست. true و false به شکل اعداد 1 و 0 در خروجی چاپ میشن چون مقادير بولی در حقيقت به شکل اعداد صحيح در حافظه ذخيره میشن. اگر پيش‌شرط مثال يعنی مرتب بودن آرايه رعايت نشه، جستجوی دودویی پاسخ درستی نمیده. به اين منظور اول بايد اين پيش‌شرط بررسی بشه.

با استفاده از تابع ()assert می‌تونیم اجرای يک برنامه رو به يک شرط وابسته کرد. اين تابع يک آرگومان بولی رو می‌پذيره. اگر مقدار آرگومان false باشه، برنامه رو تموم میکنه و موضوع رو به سيستم عامل گزارش میده‌. اگر مقدار آرگومان true باشه، برنامه رو بدون تغيير ادامه میده. تابع ()asset داخل سرفايل<cassert> تعريف شده.

مثال‌: استفاده از تابع ()assert برای رعايت كردن يك‌ پيش‌شرط

برنامه زير نسخه بهبوديافته‌ای از تابع ()search  رو آزمايش میکنه. در اين نسخه، از تابع isNonDecreasing() استفاده شده تا مشخص بشه آرايه مرتبه يا نه. نتيجه اين تابع به تابع  ()assert ارسال میشه تا اگه آرايه مرتب نباشه برنامه غلط نشه.

#include <cassert> // defines the assert() function

#include <iostream> // defines the cout object

using namespace std;

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

int main()

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

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

cout<<“index(44,a,8) = ” << index(44,a,8) << endl;

cout<<“index(60,a,8) = ” << index(60,a,8) << endl;

}

bool isNondecreasing(int a[], int n);

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

{ assert(isNondecreasing(a,n));

int lo=0, hi=n-1, i;

while (lo <= hi)

{ i = (lo + hi)/2;

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

if (a[i] < x) lo = i+1;

else hi = i-1; }

return n;

‌‌}

آرايه a[] که در اين برنامه استفاده شده خیلی مرتب‌ نيست‌ ولی هفت‌ عنصر اول‌ اون‌ مرتب‌ هست. بنابراين‌ داخل فراخوانیindex(44,a,7) تابع بولی مقدار true رو به     () assert  ارسال میکنه و برنامه ادمه پیدا میکنه. اما در دومين فراخوانی index(44,a,8) باعث میشه که تابع () isNondecreasingمقدار false رو به تابع ()assert  ارسال کنه كه در اين صورت برنامه متوقف میشه و ويندوز پنجره هشدار زیر رو نمايش میده.

استفاده از انواع شمارشی در آرايه

با استفاده از انواع شمارشی هم میتونیم آرايه‌ها رو پردازش کنیم.

مثال‌: شمارش با استفاده از روزهای هفته

اين‌ برنامه‌ يك‌ آرايه به نام‌ []high با هفت‌ عنصر از نوع float  تعريف‌ میكنه كه‌ هر عنصر حداکثر دما در يک روز هفته رو نشان میده:

int main()

{ enum Day { SUN, MON, TUE, WED, THU, FRI, SAT };

float high[SAT+1] = {28.6, 29.1, 29.9, 31.3, 30.4, 32.0, 30.7};

for (int day = SUN; day <= SAT; day++)

cout << “The high temperature for day ” << day << ” was “<< high[day] << endl;

}

انواع شمارشی به شکل مقادير عددی ذخيره میشن. اندازه آرايه، SAT+1 هست  چون SAT مقدار صحيح 6 رو داره و آرايه به هفت عنصر نيازمند هست. متغير day از نوع int هست‌ پس میتونیم مقادير Day رو به آن تخصيص بدیم. استفاده از انواع شمارشی در برخی از برنامه‌ها باعث میشه که کد برنامه خود استناد بشه. مثلا در مثال کنترل حلقه به شکل for (int day = SUN; day <= SAT; day++) باعث میشه که هر بيننده‌ای حلقه for بالا رو به راحتی بفهمه.

تعريف‌ انواع‌

انواع شمارشی يكی از راه‌هایی هست که کاربر میتونه نوع ساخت خودش رو تعريف کند. برای مثال این دستور :

enum Color{ RED,ORANGE,YELLOW, GREEN, BLUE, VIOLET };

يک نوع جديد به نام Color تعريف می‌کنه که متغيرهايی از اين نوع میتونن مقادير RED يا ORANGE يا YELLOW يا GREEN يا BLUE يا VIOLET رو داشته باشن. پس با استفاده از اين نوع میتونیم متغيرهايی به این شکل تعريف کنیم:

Color shirt = BLUE;

Color car[] = { GREEN, RED, BLUE, RED };

Floatwavelength[VIOLET+1]={420,480,530,570,600,620};

در اين‌جا shirt متغيری از نوع Color هست و با مقدار BLUE مقداردهی شده.  car يک آرايه چهار عنصریه و مقدار عناصر آن به ترتيب GREEN و RED و BLUE و REDهست. Wavelength   آرايه‌ای از نوع float هست که دارای VIOLET+1 عنصر يعنی 5+1=6 عنصر هست. در   C++میتونیم نام انواع استاندارد رو تغيير بدیم. با استفاده از کلمه کليدی typedef يک نام مستعار برای يک نوع استاندارد موجود تعريف میشه. نحوه استفاده از آن به این شکله:

typedef type alias;

 type   يک نوع استاندارد و alias نام مستعار برای اون هست‌. برای مثال‌ کسانی که با پاسکال برنامه مینويسن به جای نوع long از عبارت Integer استفاده میکنن و به جای نوع double از عبارت Real استفاده میشه. اين افراد میتونن به شکل زير از نام مستعار استفاده کنن:

typedef long Integer;

typedef double Real;

بعد از اون کدهای زير معتبرهستن:

Integer n = 22;

const Real PI = 3.141592653589793;

Integer frequency[64];

دستور typedef نوع جديد رو اعلان نمیکنه، فقط به يک نوع موجود نام مستعاری رو نسبت میده. در برنامه زیر از typedef استفاده شده تا بتونیم از نام مستعار sequrnce به عنوان يک نوع استفاده کنیم. اين نوع در فهرست پارامترها و اعلان a در تابع   main()  به کار رفته:

typedef float Sequence[];

void sort(Sequence,int);

void print(Sequence,int);

int main()

{ Sequence 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);

}

void sort(Sequence a, int n)

{ for (int i=n-1; i>0; i–)

for (int j=0; j<i; j++)

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

}

;[]typedef float Seguence   علامت براكت‌ها [] نشان میده که هر چيزی که از نوع Sequence   تعريف بشه، يک آرايه هست و عبارت float هم میگه که اين آرايه از نوع float  هست.

آرايه‌های چند بعدی

همه آرايه‌هايی كه نا الان گفتیم يک بعدی، خطی و رشته‌ای هستن. میتونيم آرايه‌ای تعريف کنيم که از نوع آرايه باشه، يعنی هر خانه از اون آرايه، خود يک آرايه باشه. به اين نوع آرايه‌ها، آرايه‌های چندبعدی میگيم. يک آرايه دو بعدی آرايه‌ای هست که هر خانه از اون، خود يک آرايه يک بعدی باشه. يک آرايه سه بعدی آرايه‌ای هست که هر خانه از آن يک آرايه دو بعدی باشه.

شکل دستيابی به عناصر در آرايه‌های چند بعدی مثل آرايه‌های يک بعدی هستن. مثلا دستور:

a[1][2][3] = 99;

مقدار 99 رو در عنصری قرار میده که ايندکس آن عنصر(1,2,3) هست. آرايه‌های‌ چند بعدی مثل آرايه‌های يک بعدی به توابع فرستاده میشن با اين تفاوت که هنگام اعلان و تعريف تابع مربوط بهش، بايد تعداد عناصر بُعد دوم تا بُعد آخر حتما گفته بشه.

دستور ;int a[5] آرايه‌ای با پنج عنصر از نوع int تعريف میکنه. اين يک آرايه يک بعدی محسوب میشه.

دستور ;int a[3][5] آرايه‌ای با سه عنصر تعريف میکنه که هر عنصر، خود يک آرايه پنج عنصری از نوع int هست. اين يک آرايه دو بعدی هست که در مجموع پانزده عضو داره.

دستور ;int a[2][3][5] آرايه‌ای با دو عنصر تعريف میکنه که هر عنصر، سه آرايه هست که هر آرايه پنج عضو از نوع int داره. اين يک آرايه سه بعدی هست که در مجموع سی عضو داره.

مثال‌: نوشتن و خواندن يك آرايه دو بعدی

برنامه‌ی زير نشان میده که يک آرايه دوبعدی چطور پردازش میشه:

void read(int a[][5]);

void print(int a[][5]);

int main()

{

void read(int a[][5])

{ cout << “Enter 15 integers, 5 per row:\n”;

for (int i=0; i<3; i++)

{ cout << “ROW ” << i << “: “;

for (int j=0; j<5; j++)

ci

void read(int a[][5])

{ cout << “Enter 15 integers, 5 per row:\n”;

for (int i=0; i<3; i++)

{ cout << “ROW ” << i << “: “;

for (int j=0; j<5; j++)

cin >> a[i][j];

}

void print(const int a[][5])

{ for (int i=0; i<3; i++)

{ for (int j=0; j<5; j++)

cout << ” ” << a[i][j];

cout << endl;

}

}

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

مثال‌: پردازش يك آرايه دوبعدی از نمرات امتحانی

const NUM_STUDENTS = 3;

const NUM_QUIZZES = 5;

typedef int Score[NUM_STUDENTS][NUM_QUIZZES];

void read(Score);

void printQuizAverages(Score);

void printClassAverages(Score);

int main()

{ Score score;

cout << “Enter ” << NUM_QUIZZES

<< ” quiz scores for each student:\n”;

read(score);

cout << “The quiz averages are:\n”;

printQuizAverages(score);

cout << “The class averages are:\n”;

printClassAverages(score);}

void read(Score score)

{ for (int s=0; s<NUM_STUDENTS; s++)

{ cout << “Student ” << s << “: “;

for(int q=0; q<NUM_QUIZZES; q++)

cin >> score[s][q];

}

}

void printQuizAverages(Score score)

{ for (int s=0; s<NUM_STUDENTS; s++)

{ float sum = 0.0;

for (int q=0; q<NUM_QUIZZES; q++)

sum += score[s][q];

cout << “\tStudent ” << s << “: ” << sum/NUM_QUIZZES

<< endl;

}}

void printClassAverages(Score score)

{ for (int q=0; q<NUM_QUIZZES; q++)

{ float sum = 0.0;

for (int s=0; s<NUM_STUDENTS; s++)

sum += score[s][q];

cout << “\tQuiz ” << q << “: ” << sum/NUM_STUDENTS << endl;

}

}

در برنامه بالا با استفاده از دستور typedef برای آرايه‌های دوبعدی 3*5 نام مستعار Score  انتخاب شده. اين باعث میشه که توابع خواناتر باشن. داخل هر تابع از دو حلقه تودرتو استفاده شده که حلقه بيرونی، بعد اول رو پيمايش می‌کنه و حلقه درونی بعد دوم رو پيمايش میکنه.

تابع ()printQuizAverages ميانگين‌ هر سطر از نمرات رو محاسبه و چاپ میکنه و تابع ()printClassAverages  ميانگين هر ستون از نمره‌ها رو چاپ میكنه.

مثال‌: پردازش يك آرايه سه بعدی اين‌ برنامه‌ تعداد صفرها رو در يك آرايه سه بعدی می‌شماره:

int numZeros(int a[][4][3], int n1, int n2, int n3);

int main()

{ int a[2][4][3]={{{5,0,2}, {0,0,9},{4,1,0},{7,7,7} }, { {3,0,0}, {8,5,0}, {0,0,0}, {2,0,9} } };

cout << “This array has ” << numZeros(a,2,4,3)

<< ” zeros:\n”;

}

int numZeros(int a[][4][3], int n1, int n2, int n3)

{ int count = 0;

for (int i = 0; i < n1; i++)

for (int j = 0; j < n2; j++)

for (int k = 0; k < n3; k++)

if (a[i][j][k] == 0) ++count;

return count;

}

اين قالب مقداردهی به خوبی نشان میده که آرايه گفته شده يک آرايه دو عنصری هست  که هر عنصر، خود يک آرايه چهار عضویه که هر عضو شامل آرايه‌ای سه عنصری هست. پس اين آرايه در مجموع 24 عنصر داره. آرايه گفته شده رو به این دو شکل زیر هم می‌تونيم مقداردهی کنيم:

• int a[2][4][3]={5,0,2,0,0,9,4,1,0,7,7,7,3,0,0,8,5,0,0,0,0,2,0,9};
• int a[2][4][3] = {{5,0,2,0,0,9,4,1,0,7,7,7},{3,0,0,8,5,0,0,0,0,2,0,9}};

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