[C] che ne pensate di questo compito?

[carro bestiame]

Ditemi un pò come vi sembra. Per me è NON molto banale. Gli argomenti sono stati senz'altro fatti, ma con queste complicazioni tipo passare liste per riferimento no...cmq ditemi un pò la vostra. Faccio un liceo PNI informatica e in quest'ultimo anno ci siamo cimentati nel C++. Le funzioni che vedete scritte un pò sulla sinistra erano richieste a noi...
insomma si capisce ove doveva agire lo studente pèerché vi è esplicitamente detto. Ovviamente si doveva solo completare un programma già dato, cmq tutte quelle funzioni in basso + l'implementazione nel corpo del programma erano richieste allo studente.
------------------------------------------------------------------------ ------------
/************

Il programma carica in due liste (l1 ed l2) una sequenza di interi forniti da un
file il cui nome è fornito dall'utente da linea di comando. Gli elementi dispari
letti dal file vengono inseriti nella lista l1 mentre i pari nella lista l2.
L'inserimento degli elementi nelle due liste viene effettuato in testa.

Successivamente ogni lista viene controllata per verificare se è ordinata in
ordine crescente.

Si carica in ordine un albero binario con il valore assoluto degli elementi
della prima lista (se entrambe le liste sono ordinate o nessuna delle due liste
è ordinata) o della seconda lista (se una soltanto delle due liste è ordinata).

Si calcola la somma dei valori di tutte le foglie dell'albero.

Si riempe una matrice MxN, dove M e N sono rispettivamenta il numero di elementi
della lista l1 e della lista l2 e l'elemento di posizione [j] della matrice
è ottenuto come somma dell'elemento i-esimo della lista l1, dell'elemento
j-esimo della lista l2 e della somma delle foglie dell'albero precedentemente
calcolato.

Infine, si salva la matrice in un file il cui nome è fornito da linea di comando
dall'utente.


------------------------------------------------------------------------ --------

Scrivere il prototipo e il corpo delle seguenti funzioni:

- Carica_liste: la funzione carica due liste (l1 e l2) prendendo gli elementi
da un file il cui nome è fornito dall'utente da linea di
comando. Gli elementi dispari letti dal file vengono inseriti
nella lista l1 mentre i pari nella lista l2. L'inserimento
degli elementi nella lista deve essere effettuato in testa.

- Se_Ordinata: la funzione restituisce un valore intero positivo se la lista
è ordinata in ordine crescente, altrimenti restituisce zero.

- Carica_albero: la funzione inserisce in un albero i valori assoluti degli
elementi di una lista.

- Somma_foglie_albero: la funzione calcola la somma dei valori di tutte le
foglie di un albero.

- Carica_matrice:la funzione riempe una matrice MxN, dove M e N sono
rispettivamenta il numero di elementi di una lista l1 e di una
lista l2 (entrambe passate come parametro) e l'elemento di
posizione [j] della matrice è ottenuto come somma
dell'elemento i-esimo della lista l1, dell'elemento j-esimo
della lista l2 e di un intero passato come parametro.

- Salva_matrice: salva una matrice in un file il cui nome è fornito da linea di
comando dall'utente.


Si richiede di implementare le funzioni "Carica_albero" e "Somma_foglie_albero"
in maniera ricorsiva.

------------------------------------------------------------------------ --------

ESEMPIO: supponendo che il file contenga i seguenti valori interi:

lista.txt:
2 -2 4 -3 6 12 -23 12 0 9 1 3


allora a valle dell'inserimento in testa i valori nelle liste saranno nel
seguente ordine:

lista l1:
3 1 9 -23 -3

lista l2:
0 12 12 6 4 -2 2

Per lista l1 la risposta della funzione Se_Ordinata sarà:
La lista 1 non e' ordinata crescente

e per lista l2:
La lista 2 non è ordinata crescente

Nell'albero verranno caricati i seguenti valori:

3
/ \
1 9
\ \
3 23

Il valore della somma delle foglie dell'albero sarà: 26

I valori caricati nella matrice saranno:
29 41 41 35 33 27 31
27 39 39 33 31 25 29
35 47 47 41 39 33 37
3 15 15 9 7 1 5
23 35 35 29 27 21 25

NON E' CONSENTITO MODIFICARE IL CODICE FORNITO

*************/

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

