بایگانی برچسب‌ها : array

آرایه انجمنی Associative array

آرایه انجمنی یا Associative array چیست؟

آرایه انجمنی (Associative array) در زبان‌های برنامه‌نویسی یک نوع داده‌ی انتزاعی است متشکل از مجموعه‌ای از دوتایی‌های (کلید، مقدار) یا (Key, Value) به طوری که هر مقدار با یک کلید در تناظر می‌باشد و کلیدهای موجود در مجموعه نیز تکراری نباشند. آرایه‌های انجمنی با نام‌هایی همچون نقشه (Map) و لغت نامه (Dictionary) نیز شناخته می‌شوند.

در آرایه‌های انجمنی تناظر میان کلیدها و مقادیر اصطلاحا اتصال (Binding) نامیده می‌شود. مهم‌ترین و رایج‌ترین اعمالی که روی این نوع داده قابل انجام می‌باشد عبارت است از افزودن (Insert یا Add) یک جفت کلید و مقدار به مجموعه، حذف (Remove یا Delete) یک جفت کلید و مقدار، تغییر مقدار تخصیص یافته به یک کلید و یافتن مقدار متناظر با یک کلید. برای افزودن یک جفت کلید و مقدار یا تغییر مقدار متناظر با یک کلید لازم است هم کلید و هم مقدار متناظر با آن در قالب آرگومان مشخص شود اما حذف یا یافتن مقدار متناظر با یک کلید تنها مبتنی بر کلید انجام می‌شود.

دو روش مهم برای ایجاد آرایه‌های انجمنی، استفاده از جدول درهم سازی (Hash table) و درخت جستجو (Search tree) می‌باشد. بسیاری از زبان‌های برنامه‌نویسی امروزی از آرایه‌های انجمنی تحت عناوین متفاوتی در قالب کتابخانه‌های استاندارد خود پشتیبانی می‌کنند (برای مثال در بسیاری از زبان‌ها از جمله C++، آرایه‌های انجمنی با عنوان map شناخته می‌شوند).

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

در مثال زیر نحوه‌ی ایجاد یک آرایه انجمنی به نام $weight در زبان PHP نمایش داده شده است. در این نمونه، 3 جفت کلید و مقدار در مجموعه مشاهده می‌شود که عبارات Alex و Rory و Paul کلیدهای این آرایه انجمنی هستند و مقادیر 40 و 50 و 45 به ترتیب به آنها تخصیص داده شده است. در این مثال عبارت $weight[‘Paul’] مقدار متناظر با کلید Paul یعنی 45 را خواهد داشت.

$weight = array("Alex"=>"40", "Rory"=>"50", "Paul"=>"45");
echo "Paul weighs" . $weight['Paul'] . " kilograms.";

پیوندهای پیشنهادی تک دیک

لینک واژه در ویکیپدیا

آرایه Array

آرایه یا Array چیست؟

آرایه (Array) ساختمان داده ای است متشکل از چندین عنصر (اِلِمان) که برای دسترسی به آن‌ها معمولا از یک اندیس استفاده می‌شود. موقعیت هر عنصر در حافظه از روی این اندیس محاسبه می‌شود.

ساده‌ترین نوع آرایه، آرایه‌ی خطی (Linear) یا تک بُعدی است. به عنوان مثال آرایه‌ای از نوع اعداد صحیح (Integer) با تعداد 5 عنصر را در زبان C++ در نظر بگیرید. این عناصر به اندیس‌های 0 تا 4 این آرایه منتسب می‌شوند. در صورتی که آدرس شروع آرایه در مموری برابر 1000 باشد با درنظر گرفتن اینکه هر مقدار Integer، چهار بایت حافظه نیاز دارد بنابراین پنج عنصر فوق آدرس‌های 1000 تا 1019 حافظه رم را اشغال خواهند کرد.

نوع متداول دیگری از آرایه‌ها که دو بعدی هستند با عنوان ماتریس نیز شناخته می‌شوند. معمولا برای دسترسی به هر عنصر در این آرایه‌ها از دو اندیس استفاده می‌شود، یکی برای سطر و دیگری برای ستون. به عنوان مثال اگر A یک آرایه‌ی دوبعدی با 3 سطر و 3 ستون باشد و اندیس شروع برابر 0 باشد A[1][2] به عنصر موجود در سطر دوم و ستون سوم اشاره می‌کند.

