الگوریتم‌ها و ساختارهای داده در ++C

الگوریتم‌ها و ساختارهای داده از مباحث مهم در علوم کامپیوتر هستند که به ما کمک می‌کنند تا داده‌ها را به‌طور بهینه ذخیره‌سازی و پردازش کنیم. در ++C، انواع مختلفی از ساختارهای داده و الگوریتم‌ها وجود دارند که می‌توانند به حل مسائل مختلف کمک کنند. در این بخش به بررسی برخی از مهم‌ترین الگوریتم‌ها و ساختارهای داده در ++C پرداخته می‌شود.

۱. ساختارهای داده در ++C

۱.۱ آرایه‌ها (Arrays)

آرایه‌ها مجموعه‌ای از داده‌ها با نوع یکسان هستند که به‌طور متوالی در حافظه ذخیره می‌شوند. در ++C می‌توان از آرایه‌ها برای ذخیره‌سازی داده‌های مشابه استفاده کرد.

#include <iostream>

using namespace std;

int main() {

    int arr[5] = {1, 2, 3, 4, 5};

    cout << "المان اول آرایه: " << arr[0] << endl;

    return 0;

}

۱.۲ لیست پیوندی (Linked List)

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

#include <iostream>

using namespace std;

struct Node {

    int data;

    Node* next;

};

int main() {

    Node* head = new Node();

    head->data = 10;

    head->next = nullptr;

    cout << "داده گره اول: " << head->data << endl;

    return 0;

}

۱.۳ پشته (Stack)

پشته یک ساختار داده خطی است که از اصول آخر وارد، اول خارج (LIFO) پیروی می‌کند. در این ساختار، عملیات افزودن و حذف داده‌ها فقط از یک سر پشته انجام می‌شود.

در ++C می‌توان از کلاس stack موجود در کتابخانه استاندارد stack استفاده کرد:

#include <iostream>

#include <stack>

using namespace std;

int main() {

    stack<int> s;

    s.push(10);

    s.push(20);

    s.push(30);

    cout << "المان بالای پشته: " << s.top() << endl;

    s.pop();

    cout << "المان بعد از حذف: " << s.top() << endl;

    return 0;

}

۱.۴ صف (Queue)

صف یک ساختار داده خطی است که از اصول اول وارد، اول خارج (FIFO) پیروی می‌کند. در این ساختار، داده‌ها از یک سر صف وارد و از سر دیگر خارج می‌شوند.

در ++C می‌توان از کلاس queue در کتابخانه queue استفاده کرد:

#include <iostream>

#include <queue>

using namespace std;

int main() {

    queue<int> q;

    q.push(10);

    q.push(20);

    q.push(30);

    cout << "المان اول صف: " << q.front() << endl;

    q.pop();

    cout << "المان بعد از حذف: " << q.front() << endl;

    return 0;

}

۱.۵ نقشه (Map)

نقشه یک ساختار داده است که جفت‌های کلید و مقدار را ذخیره می‌کند. این ساختار برای جستجو و دسترسی سریع به داده‌ها بر اساس کلید بسیار مناسب است.

در ++C می‌توان از کلاس map در کتابخانه map استفاده کرد:

#include <iostream>

#include <map>

using namespace std;

int main() {

    map<int, string> m;

    m[1] = "یک";

    m[2] = "دو";

    m[3] = "سه";

    cout << "مقدار کلید 2: " << m[2] << endl;

    return 0;

}

۱.۶ بردار (Vector)

بردار (یا داینامیک آرایه) یک ساختار داده است که اندازه آن در حین اجرای برنامه تغییر می‌کند. در ++C از کلاس vector در کتابخانه vector استفاده می‌شود.

#include <iostream>

#include <vector>

using namespace std;

int main() {

    vector<int> v = {1, 2, 3, 4, 5};

    cout << "المان اول بردار: " << v[0] << endl;

    return 0;

}

۲. الگوریتم‌ها در ++C

۲.۱ مرتب‌سازی (Sorting)

مرتب‌سازی یکی از عملیات پرکاربرد در الگوریتم‌ها است که برای ترتیب دادن داده‌ها استفاده می‌شود. در ++C کتابخانه algorithm دارای توابع مرتب‌سازی مختلفی مانند ()sort است.

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

    vector<int> v = {5, 3, 4, 1, 2};

    sort(v.begin(), v.end());  // مرتب‌سازی به صورت پیش‌فرض (صعودی)

    for (int i : v) {

        cout << i << " ";

    }

    return 0;

}

۲.۲ جستجو (Searching)

جستجو به منظور یافتن یک عنصر خاص در داده‌ها انجام می‌شود. در ++C توابعی مانند ()find برای جستجو در آرایه‌ها و بردارها استفاده می‌شوند.

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

    vector<int> v = {1, 2, 3, 4, 5};

    auto it = find(v.begin(), v.end(), 3);

    if (it != v.end()) {

        cout << "عنصر پیدا شد!" << endl;

    } else {

        cout << "عنصر پیدا نشد!" << endl;

    }

    return 0;

}

۲.۳ جستجوی دودویی (Binary Search)

جستجوی دودویی یکی از الگوریتم‌های جستجو است که در داده‌های مرتب شده برای یافتن یک عنصر استفاده می‌شود. در ++C می‌توان از تابع ()binary_search در کتابخانه algorithm استفاده کرد.

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

    vector<int> v = {1, 2, 3, 4, 5};

    if (binary_search(v.begin(), v.end(), 3)) {

        cout << "عنصر پیدا شد!" << endl;

    } else {

        cout << "عنصر پیدا نشد!" << endl;

    }

    return 0;

}

۲.۴ الگوریتم BFS و DFS

برای پیمایش گراف‌ها دو الگوریتم معروف وجود دارد: جستجوی عرض اول (BFS) و جستجوی عمق اول (DFS).

BFS (Breadth-First Search): این الگوریتم گراف را به‌صورت سطحی پیمایش می‌کند و از صف (Queue) برای نگهداری گره‌ها استفاده می‌کند.
DFS (Depth-First Search): این الگوریتم گراف را به‌صورت عمقی پیمایش می‌کند و از پشته (Stack) یا بازگشتی برای پیمایش استفاده می‌کند.

۳. پیچیدگی زمانی (Time Complexity)

الگوریتم‌ها در ++C معمولاً از لحاظ پیچیدگی زمانی (زمان اجرای الگوریتم‌ها) تحلیل می‌شوند. این تحلیل به‌طور معمول با استفاده از تحلیل پیچیدگی زمانی Big-O انجام می‌شود که نشان‌دهندهٔ نرخ رشد زمان اجرای الگوریتم نسبت به اندازه ورودی است.

O(1): عملیات ثابت، زمان اجرا مستقل از اندازه ورودی.
O(n): زمان اجرا خطی.
O(n²): زمان اجرای مربعی.
O(log n): زمان اجرای لگاریتمی.

نتیجه‌گیری

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