آرایه (ساختار داده): تفاوت میان نسخه‌ها

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

==آرايه‌هاي يكیک بعدی==

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

براي تعريفتعریف آرايه يكیک بعديبعدی يکیک مجموعه انديساندیس تعريفتعریف می شود.

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

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

آرايه هايهای دوبعديدوبعدی به عنوان ماتريسماتریس به كارکار ميمی روند.

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

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

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

==آرايه هايهای پويا==

آرايه پويا<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 عنصر درج می کند.

وقتی عنصری از آرايه حذف می شود عناصر بعدی بايد به سمت بالا منتقل شوند تا محل عنصر حذف شده پر شود. برای حذف عنصری که در مکان k ام قرار دارد، کليه عناصر از k+1 به بعد بايد به سمت بالا شيفتشیفت داده شوند.

در کل n-k عنصر بايد جابجا شوند. کمترين جابجائی وقتی است که عنصر آخر حذف شود که هيچ عنصری جابجا نمی شود. در بدترينبدترین حالت تعداد جابجائي‌هاجابجایی‌ها برابر با n-1 است وقتی که اوليناولین عنصر آرايه حذف می شود.

به طور متوسط نيازنیاز به n-1)/2) جابجائيجابجایی است.

با هربار عمل درج يکیک واحد به n (تعداد عناصر آرايه ) اضافه می شود. n تعداد عناصری که در آرايه درج شده اند را نشان می دهد و ربطی به طول آرايه ندارد.

الگوريتمالگوریتم زير عنصر kام آرايه A را حذف و در item ذخيره می کند.

پيچيدگيپیچیدگی الگوريتمالگوریتم فوق (O(n است.

همانطور که مشاهده می شود عمليات درج و حذف در آرايه به طور متوسط منجر به انتقال نصف عناصر آرايه می شود. بنابراين در مواردی که مجموعه عناصر داده‌ای به طور مکرر درحال اضافه و حذف هستند آرايه خطيخطی روش كارآمديکارآمدی براي ذخيره‌یذخیرهٔ داده‌ها نيست.

ویژگی مهم آرایه‌ها که تاکنون مطرح شد،روش دستیابی به یک عنصرخاصعنصر خاص ،ازطریق یک نوع شمارشی به نام اندیس است.عناصرآرایهعناصر آرایه برحسب این اندیس مرتب هستند و بااستفاده ازمقادیراندیساز مقادیر اندیس می توان به هرعنصرآرایههر عنصر آرایه دست یافت در بعضی ازبرنامه‌هایاز برنامه‌های کاربردی مطلوب است که ازطریق نام (بدون استفاده ازاندیساز اندیس) بتوان به اطلاعات دست یافت. به عنوان مثال، به ترتیب نام دانشجو و نمره دانشجوی [grade[i],name[iاسامي افراد كلاسکلاس را ميمی توان با دو آرايه نشان داد در ايناین حالت، يكیک ترتيبترتیب ضمني با استفاده از انديساندیس دانشجويدانشجوی i وجود دارد. یه این نوع آرایه‌ها، آرایه‌های شرکت‌‌پذیر(انجمنی) گویند.

روش دیگری نیز برای ذخیره چند جمله ای ها وجود دارد دراین روش از یک آرایه با دو سطر و k ستون استفاده می شود. که k تعداد کل جملات تشیکلتشکیل دهنده‌ی همه‌ی چند جمله‌ای‌هاست . سطر اول نشان‌دهنده‌ینشان‌دهندهٔ همه‌ی ضرایب است و سطر دوم نشان‌دهنده‌ینشان‌دهندهٔ توان متناسب با هر ضریب است.

از آنجایی‌که ماتریس های اسپارس در عمل وجود دارند و برخی موارد اندازه‌های آن‌ها بسیار بزرگ است می بایست روش بهینه‌تری را برای ذخیره آن‌ها در کامپیوترارائهکامپیوتر ارائه کنیم . یک روش آن است که ازیک آرایه دو بعدی با سه ستون استفاده کنیم . ستون های‌ اول و دوم این آرایه موقعیت سطر و ستون مقدار در ماتریس اسپارس را نشان می‌دهند و ستون سوم مقدار ذخیره شده در آن سطر و ستون رانشان می‌دهند .(تعداد سطرهای این آرایه به تعداد مقدار ذخیره شده در ماتریس اصلی است.)