Topshiriq Graf cho’qqilarini bo’yash algoritmlari

Topshiriq

Stek o’zi nima ? Oshxonadagi likopchalar turadigan quti, brovserning orqaga("nazad") tugmasi, ixtiyoriy matn muxarriridagi bekor qilish("CTRL-Z") amali, bularning barchasi Stek ma'lumotlar strukturasiga misoldir. "LIFO" y'ani oxirgi kegan birinchi ketadi qoidasi asosiga qurilgan bo'lib kompyuter olamida eng ko'p ishlatiladigan ma'lmumotlar strukturasidan biri. Demak, bugun Stek(Stack) ma'lumotlar strukturasini o'rganamiz.

Quyidagi rasmda stekning sodda ifodasi berilgan.

Rasmda ko'rinib turganidek, stek bu obyektlarning ro'yxati bo'lib, eng oxirgi qo'shilgan obyekt xar doim birinchi bo'lib qaytadi. Masalan, ushbu rasmdagi stekka yangi qiymat qo'shilsa A bitta pastga tushadi, yangi qo'shilgan obyekt "top" o'rinni egallaydi. Keyingi murojaat vaqtida aynan yangi qo'shilgan obyekt qaytariladi.

Ushbu ro'yxatda Stekning tarkibida bo'lgan operatsiyalar berilgan.

Push(value) stekka yangi qiymat qo'shadi. Aytib o'tilganidek, yangi qaiymat "top" o'ringa borib tushadi.

Pop()eng oxirgi qo'shilgan obyekt qaytariladi va stekdan o'chiriladi.

Peek()eng oxirgi qo'shilgan qaytariladi leki stekdan o'chirilmaydi.

IsEmpty() stek bo'shmi? degan savolga javobgar metod.

Size() stekdagi obyektlar sonini qaytaradi.

Stekning implementasiyasi ikki xil usulda bajarilishi mumkin. Zanjir(Linked) va Massiv. Ularning farqiga to'xtalib o'tamiz, lekin undan oldin IStack interfacega diqqat qilamiz.

#include

#include

using namespace std;

int main()

{

stack st,nt;

int n,x;

cout<<"Elementlar soni: ";

cin>>n;

puts("Stack:");

for(int i=0;i

cin>>x;

st.push(x);

}

puts("\nNatija:");

for(int i=0;i

{ x=st.top();

st.pop();

if(n%2==0)

{

if(i!=n/2||i!=(n/2-1))

nt.push(x);

}

else

{

if(i!=n/2)

nt.push(x);

}

}

while(!nt.empty())

{

cout<

nt.pop();

}

return 0;

}

Zanjir yoki Linked Stek. Esingizda bo'sla LinkedList haqida gaplashganimizda Node ma'lumotlar strukturasi haqida so'z yuritganmiz. Stekning bu ko'rinishini asosini ham ushmu MS tashkil qiladi. Stekdagi barcha element o'zidan keyingi elementga bo'glangan bo'ladi va ushbu ketma-ketlik yordamida stekdagi "top" elementni aniqlab olamiz. Ushbu usulda yaratilga Stekning vaqt murakkabligi quyidagi jadvalda berilgan.

Barcha amallarni asosini o'zlashtirish amali tashkil qilgani sababi barcha metodlar O(1) vaqtda bajariladi.

Massivga asoslangan Stek. Massivning qulayliklaridan biri bu indeks orqali massivda joylashgan elementni O(1) vaqtda qaytara olishdir. Lekin massivdagi elementlar soni ko'payib ketsa qimmatbaho amal - hajmni kengaytirish lozim bo'ladi. O'z hajmini o'zi o'zgartira oladigan massiv dinamik massiv deyiladi. .Net dasturlash tili oilasidagi List dinamik massivida asosida qurilgan.

Nazariyaga ko'ra Push(T value) O(n) bu eng yomon holatdur, lekin Resize() ning chaqirilish ehtimolligi har chaqirilgandan so'ng pasayib boradi. Natijada, yuqoridagi metodni O(1) vaqt murakkablikka ega deb qabul qilishimiz mumkin. Buning sababi esa, massivning yangi o'lchami oldingisidan ikki baravar kattaligidadur. Ya'ni aytayik massivni yaratdik, uning boshlang'ish o'lchami 50 edi. Massivning kengayib borish tartibi esa; 50,100,200,400,800,160,320... Ahamiyat bergan bo'lsangiz bir necha marta chaqirilgandan so'ng yetarlicha o'lchamdagi massivga ega bo'lamiz. Bu jihatni amortizatsiya analiz usuli bilan aniqlashimiz mumkin.

LStack vs AStack. Xo'p, ikkala usulda ham amallar O(1) murakkablikka ega bo'lsa, qaysi birida foydalanishimiz lozim? Yaxshi savol, so'raganizdan hursandman. AStack ning kamchiligi, egalllanadigan hotiraning isrof bo'lishi, ya'ni boshlang'ich vaziyatda ma'lum bir o'lchamda massiv yaratishi va ushbu massivning hamma xonasi ham ishlatilmay qolishligidadir.LStack esa faqat kerak bo'lgan taqdirdagina hotiradan joy egallaydi. AStack ning ham qulayliklari bor masalan, massivda "locality" degan hususiyat bo'lib, missivdagi elementlarning bir-biriga yaqinroq joylashgani hisobiga tezroq ishlashi mumkin.