Category Archives: cpp

Ottimizzare codice c++

Queste ottimizzazioni sono facili da applicare a codice gia esistente e in molti casi danno come risultato un aumento della velocita di esecuzione del codice. Ricorda "the fastest code is code that isn't called" ossia "il codice piu veloce è quello non chiamato".

Usa liste di inizializzazione

Usa sempre liste di inizializzazione nei costruttori. Ad esempio, usa

    TMyClass::TMyClass(const TData &data) : m_Data(data)
    {
    }

piuttosto

    TMyClass::TMyClass(const TData &data)
    {
         m_Data = data;
    }

Senza liste , le variabili del costruttore di default sono invocate prima del costruttore della classe. Con le liste di inizializzazione solo una copia del costruttore è invocata.

Continua a leggere : http://www.custard.org/~andrew/optimize.php

Struttura dati stack in c++

Obiettivo
In questo articolo tratteremo la struttura dati stack

Lo stack
Uno stack e' l'opposto di una cosa perche' utilizza un accesso ai dati di tipo LIFO (last-in,first-out) cioe'
l'ultimo ad entrare e' il primo ad uscire.
Per pensare fisicamente a uno stack, immaginiamo una pila di piatti. Il primo piatto poggiato sul tavolo sarà
l'ultimo a essere utilizzato mentre l'ultimo piatto sara' preso per primo.
Per lo stack definiamo due operazioni push e pop che rispettivamente inseriscono e tolgono i dati
dallo stack.

Codice

#include <iostream.h>
#include <stdio.h>
#include <string.h>

class ADT
{
protected :
int modify; // boolean

public :
ADT (int m = 1) : modify(m) { }
};

// Per semplicita' le derivazioni seguenti sono di tipo
// "public" ma dovrebbero essere ragionate ...

class Counter : public virtual ADT
{
private :
int value;

public :
Counter (int v=0, int m=0) : value(v), ADT(m) { }

int Get () const { return value; }
void Inc () { if (modify) value ++; }
void Dec () { if (modify) value --; }
};

template <class T>
class Stack : public virtual ADT
{
protected :
T * ptr;
int top;
int maxsize;

public :
Stack (int=3, int=1);
Stack (Stack &);
~Stack ();

void Push (const T);
T Pop ();
int Empty () const;

friend ostream & operator << (ostream &, const Stack &);
// const Stack & operator = (const Stack &);
};

template <class T>
class STACK : public Counter, public Stack<T>
{
public :
STACK (int = 2);
~STACK ();

void Push (const T);
T Pop ();
int Length () const;

STACK operator+ (STACK &);
friend ostream & operator << (ostream &, const STACK &);
};

// ************************ Stack ***************************

template <class T>
Stack<T>::Stack (int dim, int modify) :
maxsize(dim), top(-1), ADT(modify)
{
ptr = new T [maxsize];
}

template <class T>
Stack<T>::Stack (Stack<T> & s) :
maxsize(s.maxsize), top(s.top), ADT(s.modify)
{
ptr = new T [maxsize];
for (int i=0; i<=top; i++) ptr[i] = s.ptr[i];
}

template <class T>
Stack<T>::~Stack ()
{
delete [] ptr;
}

template <class T>
void Stack<T>::Push (const T data)
{
if (! modify || top>=maxsize-1) return;
ptr[++top] = data;
}

template <class T>
T Stack<T>::Pop ()
{
if (! modify || Empty()) return NULL;
return ptr[top--];
}

template <class T>
int Stack<T>::Empty () const
{
return (top == -1);
}

template <class T>
ostream & operator << (ostream & left, const Stack<T> & s)
{
char buffer[200] = "Stack = { ", buf[10];

for (int i=0; i<=s.top; i++)
{
sprintf (buf, "%d, ", s.ptr[i]);
strcat (buffer, buf);
}
return left << buffer << " }\n";
}

// ************************ STACK ***************************

template <class T>
STACK<T>::STACK (int size) :
Stack<T>(size,1), Counter()
{ }

template <class T>
STACK<T>::~STACK ()
{ }

template <class T>
void STACK<T>::Push (const T data)
{
if ( maxsize == Get() )
{
T * aux = new T [2*maxsize];
for (int i=0; i<=top; i++) aux[i] = ptr[i];
Stack<T>::~Stack();
ptr = aux;
maxsize *= 2;
}
Stack<T>::Push (data);
Inc ();
}

