آرایه (ساختار داده)
آرایه تعدادی متغیر از یک نوع داده و تحت یک نام می‌باشد. هر یک از متغیرهای درون آرایه با یک شماره که به آن «اندیس» می‌گوییم از یکدیگر متمایز می‌شوند. متغیرهای درون آرایه را «عناصر آرایه» می‌نامند که همگی قابلیت نگهداری فقط یک نوع داده را دارند. عناصر درون آرایه از نظر فیزیکی مکان‌های متوالی در حافظه اصلی رایانه را اشغال می‌کنند. بنابراین تعداد عناصر درون آرایه محدود و ثابت می‌باشد. اما از نظر منطقی عناصر درون آرایه را می‌توانند به صورت یک سطر یا یک ستون (در آرایه یک بعدی) یا به صورت یک جدول یا ماتریس (در آرایه دو بعدی) یا در داخل یک مکعب در آرایه سه بعدی تصور شوند؛ یا حتی در ابعاد بیشتر که از این نظر محدودیتی وجود ندارد. برداریک آرایه یک بعدی است و ماتریس یک آرایه دوبعدی است که شامل چند سطر و ستون است. آرایه سه بعدی شامل سطری از سطح‌ها و ستون‌هااست. به همین ترتیب آرایه‌ای باابعاد بیشتر را می‌توان با آرایه‌ای باابعاد کمتر ایجاد کرد.
خانه‌های آرایه توسط اندیس مشخص می‌شوند که یک عدد صحیح است، مثلاً خانه شماره ۵ یعنی خانه‌ای که اندیس‌اش ۵ است. هر آرایه‌ای یک اندیس شروع و یک اندیس پایان دارد که شماره‌های معتبر اندیس بین این دو خواهند بود. 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 = (۲–۱) * ۴ = ۱ * ۴ = ۴)
البته ما فرض کرده‌ایم که آدرس شروع آرایه در حافظه ۰ است، یعنی ما آدرس شروع آرایه را نسبت به خود آرایه محاسبه می‌کنیم، یعنی نسبی است. اگر آدرس شروع ارائه در حافظه ۰ نیست باید نتیجه فرمول قبلی را با آدرس شروع آرایه در حافظه جمع کنیم تا آدرس نسبی به مطلق تبدیل شود.
در آرایه‌های ۲ بعد به بالا برای اینکه بتوانیم عناصر را به صورت صحیح از خانه‌هایی که ذخیره شده‌اند بازیابی نماییم بایستی مشخص گردد که اگر ذخیرهٔ عناصر به شکل سطری است بازیابی آن‌ها نیز به شکل سطری باشد و اگر ستونی است بازیابی آن‌ها به صورت ستونی باشد.
آرایه‌های یک بعدی
آرایه یک بعدی مجموعه متناهی از زوج‌ها به صورت ‹ اندیس، مقدار› است. بدین معنی که، به ازای یک اندیس یک مقدار مربوط به آن وجود دارد. برای تعریف آرایه یک بعدی یک مجموعه اندیس تعریف می‌شود.
آرایه‌های دو بعدی
یک آرایه دو بعدی مجموعه‌ای با m×n عنصر داده‌ای است که هر عنصر آن با یک جفت اندیس مشخص می‌شود. آرایه دو بعدی را می‌توان به جدولی تشبیه کرد که دارای m سطر و n ستون است. هر سطر شامل عناصری است که اندیس‌های اول آن‌ها برابر است و هر ستون شامل عناصری هستند که اندیس‌های دوم آن‌ها برابر هستند. آرایه‌های دوبعدی به عنوان ماتریس به کار می‌روند. در تعریف آرایه دو بعدی دو مجموعه اندیس معین می‌شود. اندیس اول تعداد سطرها و اندیس آرایه تعداد ستون‌ها را مشخص می‌کند.
آرایه‌های چندبعدی
آرایه n بعدی مجموعه‌ای از m1×m2×…×mn عنصر داده‌ای است که هر عنصر توسط n اندیس نظیر i1,i2,…,in مشخص می‌شوند. آرایه‌های چند بعدی در حافظه به صورت دنباله‌ای از خانه‌های پشت سر هم ذخیره می‌شوند.
ویژگی آرایه‌ها
(۱) آرایه‌ها به دوروش سطری وستونی پیاده‌سازی می‌شوند:
روش سطری پیمایش و ذخیرهٔ آرایه‌ها
در پیمایش سطری آرایه‌ها اندیس‌های خانه‌های آرایه از سمت راست تغییر می‌کنند به‌طوری‌که اندیس سمت چپ به صورت ثابت باقی می‌ماند و یک واحد یک واحد به اندیس سمت راست اضافه می‌شود تا زمانی‌که به ماکسیمم مقدار خود برسد که در این لحظه یک واحد به اندیس سمت چپ اضافه می‌شود و دوباره اندیس سمت راست شروع به افزایش می‌یابد و این کار تا زمانی ادامه پیدا می‌کند که هر ۲ اندیس به ماکسیمم مقدار خود برسد.
روش ستونی پیمایش و ذخیرهٔ آرایه‌ها
در روش ستونی اندیس‌های آرایه از سمت چپ شروع به افزایش می‌کنند یعنی اندیس‌های سمت چپ یک واحد یک واحد اضافه می‌شوند تا زمانی که به ماکسیمم مقدار خود برسند که در این لحظه یک واحد اندیس سمت راست اضافه می‌شود و دوباره اندیس سمت چپ از ۱ شروع به افزایش می‌کند و این کار تا زمانی انجام می‌گیرد که تمامی اندیس‌ها به ماکسیمم مقدار خود برسند.
مثال زیر یک ماتریس ۳ در ۴ را به صورت ستونی پیمایش می‌کند.
b11 , b21, b31 , b12 , b22 , b32 , b13 , b23 , b33 , b14 , b24 , b34
(۲) نمایش حافظه برای آرایه‌های چندبعدی از بردار پیروی می‌کنند برای ماتریس‌ها اشیای داده اولین سطر، سپس اشیای داده دومین سطر و به همین ترتیب ذخیره می‌شود تا یک نمایش حافظه ترتیبی از تمام عناصر آرایه داشته باشیم.
(۳) توصیفگر آرایه مانند برداراست با این تفاوت که حدود بالا و پایین هر بعد نگهداری می‌شود.
آرایه‌های پویا
آرایه پویا(به انگلیسی: Dynamic Array) آرایه‌ای است که اندازه‌اش در زمان اجرا با عمل درج یا حذف عناصر در آن تغییر می‌کند. در زبان برنامه‌نویسی Visual Basic توسط دستور REDIM و در زبان C با تعریف حافظه پویا می‌توان آرایه پویا ایجاد کرد. در بعضی زبان‌ها مانند Perl کلیه آرایه‌ها به صورت پویا هستند.
درج عنصری در آرایه
برای درج عنصری در آرایه تعدادی از عناصر باید به سمت پایین منتقل شوند تا عنصر جدید در محل مورد نظر قرار گیرد. اگر بخواهیم عنصر جدید در مکان k ام آرایه درج شود کلیه عناصر از k به بعد باید شیفت داده شوند، سپس عنصر در مکان Kام ذخیره شود.
در کل n-k+1 عنصر باید جابجا شوند. اگر عنصر جدید در محل آخرین عنصر درج شود تنها عنصر آخر آرایه جابجا می‌شود. بدترین حالت زمانی اتفاق می‌افتد که بخواهیم عنصر جدید را در مکان اول آرایه درج کنیم در این حالت تعداد جابجایی‌ها برابر است با n می‌شود. به‌طور متوسط نیاز به n+1)/2) جابجایی است. با هربار عمل درج یک واحد به n تعداد عناصر آرایه اضافه می‌شود. n تعداد عناصری که در آرایه درج شده‌اند را نشان می‌دهد و ربطی به طول آرایه ندارد. الگوریتم زیر عنصر item را در مکان k ام آرایه A با n عنصر درج می‌کند.
(for (i:= n down to k
[A[j+1] := A[j
end for
A[k] := item
n := n +1
end
حذف عنصری از آرایه
وقتی عنصری از آرایه حذف می‌شود عناصر بعدی باید به سمت بالا منتقل شوند تا محل عنصر حذف شده پر شود. برای حذف عنصری که در مکان k ام قرار دارد، کلیه عناصر از k+1 به بعد باید به سمت بالا شیفت داده شوند.
در کل n-k عنصر باید جابجا شوند. کمترین جابجائی وقتی است که عنصر آخر حذف شود که هیچ عنصری جابجا نمی‌شود. در بدترین حالت تعداد جابجایی‌ها برابر با n-1 است وقتی که اولین عنصر آرایه حذف می‌شود. به‌طور متوسط نیاز به n-1)/2) جابجایی است. با هربار عمل درج یک واحد به n (تعداد عناصر آرایه) اضافه می‌شود. n تعداد عناصری که در آرایه درج شده‌اند را نشان می‌دهد و ربطی به طول آرایه ندارد. الگوریتم زیر عنصر kام آرایه A را حذف و در item ذخیره می‌کند.
[item := A[k
(for (j := k to n
[A[j] := A[j + 1
end for
n := n –1
end
پیچیدگی الگوریتم فوق (O(n است.
همان‌طور که مشاهده می‌شود عملیات درج و حذف در آرایه به‌طور متوسط منجر به انتقال نصف عناصر آرایه می‌شود. بنابراین در مواردی که مجموعه عناصر داده‌ای به‌طور مکرر در حال اضافه و حذف هستند آرایه خطی روش کارآمدی برای ذخیرهٔ داده‌ها نیست.
آرایه‌های شرکت پذیر(انجمنی)
ویژگی مهم آرایه‌ها که تاکنون مطرح شد، روش دستیابی به یک عنصر خاص ،ازطریق یک نوع شمارشی به نام اندیس است.عناصر آرایه برحسب این اندیس مرتب هستند و بااستفاده از مقادیر اندیس می‌توان به هر عنصر آرایه دست یافت در بعضی از برنامه‌های کاربردی مطلوب است که از طریق نام (بدون استفاده از اندیس) بتوان به اطلاعات دست یافت. به عنوان مثال، به ترتیب نام دانشجو و نمره دانشجوی [grade[i],name[iاسامی افراد کلاس را می‌توان با دو آرایه نشان داد در این حالت، یک ترتیب ضمنی با استفاده از اندیس دانشجوی i وجود دارد. یه این نوع آرایه‌ها، آرایه‌های شرکت‌پذیر(انجمنی) گویند.
نمایش چندجمله‌ای‌ها به کمک آرایه
همۀ چندجمله‌ای‌ها را می‌توان به کمک آرایه‌ها پیاده‌سازی کرد. روش‌های مختلفی برای این کار وجود دارد. مثلاً می‌توان بزرگترین درجه‌ای که در چندجمله‌ای می‌تواند وجود داشته باشد به عنوان Max در نظر گرفت، در این صورت می‌توان آرایه‌ای تعریف کرد که تعداد سلول‌های ان برابر با Max+1 باشد . اگر درجه چندجمله‌ای را بدانیم می‌توان هر جمله را در آرایه پیاده‌سازی کرد. در واقع [A[i ضریب (X^(n-i است.
پس از ذخیره چندجمله‌ای‌ها در داخل آرایه‌ها می‌توان اعمالی مانند جمع چندجمله‌ای و ضرب چندجمله‌ای را انجام داد.
روش قبل برای ذخیره‌سازی چندجمله‌ای ممکن است مناسب نباشد برای مثال چندجمله‌ای شما ممکن است x^1000+1 باشد. روش دیگری نیز برای ذخیره چندجمله‌ای‌ها وجود دارد در این روش از یک آرایه با دو سطر و k ستون استفاده می‌شود. که k تعداد کل جملات تشکیل دهندۀ همۀ چندجمله‌ای‌هاست. سطر اول نشان‌دهندهٔ همۀ ضرایب است و سطر دوم نشان‌دهندهٔ توان متناسب با هر ضریب است.
ماتریس پراکنده یا اسپارس
برای ذخیرۀ یک ماتریس M*N می‌توان از یک آرایهٔ دو بعدی با m سطر و n ستون استفاده کرد. گروهی از ماتریس‌ها وجود دارند که به آن ماتریس خلوت یا اسپارس می‌گوییم. در این ماتریس‌ها اکثریت عناصر مقدار صفر دارند.
از آنجایی‌که ماتریس‌های اسپارس در عمل وجود دارند و برخی موارد اندازه‌های آن‌ها بسیار بزرگ است می‌بایست روش بهینه‌تری را برای ذخیره آن‌ها در کامپیوتر ارائه کنیم . یک روش آن است که از یک آرایه دو بعدی با سه ستون استفاده کنیم . ستون‌های اول و دوم این آرایه موقعیت سطر و ستون مقدار در ماتریس اسپارس را نشان می‌دهند و ستون سوم مقدار ذخیره شده در آن سطر و ستون را نشان می‌دهند .(تعداد سطرهای این آرایه به تعداد مقدار ذخیره شده در ماتریس اصلی است.)
مثال‌ها
در زبان پی اچ پی
$array = array();
$array[] = "IRAN"; // It's Index will be 0
$array[] = "Persia"; // It's Index will be 1
echo $array[0]; // Answer : IRAN
echo $array[1]; // Answer : Persia
جستارهای وابسته
منابع
- ↑ «آرایه» [رایانه و فنّاوری اطلاعات] هم‌ارزِ «array»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر اول. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۳۱-۱ (ذیل سرواژهٔ آرایه1)
- ↑ [۱]
- برنامه‌سازی پاسکال ۲ (فنی و حرفه‌ای) گروه تحصیلی کامپیوتری
جعفرنژاد قمی، عین‌الله. طراحی الگوریتم‌ها. چاپ ششم، انتشارات علوم رایانه، ۱۳۸۳.