ساختمان داده چیست و چگونه آن را یاد بگیریم؟

اطلاعات یا «1» (Data) از موثرترین ابزارهای در دسترس هر کسبوکار و سازمانی است که میخواهد در جهان رقابتی و چالشی امروز بهترین باشد. هرچه اطلاعات بیشتر باشد، گزینهها و راهحلهای بهتری نیز برای مسائل و موانع پیشِ رو ایجاد میشود. «1 داده» (Data Structure) مجموعهای از دادهها و روابط میان آنها است. برنامهنویسان با استفاده از ساختارهای داده میتوانند دادهها را بهشکل کارآمدی ذخیره و پردازش کنند. ساختمان داده انواع مختلف بسیاری داشته و هر کدام مزیتها و معایب خود را دارند. در این مطلب از مجله فرادرس، یاد میگیریم که ساختمان داده 1 و مسیری برای یادگیری اصولی آن ارائه میدهیم.

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

ساختمان داده چیست؟

پیش از آنکه به ماهیت ساختمان داده پی ببریم، ابتدا باید با مفهوم «داده» (Data) آشنا شویم. به اطلاعاتی بهینه شده برای پردازش و ذخیره در «حافظه کامپیوتر» (Memory) داده گفته میشود. ساختمان داده روشی برای سازماندهی دادهها در حافظه کامپیوتر، بهگونهایست که بتوان آنها را پس از ذخیرهسازی، پردازش و سپس بهشکل موثری بازیابی کرد.

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

• ساختمان داده برابر است با دادههای مرتبط به علاوه اعمال عملیاتهای مجاز بر روی دادهها
• برنامه کامپیوتری برابر است با ساختمان داده بهعلاوه الگوریتم

بخشی مهم از هر سیستم نرمافزاری توسعه داده شدهای را ساختمان داده تشکیل میدهد؛ از همینرو، ساختمان داده را میتوان به عنوان یکی از مبانی مهم علوم کامپیوتر و مهندسی نرمافزار برشمرد.

اهمیت ساختمان داده چیست؟

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

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

ویژگی های ساختمان داده چیست؟

ساختمان داده روشی هدفمند برای سازماندهی دادهها است. از جمله ویژگیهای ساختمان داده میتوان به موارد زیر اشاره کرد:

• «خطی یا غیرخطی» (Linear or Non-Linear): این ویژگی مشخص کننده ترتیب دادهها است. اگر ترتیب دادهها متوالی باشد، به آن خطی و در غیر اینصورت غیرخطی میگویند.
• «ایستا و پویا» (Static and Dynamic): ساختمان دادهای ایستا است که ساختار، اندازه و موقعیت ثابتی در حافظه کامپیوتر داشته باشد. از طرفی دیگر ساختار، اندازه و موقعیت ساختمان داده پویا، بنا بر کاربرد میتواند متفاوت باشد.
• «پیچیدگی زمانی» (Time Complexity): معیار زمان در ساختمان داده بسیار حائز اهمیت است. «زمان اجرای» (Run Time) یک برنامه باید در محدودترین حالت ممکن باشد. هر چقدر زمان اجرا کوتاهتر باشد، یعنی سیستم طراحی شده دقیقتر است.
• «درستی» (Correctness): هر نوع دادهای باید واسط تعاملی داشته باشد. واسط تعاملی نشاندهنده مجموعهداده است و پیادهسازی ساختمان داده در واسط تعاملی باید دقیق باشد.
• «پیچیدگی فضایی» (Space Complexity): فضای موجود بر روی دستگاههای کاربری باید با دقت مدیریت شود. میزان استفاده مناسب از حافظه امری ضروری و میزان فضای اشغال شده کمتر، نشاندهنده عملکرد قابل قبول برنامه است.

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

انواع داده های پایه برای بررسی ساختمان داده چیست؟

تا اینجا یاد گرفتیم که ساختمان داده چیست و چه ویژگیهایی دارد. «انواع داده» (Data Types) عناصر پایهای در طبقهبندی دادهها هستند. نوع داده در واقع رابطی میان برنامهنویس و کامپایلر برای انتقال اطلاعات است. در فهرست زیر چند نمونه مهم و کاربردی از انواع داده را ملاحظه میکنید:

• «بولی» (Boolean)
• «صحیح» (Integer)
• «اعداد ممیز شناور» (Floating-Point Numbers)
• «اعداد ممیز ثابت» (Fixed-Point Numbers)
• «کاراکتر» (Character)
• «اشارهگرها» (Pointers)
• «رشته» (String)

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

نوع داده بولی

اعداد، متن و «بولی» (Boolean)، سه نوع عمده دادهها در یک برنامه کامپیوتری را تشکیل میدهند. بولی، نوع دادهایست که مقدار آن میتواند یکی از مقادیر «درست» (True)، «نادرست» (False)، «مثبت» (Positive) یا «منفی» (Negative) باشد. کاربرد نوع داده بولی در تایید «معتبر» (Valid) یا «نامعتبر» (Invalid) بودن داده است. در سیستمهای «دودویی» (Binary) از مقادیر ۰ و ۱ و از «عبارات بولی» (Boolean Expressions) در جبر، مقادیر منطقی و متغیرهای دودویی (Binary Variables) استفاده میشود.

نوع داده صحیح

نوع داده «صحیح» (Integer) قابلیت ذخیرهسازی اعداد مثبت، منفی و همچنین صفر را دارد. تمامی «عملگرهای حسابی» (Arithmetic Operations) بر روی نوع داده صحیح قابل پیادهسازی هستند. از آنجایی که نوع داده صحیح، بهازای هر مقدار عددی، ۴ بایت از فضای حافظه را اشغال میکند، در صورتیکه مقدار داده فراتر از این محدوده (Range) شمارشی باشد، «پایگاه داده» (Database) قادر به ذخیرهسازی مقادیر نخواهد بود.

اعداد ممیز شناور

نوع داده «ممیز شناور» (Floating-Point)، با استفاده از فرمولی که تناسبی میان محدوده و دقت برقرار میکند، مقادیر حقیقی را تخمین میزند. نیاز به سرعت پردازش سریع و سیستمهای حاوی مقادیر عددی بسیار بزرگ یا بسیار کوچک، از جمله موارد استفاده اعداد ممیز شناور است. بهطور معمول از توان نمایی با پایه ثابت برای تغییر مقیاس یک عدد و تخمین «ارقام معنیدار» (Significant Digits) استفاده میشود.

اعداد ممیز ثابت

ذخیرهسازی اعداد در دستگاههای الکترونیکی با استفاده از عبارات دودویی صورت میگیرد. به رشتهای با طول ثابت از مقادیر ۰ و ۱، عبارت دودویی گفته میشود. اعداد ممیز ثابت و شناور، دو نوع داده متفاوت برای نمایش اعداد دودویی هستند؛ انواع دادهای که نحوه تفسیر مقادیر ۰ و ۱ را بهوسیله عناصر سختافزاری و پردازشهای نرمافزاری مشخص میکنند. «اعداد ممیز ثابت» (Fixed-Point Numbers)، خود به دو دسته «با علامت» (Signed) و «بدون علامت» (Unsigned) تقسیم میشوند. از آنجایی که نوع داده بیت بدون علامت است، با علامت یا بدون علامت بودن عبارات دودویی بهطور صریح مشخص نیست. اما در معماری کامپیوتر، علامت اطلاعات بهطور ضمنی تعریف میشود.

نوع داده کاراکتر

اطلاعات حرفی یا «کاراکتر» (Character) با طول ثابت و نوع داده Char در فضای کامپیوتر ذخیره میشوند. صرفنظر از تعداد کاراکتر، داده میتواند «رشتهای» (String) از حروف، اعداد و دیگر نمادهای مورد پیشتیبانی پایگاه داده باشد. نوع داده رشته با طول ثابت یا متغیر قابلیت ذخیره نوع داده کاراکتر را دارد. همچنین مقادیر رشتهای با طول متغیر برخلاف مقادیر با طول ثابت، در خروجی و هنگام نمایش با کاراکتر «فاصله» (Space) بسط داده نمیشوند.

اشارهگرها

ذخیره و مدیریت خانههایی از حافظه کامپیوتر که بهصورت پویا تخصیص داده شدهاند از طریق «اشارهگرها» (Pointers) صورت میگیرد. از جمله نمونههایی که با نوع داده اشارهگر ذخیره میشوند، میتوان به نواع داده «شیء» (Object) و همچنین «آرایهای» (Arrays) از اشیاء اشاره کرد. «هیپ» (Heap) فضای حافظهای قابل پشتیبانی توسط زبانهای برنامهنویسی شیءگرا و «ساختارمند» (Structured) در جهت تخصیص حافظه پویا برای نوع داده شیء است.

نوع داده رشته

نوع داده «رشته» (String) مجموعهای پیوسته از کاراکترها است؛ این کاراکترها ممکن است بهشکل «ثابت لفظی» (Literal Constant) یا متغیر باشند. متغیرها ممکن است دارای طول ثابتی باشند و یا بتوان مقادیر آنها را تغییر داد. ساختار داده رشتهای اغلب به عنوان نوع دادهای شامل کاراکترهای متوالی و در غالب آرایهای از بایت ساخته میشود.

انواع ساختمان داده چیست؟

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

• «ساختمان داده ابتدایی» (Primitive Data Structure)
• «ساختمان داده غیرابتدایی» (Non-Primitive Data Structure)

در ادامه این مطلب، به توضیح هر یک از انواع ساختمان داده ابتدایی و غیر ابتدایی میپردازیم.

ساختمان داده ابتدایی

«ساختمان داده ابتدایی» (Primitive Data Structure)، بهطور مستقیم و مطابق با دستورالعملهای ماشین عمل میکند. انواع دادهای همچون صحیح (Int)، کاراکتر (Char)، اعشاری (Float/Double) و اشارهگرها، از جمله ساختارهای داده ابتدایی هستند که تنها یک مقدار را نگهداری میکنند.

ساختمان داده غیر ابتدایی

به ساختارهای داده پیچیده و نشأت گرفته از ساختارهای داده ابتدایی، «ساختمان داده غیر ابتدایی» (Non-Primitive Data Structure) گفته میشود. انواع داده غیر ابتدایی را میتوان به دو دسته زیر تقسیم کرد:

• «ساختمان داده خطی» (Linear Data Structure)
• «ساختمان داده غیرخطی» (Non-Linear Data Structure)

در ادامه، دو مورد ساختمان داده خطی و غیرخطی، همچنین چند نمونه پرکاربرد از هر کدام را مورد بررسی قرار میدهیم.

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

چیدمان دادههای موجود در «ساختمان داده خطی» (Linear Data Structure) بهصورت ترتیبی است؛ به این معنی که هر عنصر از ساختمان داده با عناصر قبل و بعد خود در ارتباط است. این ارتباط باعث میشود تا بتوان ساختاری خطی را در یک سطح و همچنین یک دور اجرا پیمایش کرد. بهخاطر ترتیبی بودن چیدمان حافظه کامپیوتر، پیادهسازی این نوع از ساختار داده کار راحتی است. در فهرست زیر چند نمونه ساختار داده خطی را ملاحظه میکنید:

• «آرایه» (Array)
• «لیست پیوندی» (Linked List)
• «پشته» (Stack)
• «صف» (Queue)
• «جدول هش» (Hash Table)

ساختارهای داده خطی با چیدمان ترتیبی عناصر، امکان دسترسی و پیمایش راحت دادهها را فراهم میکنند. در ادامه این مطلب از مجله فرادرس به شرح کامل نمونه ساختارهای داده خطی عنوان شده در فهرست بالا میپردازیم.

آرایه

«آرایه» (Array)، ساختاری با طول ثابت است که میتواند عناصر با نوع داده یکسان را در خود ذخیره کند. به عنوان مثال میتوان به آرایهای از عناصر با نوع داده صحیح، اعشاری، رشتهای یا حتی آرایهای از چند آرایه دیگر مانند آرایههای دو بعدی اشاره کرد. آرایهها «ایندکسگذاری شده» (Indexed) هستند؛ به این معنی که قابلیت «دسترسی تصادفی» (Random Access) دارند.

عملیات های آرایهای

از جمله عملیاتهای قابل اجرا بر روی ساختمان داده آرایه میتوان به موارد زیر اشاره کرد:

• «پیمایش» (Traverse): به ملاقات تک-تک عناصر آرایه و نمایش آنها در خروجی گفته میشود.
• «جستجو» (Search): عملیات جستجو عنصری در آرایه را گویند. برای جستجوی یک عنصر در آرایه، میتوان از مقدار یا «ایندکس» (Index) آن استفاده کرد.
• «بهروزرسانی» (Updata): عملیاتی که در آن مقدار یک عنصر در موقعیت یا همان ایندکسی خاص تغییر پیدا میکند.

امکان اجرای دو عملیات «درج» (Insert) و «حدف» (Delete) بهصورت مستقیم در ساختار داده آرایه وجود ندارد؛ چرا که اندازه آرایهها یکسان و غیرقابل تغییر است. به عنوان مثال اگر قصد داشته باشید عنصر جدیدی را به آرایهای از پیش تعریف شده اضافه کنید، ابتدا باید آریه تازهای با طول بزرگتر (۱ + طول فعلی) ساخته و پس از انتقال عناصر موجود قبلی، عنصر جدید را نیز به آن اضافه کنید. برای عمل حدف نیز، باید همین عمل را با طول آرایه جدید کوچکتر (۱ - طول فعلی) انجام دهیم.

کاربرد های ساختمان داده آرایه

به عنوان چند نمونه از کاربردهای آرایه، موارد زیر را در نظر داشته باشید:

• از آرایهها به عنوان اجزای سازنده در دیگر ساختمان دادهها همچون لیست پیوندی، هیپ، جدول هش، «بردارها» (Vectors) و «ماتریسها» (Matrices) استفاده میشود.
• عمده «الگوریتمهای مرتبسازی» (Sorting Algorithms) از جمله «مرتبسازی درجی» (Insertion Sort)، «مرتبسازی سریع» (Quick Sort)، «مرتبسازی حبابی» (Bubble Sort) و «مرتبسازی ادغامی» (Merge Sort) بر پایه ساختمان داده آرایه پیادهسازی میشوند.

بهطور خلاصه آرایهها، ساختارهای داده پایهای هستند که با بهرهگیری از آنها، پردازش ساختمان دادهها و الگوریتمهای پیچیده راحتتر میشود.

لیست پیوندی

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

• به عناصر موجود در یک لیست پیوندی «گره» (Node) گفته میشود.
• هر گره شامل یک کلید و اشارهگری به گره بعدی است.
• اشارهگری که «رأس» (Head) نامیده میشود، به اولین عنصر لیست پیوندی اشاره دارد.
• آخرین عنصر در لیست پیوندی، اشارهگره «دُم» (Tail) نام دارد.

در فهرست زیر، انواع مختلف لیستهای پیوندی را ملاحظه میکنید:

• «لیست پیوندی تک جهته» (Singly Linked List): در این نوع از لیست پیوندی، پیمایش عناصر تنها در جهتی مستقیم و رو به جلو امکانپذیر است.
• «لیست پیوندی دو جهته» (Doubly Linked List): لیستی پیوندی که در آن میتوان عناصر را در دو جهت رو به جلو و رو به عقب پیمایش کرد.
• «لیست پیوندی دایرهای» (Circular Linked List): نوعی از لیست پیوندی که در آن گره رأس با اشارهگری رو به عقب به گره دُم و گره دُم با اشارهگری رو به جلو به گره رأس اشاره میکند.

عنواین زیر، نمونه عملیاتهای قابل اجرا بر روی لیست پیوندی هستند:

• جستجو: با استفاده از جستجوی خطی ساده، اولین عنصر با کلید $$ k $$ در لیست پیوندی پیدا شده و اشارهگری به آن عنصر برگردانده میشود.
• درج: کلیدی در لیست پیوندی درج میشود. عملیات درج به سه حالت در لیست پیوندی امکانپذیر است؛ درج در ابتدای لیست، درج در انتها و درج در میانه لیست.
• حذف: حذف عنصر $$ x $$ از لیست پیوندی را گویند. حذف یک گره تنها در یک قدم امکانپذیر نیست. مانند درج، عملیات حذف نیز به سه حالت حذف از ابتدا، انتها و میانه انجام میشود.

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

• برای «مدیریت جدول نمادها» (Symbols Table Management) در طراحی کامپایلر از لیست پیوندی استفاده میشود.
• عمل تغییر سریع میان برنامههای کامپیوتری که با کلیدهای ترکیبی Alt + Tab انجام میشود را با لیست پیوندی دایرهای پیادهسازی میکنند.

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

پشته

پشته ساختاری «آخرین ورودی، اولین خروجی» (Last-In-First-Out | LIFO) است؛ در رویکرد LIFO، عنصر قرار گرفته در خانه آخر ساختمان داده، اولین عنصر در دسترس خواهد بود. ساختار داده پشته در زبانهای برنامهنویسی بسیاری پیادهسازی شده است. نام این ساختار داده، از پشته در جهان حقیقی الهام گرفته است؛ پشتهای از بشقابها.

عملیات های پشتهای

همانطور که در تصویر نیز مشاهده میکنید، دو عملیات پایهای قابل اجرا بر روی ساختار داده پشته از قرار زیر است:

• عملیات Push: به درج عنصر جدید در بالای پشته گفته میشود.
• عملیات Pop: حذف بالاییترین عنصر پشته و برگرداندن مقدار آن را گویند.

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

• تابع Peek: این تابع، بالاییترین عنصر پشته را بدون حذف آن برمیگرداند.
• تابع isEmpty: تابعی که خالی بودن یا نبودن پشته را بررسی میکند.
• تابع isFull: در این تابع، پر بودن یا نبودن پشته مورد بررسی قرار میگیرد.

برخی از کاربردهای رایج ساختمان داده پشته به شرح زیر است:

• از ساختار داده پشته در الگوریتمهایی مانند «محوطه تعویض خط» (Shunting-yard) برای تجزیه و ارزیابی عبارات ریاضی استفاده میشود.
• فراخوانی توابع در «برنامهنویسی بازگشتی» (Recursion Programming) از طریق ساختار داده پشته پیادهسازی میشوند.

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

صف

صف، ساختاری مبتنیبر رویکرد «ورودی اول، خروجی اول» (First-In-First-Out | FIFO) است. در این رویکرد، عنصر قرار گرفته در ابتدای ساختمان داده اولین عنصر در دسترس خواهد بود. مانند ساختار داده پشته، صف نیز در زبانهای برنامهنویسی پیادهسازی شده است. عنوان «صف» در این ساختار داده، نماد افرادی منتظر در صف است.

عملیات های ساختمان داده صف

همانطور که در تصویر زیر مشاهده میکنید، دو فرایند Enqueue و Dequeue، از جمله عملیاتهای اصلی قابل اجرا بر روی ساختار داده صف هستند:

• عملیات Enqueue: در این عملیات، عنصر جدیدی به انتهای صف اضافه میشود.
• عملیات Dequeue: عملیاتی که برای حذف عنصر از ابتدای صف، مورد استفاده قرار میگیرد.

در فهرست زیر، دو مورد از کاربردهای ساختار داده صف را ملاحظه میکنید:

• مدیریت «نخها» (Threads) در برنامهنویسی چند نخی از جمله کاربردهای مهم ساختمان داده صف است.
• از ساختمان داده صف برای پیادهسازی «سیستمهای صفبندی» (Queuing Systems) مانند «صف اولویت» (Priority Queue) استفاده میشود.

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

جدول هش

«جدول هش» (Hash Table)، ساختمان دادهای برای ذخیره مقادیر «همراه با کلید» (Key Associated) است. ذخیرهسازی مقادیر همراه با کلید، موجب بهینهتر شدن فرایند جستجو شده و راحتتر میتوان مقدار مورد نظر را پیدا کرد. در نتیجه جدول هش در دو فرایند درج و جستجو، فارغ از اندازه داده بسیار بهینه عمل میکند. «آدرسدهی مستقیم» (Direct Addressing) هنگام اجرای فرایند ذخیرهسازی در جدول، از «نگاشت یک-یک» (One-to-One Mapping) میان مقادیر و کلیدها بهره میبرد. با این حال اگر تعداد جفت نمونه «کلید-مقدارها» (Key-value) بیش از حد زیاد باشد، فضای بسیاری از جدول اشغال شده و این امکان وجود دارد که دیگر نتواند با فضای موجود در سیستمهای معمول اقدام به ذخیرهسازی کند. استفاده از جدول هش، راهحلی برای این مشکل است.

