نوع داده آرایه

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

در علوم کامپیوتر ، یک نوع آرایه یک نوع داده است که مجموعه‌ای از عناصر ( مقادیر یا متغیرها ) را نشان می‌دهد که هر کدام توسط یک یا چند شاخص (کلیدهای شناسایی) انتخاب می‌شوند که می‌توانند در زمان اجرا در طول اجرای برنامه محاسبه شوند. چنین مجموعه ای معمولاً یک متغیر آرایه ، مقدار آرایه یا به سادگی آرایه نامیده می شود. [1] بر اساس قیاس با مفاهیم ریاضی بردار و ماتریس ، انواع آرایه با یک و دو شاخص اغلب نوع برداری و نوع ماتریس نامیده می شوند.، به ترتیب. به طور کلی تر، یک نوع آرایه چند بعدی را می توان یک نوع تانسور نامید . [2]

پشتیبانی زبان برای انواع آرایه ممکن است شامل انواع داده‌های آرایه داخلی خاص، برخی ساختارهای نحوی (سازنده‌های نوع آرایه ) باشد که برنامه‌نویس ممکن است از آن‌ها برای تعریف این گونه انواع و اعلام متغیرهای آرایه و نمادهای ویژه برای نمایه‌سازی عناصر آرایه استفاده کند. [1] به عنوان مثال، در زبان برنامه نویسی پاسکال ، اعلان type MyTable = array [1..4,1..2] of integerیک نوع داده آرایه جدیدی به نام تعریف می کند MyTable. سپس اعلان var A: MyTableمتغیری Aاز آن نوع را تعریف می‌کند که مجموعه‌ای از هشت عنصر است که هر کدام یک متغیر عدد صحیح است که با دو شاخص مشخص می‌شود. در برنامه پاسکال، آن عناصر A[1,1]، A[1,2], A[2,1], …, , نشان داده می شوند A[4,2]. [3] انواع آرایه های خاص اغلب توسط کتابخانه های استاندارد زبان تعریف می شوند .

لیست‌های پویا نیز نسبت به آرایه‌های پویا رایج‌تر و ساده‌تر هستند . انواع آرایه عمدتاً از انواع رکورد متمایز می شوند زیرا به آنها اجازه می دهند شاخص های عنصر در زمان اجرا محاسبه شوند، مانند تخصیص پاسکال A[I,J] := A[N-I,2*J]. در میان چیزهای دیگر، این ویژگی به یک عبارت تکراری اجازه می دهد تا به طور دلخواه بسیاری از عناصر یک متغیر آرایه را پردازش کند.

در زمینه های نظری تر، به ویژه در نظریه نوع و در توصیف الگوریتم های انتزاعی ، اصطلاحات "آرایه" و "نوع آرایه" گاهی اوقات به یک نوع داده انتزاعی (ADT) اشاره دارد که آرایه انتزاعی نیز نامیده می شود یا ممکن است به یک آرایه انجمنی اشاره داشته باشد . مدل ریاضی با عملیات اساسی و رفتار یک نوع آرایه معمولی در بیشتر زبان‌ها - اساساً مجموعه‌ای از عناصر که توسط شاخص‌های محاسبه‌شده در زمان اجرا انتخاب می‌شوند.

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

تاریخچه

زبان برنامه نویسی هاینز روتیشاوزر Superplan (1949-1951) شامل آرایه های چند بعدی بود. اگرچه روتیشاوزر توضیح می‌دهد که چگونه یک کامپایلر برای زبانش باید ساخته شود، اما آن را پیاده‌سازی نکرد.

زبان‌های اسمبلی و زبان‌های سطح پایین مانند BCPL [4] معمولاً از آرایه‌ها پشتیبانی نحوی ندارند.

به دلیل اهمیت ساختارهای آرایه برای محاسبات کارآمد، اولین زبان های برنامه نویسی سطح بالا، از جمله FORTRAN (1957)، COBOL (1960)، و Algol 60 (1960) از آرایه های چند بعدی پشتیبانی می کنند.

آرایه های انتزاعی

یک ساختار داده آرایه را می توان به صورت ریاضی ساختار داده انتزاعی ( آرایه انتزاعی ) با دو عملیات مدل کرد.

