Salve...
Il seguente programma implementa due linked list con le relative funzioni.
Inoltre è presente una funzione per concatenare le due linked list.
Il problema è che la lista ottenuta dalla concatenazione non è ordinata.
Potreste modificarmi il codice della funzione ordina, affinchè l'output
sia quello desiderato?
Il codice sorgente è il seguente:
codice://file.cpp #include "Lista.h" #include <iostream> #include <list> using namespace std; //------------------------------------------------------------ void start(L& l) { l=0; } //------------------------------------------------------------ bool empty(const L& l) { return (l==0); } //------------------------------------------------------------ bool full(const L& l) { return false; } //------------------------------------------------------------ void push(L& l,const E & e) { L q=new Record; //alloca spazio q->elem=e; //vi pone e q->punt=l; //lega al resto della lista l=q; //lo mette in testa alla lista } //------------------------------------------------------------ // append versione iterativa void append(L& l,const E & e) { if(l==0) push(l,e); else { L temp=l; L q=new Record; //alloca spazio q->elem=e; //vi pone e q->punt=0; // e' l'ultimo elemento della lista while(temp->punt) temp=temp->punt; //scorre la lista, si ferma sull'ultimo elemento temp->punt=q; //lo mette in coda alla lista } //fine if } //------------------------------------------------------------ // inserimento ordinato void insert (L& l, const E & e){ if(l==0 || l->elem > e) push(l,e); else{ L prec=l, succ=0; L q=new Record; //alloca ed inizializza il nuovo elemento q->elem=e; q->punt=0; while (prec->punt && prec->punt->elem < e) //scorre la lista prec=prec->punt; //determina prec succ=prec->punt; //determina succ, se l'inserimento è in coda succ vale zero q->punt=succ; prec->punt=q; } } //------------------------------------------------------------ void pop(L& l,E& e) { //oppure: bool pop(L& l,E& e) e=l->elem; // copia in e il primo elemento L p=l; // salva il valore di l l=l->punt; //aggiorna l delete p; // dealloca il primo elemento } //------------------------------------------------------------ // Eliminazione dell'ultimo elemento: versione iterativa bool lastpop(L& testa_lista) { L el=testa_lista; while (el->punt!= NULL) { if (el->punt->punt==NULL) { L Y=el->punt; el->punt=NULL; delete Y; return true; } el = el->punt; } return false; } //------------------------------------------------------------ // inlist: ricerca sequenziale versione iterativa bool inlist(const L& l,const E & e) { L temp=l; bool trovato=false; while (temp && !trovato) { if (e==temp->elem) trovato=true; else temp=temp->punt; } return trovato; } //------------------------------------------------------------ //concatenazione di due liste L concatenate(L list1,L list2){ L l3; l3=list1; while(l3->punt!=NULL) l3=l3->punt; l3->punt=list2; return list1; } //------------------------------------------------------- //ordinamento della lista void ordina(L& l){ L temp=NULL; L current = l; while(current->punt != NULL) { if(current->elem > current->punt->elem){ temp->elem = current->elem; current->elem = current->punt->elem; current->punt->elem = temp->elem; } current = current->punt; } } //------------------------------------------------------------ // stampa versione iterativa void print(const L & l) { L temp=l; while(temp) { cout << temp->elem; cout << "\t"; temp=temp->punt; } cout<<"\n"; } void clear(L&l){ L temp; while(l){ temp=l; l=l->punt; delete temp; } } //file.h #ifndef LISTA_H #define LISTA_H #ifndef _LISTA_H_ // Compilazione condizionale #define _LISTA_H_ #include <list> typedef int E; // Def. del tipo di el. della lista struct Record; // Predichiarazione typedef Record* L; // Def. del tipo puntatore a Record struct Record { // Tipo record costituito da E elem; // campo informazione L punt; // campo puntatore al prossimo nodo della lista }; void start(L& ); // Inizializza la lista bool empty(const L& ); // Test di lista vuota bool full(const L& ); // Test di lista piena void push(L& , const E & ); // Inserimento in testa void append(L& , const E & ); // Inserimento in coda void insert(L& , const E & ); // Inserimento ordinato void pop(L& , E& ); // Cancellazione in testa bool lastpop(L& ); // Cancellazione in coda bool inlist(const L& , const E & ); // Vera se e e' presente nella lista L concatenate(L , L); // Concatenazione di due liste void ordina(L& ); void print(const L & ); // Stampa la lista void clear(L &); //Svuota la lista #endif #endif //main #include <iostream> #include <stdlib.h> #include "Lista.h" using namespace std; int main(){ L Listauno; L Listadue; L Listatre; start(Listauno); start(Listadue); start(Listatre); cout<<"***PRIMA LISTA***\n"; insert(Listauno,5); insert(Listauno,2); insert(Listauno,9); insert(Listauno,7); print(Listauno); cout<<"***SECONDA LISTA***\n"; insert(Listadue,3); insert(Listadue,1); insert(Listadue,8); print(Listadue); cout<<"***TERZA LISTA***\n"; Listatre=concatenate(Listauno,Listadue); ordina(Listatre); print(Listatre); }
Rispondi quotando
