گره (علوم رایانه)

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم رایانه، گره (به انگلیسی: Node) رکوردی است که از یک فیلد داده و همچنین از یک یا چند فیلد که پیوندی به دیگر گره‌ها هستند، تشکیل می‌شود. فیلدهای داده و پیوند معمولاً توسط اشاره‌گرها یا مراجع پیاده‌سازی می‌شوند. هر چند که جاسازی کردن داده‌ها به شکل مستقیم در گره هم بسیار رایج است. گره‌ها برای ساختن ساختار داده‌های پیوندی و سلسله‌مراتبی مانند لیست پیوندی، درخت و گراف استفاده می‌شوند. ساختار داده‌های بزرگ و پیچیده‌تر می‌توانند از گروهی از گره‌های بهم‌پیوسته تشکیل شوند. از لحاظ مفهومی، گره‌ها مشابه راس‌های تشکیل‌دهنده یک گراف هستند.

مثال‌هایی از پیاده سازی به شبه‌کد[ویرایش]

گره زیر از یک فیلد برای ذخیره کردن داده‌ها و از یک فیلد پیوندی به نام next تشکیل شده است:

 record SinglyLinkedNode {
    next, // A reference to the next node
    data // Data or reference to data
 }

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

Node chain.svg

گره زیر شامل دو فیلد پیوندی است:

 record DoublyLinkedNode {
    previous, // A reference to the previous node
    next, // A reference to the next node
    data // Data or reference to data
 }

سه نمونه از گره بالا تشکیل یک لیست دوپیوندی با طول ۳ را می‌دهند:

Doubly-linked-list.svg

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

 record BinaryNode {
    parent, // A reference to the parent node                                
    left_child, // A reference to the left child node
    right_child, // A reference to the right child node
    data // Data or reference to data
 }

منابع[ویرایش]