get ( A , I ): داده های ذخیره شده در عنصر آرایه A که اندیس های آن عدد صحیح I هستند .
set ( A , I , V ): آرایه ای که با تنظیم مقدار آن عنصر به V به دست می آید .

این عملیات برای ارضای بدیهیات مورد نیاز است [5]

دریافت ( مجموعه ( A , I , V ), I ) =  V
دریافت ( مجموعه ( A , I , V ), J ) =  دریافت ( A , J ) اگر I  ≠  J

برای هر آرایه حالت A ، هر مقدار V ، و هر تاپل I ، J که عملیات برای آنها تعریف شده است.

اصل اول به این معنی است که هر عنصر مانند یک متغیر رفتار می کند. اصل دوم به این معنی است که عناصر با شاخص های متمایز به عنوان متغیرهای متمایز رفتار می کنند ، به طوری که ذخیره یک مقدار در یک عنصر بر مقدار هیچ عنصر دیگری تأثیر نمی گذارد.

این بدیهیات هیچ محدودیتی برای مجموعه تاپل‌های شاخص معتبر I قائل نمی‌شوند ، بنابراین این مدل انتزاعی را می‌توان برای ماتریس‌های مثلثی و دیگر آرایه‌های با شکل عجیب استفاده کرد.

پیاده سازی ها

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

از سوی دیگر، برخی از زبان‌های برنامه‌نویسی انواع آرایه‌های آزادتری را ارائه می‌کنند که امکان نمایه‌سازی با مقادیر دلخواه، مانند اعداد ممیز شناور ، رشته‌ها ، اشیاء ، ارجاعات و غیره را فراهم می‌کنند. چنین مقادیر شاخصی را نمی‌توان به یک بازه محدود کرد. فاصله ثابت بنابراین، این زبان ها معمولاً اجازه می دهند عناصر جدید دلخواه در هر زمان ایجاد شوند. این انتخاب مانع از اجرای انواع آرایه به عنوان ساختارهای داده آرایه می شود. یعنی، آن زبان‌ها از نحو آرایه‌مانند برای پیاده‌سازی معنایی آرایه‌های انجمنی عمومی‌تر استفاده می‌کنند، و بنابراین باید توسط یک جدول هش یا برخی ساختار داده‌های جستجوی دیگر پیاده‌سازی شوند .

پشتیبانی زبان

آرایه های چند بعدی

تعداد شاخص های مورد نیاز برای تعیین یک عنصر را بعد ، ابعاد یا رتبه نوع آرایه می گویند. (این نامگذاری با مفهوم بعد در جبر خطی تعارض دارد، [6] که در آن تعداد عناصر است. بنابراین، آرایه ای از اعداد با 5 سطر و 4 ستون، بنابراین 20 عنصر، گفته می شود که دارای بعد 2 در زمینه های محاسباتی است. ، اما نشان دهنده ماتریسی با ابعاد 4 در 5 یا 20 در ریاضیات است. همچنین معنای علوم کامپیوتر "رتبه" مشابه معنای آن در جبر تانسور است اما به مفهوم جبر خطی رتبه یک ماتریس نیست .)

یک آرایه دو بعدی که به عنوان یک آرایه یک بعدی از آرایه های یک بعدی (ردیف ها) ذخیره می شود.

بسیاری از زبان ها فقط از آرایه های یک بعدی پشتیبانی می کنند. در آن زبان ها، یک آرایه چند بعدی معمولاً با یک بردار Iliffe نشان داده می شود ، یک آرایه یک بعدی از ارجاعات به آرایه هایی با یک بعد کمتر. یک آرایه دو بعدی، به طور خاص، به عنوان بردار اشاره گر به ردیف های آن پیاده سازی می شود. بنابراین یک عنصر در ردیف i و ستون j از آرایه A با نمایه سازی دوگانه ( A [ i ][ j ] در نماد معمولی) قابل دسترسی است. این روش شبیه سازی آرایه های چند بعدی امکان ایجاد آرایه های ناهموار را فراهم می کند، جایی که هر ردیف ممکن است اندازه متفاوتی داشته باشد - یا به طور کلی، جایی که محدوده معتبر هر شاخص به مقادیر همه شاخص های قبلی بستگی دارد.

