الگوریتمها و ساختارهای داده در ++C
الگوریتمها و ساختارهای داده از مباحث مهم در علوم کامپیوتر هستند که به ما کمک میکنند تا دادهها را بهطور بهینه ذخیرهسازی و پردازش کنیم. در ++C، انواع مختلفی از ساختارهای داده و الگوریتمها وجود دارند که میتوانند به حل مسائل مختلف کمک کنند. در این بخش به بررسی برخی از مهمترین الگوریتمها و ساختارهای داده در ++C پرداخته میشود.
۱. ساختارهای داده در ++C
۱.۱ آرایهها (Arrays)
آرایهها مجموعهای از دادهها با نوع یکسان هستند که بهطور متوالی در حافظه ذخیره میشوند. در ++C میتوان از آرایهها برای ذخیرهسازی دادههای مشابه استفاده کرد.
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5};
cout << "المان اول آرایه: " << arr[0] << endl;
return 0;
}
۱.۲ لیست پیوندی (Linked List)
لیست پیوندی یک ساختار داده است که از گرهها (nodes) تشکیل شده است. هر گره شامل یک مقدار و اشارهگری به گره بعدی است. این ساختار داده برای ذخیرهسازی دادهها بهصورت پویا مناسب است.
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 <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 <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 <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 <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 <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 <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 <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، ساختارهای داده و الگوریتمها ابزارهایی هستند که به ما کمک میکنند تا دادهها را بهطور مؤثر ذخیرهسازی و پردازش کنیم. از آرایهها و لیستهای پیوندی تا ساختارهای پیچیدهتری مانند پشتهها، صفها و نقشهها، هرکدام کاربرد خاص خود را دارند. همچنین الگوریتمهای مرتبسازی، جستجو و پیمایش گرافها از اهمیت زیادی برخوردارند و به ما کمک میکنند تا مسائل مختلف را بهطور بهینه حل کنیم.
