الگوریتم اول

لطفا صبر کنید...

الگوریتم‌ها و ساختارهای داده در ++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، ساختارهای داده و الگوریتم‌ها ابزارهایی هستند که به ما کمک می‌کنند تا داده‌ها را به‌طور مؤثر ذخیره‌سازی و پردازش کنیم. از آرایه‌ها و لیست‌های پیوندی تا ساختارهای پیچیده‌تری مانند پشته‌ها، صف‌ها و نقشه‌ها، هرکدام کاربرد خاص خود را دارند. همچنین الگوریتم‌های مرتب‌سازی، جستجو و پیمایش گراف‌ها از اهمیت زیادی برخوردارند و به ما کمک می‌کنند تا مسائل مختلف را به‌طور بهینه حل کنیم.