آموزش ++C – آرایه

۲ دیدگاه

تا اینجا با مسائلی روبرو بودیم که در آن نیاز به ذخیره حداکثر دو یا سه مقدار داشتیم، بنابراین به تعداد محدودی متغیر نیاز داشتیم. اما مساله ای را در نظر بگیرید که بخواهید ۱۰۰۰ عدد را ذخیره کنید. قطعا استفاده از ۱۰۰۰ متغیر ایده جالبی نیست. اینجاست که باید با مفهوم آرایه آشنا شوید. در ریاضیات، زمانی که متغیرها زیاد باشد از اندیس استفاده می‌کنند. مثلا x۱ و x۲ و … و xn؛ یعنی n متغیر.

در برنامه نویسی هم دقیقا از همین ایده استفاده می‌شود. فقط چون نمی‌توانیم اندیس را مانند دست‌خط زیر متغیر بنویسیم و بر روی صفحه کلید، کلیدی برای این کار تعریف نشده است از [ ] استفاده می‌کنیم. یعنی x[1] و x[2] و …و x[n]. در مثال ساده زیر مفهوم آرایه را بیشتر توضیح میدیم:


مثال ۱: برنامه ای بنویسید که ۵۰ عدد از ورودی دریافت کند. ابتدا اعداد زوج و سپس اعداد فرد را چاپ کند

توضیح کد:

خط ۴: در این دستور آرایه A تعریف شده است. تفاوت تعریف آرایه و تعریف متغیر در مشخص کردن اندازه آرایه است. در این خط آرایه ای به طول ۵۰ و از نوع int تعریف شده است.

خط ۷ و ۸: در این دو خط آرایه A از ورودی به این صورت دریافت می‌شود: به ازای i=0 وارد حلقه تکرار می‌شود و عددی که دریافت می‌شود در خانه صفر آرایه A (یا همان A[0]) ذخیره می‌شود سپس یک واحد به i اضافه می‌شود و اینبار عددی که از ورودی خوانده می‌شود در خانه یک آرایه (یا همان A[0]) ذخیره می‌شود و به همین ترتیب همه عناصر آرایه پر می شود.

نکته ۱: خانه های آرایه از صفر شماره گذاری می‌شوند. بنابراین اگر یک آرایه ۵۰ تایی داشته باشیم خانه های آن از صفر تا ۴۹ شماره گذاری می‌شوند.

در خط ۷ و ۸ برنامه، اصطلاحا این گونه می‌گوییم: آرایه از ابتدا تا انتها پیمایش می‌شود و یکی یکی خانه های آرایه را میخواند. به همین صورت می‌توانیم بگوییم که در خط ۱۰ تا ۱۲ آرایه از ابتدا تا انتها پیمایش می‌شود و اعداد زوج آرایه چاپ می‌شود و در ادامه و در خط ۱۴ تا ۱۶ آرایه از ابتدا تا انتها پیمایش می‌شود و اعداد فرد آرایه چاپ می‌شود.

مثال ۲: برنامه‌ای بنویسید که که ورودی یک آرایه را دریافت کند و واریانس اعداد آرایه را محاسبه کند

برای محاسبه واریانس اعداد X۱  و X۲ و … و Xn از فرمول زیر استفاده می‌کنیم:

که

برای نوشتن این برنامه به سه پیمایش نیاز داریم. یکی برای دریافت آرایه، یکی برای محاسبه میانگین و دیگری برای محاسبه واریانس:

توضیح کد:

خط ۱۶ و ۱۷: در این دو خط مجموع آرایه محاسبه شده است و در ادامه میانگین این اعداد در mu ذخیره شده. نکته قابل توجه در این مثال استفاده از عملگر =+ است. این عمگر به معنی این است که عبارت سمت راست را به متغیر سمت چپ اضافه کن. بنابراین در خط ۱۷ مقدار A[i] به sum اضافه می‌شود.

خط ۲۳ و ۲۴: در این دو خط فرمول واریانس محاسبه می‌شود. در خط ۲۴ از تابع pow یا همان تابع توان استفاده شده است که قبلا در مورد این تابع صحبت شده است. فقط یادآوری می‌کنیم که برای استفاده از این تابع باید فایل سرآیند cmath را به برنامه اضافه کنید.

