ساختمان داده

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

• کارایی  یا Efficiency:
  قابلیت انجام عملیات مختلف مثل: جستجو، درج، حذف و به‌ روز رسانی با سرعت مناسب.

• سازمان‌ دهی داده‌ ها یا Data Organization:
  مشخص میکند داده‌ ها چگونه کنار هم قرار میگیرند و چه ارتباطی با هم دارند.

• مدیریت حافظه یا Memory Management:
  نحوه‌ استفاده بهینه از حافظه و جلوگیری از هدر رفتن فضا.

• قابلیت دسترسی یا Accessibility:
  اینکه داده‌ ها چگونه و با چه سرعتی قابل دسترسی هستند به طور مثال: دسترسی تصادفی یا ترتیبی.

• انعطاف‌ پذیری یا Flexibility:
  امکان تغییر اندازه و ساختار یا مدیریت داده‌ ها متناسب با نیاز برنامه.

• سهولت پیاده‌ سازی یا Ease of Implementation:
  میزان پیچیدگی کد نویسی و اجرای ساختمان داده.

• پشتیبانی از عملیات مختلف یا Operation Support:
  هر ساختمان داده از مجموعه‌ ای متفاوت عملیات، پشتیبانی میکند به طور مثال: push، pop، insert، delete، search.

هدف ساختمان داده:

• استفاده بهینه از حافظه
• انجام سریع تر عملیات ها مثل: جستجو، مرتب سازی، حذف و افزودن
• ساده کردن مدل سازی مسائل واقعی مثل: صف، درخت، شبکه، گراف و …

طبقه بندی کلی ساختمان داده:

• ساختمان داده خطی یا Linear Data Structures
• ساختمان داده غیر خطی یا Non-Linear Data Structures

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

در ساختمان داده خطی داده‌ ها بصورت پشت‌ سر هم و در یک مسیر مشخص قرار میگیرند. در این نوع ساختار داده ها پشت سر هم یا توالی خطی سازماندهی میشوند. هر عنصر بجز اولی و اخری دقیقا یک عنصر قبل و یک عنصر بعد دارد. ویژگی ان: پیمایش از ابتدا تا انتها به صورت ترتیبی انجام میشود. حتما اگر داده ای در وسط باشذ یک داده قبل از ان و یک داده بعد از ان قرار دارد. 
مثل:

• ارایه یا Array

• لیست پیوندی یا Linked List

• پشته یا Stack

• صف یا Queue

ساختمان داده‌ های غیر خطی یا Non-Linear Data Structures:

در ساختمان داده غیر خطی داده‌ ها در چندین مسیر یا شاخه سازمان‌ دهی میشوند و رابطه سلسله‌ مراتبی یا شبکه‌ ای دارند. دیتا هایی که به صورت پخش یا رندم وجود دارند و شاید به یکی یا دوتا یا سه تا و… دیتا دسترسی داشته باشند و حتما به یک دیتا دسترسی ندارند به چند دیتا دسترسی دارند. داده ها به صورت سلسله مراتبی یا شبکه ای سازمان دهی میشوند نه به شکل یک خط مستقیم. ویژگی ان: هر داده ممکن است به چند داده دیگر متصل باشد نه فقط به یکی قبل و یکی بعد. 
مثل:

• درخت‌ ها یا Trees

• گراف‌ ها یا Graphs

ارایه یا Array:

داده ها در خانه های متوالی حافظه ذخیره میشوند و هر داده با شمار مکان index شناخته میشود. یکی از ساده‌ ترین و مهم‌ ترین ساختمان‌ داده‌ های خطی است که مجموعه‌ ای از عناصر هم‌ نوع را در خانه‌ های پشت‌ سر هم حافظه ذخیره میکند. مثل: [ 12،9،7،5 ] . کاربرد ان وقتی است که تعداد داده ها مشخص است و به همه باید با سرعت بالا دسترسی داشت.

یک مستطیل با 6 خانه در نطر بگیرید هر  کدام از خط های ان که خانه ها را از هم جدا کرده ایندکس یا index  ها هستند که از صفر شروع میشود و هرکدام از این خانه ها یک بلوک یا block هستند که داخل این ها دیتا ها قرار میگیرد. هر کدام از این بلاک ها میتوانند 16،8 2 و … بیت باشد. معروف ترین نوع ارایه استرینگ یا رشته است. رشته ارایه ای از کاراکتر ها است. پر مصرف ترین و ساده ترین ساختمان داده است که در اکثر برنامه ها استفاده میشود و مابقی دیتا استراکچر ها از ارایه ساخته شده اند.

ویژگی های ارایه ها:

• ترتیب مشخص دارد: یعنی خانه ها مشخص است از 0 تا 1 و 2 و 3 و …
• اندازه ثابت: یعنی وقتی ارایه ای را تعریف میکنیم به ان اندازه میدهیم.
• دسترسی مستقیم Random Access: به صورت مستقیم به index مورد نظر میرویم مثلا index 3 مستقیم به داخل خانه یا بلاک index 3 میرویم.

لیست پیوندی یا Linked List:

از چند گره یا Nods تشکیل میشود که هر گره. به دلیل اینکه هر گره به گره بعدی اشاره میکند، نام پیوندی را به ان داده‌ اند. این ساختار داده‌ برخلاف ارایه‌ ها اندازه ثابت ندارد و میتوان به راحتی گره‌ ها را اضافه یا حذف کرد بدون نیاز به جابجایی کل عناصر. کاربرد ان: وقتی میخواهیم داده ها زیاد تغییر کنند مثل افزودن یا حذف. مثل: A ⭢B ⭢C ⭢D . هر گره شامل دو بخش است:

1. داده یا Data: مقداری که گره نگه میدارد.
2. اشاره گر به گره بعدی یا Next Pointer یا Reference: اشاره‌ گری به گره بعدی در لیست.

ویژگی های لیست پیوندی:

• اندازه پویا
• درج و حذف اسان
• دسترسی ترتیبی نه مستقیم.

معایب:

• دسترسی به عنصر خاص به صورت تصادفی سخت است برای دسترسی به عنصر n ام باید از ابتدا لیست عبور کرد.

• نیاز به حافظه بیشتر برای ذخیره اشاره‌ گر دارد.

پشته یا Stack

نوعی ساختار خطی با سیاست LIFO اخرین وارد ، اولین خارج. پشته Stack یک ساختار داده‌ ای انتزاعی است که بر اساس اصل LIFO کار میکند. یعنی اخرین عنصری که وارد پشته میشود اولین عنصری است که خارج میشود. پشته ها مثل مخزن و یا یک کاسه هستند که دیتا ها از یک طرف وارد میشوند و از طرف دیگر خارج میشوند. مثل: اگر داده ها را به ترتیب A,B,C وارد کنیم خروجی خواهد بود: C,B,A . کاربرد های پشته: در بازگشت توابع undo/redo.recursion  یعنی کنترل z ، تجزیه عبارات ریاضی.

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

• Push افزودن
• Pop برداشتن
• Peek دیدن اخرین عنصر

ویژگی‌ های اصلی پشته:

• Push: افزودن یک عنصر به بالای پشته.
• Pop: حذف و برگرداندن عنصر بالای پشته.
• Peek یا Top: مشاهده عنصر بالای پشته بدون حذف ان.
• IsEmpty: بررسی خالی بودن پشته.
• IsFull: در پیاده‌ سازی‌ های ثابت مثل ارایه بررسی پر بودن پشته.

صف یا Queue

ساختار خطی با سیاست FIFO ، اولین وارد ، اولین خارج. صف یا Queue یک ساختار داده‌ ای انتزاعی است که بر اساس اصل FIFO کار میکند. FIFO = First In, First Out. یعنی اولین عنصری که وارد صف میشود، اولین عنصری است که خارج میشود. مثل صف نانوایی: کسی که زودتر امده است زودتر سرویس میگیرد و از صف خارج میشود. مثل یک لوله که دو طرف ان باز است در نظر بگیرید از یک طرف که وارد شود از طرف دیگر خارج میشود. مثل: A⭢B⭢C ابتدا A خارج میشود. بزرگ ترین کاربرد هایش در cpu است. و کاربرد صف: مدیریت صف درخواست ها، پردازش صف چاپگر، کنترل ترافیک داده ها، شبیه‌ سازی سیستم‌ های خدماتی مثل: بانک، بیمارستان و … ، ساختار داده BFS در گراف، زمان‌ بندی پردازنده‌ ها CPU Scheduling، مدیریت بسته‌ های شبکه.

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

• Enqueue افزودن : افزودن یک عنصر به انتهای صف
• Dequeue برداشتن : حذف و برگرداندن عنصر ابتدای صف

عملیات‌ های تکمیلی:

• Front یا Peek: مشاهده اولین عنصر بدون حذف

• Rear: مشاهده اخرین عنصر

• IsEmpty: بررسی خالی بودن صف

• IsFull: برای پیاده‌ سازی‌ های محدود

انواع صف:

• صف ساده Simple Queue

• صف دوتایی Double Ended Queue – Deque: میتوان از ابتدا و انتها اضافه، حذف کرد.

• صف حلقوی Circular Queue: برای جلوگیری از هدر رفتن فضا در پیاده‌ سازی با ارایه.

• صف اولویت‌ دار Priority Queue: خروج بر اساس اولویت، نه زمان ورود.

درخت ها Tree:

ساختار غیر خطی سلسله مراتبی که شامل گره ها nodes است. هر گره میتواند چند فرزند داشته باشد. درخت Tree یکی از مهم‌ ترین ساختار های داده‌ ای است که برای نمایش روابط سلسله‌ مراتبی استفاده میشود. درخت‌ ها در علوم کامپیوتر بسیار پرکاربرد هستند، از پایگاه‌ های داده گرفته تا سیستم‌ فایل‌ ها و الگوریتم‌ ها. درخت یک ساختار داده غیر خطی است که از گره‌ ها یا Nodes تشکیل شده است. هر درخت یک گره ریشه Root دارد و سایر گره‌ ها به شکل والد، فرزند به هم وصل شده‌ اند. کاربرد های درخت‌ها: ساختار دایرکتوری‌ ها در سیستم‌ عامل، پایگاه‌ داده‌ ها B-Tree, B+Tree، کامپایلر ها Syntax Tree، شبکه‌ ها Tree Routing، هوش مصنوعی درخت تصمیم، جستجو و مرتب‌ سازی سریع، ذر سیستم فایل ها، موتور های جستجو، بانک های داده. ریشه یا روت همان اولین داده است که در راس قرار دارد و شامل فرزند میشود و ان هایی که بچه ندارند را لیف میگویند و بیشترین یا طولانی ترین راه ارتباط بین ریشه تا لیف را عمق درخت میگویند.  مثل سرچ واژه که اول خود واژه سرچ میشود و بعد چیز های مربوط به واژه سرچ میشود. هر گره شامل موارد زیر است:

• Data یا داده

• اشاره‌ گر به فرزندان

اصطلاحات درخت:

• Root : گره اصلی
• Leaf: گره بدون فرزند
• Depth: عمق درخت

واژگان مهم در درخت‌ ها:

انواع درخت‌ ها:

• درخت دو دویی Binary Tree: هر گره حداکثر دو فرزند دارد Left و Right.

• درخت جستجوی دو دویی BST — Binary Search Tree: مقادیر کمتر از گره → سمت چپ . مقادیر بیشتر از گره → سمت راست ،مناسب برای جستجوی سریع.

• درخت دو دویی کامل، تراز، متوازن: انواع مختلفی از درخت‌ های دو دویی:

1. AVL Tree

2. Red-Black Tree

3. Complete Binary Tree

4. Full Binary Tree

5. درخت عمومی General Tree

هر گره میتواند هر تعداد فرزند داشته باشد.

• درخت هیپ Heap: برای پیاده‌ سازی Priority Queue استفاده میشود.

• درخت Trie: برای جستجوی رشته‌ ها، مثل: ذخیره‌ سازی دیکشنری‌ ها یا autocomplete.

• درخت B-Tree / B+Tree: در پایگاه داده‌ ها و فایل‌ سیستم‌ ها استفاده میشود.

Root ریشه:

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

Leaf برگ:

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

Depth عمق:

عمق یک گره یعنی تعداد یال‌ ها یا Edges بین ریشه تا ان گره. عمق ریشه = صفر، عمق هر گره = عمق والد + 1 . مثال: اگر از ریشه به یک گره 3 یال فاصله داشته باشد، عمق ان گره 3 است.

A         روت یا ریشه (Root, depth = 0)

\ /

B C       عمق یا (depth = 1)

\ /

D E      عمق یا (depth = 2)

• A → ریشه

• D و E و C → برگ

• عمق:

• depth(A) = 0
• depth(B) = 1
• depth(D) = 2

کراف ها یا  Graph:

ساختار غیر خطی متشکل از نود ها vertex و یال ها Edge که روابط بین ان ها را نشان میدهد. گراف یا Graph یکی از مهم‌ ترین ساختار های داده‌ ای در علوم کامپیوتر و ریاضیات است و برای نمایش رابطه‌ ها و اتصال بین اشیا استفاده میشود. یک گراف مجموعه‌ ای از: راس‌ ها یا (Vertices / Nodes)، یال‌ ها (Edges) است که یال‌ ها راس‌ ها را به یکدیگر متصل میکنند. کاربرد گراف ها: شبکه های اجتماعی، مسیر یابی ، تحلیل روابط داده ها.

ویژگی های گراف ها:

• جهت دار یا بدون جهت: فقط از A به B میتوانم بروم و از  B به  A نمیتوانم بروم. A ⭢ B
• میتواند شامل چرخه cycle باشد.
• یال ها میتوانند وزن دار و یا بی وزن باشند: میتوان از A به B که رفت روی یال ها وزن بدهیم.   A ⭢ B

