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

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

اگر شما به عنوان متخصص و یا تازه‌کار وارد حوزه برنامه ­نویسی کامپیوتر شوید، ساختمان داده کلمه­‌ای است که به طور مداوم به گوشتان خواهد رسید. بنابراین برای تبدیل شدن به یک برنامه نویس موفق و حرفه­‌ای و همچنین یک متخصص علوم و مهندسی کامپیوتر و فناوری اطلاعات (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) به هر یک از داده‌ها یک کلید متناظر با آن را داد و بطور کاراتری داده­‎ها را جستجو کرد.

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

جمع‌بندی

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

مطالب مرتبط

همه مقالات

فیلم‌های آموزشی معماری کامپیوتر

چارت درسی رشته علوم کامپیوتر

آی تی یا برنامه نویسی

گرایش محاسبات علمی رشته علوم کامپیوتر