Lezione in C/C++ – Gli alberi

Gli alberi

Ecco un passaggio più complesso, le liste sono direzionate in modo lineare, una sussegue all’altra. In questo caso l’albero a differenza della lista ha tre direzioni, sinistro, destro e precedente.

La struttura è la seguente:

struct node
{
long int value;
struct node *left;
struct node *right;
struct node *root;
};

Quindi il nodo ha una chiave, il valore value
Il nodo successivo sinistro left
Il nodo successivo destro right
Il nodo precedente root

Per gestire questa struttura, come per le liste c’è, l’inserimento, l’eliminazione e la ricerca di un elemento. Ma c’è anche la ricerca del minimo e del massimo, la visualizzazione degli elementi in ordine, pre-ordine, post-ordine e la ricerca del successivo o del precedente rispetto ad un valore.

Dunque:

Inserimento

La funzione

short int insert(long int number,struct node **q)

La funzione necessita del valore da inserire e la struttura dell’albero, ritorna con un valore per determinare il successo dell’operazione.

Le variabili sono:

short int save;
struct node *p,*list;

La variabile save viene usata per l’inserimento di un valore.
La variabile p e il nuovo elemento da allocare
La variabile list prende la posizione dell’albero q

L’allocazione di un nuovo nodo è il seguente

p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
return(0);
}
p->value=number;

Come prima cosa bisogna aver presente la struttura ad albero vuota, quindi si inserisce il primo elemento.

if(list==NULL)
{
p->root=NULL;
list=p;
*q=list;
return 1;
}

La struttura non è vuota e il nodo va inserito o nella lista di sinistra o di destra

save=0;
do{
if(number > list->value)
{
if(list->right!=NULL)list=list->right;
else
{

list->right=p;
save=1;
p->root=list;
}
}
else
{
if(list->left!=NULL)list=list->left;
else
{

list->left=p;
save=1;
p->root=list;
}
}
}while(save==0);

Quindi il valore viene confrontato con l’elemento del nodo attuale, se è maggiore viene controllata la lista di destra altrimenti quella di sinistra, quando viene trovato un elemento vuoto viene aggiunto l’elemento con l’elemento radice precedente e esce dal ciclo.

A questo punto non rimane altro che posizionarsi all’inizio

for(;list->root!=NULL;list=list->root);
*q=list;
return 1;

La lista torna al primo elemento

Nota: in questo esempio e possibile inserire i duplicati, ma si può evitarlo. Altra cosa si può inserire agli ultimi elementi il primo elemento o un nodo satellite che definisce la fine dell’albero.

Ricerca

La ricerca e’ semplice, se viene trovato l’elemento corrispondente a quello cercato ritorna con l’indirizzo del nodo. In ogni caso se il valore è maggiore del nodo corrente ci si sposta a destra, altrimenti a sinistra. Nel caso non viene trovato restituisci NULL

if(p==NULL)return NULL;
if(number == p->value)return p;
if(number > p->value)q=search(number,p->right);
if(number < p->value)q=search(number,p->left);
return q;

Cancellazione

La cancellazione avviene tramite la ricerca di un valore, viene rimosso il nodo ed eliminato. Attenzione pero, se è il primo elemento iniziale dell’albero bisogna spostare l’indirizzo dell’albero sul successivo; questo successivo viene determinato dalla funzione remove.

q=search(number,*p);
if(q==NULL)return 0;

if(q==*p)
{
remove (&q);
*p=q;
}
else
{
remove (&q);
free(q);
}
return 1;

NOTA: la funzione remove viene posta nella condizione if poiché se inserita prima falsa il risultato

La funzione remove ha quattro obiettivi:

1 – Se il nodo corrente non ha figli
2 – Se il nodo corrente ha il figlio destro
3 – Se il nodo corrente ha il figlio sinistro
4 – Se il nodo corrente ha due figli

Il nodo non ha figli

if(p->left==NULL && p->right==NULL)

Chi è l’elemento precedente?

q=p->root;

Se il figlio dell’elemento precedente è o sinistro o destro che coincide con il corrente elimina il collegamento

if(q->left==p)q->left=NULL;
if(q->right==p)q->right=NULL;

Ma se l’elemento precedente è nullo allora bisogna aggiornare l’albero che non ha nessun elemento

*tree=NULL;

Il nodo ha un figlio

if(p->left==NULL && p->right!=NULL)
oppure
if(p->left!=NULL && p->right==NULL)

Se l’elemento precedente sinistro o destro coincide con il corrente, il precedente è collegato con il successivo destro o sinistro del corrente

Nodo destro:

if(q->left==p)q->left=p->right;
if(q->right==p)q->right=p->right;
p->right->root=q;

Nodo sinistro

if(q->left==p){q->left=p->left;}
if(q->right==p)q->right=p->left;
p->left->root=q;

Se l’elemento precedente è nullo, l’elemento corrente deve cancellare l’elemento precedente e passare sul successivo. Quindi l’albero punta sull’elemento corrente

Destro

q=p;
p=p->right;
p->root=NULL;
*tree=p;

Sinistro

q=p;
p=p->left;
p->root=NULL;
*tree=p;

Il nodo ha due figli

Si definisce il nodo precedente

t=p->root;

Si trova il nodo valore successivo del corrente

q=next(p->value,p);

E si effettua la rimozione di questo nodo

remove(&q);

A questo punto se il precedente non è vuoto, controlla se il sinistro o destro coincide con l’elemento corrente, quindi collegalo con il successivo.

if(t->left==p)t->left=q;
if(t->right==p)t->right=q;

Non rimane altro che sostituire il nodo corrente con il successivo

q->root=t;
if(p->left==NULL)q->left=NULL;
else
{
q->left=p->left;
p->left->root=q;
}

if(p->right==NULL)q->right=NULL;
else
{
q->right=p->right;
p->right->root=q;
}

Fine della procedura remove.

Sucessivo

Se il nodo corrente è nullo ha trovato niente

if (p==NULL)return NULL;

Il nodo corrente è uguale al valore cercato, il valore destro esiste? Si, ritorna con il valore minimo del valore destro, altrimenti cerca nel nodo precedente

if (number == p->value)
{
if(p->right!=NULL)
{
return min(p->right);
}
else
{
return parent_next(number,p->root);
}
}

Se il valore è maggiore del nodo corrente continua a cercare nella lista a destra altrimenti a sinistra

if(number > p->value)q=next(number,p->right);
if(number < p->value)q=next(number,p->left);

Nella funzione parent_next viene controllato che il nodo esista, se il figlio sinistro è uguale al valore cercato ho trovato il valore successivo altrimenti continua a cercare

struct node *parent_next(long int number, struct node *p)
{
if(p!=NULL)
{
if(p->left!=NULL){if(p->left->value==number)return p;}
return parent_next(p->value,p->root);
}
return NULL;
}

