فصل هشتم
آرایه دوبعدی
در فصل 5 با مفهوم آرایه یک‌بعدی برای نمایش عناصر یک لیست یا دنباله‌ای از مقادیر آشنا شدیم. در بسیاری از مسائل ارتباط با داده‌هایی سروکار داریم که شکل جدولی دارند. به عبارتی داده‌ها را در قالب تعدادی سطر و ستون در خود جا می‌دهند. یکی از پرکاربردترین نمونه‌های آن در مسائل مهندسی، ماتریس‌ها هستند. در این فصل آرایه‌های دوبعدی را مطالعه می‌کنیم. تعریف این نوع آرایه را به آرایه‌های چندبعدی تعمیم می‌دهیم.
آرایه‌های دوبعدی
آرایه دوبعدی برای نمایش عناصر از یک نوع داده که بتوان آن‌ها را به‌صورت جدولی متشکل از تعدادی سطر و ستون نمایش داد، بکار می‌رود. به‌عنوان‌مثال می‌توان صفحه شطرنج یا یک ماتریس3 × 3 و یا لیست نمرات دانشجویان را در دروس مختلف نام برد که عناصر آن‌ها با آرایه‌های دوبعدی قابل‌نمایش است. هر عنصر با دو زیرنویس قابل‌دسترسی است. مثلاً اگر نام دانشجوئی در سطر n ام و نام درس در ستون m ام باشد، می‌توان با این دو عدد صحیح به نمره دانشجو در درس موردنظر دست یافت.
آرایه دوبعدی مجموعه‌ای از عناصر از یک نوع داده، با ساختاری دوبعدی است. هر عنصر با دو زیرنویس قابل‌دسترسی است که هر زیرنویس موقعیت عنصر را در یک بعد نشان می‌دهد.
شکل 8-1 یک آرایه دوبعدی با 100 سطر و 9 ستون را نشان می‌دهد. سطرها با عدد صحیحی از 0 تا 99 ، و ستون‌ها با عدد صحیحی از 0 تا 8 شماره‌گذاری شده‌اند. هر عنصر با یک جفت عدد صحیح (شماره‌های سطر ـ ستون) قابل‌دسترسی هستند.
شکل 8-1 : یک آرایه دوبعدی
تعریف آرایه دوبعدی نظیر تعریف آرایه یک‌بعدی است، با این تفاوت که در اینجا دوبعدی بودن آرایه باید نشان داده شود. چهارچوب دستوری تعریف یک آرایه با بیش از یک بعد با ذکر یک مثال چنین است.
به‌عنوان‌مثال:
در مثال فوق متغیر alpha یک آرایه دوبعدی است که همه عناصر آن از نوع اعشاری هستند. تعریف فوق آرایه‌ای را به شکل 8-1 در حافظه به وجود می‌آورد.
برای دسترسی به عناصر آرایه alpha ، دو عبارت (هریک برای یک بعد) برای تعیین موقعیت عنصر بکار گرفته می‌شود. هریک از عبارات در کروشه‌ای محصور میشوند و بعد از نام آرایه ذکر میشوند:
نظیر آرایه‌های یک‌بعدی حاصل عبارات مربوط به زیرنویس باید یک مقدار صحیح باشد. به مثال‌های زیر توجه کنید. در اینجا تعریف آرایه دوبعدی متشکل از 364 عدد صحیح داده شده است.
می‌توان آرایه hiTemp را به‌عنوان جدولی با 52 سطر و 7 ستون در نظر گرفت. موقعیت‌های موجود در جدول با اعداد صحیح که حداکثر دمای روزانه در یک سال را نشان می‌دهند پر میشوند. هر سطر جدول یکی از 52 هفته سال و هر ستون جدول یکی از 7 روز هفته را نشان می‌دهد. متغیر hiTemp[2][6] عدد صحیحی است که در سطر سوم و ستون هفتم واقع است و حداکثر دمای روز هفتم از هفته سوم سال را نشان می‌دهد. قطعه کد مندرج در شکل 8-2 مقادیر دمای هفته سوم را چاپ می‌کند.
شکل 8-2 : آرایه hiTemp
مشابه آرایه‌های یک‌بعدی، ابعاد آرایه‌های با تعداد ابعاد بالاتر نیز می‌تواند از نوع enum باشد. به مثال زیر توجه کنید. در این مثال احتمال تصادف در جدولی دوبعدی برحسب سازنده خودرو و رنگ خودرو ذخیره می‌شود. نوع هر خانه این جدول، عدد حقیقی است. هریک از زیرنویس‌ها دارای مفهوم هستند.
پردازش آرایه‌های دوبعدی
پردازش داده در یک آرایه دوبعدی به معنی دسترسی به عناصر آرایه در یکی از چهار صورت تصادفی، در راستای سطرها، در راستای ستون‌ها و یا کل آرایه است.
ساده‌ترین راه دسترسی به یک عنصر توسط موقعیت داده‌شده آن است. برای مثال برای یافتن نمره دانشجویی در درس مفروضی و در لیست نمرات (این روش دسترسی را تصادفی می‌نامیم.) کاربر شماره سطری که نام دانشجو در آن واقع است و شماره ستونی که نام درس در آن قرار دارد را به‌عنوان ورودی می‌دهد تا به نمره دسترسی پیدا کند.
حالت‌های متعددی وجود دارند که در آن‌ها انجام یک عمل روی همه عناصر سطر یا ستون خاصی از آرایه موردنظر است. برای مثال آرایه hiTemp را دوباره در نظر بگیرید که در آن سطرها؛ هفته‌های سال و ستون‌ها؛ روزهای هفته را نشان می‌دهند. اگر متوسط دماهای حداکثر را برای یک هفته خاص از سال را بخواهیم باید مقادیر عناصر سطر نظیر آن هفته را با هم جمع کنیم و بر 7 تقسیم می‌کنیم. اگر متوسط دماهای حداکثر را برای یک روز خاص از هفته بخواهیم باید عناصر ستون نظیر آن روز را با هم جمع کنیم و بر 52 تقسیم کنیم. حالت اول دسترسی سطری و حالت دوم دسترسی ستونی است.
حال فرض کنید که بخواهیم متوسط دما را برای یک سال محاسبه کنیم. در این حالت باید به همه عناصر آرایه دسترسی پیدا کنیم، آن‌ها را با هم جمع کنیم و بر 364 تقسیم کنیم. در این حالت ترتیب دسترسی ـ به سطر یا ستون ـ اهمیتی ندارد. همین وضعیت هنگامی‌که بخواهیم همه عناصر آرایه را صفر قرار دهیم پیش می‌آید.
در ادامه برای روشن‌تر شدن موضوع، عملیات رایج روی آرایه‌ها را در قالب موارد زیر نشان می‌دهیم:
-
جمع عناصر سطرهای آرایه
-
جمع عناصر ستون‌های آرایه
-
مقداردهی اولیه همه عناصر آرایه با صفر یا مقدار خاص
-
چاپ عناصر یک آرایه
برای این منظور از یک آرایه با ابعاد NUM_ROWS و NUM_COLS استفاده می‌کنیم. ثابت‌ها و متغیرهای لازم به شکل زیر تعریف میشوند:
جمع سطرها
فرض کنید بخواهیم عناصر سطر 3 آرایه فوق را با هم جمع کنیم و نتیجه را چاپ کنیم. حلقه For زیر این کار را انجام می‌دهد:
این حلقه با ثابت نگه‌داشتن زیرنویس مربوط به سطر با مقدار 3 ستون‌ها را از ابتدا تا انتها طی می‌کند، در هر تکرار حلقه مقادیر عناصر سطر سوم به متغیر total که ابتداً به صفر مقداردهی شده است اضافه میشوند.
حال فرض کنید بخواهیم مجموع عناصر سطر 2 و 3 را حساب و چاپ کنیم. برای این منظور از یک حلقه تودرتو استفاده می‌کنیم، که در آن زیرنویس سطر به‌عنوان متغیر حلقه بیرونی بکار می‌رود.
حلقه بیرونی سطرها و حلقه داخلی ستون‌ها را کنترل می‌کند. ابتدا برای یک مقدار سطر همه عناصر ستون‌ها مورد پردازش واقع میشوند و آنگاه حلقه بیرونی به سطر بعدی می‌رود و درباره همه عناصر ستون‌ها توسط حلقه داخلی مورد پردازش واقع میشوند. در تکرار اول حلقه خارجی، row برابر 2 قرار داده می‌شود و col از 0 تا 1- NUM_COLS تغییر می‌کند. سپس عناصر آرایه به ترتیب زیر در دسترس برنامه قرار می‌گیرند.
در تکرار دوم حلقه خارجی، row یک واحد افزایش داده شده و برابر 3 قرار داده می‌شود و دوباره col از 0 تا NUM_COLS-1 تغییر می‌کند. در این حالت عناصر آرایه به ترتیب زیر در دسترس قرار می‌گیرند.
می‌توان بجای حالت خاص فوق که تنها دو سطر در نظر گرفته شده است، یک حالت نسبتاً عمومی در نظر بگیریم که در آن بخشی از آرایه مورد پردازش واقع شود. به‌عبارت‌دیگر می‌خواهیم تعداد سطرها از 0 تا متغیر دلخواه rowsFilled و تعداد ستون‌ها از 0 تا متغیر دلخواه colsFilled تغییر کند. برای این منظور دو متغیر ذیل را تعریف می‌کنیم.
و قطعه کد ذیل که دارای دو حلقه است می‌نویسیم:
شکل 8-3 پردازش زیرآرایه‌ای از آرایه دوبعدی را نشان می‌دهد.
شکل 8-3 : پردازش سطری آرایه دوبعدی
جمع ستون‌ها
فرض کنید بخواهیم عناصر هر ستون را جمع و چاپ کنیم. کد ذیل این کار را انجام می‌دهد. کد برای پردازش بخشی از آرایه نوشته شده است.
در این حالت، حلقه بیرونی ستون‌ها و حلقه داخلی سطرها را کنترل می‌کند. همه عناصر اولین ستون مورد دسترس واقع شده و قبل از آنکه زیرنویس حلقه خارجی تغییر کند و عناصر ستون دوم در دسترس قرار گیرند، با هم جمع شده‌اند. شکل 8-4 پردازش ستونی آرایه را نشان می‌دهد.
شکل 8-4: پردازش ستونی آرایه دوبعدی
مقداردهی اولیه آرایه
نظیر آرایه‌های یک‌بعدی، می‌توان در حین تعریف و یا با استفاده از دستور انتساب به عناصر یک آرایه دوبعدی مقدار اولیه نسبت داد. اگر آرایه کوچک باشد، بهتر است در حین تعریف مقداردهی اولیه انجام شود. برای نسبت دادن مقادیر زیر به یک آرایه دوبعدی
به این صورت عمل می‌شود:
در این تعریف، مقادیر 5- ، 3 ، 14 در سطر اول یا سطر 0 آرایه و مقادیر 7 ، 46 ، 0 در سطر دوم یا سطر 1 قرار می‌گیرند. می‌توان فرض کرد که هر سطر آرایه دوبعدی یک آرایه یک‌بعدی است و نظیر آرایه‌های یک‌بعدی کار مقداردهی اولیه آن انجام می‌گیرد. لذا عناصر آکولاد اول اولین آرایه یک‌بعدی، و عناصر آکولاد دوم، دومین آرایه یک‌بعدی را مقداردهی می‌کنند.
اگر آرایه بزرگ باشد مقداردهی اولیه آن در حین تعریف غیرعملی است. برای یک آرایه 100 × 100 امکان لیست کردن 10,000 مقدار در برنامه وجود ندارد. برای خواندن این مقادیر آن‌ها را در فایلی قرار داده و هنگام اجرا فایل را می‌خوانیم (خواندن فایل‌ها را در فصل 10 خواهید آموخت). اگر همه مقادیر یکسان باشند از دو حلقه تودرتو به ترتیب زیر استفاده می‌کنیم. در اینجا مقدار 0 را در آرایه قرار داده‌ایم و فرض کرده‌ایم که تعداد سطر و ستون‌ها به ترتیب NUM_ROWS ، NUM_COLS باشند.
یا در موقع تعریف آرایه می‌توانیم کلیه عناصر آرایه دوبعدی را مقدار اولیه صفر دهیم.
چاپ آرایه
فرض کنید بخواهیم آرایه را سطر به سطر به‌طوری‌که هر سطر در یک خط واقع شود چاپ کنیم. در این حالت با پردازش سطری آرایه روبرو هستیم و کد ذیل این کار را انجام می‌دهد:
قطعه کد فوق عناصر آرایه را در ستون‌هایی به عرض 15 کاراکتر چاپ می‌کند. برای رعایت سَبک درست برنامه‌نویسی بهتر است برای ستون‌ها عناوین مناسب نیز انتخاب شوند و در برنامه دستور چاپ آن‌ها ذکر شود.
حکم خاصی مبنی بر اینکه عناصر آرایه حتماً به‌صورت هر سطر در یک خط چاپ شوند وجود ندارد. می‌توانیم در هر خط یک ستون از آرایه را چاپ کنیم. برای این منظور کافی است که جای دستورهای for را در کد فوق با هم عوض کنیم.
ارسال آرایه دوبعدی به‌عنوان آرگومان به توابع
در فصل 5، گفته شد که وقتی آرایه‌ای یک‌بعدی به‌عنوان پارامتر در تابعی تعریف می‌شود، اندازه آرایه را در کروشه ذکر نمی‌کنیم.
اگر اندازه آرایه ذکر شود کامپایلر از آن صرف‌نظر می‌کند. به‌علاوه در فصل 5 گفته شد که آدرس پایه (آدرس اولین عنصر آرایه) به تابع ارسال می‌شود. اگرچه تابع برای آرایه‌ای با هراندازه کار می‌کند. ولی به‌هرحال، باید اندازه آرایه را به تابع، نظیر آنچه در بالا آمده است، ارسال کنیم.
وقتی یک آرایه دوبعدی را به‌عنوان آرگومان به تابعی ارسال می‌کنیم، آدرس پایه آرایه به تابع ارسال می‌شود. در اینجا نمی‌توان هر دو اندازه آرایه را خالی گذاشت. می‌توان از اولین اندازه مربوط به تعداد سطرها صرف‌نظر کرد ولی از دومین اندازه نمی‌توان گذشت. دلیل این موضوع چیست؟
C++ آرایه‌های دوبعدی را در حافظه کامپیوتر به ترتیب سطری ذخیره می‌کند. اگر حافظه را به‌صورت سلول‌های حافظه به‌طور خطی پشت سرهم در نظر بگیرید، اولین سطر آرایه ابتدا ظاهر می‌شود و سپس دومین سطر و الی‌آخر (شکل 8-5 را ببینید)
شکل 8-5: چیدن حافظه برای یک آرایه دوبعدی 2 سطری و 4 ستونی
برای یافتن عنصر beta[1][0] در این شکل، تابعی که آدرس پایه آرایه دوبعدی beta را دریافت کرده است باید بداند که در هر سطر چهار عنصر وجود دارد یا به‌عبارت‌دیگر آرایه چهارستونی است. بنابراین در تعریف آرایه حتماً تعداد ستون‌ها باید ذکر شود.
به‌علاوه، تعداد ستون‌های مذکور در تعریف باید دقیقاً با تعداد ستون‌های آرایه تابع فراخواننده یکسان باشد. همچنان که در شکل 8-5 ملاحظه می‌شود، اگر تفاوتی در تعداد ستون‌ها وجود داشته باشد، تابع به عنصر مطلوب در حافظه نمی‌تواند دست یابد.
تابع AnotherFunc فوق‌الذکر می‌تواند آرایه دوبعدی با هر تعداد سطر را دریافت کند ولی تعداد ستون‌های آرایه ارسالی حتماً باید 4 باشد.
در عمل، بندرت برنامه‌ای می‌نویسیم که در آن از آرایه‌هایی با تعداد سطرهای متغیر ولی تعداد ستون‌های ثابت استفاده شده باشد. برای اجتناب از عدم تطابق اندازه آرایه بین تابع و تابع فراخواننده از دستور Typedef برای تعریف یک نوع آرایه دوبعدی استفاده می‌کنیم و سپس آرایه‌هایی از این نوع را تعریف می‌کنیم. برای مثال می‌توان تعریف زیر را نوشت:
و سپس می‌توان تابع همه‌منظوره زیر که همه عناصر یک آرایه دوبعدی را با مقدار دلخواهی مقداردهی می‌کند نوشت:
کد فراخواننده با فراخوانی تابع Initialize می‌تواند یک یا چند آرایه از نوع ArrayType تعریف و مقداردهی اولیه کند. برای مثال:
مثال کاربردی: ماتریس
ماتریس از ابزارهای پرکاربرد در ریاضیات و رشته‌های مهندسی است که در زبان ++C از طریق آرایه دوبعدی قابل پیاده‌سازی است. به‌عنوان‌مثال ماتریس
به‌صورت زیر قابل‌تعریف خواهد بود:
چنانچه نوع درایه‌ها به‌جای عدد صحیح، اعداد حقیقی باشد، از double استفاده خواهیم کرد.
در این مثال می‌خواهیم مجموعه‌ای از توابعی که در کار کردن با ماتریس‌ها موردنیاز هستند را به شرح ذیل بنویسیم:
-
الف- تابعی جهت دریافت درایه‌های یک ماتریس
-
ب- تابعی جهت جمع دو ماتریس
-
پ- تابعی جهت چاپ یک ماتریس
-
ت- تابعی برای ضرب دو ماتریس
حل: برای سادگی فرض می‌کنیم که توابع فوق برای یک ماتریس 3*3 موردنیاز است. برای اینکه از تعریف‌های متعدد این ماتریس جلوگیری شود، یک‌بار آن را با دستور typedef به‌صورت زیر تعریف می‌کنیم:
تابع زیر برای خواندن درایه‌های یک ماتریس قابل‌استفاده است:
برای جمع‌کردن دو ماتریس کافی است درایه‌های آن‌ها نظیر به نظیر باهم جمع شوند. دقت کنید که در C++ توابع نمی‌توانند یک آرایه را به‌عنوان خروجی تابع برگردانند، بنابراین نوع خروجی تابع را void تعریف می‌کنیم و در عوض پارامتر دیگری را به نام m3 برای حاصل جمع دو ماتریس اضافه می‌کنیم. همان‌گونه که پیش‌ازاین اشاره شد، در ارسال آرایه به‌عنوان پارامتر به تابع، همواره ارسال از نوع ارجاع در نظر گرفته می‌شود و به‌راحتی می‌توان درایه‌های آن آرایه را تغییر داد.
برای ضرب دو ماتریس نمی‌توانیم درایه‌ها را نظیر به نظیر در هم ضرب کنیم و ضرب ماتریس‌ها قدری پیچیده‌تر است. برای این منظور لازم است یک سطر از ماتریس اول در یک ستون از ماتریس دوم ضرب شود و حاصل آن در درایه‌ای با شماره سطر ماتریس یک و شماره ستون ماتریس دوم قرار گیرد. به بیان ریاضی درایه i و j از ماتریس حاصل‌ضرب با فرمول زیر قابل‌محاسبه است:
حال این رابطه را به زبان ++C تعریف می‌کنیم:
دقت داشته باشید که ازآنجاکه اطلاعات درایه‌های ماتریس m3 در محاسبه به کار گرفته شده است، حتماً باید قبل از شروع محاسبات با 0 پر شود. لذا حلقه اول بدنه تابع به این امر اختصاص یافته است.
آرایه‌های چندبعدی
C++ محدودیتی روی تعداد ابعاد آرایه‌ها ندارد. تعریف آرایه را در C++ به‌طورکلی می‌توان چنین بیان کرد.
آرایه (Array) مجموعه‌ای از عناصر، همه از یک نوع، که به‌صورت N بعدی مرتب شده‌اند (N > =1). هر عنصر با N زیرنویس که هرکدام موقعیت عنصر را در یک بعد نشان می‌دهند قابل‌دسترسی است.
به‌عنوان‌مثال در ریاضیات فضاهای n بعدی نظیر این‌گونه نمایش داده‌ها در C++ می‌باشند.
به‌عنوان‌مثال دیگر، فروشگاه زنجیره‌ای مفروضی را در نظر بگیرید که برای فروش ماهانه یک جنس خاص در هر فروشگاه، آرایه‌ای به ترتیب زیر معرفی می‌کنیم:
نمایش متغیر sales در شکل 8-6 داده شده است:
شکل 8-6 : نمایش آرایه sales
تعداد عناصر آرایه sales برابر با 12000 است، که از ضرب ابعاد آرایه درهم (10 × 12 × (100 حاصل می‌شود. اگر اطلاعات فقط برای شش ماه اول سال موجود است، نصف آرایه خالی خواهد بود. برنامه زیر تعداد اقلام به فروش رفته هر فروشگاه را به تفکیک اجناس چاپ می‌کند.
ازآنجاکه item حلقه For خارجی را کنترل می‌کند، فروش ماهانه month هر item برای هر فروشگاه store در حلقه داخلی جمع زده می‌شود. اگر بخواهیم فروش کلی هر فروشگاه را به دست آوریم، حلقه For خارجی را با store کنترل می‌کنیم و فروش ماهانه را برای همه اقلام item در حلقه داخلی جمع می‌کنیم.
برای دسترسی به عناصر یک آرایه دوبعدی به دو حلقه نیاز است. به همین ترتیب برای دسترسی به عناصر آرایه سه‌بعدی به سه حلقه نیاز است و الی‌آخر.