مجموعه یا Set:

مجموعه ای از داده ها بدون تکرار و بدون ترتیب خاص مثل: {8،6،4،2} . مجموعه یا Set یکی از بنیادی‌ ترین مفاهیم در ریاضیات و علوم کامپیوتر است. مجموعه به معنای گروهی از عناصر متمایز است، یعنی هیچ عنصر تکراری در ان وجود ندارد. ست جزء داده های ترتیبی است. مجموعه یک ساختار است که از عناصر بدون تکرار و بدون ترتیب مشخص تشکیل شده است. اگر داده ای تگراری باشد در مجموعه ست حذف میشود. مثلا اگر دوتا 8 داشته باشیم در مثال بالا یک 8 خذف میشود و فقط یکی از 8 ها نوشته میشود. ترتیب مهم نبیت فقط تکراری نباشد. {1،5،5،3،6،9،9،7،9،4} این به صورت {1،5،3،6،9،7،4} ذخیره میشود. و مجم.عه یا ست ها یک نوع داده خطی هستند.

ویژگی‌ های اصلی مجموعه ست یا set: 

• عدم وجود عنصر تکراری

اگر عدد 5 را به مجموعه {1, 5, 7} اضافه کنیم، مجموعه تغییری نمیکند.

• بدون ترتیب بودن

در مجموعه ترتیب اهمیت ندارد
{1, 2, 3} = {3, 1, 2}

• متناهی یا نا متناهی

• مجموعه اعداد 1 تا 10 → متناهی

• مجموعه اعداد طبیعی → نا متناهی

عملیات روی مجموعه‌ set: 

• اجتماع Union:

A ∪ B
ترکیب عناصر دو مجموعه.

• اشتراک Intersection:

A ∩ B
عناصر مشترک بین دو مجموعه.

• تفاضل Difference:

A − B
عناصر مجموعه A که در B نیستند.

• متمم یا Complement:

عناصر خارج از یک مجموعه در یک جهان تعریف‌ شده.

کاربرد های مجموعه ست:

• حذف داده‌ های تکراری

• ساختار داده‌ ای Set در زبان‌ هایی مانند: Python, Java, C

• تحلیل جبر مجموعه‌ ها در پایگاه‌ داده‌ ها SQL

• نظریه گراف: راس‌ ها و یال‌ ها مجموعه هستند

• نظریه زبان‌ ها و اتوماتا

• مدیریت دسته‌ های داده

• الگوریتم‌ ها به طور مثال: BFS برای جلوگیری از بازدید دوباره گره‌ ها

 نگاشت ها یا Tuple/Map/Dictionary:

هر داده شامل یک کلید Key ، و یک مقدار value است. کاربرد های نگاشت: زمانی که میخواهیم داده ها را بر اساس یک شناسه خاص ذخیرع کنیم. مثل: اطلاعات شناسنامه افراد. زمانی که یک دیتا به دیتای دیگر وصل است. مثل: نام و نام خانوادگی که هر دو میشه key و چیزهایی که در مقابل ان ها نوشته میشوذ میشه value. مقدار value  ها میتواند متفاوت باشد برای هر فرد یا هر داده اما key ها نمیتوانند متفاوت باشند چونکه در key ها زمانی که 2 تا key داریم مثلا فرشاد و احد key های ما هستند وقتی ما key را بخواهیم برگردانیم مشخص نیست کدام را به ما برمیگرداند. key  ها حتما باید یونیک باشند.

تاپل (Tuple): 

تاپل یک دنباله مرتب و تغییر ناپذیر Immutable از عناصر است. ویژگی‌ های تاپل:

• مرتب است: ترتیب عناصر مهم است.

• غیر قابل تغییر است: بعد از ایجاد نمیتوان عناصر را حذف یا اضافه یا تغییر داد.

• میتواند انواع مختلف داده را در خود نگه دارد.

موارد استفاده تاپل:

• زمانی که داده ثابت است و نباید تغییر کند.

• ذخیره رکورد های کوچک مثل مختصات: (x, y)

نگاشت Map:

Map یک ساختار داده است که هر کلید را به یک مقدار نگاشت میکند. به ان mapping یا key–value store هم گفته میشود. در بسیاری از زبان‌ ها، نام Map متفاوت است:

• Python → Dictionary

• Java → HashMap, TreeMap

• JavaScript → Map

• C++ → map / unordered_map

ویژگی‌ های نگاشت Map:

• داده‌ ها بر اساس کلید (Key) ذخیره میشوند.

• کلید ها منحصر به‌ فرد هستند.

• مقدار ها (Value) میتوانند تکراری باشند.

• دسترسی بسیار سریع بر اساس کلید.