Precedente

Se il nodo corrente è nullo ha trovato niente

if (p==NULL)return NULL;

Il nodo corrente è uguale al valore cercato, il valore sinistro esiste? Si, ritorna con il valore minimo del valore sinistro, altrimenti cerca nel nodo precedente

if (number == p->value)
{
if(p->left!=NULL)
{
return max(p->left);
}
else
{
return parent_prev(number,p->root);
}
}

Se il valore è maggiore del nodo corrente continua a cercare nella lista a destra altrimenti a sinistra

if(number > p->value)q=prev(number,p->right);
if(number < p->value)q=prev(number,p->left);

Nella funzione parent_prev viene controllato che il nodo esista, se il figlio destro è uguale al valore cercato ho trovato il valore precedente altrimenti continua a cercare

struct node *parent_prev(long int number, struct node *p)
{
if(p!=NULL)
{
if(p->right!=NULL){if(p->right->value==number)return p;}
return parent_prev(p->value,p->root);
}
return NULL;
}

Massimo

La lista a destra conclude con il valore massimo

struct node *max(struct node *p)
{
struct node *q;
if(p->right==NULL)return p;
q=max(p->right);
return q;
}

Minimo

La lista a sinistra conclude con il valore minimo

struct node *min(struct node *p)
{
struct node *q;
if(p->left==NULL)return p;
q=min(p->left);
return q;
}

Visualizzazione dei dati

La visualizzazione dei dati può essere ricreata in una lista lineare ed in seguito visualizzata, per comodità si effettua la visualizzazione sul posto.

pre-order

Visualizzazione del dato, navigazione sul sinistro, navigazione sul destro

short int preorder(struct node *p)
{
if (p==NULL)return -1;
printf(“%li -“,p->value);
preorder(p->left);
preorder(p->right);
return 2;
}

in-order

Navigazione sul sinistro, visualizzazione del dato, navigazione sul destro

short int inorder(struct node *p)
{
if (p==NULL)return -1;

inorder(p->left);
printf(“%li -“,p->value);
inorder(p->right);
return 2;
}

post-order

Navigazione sul sinistro, navigazione sul destro, visualizzazione del dato

short int postorder(struct node *p)
{
if (p==NULL)return -1;

postorder(p->left);
postorder(p->right);
printf(“%li -“,p->value);
return 2;
}

Il codice completo

#include <string.h>
#include <stdlib.h>
#include <stdio.h>// elimina quando finito
struct node
{
long int value;
struct node *left;
struct node *right;
struct node *root;
};

short int insert(long int number,struct node **q)
{

short int save;
struct node *p,*list;
list=*q;

p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
return(3);
}
p->value=number;

if(list==NULL)
{

p->root=NULL;
list=p;
*q=list;
return 2;
}
save=0;
do{
if(number > list->value)
{
if(list->right!=NULL)list=list->right;
else
{

list->right=p;
save=1;
p->root=list;
}
}
else
{
if(list->left!=NULL)list=list->left;
else
{

list->left=p;
save=1;
p->root=list;
}
}
}while(save==0);

for(;list->root!=NULL;list=list->root);
*q=list;

return 2;
}

short int preorder(struct node *p)
{
if (p==NULL)return -1;
printf(“%li -“,p->value);
preorder(p->left);
preorder(p->right);
return 2;
}

short int inorder(struct node *p)
{
if (p==NULL)return -1;

inorder(p->left);
printf(“%li -“,p->value);
inorder(p->right);
return 2;
}

short int postorder(struct node *p)
{
if (p==NULL)return -1;

postorder(p->left);
postorder(p->right);
printf(“%li -“,p->value);
return 2;
}

struct node *search(long int number,struct node *p)
{
struct node *q;

if(p==NULL)return NULL;

if(number == p->value)return p;

if(number > p->value)q=search(number,p->right);
if(number < p->value)q=search(number,p->left);

return q;
}

struct node *min(struct node *p)
{
struct node *q;
if(p->left==NULL)return p;
q=min(p->left);
return q;
}

struct node *max(struct node *p)
{
struct node *q;
if(p->right==NULL)return p;
q=max(p->right);
return q;
}

struct node *parent_next(long int number, struct node *p)
{
if(p!=NULL)
{
if(p->left!=NULL){if(p->left->value==number)return p;}
return parent_next(p->value,p->root);
}
return NULL;
}

struct node *next(long int number, struct node *p)
{
struct node *q;
if (p==NULL)return NULL;
if (number == p->value)
{
if(p->right!=NULL)
{
return min(p->right);
}
else
{
return parent_next(number,p->root);
}
}
if(number > p->value)q=next(number,p->right);
if(number < p->value)q=next(number,p->left);

return q;
}

struct node *parent_prev(long int number, struct node *p)
{
if(p!=NULL)
{
if(p->right!=NULL){if(p->right->value==number)return p;}
return parent_prev(p->value,p->root);
}
return NULL;
}
struct node *prev(long int number, struct node *p)
{
struct node *q;
if (p==NULL)return NULL;
if (number == p->value)
{
if(p->left!=NULL)
{
return max(p->left);
}
else
{
return parent_prev(number,p->root);
}
}
if(number > p->value)q=prev(number,p->right);
if(number < p->value)q=prev(number,p->left);

return q;
}
int remove(struct node **tree)
{

struct node *q,*t,*p;
p=*tree;
if (p==NULL)return 0;
if(p->left==NULL && p->right==NULL)
{
q=p->root;

if(q!=NULL)
{
if(q->left==p)q->left=NULL;
if(q->right==p)q->right=NULL;
}
else
{
*tree=NULL;
}

}
if(p->left==NULL && p->right!=NULL)
{
q=p->root;
if(q!=NULL)
{
if(q->left==p)q->left=p->right;
if(q->right==p)q->right=p->right;
p->right->root=q;
}
else
{
q=p;
p=p->right;
p->root=NULL;
*tree=p;
}
}
if(p->left!=NULL && p->right==NULL)
{
q=p->root;
if(q!=NULL)
{
if(q->left==p){q->left=p->left;}
if(q->right==p)q->right=p->left;
p->left->root=q;
}
else
{
q=p;
p=p->left;
p->root=NULL;
*tree=p;
}
}
if(p->left!=NULL && p->right!=NULL)
{
t=p->root;
q=next(p->value,p);
remove(&q);
if(t==NULL)
{

if(p->left==NULL)q->left=NULL;
else
{
q->left=p->left;
p->left->root=q;
}

if(p->right==NULL)q->right=NULL;
else
{
q->right=p->right;
p->right->root=q;
}

q->root=NULL;
*tree=q;
}
else
{
if(t->left==p)t->left=q;
if(t->right==p)t->right=q;
q->root=t;

if(p->left==NULL)q->left=NULL;
else
{
q->left=p->left;
p->left->root=q;
}

if(p->right==NULL)q->right=NULL;
else
{
q->right=p->right;
p->right->root=q;
}

}
}
return 1;
}