template <class T>
T STACK<T>::Pop ()
{
if (Get () < 1) return NULL;
Dec ();
return Stack<T>::Pop ();
}

template <class T>
int STACK<T>::Length () const
{
return Get ();
}

template <class T>
STACK<T> STACK<T>::operator+ (STACK<T> & s)
{
STACK<T> tmp(maxsize+s.maxsize);
int i;

for (i=0; i <= (top < s.top ? top : s.top); i++)
{
tmp.ptr[2*i] = ptr[i]; tmp.Inc();
tmp.ptr[2*i+1] = s.ptr[i]; tmp.Inc();
}

int j = 2*i;
if (top < s.top)
for (; i<=s.top; i++)
{
tmp.ptr[j++] = s.ptr[i]; tmp.Inc();
}
else
for (; i<=top; i++)
{
tmp.ptr[j++] = ptr[i]; tmp.Inc();
}
tmp.top = j-1;
return tmp;
}

template <class T>
ostream & operator << (ostream & left, const STACK<T> & s)
{
char buffer[200] = "Stack = { ", buf[10];

for (int i=0; i<=s.top; i++)
{
sprintf (buf, "%d, ", s.ptr[i]);
strcat (buffer, buf);
}
return left << buffer << " }\n";
}

// ************************* main ***************************

void main ()
{
/* Stack<int> a(3);

a.Push(2);
a.Push(3);
a.Push(4);
a.Push(5);

Stack<int> b = a;

cout << a; a.Pop(); a.Pop(); cout << a << '\n';
cout << b; b.Pop(); b.Pop(); cout << b;
*/
STACK<int> c, d;

c.Push(19); c.Push(29); c.Push(39);
d.Push(17); d.Push(27);
cout << "Prima :\n" << c << d;

STACK<int> somma;
somma = d+c+d;
cout << somma;
d.Pop(); d.Pop(); d.Pop();
cout << "Dopo :\n" << c << d << somma;
}

Converte stringa da postfissa a infissa in c++

Obiettivo
In questo articolo tratteremo un programma che converte una stringa da
formato postfisso a formato infisso attraverso uno stack.

