ساختار داده ها

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

در علوم کامپیوتر ، ساختار داده، سازماندهی، مدیریت و فرمت ذخیره سازی داده است که امکان دسترسی و اصلاح کارآمد را فراهم می کند. [1] [2] [3] به طور دقیق تر، یک ساختار داده مجموعه ای از مقادیر داده، روابط بین آنها، و توابع یا عملیاتی است که می تواند روی داده ها اعمال شود، [4] یعنی یک ساختار جبری است . در مورد داده ها

استفاده

ساختارهای داده به عنوان پایه ای برای انواع داده های انتزاعی (ADT) عمل می کنند. ADT شکل منطقی نوع داده را تعریف می کند. ساختار داده شکل فیزیکی نوع داده را پیاده سازی می کند. [5]

انواع مختلفی از ساختارهای داده برای انواع مختلف برنامه ها مناسب هستند و برخی از آنها برای کارهای خاص بسیار تخصصی هستند. برای مثال، پایگاه‌های داده رابطه‌ای معمولاً از شاخص‌های B-tree برای بازیابی داده‌ها استفاده می‌کنند، [6] در حالی که پیاده‌سازی‌های کامپایلر معمولاً از جداول هش برای جستجوی شناسه‌ها استفاده می‌کنند. [7]

ساختارهای داده وسیله ای برای مدیریت کارآمد مقادیر زیادی از داده ها برای استفاده هایی مانند پایگاه های داده بزرگ و خدمات نمایه سازی اینترنتی فراهم می کنند. معمولاً ساختارهای داده کارآمد کلید طراحی الگوریتم‌های کارآمد هستند. برخی از روش‌های طراحی رسمی و زبان‌های برنامه‌نویسی بر ساختار داده‌ها، به‌جای الگوریتم‌ها، به‌عنوان عامل سازمان‌دهی کلیدی در طراحی نرم‌افزار تأکید دارند. از ساختارهای داده می توان برای سازماندهی ذخیره سازی و بازیابی اطلاعات ذخیره شده در حافظه اصلی و ثانویه استفاده کرد. [8]

پیاده سازی

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

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

مثالها

پایتون 3. نوع استاندارد hierarchy.png

انواع مختلفی از ساختارهای داده وجود دارد که عموماً بر اساس انواع داده های اولیه ساده تر ساخته شده اند. نمونه های معروف عبارتند از: [10]

  • یک بایت کوچکترین مقدار داده ای است که یک CPU کامپیوتر می تواند از حافظه به یک ثبات کپی کند یا در یک دستورالعمل واحد CPU برگرداند ، بنابراین بایت استریم کارآمدترین راه برای اجرای داده های بزرگ از طریق رایانه است، بنابراین پردازش جریانی است . رفر . هیچ CPU نمی تواند یک بیت واحد را از حافظه به یک ثبات یا برگشت کپی کند، زیرا هر بیت در حافظه بخشی از یک بایت است. [11]
  • آرایه تعدادی عنصر در یک ترتیب خاص است، معمولاً همه از یک نوع (بسته به زبان، عناصر منفرد ممکن است مجبور شوند همه یک نوع باشند یا تقریباً از هر نوع باشند). عناصر با استفاده از یک شاخص عدد صحیح برای تعیین عنصر مورد نیاز قابل دسترسی هستند. پیاده سازی های معمولی کلمات حافظه پیوسته را برای عناصر آرایه ها اختصاص می دهند (اما این همیشه یک ضرورت نیست). آرایه ها ممکن است با طول ثابت یا قابل تغییر اندازه باشند.
  • یک لیست پیوندی (که فقط لیست نامیده می شود ) مجموعه ای خطی از عناصر داده از هر نوع است که گره نامیده می شود، که در آن هر گره مقداری برای خود دارد و به گره بعدی در لیست پیوندی اشاره می کند. مزیت اصلی یک لیست پیوندی نسبت به یک آرایه این است که مقادیر همیشه می توانند به طور موثر درج و بدون جابجایی بقیه لیست حذف شوند. با این حال، برخی عملیات دیگر، مانند دسترسی تصادفی به یک عنصر خاص، در لیست ها نسبت به آرایه ها کندتر هستند.
  • رکورد (همچنین تاپل یا ساختار نیز نامیده می شود ) یک ساختار داده انبوه است . رکورد مقداری است که حاوی مقادیر دیگری است، معمولاً به تعداد و دنباله ثابت و معمولاً با نام نمایه می شوند. عناصر رکوردها معمولاً فیلدها یا اعضا نامیده می شوند .
  • اتحاد یک ساختار داده ای است که مشخص می کند کدام یک از تعدادی از انواع اولیه مجاز ممکن است در نمونه های آن ذخیره شوند، به عنوان مثال float یا long integer . در تضاد با یک رکورد ، که می تواند شامل یک شناور و یک عدد صحیح تعریف شود. در حالی که در یک اتحادیه، در یک زمان تنها یک مقدار وجود دارد. فضای کافی برای گنجاندن گسترده ترین نوع داده عضو اختصاص داده شده است.
  • یک اتحادیه برچسب‌گذاری‌شده (همچنین به نام نوع ، رکورد متغیر ، اتحادیه تفکیک‌شده ، یا اتحادیه منفصل نیز نامیده می‌شود ) حاوی یک فیلد اضافی است که نوع فعلی آن را نشان می‌دهد تا ایمنی نوع پیشرفته‌تر را نشان دهد.
  • یک شی یک ساختار داده است که شامل فیلدهای داده است، مانند یک رکورد، و همچنین روش های مختلفی که بر روی محتوای داده عمل می کنند. یک شی یک نمونه در حافظه از یک کلاس از یک طبقه بندی است. در زمینه برنامه نویسی شی گرا ، رکوردها به عنوان ساختارهای داده قدیمی ساده شناخته می شوند تا آنها را از اشیا متمایز کنند. [12]