short int del(long int number,struct node **p)
{
struct node *q;

q=search(number,*p);
if(q==NULL)return 0;
if(q==*p)
{
remove (&q);
*p=q;
}
else
{
remove (&q);
free(q);
}
return 2;
}

Lezione in C/C++ – sezione 2: La tabelle hash (2)

Le funzioni hash con liste

Nelle funzioni hash in un array è possibile gestire un’indice con le liste, ovvero quando una parola è già presente in tale posizione si aggiunge una lista adiacente.

La struttura è la seguente:

struct list_word
{
char *word;
struct list_word *next;
};

word è la parola, e next è il puntatore lista

struct list_word vocabulary[26];

Così definisco l’array vocabulary di 26 unità che sono le lettere dell’alfabeto. In questo modo si ha un array e una lista adiacente rispetto all’array.

Ecco le funzioni, una che inizializza il vocabolario

wend[0]=’~’;
wend[1]=’\0′;
for(i=1;i<27;i++)
{
chara[0]=(char )96+i;
chara[1]=’\0′;
vocabulary[i].word=strmem(chara);
p=(struct list_word *)malloc(sizeof(struct list_word));
p->word=strmem(wend);
vocabulary[i].next=p;
}

wend è una stringa dove viene inserita in una lista e questa diviene l’ultima di una serie

La funzione strmem crea una stringa delle dimensioni che l’utente inserisce

char *strmem(char *str)
{
int length; char *p;
length=strlen(str);
p=(char *)malloc((length+1)*sizeof(char));
if(p==NULL)return NULL;
strcpy(p,str);
return (p);
}

Deve esserci la possibilità di una funzione di reset dell’intera struttura

for(i=1;i<27;i++)
{
current=vocabulary[i].next;
start=&vocabulary[i];

while (strcmp(start->next->word,”~\0″))
{
delelte=curren
}
}t;
vocabulary[i].next=current->next;

current=current->next;
free(delelte);
}
}

Poi ci sono le tre funzioni, inserimento, ricerca e cancellazione.
In queste tre funzione si controlla che la stringa sia di soli caratteri e in seguito si dispongono in minuscolo

len=strlen(value);
for(i=0;i<len;i++)
{
if(!isalpha(value[i]))
{
printf(“Only charatter!\n”);
return 0;
}
}

for(i=0;i<len;i++)
{
if (value[i]>=’A’ && value[i]<=’Z’)
{
value[i]=value[i]+32;
}
}

Ecco come si procede nell’inserimento
Innanzitutto si prende l’indirizzo corrente del vocabolario corrispondete al carattere della prima parola

for(i=1;i<27;i++)
if(value[0]==vocabulary[i].word[0])
{
current=&vocabulary[i];
}

A questo punto controllo la lista finché non si raggiunge l’ultima posizione di coda, confronto la parola con il vocabolario se è minore con questa. Se è minore alloco una lista e inserisco il valore, dunque questa lista deve essere prima dell’elemento del vocabolario.

while(strcmp(current->word,”~\0″))
{
if(strcmp(value,current->next->word)<0)
{
p=(struct list_word *)malloc(sizeof(struct list_word));
if(p==NULL)
{
printf(“Alloc Error New Value”);
exit(1);
}
p->word=strmem(value);
temp=current->next;
current->next=p;
p->next=temp;
return 1;
}
current=current->next;
}

Per la ricerca è molto semplice, basta un semplice confronto

while(strcmp(current->word,”~\0″))
{
if(strcmp(value,current->next->word)==0)return 1;
current=current->next;
}
return 0;

E per la cancellazione, oltre la ricerca, si elimina la parola

while(strcmp(current->word,”~\0″))
{
if(strcmp(value,current->next->word)==0)
{
delelte=current->next;
current->next=current->next->next;
free(delelte);
return 1;
}
current=current->next;
}

Lezione in C/C++ – sezione 2: La tabelle hash (1)

Le funzioni hash

Mettiamo che c’è bisogno di tenere una lista di parole in un blocco note, e questo ha una certa capacità di tenere tot parole. Dunque è possibile scrivere in base ad un’ordine alfabetico, ma se il blocco note è limitato allora devo trovare una corrispondenza tra il numero della pagina e la parola da inserire.

Dato che si usa un’array, l’indice corrispondente alla parola deve essere libero. Ma se risulta a essere occupato si può posizionare nel successivo, oppure all quadrato della posizione attuale.

Quindi  ci sono delle funzioni per gestire la posizione e sono i seguenti:

long int Linear_Probing(double k,short i)
{
short int n;
n=fmod((fmod(k,100)+i),100);
return n;
}

 

long int Quadratic_Probing(double k,short i)
{
short int n;
n=fmod((fmod(k,100)+i+(3*pow(i,2))),100);
return n;
}

 

long int Double_Hashing(double k,short i)
{
short int n;
n=fmod((fmod(k,100)+i*(fmod(k,99)+1)),100);
return n;
}

Nella funzione hash si trova anche l’inserimento, la ricerca e la cancellazione di un elemento.

L’array può essere il seguente:

struct list_word
{
char *word;
};

struct list_word vocabulary[100];

Per cancellare l’intero array:

for(i=0;i<100;i++)
{
p=vocabulary[i].word;
if(!(p))free(p);
vocabulary[i].word=NULL;
}

Per inserire o cercare un valore viene definito una stringa e un puntatore

char word[255],*wp;

Viene chiesto all’utente di inserire un valore

scanf(“%s”,word);

E poi la stringa trasformata in puntatore con la funzione strmem

wp=strmem(word);

La funzione strmem

char *strmem(char *str)
{
int length; char *p;
length=strlen(str);
p=(char *)malloc((length+1)*sizeof(char));
if(p==NULL)return NULL;
strcpy(p,str);
return (p);
}

Si vede che viene allocata una stringa di lunghezza uguale a ciò che inserisce l’utente, e l’indirizzo di questa stringa viene restituito al programma.
Questo viene utile quando le stringhe sono allocate dall’utente e non dal programmatore.

Poi nelle funzioni di ricerca, inserimento e cancellazione si passa la stringa appena inserita dall’utente. Quindi si effettua un controllo, che che sia solo caratteri, che tutti i caratteri diventino minuscoli

len=strlen(value);
if(len==0)
{
printf(“One element please\n”);
return 0;
}

len=strlen(value);
for(i=0;i<len;i++)
{
if(!isalpha(value[i]))
{
printf(“Only charatter!\n”);
return 0;
}
}

for(i=0;i<len;i++)
{
if (value[i]>=’A’ && value[i]<=’Z’)
{
value[i]=value[i]+32;
}
}

