ساختمان داده های خطی و غیر خطی چه تفاوتی دارند؟

ساختمان داده به چه معنا است؟

اگر شما به عنوان متخصص و یا تازه‌کار وارد حوزه برنامه ­نویسی کامپیوتر شوید، ساختمان داده کلمه­‌ای است که به طور مداوم به گوشتان خواهد رسید. بنابراین برای تبدیل شدن به یک برنامه نویس موفق و حرفه­‌ای و همچنین یک متخصص علوم و مهندسی کامپیوتر و فناوری اطلاعات (IT) باید دانش خوبی در زمینه ساختمان دادهساختمان داده چیستساختمان داده واقعا چیست؟ این صفحه عالی توضیح داده که ساختمان داده چیست و گفته چرا باید ساختمان داده‌ها را یاد بگیریم؟ و انواع و عملیات روی ساختمان داده را گفته داشته باشید.

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

بطور کلی دو دسته بندی در ساختارهای داده­‌ای وجود دارد:

1. ساختمان داده‌های خطی
2. ساختمان داده‌های غیرخطی

ساختمان داده‌ های خطی:

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

انواع ساختمان داده‌های خطی عبارتند از:

• آرایه
• پشته
• صف
• لیست پیوندی

آرایه (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) به هر یک از داده‌ها یک کلید متناظر با آن را داد و بطور کاراتری داده­‎ها را جستجو کرد.

 جدول خلاصه تفاوت‌ها

جمع‌بندی

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

مطالب مرتبط

همه مقالات

خرید فیلم نکته و تست مدار منطقی

مهندسی کامپیوتر شریف

دکتری کامپیوتر چند واحد است؟

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