آموزش سی پلاس پلاس – آرایه ها در ++C
در این بخش در مورد آرایه ها در ++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 میتوانیم یک آرایه را با استفاده از فهرست مقداردهی، اعلان و مقدارگذاری کنیم:
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; }
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 وجود ندارد. مثال بعدی نشان میدهد که ايندکس يک آرايه هنگام دستيابی میتواند بيشتر از عناصر تعريف شده برای آن باشد و باز هم بدون اين که خطایی گرفته شود، برنامه ادامه يابد.
مثال : تجاوز ايندکس آرايه از محدوده تعريف شده برای آن برنامه زير يک خطای زمان اجرا دارد؛ به بخشی از حافظه دستيابی میکند که از محدوده آرايه بيرون است:
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; }
فهرست پارامتر تابع فوق به شکل (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); }
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] مقدار اولين عنصر را دارد.
الگوريتم جستجوی خطی
آرايهها بيشتر برای پردازش يک زنجيره از دادهها به کار میروند.
اغلب لازم است که بررسی شود آيا يک مقدار خاص درون يک آرايه موجود است يا خير. سادهترين راه اين است که از اولين عنصر آرايه شروع کنيم و يکي يکي همه عناصر آرايه را جستجو نماييم تا بفهميم که مقدار مورد نظر در کدام عنصر قرار گرفته. به اين روش «جستجوی خطی» میگویند.
مثال: جستجوی خطی:
برنامه زير تابعی را آزمايش میکند که در اين تابع از روش جستجوی خطی برای يافتن يک مقدار خاص استفاده شده:
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 در آرايه موجود نيست).
مرتبسازی حبابی
«مرتبسازی حبابی» يکی از سادهترين الگوريتمهای مرتبسازی است. در اين روش، آرايه چندين مرتبه پويش میشود و در هر مرتبه بزرگترين عنصر موجود به سمت بالا هدايت میشود و سپس محدودهی مرتبسازی برای مرتبه بعدی يکی کاسته میشود.
در پايان همهی پويشها، آرايه مرتب شده است.
طريقهی يافتن بزرگترين عنصر و انتقال آن به بالای عناصر ديگر به اين شکل است:
- اولين عنصر آرايه با عنصر دوم مقايسه میشود.
- اگر عنصر اول بزرگتر بود، جای اين دو با هم عوض میشود.
- سپس عنصر دوم با عنصر سوم مقايسه میشود.
- اگر عنصر دوم بزرگتر بود، جای اين دو با هم عوض میشود.
- و به همين ترتيب مقايسه و جابجایی زوجهای همسايه ادامه میيابد تا وقتی به انتهای آرايه رسيديم، بزرگترين عضو آرايه در خانهی انتهایی قرار خواهد گرفت.
در اين حالت محدودهی جستجو يکی کاسته میشود و دوباره زوجهای کناری يکی يکی مقايسه میشوند تا عدد بزرگتر بعدی به مکان بالای محدوده منتقل شود. اين پويش ادامه میيابد تا اين که وقتی محدوده جستجو به عنصر اول محدود شد، آرايه مرتب شده است.
مثال: مرتبسازی
برنامهی زير تابعی را آزمايش میکند که اين تابع با استفاده از مرتبسازی حبابی يک آرايه را مرتب مینمايد:
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 داخلی را راه میاندازد تا بزرگترين عنصر بعدی به سمت بالای آرايه هدايت شود.
الگوريتم جستجوی دودویی
در روش جستجوی دودویی به يک آرايهی مرتب نياز است. ü هنگام جستجو آرايه از وسط به دو بخش بالایی و پايينی تقسيم میشود. üمقدار مورد جستجو با آخرين عنصر بخش پايينی مقايسه میشود. ü اگر اين عنصر کوچکتر از مقدار جستجو بود، مورد جستجو در بخش پايينی وجود ندارد و بايد در بخش بالایی به دنبال آن گشت. دوباره بخش بالایی به دو بخش تقسيم میگردد و گامهای بالا تکرار میشود.
سرانجام محدودهی جستجو به يک عنصر محدود میشود که يا آن عنصر با مورد جستجو برابر است و عنصر مذکور يافت شده و يا اين که آن عنصر با مورد جستجو برابر نيست و لذا مورد جستجو در آرايه وجود ندارد. اين روش پيچيدهتر از روش جستجوی خطی است اما در عوض بسيار سريعتر به جواب میرسيم.
مثال: جستجوی دودویی
برنامه آزمون زير با برنامهی آزمون مثال يکی است اما تابعی که در زير آمده از روش جستجوی دودویی برای يافتن مقدار درون آرايه استفاده میکند:
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 را برمیگرداند يعنی عنصر مورد نظر در آرايه موجود نيست. در تابع فوق هر بار که حلقه تکرار میشود، محدوده جستجو 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; }
خروجی نمایش داده میشود:
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 ارسال کند كه در اين صورت برنامه متوقف میشود و ويندوز پنجره هشدار مقابل را نمايش میدهد.
استفاده از انواع شمارشی در آرايه
انواع شمارشی در جلسه دوم توضيح داده شدهاند. با استفاده از انواع شمارشی نيز میتوان آرايهها را پردازش نمود.
مثال: شمارش با استفاده از روزهای هفته
اين برنامه يك آرايه به نام []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 است.
آرايههای چند بعدی
همه آرايههايی كه تاکنون تعريف کرديم، يک بعدی هستند، خطی هستند، رشتهای هستند. میتوانيم آرايهای تعريف کنيم که از نوع آرايه باشد، يعنی هر خانه از آن آرايه، خود يک آرايه باشد. به اين قبيل آرايهها، آرايههای چندبعدی میگوييم. يک آرايه دو بعدی آرايهای است که هر خانه از آن، خود يک آرايه يک بعدی باشد. يک آرايه سه بعدی آرايهای است که هر خانه از آن يک آرايه دو بعدی باشد.
شکل دستيابی به عناصر در آرايههای چند بعدی مانند آرايههای يک بعدی است. مثلا دستور:
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
دقت کنيد که در فهرست پارامترهای توابع بالا، بعد اول نامشخص است اما بعد دوم مشخص شده. علت هم اين است که آرايه دو بعدی [][]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 انتخاب شده. اين باعث میشود که توابع خواناتر باشند. هر تابع از دو حلقه 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، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.
سلام
من میخوام یک برنامه بنویسم که اعضای یک آرایه دو بعدی را با هم جمع کنه
باید چه کاری انجام بدم؟
سلام و وقت بخیر
برای این کار باید سطر و ستون دو تا آرایه باهم یکی باشند. ما آرایه [5][5]x و [5][5]y رو در نظر می گیریم. یک آرایه [5][5]z رو هم برای قرار دادن جمع مقادیر ازش استفاده می کنیم. حالا با دو تا حلقه for بصورت زیر اعضای دو آرایه x و y را نظیر به نظیر باهم جمع می کنیم و در درخانه متناظر z قرار می دهیم.
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
z[i][j]=x[i][j]+y[i][j]