A questo punto bisogna associare la parola ad un numero, quindi procedo a definire che la lettera “a” è uguale a 1 mentre “z” è uguale a 26. Quindi il sistema è una composizione di 26 lettere e la composizione aumenta con la lunghezza della parola

code=0;
for(i=len-1;i>=0;i–)
{
n=(value[i]-96);
num=((double)n*(double)pow(26,len-i-1));
code=code+num;
}

ovvero

n=<alfabeto>-96[codice ascii];
codice=codice+n*(26^(len-i-1))

Per l’inserimento:

index=0;
position=0;
do{
position=Double_Hashing(code,index);// oppure
//position=Linear_Probing(code,index);//oppure
//position=Quadratic_Probing(code,index);
if(vocabulary[position].word==NULL)
{
vocabulary[position].word=value;
break;
}
index++;
}while(vocabulary[position].word!=NULL);

Per cancellare

int i;
char *string;
for(i=0;i<99;i++)
{

if((vocabulary[i].word)!=NULL)
{
if(strcmp(value,vocabulary[i].word)==0)
{
string=vocabulary[i].word;
free(string);
vocabulary[i].word=NULL;
return 1;
}
}
}

Per la ricerca

for(i=0;i<99;i++)
{

if((vocabulary[i].word)!=NULL)
{
if(strcmp(value,vocabulary[i].word)==0)
{
return 1;
}
}
}

Lezione in C/C++ – sezione 2: Le liste e l’ordinamento (2)

Le liste e l’ordinamento

Si vede ora come vengono ordinate le liste.
Nel caso della selection sort viene ordinata sul posto, mentre peri altri metodi viene convertita in array.

Selection Sort

La funzione

void selection_sort(struct number **list)

Le variabili

struct number *index_list,*minimum_list,*first_list,*order_list,*first_order_list;

order_list=NULL;
first_list=NULL;
first_order_list=NULL;
minimum_list=NULL;

Index list è la variabile che naviga nella lista

index_list=*list;

Se è vuota non procedere

if(index_list->next==index_list)return;

Quindi la posiziono sull’elemento successivo e salvo questo elemento come primo indice. Poi navigo nello stesso finché non torno all’inizio.

first_list=index_list->next;
index_list=index_list->next;

do
{

}while(index_list->next!=index_list);

Per prima cosa memorizzo il primo elemento come valore minimo per l’ordinamento

minimum_list=index_list;

Quindi effettuo un’altro ciclo per valutare se esista un’altro elemento più piccolo dell’attuale memorizzato

do{

index_list=index_list->next;
}while(index_list->next!=first_list->next);

Quindi in questo ciclo effettuo il controllo e salvo l’elemento come minimo

if(minimum_list->next->value >= index_list->next->value)
{
minimum_list=index_list;
}

Trovato il valore minimo nell’elemento successivo salvo questo nell’indice e come primo elemento

index_list=minimum_list;
first_list=minimum_list;

Quindi correggo l’elemento successivo minimo come corrente

minimum_list=minimum_list->next;

Questo elemento lo tolgo dalla lista

index_list->next=index_list->next->next;

E lo concateno su di esso

minimum_list->next=minimum_list;

A questo punto l’elemento minimo lo salvo su una lista ordinata, quindi se questa lista è vuota viene memorizzato

if(order_list==NULL)
{
order_list=minimum_list;
order_list->next=order_list;
first_order_list=order_list;
}

Altrimenti mi sposto sull’ultimo elemento della lista ordinata, memorizzo il nuovo minimo e lo concateno con il primo

for(order_list=first_order_list;order_list->next!=first_order_list;order_list=order_list->next);
order_list->next=minimum_list;
order_list->next->next=first_order_list;

Fatto questo posiziono la lista all’inizio della lista ordinata

*list=first_order_list;

Il codice

void selection_sort(struct number **list)
{
struct number *index_list,*minimum_list,*first_list,*order_list,*first_order_list;

order_list=NULL;
first_list=NULL;
first_order_list=NULL;
minimum_list=NULL;

if(*list==NULL)return;

index_list=*list;

if(index_list->next==index_list)return;

first_list=index_list->next;
index_list=index_list->next;

do
{
minimum_list=index_list;

do{

if(minimum_list->next->value >= index_list->next->value)
{
minimum_list=index_list;
}
index_list=index_list->next;
}while(index_list->next!=first_list->next);

index_list=minimum_list;
first_list=minimum_list;
minimum_list=minimum_list->next;
index_list->next=index_list->next->next;
minimum_list->next=minimum_list;
if(order_list==NULL)
{
order_list=minimum_list;
order_list->next=order_list;
first_order_list=order_list;
}
else
{
for(order_list=first_order_list;order_list->next!=first_order_list;order_list=order_list->next);
order_list->next=minimum_list;
order_list->next->next=first_order_list;
}
}while(index_list->next!=index_list);

if(index_list->next==index_list)
{
for(;order_list->next!=first_order_list;order_list=order_list->next);
order_list->next=index_list;
order_list->next->next=first_order_list;
}

*list=first_order_list;

}

Counting sort

La funzione

int counting_sort(struct number **list)

Le variabili

long int max, min, length,i,n;
struct number *counting,*p,*start,*order,*temp;

Se la lista è vuota torna al programma

if(*list==NULL)return 0;

Per prima cosa leggo nella lista qual’è il massimo e il minimo, e torno con il risultato

max=max_sort(list);
min=min_sort(list);

La lunghezza è la differenza tra il massimo e il minimo più uno

length=max-min+1;

A questo punto alloco un array del conteggio degli elementi con questa lunghezza appena trovata

counting=(struct number *) malloc( length * sizeof(struct number));

Se l’allocazione fallisce torna con valore di errore

if(counting==NULL){
printf(“\nAlloc Counting Error\n”);
return 0;
}

Azzero la lista

for(i=1;i<length;i++)counting[i].value=0;

A questo punto devo convertire la lista in array, quindi ho bisogno di leggerne la lunghezza

n=0;
for(p=*list;p->next!=*list;p=p->next)n++;
n=n+1;

E creare un nuovo array di questa lunghezza, verificando che si riesce ad allocare.

temp=(struct number *) malloc( n * sizeof(struct number));
if(counting==NULL){
printf(“\nAlloc Counting Error\n”);
return 0;
}

Dunque la variabile temp è l’array ordinato, rimane da fare il conteggio dei valori.
Mi posiziono all’inizio della lista

start=*list;
p=start;

Navigando nella lista, il valore corrente lo sottraggo al minimo più uno

do{
counting[(p->value)-min+1].value=counting[(p->value)-min+1].value+1;
p=p->next;
}while(p->next!=start->next);

In questo modo ho una lista del conteggio dei numeri, a questo punto bisogna sommare gli elementi per incremento

for(i=1;i<=length;i++)counting[i].value=counting[i].value+counting[i-1].value;

Quindi, navigo nell’elemento

do{

p=p->next;
}while(p->next!=start->next);

In questo ciclo, il valore corrente

(p->value)-min+1

Nell’array del conteggio

counting[(p->value)-min+1].value-1

Posizionalo nell’array temporaneo

temp[counting[(p->value)-min+1].value-1]

E nel puntatore memorizza il suo indirizzo

temp[counting[(p->value)-min+1].value-1].next=p;

Ora il puntatore order viene inizializzato, messo alla posizione iniziale del puntatore del primo array temporaneo

order=NULL;
order=temp[0].next;

E viene impostato come primo elemento

start=order;

Non rimane altro che concatenare l’array nella lista.
Ad ogni puntatore dell’array viene inserito nella lista finché non raggiunge la lunghezza massima

i=1;
while(i<n){
order->next=temp[i].next;
order=order->next;
i++;
};

Non rimane altro che concatenare l’ultimo elemento con il primo e posizionare la lista con questo elemento ordinato

order->next=start;
order=start;
*list=order;

Il codice

short int counting_sort(struct number **list)
{
long int max, min, length,i,n;
struct number *counting,*p,*start,*order,*temp;

if(*list==NULL)return 0;

max=max_sort(list);
min=min_sort(list);
length=max-min+1;

counting=(struct number *) malloc( length * sizeof(struct number));
if(counting==NULL){
printf(“\nAlloc Counting Error\n”);
return 0;
}

for(i=1;i<length;i++)counting[i].value=0;

n=0;
for(p=*list;p->next!=*list;p=p->next)n++;
n=n+1;

temp=(struct number *) malloc( n * sizeof(struct number));
if(counting==NULL){
printf(“\nAlloc Counting Error\n”);
return 0;
}

start=*list;
p=start;
do{
counting[(p->value)-min+1].value=counting[(p->value)-min+1].value+1;
p=p->next;
}while(p->next!=start->next);

for(i=1;i<=length;i++)counting[i].value=counting[i].value+counting[i-1].value;

do{
temp[counting[(p->value)-min+1].value-1].next=p;
counting[(p->value)-min+1].value–;
p=p->next;
}while(p->next!=start->next);

order=NULL;
order=temp[0].next;
start=order;

i=1;
while(i<n){
order->next=temp[i].next;
order=order->next;
i++;
};

order->next=start;
order=start;
*list=order;

return 1;
}

Mergesort

La funzione

void MergeList(struct number **list)

Variabili

long int element, index;
struct number *p,*q,*array,*start;

Se la lista è vuota ritorna errore

p=*list;
if(*list==NULL)return 0;

Conta gli elementi della lista

element=count(&p);

Alloca il nuovo array con la quantità di elementi trovati

element=count(&p);
array=(struct number *) malloc( element * sizeof(struct number));

Se non riesce ad allocarli torna errore

if(array==NULL)return 0;

L’elemento iniziale è nel primo elemento

start=*list;

index=0;

Navigare nella lista, impostare il valore e nella variabile puntatore l’indirizzo puntatore dell’elemento

index=0;
do{
array[index].value=p->value;
array[index].next=p;
p=p->next;
index++;
}while(p->next!=start->next);

A questo punto procedere alla funzione di ordinamento

mergesort(array,0,element-1);

Impostare l’inizio dell’array ordinato

start=array[0].next;
q=array[0].next;

L’indirizzo della lista corrisponde al puntatore dell’array

index=1;
while(index<element)
{
q->next=array[index].next;
q=q->next;
index++;
}

Quindi concateno il fine della lista con l’inizio

q->next=start;
q=q->next;

E la lista viene indirizzata a questa lista ordinata

*list=q;

Il codice

short int MergeList(struct number **list)
{
long int element, index;
struct number *p,*q,*array,*start;

p=*list;

if(p==NULL)return 0;

element=count(&p);
array=(struct number *) malloc( element * sizeof(struct number));
if(array==NULL)return 0;
start=*list;

index=0;
do{
array[index].value=p->value;
array[index].next=p;
p=p->next;
index++;
}while(p->next!=start->next);
mergesort(array,0,element-1);

start=NULL;
q=NULL;
start=array[0].next;
q=array[0].next;
index=1;
while(index<element)
{
q->next=array[index].next;
q=q->next;
index++;
}
q->next=start;
q=q->next;

*list=q;

return 1;
}

Nota: nel codice del merge viene apportata questa modifica:

while (i<=q && j<=r)
{
if (a[i].value<=a[j].value)
{
b[k].value=a[i].value;
b[k].next=a[i].next;
i++;
}
else
{
b[k].value=a[j].value;
b[k].next=a[j].next;
j++;
}
k++;
}
while (i<=q)
{
b[k].value = a[i].value;
b[k].next=a[i].next;
i++;
k++;
}

while (j<=r)
{
b[k].value = a[j].value;
b[k].next=a[j].next;
j++;
k++;
}

for (k=p; k<=r; k++)
{
a[k].value = b[k-p].value;
a[k].next = b[k-p].next;
}

QuickSort

La procedura del quicksort è la medesima del mergesort.

La funzione

short int QuickList(struct number **list)

Le variabili

long int element, index;
struct number *p,*q,*array,*start;

Se la lista è vuota non procedere

p=*list;
if(p==NULL) return 0;

Conta gli elementi e alloca un’array di tale dimensione, se fallisce torna errore

array=(struct number *) malloc( element * sizeof(struct number));
if(array==NULL)return 0;

Posizione sull’inizio della lista

start=*list;

Da lista a array

index=0;
do{
array[index].value=p->value;
array[index].next=p;
p=p->next;
index++;
}while(p->next!=start->next);

Si effettua la funzione di ordinamento

quicksort(array,0,element-1);

Dall’array ordinato si passa i parametri alla lista

start=array[0].next;
q=array[0].next;
index=1;
while(index<element)
{
q->next=array[index].next;
q=q->next;
index++;
}

Si concatena l’ultimo con il primo

q->next=start;
q=q->next;

E la lista viene indirizzata a questa lista ordinata

*list=q;

Il codice

short int QuickList(struct number **list)
{
long int element, index;
struct number *p,*q,*array,*start;

p=*list;
if(p==NULL) return 0;

element=count(&p);
array=(struct number *) malloc( element * sizeof(struct number));
if(array==NULL)return 0;
start=*list;
index=0;
do{
array[index].value=p->value;
array[index].next=p;
p=p->next;
index++;
}while(p->next!=start->next);

quicksort(array,0,element-1);

start=NULL;
q=NULL;
start=array[0].next;
q=array[0].next;
index=1;
while(index<element)
{
q->next=array[index].next;
q=q->next;
index++;
}
q->next=start;
q=q->next;

*list=q;
return 1;

}

Nota: La funzione quicksort, cioè il partition, necessita di questa modifica

