Lista di liste

di il
9 risposte

Lista di liste

Salve, devo realizzare questo esercizio:
Realizzare l’operazione di prodotto scalare di 1 matrice per un reale.
Il tipo di dato matrice deve essere rappresentato come una lista di liste.

So già che è sprecato utilizzare una lista per questo tipo di esercizio ma il professore vuole che lo facciamo così.
Io ho pensato di strutturare il codice in questo modo:

#include <stdio.h>
#include <stdlib.h>
#define DIM 6

typedef struct CNodo{
	int dato;
	struct CNodo *prox;
}CNodo;

typedef struct RNodo{
	struct CNodo *prox;
}RNodo;

typedef RNodo *Lista;

typedef struct{
	int righe;
	int colonne;
}matrice;


int main(void){
	Lista a;
	Lista prodotto;
	matrice i;
	int Vett[DIM] = {1, 2, 3, 4, 5, 6};
	int num = 3;

	a = Inizializza();
	prodotto = Inizializza();

	a = ScriviMatrice(a, &i, Vett);
	StampaMatrice(a, i);

	prodotto = ProdottoMatrici(a, i, num, prodotto);
	StampaMatrice(prodotto, i);


	system("pause");
	return 0;
}
Cosa ve ne pare? Ho realizzato correttamente una liste di liste?
Grazie.

