گردآورد (نوع داده انتزاعی)
در علوم رایانه، یک گردآورد[1] (به انگلیسی: collection) یا گنجانه (به انگلیسی: container) یک گروهبندی از عناصر داده با سایز متغیر (ممکن است سایز صفر باشد) است، که این عناصر برای مسالهای که قصد حل کردن آن را داریم، دارای اهمیت مشترک میباشند، و لازم است تا به یک روش نظارتشده روی آنها عملیاتی به صورت دستجمعی انجام شود.
بهطور کلی دادهها از یک نوع هستند و یا در پشتیبانی از وراثت زبانها از اجداد مشترک از یک نوع نشات گرفتهاند یک مجموعه یک مفهوم قابل استفاده برای انواع داده انتزاعی و نه تجویز خاص پیادهسازی به عنوان یک بتن ساختمان داده, هر چند اغلب یک انتخاب متعارف وجود دارد .
نمونههایی از مجموعههای شامل لیست ها, مجموعهها , چند دسته ها , درخت ها و گراف ها است .
آرایه (یا جدول) با اندازه ثابت معمولاً به عنوان یک مجموعه در نظر گرفته نمیشود به دلیل نگهداری مقدار ثابت از دادهها اگر چه آنها معمولاً نقش مهمی در پیادهسازی مجموعه ایفا میکنند . آرایههایی با اندازه متغیر بهطور کلی مجموعه در نظر گرفته میشوند.
مجموعه های خطی
هم چنین ببینید : فهرست ساختار داده
بسیاری از مجموعهها یک ترتیب خطی خاص را تعریف میکنند.و بعضی داده ساختارها نیازی به پیادهسازی خطی نیست ; برای مثال یک صف اولویت که اغلب پیادهسازی آن با پشته است که یک نوع درخت است. مجموعههای مهم خطی عبارتند از:
- لیست
- پشته
- صف
- صف اولویت دار
- صف دوطرفه
- صف دو طرفه اولویت دار
فهرست
مقاله اصلی :لیست (نوع داده انتزاعی)
یک لیست یا دنباله، یک نوع داده انتزاعی است که نمایانگر تعداد شمارش پذیری از مقادیر مرتب است، بطوریکه یک مقدار ممکن است بیش از یکبار مشاهده شود. یک لیست نمایش کامپیوتری از مفهوم دنبالههای متناهی در ریاضیات است.[2] نمونههایی از عملیات در لیستها جستجو برای یک داده در لیست و تعیین محل آن (اگر آن وجود دارد) , حذف یک آیتم داده از لیست، اضافه کردن یک آیتم داده به لیست در یک مکان خاص و غیره است .اگر عملیات اصلی در لیست، اضافه کردن اقلام داده در یک انتها و حذف موارد داده در انتهای دیگر باشد یک صف یا FIFO به وجود میآید
پشته
مقاله اصلی :پشته
پشته یک ساختار داده LIFO (آخرین ورودی از همه زودتر خارج میشود : Last In First Out) با دو عملیات اصلی است: (push) که یک عنصر به بالای مجموعه اضافه میکند و (pop) عنصر بالای مجموعه را حذف میکند.
صف
مقاله اصلی : صف
صف لیستی است که عمل افزودن دادهها درون آن از انتهای لیست و عمل حذف دادهها از ابتدای لیست انجام میشود.
مثل یک صف نانوایی دادهها به ترتیب ورود پشت سر هم در صف قرار میگیرند. بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود، این به این معنی است که شیوهٔ عملکرد صف براساس سیاست FIFO است.
صف اولویت
مقاله اصلی :صف اولویت
در صف اولویتدار برای هر داده اولویتی - نه لزوماً منحصربهفرد - مشخص میشود. صف اولویت را میتوان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستمعامل کامپیوتر هم برای مدیریت پردازشها از صفهای اولویت استفاده میکند.
صف دو طرفه
مقاله اصلی :صف دوطرفه
یک صف را تعمیم میبخشد به طوری که بتوان هم از ابتدای صف و هم از انتهای صف حذف یا اضافه کرد و دسترسی داشت. این ساختمان داده هم مانند صف از عملکرد بر اساس سیاست FIFO (خروج به ترتیب ورود) و هم مانند پشته از عملکرد بر اساس سیاست LIFO (خروج به ترتیب عکس ورود) پشتیبانی میکند
مجموعه های انجمنی
- دسته ها
- چند دسته ها
- آرایه های انجمنی.
دسته
در یک دسته یا (set)، ترتیب آیتمهای داده مهم نیست (یا نامشخص است) اما اقلام داده تکراری مجاز نیستند. نمونههایی از عملیات در دستهها افزودن و حذف آیتمهای داده و جستجو برای اطلاعات در این دسته است. برخی از زبانها دسته را بهطور مستقیم پشتیبانی میکنند . در بقیه زبانها دسته میتواند توسط یک جدول هش با ارزش ساختگی پیادهسازی شود ; تنها کلید برای نمایندگی از دسته استفاده میشود.
چند دسته ای
در یک چند دسته ای یا multiset همانند یک دسته ترتیب دادهها مهم نیست اما در این مورد تکرار دادهها موارد مجاز است. نمونههایی از عملیات در multisets افزودن و حذف آیتمهای داده و تعیین اینکه چند تکرار از یک داده خاص در حال حاضر در multiset.وجود دارد . Multisets را میتوان با عمل مرتب سازی به لیست تبدیل کرد .
آرایه های انجمنی
در علوم رایانه، آرایهٔ ربطی، نگاشت، یا دیکشنری به نوع داده انتزاعی اطلاق میشود که از کلکسیونی از جفتهای (کلید، مقدار) تشکیل شدهاست، بطوریکه هر کلید ممکن حداکثر یکبار در کلکسیون ظاهر میشود. دلیل این نامگذاری این است که در این نوع آرایه هر مقدار به صراحت به یک کلید «ربط» داده شدهاست (در انگلیسی: Associated) در حالیکه در نوع عادی آرایه، ربط دهی به صورت ضمنی انجام میشود؛ یعنی هر مقدار بهطور ضمنی مرتبط با یک اندیس (در انگلیسی: Index) است و نیازی به ذخیرهٔ کلید (اندیس) وجود ندارد. به دلیل صریح بودن ربط دهی در این نوع آرایه، آن را آرایهٔ «ربطی» (به انگلیسی Associative Array) مینامند، که برخی آن را آرایهٔ انجمنی نیز ترجمه کردهاند.[3]
گراف
مقاله اصلی : گراف
یک داده ساختار گراف اساساً از یک مجموعهٔ متناهیِ زوجهای مرتب موسوم به یال شامل واحدهایی به نام رأس یا گره تشکیل میشود؛ همانطور که در ریاضیات به ازای یک یال (u,v) میگوییم که u به v میرود یا u و v مجاورند. همچنین میتوان به هر یال یک گراف یک عدد نسبت داد که در این صورت گراف وزن دار به وجود می آید .
نمونههایی از عملیات بر روی نمودارها، عبور و جستجو هستند که ارتباطات اقلام داده را دنبال میکنند که به دنبال برخی از ویژگیهای خاص هستند.
درخت
درخت ساختار دادهٔ پر استفاده است که شبیه به یک ساختار درختی با مجموعهای از گرههای متصل به هم است. درخت یک گراف همبند بدون دور است. اکثر نویسندگان این قید را نیز اضافه میکنند که گراف باید بدون جهت باشد. به علاوه بعضی قید بدون وزن بودن یالها را نیز اضافه میکنند.
پیاده سازی
در یک زبان بعضی از مجموعهها ممکن است انواع دادههای اولیه باشند مانند لیست در حالی که در مجموعههای پیچیده تر انواع داده کامپوزیت در کتابخانهها پیادهسازی شدهاند . مثالها عبارتند از:
منابع
- «گردآوری دادهها» [رایانه و فنّاوری اطلاعات] همارزِ «data collection»؛ منبع: گروه واژهگزینی. جواد میرشکاری، ویراستار. دفتر دوم. فرهنگ واژههای مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۳۷-۰ (ذیل سرواژهٔ گردآوری دادهها)
- Fry, Christopher; Abelson, Harold; Sussman, Gerald; Sussman, Julie (1985). "Structure and Interpretation of Computer Programs". Computer Music Journal. 9 (3): 81. doi:10.2307/3679579. ISSN 0148-9267.
- Masum, Hassan (2001-03-01). "Review of Data Structures and Algorithms in Java (2nd ed)". ACM SIGACT News. 32 (1): 3. doi:10.1145/568438.568441. ISSN 0163-5700.
- Feuerstein, Steven; Pribyl, Bill; Dawes, Chip (2007) [1999]. "Collections in PL/SQL". Oracle PL/SQL Language Pocket Reference. Pocket Reference (4 ed.). Sebastopol, California: O'Reilly Media, Inc. p. 63. ISBN 9780596551612. Retrieved 2017-06-26.
Collections are implemented as TYPEs. As with any programmer-defined type, you must first define the type; then you can declare instances of that type.