این نمایش برای آرایه های چند بعدی در نرم افزارهای C و C++ کاملاً رایج است. با این حال، C و C++ از فرمول نمایه‌سازی خطی برای آرایه‌های چند بعدی استفاده می‌کنند که با اندازه ثابت زمان کامپایل، به‌عنوان مثال توسط int A[10][20]یا int A[m][n]، به جای سنتی ، اعلان می‌شوند int **A. [7]

نماد نمایه سازی

اکثر زبان های برنامه نویسی که از آرایه ها پشتیبانی می کنند، عملیات ذخیره و انتخاب را پشتیبانی می کنند و دستور خاصی برای نمایه سازی دارند. زبان های اولیه از پرانتز استفاده می کردند، به عنوان مثال A(i,j)، مانند FORTRAN. دیگران براکت های مربع را انتخاب می کنند، به عنوان مثال A[i,j]یا A[i][j]، مانند الگول 60 و پاسکال (برای تمایز از استفاده از پرانتز برای فراخوانی تابع ).

انواع فهرست

انواع داده‌های آرایه اغلب به عنوان ساختارهای آرایه پیاده‌سازی می‌شوند: با شاخص‌ها محدود به مقادیر صحیح (یا کاملاً مرتب شده)، محدوده‌های شاخص ثابت در زمان ایجاد آرایه، و آدرس‌دهی عناصر چند خطی. این مورد در اکثر زبان های "نسل سوم" بود و هنوز هم در مورد اکثر زبان های برنامه نویسی سیستم ها مانند Ada ، C و C++ وجود دارد. با این حال، در برخی زبان‌ها، انواع داده‌های آرایه دارای معنای آرایه‌های انجمنی، با شاخص‌هایی از نوع دلخواه و ایجاد عنصر پویا هستند. این مورد در برخی از زبان های اسکریپت نویسی مانند Awk و Lua و برخی از انواع آرایه های ارائه شده توسط C++ استاندارد وجود دارد. کتابخانه ها

بررسی مرزها

برخی از زبان‌ها (مانند پاسکال و مدولا) برای هر دسترسی، محدودیت‌ها را بررسی می‌کنند، یک استثنا ایجاد می‌کنند یا برنامه را لغو می‌کنند، زمانی که هر شاخصی خارج از محدوده معتبر خود باشد. کامپایلرها ممکن است اجازه دهند این چک‌ها خاموش شوند تا ایمنی را با سرعت معامله کنند. زبان های دیگر (مانند FORTRAN و C) به برنامه نویس اعتماد دارند و هیچ بررسی انجام نمی دهند. کامپایلرهای خوب همچنین ممکن است برنامه را تجزیه و تحلیل کنند تا محدوده مقادیر ممکنی که این شاخص ممکن است داشته باشد را تعیین کند و این تجزیه و تحلیل ممکن است منجر به حذف کرانه ها شود .

مبدا فهرست

برخی از زبان‌ها، مانند C، تنها انواع آرایه‌های مبتنی بر صفر را ارائه می‌کنند ، که حداقل مقدار معتبر برای هر شاخصی 0 است. این انتخاب برای اجرای آرایه و محاسبات آدرس مناسب است. با زبانی مانند C، یک اشاره گر به داخل هر آرایه را می توان تعریف کرد که به طور نمادین به عنوان شبه آرایه ای عمل می کند که شاخص های منفی را در خود جای می دهد. این فقط به این دلیل کار می کند که C در هنگام استفاده یک شاخص را در مقابل کران ها بررسی نمی کند.

زبان‌های دیگر فقط انواع آرایه‌های یک‌پایه را ارائه می‌کنند که در آن هر شاخص با 1 شروع می‌شود. این قرارداد سنتی در ریاضیات برای ماتریس ها و دنباله های ریاضی است . چند زبان مانند پاسکال و لوا از انواع آرایه های مبتنی بر n پشتیبانی می کنند که حداقل شاخص های قانونی آنها توسط برنامه نویس انتخاب می شود. شایستگی نسبی هر انتخاب موضوع بحث های داغ بوده است. نمایه سازی مبتنی بر صفر می تواند از خطاهای off-by-one یا fencepost جلوگیری کند ، [8] به طور خاص برای (i=0;i<5;i+=1) بر اساس 0 (5-0) بار تکرار می شود، در حالی که در محدوده نیمه باز مبتنی بر 1 معادل برای (i=1;i<6;i+= 1) 6 به خودی خود یک چنین خطای بالقوه ای است که معمولاً به طول()+1 نیاز دارد و محدوده شامل بر اساس 1 برای (i=1;i<=5;i+=1) تکرار (5-1)+1 بار است. .

