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

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

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

خانه‌های آرایه توسط اندیس مشخص می شوند که یک عدد صحیح است، مثلا خانه شماره 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»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ ژانویه ۲۰۱۴).