9 Risposte

  • Re: Lista di liste

    Spark ha scritto:


    So già che è sprecato utilizzare una lista per questo tipo di esercizio ma il professore vuole che lo facciamo così.
    Un feticista delle liste!

    Spark ha scritto:


    Cosa ve ne pare? Ho realizzato correttamente una liste di liste?
    Innanzitutto mancano le funzioni, quindi non posso dirti se il programma nel suo complesso è corretto.
    Inoltre la struct RNodo non dovrebbe contenere anche un membro
    struct RNodo *next;
    ?

    In ogni caso io imposterei il tutto nel seguente modo:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define RIG 3
    #define COL 5
    
    typedef struct nodo_1
    {
        int dato;
        struct nodo_1 *next;
    }   nodo_1;
    
    typedef struct nodo_2
    {
        nodo_1 *dato;
        struct nodo_2 *next;
    }   nodo_2;
    
    void aggiungi_in_testa_1(nodo_1 **p, int n)
    {
        ...
    }
    
    void aggiungi_in_testa_2(nodo_2 **p, int *v, unsigned int dim)
    {
        ...
    }
    
    void stampa_1(nodo_1 *p)
    {
        ...
    }
    
    void stampa_2(nodo_2 *p)
    {
        ...
    }
    
    int main()
    {
        int m[RIG][COL] = {{15, 14, 13, 12, 11}, {10, 9, 8, 7, 6}, {5, 4, 3, 2, 1}};
        nodo_2 *l = NULL;
        for(unsigned int i = 0; i < RIG; ++i)
        {
            aggiungi_in_testa_2(&l, m[i], COL);
        }
        stampa_2(l);
    }
  • Re: Lista di liste

    Non sarebbe più semplice utilizzare in questo caso la funzione AggiungiInCoda() visto che l'inserimento in testa è paragonabile ad una pila e l'inserimento in coda è di tipo first in first out ?
  • Re: Lista di liste

    Per aggiungere in coda non bisogna scorrere l'intera lista ogni volta?
  • Re: Lista di liste

    Giusto.
    Ho provato a scrivere il codice e non mi stampa la lista creata. Inoltre mi da un segmentation fault.
    Dove posso aver sbagliato?
    #include <stdio.h>
    #include <stdlib.h>
    #define RIG 3
    #define COL 2
    
    typedef struct CNodo{
    	int el;
    	struct CNodo *prox;
    }CNodo;
    
    typedef struct RNodo{
    	CNodo *dato;
    	struct RNodo *prox;
    }RNodo;
    
    typedef RNodo *Lista;
    
    typedef struct{
    	int righe;
    	int colonne;
    }matrice;
    
    Lista Inizializza(void);
    Lista ScriviMatrice(Lista a, matrice *p, int Vett[][COL]);
    Lista AggiungiRigaInCoda(Lista l, int Vett[][COL], int j);
    void StampaMatrice(Lista l, matrice p);
    
    int main(void){
    	Lista a;
    
    	//Lista prodotto;
    	matrice i;
    	int Vett[RIG][COL] = {{1, 2}, {3, 4}, {5, 6}};
    	//int num = 3;
    
    	a = Inizializza();
    	//prodotto = Inizializza();
    
    	a = ScriviMatrice(a, &i, Vett);
    
    	StampaMatrice(a, i);
    
    	//prodotto = ProdottoMatrici(a, i, prodotto, num);
    	//StampaMatrice(prodotto, i);
    
    
    	system("pause");
    	return 0;
    }
    
    Lista Inizializza(void){
    	return NULL;
    }
    
    Lista ScriviMatrice(Lista a, matrice *p, int Vett[][COL]){
    	RNodo *temp = a;
    	int j = 0;
    	p->colonne = 2;
    	p->righe = 3;
    
    	while (j < RIG){
    		temp = AggiungiRigaInCoda(temp, Vett, j); //viene inserita la riga Vett[j] all'interno del nodo RNodo
    		j++;
    	}
    	temp = a;
    
    	return temp;
    }
    
    Lista AggiungiRigaInCoda(Lista l, int Vett[][COL], int j){
    	//creo un nodo, lo alloco, lo faccio puntare a NULL. L'ultimo nodo punterà al nodo creato
    	//in questo modo il nuovo nodo è adesso l'ultimo elemento
    	RNodo *temp = l;
    	int i = 0;
    
    	temp = malloc(sizeof(RNodo));
    	temp->dato = malloc(sizeof(CNodo));
    	while (i < COL){
    		temp->dato->el = Vett[j][i];
    		//printf("temp->dato->el > %d\n",temp->dato->el);
    		temp->dato->prox = malloc(sizeof(CNodo));
    		temp->dato = temp->dato->prox;
    		i++;
    
    	}
        temp = temp->prox;
    
        return temp;
    }
    
    void StampaMatrice(Lista l, matrice p){
    	RNodo *temp = l;
    	int i = 0;
    	int j;
    	while(i < RIG){
    		j = 0;
    		while(j < COL){
    			printf("%d ",temp->dato->el);
    			temp->dato = temp->dato->prox;
    			j++;
    		}
    		printf("\n");
    		i++;
    		temp = temp->prox;
    	}
    	printf("\n");
    
    	return;
    }
    
  • Re: Lista di liste

    Innanzitutto la struct matrice è completamente inutile e la funzione Inizializza() superflua, basta inizializzare il puntatore a NULL quando lo dichiari.
    Per il resto dovrei mettermi d'impegno per cercare gli eventuali errori, ma sinceramente credo che non ne valga la pena, in quanto ritengo l'impostazione del codice inutilmente complicata.
    Di seguito la versione completa del codice che ho postato in precedenza:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define RIG 3
    #define COL 5
    
    typedef struct nodo_1
    {
        int dato;
        struct nodo_1 *next;
    }   nodo_1;
    
    typedef struct nodo_2
    {
        nodo_1 *dato;
        struct nodo_2 *next;
    }   nodo_2;
    
    void aggiungi_in_testa_1(nodo_1 **p, int n)
    {
        nodo_1 *nuovo = (nodo_1*)malloc(sizeof(nodo_1));
        nuovo->dato = n;
        nuovo->next = *p;
        *p = nuovo;
    }
    
    void aggiungi_in_testa_2(nodo_2 **p, int *v, unsigned int dim)
    {
        nodo_2 *nuovo = (nodo_2*)malloc(sizeof(nodo_2));
        nuovo->dato = NULL;
        nuovo->next = *p;
        *p = nuovo;
        for(unsigned int i = 0; i < dim; ++i)
        {
            aggiungi_in_testa_1(&(*p)->dato, v[i]);
        }
    }
    
    void stampa_1(nodo_1 *p)
    {
        while(p)
        {
            printf("%2d  ", p->dato);
            p = p->next;
        }
        printf("\n");
    }
    
    void stampa_2(nodo_2 *p)
    {
        while(p)
        {
            stampa_1(p->dato);
            p = p->next;
        }
    }
    
    int main()
    {
        int m[RIG][COL] = {{15, 14, 13, 12, 11}, {10, 9, 8, 7, 6}, {5, 4, 3, 2, 1}};
        nodo_2 *l = NULL;
        for(unsigned int i = 0; i < RIG; ++i)
        {
            aggiungi_in_testa_2(&l, m[i], COL);
        }
        stampa_2(l);
    }
    Se qualcosa non ti è chiaro chiedi pure.
  • Re: Lista di liste

    Perchè nella chiamata di funzione
    aggiungi_in_testa_2(&l, m[i], COL);
    passi
    m[i]
    per valore e non per indirizzo ?
  • Re: Lista di liste

    La funzione aggiungi_in_testa_2() si aspetta come secondo argomento un puntatore ad int che rappresenta l'array i cui elementi saranno utilizzati per aggiungere in testa alla lista di liste una nuova "riga".
    Ed essendo m[_i_]l'indirizzo di memoria dell'elemento che apre l'i-esima riga della matrice di interi, tutto torna.

    Tu come l'avresti scritta la chiamata a funzione?
  • Re: Lista di liste

    Ok, si, in effetti stai passando il primo elemento di una riga che in C corrisponde all'indirizzo dell'array.
    Ho fatto l'esercizio seguendo il modo in cui hai strutturato la lista di liste.
    #include <stdio.h>
    #include <stdlib.h>
    #define RIG 3
    #define COL 2
    
    typedef struct CNodo{
    	int el;
    	struct CNodo *prox;
    }CNodo;
    
    typedef struct RNodo{
    	CNodo *dato;
    	struct RNodo *prox;
    }RNodo;
    
    typedef CNodo *Lista2;
    typedef RNodo *Lista1;
    
    Lista1 CreaNodoRiga(Lista1 a);
    Lista1 AggiungiRigaInCoda(Lista1 a, int *Vett, int dim);
    Lista2 AggiungiInCoda(Lista2 b, int e);
    void StampaMatrice(Lista1 a);
    int Lista1Vuota(Lista1 a);
    int Lista2Vuota(Lista2 b);
    
    int main(void){
    	Lista1 a = NULL;
    
    	int i = 0;
    	int Vett[RIG][COL] = {{1, 2}, {3, 4}, {5, 6}};
    
    	while(i < RIG){
    		a = AggiungiRigaInCoda(a, Vett[i], COL);
    		i++;
    	}
    	printf("La matrice data in input e' la seguente:\n");
    	StampaMatrice(a);
    
    	system("pause");
    	return 0;
    }
    
    Lista1 AggiungiRigaInCoda(Lista1 a, int *Vett, int dim){
    	RNodo *temp = a;
    	int i = 0;
    
    	temp = CreaNodoRiga(temp);
    	printf("%p\n",temp); <------------------mi stampa sempre lo stesso indirizzo
    	while(i < dim){
    		temp->dato = AggiungiInCoda(temp->dato, Vett[i]);
    		i++;
    	}
    
    	return temp;
    }
    
    Lista1 CreaNodoRiga(Lista1 a){
    	//creo un nodo, lo alloco, lo faccio puntare a NULL. L'ultimo nodo punterà al nodo creato
    	//in questo modo il nuovo nodo è adesso l'ultimo elemento
    	RNodo *temp;
    	if(Lista1Vuota(a)) {
    		//se la lista è vuota, il nodo andrà al primo posto
    		temp = malloc(sizeof(RNodo));
    		temp->dato = NULL;
    		temp->prox = NULL;
    	}else {
    		temp = a;
    		//ciclo per posizionarsi sull’ultimo elemento con prox==NULL
    		while(temp->prox != NULL){
    			temp = temp->prox;
    		}
    		//assegnazione nuovo nodo in ultima posizione
    		temp->prox = malloc(sizeof(RNodo));
    		temp->prox->dato = NULL;
    		temp->prox->prox = NULL;
    		temp = a;
    	}
    	return temp;
    }
    
    Lista2 AggiungiInCoda(Lista2 b, int e){
    	//creo un nodo, lo alloco, lo faccio puntare a NULL. L'ultimo nodo punterà al nodo creato
    	//in questo modo il nuovo nodo è adesso l'ultimo elemento
    	CNodo *temp;
    	if(Lista2Vuota(b)) {
    		//se la lista è vuota, il nodo andrà al primo posto
    		temp = malloc(sizeof(CNodo));
    		temp->el = e;
    		temp->prox = NULL;
    	}else {
    		temp = b;
    		//ciclo per posizionarsi sull’ultimo elemento con prox==NULL
    		while(temp->prox != NULL){
    			temp = temp->prox;
    		}
    		//assegnazione nuovo nodo in ultima posizione
    		temp->prox = malloc(sizeof(CNodo));
    		temp->prox->el = e;
    		temp->prox->prox = NULL;
    		temp = b;
    	}
    	return temp;
    }
    
    int Lista1Vuota(Lista1 a){
    	return (a == NULL);
    }
    
    int Lista2Vuota(Lista2 b){
    	return (b == NULL);
    }
    
    void StampaMatrice(Lista1 a){
    	RNodo *temp = a;
    	int i = 0;
    	int j;
    
    	while(i < RIG){
    		j = 0;
    		while(j < COL){
    			printf("%d ",temp->dato->el);
    			temp->dato = temp->dato->prox;
    			j++;
    		}
    		printf("\n");
    		temp = temp->prox;
    		i++;
    	}
    
    	return;
    }
    Ho solo un problema, ovvero in questa funzione:
    Lista1 AggiungiRigaInCoda(Lista1 a, int *Vett, int dim){
    	RNodo *temp = a;
    	int i = 0;
    
    	temp = CreaNodoRiga(temp);
    	printf("%p\n",temp); <------------------mi stampa sempre lo stesso indirizzo
    	while(i < dim){
    		temp->dato = AggiungiInCoda(temp->dato, Vett[i]);
    		i++;
    	}
    
    	return temp;
    }
    temp vale sempre lo stesso indirizzo, quindi praticamente viene scritta solo la prima riga.
    Infatti quando vado ad eseguire il programma mi stampa questo:
    
    0x22d6010                                                                                                                                                                      
    0x22d6010                                                                                                                                                                      
    0x22d6010                                                                                                                                                                      
    La matrice data in input e' la seguente:                                                                                                                                       
    1 2                                                                                                                                                                            
    Segmentation fault (core dumped)
    
    Dove posso aver sbagliato? Grazie.
  • Re: Lista di liste

    Innanzitutto le funzioni ListaVuota() sono superflue.
    -------------------------------------------------------------------------
    int i = 0;
    while(i < RIG)
    {
        a = AggiungiRigaInCoda(a, Vett[i], COL);
        i++;
    }
    Hai qualcosa contro il for?
    -------------------------------------------------------------------------
    Passiamo alla funzione StampaMatrice()... utilizzando i for al posto dei while e rimuovendo la variabile temp che è superflua, si ottiene:
    void StampaMatrice(RNodo *p)
    {
        for(unsigned int i = 0; i < RIG; ++i)
        {
            for(unsigned int j = 0; j < COL; ++j)
            {
                printf("%d ", p->dato->el);
    	    p->dato = p->dato->prox;
            }
            printf("\n");
    	p = p->prox;
        }
    }
    Innanzitutto è concettualmente sbagliato, oltre che inutile, utilizzare delle dimensioni (mi riferisco a RIG e COL) quando si ha a che fare con delle liste, basta sfruttare il fatto che l'ultimo elemento punta a NULL. Quindi il codice diventa:
    void StampaMatrice(RNodo *p)
    {
        for(; p; p = p->prox)
        {
            for(; p->dato; p->dato = p->dato->prox)
            {
                printf("%d ", p->dato->el);
            }
            printf("\n");
        }
    }
    A questo punto ti faccio notare che stai andando a modificare i membri dato di p, i quali all'uscita della funzione punteranno tutti a NULL. Per il secondo for quindi diventa indispensabile utilizzare una variabile temporanea:
    void StampaMatrice(RNodo *p)
    {
        for(; p; p = p->prox)
        {
            for(CNodo *temp = p->dato;  temp; temp = temp->prox)
            {
                printf("%d ",temp->el);
            }
            printf("\n");
        }
    }
    Come alternativa potresti anche utilizzare le funzioni stampa_1() e stampa_2() che ho postato in precedenza.
    -------------------------------------------------------------------------
    Per quanto riguarda l'aggiunta in coda classica (ossia la funzione AggiungiInCoda()) mi sembra corretta, ma un po' ridondante. Potresti per esempio ricorrere a qualcosa del genere
    nodo* aggiungi_in_coda(nodo *p, int n)
    {
        nodo *nuovo = (nodo*)malloc(sizeof(nodo));
        nuovo->data = n;
        nuovo->next = NULL;
        if(!p)
        {
            p = nuovo;
        }
        else
        {
            nodo *temp = p;
            while(temp->next)
            {
                temp = temp->next;
            }
            temp->next = nuovo;
        }
        return p;
    }
    o ancora meglio utilizzare i puntatori doppi implementando la funzione di aggiunta in coda sfruttando quella di aggiunta in testa
    void aggiungi_in_testa(nodo **p, int n)
    {
        nodo *nuovo = (nodo*)malloc(sizeof(nodo));
        nuovo->data = n;
        nuovo->next = *p;
        *p = nuovo;
    }
    
    void aggiungi_in_coda(nodo **p, int n)
    {
        while(*p)
        {
            p = &(*p)->next);
        }
        aggiungi_in_testa(p, n);
    }
    -------------------------------------------------------------------------
    Lo stesso identico discorso vale anche per CreaNodoRiga().
    -------------------------------------------------------------------------
    Infine analizziamo la funzione AggiungiRigaInCoda(). Il problema qui è che CreaNodoRiga() restituisce sempre la testa della lista, quindi tutti gli array passati alla funzione saranno copiati sempre nel primo elemento della lista più esterna. Per intenderci, all'uscita del ciclo while nel main(), la lista di liste a sarà costituita da qualcosa del genere:



    Soluzione? Ce ne sono molte, ma credo che la cosa più semplice sia unire CreaNodoRiga() e AggiungiRigaInCoda() in un'unica funzione del tipo:
    nodo_2* aggiungi_in_coda_2(nodo_2 *p, int *v, unsigned int dim)
    {
        nodo_2 *nuovo = (nodo_2*)malloc(sizeof(nodo_2));
        nuovo->data = NULL;
        for(unsigned int i = 0; i < dim; ++i)
        {
            nuovo->data = aggiungi_in_coda_1(nuovo->data, v[i]);
        }
        nuovo->next = NULL;
        if(!p)
        {
            p = nuovo;
        }
        else
        {
            nodo_2 *temp = p;
            while(temp->next)
            {
                temp = temp->next;
            }
            temp->next = nuovo;
        }
        return p;
    }
Devi accedere o registrarti per scrivere nel forum
9 risposte