نویسنده : ساجده فدائی - دانشجو ارشد کامپیوتر صنعتی شریف ساختمان داده به چه معنا است؟
اگر شما به عنوان متخصص و یا تازه‌کار وارد حوزه برنامه نویسی کامپیوتر شوید، ساختمان داده کلمه‌ای است که به طور مداوم به گوشتان خواهد رسید. بنابراین برای تبدیل شدن به یک برنامه نویس موفق و حرفه‌ای و همچنین یک متخصص علوم و مهندسی کامپیوتر و فناوری اطلاعات (IT) باید دانش خوبی در زمینه ساختمان دادهساختمان داده چیست
ساختمان داده واقعا چیست؟ این صفحه عالی توضیح داده که ساختمان داده چیست و گفته چرا باید ساختمان داده‌ها را یاد بگیریم؟ و انواع و عملیات روی ساختمان داده را گفته داشته باشید.
ساختمان داده تکنیکی برای ذخیره و سازماندهی داده‌ها برای استفاده‌ای کارآمد از آنها است. در علوم کامپیوتر، ساختمان دادهآموزش ساختمان داده و الگوریتم
هر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم میکند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است ها به گونه‌ای طراحی می‌شوند که قابلیت اجرا با الگوریتم‌های مختلف را داشته باشند. به همین دلیل، هرساله مقالات زیادی در حوزه علم ساختمان داده منتشر می‌شوند که به بررسی و تشخیص داده ساختارهای مهم و کاربردی‌تر می‌پردازند.
بطور کلی دو دسته بندی در ساختارهای داده‌ای وجود دارد:
- ساختمان داده‌های خطی
- ساختمان داده‌های غیرخطی
ساختمان داده های خطی:
ساختمان داده خطی، ساختاری است که در آن هر عنصر به عنصر قبلی و بعدی خود متصل است و عناصر به صورت متوالی و خطی در حافظه کامپیوتر ذخیره می‌شوند. پیاده سازی ساختمان داده‌های خطی بسیار آسان است و تنها در یک اجرا میتوان به داده‌ها دسترسی داشت و آنها را پیمایش کرد.
انواع ساختمان داده‌های خطی عبارتند از:
- آرایه
- پشته
- صف
- لیست پیوندی
آرایه (Array):
این نوع از ساختمان داده اساسی‌ترین و پایه‌ای‌ترین نوع ساختار داده‌ای است، که عناصری از یک نوع (type) را ذخیره میکند.
به داده‌های ذخیره شده در هر موقعیت از یک آرایه مقدار مثبتی به نام شاخص (Index) داده می‌شود. این شاخص به پیداکردن مکان یک عنصر در آرایه کمک میکند. به طور مثال اگر در برنامه‌ای قرار باشد که قیمت ده خودرو ذخیره شود، با داشتن یک آرایه نیازی به ایجاد ده متغیر جداگانه نخواهد بود و به وسیله آرایه میتوان همه اعداد را در یک متغیر ذخیره کرد. بنابراین علاوه بر کم شدن خطوط کد برنامه، مصرف حافظه نیز کاهش مییابد.
پشته (Stack):
این نوع ساختمان داده از قانون LIFO (Last In – First Out) تبعیت میکند، یعنی آخرین عنصری که وارد پشته می‌شود، از همه زودتر حذف می‌گردد. در پشته عمل اضافه کردن یک عنصر (Push) و برداشتن و حذف داده (Pop) فقط در یک طرف آن، بنام بالای پشته انجام می‌شود.
این ساختار را با مثال کتاب‌های چیده شده بر روی هم میتوان توضیح داد. برای دسترسی به اولین کتاب، باید تمام کتاب‌های قرار گرفته در بالای کتاب اول برداشته شوند.
صف (Queue):
این ساختار تقریبا شبیه به پشته است با این تفاوت که از قانون FIFO (First In – First Out) پیروی میکند. به این معنا که اولین عنصر ورودی اولین عنصر خروجی نیز خواهد بود. کلمات Front (به یک عنصر قبل از عنصر ابتدایی اشاره میکند) و rear (به آخرین عنصر اشاره میکند) دو عبارتی هستند که در ساختار صف به کار برده می‌شوند. به عملیات درج در صف (Enqueue) و به عمل حذف (Dequeue) گفته می‌شود.
این نوع ساختار داده‌ای را میتوان با مثال از افرادی که برای سوار شدن به اتوبوس صف می‌کشند توضیح داد. اولین نفر در صف این شانس را دارد که از صف خارج شده و سوار اتوبوس شود در حالیکه نفر آخر، آخرین فردی است که از صف خارج می‌شود.
لیست پیوندی (Linked list) :
لیست‌های پیوندی شامل دنباله‌ای از عناصر است که در این ساختمان داده، عناصر در قالب نود ذخیره می‌شوند. هر نود شامل عناصر داده و اشاره گر آدرس است.
اشاره گرها بعنوان راهنما به نودی که در کنار عنصر در دنباله قرار دارد اشاره میکند. داده‌ها در یک لیست پیوندی ممکن است به هر شکل اعم از رشته، اعداد و یا کاراکتر به صورت منحصربفرد و یا تکراری ذخیره شوند. مزیت مهم لیست پیوندی این است که ترتیب قرارگرفتن داده‌ها در آن با ترتیب قرارگرفتن آنها در حافظه متفاوت است.
ساختمان داده های غیرخطی:
در این نوع ساختار داده، عناصر به صورت متوالی ذخیره نمی‌شوند و از یک رابطه سلسله مراتبی بین عناصر بنام پدر و فرزند استفاده می‌کنند.
به عبارت دیگر داده‌ها از طریق ایجاد یک رابطه به یکدیگر وصل می‌شوند. در ساختارهای خطی هر عنصر می‌توانست به دو عنصر (قبل و یا بعد از خود) متصل شود، در حالیکه در ساختارهای غیرخطی امکان اتصال هر عنصر به بیش از دو عنصر دیگر امکانپذیر است.
درخت و گراف رایج‌ترین ساختارهای غیرخطی هستند.
درخت (Tree) :
یک ساختار درختی، شامل نودهایِ متصل بهمِ متعددی است که از طریق یال‌ها به یکدیگر وصل می‌شوند. ساختار درختی یک ساختار سلسله مراتبی است که به صورت رابطه پدر – فرزندی تعریف می‌شود. در درخت‌ها تنها یک مسیر از نود ریشه به هر نود وجود دارد. انوع مختلفی از درخت‌ها براساس ساختارشان وجود دارد مانند: درخت دودویی (binary tree) ، AVL (یک نوع درخت جستجو دودویی با ارتفاع متوازن) و درخت قرمز-سیاه.
گراف (Graph):
گراف یک ساختار غیرخطی است که ازتعداد مشخصی نود و یال تشکیل شده، نودها برای ذخیره داده‌ها بکار می‌روند و یال‌ها ارتباط میان نودها را نشان می‌دهند.
تفاوت میان درخت و گراف در این است که قانون مشخصی برای ارتباط میان نودها وجود ندارد. گراف، کاربرد زیادی در دنیای واقعی مانند شبکه‌های مخابراتی، به ویژه شبکه‌های اجتماعی مانند LinkdIn, facebook دارد.
در شبکه فیسبوک هر کاربر بعنوان یک نود در نظر گرفته می‌شود و ارتباط آن با دیگر کاربران از طریق یال‌ها مشخص می‌گردد.
تابع هش یا درهم ساز (Hashmap):
در جدول Hash از جفتهای کلید-مقدار برای ذخیره سازی داده‌ها استفاده می‌شود. این ساختار می‌تواند هم به صورت ساختارهای خطی و هم غیرخطی در نظر گرفته شود.
این ساختمان داده با استفاده از یک تابع درهمسازی (Hash Function) یک داده را دریافت و آن را به یک کلید (Key) مناسب تبدیل میکند. به این ترتیب میتوان با استفاده از یک جدول هش (Hashmap) به هر یک از داده‌ها یک کلید متناظر با آن را داد و بطور کاراتری داده‌ها را جستجو کرد.
جدول خلاصه تفاوت‌ها
| خلاصه تفاوت ها | ||||
|---|---|---|---|---|
| ردیف | موارد | ساختار خطی | ساختار غیرخطی | |
| 1 | پایه و اساس | داده ها به صورت خطی و متوالی به یکدیگر متصل می شوند و آرایش پیدا می کنند. | داده ها به صورت سلسله مراتبی و غیرخطی چیده می شوند. | |
| 2 | انواع | آرایه، صف، پشته، لیست پیوندی | درخت و گراف | |
| 3 | پیاده سازی | آسان | سخت | |
| 4 | پیمایش و جستجو | تنها با یک اجرا میتوان به تمام عناصر دسترسی داشت. | باچندین اجرا میتوان به تمام عناصر دسترسی داشت. | |
| 5 | آرایش | هرعنصر، تنها به یک عنصر قبل و بعد خود متصل است. | هر عنصر می تواند به چندین عنصر متصل باشد. | |
| 6 | سطوح | در یک سطح و بصورت متوالی آرایش پیدا می یابند. | عناصر در چندین سطح مختلف آرایش پیدا می کنند. | |
| 7 | استفاده از حافظه | غیربهینه | بسیار بهینه | |
| 8 | پیچیدگی زمانی | با افزایش داده ها، زیاد می شود. | با افزایش اندازه ورودی ثابت می ماند. | |
| 9 | کاربرد | گسترش نرم افزارها | پردازش تصویر و هوش مصنوعی | |
جمع‌بندی
امروزه با افزایش داده‌ها ، نیاز به طراحی و ساخت ساختمان داده‌های پیچیده‌تری وجود دارد. در این مقاله سعی کردیم درک مختصری از انواع ساختمان داده ارائه و تفاوت‌های کلیدی بین ساختار داده خطی و غیرخطی را بیان کنیم. با این حال، ساختار داده‌های مختلف کاربردهای متفاوتی دارند. یادگیری ساختارهای داده، درک آسان زبان‌های برنامه نویسی مختلف را امکانپذیر میکند، بنابراین اولین قدم مهم برای یک برنامه نویس خوب، داشتن درک اولیه از مفاهیم ساختار داده است.
