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);
}