#define MAXDIM 100

struct Tag_Nodo
{
int Info;
struct Tag_Nodo *Next;
};

typedef struct Tag_Nodo Tipo_Nodo;
typedef Tipo_Nodo *Tipo_Lista;


struct Tag_Nodo_Albero
{
int Info;
struct Tag_Nodo_Albero *Right;
struct Tag_Nodo_Albero *Left;
};

typedef struct Tag_Nodo_Albero Tipo_Nodo_Albero;
typedef Tipo_Nodo_Albero *Tipo_Albero;



//PROTOTIPI DELLE FUNZIONI
Tipo_Lista Inserisci_in_Testa(Tipo_Lista l, int value);
void Print_List(Tipo_Lista l);
Tipo_Albero Insert_Albero(Tipo_Albero t,int value);
void Print_Tree(Tipo_Albero t);


//INSERIRE QUI I PROTOTIPI DELLE FUNZIONI RICHIESTE
void Carica_liste(Tipo_Lista *l1, Tipo_Lista *l2);
Tipo_Albero Carica_albero(Tipo_Albero t, Tipo_Lista l);
int Se_Ordinata(Tipo_Lista l);
int Somma_foglie_albero(Tipo_Albero t);
void Carica_matrice(int x[MAXDIM][MAXDIM], Tipo_Lista l1, Tipo_Lista l2, int s, int *r, int *c);
void Salva_matrice(int x[MAXDIM][MAXDIM], int r, int c);



main()
{
Tipo_Lista l1 = NULL;
Tipo_Lista l2 = NULL;
Tipo_Albero t = NULL;

int cresc1,cresc2;
int somma_f;
int matrice[MAXDIM][MAXDIM],rig,col;

//Inserire qui la chiamata alla funzione "Carica_liste"
Carica_liste(&l1, &l2);


printf("\nLista iniziale 1:\n");
Print_List(l1);
printf("\n");

printf("\nLista iniziale 2:\n");
Print_List(l2);
printf("\n");

//Inserire qui le chiamate alla funzione "Se_Ordinata" per controllare quali
//delle due liste è ordinata
cresc1=Se_Ordinata(l1);
cresc2=Se_Ordinata(l2);

if(cresc1)
printf("La lista 1 e' ordinata crescente\n");
else
printf("La lista 1 non e' ordinata crescente\n");

if(cresc2)
printf("La lista 2 e' ordinata crescente\n");
else
printf("La lista 2 non e' ordinata crescente\n");


//Inserire qui la chiamata alla funzione "Carica_albero"
if((cresc1&&cresc2)||((!cresc1)&&(!cresc2)))
t=Carica_albero(t,l1);
else
t=Carica_albero(t,l2);

printf("\nAlbero:\n");
Print_Tree(t);
printf("\n");


//Inserire qui la chiamata alla funzione "Somma_foglie_albero"
somma_f = Somma_foglie_albero(t);

printf("\nLa somma delle foglie dell'albero e':\n%d\n", somma_f);

//Inserire qui la chiamata alla funzione "Carica_matrice"
Carica_matrice(matrice,l1,l2,somma_f,&rig,&col);

//Inserire qui la chiamata alla funzione "Salva_matrice"
Salva_matrice(matrice,rig,col);

system("PAUSE");
}


Tipo_Lista Inserisci_in_Testa(Tipo_Lista l, int New_Value)
{
Tipo_Lista k;

k=(Tipo_Lista)malloc(sizeof *k);
k->Info=New_Value;
k->Next=l;
return k;
}


void Print_List(Tipo_Lista l)
{
while (l != NULL)
{
printf("%d ", l->Info);
l = l->Next;
}
}


Tipo_Albero Insert_Albero(Tipo_Albero t,int value)
{
Tipo_Albero Temp;

if(t==NULL)
{
//InserimentoinTesta.
Temp=(Tipo_Albero)malloc(sizeof(Tipo_Nodo_Albero));
if(Temp==NULL)
{
printf("Errore di allocazione.");
exit(1);
}
Temp->Right=Temp->Left=NULL;
Temp->Info=value;
return Temp;
}
else if (value<=t->Info)
{
//Inserimento nel Sotto Albero Sinistro
t->Left=Insert_Albero(t->Left,value);
return t;
}
else
{
//Inserimento nel Sotto Albero Destro
t->Right=Insert_Albero(t->Right,value);
return t;
}
}

void Print_Tree(Tipo_Albero t)
{
if(t!=NULL)
{
Print_Tree(t->Left);
printf("%d\n",t->Info);
Print_Tree(t->Right);
}
}


//INSERIRE IL CORPO DELLE FUNZIONI QUI

• void Carica_liste(Tipo_Lista *l1, Tipo_Lista *l2)
  {
  int val;
  char nomefile[30];
  Tipo_Lista l=NULL;
  FILE *f;
  
  printf("Digitare il nome del file: ");
  scanf("%s",nomefile);
  if((f=fopen(nomefile,"r"))==NULL){
  printf("Errore apertura file!\n");
  exit(0);
  }
  while(fscanf(f,"%d",&val)!=EOF)
  if(val%2)
  *l1=Inserisci_in_Testa(*l1,val);
  else
  *l2=Inserisci_in_Testa(*l2,val);
  fclose(f);
  }
  
  Tipo_Albero Carica_albero(Tipo_Albero t, Tipo_Lista l)
  {
  if (l==NULL)
  return t;
  else
  if ((l->Info)>0)
  t=Insert_Albero(t,l->Info);
  else
  t=Insert_Albero(t,-l->Info);
  if (l->Next!=NULL)
  t=Carica_albero(t,l->Next);
  return t;
  }
  
  int Se_Ordinata(Tipo_Lista l)
  {
  Tipo_Lista Prec = NULL;
  Tipo_Lista Succ = l;
  int cresc=1;
  int value_prec=-1;
  
  while ( (Succ != NULL) && cresc )
  {
  if (Succ->Info>value_prec)
  cresc=1;
  else
  cresc=0;
  value_prec=Succ->Info;
  Prec = Succ;
  Succ = Succ->Next;
  }
  return cresc;
  
  }
  
  int Somma_foglie_albero(Tipo_Albero t)
  {
  if (t==NULL)
  return 0;
  else if ((!t->Right) && (!t->Left))
  return t->Info;
  else
  return Somma_foglie_albero(t->Left)+Somma_foglie_albero(t->Right);
  }
  
  void Carica_matrice(int x[MAXDIM][MAXDIM], Tipo_Lista l1, Tipo_Lista l2, int s, int *r, int *c)
  {
  int i,j;
  int lis1[MAXDIM],lis2[MAXDIM];
  
  *r=*c=0;
  while (l1 != NULL){
  lis1[*r]=l1->Info;
  (*r)++;
  l1 = l1->Next;
  }
  while (l2 != NULL){
  lis2[*c]=l2->Info;
  (*c)++;
  l2 = l2->Next;
  }
  for(i=0; i<*r; i++)
  for(j=0; j<*c; j++)
  x[j]=s+lis1+lis2[j];
  }
  
  void Salva_matrice(int x[MAXDIM][MAXDIM], int r, int c)
  {
  char nomefile[30];
  FILE *f;
  int i,j;
  
  printf("Digitare il nome del file: ");
  scanf("%s",nomefile);
  if((f=fopen(nomefile,"w"))==NULL){
  printf("Errore apertura file!\n");
  exit(0);
  }
  for(i=0; i<r; i++){
  for(j=0; j<c; j++)
  fprintf(f, "%d\t", x[j]);
  fprintf(f, "\n");
  }
  fclose(f);
  }

[MindFlyer]

Mah, onestamente non vedo delle grandi difficoltà nel fare delle operazioni banali su liste ed alberi. Anche il passaggio di liste per riferimento non mi sembra richiedere dei grandi balzi concettuali: basta passare il puntatore alla lista, esattamente come per qualunque altra cosa.

[snagg]

beh se avete fatto le liste e gli alberi allora non risulta nulla di complesso . più che altro potrebbe essere scritto molto meglio , ah è inutile che insegnino a trattare con alberi se poi non dicono che usare scanf fa male ed ad ottimizzare ottimizzare quello che scrivete evitando maree di righe inutili se non dannose

[MindFlyer]

snagg, non so che competenze informatiche tu abbia (probabilmente molto più profonde delle mie), ma mi pare che tu stia trascurando il fatto che quel compito riguardava l'algoritmica, e non l'ottimizzazione di codice C sotto un qualche specifico compilatore.
Un corso per Licei di programmazione dovrebbe insegnare a migliorare il tempo asintotico di un algoritmo, e non a migliorarlo di un fattore costante "usando solo le funzioni di libreria fighe" ed "evitando una riga inutile".

[snagg]

posto che credo che tu mind ne abbia più di me (se non per altro per una questione anagrafica). Comunque io penso che a scuola nessuno ti dovrebbe insegnare come rendere il tempo di un algoritmo O(1) per un motivo fondamentale perchè non ti compete e perchè spesso non compete neanche loro, non si possono improvvisare tutti alogirtmisti ti pare?Detto questo quando uno impara a programmare ,IMHO, dovrebbe prima "imparare" e poi "programmare". Ergo se non sai che scanf è deprecata , non si usa e ti può dare seri problemi di sicurezza importa poco che tu riesca a rendere lineare il tempo di esecuzione di un algoritmo. "Premature optimization is the root of alll evil"

[freeware]

snagg io credo che questo programma non corra seri pericoli con la scanf, tantopiu se gli serve di leggere interi..cmq quoto mindflyer perche IMHO l'ottimizzazione si impara con l'esperienza, e a sqola non si impara l'esperienza, ma la matematica o (grasso che cola) informatica quasi seria..
che poi, in un programma del genere 10 righe di meno spostano il tempo di esecuzione medio di diciamo un ms..per curiosita, che cos'è un albero binario?

[snagg]

char nomefile[30];

printf("Digitare il nome del file: ");
scanf("%s",nomefile);
]

da quando questo è un int?

comunque sia circa gli alberi qualche link tipo http://www.di.unipi.it/~andrea/Didattic ... ain.html#2

[MindFlyer]

posto che credo che tu mind ne abbia più di me (se non per altro per una questione anagrafica)

Vergate sul Membro è rinomato per l'Informatica!

[snagg]

già

[carro bestiame]

da quando questo è un int?


[/url]

dicevi? che intendi?

[snagg]

snagg io credo che questo programma non corra seri pericoli con la scanf, tantopiu se gli serve di leggere interi.

mi riferivo a questo in merito alla scanf

[Singollo]

Scusate l'OT e la mia ignoranza, ma Vergate sul Membro esiste davvero??

[MindFlyer]

Certo, nella letteratura goliardica è quasi onnipresente!

[carro bestiame]

snagg io credo che questo programma non corra seri pericoli con la scanf, tantopiu se gli serve di leggere interi.

mi riferivo a questo in merito alla scanf

tu usi cin e cout ? mi pare più elegante usare i puntatori. in ogni caso non abbiamo fatto il discorso della complessità algoritmica perchè esula dal programma quindi non saprei qual è meglio sa questo punto di vista. ci ha cmq detto che l'argomento puntatori fa ragionare di più mentre cin e cout è molto più meccanico


int n;

cin >> n;



int n;

scanf (n, %d);



anzi nel secondo caso, con la scanf, mi pare che il programma sia facilitato a leggere l'intero x' gli si dice anche il tipo


p.s: a questo compito ho preso 8,5 e ho brutalmente cannato una funzione ricorsiva, il resto ho fatto bene... ma quasi tutti, forse perché la ricorsione ce l'hanno spiegata coi piedi o molto più verosimilmente perché sono io idiota

[snagg]

Evidentemente non sono in grado di spiegarmi .. da quando usi un puntatore a char per prendere degli interi scrivendo in output "Immettere il nome del file:" è uno strano metodo di prendere interi non ti pare.. (casomai non si fosse capito il mio umorismo inglese , il problema è nel prendere stringhe con la scanf )
PS , NB : ci sono milioni di modi per prendere interi in input e sarebbe opportuno dire al tuo professore che la testa si può usare in qualunque modo anche facendo un cast ad un puntatore a void perchè si sappia cosa si sta facendo