Ordinamento lista

2 Risposte

• 

  Weierstrass

  Utente Famoso

  Iscritto da

  feb, 2019

  Messaggi:

  2248

  Re: Ordinamento lista

  27 feb 2019, 14:49

  Prova così
  
  se non vuoi prememorizzare il numero di vocali, semplicemente ricalcolale ogni volta prima del sort
  
  ciao
  

  
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <time.h>
  
  struct lista 
  {
  	char c [100];	
  	int id;
  	int vocali;
      	struct lista *next; 
  };
  
  int gestisciMenu() 
  {
  	int n;
  	printf("\n 1 per creare un elemento\n 2 per visualizzare elementi\n 3 per ordinare elementi\n 4 per salvare elementi\n 5 per uscire\n");
  	scanf("%d",&n);
  	return n;
  }
  
  // Aggiunge un elemento alla lista
  void aggiuntaElemento(struct lista **head, struct lista *elemento) {
  
      //nodo usato per attraversare la lista
      struct lista *prec = NULL;
      elemento->next = NULL;
  
      //se lista vuota
      if(*head == NULL){
          *head = elemento;
      }
      //aggiungo in coda
      else{
  		prec = *head;
          while(prec->next) 
              prec = prec->next;
              prec->next = elemento;
      }
  }
  
  struct lista *creaElemento() {
  	char vocali [6] = {'a' , 'e', 'i', 'o', 'u', 'y'};
      char c[100];
      int id = 0;
      struct lista *elemento=NULL;
  	int tot_voc = 0;
  	srand(time(NULL));
  	for (int i = 0; i<sizeof(c)-1; i++){
  		c[i]=('a'+ rand() % 26);
  		for(int k = 0; k < sizeof(vocali); k++) {
  			if(c[i] == vocali[k]){
  				tot_voc++;
  				break;
              }
          }
      }
  	c[sizeof(c)-1]= '\0';
      printf("Elemento aggiunto correttamente\n"); 
      elemento = (lista * )malloc(sizeof(struct lista));
      elemento->id = id;
  	elemento->vocali = tot_voc;
  	strncpy(elemento->c, c, 100);
  
     return elemento;
  }
  
  
  void gestisciAggiunta(struct lista **head) {
  
          struct lista *nuovo=creaElemento();
          aggiuntaElemento(head, nuovo);
  }
  
  
  int stampaLista(struct lista *head){
          int i = 0;
  		while(head != NULL){
  			head->id = i;
  			printf("%d. %s\n", head->id, head->c);
  
  			// Conteggio vocali presenti nella stringa    
  			printf("\tVocali presenti = %d\n", head->vocali);
  			head = head->next;
  			i++;
  		}
      return i;
  }
  
  void salvaFile(struct lista *head) {
      FILE *fp;
      fp = fopen ("buffer.csv", "w");
      while (head!=NULL){
          fprintf(fp, "%d, %s\n", head->id, head->c);
          head = head->next;
          }
      fclose(fp);
  }
  
  
  // Ordina gli elementi della lista con conteggio vocali (ordine decrescente)
  // Algoritmo di bubble sort
  void ordinamento(struct lista **head){
  	struct lista *curr = *head;
  	struct lista *min_value = NULL, *t = NULL;
  	
  	int buff;		//variabile appoggio
  
  	while(curr->next){		//scorro lista accedendo elemento successivo
  		min_value = t = curr->next;
  		while (t != NULL){
  			if(t->vocali < min_value->vocali)	//se elemento corrente più piccolo 
  				min_value = t;					//lo metto al valore minimo 
  			t = t->next;						//e continuo a scorrere
  		}
          // algoritmo di bubble sort
  		if(min_value->vocali < curr->vocali){
  			buff = min_value->vocali;
  			min_value->vocali = curr->vocali;
  			curr->vocali = buff;
  		}
  		curr = curr->next;
  	}
  }
  
  int main(void)
  {
  struct lista *head = NULL;
           while (1) {
  
          int menu= gestisciMenu();
  
                  switch (menu) {
  
                  case 1: gestisciAggiunta(&head); 
                  
                  break;
  
                  case 2: stampaLista(head); 
                  break;
  
                  case 3: ordinamento(&head);
                          stampaLista(head); 
                  break;
  		
  		case 4: salvaFile(head);
                          printf("File correttamente salvato\n");
  		break;
  
                  case 5:
                          printf("sei uscito correttamente\n");
                          exit(EXIT_SUCCESS);
                          break;
  
                  default:
                          printf("errore, rinserisci il numero\n");
                          break;
                  }
          }
  
  
  return 0;
  }
  

