[C] Problema con le liste

[jarrod]

Ciao, la consegna è questa:

typedef struct item{
	char nome[20];
	int voto;
	struct item *next;
}nodo;

Data una lista esistente di elementi nodo, scrivere una funzione che crea una lista contenente, per ciascun nome (quindi per ogni persona), la media aritmetica dei propri voti. La nuova lista sia ordinata in ordine alfabetico rispetto al nome.

questo è il mio programmino:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>

typedef struct itemV{
	char nome[20];
	int voto;
	struct itemV *next;
}nodoV;

typedef struct itemM{
	char nome[20];
	int media;
	struct itemM *next;
}nodoM;

typedef nodoV *listV;
typedef nodoM *listM;

void emptylist(){
	return;
}

bool empty(void *l){	
	return l == NULL;
}

listV tailV(listV lV){

	if (empty(lV)){
		abort();
	}
	return lV->next;

}

listM tailM(listM lM){
	if (empty(lM)){
		abort();
	}
	return lM->next;
}

listV conslistV(char nome[], int voto, listV next){
	listV lV = malloc(sizeof(nodoV));
	strcpy(lV->nome, nome);
	lV->voto = voto;
	lV->next = next;

	return lV;
}

listM conslistM(char nome[], int media, listM next){
	listM lM = malloc(sizeof(nodoM));
	strcpy(lM->nome, nome);
	lM->media = media;
	lM->next = next;

	return lM;
}

listV insertTailV(char nome[], int voto, listV lV){
	if (empty(lV)){
		return conslistV(nome, voto, NULL);
	}
	listV root = lV;
	listV prev = lV;

	while (!empty(lV)){
		prev = lV;
		lV = tailV(lV);
	}
	prev->next = conslistV(nome, voto, NULL);

	return root;
}

int calcolomedia(listV lV){

	int sum = 0;
	int i = 0;
	while (!empty(lV)){
		
		sum += lV->voto;
		lV = tailV(lV); 
		i++;
	}

	int media = sum / i;

	return media;
}


listM insertTailM(char nome[], int media, listM lM){
	if (empty(lM)){
		return conslistM(nome, media, NULL);
	}

	listM root = lM;
	listM prev = lM;
	while (!empty(lM)){
		prev = lM;
		lM = tailM(lM);
	}
	prev->next = conslistM(nome, media, NULL);

	return root;

}

int main(){
	listV mylist = NULL;		//lista vuota di partenza
	listM mynewlist = NULL;
	char nome[20];
	int voto;
	printf("digita nome:");
	scanf("%s", &nome);


	do{
		
		printf("digito voto:");
		scanf("%d", &voto);
		if (voto >= 0){
			mylist = insertTailV(nome, voto, mylist);
		}
	} while (voto >= 0);

	int media = calcolomedia(mylist);

	mynewlist = insertTailM(nome, media, mynewlist);

}

Ho questi dubbi/problemi:
Per prima cosa, nella consegna viene detto che dobbiamo creare una nuova lista partendo da una lista già esistente. Quindi, io ho pensato di creare una lista sul momento, cioè tramite scanf gli passo i voti di una persona, cosi costruisco la lista a poco a poco. Però mi sono accorto che non è il massimo fare cosi, perchè altrimenti se voglio aggiungere un'altra persona con altri voti, non riuscirei a farlo. Qualcuno mi riesce ad indicare un metodo simile, o un altro metodo?

Poi per quanto riguarda l'ultimo punto.. per riordinare in ordine alfabetico a me sono venuti in mente tecniche di ordinamento come Bubble sort, però in questo caso mi sembra abbastanza difficile utilizzarla dal momento che si tratta di liste e di non array.. avete per favore qualche consiglio da darmi?

[Super Squirrel]

