#include <iostream>
#include "listavt.h"
#include "servizi.h"
using namespace std;
typedef Lista<double>::tipoelem tipoelem;
typedef int posizione;
//FUNZIONE INSERIMETO DEGLI ELEMENTI NELLA LISTA
void scrivi(Lista<double> &L){
int n;
posizione indiceElem = L.primoLista();
tipoelem ilprimo, elemento;
cout<<"Quanti elementi vuoi inserire?\n\n";
cin>>n;
if(n<=MAX){
if (n>0){
/*cout<<"Inserisci il primo elemento\n\n";
cin>>ilprimo;
L.insLista(ilprimo, indiceElem);*/
for (int i=1; i<=n; i++){
cout<<"Inserisci l' elemento:\t";
cin>>elemento;
cout<<"\n";
L.insLista(elemento, indiceElem);
indiceElem=L.succLista(indiceElem);
}
}
else cout<<"Nessun elemento da inserire\n\n";
}
else cout<<"Errore: numero massimo di elementi superato!\n\n";
}
//FUNZIONE DI STAMPA DELLA LISTA
void stampa(Lista<double> &L){
posizione i;
cout<<"La lista inserita e':\n\n";
cout<<"[ ";
for (i=L.primoLista(); !L.fineLista(i); i=L.succLista(i)){
cout<<L.leggiLista(i)<<"\t";
}
cout<<" ]\n\n";
}
//FUNZIONE DI CANCELLAZIONE DI UN ELEMENTO DALLA LISTA
void cancElem(Lista<double> &L){
posizione pos,temp;
cout<<"CANCELLAZIONE ELEMENTO\n";
cout<<"Inserisci la posizione dell' elemento che vuoi cancellare:\t";
cin>>pos;
temp=L.primoLista();
while(temp!=pos){
temp=L.succLista(temp);
}
cout<<"\n";
L.cancLista(pos);
}
//FUNZIONE INSERIMENTO ELEMENTO
void inserimentoElem(Lista<double> &L){
posizione pos;
tipoelem elemento;
cout<<"INSERIMENTO ELEMENTO\n";
cout<<"Inserisci l'elemento che vuoi aggiungere alla lista:\t";
cin>>elemento;
cout<<"\n";
cout<<"Inserisci la posizione in cui vuoi inserire l'elemento:\t";
cin>>pos;
cout<<"\n";
for(int j=L.primoLista(); j<=pos; j++ ){
j=L.succLista(j);
}
L.insLista(elemento, pos);
}
//FUNZIONE AGGIORNAMENTO ELEMENTO
void aggiornamentoElem(Lista<double> &L){
posizione i, temp;
tipoelem elemento;
cout<<"AGGIORNAMENTO\n";
cout<<"Inserisci l'elemento che vuoi inserire:\t";
cin>>elemento;
cout<<"\n";
cout<<"Inserisci la posizione di cui vuoi aggiornare l'elemento:\t";
cin>>i;
cout<<"\n";
temp=L.primoLista();
while (temp!=i){
temp=L.succLista(temp);
}
L.scriviLista(elemento,i);
}
tipoelem letturaElem(Lista<double> &L){
if(!L.listaVuota()){
posizione pos,temp;
cout<<"Inserisci la posizione di cui vuoi visualizzare il valore:\t";
cin>>pos;
temp=L.primoLista();
while (temp!=pos){
temp=L.succLista(temp);
}
cout<<"\n Il valore nella posizione "<<pos<<" e':\t"<<L.leggiLista(pos)<<"\n\n";
}
}
void epurazione(Lista<double> &L){
posizione p, q;
p=L.primoLista();
while(!L.fineLista(p)){
q=L.succLista(p);
while (!L.fineLista(q)){
if (L.leggiLista(p)==L.leggiLista(q)){
L.cancLista(q);
}
else q=L.succLista(q);
}
p=L.succLista(p);
}
}
//ORDINAMENTO BUBBLESORT
void bubbleSort (Lista<double> &L){
posizione lunghezza=0;
tipoelem elemento;
posizione pl;
posizione alto;
pl=L.primoLista();
while (!L.fineLista(pl)){
pl=L.succLista(pl);
lunghezza=lunghezza+1;
}
alto=lunghezza-1;
while (alto>0){
pl=L.primoLista();
while(pl!=lunghezza){
if((L.leggiLista(pl))>(L.leggiLista(L.succLista(pl)))){
elemento=L.leggiLista(pl);
L.scriviLista(L.leggiLista(L.succLista(pl)),pl);
L.scriviLista(elemento,L.succLista(pl));
}
pl=L.succLista(pl);
}
alto=alto-1;
}
}
//RICERCA DI UN ELEMENTO
void ricerca(Lista<double> &L){
tipoelem elemento;
cout<<"Insersci l'elemento che vuoi ricercare \t";
cin>>elemento;
posizione p=L.primoLista();
while(elemento!=L.leggiLista(p)){
p=L.succLista(p);
}
cout<<"L'elemento e' stato trovato e ha posizione "<<p<<"\n\n";
}
//ORDINAMENTO NATURALE MERGE SORT
/*void mergesort(Lista &L){
int n_catene=0;
while (n_catene!=1 ){
Lista A;
Lista B;
distribuisci(L, A, B);
n_catene=0;
Lista L;
merge(A, B, L, n_catene);
stampa(L);
}
}
void distribuisci(Lista &L, Lista &A, Lista &B){
posizione pl=L.primoLista();
posizione pa=A.primoLista();
posizione pb=B.primoLista();
while (!L.fineLista(pl)){
copiaCatena(pl, L, pa, A);
if (!L.fineLista(pl)){
copiaCatena(pl, L, pb, B);
}
}
}
posizione copiaCatena(posizione &pa, Lista &A, posizione &pb, Lista &B){
bool finecatena=false;
while (finecatena!=true){
copia(pa, A, pb, B, finecatena);
}
return pa;
}
bool copia(posizione &pa, Lista &A, posizione &pl, Lista &L, bool &finecatena){
tipoelem elemento=A.leggiLista(pa);
L.insLista(elemento, pl);
pa=A.succLista(pa);
pl=L.succLista(pl);
if (A.fineLista(pa))
finecatena=true;
else
{ finecatena=(elemento>A.leggiLista(pa)); }
return finecatena;
}
int merge(Lista &A, Lista &B, Lista &L, int &n_catene){
posizione pa=A.primoLista();
posizione pb=B.primoLista();
posizione pl=L.primoLista();
while((!A.fineLista(pa)) && (!B.fineLista(pb))){
fondiCatena(pa, A, pb, B, pl, L);
n_catene++;
}
while (!A.fineLista(pa)){
copiaCatena(pa, A, pl, L);
n_catene++;
}
while (!B.fineLista(pb)){
copiaCatena(pb, B, pl, L);
n_catene++;
}
return n_catene;
}
void fondiCatena(posizione &pa, Lista &A, posizione &pb, Lista &B, posizione &pl, Lista &L){
bool finecatena=false;
while (finecatena!=true){
if (A.leggiLista(pa)<B.leggiLista(pb)){
copia(pa, A, pl, L, finecatena);
if (finecatena==true)
copiaCatena(pb, B, pl, L);
}
else{
copia(pb, B, pl, L, finecatena);
if (finecatena==true){
copiaCatena(pa, A, pl, L);
}
}
}
}
*/
//FUSIONE DI DUE LISTE ORDINATE
void fusione(Lista<double> &L1, Lista<double> &L2, Lista<double> &L3){
cout<<"FUSIONE DI DUE LISTE ORDINATE\n\n";
posizione pl1, pl2, pl3;
tipoelem elem1, elem2;
pl1=L1.primoLista();
pl2=L2.primoLista();
pl3=L3.primoLista();
int contatore=0;
while ((!L1.fineLista(pl1)) && (!L2.fineLista(pl2))){
elem1=L1.leggiLista(pl1);
elem2=L2.leggiLista(pl2);
if (elem1<elem2){
L3.insLista(elem1,pl3);
contatore++;
pl1=L1.succLista(pl1);
}
else {
L3.insLista(elem2, pl3);
contatore++;
pl2=L2.succLista(pl2);
}
pl3=L3.succLista(pl3);
}
while (!L1.fineLista(pl1)){
L3.insLista(L1.leggiLista(pl1), pl3);
contatore++;
pl1=L1.succLista(pl1);
pl3=L3.succLista(pl3);
}
while (!L2.fineLista(pl2)){
L3.insLista(L2.leggiLista(pl2), pl3);
contatore++;
pl2=L2.succLista(pl2);
pl3=L3.succLista(pl3);
}
}