if(i<j)
{
temp=a[i].value;
q=a[i].next;

a[i].value=a[j].value;
a[i].next=a[j].next;

a[j].value=temp;
a[j].next=q;
}

Test

C’è chi pensa che il quicksort può essere sviluppato solo con le liste? Il mergesort e il countingsort?

Lezione in C/C++ – sezione 2: Le liste e l’ordinamento (1)

Le liste e l’ordinamento

La lista può essere costruita in tre modi:
– Semplice
– Con sentinelle
– Concatenate

La lista semplice l’ultimo elemento è NULL dove si può inserire il nuovo elemento o in coda o in testa.

La lista con sentinelle ha due elementi definiti uno in testa e l’altro in coda che possono essere definiti come massimo e minimo e quindi nell’inserimento viene automaticamente ordinato.

La lista concatenata l’ultimo elemento è collegato al primo elemento e dunque diventa circolare.

Nell’esempio che viene proposto si usa una lista circolare con l’inserimento di un nuovo elemento in coda.

Inserimento elemento

La funzione

short int insert(struct number **list,long int value)

Le variabili

struct number *p,*current;

Allocazione di un nuovo elemento

p=(struct number *)malloc(sizeof(struct number));

In caso non viene allocato ritorna errore

if (p==NULL)return 0;

Imposta il valore nell’elemento

p->value=value;

Quindi se non è stato ancora inserito nessun valore nella lista

if (*list==NULL)

Concatena il successivo sullo stesso

p->next=p;

Quindi la lista si imposta su questo elemento

*list=p;

Altrimenti se è già presente dei valori nella lista, ci si posiziona in fondo alla lista

for(current=*list;current->next!=*list;current=current->next);

Si inserisce in fondo alla coda il nuovo elemento

current->next=p;

E si concatena con il primo elemento

p->next=*list;

Il codice

short int insert(struct number **list,long int value)
{
struct number *p,*current;
p=(struct number *)malloc(sizeof(struct number));
if (p==NULL)return 0;

p->value=value;

if (*list==NULL)
{
p->next=p;
*list=p;
}
else
{
for(current=*list;current->next!=*list;current=current->next);
current->next=p;
p->next=*list;
}

return 1;
}

Cancellare Elemento

La funzione

short int del(struct number **list,long int value)

Le variabili

struct number *p,*q;

Se la lista è vuota non procedere

p=*list;
if(p==NULL)return 0;

Dunque devo verificare se nel primo elemento è presente il valore da cancellare

if(p->value==value)

La lista si sposta sul sucessivo

*list=p->next;

Quindi mi porto sull’ultimo elemento

for(q=*list;q->next!=p;q=q->next);

E concateno il successivo  del primo elemento

q->next=*list;

A questo punto posso liberare dalla memoria il primo elemento

free(p);

E in questa condizione finisco la procedura

return 1;

A questo punto cerco nella lista l’elemento da cancellare, quindi mi sposto nella lista finché non raggiungo il primo elemento

do{

p=p->next;
}
while(p->next!=*list);

Se viene trovato l’elemento

if(p->next->value==value)

Lo memorizzo in una variabile

q=p->next;

Quindi elimino l’elemento dalla lista

p->next=p->next->next;

E libero dalla memoria questo elemento

free(q);

E torno al programma con successo

return 1;

Nel caso non viene trovato torno al programma con errore

return 0;

Il codice

short int del(struct number **list,long int value)
{
struct number *p,*q;

p=*list;
if(p==NULL)return 0;

if(p->value==value)
{
*list=p->next;

for(q=*list;q->next!=p;q=q->next);
q->next=*list;

free(p);
return 1;
}
do{

if(p->next->value==value)
{
q=p->next;

p->next=p->next->next;

free(q);

return 1;
}

p=p->next;
}
while(p->next!=*list);

return 0;
}

Cancellare intera lista

La funzione e le variabili