تابع هش

«تابع هش» (Hash Function)، تابعی است با نماد $$ h $$ که برای غلبهبر مشکل موجود در آدرسدهی مستقیم بهکار گرفته میشود. در فرایند آدرسدهی مستقیم، دادهای با کلید $$ k $$ در خانه $$ k $$ ذخیره میشود. با استفاده از تابع هش، ایندکس هر جدول شامل مقادیر مختلف داده را محاسبه میکنیم. مقدار محاسبهشده بهوسیله تابع هش برای کلیدی مشخص، «مقدار هش» (Hash Value) نام داشته و نشاندهنده ایندکس جدولی است که داده در آن ذخیره شده است. فرمول تابع هش به شرح زیر است:

$$ h(k) = k % m $$

• نماد $$ h $$: تابع هش.
• نماد $$ k $$: کلیدی که مقدار هش بهوسیله آن مشخص میشود.
• نماد $$ m $$: اندازه جدول هش یا همان تعداد خانههایی که در جدول موجود است. «عدد اولی» (Prime Value) که چندان نزدیک به توان ۲ نیز نباشد، انتخاب خوبی برای مقدار $$ m $$ است.

تابع هش که در آن اندازه جدول هش برابر با ۲۰ است را در نظر بگیرید:

$$ h(k) = k % 20 $$

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

$$ 1 rightarrow 1 % 20 rightarrow 1 $$

$$ 5 rightarrow 5 % 20 rightarrow 5 $$

$$ 23 rightarrow 23 % 20 rightarrow 3 $$

$$ 63 rightarrow 63 % 20 rightarrow 3 $$

همانطور که در دو نمونه آخر مشاهده میکنید، در صورتی که تابع هش برای بیش از یک کلید، دو ایندکس یکسان تولید کند، تصادم یا «برخورد» (Collision) رخ میدهد. با انتخاب تابع هش مناسب و بهرهگیری از تکنیکهایی همچون «زنجیرهسازی» (Chaining) و «آدرسدهی باز» (Open Addressing) میتوان بر مشکل تصادم غلبه کرد. در فهرست زیر برخی از کاربردهای جدول هش را ملاحظه میکنید:

• از جدول هش برای پیادهسازی ایندکسهای پایگاه داده استفاده میشود.
• پیادهسازی «آرایههای انجمنی» (Associative Arrays) از طریق جداول هش صورت میگیرد.
• ساختار داده «سِت» (Set) با استفاده از جدول هش پیادهسازی میشود.

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

ساختمان داده غیرخطی

در «ساختارهای داده غیرخطی» (Non-Linear Data Structures)، مجموعه ترتیبی از عناصر متصل به یکدیگر وجود نداشته و هر عنصر میتواند از طریق روشهای متفاوتی با دیگر عناصر ارتباط برقرار کند. ساختارهای داده غیرخطی از ذخیرهسازی «چند سطحی» (Multi-Level) پشتیبانی میکنند و گاهی امکان پیمایش تک مرحلهای در آنها وجود ندارد. پیادهسازی چنین ساختارهای دادهای کار راحتی نیست اما، راهاندازی آنها موجب استفاده بهینه از فضای حافظه میشود. در فهرست زیر چند نمونه ساختار داده غیرخطی را ملاحظه میکنید:

• «درخت» (Tree)
• «هیپ» (Heap)
• «گراف» (Graph)

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

درخت

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

• «درخت جستجوی دودویی» (Binary Search Tree | BST)
• «درخت بی» (B Tree)
• «درخت تریپ» (Treap)
• «درخت قرمز-سیاه» (Red-Black Tree)
• «درخت گسترده» (Splay Tree)
• «درخت اِیویاِل» (AVL Tree)
• درخت N-ary

در ادامه این بخش، بیشتر با درخت جستجوی دودویی آشنا میشویم.

درخت جستجوی دودویی در ساختمان داده چیست؟

همانطور که از اسمش پیداست، «درخت جستجوی دودویی» (Binary Search Tree | BST)، درختی دودویی است که در آن دادهها بهصورت سلسلهمراتبی منظم میشوند.

در این درخت، دادهها به ترتیب ذخیره میشوند. هر گره در درخت جستجوی دودویی از ویژگیهای زیر تشکیل میشود:

1. ویژگی کلید: مقدار ذخیره شده در گره.
2. ویژگی چپ: اشارهگر به «گره فرزند» (Child Node) سمت چپ.
3. ویژگی راست: اشارهگر به گره فرزند سمت راست.
4. ویژگی p: اشارهگر به «گره والد» (Parent Node).

درخت جستجوی دودویی، شامل ویژگی منحصربهفردی است که آن را از سایر درختها متمایز میکند. فرض کنید $$ x $$ گرهای در یک درخت جستجوی دودویی است. حال با توجه به تصویر زیر:

• اگر $$ y $$ گرهای در زیردرخت سمت چپ $$ x $$ باشد، نتیجه میگیریم که:

$$ y.key le x.key $$

• اگر $$ y $$ گرهای در زیر درخت سمت راست $$ x $$ باشد، نتیجه میگیریم:

$$ y.key ge x.key $$

به عنوان چند نمونه از کاربردهای درخت جستجو، میتوان به موارد زیر اشاره کرد:

• درخت دودویی: از درختهای دودویی برای پیادهسازی «تجزیهگرها» (Parsers) استفاده میشود.
• درخت جستجوی دودویی: از درخت جستجوی دودویی در کاربردهای جستجویی در آنها جریان ورود و خروج دادهها بالاست کمک گرفته میشود.
• ساختار داده هیپ: در «محیط زمان اجرای زبان برنامهنویسی جاوا» (Java Virtual Machine | JVM) و برای ذخیرهسازی نوع داده شیء از این ساختار استفاده میشود.
• ساختار داده تریپ: ساختار داده تریپ در «شبکههای بیسیم» (Wireless Networks) کاربرد بسیاری دارد.

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

هیپ

ساختار داده «هیپ» (Heap) نمونهای از درخت دودویی است که در آن مقدار گره والد با مقادیر گرههای فرزند مقایسه شده و بر همین اساس مرتب میشوند. هیپ را میتوان هم بهصورت درخت و هم آرایه به نمایش گذاشت. در دو تصویر زیر، نمایش درختی و آرایهایی ساختار داده هیپ را مشاهده میکنید:

در تصویر زیر، مثال پیادهسازی هیپ با آرایه نشان داده شده است.

هیپ میتواند دو حالت داشته باشد:

1. «هیپ کمینه» (Min Heap): کلید گره والد کوچکتر یا برابر با مقدار گره فرزند است. «گره ریشه» (Root Node) کوچکترین مقدار را در تمامی ساختار هیپ کمینه شامل میشود.
2. «هیپ بیشینه» (Max Heap): در هیپ بیشینه، کلید گره والد بزرگتر یا برابر با گره فرزند آن است. مقدار گره ریشه در هیپ کمینه از سایر گرهها بزرگتر است.

در فهرست زیر، به تعدادی از کاربردهای ساختار داده هیپ اشاره شده است:

• ساختار داده هیپ در الگوریتم «مرتبسازی هیپ» (Heap Sort) بهکار گرفته میشود.
• در پیادهسازی صف اولویت از هیپ استفاده میشود. پیادهسازی ساختار داده هیپ در صف اولویت بهصورت آرایه است.
• «توابع صف» (Queue Functions) را میتوان از طریق ساختار داده هیپ و با پیچیدگی زمانی $$ O(log n) $$ پیادهسازی کرد.
• از فرایند جستجوی کوچکترین یا بزرگترین مقدار آرایه، به عنوان یکی دیگر از موارد استفاده ساختار داده هیپ یاد میشود.

هیپ یکی از پرکاربردترین ساختمان دادهها در «سیستمهای تعبیهای» (Embedded Systems) است. دسترسی سریع به دادهها و در نتیجه عملکرد بالا، از جمله ویژگیهای متمایزکننده هیپ از دیگر ساختارهای داده است.

گراف در ساختمان داده چیست؟