La notazione infissa e postfissa
La notazione infissa e' il modo comune di scrivere una espressione artimetica cioe':
(6+2)*5-8/4
Nella notazione postfissa l' operatore e' scritto dopo gli operandi
(non servono parentesi ne conoscere la precedenza ed associativita` degli operatori )
L' espressione precedente puo` essere scritta come:
3 4 + 5 * 8 4 / -
e puo` essere facilmente calcolata per mezzo di una pila usando l'algoritmo che segue.

Codice

#include<stdio.h>
#include<stdlib.h>
#define MAX 1000
typedef struct pila
{
int elem[MAX];
int top;
}PILA;

PILA *crea();
int push(PILA *,int);
int pop(PILA *,int *);
int vuota(PILA *);
int piena(PILA *);
void postfix(char *,char *,PILA *);
int valuta(char *,PILA *);
main()
{
char exp[10];
char expin[10];
PILA *p;
p=crea();
printf("inserisci stringa");
scanf("%s",exp);
postfix(exp,expin,p);
printf("risultato:%d",valuta(expin,p));
}

void postfix(char *x,char *y,PILA *p)
{
while(*x!='\0')
{
if(*x=='(');
if(*x=='+')push(p,*x);
if(*x=='-')push(p,*x);
if(*x=='*')push(p,*x);
if(*x=='/')push(p,*x);
if(*x==')')
{
pop(p,(int *)y);
y++;
}

if(*x>='0' && *x<='9')
{
*y=*x;
++y;
}
x++;
}

while(p!=NULL)
{
pop(p,(int *)y);
y++;
}
return;
}

int valuta(char *x,PILA *p)
{
int a,b,c=0;
while(*x!='\0')
{
if(*x=='+')
{
(pop(p,&a) && pop(p,&b));
c=a+b;
}
if(*x=='-')
{
(pop(p,&a)&&pop(p,&b));
c=a-b;
}
if(*x=='*')
{
(pop(p,&a)&&pop(p,&b));
c=a*b;
}
if(*x=='/')
{
(pop(p,&a)&&pop(p,&b));
c=a/b;
}
if(*x>='0'&&*x<='9')
{
scanf(x,"%d",&c);
push(p,*x);
x++;
}
}
return (int)x;
}

PILA *crea()
{
PILA *p;
p=(PILA *)malloc(sizeof(PILA));
p->top=0;
return p;
}

int vuota(PILA *p)
{
if(p->top<=0)return 1;
else return 0;
}

int piena(PILA *p)
{
if(p->top>=MAX)return 1;
else return 0;
}

int push(PILA *p,int d)
{
if(piena(p))return 0;
else
{
p->elem[p->top]=d;
p->top++;
}
return 1;
}

int pop(PILA *p,int *d)
{
if(vuota(p))return 0;
else
{
*d=p->elem[p->top];
p->top--;
}
}

Struttura dati pila c++

Obiettivo
In questo articolo tratteremo la struttura dati pila

La pila
Una pila e' l'opposto di una cosa perche' utilizza un accesso ai dati di tipo LIFO (last-in,first-out) cioe'
l'ultimo ad entrare e' il primo ad uscire.
Per pensare fisicamente a una pila, immaginiamo una pila di piatti. Il primo piatto poggiato sul tavolo sarà
l'ultimo a essere utilizzato mentre l'ultimo piatto sara' preso per primo.
Per la pila definiamo due operazioni push e pop che rispettivamente inseriscono e tolgono i dati
dalla pila.

Codice

typedef struct pila
{
int elem;
struct pila *next;
}PILA;

 

PILA *crea_pila()
{
PILA *p;
p=NULL;
return p;
}

 

int vuota(PILA *p)
{
if(p==NULL)return 1;
else return 0;
}

 

int piena(PILA *p)
{
return 0;
}

 

int push(PILA **p,int d)
{
PILA *ptr;
if(piena(p))return 0;
else
{
ptr=(PILA *)malloc(sizeof(PILA));
ptr->elem=d;
ptr->next=*p;
*p=ptr;
}
return 1;
}

 

int pop(PILA **p,int *d)
{
PILA *ptr;
if(vuota(p))return 0;
else
{
*d=*p->elem;
ptr=*p;
*p=*p->next;
free(ptr);
return d;
}

Struttura dati pila

Obiettivo
In questo articolo tratteremo la struttura dati pila

La pila
Una pila e' l'opposto di una cosa perche' utilizza un accesso ai dati di tipo LIFO (last-in,first-out) cioe'
l'ultimo ad entrare e' il primo ad uscire.
Per pensare fisicamente a una pila, immaginiamo una pila di piatti. Il primo piatto poggiato sul tavolo sarà
l'ultimo a essere utilizzato mentre l'ultimo piatto sara' preso per primo.
Per la pila definiamo due operazioni push e pop che rispettivamente inseriscono e tolgono i dati
dalla pila.

Codice

#define MAX 100

typedef struct pila
{
int elem[MAX];
int top;
}PILA;

 

PILA *crea_pila()
{
PILA *p;
p=(PILA *)malloc(SIZEOF(PILA));
p->top=0;
return p;
}

int vuota(PILA *p)
{
if(p->top<=0)return 1;
else return 0;
}

int piena(PILA *p)
{
if(p->top>=MAX)return 1;
else return 0;
}

 

int push(PILA *p,int d)
{
if(piena(p))return 0;
else
{
p->elem[p->top]=d;
p->top++;
}
return 1;
}

 

int pop(PILA *p,int *d)
{
if(vuota(p))return 0;
else
{
*d=p->elem[p->top];
p->top--;
}

Algoritmi di ordinamento in c++

Obiettivo
In questo articolo tratteremo tre algoritmi di ordinamento: inserction sort,
selection sort, bubble sort.

Funzione ausiliaria

FUNZIONE AUSILIARIA CHE SCAMBIA DUE ELEMENTI

void scambia(int a,int b)
{
int tmp;
a=tmp;
a=b;
b=tmp;
}

Selection sort
Il selection sort invece è un metodo che cerca il valore più grande e lo mette alla fine dell'array,
facendo lo scambio fra la posizione con il valore maggiore e l'ultima cella dell'array.

void selection(int a[],int n)
{
int i,j,min;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[min])min=j;
}
scambia(a[min],a[i])
}
}

Insertion sort
Un esempio di insertion sort occorre nella vita di ogni giorno mentre giochiamo a carte.
Per ordinare le carte nelle tue mani estrai una carta, "scala" le carte rimanenti,
e inserisci la carta estratta nel posto corretto. Questo processo è ripetuto finchè tutte
le carte sono nella sequenza corretta.
Il metodo di ordinamento ad inserzione trae lo spunto dall'idea che un vettore ordinato si
ottiene inserendo le sue componenti una per una "al posto giusto". Non si introduce un secondo
vettore, ma si "simula" l' inserzione degli elementi nel vettore dato

void insertion(int a[],int n)
{
int i,j,val;
for(i=1;i<n;i++)
{
val=a[i];
for(j=i;j>0&&a[j-1]>val;j--)
{
a[j]=a[j-1];
}
a[j]=val;
}
}

Bubble sort
Il bubble sort e' un algoritmo di scambio. L'algoritmo implica la ripetizione di confronti e, se necessario, lo
scambio di elementi adiacenti. Gli elementi sono come bolle in un serbatoio di acqua, ognuna delle quali cerca il
proprio livello.
Supponiamo di voler ordinare questi elementi DCAB
passo 1 ADCB
passo 2 ADBC
passo 3 ABCD

void bubble(int a[],int n)
{
int i,j;
for(i=1;i<n;i++)
for(j=n-1;j>=i;j--)
{
if(a[j-1]>a[j])
{
scambia(a[j-1],a[j])
}
}
}

Struttura dati matrice in c++

Obiettivo
In questo articolo tratteremo come definire una matrice

Codice

#include <iostream.h>
#include <stdlib.h>

template <class T>
class Matrix
{
private :

int rows, cols;
T * element;

public :

Matrix (int r=0, int c=0);
Matrix (int r, int c, T value);
Matrix (const Matrix<T> & m);
~Matrix () { delete [] element; }

int Rows () const { return rows; }
int Columns () const { return cols; }

T & operator ( ) (int i, int j) const;
Matrix<T> & operator = (const Matrix<T> & m);
Matrix<T> operator + () const;
Matrix<T> operator + (const Matrix<T> & m) const;
Matrix<T> operator - () const;
Matrix<T> operator - (const Matrix<T> & m) const;
Matrix<T> operator * (const Matrix<T> & m) const;
Matrix<T> operator += (const T & x);

void Show () const;

}; // End class Matrix

template <class T>
Matrix<T>::Matrix (int r, int c)
{
if (r<0 || c<0)
{
cout << "Indici errati\n";
return;
}

rows = r;
cols = c;
element = new T [r*c];
}

template <class T>
Matrix<T>::Matrix (int r, int c, T value)
{
if (r<0 || c<0)
{
cout << "Indici errati\n";
return;
}

rows = r;
cols = c;
element = new T [r*c];

for (int i=0; i<rows*cols; i++)
element[i] = value;
}

template <class T>
Matrix<T>::Matrix (const Matrix<T> & m)
{
rows = m.rows;
cols = m.cols;
element = new T [rows*cols];

for (int i=0; i<rows*cols; i++)
element[i] = m.element[i];
}

template <class T>
T & Matrix<T>::operator () (int i, int j) const
{
if (i<1 || i>rows || j<1 || j>cols)
{
cout << "Indici errati";
exit (1);
}

return element [ (i-1)*cols + j - 1 ];
}

template <class T>
Matrix<T> Matrix<T>::operator + (const Matrix<T> & m) const
{
if ( rows != m.rows || cols != m.cols )
{
cout << "Operazione non consentita\n";
return NULL;
}

Matrix<T> result(rows, cols);

for (int i=0; i<rows*cols; i++)
result.element[i] = element[i] + m.element[i];

return result;
}

template <class T>
Matrix<T> Matrix<T>::operator * (const Matrix<T> & m) const
{
if ( cols != m.rows )
{
cout << "Operazione non consentita\n";
return NULL;
}

Matrix<T> result (rows, m.cols);
int c1=0, c2=0, c=0;

for (int i=1; i<=rows; i++)
{
for (int j=1; j<=m.cols; j++)
{
T sum = element[c1] * m.element[c2];
for (int k=2; k<=cols; k++)
{
c1++;
c2 += m.cols;
sum += element[c1] * m.element[c2];
}
result.element[c++] = sum;
c1 -= cols-1;
c2 = j;
}
c1 += cols;
c2 = 0;
}
return result;
}

template <class T>
void Matrix<T>::Show () const
{
for (int i=0; i<rows; i++)
{
for (int j=0; j<cols; j++)
cout << element[(i*cols)+j] << '\t';
cout << '\n';
}
}

void main ()
{
Matrix<int> A(2,3,1);
cout << "A = \n"; A.Show();
Matrix<int> B = A+A+A;
B(1,1)=0; B(2,3)=9;
cout << "B = \n";
B.Show();
cout << endl;
}

Struttura dati lista doppiamente concatenata

In questo articolo tratteremo la struttura dati lista doppiamente concatenata

typedef struct lista
{
int dato;
struct lista *next,*prec;
}LISTA;

void insert(LISTA **h,LISTA **t,int d)
{
LISTA *ptr;
ptr=(LISTA *)malloc(sizeof(LISTA));
ptr->dato=d;
ptr->prec=NULL;
ptr->next=*h;
if(*t==NULL)
*h=*t=ptr;
else
{
*h->prec=ptr;
*h=ptr; 
}
}

 

int cancella(LISTA **h,LISTA **t,int d)
{
LISTA *ptr,*paus;
int trovato=0;
while(*h->dato==d)
{
paus=*h;
*h=*h->next; /*sposto la testa nella prossima locazione e libero la precedente*/
free(paus)
if(*h==NULL) /*se non ci sono piu caselle*/
{
*t=NULL; /*metto la coda a NULL e ritorno 1*/
return trovato=1;
}
else
{
*h->prec=NULL; /*altrimenti la testa è nella nuova casella e faccio puntare il prec*/
trovato=1; /*della casella precedente a NULL x' l'ho liberato prima*/
}
}

ptr=*h->next;
while(ptr!=NULL)
{
if(ptr->dato==d)
{
trovato=1;
paus=ptr;
if(ptr==*t) /*se la casella è l'ultima*/ 
{
*t=ptr->prec;
*t->next=NULL;
free(paus);
return trovato;
}
else /*se ci sono altre caselle*/
{
ptr->next->prec=ptr->prec;
ptr->prec->next=ptr->next;
ptr=ptr->next;
}
FREE(paus);
}
else ptr=ptr->next;
}
return trovato;

Struttura dati lista 2

In questo articolo tratteremo la struttura dati lista

#include <iostream.h>
#include <stdio.h>
#include <string.h>

class Data
{
private :

char buffer [80];

public :

Data () { }
Data (const char * str) { strcpy (buffer, str); }

const char * Get () const { return buffer; }

}; // End class Data

class Node
{
private :

Data * ptr;
Node * next;

public :

Node (Data d)
{
ptr = new Data (d.Get());
next = NULL;
}

~Node() { delete ptr; }

const Data * GetData () const { return ptr; }
Node * GetNext () const { return next; }
void SetNext (Node * x) { next = x; }

}; //End class Node

class List
{
private :

Node * front;
Node * rear;
int NodesNumber;

public :

List () : front(NULL), rear(NULL), NodesNumber(0) { }
~List ();

void operator += (Data);
const char * operator [ ] (int) const;

void Show () const;

}; //End class List

List::~List ()
{
Node * p, *q = front;

while ( (p = q) != NULL)
{
q = p -> GetNext();
delete p;
}
}

void List::operator += (Data d)
{
Node * aux = new Node (d);

NodesNumber++;
if (front == NULL)
{
front = rear = aux;
}
else
{
rear -> SetNext (aux);
rear = rear->GetNext();
}
}

const char * List::operator [ ] (int index) const
{
if (NodesNumber <= index)
{
cout << "Non ci sono cosi' tanti elementi.\n";
return NULL;
}

for (Node * p = front; index > 1; index--, p = p->GetNext() );

return p -> GetData() -> Get();
}

void List::Show () const
{
Node * p = front;

cout << "< ";
while ( p != NULL)
{
cout << p -> GetData() -> Get() << ", ";
p = p -> GetNext();
}
cout << "\b\b >";

}

void main ()
{
const Dim = 5;
char * elements [Dim] = { "Primo", "Secondo",
"Terzo", "Quarto", "Quinto" };
List lista;

for (int i = 0; i<Dim; i++)
lista += Data(elements[i]);

cout << "Il secondo elemento in lista e' : " << lista[2] << endl;

cout << "LISTA : ";
lista.Show ();
cout << endl;
}