علاوه بر این، هش‌ها ، نمودارها و درخت‌های دودویی دیگر ساختارهای داده رایج هستند.

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

اکثر زبان‌های اسمبلی و برخی از زبان‌های سطح پایین ، مانند BCPL (زبان برنامه‌نویسی ترکیبی پایه)، فاقد پشتیبانی داخلی برای ساختارهای داده هستند. از سوی دیگر، بسیاری از زبان‌های برنامه‌نویسی سطح بالا و برخی از زبان‌های اسمبلی سطح بالاتر، مانند MASM ، دارای نحو خاص یا پشتیبانی داخلی دیگر برای ساختارهای داده خاص، مانند رکوردها و آرایه‌ها هستند. به عنوان مثال، زبان‌های C (نخست مستقیم BCPL) و پاسکال به ترتیب از ساختارها و رکوردها، علاوه بر بردارها ( آرایه‌های یک‌بعدی ) و آرایه‌های چند بعدی پشتیبانی می‌کنند. [13] [14]

بیشتر زبان های برنامه نویسی دارای نوعی مکانیسم کتابخانه ای هستند که امکان استفاده مجدد از ساختار داده توسط برنامه های مختلف را فراهم می کند. زبان‌های مدرن معمولاً دارای کتابخانه‌های استانداردی هستند که رایج‌ترین ساختارهای داده را پیاده‌سازی می‌کنند. به عنوان مثال می توان به کتابخانه قالب استاندارد C++ ، چارچوب مجموعه های جاوا و چارچوب دات نت مایکروسافت اشاره کرد.

زبان‌های مدرن نیز عموماً از برنامه‌نویسی مدولار ، جداسازی بین رابط یک ماژول کتابخانه و اجرای آن پشتیبانی می‌کنند. برخی از آنها انواع داده غیرشفاف را ارائه می دهند که به مشتریان اجازه می دهد جزئیات پیاده سازی را پنهان کنند. زبان های برنامه نویسی شی گرا مانند C++ ، جاوا و اسمال تاک معمولاً از کلاس ها برای این منظور استفاده می کنند.

بسیاری از ساختارهای داده شناخته شده دارای نسخه های همزمان هستند که به چندین رشته محاسباتی اجازه می دهد تا به یک نمونه عینی از یک ساختار داده به طور همزمان دسترسی داشته باشند. [15]

همچنین مشاهده کنید

منابع

  1. ^ کورمن، توماس اچ. لیزرسون، چارلز ای. ریست، رونالد ال. استاین، کلیفورد (2009). مقدمه ای بر الگوریتم ها، ویرایش سوم (ویرایش سوم). مطبوعات MIT. شابک 978-0262033848.
  2. بلک، پل ای. (15 دسامبر 2004). "ساختار داده" . در پیترز، وردا؛ بلک، پل ای. (ویرایش‌ها). فرهنگ لغت الگوریتم ها و ساختارهای داده [آنلاین] . موسسه ملی استاندارد و فناوری . بازیابی شده در 2018-11-06 .
  3. «ساختار داده» . دایره المعارف بریتانیکا . 17 آوریل 2017 . بازیابی شده در 2018-11-06 .
  4. ^ وگنر، پیتر؛ ریلی، ادوین دی (29-08-2003). دایره المعارف علوم کامپیوتر . چیچستر، انگلستان: جان وایلی و پسران. ص 507-512. شابک 978-0470864128.
  5. «انواع داده انتزاعی» . ویرجینیا تک - ساختارهای داده و الگوریتم‌های CS3 .
  6. گاوین پاول (2006). "فصل 8: ساخت مدل های پایگاه داده با عملکرد سریع" . شروع طراحی پایگاه داده انتشارات Wrox . شابک 978-0-7645-7490-0.
  7. «1.5 کاربردهای جدول هش» . دانشگاه رجینا - آزمایشگاه CS210: جدول هش .
  8. «وقتی داده‌ها خیلی بزرگ هستند که در حافظه اصلی جای نمی‌گیرند» . homes.sice.indiana.edu .
  9. ^ دوبی، آرسی (2014). بیوتکنولوژی پیشرفته: برای دانشجویان کارشناسی ارشد و کارشناسی ارشد بیوتکنولوژی و سایر علوم زیستی . دهلی نو: اس چاند. شابک 978-81-219-4290-4. OCLC  883695533 .
  10. سیمور، لیپشوتز (2014). ساختارهای داده (ویرایش اول تجدید نظر شده). دهلی نو، هند: آموزش مک گراو هیل. شابک 9781259029967. OCLC  927793728 .
  11. ^ کلین، مارشال. "سؤالات متداول C++: قوانین مربوط به بایت ها، کاراکترها و کاراکترها" .
  12. والتر ای. براون (۲۹ سپتامبر ۱۹۹۹). "نکته زبان C++: انواع POD" . آزمایشگاه ملی شتاب دهنده فرمی . بایگانی شده از نسخه اصلی در 2016-12-03 . بازبینی شده در 6 دسامبر 2016 .
  13. «راهنمای GNU C» . بنیاد نرم افزار آزاد بازیابی 2014-10-15 .
  14. ون کانیت، مایکل (سپتامبر ۲۰۱۷). "پاسکال رایگان: راهنمای مرجع" . پاسکال رایگان.
  15. مارک مویر و نیر شاویت. "ساختارهای داده همزمان" (PDF) . cs.tau.ac.il .

کتابشناسی

ادامه مطلب

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