[go: up one dir, main page]
Scribd
Upload
98 views19 pages

Lab3 PDF

The document discusses templates in C++ including template functions, template classes, and examples of each. It also covers stacks as an abstract data type and provides an implementation of a stack class. Finally, it provides exercises related to templates, stacks, and sorting algorithms.

Uploaded by

Vasile
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
98 views19 pages

Lab3 PDF

The document discusses templates in C++ including template functions, template classes, and examples of each. It also covers stacks as an abstract data type and provides an implementation of a stack class. Finally, it provides exercises related to templates, stacks, and sorting algorithms.

Uploaded by

Vasile
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 19

Iulia-Cristina Stanica

iulia.stanica@gmail.com
 Template functions
 Template classes
 Stack
 Using headers
 Applications of stack
 Info: Sorting algorithms
 Generic programming
 Allows a function or class to work on many
different data types without being rewritten
for each one
 A function template allows any type of data (T)
for its arguments
 Syntax:
template <typename T>
T functionName(T a, T b)
{
// code
}
 typename can be replaced with class
 Ex:
template <typename T>
T maxim(T a, T b) {
return a > b ? a : b; //if a>b return a, else, b
// equivalent to: if (a>b) return a; else return b;
}

 Function call:  Ex. templates


◦ maxim (10, 15); (std):
◦ maxim (1.3, 2.4); • std::min,
or: std::max
◦ maxim<int> (10, 15); • std::count,
std::sort etc.
 A generic class, which allows any type (T) for
its members
 Syntax:
template <typename T>
class className{
// code
};
 Create objects:
◦ className <type> object (…);
template <class T>
class mypair {
T values [2];
public:
mypair (T first, T second)
{
values[0]=first;
values[1]=second;
}
};

Create objects:
 mypair <int> object (25, 13);
 Example with 2 fields:

template<typename Type1, typename Type2>


class KeyValue
{
public:
int key;
Type1 value1;
Type2 value2;
//constructor with 2 fields
};

 We create objects:
◦ KeyValue <int, char> obj (12, ‘c’);
Change the class Point from the previous lab
by using templates (the x and y coordinates
are of type T). Test the class using float and
int coordinates.
Write a template function to sort an array of 5
elements. Write a different template function for
swapping 2 values of the array. Read the values
from keyboard.

Array declaration: int a[5];


 Instance of an abstract data type (ADT)
 Formalizes the concept of the LIFO
collection (last in first out)
 push(x)
◦ Adds the element x at the top of the stack
 pop()
◦ Removes the element from the top of the stack
and returns it
◦ Returns an error if the stack is empty
 peek()
◦ Returns (but does not remove) the element at the
top of the stack
 isEmpty()
◦ Returns 1 if the stack is empty and 0 otherwise

See implementation on moodle!


a) Test the implementation of the stack. Call
the various functions (pop, push, peek)
b) Define the Stack class in a header file (e.g.
mystack.h) and test it in a different file
which contains the main function and
includes the header:
#include “mystack.h”
c) Add the following method to the class Stack:
 Display all the elements of a stack.
 Write a program which reads a number n
and n numbers of type double. The
numbers are displayed in reversed order
using the stack.
1. Search for a new sorting method (not bubble sort or
selection sort) and implement it in C++.
By using the class Point from the previous homework,
create a function which sorts 5 points using the
previously chosen sorting method. You should take as a
sorting criteria the distance of the point from the origin.

2. Given a string check if it's a palindrome or not using


Stack.
Ex: “a santa at nasa”, “a nut for a jar of tuna” are
palindromes.
HINT exo 2: (create a char array)
#include <iostream>
#include <string>
using namespace std;
int main(){
string s ="Hello";
char suite[10];
for(int i=0; i<s.length(); i++){
suite[i]=s[i];
cout<<suite[i]<<" ";
}
}
 Implement a template class called LargeStack which can store
elements of type T. The class will have the following
members:
Stack<T> Smain, Saux;
 Smain is the main stack which allows storing the values
added in the LargeStack. Saux is an auxiliary stack which
must be empty before and after the call of any function from
the class LargeStack (Saux is used only for internal
operations)
 The class LargeStack has the following methods:
◦ void push(T x): add the element x at the top of the Smain stack.
◦ T pop() : deletes and returns the element situated at the top of the Smain
stack
◦ void swap(int i, int j): changes the values from the levels i and j of the
Smain stack (The levels are numbered starting from 0.
HINT: You can use the auxiliary stack Saux in order to store
temporarily the elements of the Smain stack. You can use all
the methods from the Stack class (pop, push, isEmpty etc.)
for the variables Smain and Saux.
1. Bubble sort
Method: Compare each two adjacent items and swap
their positions if they are in the wrong order.
bool ok = false;
int n = tab.size();
while(!ok)
{
ok = true;
for(int i=0 ; i < n-1; i++)
{
if(tab[i] > tab[i+1])
{
// swap the 2 elements tab[i],tab[i+1]
ok = false;
}
}
n--;
}
2. Selection sort
Method: search for the smallest element, place it on the
first position of the array, restart with the second
smallest element, place it on the second position etc.,
until we run through the whole array.
for (int i=0; i<n-1; i++)
{
int minIndex = i;
for(int j=i+1; j<n; j++)
{
if(tab[j]<tab[minIndex])
{
minIndex= j;
}
}
if (minIndex != i)
// // swap the 2 elements tab[i], tab[minIndex];
}

You might also like