بالاترین شاخص

رابطه بین اعداد ظاهر شده در یک اعلان آرایه و شاخص آخرین عنصر آن آرایه نیز بر اساس زبان متفاوت است. در بسیاری از زبان ها (مانند C)، باید تعداد عناصر موجود در آرایه را مشخص کرد. در حالی که در موارد دیگر (مانند پاسکال و ویژوال بیسیک دات نت ) باید مقدار عددی شاخص آخرین عنصر را مشخص کرد. نیازی به گفتن نیست که این تمایز در زبان هایی که شاخص ها از 1 شروع می شوند، مانند Lua بی اهمیت است .

جبر آرایه ای

برخی از زبان های برنامه نویسی از برنامه نویسی آرایه پشتیبانی می کنند ، که در آن عملیات و توابع تعریف شده برای انواع داده های خاص به طور ضمنی به آرایه هایی از عناصر آن نوع گسترش می یابد. بنابراین می توان A + B را برای اضافه کردن عناصر مربوط به دو آرایه A و B نوشت . معمولاً این زبان‌ها هم ضرب عنصر به عنصر و هم حاصل ضرب ماتریس استاندارد جبر خطی را ارائه می‌کنند ، و اینکه کدام یک از اینها توسط عملگر * نشان داده می‌شود، براساس زبان متفاوت است.

زبان‌هایی که قابلیت‌های برنامه‌نویسی آرایه‌ای را ارائه می‌کنند، از زمان نوآوری‌ها در این زمینه از APL گسترش یافته‌اند . اینها قابلیت‌های اصلی زبان‌های دامنه خاص مانند GAUSS ، IDL ، Matlab و Mathematica هستند. آنها یک مرکز اصلی در زبان های جدیدتر، مانند جولیا و نسخه های اخیر Fortran هستند. این قابلیت‌ها همچنین از طریق کتابخانه‌های برنامه‌نویسی استاندارد برای سایر زبان‌های برنامه‌نویسی عمومی (مانند کتابخانه NumPy برای پایتون ) ارائه می‌شوند.

انواع رشته ها و آرایه ها

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

پرس و جوهای محدوده فهرست آرایه

برخی از زبان‌های برنامه‌نویسی عملیاتی را ارائه می‌کنند که اندازه (تعداد عناصر) یک بردار، یا به‌طور کلی‌تر، محدوده هر شاخص یک آرایه را برمی‌گرداند. در C و C++ آرایه‌ها از تابع اندازه پشتیبانی نمی‌کنند ، بنابراین برنامه‌نویسان اغلب مجبورند متغیر جداگانه‌ای را برای نگهداری اندازه اعلام کنند و آن را به عنوان یک پارامتر جداگانه به رویه‌ها ارسال کنند.

عناصر یک آرایه تازه ایجاد شده ممکن است دارای مقادیر تعریف نشده باشند (مانند C)، یا ممکن است دارای یک مقدار "پیش فرض" خاص مانند 0 یا یک اشاره گر تهی (مانند جاوا) تعریف شوند.

در C++ یک شی std::vector عملیات ذخیره ، انتخاب و الحاق را با ویژگی های عملکردی که در بالا توضیح داده شد، پشتیبانی می کند. بردارها را می توان برای اندازه آنها پرس و جو کرد و می توان اندازه آنها را تغییر داد. عملیات کندتر مانند قرار دادن یک عنصر در وسط نیز پشتیبانی می شود.

برش