Premetto che ho dato un'occhiata molto veloce al codice. Alcune osservazioni:
- al fine di creare la lista iniziale, ti consiglio una semplice funzione che aggiunge in coda un nuovo nodo caratterizzato da un certo nome e un certo voto inseriti tramite scanf;
- utilizzerei una sola struct senza fare distinzione tra voto e media;
- come già detto nell'altro topic sostituirei le varie funzioni emptylist, empty, tail e conslist con un'unica funzione ed eviterei di usare la funzione abort.

Creata la lista iniziale con nomi diversi che si ripetono, bisogna quindi escogitare un algoritmo che crei una nuova lista che rispetti le indicazioni della consegna. Per quanto riguarda l'ordinamento sono d'accordo sul fatto che con le liste, rispetto agli array, risulta più complicato, ma è cmq fattibile.
Se serve aiuto chiedi pure.

[jarrod]

"Super Squirrel":
- al fine di creare la lista iniziale, ti consiglio una semplice funzione che aggiunge in coda un nuovo nodo caratterizzato da un certo nome e un certo voto inseriti tramite scanf;

Ho un dubbio.. io la consegna l'ho interpretata cosi:
gli passo ad esempio:
nome: Luca
voto: 7

nome: Matteo
voto: 6

nome: Luca
voto: 9

nome: Carlo
voto: 4

nome: Matteo
voto: 10


Cosi poi creo una lista:
con Luca e la sua media, poi Matteo con la sua media e infine Carlo con la sua media

Oppure devo digitare una volta un nome, e poi tutti i suoi voti? (come il do-while che ho utilizzato nel mio codice)
Se sono disordinati, come nell'esempio precedente, la strada della scanf non è impossibile?

[Super Squirrel]

Ho un dubbio.. io la consegna l'ho interpretata cosi:
gli passo ad esempio:
nome: Luca
voto: 7

nome: Matteo
voto: 6

nome: Luca
voto: 9

nome: Carlo
voto: 4

nome: Matteo
voto: 10


Cosi poi creo una lista:
con Luca e la sua media, poi Matteo con la sua media e infine Carlo con la sua media

Anche io l'ho interpretata così.
Non capisco dove sia il problema, inserisci da tastiera nome e voto e passi questi dati alla funzione che aggiungerà in coda il nuovo nodo.

[jarrod]

aggiungere a poco alla volta è facile, ho molto chiaro il metodo da utilizzare.. Infatti io in ogni esercizio, ho sempre digitato e subito inserito l'elemento nella lista.. non capisco in questo caso come potrei creare una lista dove da disordinati, riesco ad esempio a prendere tutti i voti di luca e mettere la media in un nodo, poi nel nodo successivo, trovare tutti i voti di Matteo e metterli nel nodo successivo. Non ho chiaro il meccanismo di controllo, cioè ho un nome di un tipo, e scarto tutti i voti degli altri..
Se non hai capito, provo a spiegarlo in un altro modo

[Super Squirrel]

Non sono sicuro di aver capito quello che intendi.
In ogni caso per creare la prima lista farei qualcosa del genere:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct item
{
    char nome[20];
    float voto;
    struct item *next;
}   nodo;

