کنکور کامپیوتر

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

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

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

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

نمایش هش

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

خلاصه تفاوت ها
ردیفمواردساختار خطیساختار غیرخطی
1 پایه و اساس داده ها به صورت خطی و متوالی به یکدیگر متصل می شوند و آرایش پیدا می کنند. داده ها به صورت سلسله مراتبی و غیرخطی چیده می شوند.
2 انواع آرایه، صف، پشته، لیست پیوندی درخت و گراف
3 پیاده سازی آسان سخت
4 پیمایش و جستجو تنها با یک اجرا میتوان به تمام عناصر دسترسی داشت. باچندین اجرا میتوان به تمام عناصر دسترسی داشت.
5 آرایش هرعنصر، تنها به یک عنصر قبل و بعد خود متصل است. هر عنصر می تواند به چندین عنصر متصل باشد.
6 سطوح در یک سطح و بصورت متوالی آرایش پیدا می یابند. عناصر در چندین سطح مختلف آرایش پیدا می کنند.
7 استفاده از حافظه غیربهینه بسیار بهینه
8 پیچیدگی زمانی با افزایش داده ها، زیاد می شود. با افزایش اندازه ورودی ثابت می ماند.
9 کاربرد گسترش نرم افزارها پردازش تصویر و هوش مصنوعی

جمع‌بندی

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

همچنین هر گونه سوالی در مورد کلاس‌های آنلاین کنکور کامپیوتر و یا تهیه فیلم‌ها و یا رزرو مشاوره تک جلسه‌ای تلفنی با استاد رضوی دارید می‌توانید به طرق زیر از تیم پشتیبانی بپرسید:

آی دی تلگرام تیم پشتیبانی:     konkurcomputer_admin@

تماس با پشتیبانی:   09378555200

امتیازدهی4.5555555555556 1 1 1 1 1 1 1 1 1 14.56 امتیاز (9 رای)
بارگذاری نظرات