آرایه‌ (Array) در برنامه‌نویسی چیست و انواع آن کدام است؟

آرایه چیست؟

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

خانه‌های آرایه توسط اندیس مشخص می‌شوند که یک عدد صحیح است. به‌طور مثال خانه شماره 5 یعنی خانه‌ای که اندیس‌اش 5 است. هر آرایه‌ای یک اندیس شروع و یک اندیس پایان دارد که شماره‌های معتبر اندیس بین این دو خواهند بود. L1 اندیس شروع آرایه است و L اختصاری Low یعنی پایین است. در بعضی زبان‌ها اندیس شروع همیشه 0 است. اما در زبان‌های دیگر می‌تواند هر عدد مثبتی باشد. مثلاً اگر L1 برابر ۴ باشد، اولین اندیس آرایه ۴ است. U1 اندیس پایان آرایه است و U اختصاری Up یعنی بالا است. مقدار U1 همیشه مساوی با بزرگتر از L1 است. اگر اندیس شروع یک آرایه (L1) برابر ۱ و اندیس پایان آرایه (U1) برابر با ۵ باشد، اندیس‌های معتبر آرایه مقادیر ۱ و ۲ و ۳ و ۴ و ۵ خواهند بود. تعداد خانه‌های آرایه برابر است با ۵ خانه که از فرمول زیر محاسبه می‌شود:

آرایه‌های یک بعدی

آرایه یک بعدی مجموعه متناهی از زوج‌ها به صورت ‹ اندیس، مقدار› است. بدین معنی که، به ازای یک اندیس یک مقدار مربوط به آن وجود دارد. برای تعریف آرایه یک بعدی یک مجموعه اندیس تعریف می‌شود.

آرایه‌های دو بعدی

یک آرایه دو بعدی مجموعه‌ای با m×n عنصر داده‌ای است که هر عنصر آن با یک جفت اندیس مشخص می‌شود. آرایه دو بعدی را می‌توان به جدولی تشبیه کرد که دارای m سطر و n ستون است. هر سطر شامل عناصری است که اندیس‌های اول آن‌ها برابر است و هر ستون شامل عناصری هستند که اندیس‌های دوم آن‌ها برابر هستند. آرایه‌های دوبعدی به عنوان ماتریس به کار می‌روند. در تعریف آرایه دو بعدی دو مجموعه اندیس معین می‌شود. اندیس اول تعداد سطرها و اندیس آرایه تعداد ستون‌ها را مشخص می‌کند.

آرایه‌های چندبعدی

آرایه n بعدی مجموعه‌ای از m1×m2×…×mn عنصر داده‌ای است که هر عنصر توسط n اندیس نظیر i1,i2,…,in مشخص می‌شوند. آرایه‌های چند بعدی در حافظه به صورت دنباله‌ای از خانه‌های پشت سر هم ذخیره می‌شوند.

ویژگی آرایه‌ها

آرایه‌ها به دو روش سطری و ستونی پیاده‌سازی می‌شوند:

روش سطری پیمایش و ذخیره آرایه‌ها

در پیمایش سطری آرایه‌ها اندیس‌های خانه‌های آرایه از سمت راست تغییر می‌کنند به‌طوری‌که اندیس سمت چپ به صورت ثابت باقی می‌ماند و یک واحد یک واحد به اندیس سمت راست اضافه می‌شود تا زمانی‌که به ماکسیمم مقدار خود برسد که در این لحظه یک واحد به اندیس سمت چپ اضافه می‌شود و دوباره اندیس سمت راست شروع به افزایش می‌یابد و این کار تا زمانی ادامه پیدا می‌کند که هر 2 اندیس به ماکسیمم مقدار خود برسد.

روش ستونی پیمایش و ذخیره آرایه‌ها

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

آرایه‌های شرکت پذیر(انجمنی)

