آشنایی با ساختمان داده ها (Data Structure)

ترجمه و تالیف : پشتیبانی راکت
تاریخ انتشار : 13 خرداد 98
خواندن در 3 دقیقه
دسته بندی ها : آموزشی

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

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

آشنایی با ساختمان داده ها (Data Structure)

برخی دیگر از ساختمان داده ها عبارتند از: پشته، صف و گراف

  • پشته Stack : یک پشته که به آن یک سیستم LIFO یا آخرین ورودی اولین خروجی است، نیز میگویند، یک لیست خطی است که در آن عملیات اضافه شدن عناصر تنها از یک انتهای آن موسوم به بالای پشته Top صورت میگیرد.
  • صف Queue : یک صف که به آن سیستم FIFO یا اولین ورودی اولین خروجی است، نیز میگویند، یک لیست خطی است که در آن عملیات حذف عناصر تنها از یک انتهای لیست موسوم به ابتدا front لیست و اضافه شدن  عناصر به صف تنها از انتهای دیگر لیست، موسوم به انتهاRear لیست صورت میگیرد.
  • گراف : گاهی اوقات داده ها یک رابطه بین جفت عناصر موجود در طبیعت را بیان میکنند که لزوما بصورت سلسله مراتبی نیستند.

عملیات بر روی ساختمان داده ها

آشنایی با ساختمان داده ها (Data Structure)

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

چهار عمل اصلی در ساختمان داده ها عبارتنداز:

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

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

دو عمل زیر نیز در وضعیتهای خاص مورد استفاده قرار میگیرند :

  • مرتب کردن : عبارتست از قرار دادن رکوردها با یک نظم معین در کنار هم. مثلا با یک نظم الفبایی براساس یک کلید نام NAME یابا یک نظم عددی بر طبق یک کلید عددی NUMBER مانند شماره تامین اجتماعی یا شماره حساب بانکی.
  • ادغام کردن : ترکییب رکوردهای دو فایل مرتب شده ی مختلف و قرار دادن آنها در یک فایل مرتب شده ادغام کردن نام دارد.

عملیات دیگری نیز مانند کپی کردن و اتصال اطلاعات در ساختمان داده ها استفاده میشود.

روش ایجاد پشته یا  stack

 آشنایی با ساختمان داده ها (Data Structure)

پشته یا stack یکی از انواع ساختارهای داده ای است و برای ذخیره و بازیابی داده‌ ها کاربرد فراوانی دارد. پشته در برنامه نویسی کاربردهای بسیار زیادی دارد. الگوریتم و نحوه ی کار پشته ها به صورت LIFO است.

واژه ی LIFO مخفف عبارت Last In First Out است که این بدان معنی می باشد که همیشه آخرین ورودی اولین خروجی می باشد. این LIFO است که اساس کار پشته‌ ها را تشکیل داده و سبک بازیابی داده ای در پشته ها را سازماندهی می کند.

هر پشته قادر به انجام موارد زیر می باشد :

  • Init : پشته را می‌سازد.
  • push : یک آیتم را به بالای پشته اضافه می‌کند.
  • pop : آخرین آیتمی‌ که به پشته اضافه شده باشد را می خواند و سپس حذف می‌کند.
  •   isEmpty : مشخص می‌کند که آیا پشته دارای آیتم دیگری هست‌ یا خیر ( در واقع خالی بودن پشته را بررسی می کند).

برای پیاده سازی پشته از کلاس زیر می توان استفاده کرد:  

از کلاس بالا به شکل زیر می توانید استفاده کنید

نکته :

  • تابع top تنها مقدار بالای پشته را نمایش می دهد ولی همچنان در پشته مقدار آن خانه باقی می ماند.
  • پشته ی بالا را می توان به تعداد خانه های متفاوتی محدود کرد که با توجه به نیاز شما با تغییر متغیر $limit قابل تغییر است.

ایجاد صف یا queue

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

عملیات های صف :

چون صف مجموعه ای از عناصر است که عناصر از یک طرف به نام آخر صف به آن اضافه و از طرف جلوی صف از آن حذف میشوند، میتوان عملیات هایی بر اساس این تعریف برای صف در نظر گرفت. عملیات های صف عبارتنداز:

  • Enqueue : عنصری را به انتهای صف اضافه میکند.
  • Dequeue : عنصر جلوی صف را حذف میکند.
  • Peek : عنصر جلوی صف را بازیابی میکند ولی حذف نمیکند.
  • QueueEmpty : خالی بودن صف را بررسی میکند.
  • Clear  : تمام عناصر صف را حذف میکند.
  • Contains : مشخص میکند که عنصر خاصی در صف وجود دارد یا خیر.
  • CopyTo : محتویات صف را درآرایه ای از نوع Object کپی میکند.
  • ToArray : محتویات صف را در آرایه ای از نوع معین کپی میکند.
گردآوری و تالیف پشتیبانی راکت
آفلاین
user-avatar

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

دیدگاه‌ها و پرسش‌ها

برای ارسال نظر لازم است ابتدا وارد سایت شوید
در حال دریافت نظرات از سرور، لطفا منتظر بمانید