آرایه برش عملیات طول می کشد یک زیر مجموعه از عناصر از یک نهاد آرایه تایپ (ارزش یا متغیر) و سپس آنها را مونتاژ به عنوان نهاد آرایه تایپ دیگر، احتمالا با دیگر شاخص. اگر انواع آرایه‌ها به‌عنوان ساختارهای آرایه‌ای پیاده‌سازی شوند، بسیاری از عملیات برش مفید (مانند انتخاب یک آرایه فرعی، تعویض شاخص‌ها یا معکوس کردن جهت شاخص‌ها) را می‌توان با دستکاری بردار ناخالصی ساختار بسیار کارآمد انجام داد . برش های ممکن به جزئیات پیاده سازی بستگی دارد: برای مثال، FORTRAN اجازه می دهد یک ستون از یک متغیر ماتریس را برش دهید، اما نه یک ردیف، و آن را به عنوان یک بردار در نظر بگیرید. در حالی که C اجازه می دهد یک ردیف از یک ماتریس برش داده شود، اما نه یک ستون.

از سوی دیگر، سایر عملیات برش زمانی امکان پذیر است که انواع آرایه ها به روش های دیگر پیاده سازی شوند.

تغییر اندازه

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

برای آرایه های یک بعدی، این تسهیلات ممکن است به عنوان یک عملیات " append( A , x )" ارائه شود که اندازه آرایه A را یک افزایش می دهد و سپس مقدار آخرین عنصر را روی x قرار می دهد. انواع آرایه های دیگر (مانند رشته های پاسکال) یک عملگر الحاقی را ارائه می دهند که می تواند همراه با برش برای رسیدن به آن اثر و موارد دیگر استفاده شود. در برخی از زبان ها، اختصاص یک مقدار به یک عنصر از یک آرایه، در صورت لزوم، آرایه را به طور خودکار گسترش می دهد تا آن عنصر را نیز شامل شود. در سایر انواع آرایه، یک برش را می توان با آرایه ای با اندازه های مختلف جایگزین کرد و عناصر بعدی بر این اساس شماره گذاری مجدد می شوند - مانند تخصیص لیست پایتون " A "[5:5] = [10,20,30]، که سه عنصر جدید (10،20، و 30) را قبل از عنصر " A [5] وارد می کند." آرایه های قابل تغییر اندازه از نظر مفهومی شبیه لیست ها هستند و این دو مفهوم عبارتند از مترادف در برخی از زبان ها

یک آرایه توسعه پذیر را می توان به عنوان یک آرایه با اندازه ثابت، با شمارنده ای که تعداد عناصر واقعی در حال استفاده را ثبت می کند، پیاده سازی کرد. عملیات appendفقط شمارنده را افزایش می دهد. تا زمانی که کل آرایه استفاده شود، زمانی که appendعملیات ممکن است شکست بخورد. این یک پیاده سازی از یک آرایه پویا با ظرفیت ثابت است، مانند stringنوع پاسکال. روش دیگر، appendعملیات ممکن است آرایه زیربنایی را با اندازه بزرگتر دوباره تخصیص دهد و عناصر قدیمی را در ناحیه جدید کپی کند.

همچنین ببینید

منابع

  1. ^ a b Robert W. Sebesta (2001) مفاهیم زبان های برنامه نویسی . ادیسون-وسلی. ویرایش چهارم (1998)، ویرایش پنجم (2001)، شابک  9780201385960
  2. «مقدمه ای بر تانسورها | هسته TensorFlow» . تنسورفلو _
  3. ^ K. Jensen and Niklaus Wirth، راهنمای کاربر PASCAL و گزارش . اسپرینگر. چاپ شومیز (1386) 184 صفحه، ISBN 978-3540069508 
  4. جان میچل، مفاهیم زبان های برنامه نویسی . انتشارات دانشگاه کمبریج.
  5. لوکام، سوزوکی (1979)، "تأیید عملیات آرایه، رکورد و نشانگر در پاسکال". ACM Transactions on Programming Languages ​​and Systems 1 (2)، 226-244.
  6. ^ تعریف ماتریس را ببینید
  7. برایان دبلیو کرنیگان و دنیس ام. ریچی (1988)، زبان برنامه نویسی C. پرنتیس هال، ص. 81.
  8. ^ Edsger W. Dijkstra ، " چرا شماره گذاری باید از صفر شروع شود "

پیوندهای خارجی