موضوع مقاله: آرایه (ساختار داده) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # آرایه (ساختار داده) | مقدمه: هر یک از متغیرهای درون آرایه با یک شماره که به آن «اندیس» می‌گوییم از یکدیگر متمایز می‌شوند. | ## بخش 1: آرایه (ساختار داده) | متغیرهای درون آرایه را «عناصر آرایه» می‌نامند که همگی قابلیت نگهداری فقط یک نوع داده را دارند. عناصر درون آرایه از نظر فیزیکی مکان‌های متوالی در حافظه اصلی رایانه را اشغال می‌کنند. اما از نظر منطقی عناصر درون آرایه را می‌توانند به صورت یک سطر یا یک ستون (در آرایه یک بعدی) یا به صورت یک جدول یا ماتریس (در آرایه دو بعدی) یا در داخل یک مکعب در آرایه سه بعدی تصور شوند؛ یا حتی در ابعاد بیشتر که از این نظر محدودیتی وجود ندارد. برداریک آرایه یک بعدی است و ماتریس یک آرایه دوبعدی است که شامل چند سطر و ستون است. به همین ترتیب آرایه‌ای باابعاد بیشتر را می‌توان با آرایه‌ای باابعاد کمتر ایجاد کرد. خانه‌های آرایه توسط اندیس مشخص می‌شوند که یک عدد صحیح است، مثلاً خانه شماره ۵ یعنی خانه‌ای که اندیس‌اش ۵ است. هر آرایه‌ای یک اندیس شروع و یک اندیس پایان دارد که شماره‌های معتبر اندیس بین این دو خواهند بود. اگر اندیس شروع یک آرایه (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 = (۲–۱) * ۴ = ۱ * ۴ = ۴) البته ما فرض کرده‌ایم که آدرس شروع آرایه در حافظه ۰ است، یعنی ما آدرس شروع آرایه را نسبت به خود آرایه محاسبه می‌کنیم، یعنی نسبی است. اگر آدرس شروع ارائه در حافظه ۰ نیست باید نتیجه فرمول قبلی را با آدرس شروع آرایه در حافظه جمع کنیم تا آدرس نسبی به مطلق تبدیل شود. در آرایه‌های ۲ بعد به بالا برای اینکه بتوانیم عناصر را به صورت صحیح از خانه‌هایی که ذخیره شده‌اند بازیابی نماییم بایستی مشخص گردد که اگر ذخیرهٔ عناصر به شکل سطری است بازیابی آن‌ها نیز به شکل سطری باشد و اگر ستونی است بازیابی آن‌ها به صورت ستونی باشد. | ## بخش 2: آرایه (ساختار داده) | آرایه‌های یک بعدی آرایه یک بعدی مجموعه متناهی از زوج‌ها به صورت ‹ اندیس، مقدار› است. آرایه‌های دو بعدی یک آرایه دو بعدی مجموعه‌ای با m×n عنصر داده‌ای است که هر عنصر آن با یک جفت اندیس مشخص می‌شود. هر سطر شامل عناصری است که اندیس‌های اول آن‌ها برابر است و هر ستون شامل عناصری هستند که اندیس‌های دوم آن‌ها برابر هستند. آرایه‌های چندبعدی آرایه n بعدی مجموعه‌ای از m1×m2×…×mn عنصر داده‌ای است که هر عنصر توسط n اندیس نظیر i1,i2,…,in مشخص می‌شوند. آرایه‌های چند بعدی در حافظه به صورت دنباله‌ای از خانه‌های پشت سر هم ذخیره می‌شوند. ویژگی آرایه‌ها (۱) آرایه‌ها به دوروش سطری وستونی پیاده‌سازی می‌شوند: روش سطری پیمایش و ذخیرهٔ آرایه‌ها در پیمایش سطری آرایه‌ها اندیس‌های خانه‌های آرایه از سمت راست تغییر می‌کنند به‌طوری‌که اندیس سمت چپ به صورت ثابت باقی می‌ماند و یک واحد یک واحد به اندیس سمت راست اضافه می‌شود تا زمانی‌که به ماکسیمم مقدار خود برسد که در این لحظه یک واحد به اندیس سمت چپ اضافه می‌شود و دوباره اندیس سمت راست شروع به افزایش می‌یابد و این کار تا زمانی ادامه پیدا می‌کند که هر ۲ اندیس به ماکسیمم مقدار خود برسد. روش ستونی پیمایش و ذخیرهٔ آرایه‌ها در روش ستونی اندیس‌های آرایه از سمت چپ شروع به افزایش می‌کنند یعنی اندیس‌های سمت چپ یک واحد یک واحد اضافه می‌شوند تا زمانی که به ماکسیمم مقدار خود برسند که در این لحظه یک واحد اندیس سمت راست اضافه می‌شود و دوباره اندیس سمت چپ از ۱ شروع به افزایش می‌کند و این کار تا زمانی انجام می‌گیرد که تمامی اندیس‌ها به ماکسیمم مقدار خود برسند. b11 , b21, b31 , b12 , b22 , b32 , b13 , b23 , b33 , b14 , b24 , b34 (۲) نمایش حافظه برای آرایه‌های چندبعدی از بردار پیروی می‌کنند برای ماتریس‌ها اشیای داده اولین سطر، سپس اشیای داده دومین سطر و به همین ترتیب ذخیره می‌شود تا یک نمایش حافظه ترتیبی از تمام عناصر آرایه داشته باشیم. (۳) توصیفگر آرایه مانند برداراست با این تفاوت که حدود بالا و پایین هر بعد نگهداری می‌شود. آرایه‌های پویا آرایه پویا// آرایه‌ای است که اندازه‌اش در زمان اجرا با عمل درج یا حذف عناصر در آن تغییر می‌کند. درج عنصری در آرایه برای درج عنصری در آرایه تعدادی از عناصر باید به سمت پایین منتقل شوند تا عنصر جدید در محل مورد نظر قرار گیرد. اگر بخواهیم عنصر جدید در مکان k ام آرایه درج شود کلیه عناصر از k به بعد باید شیفت داده شوند، سپس عنصر در مکان Kام ذخیره شود. بدترین حالت زمانی اتفاق می‌افتد که بخواهیم عنصر جدید را در مکان اول آرایه درج کنیم در این حالت تعداد جابجایی‌ها برابر است با n می‌شود. n تعداد عناصری که در آرایه درج شده‌اند را نشان می‌دهد و ربطی به طول آرایه ندارد. برای حذف عنصری که در مکان k ام قرار دارد، کلیه عناصر از k+1 به بعد باید به سمت بالا شیفت داده شوند. | ## بخش 3: آرایه (ساختار داده) | در بدترین حالت تعداد جابجایی‌ها برابر با n-1 است وقتی که اولین عنصر آرایه حذف می‌شود. n تعداد عناصری که در آرایه درج شده‌اند را نشان می‌دهد و ربطی به طول آرایه ندارد. همان‌طور که مشاهده می‌شود عملیات درج و حذف در آرایه به‌طور متوسط منجر به انتقال نصف عناصر آرایه می‌شود. بنابراین در مواردی که مجموعه عناصر داده‌ای به‌طور مکرر در حال اضافه و حذف هستند آرایه خطی روش کارآمدی برای ذخیرهٔ داده‌ها نیست. آرایه‌های شرکت پذیر(انجمنی) ویژگی مهم آرایه‌ها که تاکنون مطرح شد، روش دستیابی به یک عنصر خاص ،ازطریق یک نوع شمارشی به نام اندیس است.عناصر آرایه برحسب این اندیس مرتب هستند و بااستفاده از مقادیر اندیس می‌توان به هر عنصر آرایه دست یافت در بعضی از برنامه‌های کاربردی مطلوب است که از طریق نام (بدون استفاده از اندیس) بتوان به اطلاعات دست یافت. به عنوان مثال، به ترتیب نام دانشجو و نمره دانشجوی [grade[i],name[iاسامی افراد کلاس را می‌توان با دو آرایه نشان داد در این حالت، یک ترتیب ضمنی با استفاده از اندیس دانشجوی i وجود دارد. نمایش چندجمله‌ای‌ها به کمک آرایه همۀ چندجمله‌ای‌ها را می‌توان به کمک آرایه‌ها پیاده‌سازی کرد. مثلاً می‌توان بزرگترین درجه‌ای که در چندجمله‌ای می‌تواند وجود داشته باشد به عنوان Max در نظر گرفت، در این صورت می‌توان آرایه‌ای تعریف کرد که تعداد سلول‌های ان برابر با Max+1 باشد . پس از ذخیره چندجمله‌ای‌ها در داخل آرایه‌ها می‌توان اعمالی مانند جمع چندجمله‌ای و ضرب چندجمله‌ای را انجام داد. روش قبل برای ذخیره‌سازی چندجمله‌ای ممکن است مناسب نباشد برای مثال چندجمله‌ای شما ممکن است x^1000+1 باشد. روش دیگری نیز برای ذخیره چندجمله‌ای‌ها وجود دارد در این روش از یک آرایه با دو سطر و k ستون استفاده می‌شود. سطر اول نشان‌دهندهٔ همۀ ضرایب است و سطر دوم نشان‌دهندهٔ توان متناسب با هر ضریب است. ماتریس پراکنده یا اسپارس برای ذخیرۀ یک ماتریس M*N می‌توان از یک آرایهٔ دو بعدی با m سطر و n ستون استفاده کرد. | ## جمع‌بندی | از آنجایی‌که ماتریس‌های اسپارس در عمل وجود دارند و برخی موارد اندازه‌های آن‌ها بسیار بزرگ است می‌بایست روش بهینه‌تری را برای ذخیره آن‌ها در کامپیوتر ارائه کنیم .