در این بخش، در مورد آرایه ها در ++C صحبت خواهیم کرد. در این جلسه، به توضیح موارد مختلفی خواهیم پرداخت. ابتدا به علت استفاده از آرایه‌ها در برنامه‌ها پرداخته میشود و سپس آرایه‌های یک‌بعدی و چندبعدی معرفی خواهند شد. بعد از آن، مفهوم ایندکس و خطای اثر همسایگی بررسی خواهد شد. در ادامه، نحوه ارسال آرایه‌ها به توابع توضیح داده میشود. همچنین، روش‌های جستجوی خطی و جستجوی دودویی به طور کامل توضیح داده خواهند شد. در نهایت، مرتب‌سازی حبابی به عنوان یکی از الگوریتم‌های مرتب‌سازی معرفی و بررسی خواهد شد. تمامی این مباحث به‌صورت کامل و همراه با مثال‌های عملی و برنامه‌نویسی آنلاین ارائه خواهند شد.
مقدمه
در برنامه‌هایی که داده‌های فراوانی را پردازش می‌کنند استفاده از متغیرهای معمولی کار عاقلانه‌ای نیست زیرا در بسیاری از این برنامه‌ها پردازش دسته‌ای صورت می‌گیرد به این معنی که مجموعه‌ای از داده‌های مرتبط با هم در حافظه قرار داده میشود و پس از پردازش، کل این مجموعه از حافظه خارج میشود و مجموعه بعدی در حافظه بارگذاری میشود.
اگر قرار باشد برای این کار از متغیرهای معمولی استفاده شود بیشتر وقت برنامه‌نویس صرف پر و خالی کردن انبوهی از متغیرها میشود. به همین دلیل در بیشتر زبان‌های برنامه‌نویسی آرایه ها تدارک دیده شده‌اند. آرایه را میتوان متغیری تصور کرد که یک نام دارد ولی چندین مقدار را به طور هم‌زمان نگهداری می‌نماید.
یک آرایه، یک زنجیره از متغیرهایی است که همه از یک نوع هستند. به این متغیرها اعضای آرایه می‌گویند. هر عضو آرایه با یک شماره مشخص میشود که به این شماره ایندکس index یا زیرنویس می‌گویند. عناصر یک آرایه در خانه‌های پشت سر هم در حافظه ذخیره می‌شوند. به این ترتیب آرایه را میتوان بخشی از حافظه تصور کرد که این بخش خود به قسمت‌های مساوی تقسیم شده و هر قسمت به یک عنصر تعلق دارد. شکل زیر آرایه a که پنج عنصر دارد را نشان می‌دهد. عنصر [a[0 حاوی مقدار ۱۷.۵ و عنصر [a[1 حاوی ۱۹.۰ و عنصر [a[4 حاوی مقدار ۱۸.۰ است.
| ۴ | ۳ | ۲ | ۱ | ۰ |
| ۱۸.۰۰ | ۱۵.۰۰ | ۱۶.۷۵ | ۱۹.۰۰ | ۱۷.۵۰ |
پردازش آرایه ها در ++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 اعلان شده، پس یک سلول چهاربایتی بلافاصله بعد از دوازده بایت آرایه به آن تخصیص مییابد. بنابراین وقتی برنامه تلاش میکند مقدار ۸۸.۸ را در 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;
}
در ++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 موجود نیست.
در اولین اجرای آزمایشی، مشخص شده که مقدار ۴۴ در a[1] واقع است و در اجرای آزمایشی دوم مشخص شده که مقدار ۴۰ در آرایه a موجود نیست (یعنی مقدار ۴۴ در a[7] واقع است و از آن‌جا که آرایه a فقط تا a[6] عنصر دارد، مقدار ۷ نشان می‌دهد که ۴۰ در آرایه موجود نیست).
مرتب‌سازی حبابی
«مرتب‌سازی حبابی» یکی از ساده‌ترین الگوریتم‌های مرتب‌سازی در برنامه‌نویسی است. این روش معمولاً برای آرایه ها در ++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);
}
۵۵.۵, ۲۲.۲, ۹۹.۹, ۶۶.۶, ۴۴.۴, ۸۸.۸, ۳۳.۳, ۷۷.۷ ۲۲.۲, ۳۳.۳, ۴۴.۴, ۵۵.۵, ۶۶.۶, ۷۷.۷, ۸۸.۸, ۹۹.۹
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 داخلی را راه می‌اندازد تا بزرگ‌ترین عنصر بعدی به سمت بالای آرایه هدایت شود.
الگوریتم جستجوی دودویی
جستجوی دودویی (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 مقدار ۳ =۲/(۶+۰) را می‌گیرد. پس عنصر a[i] عنصر وسط آرایه‌ی a[0..6] است. مقدار a[3] برابر با ۵۵ است که از مقدار x بزرگ‌تر است. پس x در نیمه‌ی بالایی نیست و جستجو در نیمه پایینی ادامه مییابد. لذا hi با i-1 یعنی ۲ مقداردهی میشود و حلقه تکرار می‌گردد.
حالا hi=2 و lo=0 است و دوباره عنصر وسط آرایه a[0..2] یعنی a[1] با x مقایسه میشود. a[1] برابر با ۳۳ است که کوچک‌تر از x می‌باشد. پس این دفعه lo برابر با i+1 یعنی ۲ میشود. در سومین دور حلقه، hi=2 و lo=2 است. پس عنصر وسط آرایه a[2..2] که همان a[2] است با x مقایسه میشود. a[2] برابر با ۴۴ است که با x برابر است. پس مقدار ۲ بازگشت داده میشود؛ یعنی 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 است. بنابراین تابع مقدار ۷ را برمی‌گرداند یعنی عنصر مورد نظر در آرایه ها در ++C موجود نیست. در تابع فوق هر بار که حلقه تکرار میشود، محدوده جستجو ۵۰% کوچک‌تر میشود. در آرایه 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 به شکل اعداد ۱ و ۰ در خروجی چاپ می‌شوند زیرا مقادیر بولی در حقیقت به شکل اعداد صحیح در حافظه ذخیره می‌شوند. اگر پیش‌شرط مثال یعنی مرتب بودن آرایه رعایت نشود، جستجوی دودویی پاسخ درستی نمی‌دهد. به این منظور ابتدا باید این پیش‌شرط بررسی شود.
با استفاده از تابع () 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 مقدار صحیح ۶ را دارد و آرایه به هفت عنصر نیازمند است. متغیر 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 عنصر یعنی ۵+۱=۶ عنصر است. در ++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;
مقدار ۹۹ را در عنصری قرار می‌دهد که ایندکس آن عنصر(۱,۲,۳) است. آرایه‌های چند بعدی مثل آرایه‌های یک بعدی به توابع فرستاده می‌شوند با این تفاوت که هنگام اعلان و تعریف تابع مربوطه، باید تعداد عناصر بُعد دوم تا بُعد آخر حتما ذکر شود.
دستور 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
۴۴ ۷۷ ۳۳ ۱۱ ۴۴
۶۰ ۵۰ ۳۰ ۹۰ ۷۰
۶۵ ۲۵ ۴۵ ۴۵ ۵۵
دقت کنید که در فهرست پارامترهای توابع بالا، بُعد اول نامشخص است اما بُعد دوم مشخص شده. این رفتار از ویژگی‌های آرایه ها در ++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 برای آرایه های دوبعدی ۳×۵ نام مستعار 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:
توجه کنید که آرایه چگونه مقداردهی شده است. این قالب مقداردهی به خوبی نمایان میکند که آرایه مذکور یک آرایه دو عنصری است که هر عنصر، خود یک آرایه چهار عضوی است که هر عضو شامل آرایه‌ای سه عنصری می‌باشد. پس این آرایه در مجموع ۲۴ عنصر دارد. آرایه مذکور را به شکل زیر نیز میتوانیم مقداردهی کنیم:
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 در خدمت شما خواهیم بود.