ساختمان داده «گراف» (Graph) متشکل از «مجموعه متناهی» (Finite Set) از «گرهها» (Vertices) و «یالهای» (Edges) متصلکننده گرهها به یکدیگر است. «مرتبه» (Order) یک گراف برابر با تعداد گرههای آن است. همچنین اندازه گراف را تعداد یالهای آن تشکیل میدهند. دو رأس در گراف را «مجاور» (Adjacent) مینامند، اگر از طریق یال یکسانی به یکدیگر متصل باشند. ساختار داده گراف به دو نوع «جهتدار» (Directed) و «بدون جهت» (Undirected) تقسیم میشود که در ادامه هر کدام را بیشتر توضیح میدهیم.

گراف جهتدار

گراف $$ G $$ جهتدار است، اگر تمامی یالهای آن جهت داشته و رئوس شروع و پایان آنها نیز مشخص باشد. به عنوان مثال، عبارت $$ (u, v) $$ به معنی یالی است که از رأس $$ u $$ خارج و به رأس $$ v $$ وارد میشود. اگر یالی از یک رأس شروع و به همان رأس ختم شود، آن را «حلقه» (Self-loop) مینامیم.

گراف بدون جهت

گراف $$ G $$ بدون جهت است، اگر تمامی یالهای آن بدون جهت بوده و به هر دو رأس مجاور راه داشته باشند. به رأسی که به هیچ گره دیگری در گراف متصل نباشد، رأس «جدا» (Isolated) گفته میشود. در تصویر زیر شرح کاملی از دو گراف جهتدار و بدون جهت را مشاهده میکنید:

موارد زیر، تنها چند نمونه از کاربردهای ساختار داده گراف هستند:

• با استفاده از گراف، میتوان ساختار کلی شبکههای اجتماعی را به نمایش گذاشت. هر کاربر یک رأس است و زمانی که دو کاربر با یکدیگر ارتباط برقرار میکنند، یالی میان آنها ایجاد میشود.
• از ساختار داده گراف برای نمایش صفحات وب و لینکهای موجود در موتورهای جستجو استفاده میشود. صفحات وب در فضای اینترنت از طریق «ابَر پیوندها» (Hyperlinks) به یکدیگر متصل هستند. هر صفحه گرهایست و ابر پیوند میان دو صفحه در واقع همان یال است. در نتیجه فرایند رتبهبندی صفحات گوگل با گراف انجام میشود.
• گراف در نمایش موقعیتهای مکانی و مسیریابی در «جیپیاِس» (GPS) نقش موثری را ایفا میکند. در این کاربرد، موقعیتهای مکانی رئوس و مسیرهای متصلکننده آنها به یکدیگر، همان یالهای گراف هستند. محاسبه کوتاهترین مسیر میان دو موقعیت مکانی، یکی از موارد کاربردی استفاده از ساختار داده گراف است.

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

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

ساختمان داده به دستهبندیها و انواع مختلفی تقسیم میشود. بهطور کلی یک ساختار داده ممکن است در یک یا چند مورد از چهار دسته زیر قرار بگیرد:

• «ساختار داده ایستا» (Static Data Structure)
• «ساختار داده پویا» (Dynamic Data Structure)
• «ساختار داده همگن» (Homogenous)
• «ساختار داده ناهمگن» (Non-Homogenous)

در ادامه این مطلب، هر یک از انواع ساختمان دادههای عنوان شده در فهرست بالا را توضیح میدهیم.

ساختار داده ایستا

در «ساختارهای داده ایستا» (Static Data Structures)، اندازه حافظه مورد نیاز در «زمان کامپایل» (Compile Time) مشخص میشود. هنگام استفاده از این ساختار داده، فرد برنامهنویس باید قبل از اجرای برنامه، اندازه دقیق مورد استفاده خود را در حافظه کامپیوتر مشخص کند.

ساختار داده پویا

تعیین اندازه حافظه مورد نیاز در «ساختارهای داده پویا» (Dynamic Data Structures) در «زمان اجرا» (Run Time) صورت میگیرد. از همینرو حد بیشینه اندازه منعطف بوده و ممکن است بهازای هر درخواست تغییر کند. همچنین در ساختار داده پویا، موقعیت مکانی داده در حافظه نیز قابل تغییر است.

ساختار داده همگن

ساختار دادهای «همگن» (Homogenous) است که در آن تمامی عناصر از یک نوع باشند. به عنوان مثال، آرایه ساختمان دادهای همگن است.

برچسب: نویسنده: خنجی تاريخ: دوشنبه 18 دی 1402 ساعت: 18:34