Další příklady Katedra softwarového inženýrství Katedra teoretické informatiky, Fakulta informačních technologii, ČVUT v Praze
© Karel Müller, 2011
Programování a algoritmizace 2, BI-PA2, 2011, Cvičení 11-13 BI-PA2
Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti
Karel Müller (ČVUT FIT)
Další příklady
BI-PA2, 2011, Cvičení 11-13
1/5
Další příklady Následující příklady mohou být zadány u zkoušky. Na cvičení budou probrány a za domácí úkol zadány jen některé z nich. 1. Stáhněte si a vyzkoušejte příklady z adresáře p11\matrix, array, set a table. Seznamte se s přetěžováním operátoru (), které je použito v šabloně Matrix. 2. Napište šablonu třídy Array1 pro realizaci jednorozměrného pole prvků typu T, kde parametry konstruktoru budou udávat dolní a horní mez indexu. 3. Napište šablonu třídy Array2 pro realizaci dvojrozměrného pole uloženého v souvislém paměťovém úseku, pro přístup k prvkům použijte přetížený operátor (). 4. Do třídy Set (viz přednáška) doplňte metodu card, jejímž výsledkem bude počet prvků množiny. 5. Napište šablonu třídy MultiSet úpravou třídy Set tak, aby umožňovala duplicity. Nápověda: pole upravte tak, aby každý prvek pole obsahoval počet výskytů. 6. Do šablon tříd realizujících množiny doplňte kontruktor, který vytvoří množinu z prvků pole daného parametrem. 7. Do šablon tříd realizujících množiny doplňte binární operátor – pro množinovou operaci diference (rozdíl).
Karel Müller (ČVUT FIT)
Další příklady
BI-PA2, 2011, Cvičení 11-13
2/5
Další příklady 8. Napište šablonu třídy List1 realizující jednosměrný spojový seznam s těmito operacemi: ins(x) vložení prvku s hodnotou x do seznamu del(x) odebrání prvku s hodnotou x ze seznamu incl(x) test, zda seznam obsahuje prvek s hodnotou x Pro třídu definujte kopírující konstruktor a operátor přiřazení používající techniku hluboké kopie. 9. Napište šablonu třídy List2 realizující dvojsměrný spojový seznam s těmito operacemi: ins(x) vložení prvku s hodnotou x do seznamu del(x) odebrání prvku s hodnotou x ze seznamu incl(x) test, zda seznam obsahuje prvek s hodnotou x Pro třídu definujte kopírující konstruktor a operátor přiřazení používající techniku hluboké kopie. 10. Napište šablonu třídy SrtList1 realizující jednosměrný vzestupně uspořádaný spojový seznam s těmito operacemi: ins(x) vložení prvku s hodnotou x do seznamu del(x) odebrání prvku s hodnotou x ze seznamu incl(x) test, zda seznam obsahuje prvek s hodnotou x Pro třídu definujte kopírující konstruktor a operátor přiřazení používající techniku hluboké kopie. Karel Müller (ČVUT FIT)
Další příklady
BI-PA2, 2011, Cvičení 11-13
3/5
Další příklady 11. Napište šablonu třídy SrtList2 realizující dvojsměrný vzestupně uspořádaný spojový seznam s těmito operacemi: ins(x) vložení prvku s hodnotou x do seznamu del(x) odebrání prvku s hodnotou x ze seznamu incl(x) test, zda seznam obsahuje prvek s hodnotou x Pro třídu definujte kopírující konstruktor a operátor přiřazení používající techniku hluboké kopie. 12. Napište šablonu třídy LstSet1 realizující množinu jednosměrným spojovým seznamem. 13. Napište šablonu třídy LstSet2 realizující množinu dvojsměrným spojovým seznamem. 14. Napište šablonu třídy SrtLstSet1 realizující množinu jednosměrným vzestupně uspořádaným spojovým seznamem. 15. Napište šablonu třídy SrtLstSet2 realizující množinu dvojsměrným vzestupně uspořádaným spojovým seznamem. 16. Napište šablonu třídy LstTab1 realizující tabulku jednosměrným spojovým seznamem. 17. Napište šablonu třídy LstTab2 realizující tabulku dvojsměrným spojovým seznamem. 18. Napište šablonu třídy SrtLstTab1 realizující tabulku jednosměrným vzestupně uspořádaným spojovým seznamem. 19. Napište šablonu třídy SrtLsTabt2 realizující tabulku dvojsměrným vzestupně uspořádaným spojovým seznamem. Karel Müller (ČVUT FIT)
Další příklady
BI-PA2, 2011, Cvičení 11-13
4/5
Další příklady 20. Napište program který přečte řadu čísel zakončenou nulou a vypíše nejprve všechna vzájemně různá záporná čísla a pak všechna vzájemně různá kladná čísla. 21. Napište program, který přečte řadu celých čísel zakončenou nulou a vypíše tabulku četnosti čísel. 22. Napište program, který přečte textový soubor složený ze slov (slovo je posloupnost písmen) a vypíše seznam vzájemně různých slov seřazený podle abecedy. 23. Napište program, který přečte textový soubor složený ze slov (slovo je posloupnost písmen) a vypíše tabulku četnosti slov. 24. Pro každou implementaci množiny odhadněte složitost operací v nejlepším a nejhorším případě. 25. Pro každou implementaci tabulky odhadněte složitost operací v nejlepším a nejhorším případě. 26. Pro různé způsoby implementace tabulky napište šablonu třídy realizující tabulku, ve které se mohou vyskytovat prvky se stejným klíčem. Operaci del(k) napište tak, aby v případě více prvků s klíčem k byl odstraněn prvek naposledy (nejdříve) vložený. 27. Do šablon realizujících množinu doplňte operaci uložení množiny do souboru a konstruktor pro vytvoření množiny ze souboru. 28. Do šablon realizujících tabulku doplňte operaci uložení tabulky do souboru a konstruktor pro vytvoření tabulky čtením souboru. Karel Müller (ČVUT FIT)
Další příklady
BI-PA2, 2011, Cvičení 11-13
5/5