با وجود اینکه کاربرد آرایه‌های با ابعاد بالاتر به اندازه‌ی آرایه‌های خطی و دو بعدی نیست اما محدودیتی در ابعاد آرایه‌ها وجود ندارد. در عین حال تمامی عناصر یک Array باید از یک نوع باشند. معادل ریاضی آرایه، چندتایی (Tuple) می‌باشد.

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

آرایه در زبان‌های برنامه نویسی کاربرد بسیار زیادی دارد و از مهم‌ترین انواع ساختمان داده‌ها به شمار می‌رود. حتی بسیاری از ساختمان داده‌های دیگر نظیر صف، پشته، رشته و … نیز با کمک آرایه پیاده‌سازی می‌شوند.

در اغلب زبان‌های برنامه نویسی، اندیس پیش فرض اولین عنصر آرایه برابر با 0 (نظیر خانواده زبان ‌های C و بیسیک) یا 1 (نظیر MATLAB و Fortran) می‌باشد و کران بالای اندیس‌ها براساس نیاز تعیین می‌شود.

در قطعه کد زیر نحوه‌ی تعریف و مقداردهی اولیه‌ی آرایه‌ای به نام Length با پنج عنصر در زبان C++ نمایش داده شده است.

int Length[5] = {16, 20, 27, 40, 45};

به منظور تجسم این Array می‌توان تصویر زیر را در نظر گرفت. اعداد بالای خانه‌های این تصویر نمایانگر اندیس عنصر متناظر هستند.

آرایه Array
تجسم تصویری یک Array با 5 عنصر

پیوندهای پیشنهادی تک دیک

لینک واژه در ویکیپدیا

صف Queue

صف یا Queue چیست؟

صف (Queue) عنوان ساختمان داده‌ای است که مجموعه‌ای از المان‌ها (عناصر) را بر اساس اصل FIFO (خروج به ترتیب ورود) در خود نگه‌داری می‌کند.

برای Queue دو عمل اصلی تعریف می‌شود. عمل Enqueue که عنصر جدیدی را به انتهای آن (که rear نامیده می‌شود) اضافه می‌کند و عمل Dequeue که عنصری را از ابتدای آن (که front نامیده می‌شود) حذف می‌کند. به این ترتیب اولین عنصری که به یک Queue افزوده می‌شود اولین عنصری خواهد بود که از آن حذف خواهد شد. از این رو، صف‌ها را نوعی ساختمان داده‌ی FIFO به شمار می‌آورند. در برخی از پیاده‌سازی‌ها، عملی به نام Front یا Peek نیز تعریف می‌شود که مقدار المان اول را بدون حذف آن برمی‌گرداند.

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

پیاده‌سازی صف

هرچند از نظر تئوری می‌توان صف‌ها را به صورت نامتناهی و بدون محدودیت در ظرفیت تجسم نمود اما در صورتی که صف را توسط آرایه‌ای با طول ثابت پیاده سازی کنیم ظرفیت آن ثابت خواهد بود. با درنظر گرفتن این آرایه به صورت یک دایره می‌توان یک صف حلقوی ایجاد نمود. در این نوع Queue لزوما انتهای آرایه، انتهای صف نیست بلکه می‌توان از فضای خالی به وجود آمده در ابتدای آرایه (به دلیل اعمال Dequeue)، برای افزودن عناصر جدید استفاده نمود. در صورتی که Queue پر باشد و بخواهیم عنصر جدیدی به آن اضافه کنیم حالتی به نام سرریز (Overflow) رخ می‌دهد. به طور مشابه در صورتی که بخواهیم روی یک Queue خالی، عمل Dequeue را انجام دهیم حالت زیرریز (Underflow) رخ خواهد داد.

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

اعمال حذف و اضافه روی یک صف
اعمال حذف و اضافه روی یک Queue

پیوندهای پیشنهادی تک دیک

لینک واژه در ویکیپدیا