آرایه (ساختار داده)

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

                                                     U1 - L1 + 1 = 5 - 1 + 1 = 5

در آرایه‌های ساده، طول داده هر خانه بر حسب بایت ثابت و مشخص است. مثلا برای هر خانه از آرایه فرضا 4 بایت در نظر گرفته می شود. اگر ما تعداد خانه های آرایه و طول داده هر خانه بر حسب بایت را بدانیم طبیعتا می توانیم با ضرب کردن این دو عدد در هم میزان حافظه لازم برای ایجاد کردن کل آرایه را بدست بیاوریم. مثلا اگر تعداد خانه های آرایه 5 خانه و هر خانه 4 بایت باشد، جمعا برای این آرایه به 20 بایت فضا احتیاج داریم. اگر طول داده یک خانه از حافظه را با N مشخص کنیم، یعنی در مثال N را 4 در نظر بگیریم، با استفاده از فرمول قبلی میزان حافظه کل آرایه برابر است با :

                                   U1 - L1 + 1) * N = (5 - 1 + 1) * 4 = 5 * 4 = 20)

اگر آدرس شروع آرایه در حافظه را 0 فرض کنیم، داده‌ای که در اولین خانه آرایه نوشته می شود در آدرس 0 ذخیره خواهد شد. چون هر خانه از آرایه N بایت طول دارد، داده های خانه دوم آرایه N بایت بعد از داده های خانه اول ذخیره خواهد شد، یعنی در آدرس N و به همین ترتیب داده های خانه سوم در آدرس N + N و ... طبق این روال اگر بخواهیم بدانیم که داده های خانه ای با اندیس i در چه آدرسی از حافظه نوشته می شود، فرمول اش چنین خواهد بود :

                                                                      i - L1) * N)

مثلا اگر طول داده هر خانه (N) برابر 4 و اندیس شروع آرایه (L1) برابر 1 باشد، داده های خانه اندیس 1 در آدرس 0 نوشته خواهند شد :

                                             i - L1) * N = (1 - 1) * 4 = 0 * 4 = 0)

و داده های خانه اندیس 2 در آدرس 4 نوشته خواهند شد :

                                              i - L1) * N = (2 - 1) * 4 = 1 * 4 = 4)


البته ما فرض کرده ایم که آدرس شروع آرایه در حافظه 0 است، یعنی ما آدرس شروع آرایه را نسبت به خود آرایه محاسبه می کنیم، یعنی نسبی است. اگر آدرس شروع ارایه در حافظه 0 نیست باید نتیجه فرمول قبلی را با آدرس شروع آرایه در حافظه جمع کنیم تا آدرس نسبی به مطلق تبدیل شود.

در آرایه های 2 بعد به بالا برای اینکه بتوانیم عناصر را به صورت صحیح از خانه هایی که ذخیره شده اند بازیابی نماییم بایستی مشخص گردد که اگر ذخیره‌ی عناصر به شکل سطری است بازیابی آن‌ها نیز به شکل سطری باشد و اگر ستونی است بازیابی آن‌ها به صورت ستونی باشد.

آرايه‌هاي یک بعدی[ویرایش]

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

آرايه‌هاي دو بعدي[ویرایش]

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

آرایه‌های چندبعدی[ویرایش]

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

ویژگی آرایه ها[ویرایش]

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

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

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

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

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

مثال زیر یک ماتریس 3 در 4 را به صورت ستونی پیمایش می‌کند.


                                                          b11 , b21, b31 , b12 , b22 , b32 , b13 , b23 , b33 , b14 , b24 , b34

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

(3) توصیفگر آرایه مانند برداراست بااین تفاوت که حدود بالا و پایین هر بعد نگهداری می شود.

آرايه های پويا[ویرایش]

آرایه پویا[۱](به انگلیسی: 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


منابع[ویرایش]

  1. برنامه سازی پاسکال ۲ (فنی و حرفه‌ای) گروه تحصیلی کامپیوتری

جعفرنژاد قمی، عین الله. طراحی الگوریتم ها. چاپ ششم، انتشارات علوم رایانه، ۱۳۸۳.

  • مشارکت‌کنندگان ویکی‌پدیا، «Array»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ژانویه ۲۰۱۴).
  • مشارکت‌کنندگان ویکی‌پدیا، «Dynamic Array»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ ژانویه ۲۰۱۴).