آرایه (ساختار داده)
From Wikipedia, the free encyclopedia
آرایه[1] تعدادی متغیر از یک نوع داده و تحت یک نام میباشد. هر یک از متغیرهای درون آرایه با یک شماره که به آن «اندیس» میگوییم از یکدیگر متمایز میشوند. متغیرهای درون آرایه را «عناصر آرایه» مینامند که همگی قابلیت نگهداری فقط یک نوع داده را دارند. عناصر درون آرایه از نظر فیزیکی مکانهای متوالی در حافظه اصلی رایانه را اشغال میکنند. بنابراین تعداد عناصر درون آرایه محدود و ثابت میباشد. اما از نظر منطقی عناصر درون آرایه را میتوانند به صورت یک سطر یا یک ستون (در آرایه یک بعدی) یا به صورت یک جدول یا ماتریس (در آرایه دو بعدی) یا در داخل یک مکعب در آرایه سه بعدی تصور شوند؛ یا حتی در ابعاد بیشتر که از این نظر محدودیتی وجود ندارد. برداریک آرایه یک بعدی است و ماتریس یک آرایه دوبعدی است که شامل چند سطر و ستون است. آرایه سه بعدی شامل سطری از سطحها و ستونهااست. به همین ترتیب آرایهای باابعاد بیشتر را میتوان با آرایهای باابعاد کمتر ایجاد کرد.
خانههای آرایه توسط اندیس مشخص میشوند که یک عدد صحیح است، مثلاً خانه شماره ۵ یعنی خانهای که اندیساش ۵ است. هر آرایهای یک اندیس شروع و یک اندیس پایان دارد که شمارههای معتبر اندیس بین این دو خواهند بود. L1 اندیس شروع آرایه است و L اختصاری Low یعنی پایین است. در بعضی زبانها اندیس شروع همیشه ۰ است. ولی در زبانهای دیگر میتواند هر عدد مثبتی باشد. مثلاً اگر L1 برابر ۴ باشد، اولین اندیس آرایه ۴ است. U1 اندیس پایان آرایه است و U اختصاری Up یعنی بالا است. مقدار U1 همیشه مساوی با بزرگتر از L1 است. اگر اندیس شروع یک آرایه (L1) برابر ۱ و اندیس پایان آرایه (U1) برابر با ۵ باشد، اندیسهای معتبر آرایه مقادیر ۱ و ۲ و ۳ و ۴ و ۵ خواهند بود. تعداد خانههای آرایه برابر است با ۵ خانه که از فرمول زیر محاسبه میشود:
U1 - L1 + 1 = ۵–۱ + ۱ = ۵
در آرایههای ساده، طول داده هر خانه بر حسب بایت ثابت و مشخص است. مثلاً برای هر خانه از آرایه فرضاً ۴ بایت در نظر گرفته میشود. اگر ما تعداد خانههای آرایه و طول داده هر خانه بر حسب بایت را بدانیم طبیعتاً میتوانیم با ضرب کردن این دو عدد در هم میزان حافظه لازم برای ایجاد کردن کل آرایه را بهدست بیاوریم. مثلاً اگر تعداد خانههای آرایه ۵ خانه و هر خانه ۴ بایت باشد، جمعاً برای این آرایه به ۲۰ بایت فضا احتیاج داریم. اگر طول داده یک خانه از حافظه را با N مشخص کنیم، یعنی در مثال N را ۴ در نظر بگیریم، با استفاده از فرمول قبلی میزان حافظه کل آرایه برابر است با:
U1 - L1 + 1) * N = (۵–۱ + ۱) * ۴ = ۵ * ۴ = ۲۰)
اگر آدرس شروع آرایه در حافظه را ۰ فرض کنیم، دادهای که در اولین خانه آرایه نوشته میشود در آدرس ۰ ذخیره خواهد شد. چون هر خانه از آرایه N بایت طول دارد، دادههای خانه دوم آرایه N بایت بعد از دادههای خانه اول ذخیره خواهد شد، یعنی در آدرس N و به همین ترتیب دادههای خانه سوم در آدرس N + N و … طبق این روال اگر بخواهیم بدانیم که دادههای خانهای با اندیس i در چه آدرسی از حافظه نوشته میشود، فرمول اش چنین خواهد بود:
i - L1) * N)
مثلاً اگر طول داده هر خانه (N) برابر ۴ و اندیس شروع آرایه (L1) برابر ۱ باشد، دادههای خانه اندیس ۱ در آدرس ۰ نوشته خواهند شد:
i - L1) * N = (۱–۱) * ۴ = ۰ * ۴ = ۰)
و دادههای خانه اندیس ۲ در آدرس ۴ نوشته خواهند شد:
i - L1) * N = (۲–۱) * ۴ = ۱ * ۴ = ۴)
البته ما فرض کردهایم که آدرس شروع آرایه در حافظه ۰ است، یعنی ما آدرس شروع آرایه را نسبت به خود آرایه محاسبه میکنیم، یعنی نسبی است. اگر آدرس شروع ارائه در حافظه ۰ نیست باید نتیجه فرمول قبلی را با آدرس شروع آرایه در حافظه جمع کنیم تا آدرس نسبی به مطلق تبدیل شود.
در آرایههای ۲ بعد به بالا برای اینکه بتوانیم عناصر را به صورت صحیح از خانههایی که ذخیره شدهاند بازیابی نماییم بایستی مشخص گردد که اگر ذخیرهٔ عناصر به شکل سطری است بازیابی آنها نیز به شکل سطری باشد و اگر ستونی است بازیابی آنها به صورت ستونی باشد.