در مثال ۴ نحوه استفاده از const توضیح داده شده است.

مثال ۳: برنامه‌ای بنویسید که جملات اول تا ۵۰ام دنباله فیبوناچی را در یک آرایه محاسبه کند.

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

اگر این کد را اجرا کنید خواهید دید که ازاعداد ۴۷ به بعد عدد منفی هم در لیست ظاهر می‌شود. برای دانستن علت این موضوع overflow را درگوگل سرچ کنید!

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

توضیح کد:

در خط ۵ برنامه از متغیر n و از جنس const استفاده شده است. این متغیر به چه معناست و چرا به آن نیاز داریم؟ در این مثال ما به چهار پیمایش آرایه نیاز داریم. و در همه این پیمایشها باید آرایه را تا خانه آخر پیمایش کنیم. اگر ما از متغیر n استفاده نمیکردیم باید به جای همه nها عدد ۱۰ قرار میدادیم. حال فرض کنید تصمیم گرفتید که آرایه‌تان را به ۱۰۰ خانه تغییر دهید. باید همه اعداد ۱۰ در کدتان را به ۱۰۰ تغییر دهید. علاوه بر اینکه دردسر این کار زیاد است، ممکن است یکی از ده ها را فراموش کنید به صد تغییر دهید و طبیعتا برنامه به درستی کار نمی‌کند. از طرف دیگر کامپایلر ++c شما را مجبور میکند که در حین تعریف آرایه اندازه آن را به صورت ثابت و const تعریف کنید. بنابراین باید متغیر n از نوع const تعریف شود.

مثال ۵: برنامه‌ای بنویسید که از ۱۰۰ عدد دریافت کند و در آرایه قرار دهد. سپس بزرگترین عدد را چاپ کند.

این مثال در مبحث ساختار تکرار بدون استفاده از آرایه پیاده‌سازی شد. برای پیاده سازی با آرایه به دو پیمایش نیاز داریم: یکی برای خواندن آرایه و دیگری برای پیدا کردن ماکزیمم.

توضیح کد:

در خط ۱۲ و ۱۳ آرایه از ورودی دریافت می‌شود . در خط ۱۵ فرض میکنیم عدد اول بزرگترین عدد است و در ساختار تکرار (خط ۱۷ تا ۱۹) از خانه دوم (i=2) تا خانه آخر یکی یکی خانه های آرایه را پیمایش می‌کنیم و تک تک خانه‌ها را با max مقایسه می‌کنیم. چنانچه بزرگتر بود آن را در max ذخیره می‌کنیم.

در روش بالا بزرگترین خانه آرایه چاپ می‌شود، اما فرض کنید علاوه بر بزرگترین عدد به اندیس خانه بزرگترین عدد هم نیاز داشته باشیم. یعنی مثلا در انتها مشخص شود که عدد ۱۵۸ که در خانه ۷ام وجود دارد بزرگترین عدد آرایه است. برای این مساله کد زیر را پیاده سازی می‌کنیم:

توضیح کد:

تفاوت این روش با روش قبل در استفاده از متغیر idx به جای max است. در مثال قبل در max بزرگترین عدد ذخیره می‌شد و در این مثال در idx اندیس (خانه) بزرگترین عدد ذخیره می‌شود. به همین خاطر است که در خط ۱۵ idx را با صفر مقدار دهی کردیم که به این معنی است که فرض میکنیم که بزرگترین عدد در خانه صفرم است. ادامه کد نیز با توضیحات ارائه شده قابل فهم است

جستجو در آرایه

یکی از مسائلی که در برنامه نویسی حائز اهمیت است جستجوی یک عدد در آرایه است. جستجو در آرایه به دو صورت امکان‌پذیر است: ترتیبی و دودویی. در جستجوی ترتیبی همانطور که از اسمش پیداست باید عدد مورد جستجو را به ترتیب از اول تا آخر با تک تک اعداد مقایسه کرد. اما در جستجوی دودویی که در ادامه به صورت کامل توضیح داده خواهد شد سرعت جستجو به مراتب از جستجوی ترتیبی بیشتر است. این نکته نیز قابل ذکر است که جستجوی دودویی بر روی آرایه مرتب (چه به صورت صعودی مرتب و چه به صورت نزولی مرتب) صورت میگیرد و در جستجوی ترتیبی شرط مرتب بودن آرایه مهم نیست.