short int delAll(struct number **list)
{
struct number *p,*q;

Se la lista è vuota non effettuare operazioni

if(*list==NULL)return 0;

Ci si sposta nella lista affinché tutti gli elementi vengono liberati dalla memoria

p=*list;
do{
q=p;
p=p->next;
free(q);
}while(p!=*list);

Quindi la lista fa riferimento ad un valore vuoto

*list=NULL;

Il codice completo

short int delAll(struct number **list)
{
struct number *p,*q;
if(*list==NULL)return 0;
p=*list;
do{
q=p;
p=p->next;
free(q);
}while(p!=*list);

*list=NULL;
return 1;
}

Trovare un elemento

Funzione e variabili

short int search(struct number **list,long int value)
{
struct number *p;

Navigazione nella lista

do{

p=p->next;
}while(p!=*list);

Se viene trovato l’elemento torna con valore 1

if(p->value==value)return 1;

Se nella lista non viene trovato torna con valore zero

return 0;

Il codice

short int search(struct number **list,long int value)
{
struct number *p;
p=*list;
if(*list==NULL)printf(“\n”);return 0;

do{
if(p->value==value)return 1;
p=p->next;

}while(p!=*list);

return 0;
}

Mostrare  la lista

Funzione e variabile

short int show(struct number **list)
{
struct number *p;

Se la lista è vuota va a capo e torna con valore zero

if(p==NULL){printf(“\n”);return 0;}

Si sposta nella lista affinché tutti gli elementi vengono mostrati

do{
printf(“%li”,p->value);
p=p->next;
if(p!=*list)printf(” – “);
}while(p!=*list);

Quindi torna al programma

printf(“\n”);
return 1;

Il codice

short int show(struct number **list)
{
struct number *p;
p=*list;

if(p==NULL){printf(“\n”);return 0;}

do{
printf(“%li”,p->value);
p=p->next;
if(p!=*list)printf(” – “);
}while(p!=*list);

printf(“\n”);
return 1;
}

 

Lezione in C/C++ – sezione 2: Le liste

Le liste

La struttura di una lista è la seguente:

struct number
{
long int value;
struct number *next;
};

Il puntatore *next è definito con la stessa struttura, dove c’è la possibilità di collegare un’altra struttura. Guardando l’aspetto grafico risulta molto esemplificativo il suo funzionamento:

Quindi è necessario definire una variabile di tale struttura

struct number *head=NULL;

Ci sono cinque funzioni principali di una lista:
1 – L’inserimento di un elemento
2 – Cancellare un elemento
3 – Trovare un elemento
4 – Visualizzare la lista

Inserimento di un elemento

La funzione

int insert(struct number **list, int value)

E’ necessario il doppio puntatore perché la lista ha un’indirizzo base su tutti i elementi.
Si definisce una variabile

struct number *p;

Viene allocato un nuovo elemento della struttura nella memoria

p=(struct number *)malloc(sizeof(struct number));

Se l’allocazione fallisce ritorna con un valore di errore

if (p==NULL)return 0;

A questo punto viene impostato in questo elemento un valore

p->value=value;

Dopodiché inserisco questo elemento in testa alla lista

p->next=*list;

E posiziono la lista in questo nuovo elemento

*list = p;

Il codice

int insert(struct number **list, int value)
{
struct number *p;
p=(struct number *)malloc(sizeof(struct number));
if (p==NULL)return 0;
p->value=value;
p->next=*list;
*list=p;
return 1;
}

Cancellare un elemento

La funzione

int del(struct number **list,int value)

Le variabili

struct number *p,*q;

Se la lista è vuota non procedere

p=*list;
if(p==NULL)return 0;

Verifico il primo elemento, se trovo il valore l’elemento viene eliminato

if(p->value==value)
{
*list=p->next;
free(p);
return 1;
}

Quindi cerco nella lista gli altri elementi se trovo l’elemento da cancellare

while(p->next!=NULL)
{

p=p->next;
}

Se non viene trovato torna con valore 0

return 0;

Nel ciclo while controllo se nell’elemento successivo è presente la variabile

if(p->next->value==value)
{

E’ presente quindi imposto una variabile con questo elemento perché la devo eliminare dalla memoria

q=p->next;

Devo chiedermi se ho raggiunto la fine della lista, nell’elemento successivo dove ho letto il valore è diverso da NULL  e quindi ci sono altri elementi?

Se ‘si’ collega l’elemento corrente all’elemento successivo di quello trovato, altrimenti imposta all’elemento corrente successivo l’elemento di coda NULL

if(p->next->next!=NULL)p->next=p->next->next;
else p->next=NULL;

Libera dalla memoria l’elemento da eliminare

free(q);

Ritorna con valore 1 per il successo dell’operazione

return 1;

Il codice

int del(struct number **list,int value)
{
struct number *p,*q;
p=*list;
if(p==NULL)return 0;
if(p->value==value)
{
*list=p->next;
free(p);
return 1;
}

while(p->next!=NULL)
{
if(p->next->value==value)
{
q=p->next;

if(p->next->next!=NULL)p->next=p->next->next;
else p->next=NULL;

free(q);

return 1;
}
p=p->next;
}

return 0;
}

Trovare un elemento

Funzione

int search(struct number *list,int value)

Variabili

struct number *p;

Mi sposto nella lista finché trovo l’elemento

while(p!=NULL)
{

p=p->next
}

In caso non trovo dei valori ritorno con valore 0

return 0;

Nel ciclo while quando trovo l’elemento torno con valore 1

if(p->value==value)return 1;

Il codice

int search(struct number *list,int value)
{
struct number *p;
p=list;

while(p!=NULL)
{
if(p->value==value)return 1;
p=p->next;
}
return 0;
}

Visualizzare la lista

La funzione

void show(struct number *list)

La variabile

struct number *p;

La variabile si posizione sulla lista

p=list;

Un messaggio per la visualizzazione della lista

printf(“The list is: “);

Mi sposto nella lista affinché viene mostrata tutta

while(p!=NULL)
{

p=p->next;
}
printf(“\n”)

Nel ciclo while vengono mostrati gli elementi

printf(“%ld”,p->value);
if(p!=NULL)printf(” – “);

Il codice

void show(struct number *list)
{
struct number *p;
p=list;
printf(“The list is: “);
while(p!=NULL)
{
printf(“%ld”,p->value);
p=p->next;
if(p!=NULL)printf(” – “);
}
printf(“\n”);
}

 

 

Tipi di dati nel linguaggio C/C++

Type Explanation Format Specifier
char Smallest addressable unit of the machine that can contain basic character set. It is an integer type. Actual type can be either signed or unsigned depending on the implementation. It contains CHAR_BIT bits.  %c
signed char Of the same size as char, but guaranteed to be signed. Capable of containing at least the [−127, +127] range;  %c (or %hhi for numerical output)
unsigned char Of the same size as char, but guaranteed to be unsigned. It is represented in binary notation without padding bits; thus, its range is exactly [0, 2CHAR_BIT − 1].  %c (or %hhu for numerical output)
short
short int
signed short
signed short int
Short signed integer type. Capable of containing at least the [−32767, +32767] range; thus, it is at least 16 bits in size. The negative value is −32767 (not −32768) due to the one’s-complement and sign-magnitude representations allowed by the standard, though the two’s-complement representation is much more common.[6]  %hi
unsigned short
unsigned short int
Similar to short, but unsigned.  %hu
int
signed
signed int
Basic signed integer type. Capable of containing at least the [−32767, +32767] range; thus, it is at least 16 bits in size.  %i or %d
unsigned
unsigned int
Similar to int, but unsigned.  %u
long
long int
signed long
signed long int
Long signed integer type. Capable of containing at least the [−2147483647, +2147483647] range; thus, it is at least 32 bits in size.  %li
unsigned long
unsigned long int
Similar to long, but unsigned.  %lu
long long
long long int
signed long long
signed long long int
Long long signed integer type. Capable of containing at least the [−9223372036854775807, +9223372036854775807] range; thus, it is at least 64 bits in size. Specified since the C99 version of the standard.  %lli
unsigned long long
unsigned long long int
Similar to long long, but unsigned. Specified since the C99 version of the standard.  %llu
float Real floating-point type, usually referred to as a single-precision floating-point type. Actual properties unspecified (except minimum limits), however on most systems this is the IEEE 754 single-precision binary floating-point format. This format is required by the optional Annex F “IEC 60559 floating-point arithmetic”.  %f (promoted automatically todouble forprintf())
double Real floating-point type, usually referred to as a double-precision floating-point type. Actual properties unspecified (except minimum limits), however on most systems this is the IEEE 754 double-precision binary floating-point format. This format is required by the optional Annex F “IEC 60559 floating-point arithmetic”.  %f (%F)(%lf (%lF) forscanf())
%g  %G
%e  %E (forscientific notation)[7]
long double Real floating-point type, usually mapped to an extended precision floating-point number format. Actual properties unspecified. Unlike types float and double, it can be either 80-bit floating point format, the non-IEEE “double-double” or IEEE 754 quadruple-precision floating-point format if a higher precision format is provided, otherwise it is the same as double. See the article on long double for details.  %Lf  %LF
%Lg  %LG
%Le  %LE[7]

Lezione in C/C++ – sezione 3, Visualizzare un messaggio

Visualizzare un messaggio

In questo esempio viene visualizzato un messaggio di saluto “Hello World”

#include <iostream>

int main()
{
std::cout << “Hello World!\n”;
}

Viene inclusa la libreria iostream, i segni << stanno a indicare metti su. Dove? nel canale di uscita std::cout Quindi verrà visualizzato il messaggio

Hello World!

Si può evitare di ripetere la dicitura std in questo modo:

using namespace std;

Quindi:

cout << “Hello World!\n”;

 

Lezione in C/C++ – sezione 2, Comparazione algoritmi di ordinamento

Algoritmi di ordinamento

In questo programma viene comparato ogni funzione dell’ordinamento in quanti clock viene eseguito.

Dunque, vengono inseriti dei valori casuali dal computer di n quantità

n=rand()%element;

Per utilizzare il tempo viene usata la libreria time.h . Le variabili sono Start , End , Total .

Start = clock();
// funzione
End = clock();
Total = End – Start

In questo modo nella variabile Total ho il numero di clock

Primo esempio

In questo esempio vengono inseriti valori da 0 a 50.

— Sort Element Random Comparison —

Number element in the array is 9 element

Processing…

– Counting Sort: 4 number of clock

– Merge Sort: 3 number clock

– Heap Sort: 4 number clock

– Selection Sort: 2 number clock

– Quick Sort: 3 number clock

In un array di 9 elementi la funzione più veloce è stata la Selection Sort con 2 clock, al secondo posto il Quick Sort e il Merge Sort con 3 clock,  mentre quella più lenta è il Counting Sort e Heap Sort con 4 clock

Si prova ora con più elementi:

— Sort Element Random Comparison —

Number element in the array is 93010 element

Processing…

– Counting Sort: 3991 number of clock

– Merge Sort: 20934 number clock

– Heap Sort: 37693 number clock

– Selection Sort: 15208198 number clock

– Quick Sort: 13472 number clock

Si può notare che la funzione più lenta è la Selection Sort con 15208198 clock mentre la più veloce è la Counting Sort con 3991 clock al secondo posto il Quick Sort con 13472 clock

Secondo esempio 

in questo esempio vengono inseriti valori da 0 a 500000

Number element in the array is 9 element

Processing…

– Counting Sort: 10183 number of clock

– Merge Sort: 2 number clock

– Heap Sort: 2 number clock

– Selection Sort: 0 number clock

– Quick Sort: 2 number clock

Notato la differenza? Il Counting Sort impiega 10183 clock nonostante l’array sia molto piccolo, il Selection Sort ci ha impiegato 0 clock mentre tutti gli altri 4 clock.

Si prova con più elementi:

Number element in the array is 77874 element

Processing…

– Counting Sort: 8547 number of clock

– Merge Sort: 19697 number clock

– Heap Sort: 34334 number clock

– Selection Sort: 10718221 number clock

– Quick Sort: 15605 number clock

Il Counting Sort è stato il più veloce con 8547 clock, al secondo posto il Quick Sort con 15605 clock e il più lento il Selection Sort con 10718221 clock

Conclusioni 

Si può notare che se ci sono pochi elementi da ordinare è preferibile il Selection Sort è di gran lunga più veloce confronto gli altri. Ma quando si tratta di più elementi diventa ingestibile.
Il Counting Sort è efficente ma è ingestibile quando ci sono elementi molto diversi tra loro.
Il Quick Sort è veloce quanto il Merge Sort ma non sono preferibili quando l’array è di poche dimensioni.
L’heap Sort in ogni caso mantiene una velocità all’aumentare dell’array e se l’array è ordinato e più è efficente.

Il codice

Se qualcuno vuole testare il programma in questo codice rilascio il programma principale, le funzioni di ordinamento necessitano delle revisioni non impossibili da fare.

#include <stdio.h>
#include <cstdlib>
#include <time.h>
#include <string.h>
#include “QuickSort.h”
#include “Interactive.h”
#include “CountingSort.h”
#include “function.h”
#include “MergeSort.h”
#include “HeapSort.h”
#include “SelectionSort.h”
int main(int argc, char **argv)
{
int n, min, max,element,value;
struct number *list,*copyl;
clock_t Start, End, Total;

if (argc < 3)
{
printf(“\nToo low arguments\n”);
return 0;
}
element=atoi (*(argv+1));
value=atoi(*(argv+2));

srand(time(NULL));

printf(“\n– Sort Element Random Comparison — \n”);
//n=ask_quantity();
n=rand()%element;
list=alloc(n);
insert_number(n,list,value);

if (argc==4) if(strcmp(*(argv+3),”y”)==0)print(n,list);

printf(“\nNumber element in the array is %d element\n”,n);
printf(“\n Processing…\n”);

copyl=alloc(n);
CopyStruct(list,copyl,n);

Start = clock();
min=Min(copyl,n);
max=Max(copyl,n);
LessMin(copyl,n,min);
CountingSort(copyl,n-1,max+1);
MoreMin(copyl,n,min);
End = clock();

Total = End – Start ;
printf(“\n- Counting Sort: %ld number of clock \n”, Total );
//print(n,copyl);
free(copyl);
copyl=alloc(n);
CopyStruct(list,copyl,n);
Start = clock();
mergesort(copyl,0,n-1);
End = clock();

Total = End – Start ;
printf(“\n- Merge Sort: %ld number clock \n”, Total );
//print(n,copyl);
free(copyl);
copyl=alloc(n);
CopyStruct(list,copyl,n);
Start = clock();
HeapSort(copyl,&n);
End = clock();

Total = End – Start ;
printf(“\n- Heap Sort: %ld number clock \n”,Total );
//print(n,copyl);
free(copyl);
copyl=alloc(n);
CopyStruct(list,copyl,n);
Start = clock();
selectionsort(copyl,n);
End = clock();

Total = End – Start ;
printf(“\n- Selection Sort: %ld number clock \n”,Total );
//print(n,copyl);
free(copyl);

copyl=alloc(n);
CopyStruct(list,copyl,n);

Start = clock();
quicksort(copyl,0,n-1);
End = clock();

Total = End – Start ;
printf(“\n- Quick Sort: %ld number clock \n”, Total );
//print(n,copyl);
free(copyl);

return 0;
}

Interactive.cpp

int ask_quantity(void)
{
int n;
printf(“\n\tInsert length array: “);
scanf(“%d”,&n);
return n;
}

struct number *alloc(int n)
{
int i; struct number *p;
p=(struct number *) malloc( n * sizeof(struct number));
if(p==NULL)return NULL;

for(i=0;i<n;i++)
{
p[i].value=0;
}

return p;
}

void insert_number(int n, struct number *p,int value)
{
int i,number;
//printf(“\n”);
for(i=1;i<n+1;i++)
{
//printf(“\tInsert %d° number : “,i);
//scanf(“%d”, &number);
//p[i-1].value=number;
p[i-1].value=rand()%value;
}
}

void print(int n, struct number *p)
{
int i;
printf(“\nThe array is\t\n\n”);
for(i=0;i<n;i++)
{
printf(“%d° number : %d \n”,i+1,p[i].value);
}
printf(“\n”);
}

function.cpp

void CopyStruct(struct number *a,struct number *b,int n)
{
int i;
for(i=0;i<n;i++)b[i].value=a[i].value;
}