ویژگی مهم آرایه‌ها که تاکنون مطرح شد، روش دستیابی به یک عنصر خاص ،ازطریق یک نوع شمارشی به نام اندیس است.عناصر آرایه برحسب این اندیس مرتب هستند و بااستفاده از مقادیر اندیس می‌توان به هر عنصر آرایه دست یافت در بعضی از برنامه‌های کاربردی مطلوب است که از طریق نام (بدون استفاده از اندیس) بتوان به اطلاعات دست یافت. به عنوان مثال، به ترتیب نام دانشجو و نمره دانشجوی [grade[i],name[iاسامی افراد کلاس را می‌توان با دو آرایه نشان داد در این حالت، یک ترتیب ضمنی با استفاده از اندیس دانشجوی i وجود دارد. یه این نوع آرایه‌ها، آرایه‌های شرکت‌پذیر(انجمنی) گویند.

نمایش چندجمله‌ای‌ها به کمک آرایه

همۀ چندجمله‌ای‌ها را می‌توان به کمک آرایه‌ها پیاده‌سازی کرد. روش‌های مختلفی برای این کار وجود دارد. مثلاً می‌توان بزرگترین درجه‌ای که در چندجمله‌ای می‌تواند وجود داشته باشد به عنوان Max در نظر گرفت، در این صورت می‌توان آرایه‌ای تعریف کرد که تعداد سلول‌های ان برابر با Max+1 باشد . اگر درجه چندجمله‌ای را بدانیم می‌توان هر جمله را در آرایه پیاده‌سازی کرد. در واقع [A[i ضریب (X^(n-i است.

پس از ذخیره چندجمله‌ای‌ها در داخل آرایه‌ها می‌توان اعمالی مانند جمع چندجمله‌ای و ضرب چندجمله‌ای را انجام داد.

روش قبل برای ذخیره‌سازی چندجمله‌ای ممکن است مناسب نباشد برای مثال چندجمله‌ای شما ممکن است x^1000+1 باشد. روش دیگری نیز برای ذخیره چندجمله‌ای‌ها وجود دارد در این روش از یک آرایه با دو سطر و k ستون استفاده می‌شود. که k تعداد کل جملات تشکیل دهندۀ همۀ چندجمله‌ای‌هاست . سطر اول نشان‌دهنده همۀ ضرایب است و سطر دوم نشان‌دهنده توان متناسب با هر ضریب است.

ماتریس پراکنده یا اسپارس

برای ذخیرۀ یک ماتریس M*N می‌توان از یک آرایه دو بعدی با m سطر و n ستون استفاده کرد. گروهی از ماتریس‌ها وجود دارند که به آن ماتریس خلوت یا اسپارس می‌گوییم. در این ماتریس‌ها اکثریت عناصر مقدار صفر دارند.

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

آرایه پویا

آرایه پویا، آرایه‌ای است که می‌تواند تغییر اندازه دهد و اجازه دهد عناصری به آن اضافه یا از آن حذف شود. امروزه امکان انجام این عمل در بسیاری از کتابخانه‌های استاندارد زبان‌های رایج برنامه‌نویسی تعبیه شده‌است. در یک آرایه پویا در ابتدای کار حافظه اختصاص داده نمی‌شود؛ به‌طوری‌که اندازه‌اش غیرقابل تغییر باشد.

آرایه‌های پویای کراندار و ظرفیت آن‌ها

ساده‌ترین آرایه پویا با اختصاص دادن آرایه‌ای به طول ثابت ساخته می‌شود که بعد آن را به دو قسمت تقسیم می‌کنند: قسمت اول عناصر آرایه پویا را ذخیره می‌کند و قسمت دوم ذخیره شده، یا بدون استفاده می‌ماند. سپس می‌توان با استفاده از فضای رزرو شده در زمانی ثابت عناصر را به انتهای آرایه پویا اضافه کرد یا آن‌ها را حذف کرد، تا زمانی که این فضا به‌طور کامل استفاده شود. تعداد عناصری که توسط محتویات آرایه پویا استفاده می‌شود اندازه منطقی یا اندازه آن است، در حالیکه اندازه آرایه زیرین ظرفیت آرایه پویا نام دارد، که حداکثر اندازه منطقی ممکن است. در برنامه‌هایی که اندازه منطقی کراندار است، این ساختار داده کفایت می‌کند. تغییر دادن اندازه آرایه زیرین عملی هزینه بر است، گاهی ناچار می‌شویم تمام محتویات آرایه را کپی کنیم.

تصاعد هندسی و هزینه واگذار شده

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

در فرایند درج n عنصر، ظرفیت‌ها تشکیل تصاعد هندسی می‌دهند. بسط دادن آرایه با هر نسبت ثابتی تضمین می‌کند وارد کردن عنصر در کل از (O(n زمان می‌برد، یعنی وارد کردن هر عنصر زمان سرشکن شده ثابتی می‌برد. مقدار این تناسب منجر به لزوم سبک‌سنگین کردن این فاصله زمانی می‌شود.

کارایی آرایه پویا شبیه آرایه‌های عادی ‌است، با این‌حال عمل حذف و افزودن عناصر به انتها:

• گرفتن یا قرار دادن مقدار در محلی خاص (زمان ثابت)
• به ترتیب روی عناصر حرکت کردن (زمان خطی)
• وارد کردن یا پاک کردن عنصر در وسط آرایه (زمان خطی)
• وارد کردن یا پاک کردن عنصر در آخر آرایه (زمان ثابت سرشکن)

بسیاری از مزیت‌های آرایه‌ها در آرایه‌های پویا نیز وجود دارد، از جمله محل مناسب مرجع و استفاده از حافظه نهان، تراکم (کم استفاده کردن از حافظه)، و دسترسی تصادفی. معمولاً آرایه‌های پویا در کل فقط یک حافظه اضافی کوچکی برای اطلاعات اندازه و ظرفیت دارند. این ویژگی موجب می‌شود آرایه‌های پویا ابزار مناسبی برای ساختن داده ساختار متناسب با حافظه نهان شوند. آرایه‌های پویا در مقایسه با لینک لیست، قابلیت شاخص گذاری سریع تری دارند (زمان ثابت در برابر زمان خطی) و معمولاً به دلیل اصلاح محل مرجع عناصر سریعتر می‌توان بر روی عناصر واقع در خانه‌های آرایه حرکت کرد؛ اگرچه، آرایه‌های پویا برای وارد کردن در محلی دلخواه یا پاک کردن از جایگاهی اختیاری زمانی خطی نیاز دارند، چون همه عناصر بعدی باید یک عنصر جابه‌جا شوند، در حالیکه لینک لیست می‌تواند این عمل را در زمانی ثابت انجام دهد. به وسیله میانگیر وقفه و متغیرهای بردار صف شده این اشکال را برطرف کرده‌اند که در مورد آن در قسمت متغیرها بحث شده‌است. همچنین، ممکن است یافتن فضایی پیوسته در ناحیه یک حافظه بسیار قطعه بندی شده هزینه بر یا غیرممکن باشد، در حالیکه لینک لیست‌ها نیازی ندارند همه داده ساختار به‌طورپیوسته در حافظه ذخیره شود.

زبان‌های پشتیبانی‌کننده

در سی‌پلاس‌پلاس Std::vector یک نمونه پیاده‌سازی برای آرایه‌های پویا است، همان‌طور که کلاس‌های ArrayList توسط API java و دات‌نت فریمورک عرضه شده‌است. کلاس نوع List که توسط دات‌نت ارایه شده پیاده‌سازی دیگری برای آرایه‌های پویا است.