Algoritmer och datastrukturer TF3 Sy

samt
Algoritmer och datastrukturer med objektorienterad programmering, fristående kurs

Veckouppgift för vecka 7

1. Studera klassen List .

   Du får anta i denna uppgift att listan är platt, och innehåller heltal. Du får också anta att listan innehåller minst 2 tal.

   Utöka klassen med en metod int List::nast_storst(), som returnerar det näst största talet i listan.

   Funktionen ska skrivas iterativt. Du avgör själv i vilken utsträckning du vill använda de primitiverna. Efter exekveringen av nast_storst() ska den anropade listan finnas kvar oförändrat.

2. Studera klassen List .

   Skriv en metod void My_list::sam(My_list* l) till en klass My_list som ärver klassen List publikt. Både den anropade listan och listan l är sorterade listor av heltal.

   Metoden ska förändra den anropade listan så att den kommer att innehålla samtliga element ur den anropade listan och samtliga element ur l. Den resulterande listan ska vara sorterad. Uttryckt i andra termer ska de två listorna samsorteras till en. Din metod ska utnyttja att de två ursprungliga listorna redan är sorterade.

   Skriv metoden rekursivt. Använd primitiverna som finns definierade i klassen List på ett relevant sätt. Din metod ska med andra ord inte använda sig av explicit pekarhantering.

3. a) Specificera den abstrakta datatypen Urna, som innehåller ingen, en eller flera med naturliga tal numrerade kulor. Våra urnor kan inte innehålla dubletter och elementen har naturligtvis ingen ā priori given ordning. Urnorna kan dessutom, i denna värld, innehålla ett oändligt antal kulor. Du bör noggrant tänka igenom valet av primitiva funktioner. Tips: Tänk på att primitiver är enkla - snitt och union (definierade såsom på mängder) är m a o ej primitiver.

   b) Ge förslag på ett klasshuvud för Urnor i C++. Låt den klass du skapar heta Urna

   c) Implementera ditt förslag från deluppgifterna a) och b) på listor. Du ska naturligtvis använda klassen List på ett relevant sätt.

   d) Utöka din urnklass med en metod Urna* Urna::snitt(Urna* u) som returnerar snittet (definierat som på mängder, dvs naturligtvis utan dubletter) mellan den anropade urnan och urnan u. Du ska på ett relevant sätt använda de primitiver du implementerat i deluppgift c). Ingen av de ursprungliga urnorna får förstöras. Det är m a o ett rimligt antagande, i denna värld, att kulor kan skapas ur intet vid behov, och kan, när man så önskar, utan spår förstöras. Du får, om du hellre vill, returnera en urna i stället för en pekare till en urna, och/eller ge en urna, i stället för en pekare till en urna, som argument.

4. Skriv ett huvudprogram som testar funktionerna och klasserna i deluppgift 1 - 3.

OBS: Sökväg till källkod och körbar fil skall gälla på Datortekniks undervisningssystem, d.v.s. systemen i hus 1.