• 

  Nippolo

  Molto attivo

  Iscritto da

  mar, 2018

  Messaggi:

  1238

  Re: Ordinamento lista

  27 feb 2019, 15:39

  Innanzitutto bisogna ottimizzare e sistemare un po' il codice:
  - dal punto di vista formale, al fine di rendere il codice più chiaro e leggibile, ti consiglio di rispettare la spaziatura e l'indentazione, di racchiudere sempre il corpo (anche se costituito da una sola riga di codice) di un'istruzione di controllo all'interno di parentesi graffe, di evitare tutti quei commenti e spazi bianchi;
  - perchè non utilizzi un typedef per evitare di ripetere ogni volta la parola-chiave struct?
  - per la dimensione delle parole sarebbe meglio definire una costante;
  - la funzione srand() va richiamata una sola volta, quindi il suo posto non è certamente all'interno della funzione creaElemento();
  - per un programma sulle liste concatenate sarebbe auspicabile prevedere una funzione per l'aggiunta di un nuovo elemento sia in testa che in coda. A tal proposito ti faccio notare che la funzione che aggiunge in coda può essere implementata sfruttando la funzione che aggiunge in testa;
  - la funzione gestisciAggiunta() può essere evitata;
  - la funzione stampaLista() si deve limitare a stampare la lista... non vedo il motivo per cui bisogna prima stampare la lista per assegnare gli id e calcolare il numero di vocali;
  - per l'assegnazione degli id potresti per esempio utilizzare una variabile globale;
  - la funzione creaElemento() può essere ampiamente ottimizzata... perchè utilizzare una seconda stringa per poi copiarla con strncpy()? Quale sarebbe l'utilità di memset()?
  
  Alla luce di quanto appena detto io farei qualcosa del genere:

  #include <stdio.h>
  #include <stdlib.h>
  #include <time.h>
  
  #define DIM 30
  
  unsigned int ID = 0;
  
  typedef struct nodo_
  {
  	char c[DIM];
  	unsigned int id;
      struct nodo_ *next;
  }   nodo;
  
  void aggiungi_in_testa(nodo **head, nodo *nuovo)
  {
      if(nuovo)
      {
          nuovo->next = *head;
          *head = nuovo;
      }
  }
  
  void aggiungi_in_coda(nodo **head, nodo *nuovo)
  {
      nodo **temp = head;
      while(*temp)
      {
          temp = &(*temp)->next;
      }
      aggiungi_in_testa(temp, nuovo);
  }
  
  nodo* crea_nuovo_elemento()
  {
      nodo *nuovo = malloc(sizeof(nodo));
      if(nuovo)
      {
          unsigned int i;
          for(i = 0; i < DIM - 1; ++i)
          {
              nuovo->c[i] = ('a' + rand() % 26);
          }
          nuovo->c[i] = '\0';
          nuovo->id = ID++;
      }
      return nuovo;
  }
  
  void stampa_lista(nodo *head)
  {
      while(head)
      {
          printf("%d:\t%s\n", head->id, head->c);
          head = head->next;
      }
  }
  
  int main()
  {
      srand(time(0));
      nodo *head = NULL;
      for(unsigned int i = 0; i < 15; ++i)
      {
          aggiungi_in_coda(&head, crea_nuovo_elemento());
      }
      stampa_lista(head);
      return 0;
  }

  se qualcosa non ti è chiaro chiedi pure.
  
  Detto ciò qual è la tua idea per ordinare la lista?
  Se la struct non può contenere altri membri e non vuoi tenere traccia del numero di vocali della singola stringa, andando un po' a discapito delle prestazioni potresti semplicemente sostituire

  if(min_value->cntVocali < curr->cntVocali)

  con

  if(conta_vocali(min_value->c) < conta_vocali(curr->c))

  dove

  unsigned int conta_vocali(char *str)
  {
      ...
  }

  è una funzione che ritorna il numero di vocali della stringa passata come argomento.