مثال ۶ – برنامه‌ای بنویسید که یک آرایه از ورودی دریافت کند، سپس عددی از کاربر دریافت کند و آن عدد را در آرایه جستجو کند.

توضیح کد:

در این برنامه هم از متغیر flag استفاده شده است. با این تفاوت که فرض را بر این گذاشتیم که عدد در آرایه وجود ندارد (بنابراین flag را برابر false قرار داده‌ایم) و در پیمایش خط ۱۷ چنانچه x را پیدا کردیم flag را برابر true قرار می‌دهیم و از ساختار تکرار خارج می‌شویم.

نکته: متغیر flag از نوع bool است. بنابراین مقدار این متغیر یا true است یا false. پس در خط ۲۳ شرط if(flag) معادل این دستور خواهد بود if(flag == true)

مثال ۷ – برنامه ای بنویسید که یک آرایه مرتب از ورودی دریافت کند و سپس عدد دیگری از کاربر دریافت کند و آن عدد را در آرایه به صورت دودویی جستجو کند

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

  1. x با عنصر میانی آرایه مقایسه می‌شود.
  2. اگر x با عنصر میانی آرایه یکی بود،یعنی x در آرایه وجود دارد.
  3. در غیر این صورت، اگر x بزرگ‌تر از عنصر میانی بود، امکان دارد x در نیمه سمت راست آرایه، پس از عنصر میانی، قرار داشته باشد (شایان توجه است که همانطور که پیش‌تر اشاره شد، آرایه مرتب شده است. پس در این حالت، نیمه‌ای با مقادیر بزرگ‌تر برای ادامه جستجو گزینش می‌شود).
  4. در غیر این صورت، اگر x از عنصر میانی آرایه کوچک‌تر باشد، آرایه به دو نیمه شکسته شده و جستجو در نیمه سمت چپ (با مقادیر کوچک‌تر از میانه)، ادامه پیدا می‌کند.

در تصویر متحرک زیر طریقه جستجوی عدد ۳۷ در یک آرایه مرتب به دو صورت ترتیبی و دودویی نشان داده می‌شود. همانطور که می‌بینید روش دودویی به مراتب سریعتر است.

در این کد برای پیدا کردن عنصر میانه نیاز به اندیس ابتدا و انتهای آرایه داریم. به همین دلیل در خط ۱۷ و ۱۸ low و high با اندیس صفر و n-1 مقداردهی می‌شود. در ساختار تکرار در هر مرحله میانگین low و high را در اندیس mid ذخیره میکنیم. (خط ۲۲) مثلا در تصویر بالا ابتدا mid برابر ۸ خواهد شد (زیرا high = 16 و low = 0 است.) در دستور if (خط ۲۴) با یک مقایسه ساده میخواهیم بدانیم که آیا به عدد مورد نظر رسیده ایم یا نه. در مثال بالا ما به دنبال عدد ۳۷ هستیم و عنصر mid ما برابر ۲۳ است. از آنجایی که ۳۷ از ۲۳ بزرگتر است پس باید در نیمه سمت راست آرایه به دنبال عدد بگردیم. پس مقدار شرط خط ۲۷ برابر true می‌شود و دستور خط ۲۸ اجرا می‌شود. بنابراین مقدار low = 9 خواهد شد و همچنان high=16 خواهد بود . پس در دور بعدی تکرار mid = (16 + 9)/2 یا همان ۱۲ خواهد شد. و این دستورات ادامه پیدا خواهد کرد.

مرتب سازی

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

مثال ۸: برنامه ای بنویسید که یک آرایه از ورودی دریافت کند و به روش حبابی آرایه را به صورت صعودی مرتب کند.

برای توضیح این روش فرض کنید آرایه [۲ ۱ ۳ ۴ ۵] را داریم و میخواهیم این آرایه را مرتب کنیم. ایده اصلی روش حبابی و انتخابی این است که در هر دو روش در هر پیمایش بزرگترین عنصر آرایه را به سمت راست آرایه شیفت میدهیم. تفاوت این دو روش در نحوه پیاده سازی این ایده است. روش حبابی را قدم به قدم روی این آرایه توضیح می‌دهم:

۱- ابتدا، دو عنصر اول آرایه با یکدیگر مقایسه می‌شوند و با توجه به آنکه ۵ از ۴ بزرگتر است (۴<۵)، این دو عنصر با یکدیگر جا به جا می‌شوند:

[۲ ۱ ۳ ۵ ۴] <– [2 1 3 4 5]

۲- در اینجا، عناصر دوم و سوم آرایه مقایسه می‌شوند و با توجه به اینکه ۵ از ۳ بزرگ‌تر است (۳<۵)، این دو عنصر با یکدیگر جا به جا می‌شوند:

[۲ ۱ ۵ ۳ ۴] <– [2 1 3 5 4]

۳- اکنون، عنصر سوم و چهارم آرایه مقایسه می‌شوند و با توجه به اینکه ۱ از ۵ کوچک‌تر است (۱<۵)، این دو عنصر با یکدیگر جا به جا می‌شوند:

[۲ ۵ ۱ ۳ ۴] <– [2 1 5 3 4]

۴- و در مرحله آخرِ پبمایش اول ۵ با ۲ مقایسه می‌شود و چون ۵ از ۲ بزرگتر است جای این دو عنصر با هم عوض می‌شود.

[۵ ۲ ۱ ۳ ۴] <– [2 5 1 3 4]

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

در ادامه کد این برنامه را با هم بررسی میکنیم:

توضیح کد:

در خط ۱۲ و ۱۳ آرایه را از ورودی دریافت می‌کنیم.

قبل از توضیح ادامه کد باید به این نکته اشاره کنیم که اگر آرایه n عنصر داشته باشد (یعنی خانه های آرایه از صفر تا ۱-n شماره گذاری شده باشند) در پیمایش اول باید آرایه را تا ۲-n پیمایش کنیم. زیرا در هر دور تکرار باید خانه iام را با خانه بعدی یعنی خانه ۱+iام مقایسه کنیم. پس حداکثر تا خانه ۲-n می‌توانیم حرکت کنیم زیرا به ازای مقدار i=n-2 خانه بعدی که قرار است با آن مقایسه شود ۱-n خواهد شد که آخرین خانه آرایه است

در خط ۱۵ تا ۲۱ با حلقه for تو در تو روبرو هستیم! اول اینکه چرا به حلقه for تو در تو نیاز داریم؟ اگر یک بار دیگر بخواهیم الگوریتم را به صورت دقیق‌تر با هم مرور کنیم الگوریتم حبابی به این صورت است:
در پیمایش اول، آرایه از خانه صفر تا ۲-n پیمایش می‌شود و در انتهای این پیمایش بزرگترین عدد به خانه آخر فرستاده می‌شود.
در پیمایش دوم، آرایه از خانه صفر تا ۳-n پیمایش می‌شود و در انتهای این پیمایش بزرگترین عدد به خانه یکی مانده به آخر فرستاده می‌شود.
در پیمایش سوم، آرایه از خانه صفر تا ۴-n پیمایش می‌شود و در انتهای این پیمایش بزرگترین عدد به خانه دو تا مانده به آخر فرستاده می‌شود.
.
.
.

برای پیاده‌سازی چنین پیمایشهایی باید از حلقه for تو در تو استفاده کرد. با هم خط ۱۵ تا ۲۱ را بررسی میکنیم:
در خط ۱۵ به ازای j=n-2 وارد حلقه for میشویم در حلقه for دوم باید از i=0 تا i<=j حرکت کنیم. از آنجایی که j=n-2 است پس در حلقه for دوم i از صفر تا n-2 حرکت می‌کند و در هر دور تکرار خانه i را با خانه بعدی یعنی i+1 مقایسه می‌کند. چنانچه خانه i از i+1 بزرگتر باشد با استفاده از متغیر temp جای این دو متغیر با هم عوض می‌شود. وقتی حلقه for دوم تمام شد در حلقه for اول یکی از j کم می‌‌شود و j برابر n-3 می‌شود و اینبار به ازای j=n-3 وارد for دوم می‌شویم. در حلقه for دوم اینبار i از صفر تا n-3 حرکت می‌کند و آرایه به این صورت پیمایش می‌شود….
این دستورات تا زمانی که j>0 است ادامه پیدا خواهد کرد.