void aggiungi_coda(nodo **testa, char *NOME, int VOTO)
{
    nodo *nuovo = malloc(sizeof(nodo));
    strcpy(nuovo->nome, NOME);
    nuovo->voto = VOTO;
    nuovo->next = NULL;
    if(*testa == NULL)
    {
        *testa = nuovo;
    }
    else
    {
        nodo *temp = *testa;
        while(temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = nuovo;
    }
}

void mostra_lista(nodo *testa)
{
    if(testa == NULL)
    {
        printf("LISTA VUOTA!\n");
    }
    else
    {
        do
        {
            printf("%s: %.1f\n", testa->nome, testa->voto);
            testa = testa->next;
        }
        while(testa != NULL);
    }
}

int main()
{
    nodo *list_1 = NULL;
    nodo *list_2 = NULL;
    int inserimento;
    char NOME[20];
    float VOTO;
    while(1)
    {
        printf("INSERIMENTO: ");
        scanf("%d", &inserimento);
        if(inserimento == 0)
        {
            break;
        }
        printf("NOME: ");
        scanf("%s", &NOME);
        printf("VOTO: ");
        scanf("%f", &VOTO);
        aggiungi_coda(&list_1, NOME, VOTO);
    }
    mostra_lista(list_1);
}

A questo punto per ottenere la seconda lista potresti scorrere gli elementi della prima e:
- se incontri un nodo caratterizzato da un nome non presente nella seconda lista, aggiungi tale nodo in coda alla seconda lista;
- se incontri un nodo caratterizzato da un nome già presente nella seconda lista, aggiorni il corrispondente nodo della seconda lista sommandogli il voto.
Alla fine di questo procedimento la seconda lista conterrà tutti i nomi senza ripetizioni e la variabile membro voto conterrà la somma di tutti i voti di quella persona. Per calcolare la media potresti tener traccia del numero di voti in un array oppure utilizzando per la seconda lista una nuova struct dotata di una variabile membro contatore.
A questo punto non resta che ordinare la seconda lista in ordine alfabetico.

Questa è la prima cosa che mi è venuta in mente, non escludo che ci possa essere un approccio più efficiente.

[Super Squirrel]

Ho provato a risolvere l'esercizio:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

typedef struct item
{
    char nome[20];
    float voto;
    int cont;
    struct item *next;
}   nodo;

void aggiungi_coda(nodo **testa, char *NOME, int VOTO)
{
    nodo *nuovo = malloc(sizeof(nodo));
    strcpy(nuovo->nome, NOME);
    nuovo->voto = VOTO;
    nuovo->cont = 1;
    nuovo->next = NULL;
    if(*testa == NULL)
    {
        *testa = nuovo;
    }
    else
    {
        nodo *temp = *testa;
        while(temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = nuovo;
    }
}

void mostra_lista(nodo *testa)
{
    if(testa == NULL)
    {
        printf("LISTA VUOTA!\n");
    }
    else
    {
        do
        {
            printf("%s: %.1f\n", testa->nome, testa->voto);
            testa = testa->next;
        }
        while(testa != NULL);
    }
}

nodo* ottieni_lista(nodo *testa_1)
{
    nodo *testa_2 = NULL;
    nodo *temp;
    bool flag;
    while(testa_1 != NULL)
    {
        temp = testa_2;
        flag = true;
        while(temp != NULL)
        {
            if(strcmp(testa_1->nome, temp->nome) == 0)
            {
                temp->voto += testa_1->voto;
                ++(temp->cont);
                flag = false;
                break;
            }
            temp = temp->next;
        }
        if(flag)
        {
            aggiungi_coda(&testa_2, testa_1->nome, testa_1->voto);
        }
        testa_1 = testa_1->next;
    }
    temp = testa_2;
    while(temp != NULL)
    {
        temp->voto = temp->voto / temp->cont;
        temp = temp->next;
    }
    return testa_2;
}

void ordina_lista(nodo **testa)
{
    if(*testa != NULL && (*testa)->next != NULL)
    {
        nodo *temp_1;
        nodo *temp_2;
        nodo *prev;
        bool flag;
        do
        {
            temp_1 = *testa;
            temp_2 = (*testa)->next;
            flag = false;
            do
            {
                if(strcmp(temp_1->nome, temp_2->nome) > 0)
                {
                    temp_1->next = temp_2->next;
                    temp_2->next = temp_1;
                    if(*testa == temp_1)
                    {
                        *testa = temp_2;
                    }
                    else
                    {
                        prev->next = temp_2;
                    }
                    prev = temp_2;
                    temp_2 = temp_1->next;
                    flag = true;
                }
                else
                {
                    prev = temp_1;
                    temp_1 = temp_1->next;
                    temp_2 = temp_2->next;
                }
            }
            while(temp_2 != NULL);
        }
        while(flag);
    }
}

int main()
{
    nodo *list_1 = NULL;
    /*
    char NOME[20];
    float VOTO;
    int inserimento;
    while(true)
    {
        printf("INSERIMENTO: ");
        scanf("%d", &inserimento);
        if(inserimento == 0)
        {
            break;
        }
        printf("NOME: ");
        scanf("%s", &NOME);
        printf("VOTO: ");
        scanf("%f", &VOTO);
        aggiungi_coda(&list_1, NOME, VOTO);
    }
    */
    aggiungi_coda(&list_1, "Zorro"   , 7);
    aggiungi_coda(&list_1, "Mario"   , 5);
    aggiungi_coda(&list_1, "Antonio" , 6);
    aggiungi_coda(&list_1, "Maria"   , 3);
    aggiungi_coda(&list_1, "Maria"   , 9);
    aggiungi_coda(&list_1, "Luca"    , 4);
    aggiungi_coda(&list_1, "Giorgio" , 7);
    aggiungi_coda(&list_1, "Mario"   , 9);
    aggiungi_coda(&list_1, "Luca"    , 6);
    aggiungi_coda(&list_1, "Zorro"   , 8);
    aggiungi_coda(&list_1, "Maria"   , 7);
    aggiungi_coda(&list_1, "Antonio" , 5);
    aggiungi_coda(&list_1, "Maria"   , 8);
    aggiungi_coda(&list_1, "Aldo"    , 7);
    aggiungi_coda(&list_1, "Zorro"   , 7);
    nodo *list_2 = ottieni_lista(list_1);
    ordina_lista(&list_2);
    mostra_lista(list_2);
}

Per tenere conto del numero di voti ho modificato la struct aggiungendo la variabile membro contatore.
Per quanto riguarda l'ordinamento ho optato per il bubble sort. Ho implementato la prima cosa che mi è venuta in mente, è probabile quindi che ci siano margini di miglioramento.

[jarrod]

Grazie del tuo svolgimento! io comunque l'ho rifatto in altro modo, leggendo da file, e fino a costruire la lista dei voti mi funziona. Quando faccio l'if che mi avevi spiegato precedentemente (che verifica se i nomi sono uguali), non riesco a capire come potrei puntare esattamente al prezzo della lista nuova, in modo da riuscirci a mettere la somma dei voti che avviene in quel momento..
Questo è il mio programma:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>



typedef struct Voti{
	char nome[20];
	int voto;
}Voti;

typedef struct Medie{
	char nome[20];
	int media;
}Medie;

typedef struct list_elementV{
	Voti value;
	struct list_elementV *next;
}itemV;

typedef itemV* listV;

typedef struct list_elementM{
	Medie value;
	struct list_elementM *next;
}itemM;

typedef itemM* listM;

listV emptylistV(){
	return NULL;
}

listM emptylistM(){
	return NULL;
}
bool emptyV(listV l){	//ho messo void *l e non list l, perchè sto creando due liste
	return (l == NULL);
}

bool emptyM(listM l){
	return (l == NULL);
}

bool isEqual(Voti e1, Medie e2) {
	if (strcmp(e1.nome, e2.nome) == 0){
		return 1;
	}
		
	else return 0;
	
}
Voti copyV(Voti e){
	Voti el;
	el = e;
	return el;
}

Medie copyM(Medie e){
	Medie el;
	el = e;
	return el;
}

Voti headV(listV l){
	if (emptyV(l)) abort();
	else
		return l->value;
}

Medie headM(listM l){
	if (emptyM(l)) abort();
	else
		return l->value;
}

listV tailV(listV l){
	if (emptyV(l)) abort();
	else
		return l->next;
}

listM tailM(listM l){
	if (emptyM(l)) abort();
	else
		return l->next;
}

listV consV(Voti e, listV l) {
	listV t;
	t = (listV)malloc(sizeof(itemV));
	t->value = copyV(e);
	t->next = l;
	return t;
}

listM consM(Medie e, listM l) {
	listM t;
	t = (listM)malloc(sizeof(itemM));
	t->value = copyM(e);
	t->next = l;
	return t;
}

listV insertTailV(Voti e, listV l){
	if (emptyV(l)){
		return consV(e, emptylistV());
	}
	listV root = l;
	listV prev = l;
	
	while (!emptyV(l)){
		prev = l;
		l = tailV(l);
	}
	prev->next = consV(e, emptylistV());
	return root;
}

listM insertTailM(Medie e, listM l){
	if (emptyM(l)){
		return consM(e, emptylistM());
	}
	listM root = l;
	listM prev = l;

	while (!emptyM(l)){
		prev = l;
		l = tailM(l);
	}
	prev->next = consM(e, emptylistM());
	return root;
}
void printelementV(Voti el){
	printf("\n nome: %s, voto: %d ", el.nome, el.voto);
}

void printelementM(Medie el){
	printf("\n nome: %s, media: %d ", el.nome, el.media);
}

void showlistV(listV l){
	printf("Voti:");
	while (!emptyV(l)){
		printelementV(headV(l));
		l = tailV(l);
	}
	printf("\n");
}

void showlistM(listM l){
	printf("Medie:");
	while (!emptyM(l)){
		printelementM(headM(l));
		l = tailM(l);
	}
	printf("\n");
}



int main(){
	listV mylist = emptylistV();		//lista vuota di partenza
	listM mynewlist = emptylistM();
	Voti e1;
	Medie e2;
	int nV = 0;

	
	FILE *f = fopen("persone.txt", "rt");
	while (fscanf(f, "%s %d", &(e1.nome), &(e1.voto)) > 0){
		nV++;
		mylist = insertTailV(e1, mylist);
	}
	showlistV(mylist);
	int votuz;
	for (int i = 0; i < nV; i++){
		if (isEqual(e1, e2)){
			votuz = headV(mylist).voto;
			mynewlist = insertTailM(votuz + headV(mylist).voto, mynewlist)
		}
	}
	


	getchar();
}

mynewlist = insertTailM(votuz + headV(mylist).voto, mynewlist)

questa è la parte di codice dove ho un problema..
in teoria posso fare solo:

mynewlist->value = insertTailM(votuz + headV(mylist).voto, mynewlist)

però io vorrei solo caricare il voto, come faccio?

[apatriarca]

Vorrei solo osservare che non c'è alcun bisogno di aggiungere gli elementi in coda (o testa come sarebbe molto più efficiente e sensato per il tipo di struttura dati) e poi ordinare. E' infatti possibile inserire un elemento direttamente nella posizione che dovrà assumere alla fine dell'ordinamento. Se tutti gli elementi sono inseriti in ordine la lista sarà infatti alla fine già ordinata e non sarà necessario cercare di implementare un algoritmo di ordinamento. Per inserire un elemento in ordine è sufficiente trovare il primo elemento più grande di quello corrente nella lista e inserire l'elemento prima di questo. Spero sia chiaro, non ho molta voglia di scrivere il corrispondente codice..

[Super Squirrel]

Grazie del tuo svolgimento! io comunque l'ho rifatto in altro modo, leggendo da file, e fino a costruire la lista dei voti mi funziona. Quando faccio l'if che mi avevi spiegato precedentemente (che verifica se i nomi sono uguali), non riesco a capire come potrei puntare esattamente al prezzo della lista nuova, in modo da riuscirci a mettere la somma dei voti che avviene in quel momento..

Scusa, ma non ho il tempo di leggere tutto il codice (e tutte quelle funzioni) per inquadrare la situazione e cercare di capire come risolvere il problema.
Come detto giustamente da apatriarca, la seconda lista potrebbe anche essere riempita facendo in modo che risulti già ordinata, anche se ritengo che l'implementazione di un algoritmo di ordinamento per una lista sia un buon esercizio.