آرایه (ساختار داده): تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز Bkouhi صفحهٔ آرایه (ساختمان داده‌ها) را به آرایه (ساختار داده) منتقل کرد |
بدون خلاصۀ ویرایش برچسب: افزودن پیوند بیرونی به جای ویکی‌پیوند (پخ) |
||
خط ۱:
{{دیگر کاربردها|آرایه}}
'''آرایه''' تعدادی [[متغیر (برنامه نویسی)|متغیر]] از یک نوع [[داده]] و تحت یک نام می‌باشد. هر یک از متغیرهای درون آرایه با یک شماره که به آن «اندیس» می‌گوییم از یکدیگر متمایز می‌شوند. متغیرهای درون آرایه را «عناصر آرایه» می‌نامند که همگی قابلیت نگهداری فقط یک نوع داده را دارند. عناصر درون آرایه از نظر فیزیکی مکان‌های متوالی در [[حافظه اصلی]] رایانه را اشغال می‌کنند. بنا بر این تعداد عناصر درون آرایه محدود و ثابت می‌باشد. اما از نظر منطقی عناصر درون آرایه را می‌توانند به صورت یک سطر و یا یک ستون (در آرایه یک بعدی) یا به صورت یک [[جدول]] یا [[ماتریس]] (در آرایه دو بعدی) و یا در داخل یک مکعب در آرایه سه بعدی تصور شوند. و یا حتی در ابعاد بیشتر که از این نظر محدودیتی وجود ندارد. برداریک آرایه یک بعدی است وماتریس یک آرایه دوبعدی است که شامل چندسطروستون است .آرایه سه بعدی شامل سطری ازسطح ها وستون‌هااست.به همین ترتیب آرایه ای باابعادبیشتررامیتوان با آرایه ای باابعادکمترایجادکرد.
خانه های آرایه توسط اندیس مشخص می شوند که یک عدد صحیح است، مثلا خانه شماره 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).توصیفگرآرایه مانند برداراست بااین تفاوت که حدودبالاوپایین هر بعد نگهداری می شود.
==آرايه هاي پويا==
آرايه پويا<ref>[//https://en.wikipedia.org/wiki/Dynamic_array]</ref>{{به انگلیسی|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 وجود دارد.
== مثال‌ها ==
در زبان [[پی اچ پی]]
سطر ۱۷ ⟵ ۱۶۵:
# برنامه سازی پاسکال ۲ (فنی و حرفه‌ای) گروه تحصیلی کامپیوتری
{{ویکی‌انبار-رده|Array data structure}}
#قدسی، محمد، [[داده ساختارها]] و مبانی الگوریتم‌ها، چاپ اول، [[انتشارات فاطمی]]، ۱۳۸۸.
*{{یادکرد-ویکی|پیوند=https://en.wikipedia.org/wiki/Array_data_structure|عنوان = Array|بازیابی =۳ می ۲۰۱۱}}
[[رده:آرایه]]
| |||