در این بخش، در مورد آرایه ها در ++C صحبت خواهیم کرد. در این جلسه، به توضیح موارد مختلفی خواهیم پرداخت. ابتدا به علت استفاده از آرایهها در برنامهها پرداخته میشود و سپس آرایههای یکبعدی و چندبعدی معرفی خواهند شد. بعد از آن، مفهوم ایندکس و خطای اثر همسایگی بررسی خواهد شد. در ادامه، نحوه ارسال آرایهها به توابع توضیح داده میشود. همچنین، روشهای جستجوی خطی و جستجوی دودویی به طور کامل توضیح داده خواهند شد. در نهایت، مرتبسازی حبابی به عنوان یکی از الگوریتمهای مرتبسازی معرفی و بررسی خواهد شد. تمامی این مباحث بهصورت کامل و همراه با مثالهای عملی و برنامهنویسی آنلاین ارائه خواهند شد.
مقدمه
در برنامههایی که دادههای فراوانی را پردازش میکنند استفاده از متغیرهای معمولی کار عاقلانهای نیست زیرا در بسیاری از این برنامهها پردازش دستهای صورت میگیرد به این معنی که مجموعهای از دادههای مرتبط با هم در حافظه قرار داده میشود و پس از پردازش، کل این مجموعه از حافظه خارج میشود و مجموعه بعدی در حافظه بارگذاری میشود.
اگر قرار باشد برای این کار از متغیرهای معمولی استفاده شود بیشتر وقت برنامهنویس صرف پر و خالی کردن انبوهی از متغیرها میشود. به همین دلیل در بیشتر زبانهای برنامهنویسی آرایه ها تدارک دیده شدهاند. آرایه را میتوان متغیری تصور کرد که یک نام دارد ولی چندین مقدار را به طور همزمان نگهداری مینماید.
یک آرایه، یک زنجیره از متغیرهایی است که همه از یک نوع هستند. به این متغیرها اعضای آرایه میگویند. هر عضو آرایه با یک شماره مشخص میشود که به این شماره ایندکس index یا زیرنویس میگویند. عناصر یک آرایه در خانههای پشت سر هم در حافظه ذخیره میشوند. به این ترتیب آرایه را میتوان بخشی از حافظه تصور کرد که این بخش خود به قسمتهای مساوی تقسیم شده و هر قسمت به یک عنصر تعلق دارد. شکل زیر آرایه a که پنج عنصر دارد را نشان میدهد. عنصر [a[0 حاوی مقدار 17.5 و عنصر [a[1 حاوی 19.0 و عنصر [a[4 حاوی مقدار 18.0 است.
| 4 | 3 | 2 | 1 | 0 |
| 18.00 | 15.00 | 16.75 | 19.00 | 17.50 |
پردازش آرایه ها در ++C
آرایه ها را میتوان مثل متغیرهای معمولی تعریف و استفاده کرد. با این تفاوت که آرایه یک متغیر مرکب است و برای دستیابی به هر یک از خانههای آن باید از ایندکس استفاده نمود.
- مثال: دستیابی مستقیم به عناصر آرایه برنامه ساده زیر یک آرایه سه عنصری را تعریف میکند و سپس مقادیری را در آن قرار داده و سرانجام این مقادیر را چاپ میکند.
#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
در ++C میتوانیم یک آرایه را با استفاده از فهرست مقداردهی، اعلان و مقدارگذاری کنیم:
float a[] = {22.2,44.4,66.6};
به این ترتیب مقادیر داخل فهرست به همان ترتیبی که چیده شدهاند درون عناصر آرایه قرار میگیرند. اندازه آرایه نیز برابر با تعداد عناصر موجود در فهرست خواهد بود. پس همین خط مختصر، آرایهای از نوع float و با نام a و با تعداد سه عنصر اعلان کرده و هر سه عنصر را با مقدارهای درون فهرست، مقداردهی میکند.
- مثال: مقداردهی آرایه ها در ++C با استفاده از فهرست مقداردهی برنامه زير، آرايه 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;
}
a[0] = 22.2 a[1] = 44.4 a[2] = 66.6
هنگام استفاده از فهرست مقداردهی برای اعلان آرايه، میتوانيم تعداد عناصر آرايه را هم به طور صريح ذکر کنيم. در اين صورت اگر تعداد عناصر ذکر شده از تعداد عناصر موجود در فهرست مقداردهی بيشتر باشد، خانههای بعدی با مقدار صفر پر میشوند:
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;
}
a[0] = 6.01838e-39 a[1] = 9.36651e-39 a[2] = 6.00363e-39 a[3] = 0
آرايهها را میتوان با استفاده از عملگر جايگزينی مقداردهی کرد اما نمیتوان مقدار آنها را به يکديگر تخصيص داد:
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 وجود ندارد. مثال بعدی از آرایه ها در ++C نشان میدهد که ايندکس يک آرايه هنگام دستيابی میتواند بيشتر از عناصر تعريف شده برای آن باشد و باز هم بدون اين که خطایی گرفته شود، برنامه ادامه يابد.
- مثال: تجاوز ايندکس آرایه ها در ++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;
}
a[0] = 33.3 a[1] = 44.4 a[2] = 55.5 a[3] = 66.6 a[4] = 5.60519e-45 a[5] = 6.01888e-39
آرايهای که در اين برنامه تعريف شده، چهار عنصر دارد ولی تلاش میشود به هفت عنصر دستيابی شود. سه مقدار آخر واقعا جزو آرايه نيستند و فقط سلولهای از حافظهاند که دقيقا بعد از عنصر چهارم آرايه قرار گرفتهاند. اين سلولها دارای مقدار زباله هستند.
- مثال: اثر همسايگی
برنامه زير از ايندکس خارج از محدوده استفاده میکند و اين باعث میشود که مقدار يک متغير به طور ناخواسته تغيير کند:
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 را اعلان میکند دو چيز را به کامپايلر میگويد:
1- اين که نام آرايه a است.
2- عناصر آرايه از نوع 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;
}
در ++C، فهرست پارامتر تابع فوق به شکل (int a[], int n) نوشته شده است، به این معنا که این تابع یک آرایه از نوع int و یک متغیر از نوع int دریافت میکند. به اعلان این تابع در بالای تابع main() نگاه کنید؛ نام پارامترها حذف شده است. هنگام فراخوانی تابع نیز از عبارت sum(a, size) استفاده شده که فقط نام آرایه به تابع ارسال شده است. در واقع، نام آرایه نشانی اولین عنصر آن است (یعنی a[0]). این ویژگی یکی از خصوصیات نحوهی کار با آرایه ها در ++C است، که در آن آرایه هنگام ارسال به تابع به اشارهگر (pointer) تبدیل میشود.
تابع از اين نشانی برای دستيابی به عناصر آرايه استفاده میکند. همچنين تابع میتواند با استفاده از اين نشانی، محتويات عناصر آرايه را دستکاری کند. پس ارسال آرايه به تابع شبيه ارسال متغير به طريق ارجاع است. به مثال بعدی دقت کنيد.
- مثال: توابع ورودی و خروجی برای يک آرايه
در اين برنامه از تابع ()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<n; i++)
cout << a[i] << " ";
}
چون n يک متغير است، برای اين که تابع ()read بتواند مقدار آن را تغيير دهد اين متغير بايد به شکل ارجاع ارسال شود. همچنين برای اين که تابع مذکور بتواند مقادير داخل آرايه a را تغيير دهد، آرايه نيز بايد به طريق ارجاع ارسال شود، اما ارجاع آرايهها کمی متفاوت است.
در ++C توابع قادر نيستند تعداد عناصر آرایهی ارسالی را تشخيص دهند. بنابراين به منظور ارسال آرايهها به تابع از سه مشخصه استفاده میشود:
- آدرس اولين خانهی آرايه
- تعداد عناصر آرايه
- نوع عناصر آرايه
تابع با استفاده از اين سه عنصر میتواند به تک تک اعضای آرايه دستيابی کند. آدرس اولين خانهی آرايه، همان نام آرايه است. پس وقتی نام آرايه را به تابع بفرستيم آدرس اولين خانه را به تابع فرستادهايم. نوع آرايه نيز در تعريف تابع اعلان میشود. بنابراين با اين دو مقدار، تابع میتواند به آرايه دسترسی داشته باشد.
- مثال: آدرس اولين خانه آرايه و مقدار درون آن
برنامه زير، آدرس ذخيره شده در نام آرايه و مقدار موجود در آن خانه را چاپ میکند:
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] مقدار اولين عنصر را دارد.
ارتباط الگوریتمها با آرایه ها در ++C
در زبان ++C، آرایهها یکی از سادهترین و پرکاربردترین ساختارهای داده هستند که اغلب در کنار الگوریتمهای پایهای مانند جستجو و مرتبسازی مورد استفاده قرار میگیرند. بسیاری از الگوریتمهای کلاسیک را میتوان بهراحتی روی آرایهها پیادهسازی کرد. در این بخش، چند الگوریتم مهم را که کاربرد گستردهای در کار با آرایهها دارند بررسی میکنیم.
الگوريتم جستجوی خطی
جستجوی خطی (Linear Search) سادهترین روش برای یافتن یک مقدار خاص در آرایه است. در این الگوریتم، از اولین عنصر آرایه شروع میکنیم و هر عنصر را با مقدار مورد نظر مقایسه میکنیم تا زمانی که مقدار مورد نظر پیدا شود یا به انتهای آرایه برسیم. این الگوریتم در مواردی کاربرد دارد که دادهها مرتب نشدهاند یا اندازه آرایه کوچک است.
در ++C، آرایهها بیشتر برای پردازش یک زنجیره از دادهها به کار میروند. در بسیاری از برنامههایی که با آرایه ها در ++C نوشته میشوند، لازم است بررسی کنیم آیا یک مقدار خاص درون آرایه وجود دارد یا نه. سادهترین روش این است که از اولین عنصر آرایه شروع کنیم و یکییکی همه عناصر را بررسی کنیم تا ببینیم مقدار مورد نظر در کدام خانه قرار دارد.
به این روش «جستجوی خطی» گفته میشود، چون دادهها به ترتیب و پشت سر هم بررسی میشوند.
- مثال: جستجوی خطی
برنامه زير تابعی را آزمايش میکند که در اين تابع از روش جستجوی خطی برای يافتن يک مقدار خاص استفاده شده:
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(44,a,7) = 1 index(40,a,7) = 7
تابع index() سه پارامتر دارد:
- پارامتر x مقداری است که قرار است جستجو شود،
- پارامتر a آرايهای است که بايد در آن جستجو صورت گيرد
- و پارامتر n هم ايندکس عنصری است که مقدار مورد نظر در آن پيدا شده است.
در اين تابع با استفاده از حلقه for عناصر آرايه a پيمايش شده و مقدار هر عنصر با x مقايسه میشود. اگر اين مقدار با x برابر باشد، ايندکس آن عنصر بازگردانده شده و تابع خاتمه میيابد. اگر مقدار x در هيچ يک از عناصر آرايه موجود نباشد، مقداری خارج از ايندکس آرايه بازگردانده میشود که به اين معناست که مقدار x در آرايه a موجود نيست.
در اولین اجرای آزمایشی، مشخص شده که مقدار 44 در a[1] واقع است و در اجرای آزمایشی دوم مشخص شده که مقدار 40 در آرايه a موجود نيست (يعنی مقدار 44 در a[7] واقع است و از آنجا که آرايه a فقط تا a[6] عنصر دارد، مقدار 7 نشان میدهد که 40 در آرايه موجود نيست).
مرتبسازی حبابی
«مرتبسازی حبابی» یکی از سادهترین الگوریتمهای مرتبسازی در برنامهنویسی است. این روش معمولاً برای آرایه ها در ++C بهکار میرود و در آن، آرایه چندین بار پیمایش میشود.
در هر بار پیمایش، بزرگترین عنصر موجود به انتهای بخشِ بررسینشده آرایه “حبابوار” حرکت میکند. سپس، در تکرار بعدی، محدودهی مرتبسازی یک خانه کوچکتر میشود تا زمانیکه کل آرایه مرتب شود.
در پايان همهی پويشها، آرايه مرتب شده است.
طريقهی يافتن بزرگترين عنصر و انتقال آن به بالای عناصر ديگر به اين شکل است:
- اولين عنصر آرايه با عنصر دوم مقايسه میشود.
- اگر عنصر اول بزرگتر بود، جای اين دو با هم عوض میشود.
- سپس عنصر دوم با عنصر سوم مقايسه میشود.
- اگر عنصر دوم بزرگتر بود، جای اين دو با هم عوض میشود.
- و به همين ترتيب مقايسه و جابجایی زوجهای همسايه ادامه میيابد تا وقتی به انتهای آرايه رسيديم، بزرگترين عضو آرايه در خانهی انتهایی قرار خواهد گرفت.
در اين حالت محدودهی جستجو يکی کاسته میشود و دوباره زوجهای کناری يکی يکی مقايسه میشوند تا عدد بزرگتر بعدی به مکان بالای محدوده منتقل شود. اين پويش ادامه میيابد تا اين که وقتی محدوده جستجو به عنصر اول محدود شد، آرايه مرتب شده است.
- مثال: مرتبسازی
برنامهی زير تابعی را آزمايش میکند که اين تابع با استفاده از مرتبسازی حبابی يک آرايه را مرتب مینمايد:
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<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 از دو حلقهی تودرتو استفاده میکند.
1- حلقه for داخلي زوجهای همسايه را با هم مقايسه میکند و اگر آنها خارج از ترتيب باشند، جای آن دو را با هم عوض میکند. وقتی for داخلی به پايان رسيد، بزرگترين عنصر موجود در محدودهی فعلی به انتهای آن هدايت شده است.
2-سپس حلقهی for بيرونی محدودهی جستجو را يکی کم میکند و دوباره for داخلی را راه میاندازد تا بزرگترين عنصر بعدی به سمت بالای آرايه هدايت شود.
الگوريتم جستجوی دودویی
جستجوی دودویی (Binary Search) یک الگوریتم سریعتر برای جستجو در آرایههای مرتبشده است. در این روش، عنصر میانی آرایه بررسی میشود. اگر مقدار مورد نظر کوچکتر یا بزرگتر از عنصر میانی باشد، جستجو فقط در نیمهی مربوطه ادامه پیدا میکند.
این فرآیند تا زمانیکه مقدار پیدا شود یا بازه جستجو به صفر برسد ادامه دارد. این الگوریتم بهدلیل پیچیدگی زمانی O(log n) بسیار بهینهتر از جستجوی خطی است، البته تنها زمانی قابل استفاده است که آرایه از پیش مرتب شده باشد.
در روش جستجوی دودویی، وجود یک آرایهی مرتب ضروری است. در هر مرحله از جستجو، بازهی آرایه به دو بخش تقسیم میشود و مقدار مورد نظر با عنصر میانی این بازه مقایسه میگردد.
اگر مقدار مورد نظر از عنصر میانی کوچکتر باشد، جستجو در نیمهی پایینی ادامه مییابد؛ در غیر این صورت، در نیمهی بالایی به جستجو ادامه داده میشود. این فرآیند تا زمانی تکرار میشود که مقدار مورد نظر پیدا شود یا بازهی جستجو به صفر برسد.
در پایان، محدودهی جستجو به تنها یک عنصر میرسد. اگر این عنصر با مقدار مورد نظر برابر باشد، جستجو موفقیتآمیز بوده است. در غیر این صورت، مشخص میشود که مقدار مورد نظر در آرایه ها در ++C وجود ندارد. این روش اگرچه نسبت به جستجوی خطی پیچیدهتر است، اما از نظر زمان اجرا بسیار سریعتر و کارآمدتر عمل میکند؛ بهویژه در آرایه ها در ++C با تعداد زیاد عناصر.
- مثال: جستجوی دودویی
برنامه آزمون زير با برنامهی آزمون مثال يکی است اما تابعی که در زير آمده از روش جستجوی دودویی برای يافتن مقدار درون آرايه استفاده میکند:
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) = 2 index(60,a,7) = 7
برای اين که بفهميم تابع چطور کار میکند، فراخوانی 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 را برمیگرداند یعنی عنصر مورد نظر در آرایه ها در ++C موجود نیست. در تابع فوق هر بار که حلقه تکرار میشود، محدوده جستجو 50% کوچکتر میشود. در آرايه n عنصری، روش جستجوی دودویی حداکثر به مقايسه نياز دارد تا به پاسخ برسد. حال آن که در روش جستجوی خطی به n مقايسه نياز است.
تفاوتهای جستجوی دودویی و خطی
جستجوی دودویی سریعتر از جستجوی خطی است. دومین تفاوت در این است که اگر چند عنصر دارای مقادیر یکسانی باشند، آنگاه جستجوی خطی همیشه کوچکترین ایندکس را برمیگرداند، ولی در مورد جستجوی دودویی نمیتوان گفت که کدام ایندکس بازگردانده میشود.
سومین فرق در این است که جستجوی دودویی فقط روی آرایه ها در ++C مرتب کارایی دارد و اگر آرایهای مرتب نباشد، جستجوی دودویی پاسخ غلط میدهد، ولی جستجوی خطی همیشه پاسخ صحیح خواهد داد.
در زمینه این موضوع، فایل آمادهای در سایت پی استور موجود است و برای آگاهی بیشتر مطالعه نمایید.
- مثال: مشخص کردن اين که آيا آرايه مرتب است يا خير. برنامه زير يک تابع بولی را آزمايش میکند. اين تابع مشخص مینمايد که آيا آرايه داده شده غير نزولی است يا خير.
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;
}
خروجی نمایش داده میشود:
isNondecreasing(a,4) = 1 isNondecreasing(a,7) = 0
اين تابع يک بار کل آرايه را پيمايش کرده و زوجهای 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;
}
خروجی به صورت زیر است:
index(44,a,7) = 2
آرايه []a که در اين برنامه استفاده شده کاملا مرتب نيست اما هفت عنصر اول آن مرتب است. بنابراين در فراخوانیindex(44,a,7) تابع بولی مقدار true را به () assert ارسال میکند و برنامه ادمه میيابد. اما در دومين فراخوانی index(44,a,8) باعث میشود که تابع ()isNondecreasing مقدار false را به تابع ()assert ارسال کند که در اين صورت برنامه متوقف میشود و ويندوز پنجره هشدار مقابل را نمايش میدهد.
استفاده از انواع شمارشی در آرايه
با استفاده از انواع شمارشی نیز میتوان آرایه ها در ++C را پردازش نمود.
- مثال: شمارش با استفاده از روزهای هفته
اين برنامه يک آرايه به نام []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;
}
The high temperature for day 0 was 28.6 The high temperature for day 1 was 29.1 The high temperature for day 2 was 29.9 The high temperature for day 3 was 31.3 The high temperature for day 4 was 30.4 The high temperature for day 5 was 32.0 The high temperature for day 6 was 30.7
به خاطر بياوريد که انواع شمارشی به شکل مقادير عددی ذخيره میشوند. اندازه آرايه، 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 را نشان میدهد. برنامه زير همان برنامه مثال است با اين فرق که از 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 نگاه کنيد:
;[]typedef float Seguence علامت براکتها [] نشان میدهند که هر چيزی که از نوع Sequence تعريف شود، يک آرايه است و عبارت float نيز بيان میکند که اين آرايه از نوع float است.
آرايههای چند بعدی
همه آرایه هایی که در مقاله آرایه ها در ++C تعریف کردیم، یکبعدی و خطی بودند. اما میتوانیم آرایهای تعریف کنیم که هر خانهی آن، خود یک آرایه باشد. به این نوع ساختار، آرایهی چندبعدی گفته میشود.
برای مثال، یک آرایهی دوبعدی، آرایهای است که هر عنصر آن یک آرایهی یکبعدی است. به همین ترتیب، یک آرایهی سهبعدی شامل عناصری است که هرکدام یک آرایهی دوبعدی هستند.
شکل دستيابی به عناصر در آرايههای چند بعدی مانند آرايههای يک بعدی است. مثلا دستور:
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;
}
}
Enter 15 integers, 5 per row:
row 0: 44 77 33 11 44
row 1: 60 50 30 90 70
row 2: 65 25 45 45 55
44 77 33 11 44
60 50 30 90 70
65 25 45 45 55
دقت کنید که در فهرست پارامترهای توابع بالا، بُعد اول نامشخص است اما بُعد دوم مشخص شده. این رفتار از ویژگیهای آرایه ها در ++C است، چرا که در این زبان، آرایهی دوبعدی 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;
}
}
خروجی برنامه :
Enter 5 quiz scores for each student:
student 0: 8 7 9 8 9
student 1: 9 9 9 9 8
student 2: 5 6 7 8 9
The quize averages are:
student 0: 8.2
student 1: 8.8
student 2: 7
The class averages are:
Quiz 0: 7.33333
Quiz 1: 7.33333
Quiz 2: 8.33333
Quiz 3: 8.33333
Quiz 4: 8.66667
در برنامه فوق، با استفاده از دستور typedef برای آرایه های دوبعدی 3×5 نام مستعار Score انتخاب شده است. این شیوه در کار با آرایه ها در ++C رایج است و باعث میشود که توابع خواناتر و سادهتر نوشته شوند. هر تابع از دو حلقهی for تو در تو استفاده کرده که در آن، حلقهی بیرونی بعد اول و حلقهی درونی بعد دوم را پیمایش میکند.
تابع ()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;
}
This array has 11 zeros:
توجه کنيد که آرايه چگونه مقداردهی شده است. اين قالب مقداردهی به خوبی نمايان میکند که آرايه مذکور يک آرايه دو عنصری است که هر عنصر، خود يک آرايه چهار عضوی است که هر عضو شامل آرايهای سه عنصری میباشد. پس اين آرايه در مجموع 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}};
هر سه اين قالبها برای کامپايلر يک مفهوم را دارند، اما با نگاه کردن به دو قالب اخير به سختی میتوان فهميد که کدام عنصر از آرايه، کدام مقدار را خواهد داشت.
سخن پایانی درمورد آرایه ها در ++C
در این بخش آرایه ها را در ++C توضیح دادیم، آرایه های چند بعدی را تعریف کردیم. به توضیح الگوریتم جستجوی دودویی و خطی و به تفاوتهای آنها پرداختیم. امیدواریم این مطالب برای شما مفید باشد. در درس بعدی با مقاله ارجاع ها و اشاره گرها در ++C در خدمت شما خواهیم بود.
اعضای یک ارایه چند نوع متفاوت را میتواند داشته باشد