[C] Intersezione ordinata di due liste

Messaggioda nick_10 » 24/12/2018, 12:46

Ciao a tutti! Ho iniziato i primi esercizi sulle liste e dopo i primi (pochi) successi mi sono bloccato su questo esercizio:
"Scrivere un programma che acquisisca da tastiera due successioni di interi positivi, entrambe terminate da un numero negativo, e le inserisca in due liste distinte. Scegliere se realizzare una procedura o una funzione che, prese
in input le due liste, crei una terza lista contenente l’intersezione ordinata tra le due precedenti: non vi devono quindi essere elementi ripetuti e i valori devono essere memorizzati in ordine crescente. Si stampi il contenuto della
lista intersezione"
Prima di tutto ho provato a fare una funzione che crei l'intersezione delle due liste, poi farei una per ordinarla. Il punto è che non va la prima funzione.
Codice:
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE 1
struct elemento{
    int info;
    struct elemento * next;
};
typedef struct elemento ElementoLista;
typedef ElementoLista* ListaDiElementi;
ListaDiElementi crealista(){
    ListaDiElementi lista,aux;
    int n;
    scanf("%d",&n);
    if(n<0) {
        lista=NULL;
        return(lista);
    }
    else{
        //creo il primo elemento
        lista=malloc(sizeof(ElementoLista));
        lista->info=n;
        aux=lista;
        while(n>=0){
            scanf("%d",&n);
            if(n>=0){
                aux->next=malloc(sizeof(ElementoLista));
                aux=aux->next;
                aux->info=n;
            }
        }
        aux->next=NULL;
        return(lista);
    }
}
void stampalista(ListaDiElementi lista){
    while(lista!=NULL){
        printf("%d",lista->info);
        lista=lista->next;
        printf("\n");
    }
}
ListaDiElementi intersezione(ListaDiElementi *lista1, ListaDiElementi *lista2){
    ListaDiElementi lista3,p,i,aux;
    int trovato=FALSE;
    int primavolta=TRUE;
    p=*lista1;
    i=*lista2;
    while(p->next!=NULL){
        while(i->next!=NULL && !trovato){
            if((p->info)==(i->info)){
                trovato=TRUE;
                if(primavolta){
                    lista3=malloc(sizeof(ElementoLista));
                    lista3->info=p->info;
                    aux=lista3;
                    primavolta=FALSE;
                }
                else{
                    aux->next=malloc(sizeof(ElementoLista));
                    aux=aux->next;
                    aux->info=p->info;
                }
            }
            i=i->next;
        }
        p=p->next;
    }
    aux->next=NULL;
    return(lista3);
}
int main() {
    ListaDiElementi lista1,lista2,lista3;
    lista1=crealista();
    lista2=crealista();
    lista3=intersezione(&lista1, &lista2);
    stampalista(lista3);
    return 0;
}
nick_10
Average Member
Average Member
 
Messaggio: 372 di 754
Iscritto il: 17/11/2016, 16:21

Re: [C] Intersezione ordinata di due liste

Messaggioda Super Squirrel » 26/12/2018, 14:14

Credo che la cosa più semplice ed efficiente sia implementare una funzione del tipo

void fun(nodo **L, int n)

che inserisca l'elemento n direttamente nella posizione corretta (ossia tale da rispettare l'ordine crescente), a meno che esso non sia già presente nella lista L.
Fatto ciò basterà fare qualcosa del genere:
Codice:
...

void intersezione_liste(nodo **destinazione, nodo *origine)
{
    while(origine)
    {
        fun(destinazione, origine->dato);
        origine = origine->next;
    }
}

int main()
{
    nodo *L1 = NULL;
    nodo *L2 = NULL;
    nodo *L3 = NULL;
    ...
    intersezione_liste(&L3, L1);
    intersezione_liste(&L3, L2);
}
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 333 di 1486
Iscritto il: 16/05/2013, 22:05

Re: [C] Intersezione ordinata di due liste

Messaggioda nick_10 » 30/12/2018, 13:04

Grazie per l'interesse e scusa per l'attesa. Son stati giorni un po impegnativi
Comunque poi avevo scritto una cosa del genere:
Codice:
#include <stdio.h>
#include <stdlib.h>
struct elemento{
    int info;
    struct elemento * next;
};
typedef struct elemento ElementoLista;
typedef ElementoLista* ListaDiElementi;
void stampalista(ListaDiElementi lista){
    while(lista!=NULL){
        printf("%d",lista->info);
        lista=lista->next;
        printf("\n");
    }
}
void aggiungiintesta(ListaDiElementi *lista,int v){
    ListaDiElementi aux;
    aux=malloc(sizeof(ElementoLista));
    aux->info = v;
    aux->next = *lista;
    *lista = aux;
}
void InserzioneOrdinata(ListaDiElementi *lista, int elem) {
    if (*lista==NULL) {
        aggiungiintesta(lista,elem);
    }
    else {
        if ((*lista)->info > elem) {
            aggiungiintesta(lista,elem);
        }
        else InserzioneOrdinata(&((*lista)->next), elem);
    }
}
ListaDiElementi EliminaDoppi(ListaDiElementi lista3)
{
    if(lista3==NULL)
        return NULL;
    ListaDiElementi prec=lista3;
    ListaDiElementi corr=prec->next;
    ListaDiElementi tmp=NULL;
    while(corr!=NULL)
    {
        if(prec->info==corr->info)
        {
            tmp=corr;
            prec->next=corr->next;
            corr=corr->next;
            free(tmp);
        }
        else
        {
            prec=corr;
            corr=corr->next;
        }
    }
    return lista3;
}
ListaDiElementi IntOrd(ListaDiElementi lista1, ListaDiElementi lista2){
   
    ListaDiElementi l;
    if ((lista1==NULL)||(lista2==NULL)){ return NULL;}
    else if (lista1->info < lista2->info){
        return IntOrd(lista1->next,lista2);
    }
    else if (lista1->info > lista2->info){
        return IntOrd(lista1,lista2->next);
    }
    else{
        l = malloc(sizeof(ElementoLista));
        l->info = lista1->info;
        l->next = IntOrd(lista1->next,lista2->next);
        return l;
    }
}

Ho evitato di riportare anche il main...
nick_10
Average Member
Average Member
 
Messaggio: 373 di 754
Iscritto il: 17/11/2016, 16:21

Re: [C] Intersezione ordinata di due liste

Messaggioda Super Squirrel » 30/12/2018, 17:02

Devo fare una rettifica: non so perché, ma nel mio precedente post quando ho scritto intersezione mi stavo invece riferendo all'unione, che mi rendo conto nulla c'entra con l'esercizio che stai svolgendo! :D
Giusto per chiarire, affinché il codice che ho postato risulti corretto bisogna rinominare la funzione intersezione_liste() in unione_liste(), in ogni caso il discorso relativo alla funzione fun() rimane valido.

Tornando all'intersezione e all'ultimo codice che hai postato:
- a scanso di equivoci, la funzione EliminaDoppi() dovrebbe essere chiamata elimina_doppi_da_lista_ordinata();
- anche la funzione IntOrd() funziona solo se le due liste passate come argomento sono ordinate (in ordine crescente). Per liste qualsiasi invece bisognerà scorrere interamente la lista2 per ogni elemento della lista1 (o viceversa);
- se modifichi la funzione InserzioneOrdinata() affinché sia equivalente a fun(), ti renderai conto che la funzione EliminaDoppi() diventa superflua.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 334 di 1486
Iscritto il: 16/05/2013, 22:05


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite