الخوارزميات وهياكل البيانات بلغة Rust: دليل عملي

مقدمة في الخوارزميات وهياكل البيانات باستخدام Rust

لغة البرمجة Rust حظيت بتقدير المطورين بفضل أدائها العالي وضماناتها الصارمة لسلامة الذاكرة. ومع ذلك، قد يكون الانتقال إلى Rust من لغات أخرى مثل Python أو JavaScript أمرًا صعبًا، خاصة عند تنفيذ الخوارزميات وهياكل البيانات الكلاسيكية. في هذه المقالة، سننظر في كيفية تنفيذ هياكل البيانات والخوارزميات الأساسية بكفاءة باستخدام Rust، مع مراعاة ميزات نظام الملكية (ownership) والاقتراض (borrowing).

المقالة موجهة للمطورين الذين هم على دراية بأساسيات Rust بالفعل. سنركز على أمثلة عملية من الكود يمكن استخدامها فورًا في المشاريع الحقيقية. جميع الأمثلة ستكون مصحوبة بتعليقات مفصلة.

تنفيذ القائمة المرتبطة (Linked List) باستخدام Rust

القائمة المرتبطة هي واحدة من هياكل البيانات الأساسية. في Rust، يتطلب تنفيذها اهتمامًا خاصًا بسبب قواعد الملكية. سننظر في قائمة مرتبطة أحادية الاتجاه باستخدام Box لإدارة الذاكرة.

قائمة مرتبطة أحادية الاتجاه أساسية

لنبدأ بتعريف العقدة والقائمة نفسها:

use std::fmt::Display;

#[derive(Debug)]struct Node<T> {    value: T,    next: Option<Box<Node<T>>>,}

#[derive(Debug)]struct LinkedList<T> {    head: Option<Box<Node<T>>>,    length: usize,}

impl<T> LinkedList<T> {    fn new() -> Self {        LinkedList {            head: None,            length: 0,        }    }

    fn push_front(&mut self, value: T) {        let new_node = Box::new(Node {            value,            next: self.head.take(),        });        self.head = Some(new_node);        self.length += 1;    }

    fn pop_front(&mut self) -> Option<T> {        self.head.take().map(|node| {            self.head = node.next;            self.length -= 1;            node.value        })    }

    fn is_empty(&self) -> bool {        self.head.is_none()    }

    fn len(&self) -> usize {        self.length    }}

لاحظ استخدام Option<Box<Node<T>>>. هذه هي الطريقة القياسية لإنشاء هياكل تكرارية في Rust، حيث يتطلب المترجم حجمًا معروفًا مسبقًا. تسمح طريقة take() باستخراج القيمة بأمان من Option، مع استبدالها بـ None.

التكرار عبر القائمة

لننفذ مكررًا (iterator) للقائمة:

impl<T: Clone> LinkedList<T> {    fn iter(&self) -> LinkedListIterator<T> {        LinkedListIterator {            current: self.head.as_deref(),        }    }}

struct LinkedListIterator<T> {    current: Option<&Node<T>>,}

impl<T> Iterator for LinkedListIterator<T> {    type Item = &T;

    fn next(&mut self) -> Option<Self::Item> {        self.current.take().map(|node| {            self.current = node.next.as_deref();            &node.value        })    }}

شجرة البحث الثنائية (BST) باستخدام Rust

الأشجار هي هيكل بيانات مهم آخر. سننفذ شجرة بحث ثنائية مع دعم الإدراج والبحث والاجتياز.

الهيكل والإدراج الأساسي

#[derive(Debug)]struct TreeNode<T> {    value: T,    left: Option<Box<TreeNode<T>>>,    right: Option<Box<TreeNode<T>>>,}

#[derive(Debug)]struct BinarySearchTree<T> {    root: Option<Box<TreeNode<T>>>,}

impl<T: Ord> BinarySearchTree<T> {    fn new() -> Self {        BinarySearchTree { root: None }    }

    fn insert(&mut self, value: T) {        let mut current = &mut self.root;        while let Some(node) = current {            if value <
```