مثال ۹: برنامه ای بنویسید که یک آرایه از ورودی دریافت کند و به روش انتخابی آرایه را به صورت صعودی مرتب کند.

در روش حبابی در هر مرحله بزرگترین عدد را به انتهای آرایه میفرستادیم و در این مثال در هر مرحله کوچکترین عدد را به ابتدای آرایه میفرستیم. توجه داشته باشید که هیچ تفاوتی بین این دو ایده نیست و صرفا برای تفاوت در پیاده سازی این دو روش این کار را انجام میدهیم. شما می‎‌توانید روش مرتب سازی انتخابی بنویسید که در هر مرحله بزرگترین عدد را به انتهای آرایه بفرستد!

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

آرایه [۲ ۱ ۴ ۳ ۵] را در نظر بگیرید. روش انتخابی را قدم به قدم و با فرض n=5 توضیح می‌دهیم:

۱- در پیمایش اول از خانه صفرم تا خانه چهارم حرکت می‌کنیم، اندیس کوچکترین عدد آرایه را پیدا میکنیم (idx=3 می‌شود به این معنی کوچکترین عدد در خانه سوم است که عدد یک می‌شود) و جای خانه صفر و ۳ را باهم عوض می‌کنیم:

[۲ ۵ ۴ ۳ ۱] <– [2 1 4 3 5]

۲- در پیمایش دوم از خانه ۱ تا خانه چهارم حرکت می‌کنیم (توجه داشته باشید کوچکترین عدد در خانه صفرم قرار گرفته و دیگر نیازی نیست در پیمایش دیده شود) اندیس کوچکترین عدد آرایه را پیدا میکنیم (که در این پیمایش idx=4 خواهد شد) و جای خانه ۱ و ۴ را باهم عوض میکنم:

[۳ ۵ ۴ ۲ ۱] <– [2 5 4 3 1]

۳- در پیمایش سوم از خانه ۲ تا خانه ۴ حرکت می‌کنیم. idx = 4 خواهد شد و جای خانه ۲ و ۴ با هم عوض می‌شود.

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

در ادامه کد مربوط به این روش را می‌بینید:

توضیح کد:

قسمت اصلی این کد که نیاز به توضیح دارد خط ۱۷ تا ۲۷ است. در حلقه for اول i از صفر تا n حرکت می‌کند. به ازای i=0 وارد دستورات می‌شود و در خط ۱۸ idx=0 می‌شود به این معنی که فرض میکنیم که کوچکترین عدد در خانه صفر است. در حلقه for دوم j از یک تا آخر حرکت میکند و و با مقایسه ای که در خط ۲۰ انجام می‌دهد اندیس کوچکترین عدد پیدا می‌شود و در خط ۲۴ تا ۲۶ جای A[0] و A[idx] با هم عوض می‌شود. بنابراین در پیمایش اول کوچکترین عدد در خانه صفر قرار می‌گیرد. در پیمایش بعدی i=1 میشود و به همان ترتیبی که گفت کوچکترین عنصر بعدی آرایه پیدا می‌شود و در خانه یک قرار می‌گیرد و این ترتیب ادامه پیدا می‌کند…

در این نوشته سعی شد مبحث آرایه ها که پیچیدگی بیشتری نسبت به آموزشهای قبلی داشت توضیح داده شود. چنانچه در فهم مثالها مشکل داشتید در قسمت نظرات سوالاتتان را بپرسید

  • نویسنده
    حمید جهانگیری
  • تعداد بازدید
    2,670
۲دیدگاه فرستاده شده است.
شما هم دیدگاه خود را بنویسید
نوشته‌های ویژه
اخبار ویژه

با عضویت در خبرنامه، تازه‌ترین نوشته‌های وبلاگ را در ایمیل‌تان دریافت کنید.
برای عضویت نشانی ایمیل خود را وارد کرده و بر روی دکمه عضویت کلیک نمایید.