المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:برنامه‌نویسی:دربرگیرنده‌ها

در برگیرنده ها $Containers$

به منظور راحتی برنامه نویسان بسیاری از داده ساختار های پرکاربرد در قالب کلاس های آماده در کتابخانه $STL$ نوشته شده است که در اینجا به معرفی برخی از آن ها میپردازیم

$vector$

این داده ساختار همچون یک آرایه با سایز متغیر است که امکان دسترسی مستقیم به اعضا و همچنین درج عنصر در انتها و یا حذف آخرین عنصر مهیا است. حال به نحوه تعریف و استفاده از آن میپردازیم

vector.cpp
# include<vector>        // کتابخانه مورد نیاز
vector<Type> vectorName; //  vector تعریف
vectorName[i];           // ام i دسترسی به عنصر  
vectorName.push_back(x); // به انتها x اضافه کردن 
vectorName.pop_back();   // vector حذف عنصر انتهای
vectorName.size();       // vector برگرداندن اندازه 
vectorName.empty();      // خالی است vector برگرداندن اینکه 
vectorName.clear()       // vector خالی کردن

$stack$

این داده ساختار در واقع همان داده ساختار پشته است که از قاعده $LIFO(LastInFirstOut)$ پیروی میکند.

stack.cpp
# include<stack>       // کتابخانه مورد نیاز
stack<Type> stackName; // تعریف پشته
stackName.push(x);     // روی پشته x گذاشتن  
stackName.top()        // برگرداندن عنصر روی پشته
stackName.pop();       // برداشتن بالاترین عنصر پشته
stackName.size();      // برگرداندن اندازه پشته
stackName.empty();     // برگرداندن اینکه پشته خالی است
stackName.clear();     // خالی کردن پشته 

$queue$

این کلاس همان داده ساختار صف است که از قاعده $FIFO(FirstInFirstOut)$ پیروی میکند.

queue.cpp
# include<queue>       // کتابخانه مورد نیاز
queue<Type> queueName; // تعریف صف
queueName.push(x);     // انتها صف x گذاشتن  
queueName.front()      // برگرداندن عنصر ابتدای صف
queueName.pop();       // برداشتن اولین عنصر صف
queueName.size();      // برگرداندن اندازه صف
queueName.empty();     // برگرداندن اینکه صف خالی است
queueName.clear();     // خالی کردن صف 

$set$

این کلاس داده ساختار درخت دودویی جست جو بهینه است که با الگوریتم $RedBlackTree$ پیاده سازی شده است.

set.cpp
# include<set>       //  کتابخانه مورد نیاز
set<Type> setName; //  set تعریف 
setName.insert(x);   //  set به x افزودن   
setName.find(x)      //  و در صورت پیدا شدن set در x پیدا کردن عنصر 
                     //  برگرداندن اشاره گر به آن و در غیر اینصورت برگرداندن
		     //  setName.end() اشاره گر
setName.erase(x);    //  set در صورت وجود از x حذف عنصر 				 
setName.size();      //  set برگرداندن اندازه 
setName.empty();     //  خالی است  set برگرداندن اینکه 
setName.clear();     //  set خالی کردن 

$map$

این داده ساختار در واقع همچون جدولی میماند که که یک سری کلید را به عنصر مربوطه مرتبط میکند در پیاده سازی آن در واقع از همان $set$ استفاده شده است که عناصر آن زوج مرتبی از کلید و مقدار هستند. توجه کنید که عنصر مربوط به هر کلید یکتاست در نتیجه دو زوج مرتب با مولفه اول یکسان در درخت موجود نیستند.

map.cpp
# include<map>       //  کتابخانه مورد نیاز
map<KeyType,ValueType> mapName; //  map تعریف 
mapName[key];        //  key دسترسی به مقدار مربوط به کلید   
mapName.find(key)    //  و در صورت پیدا شدن map در key پیدا کردن عنصر با کلید 
		     //  برگرداندن اشاره گر به آن و در غیر اینصورت برگرداندن
		     //  mapName.end() اشاره گر				 
mapName.size();      //  map برگرداندن اندازه 
mapName.empty();     //  خالی است  map برگرداندن اینکه 
mapName.clear();     //  map خالی کردن 

مثال اول

با استفاده از پشته میخواهیم برنامه ای بنویسیم که تشخیص دهد یک پرانتز گذاری معتبر است یا نه برای هرکس اندیس جفت آن را بدست آورد.

balanced.cpp
#include <iostream>
#include <stack>
using namespace std;
const int MAX_N=100*1000;
int match[MAX_N];
string P;
stack<int> S;
bool notBalanced;
int main()
{
	cin >> P;
	for(int i=0;i<(int)P.size();i++)
	{
		if(P[i]=='(')
			S.push(i);
		else{
			if(S.empty()){
				notBalanced=true;
				break;
			}
			match[i]=S.top();
			match[match[i]]=i;
			S.pop();
		}
	}
	if(!S.empty())
        notBalanced=true;
	if(notBalanced)
		cout<<"The Input String is not Balanced !";
	else
		for(int i=0;i<(int)P.size();i++)
			cout<<match[i]+1<<" ";
	cout<<endl;
}

مثال 2

در مثال دوم میخواهیم ببنیم که جمع اعضای زیر مجموعه های یک مجموعه حداکثر $20$ عضوی چند عدد متمایز تولید میکنند.

subsetSum.cpp
# include <iostream>
# include <vector>
# include <set>
using namespace std;
int N;
vector<int> V;
set<int> S;
int main()
{
	cin >> N;
	for(int i=0;i<N;i++){
        int temp;
        cin >> temp;
        V.push_back(temp);
	}
	for(int mask=0;mask<(1<<N);mask++){
        int sum=0;
        for(int j=0;j<N;j++)
            if((mask>>j)&1)
                sum+=V[j];
        S.insert(sum);
	}
	cout<<S.size()<<endl;
	return 0;
}

ابزار صفحه