PDA

Visualizza la versione completa : [C] Acquisizione e ordinamento di parole


Veon
07-02-2007, 18:56
Innanzi tutto buon giorno a tutti :D

Sono nuovo da queste parti e perdonate se parto subito col chiedere aiuto, ma purtroppo non tutti sono portati per questo genere di cose :cry:

Allora il mio compito è relativamente semplice:

1-Innanzi tutto il programma deve acquisire un determinato numero di parole da un testo (probabilmente solo in minuscolo e senza caratteri speciali) e metterle ognuna in un array.

2-Passare questi array a una funzione di ordinamento.

3-Questa funzione deve decidere, in base al numero di parole, se utilizzare un algoritmo di ordinamento per inserimento o la tradizionale quicksort.

4-In entrambi i casi devo scrivere l'algoritmo di mio pugno, senza usare funzione delle librerie.

5-atto questo stampare le parole in ordine alfabetico.


Allego parte del testo del compito. (L'algoritmo misto di cui parla è quello del punto 3)
http://img174.imageshack.us/img174/4061/img01jq0.jpg

Scusate se come prima richiesta è ambiziosa ma finora me l'ero sempre cavata da solo, ora però mi trovo in difficoltà. :oVVoVe:

Vi ringrazio anticipatamente per l'aiuto. :)

Veon
08-02-2007, 16:19
Non pensavo fosse così difficile anche solo da spiegare..

Va bè mi arrangerò :madai!?:

oregon
08-02-2007, 16:24
Non e' difficile ... magari non si ha il tempo di affrontare il tuo problema da zero ...

Magari, se tu postassi del codice che hai iniziato a scrivere e che non funziona perfettamente, si troverebbe un minuto per darti delle dritte ...

Veon
08-02-2007, 16:36
Avevo iniziato così:



#include <stdio.h>
#include <string.h>
#define M 5
#define N 20

void riempimento(char * vett[][]);
void stampa(char vett[][]);
void ordina(char vett[][]);

int main()
{
char vett[M][N];
riempimento(&vett[0][0]); // inserimento delle stringhe nel vettore
stampa(vett); // stampa del vettore prima dell'ordinamento
ordina(vett);
stampa(vett); // stampa del vettore dopo l'ordinamento
}

void riempimento(char * vett[][])
{
int i;
for(i=0;i<M;i++)
{
printf("Inserire stringa: ");
scanf("%s",vett[i][0]);
}
}

void stampa(char vett[][])
{
int i;
printf("Vettore di stringhe: \n");
for(i=0;i<M;i++)
printf("%s\n",vett[i][0]);
}

void ordina(char vett[][])
{
// Inserire gli algoritmi di ordinamento
}


Però suppongo ci siano parecchi errori di sintassi...
E in ogni caso non credo sia corretto neanche la funzione per acquisire le stringhe (??)

Perchè dovrei acquisir le parole da un unico testo e non parola per parola..

Veon
08-02-2007, 23:05
finora zero aiuti :D

però ho fatto qualcosa con un mio amico
però ho dei problemucci!!

Il programma è questo:



#include<stdio.h>
#include<stdlib.h>
#include<string.h> /* libreria per poter usare le funzioni per la gestione delle stringhe */

#define NUM_STR 8 /* che definisce di quante stringhe è composto il vettore */
#define DIM_STR 20 /* etchetta che definisce la lunghezza massima delle stringhe del vettore */
#define PARTIZIONE 5 /* che definisce la soglia fissata per il cambio di algoritmo di ordinamento */

void inserimento(char array[NUM_STR][DIM_STR]) /*funzione che inserisce nel vettore di stringhe l'imput da tastiera */
/*riceve come parametro solo il l'array e non restituisce nessun parametro */
/*tranne che il vettore tramite indirizzo */
{
int i; /*indice di scorrimento del vettore */

for(i=0;i<NUM_STR;i++) /*ciclo di scorrimento. Parte da 0 e finisce a NUM_STR */

gets(array[i]); /*inserisco nel vettore la stringa in posizione i con l'apposita funzione */
/*che riceve come parametro un 'char *' */
}

void stampa(char array[NUM_STR][DIM_STR]) /*funzione che stampa l'array ordinato. Riceve come parametri in ingresso il */
/*vettore di stringhe. */
{
int s; /*indice di scorrimento del vettore */

for(s=0;s<NUM_STR;s++) /*ciclo di scorrimento. Parte da 0 e finisce a NUM_STR */

puts(array[s]); /*stampo a video la stringa in posizione i con l'apposita funzione */
/*che riceve come parametro un 'const char *' */
}

void inserzione(char array[NUM_STR][DIM_STR],int ileft,int iright) /*Questa funzione contiene l'ordinamento per inserzione. */
/*Come richiesto dal testo, quando le partizioni del quicksort */
/*diventano più piccole della soglia(PARTIZIONE), il quicksort */
/*richiama questa funzione passando gli estremi di ordinamento */
/*e il vettore. */
/*ileft è l'estremo sinistro, mentre iright quello destro. */
{
int i,j; /*indici che servono a scorrere il vettore. */

i=ileft+1; /*poichè il valore di nel for deve partire da 1 e non da 0, */
/*perché bisogna saltare il primo valore, bisogna aumentare di */
/*1 il margine sinistro, in questo caso ileft. */

char x[DIM_STR]; /*una stringa di supporto, che servirà a contenere una stringa */
/*che dovrà essere trasferita in un'altra cella del vettore. */

for(;i<iright;i++) /*ciclo di scorrimento generale del vettore. Finisce quando i */
/*arriva al valore di iright */
{
strcpy(x,array[i]); /*bisogna copiare nella stringa di supporto il contenuto di */
/*array[i] perché verrà modificato nelle successive istruzioni */
/*e non deve andare perso. */

j=i-1; /*la j viene messa a i-1 perché deve controllare tutto il */
/*vettore alla ricerca di una posizione in cui bisogna mettere*/
/*il nuovo elemento.*/

while((j>=0) && (strcmp(x,array[j])<0)) /*1°condizione: una sentinella. non si può andare oltre */
/*l'estremo sinistro della parte di vettore già ordinata. */
/*2°condizione: ricerca del posto in cui mettere il valore */
{
strcpy(array[j+1],array[j]); /*scambio di stringhe. In quesot modo viene trovato lo spazio */
/*posizionare il valore contenuto in x */

j--; /*sentinella decrementata. In questo modo viene aggiornato */
/*il limite dell'estremo sinistro */
}
strcpy(array[j+1],x); /*il valore di x viene messo nella cella del vettore che è */
/*stata liberata. */
}
printf("Ordinamento per inserimento\n");
}

void q_sort(char array[NUM_STR][DIM_STR], int ileft, int iright) /*Questa funzione contiene il corpo dell'ordinamento quicksort */
/*Riceve come parametri gli estremi del vettore, chiamati */
/*ileft e iright. La prima volta che si entra, il primo è a 0, */
/*il secondo a NUM_STR. */
{
int l_hold = ileft; /*questa variabile serve per il ripristino del valore di ileft */
/*così, quando alla fine del programma, ileft dovrà essere */
/*riportata al suo valore iniziale questo non sarà andato */
/*perso */

int r_hold = iright; /*questa variabile serve per il ripristino del valore di */
/*iright così, quando alla fine del programma, iright dovrà */
/*essere riportata al suo valore iniziale questo non sarà */
/*andato perso. */

int aus; /*variabile ausiliaria che conterrà le stringhe da modificare */

char pivot[DIM_STR]; /*questa variabile servirà per contenere il valore della */
/*stringa cardine, quella stringa che servirà da confronto */
/*per tutto il programma */

char t[DIM_STR]; /*variabile ausiliaria che conterrà le stringhe da modificare */

strcpy(pivot,array[ileft]); /*La variabile pivot viene settata con il primo valore del */
/*vettore, almeno la prima volta. Nelle volte successive, */
/*essendo qiesta funzione una funzione ricorsiva, verrà */
/*settata ad un valore diverso ogni volta, un valore */
/*dipendente da ileft. */

while (ileft < iright) /*la condizione controlla che il valore di ileft sia minore */
/*di quello di iright, segno che ci sono ancora valori da */
/*controllare. */
{
while ((strcmp(array[iright],pivot)>=0) && (ileft < iright)) /*in questo while, la variabile iright viene diminuita di */
/*un valore ogni volta che il valore di array[iright] è */
/*maggiore o uguale a quello di pivot e che ileft sia sempre */
/*minore di iright */

iright--; /*diminuzione di iright. */

if (ileft != iright) /*questa condizione viene esaudita quando, nel ciclo */
/*precedente, il loop è terminato non per la seconda */
/*condizione, ma per la prima, segno che i valori sono finiti */
/* e che si è trovato il punto in cui fare lo scambio tra */
/*la variabile puntata da ileft e quella puntata da iright. */

{
strcpy(t,array[ileft]); /*in questo gruppo di istruzioni viene effettuato lo scambio */
strcpy(array[ileft],array[iright]); /*tra le due stringhe, reso possibile dalla presenza della */
strcpy(array[iright], t); /*variabile ausiliaria t; */
ileft++; /*viene aumentata ileft perché adesso il primo valore è stato */
/*controllato e posizionato al posto giusto */
}
while ((strcmp(array[ileft], pivot)<=0) && (ileft < iright)) /*in questo while, la variabile ileft viene aumentata di */
/*un valore ogni volta che il valore di array[ileft] è */
/*mimore o uguale a quello di pivot e che ileft sia sempre */
/*minore di iright */

ileft++; /*aumento di ileft. */

if (ileft != iright) /*questa condizione viene esaudita quando, nel ciclo */
/*precedente, il loop è terminato non per la seconda */
/*condizione, ma per la prima, segno che i valori sono finiti */
/* e che si è trovato il punto in cui fare lo scambio tra */
/*la variabile puntata da iright e quella puntata da ileft. */
{
strcpy(t,array[iright]); /*in questo gruppo di istruzioni viene effettuato lo scambio */
strcpy(array[iright],array[ileft]); /*tra le due stringhe, reso possibile dalla presenza della */
strcpy(array[ileft], t); /*variabile ausiliaria t; */
iright--; /*viene diminuita iright perché adesso il valore è stato */
/*controllato e posizionato al posto giusto */
}
}
strcpy(array[ileft], pivot); /*con questa istruzione sposto i valore che si era deciso di */
/*tenere come pivot al suo posto. Adesso ne verrà scelto un */
/*altro tramite la chiamata ricorsiva. */

strcpy(pivot," "); /*la stringa pivot viene resettata e riempita di spazi. */

aus=ileft; /*viene salvato il valore di ileft */

ileft=l_hold; /*ileft viene resettato al suo valore iniziale, come spiegato */
/*al principio della funzione. */

iright=r_hold; /*iright viene resettato al suo valore iniziale, come spiegato */
/*al principio della funzione. */

if(iright-ileft<PARTIZIONE) /*in questo if viene controllato se la grandezza della */
/*partizione ha raggiunto la soglia. */

inserzione(array,ileft,iright); /*Viene chiamato l'ordinamento di inserzione, come chiesto */
/*dal testo. */

else /*altrimenti */
{
if (ileft < aus) /*viene controllato l'estremo sinistro */

q_sort(array, ileft, aus-1); /*chiamata alla funzione ricorsiva. L'unico parametro che */
/*varia è iright, che assume il valore di aus-1 */

if (iright > aus) /*viene controllato l'estremo destro */

q_sort(array, aus+1, iright); /*chiamata alla funzione ricorsiva. L'unico parametro che */
/*varia è ileft, che assume il valore di aus+1 */
}
printf("Ordinamento Quicksort\n");
}

int main(int argc, char *argv[]) /*inizio del corpo main del programma. I parametri che */
/*riceve sono opzionali e possono essere tolti. */
{
char array[NUM_STR][DIM_STR]; /*viene definito il vettore di stringhe, contenente NUM_STR */
/*stringhe di grandezza DIM_STR. */

inserimento(array); /*si richiama la funzione di inserimento. Come si vede nel */
/*corpo della funzione, riceve un solo parametro ma non */
/*ritorna niente tramite return. */

q_sort(array,0,NUM_STR); /*chiamata alla funzione di ordinamento. Riceve come */
/*parametri il vettore e i due estremi che, nel primo caso, */
/*sono uno a 0, che è l'inizio del vettore, l'altro a NUM_STR, */
/*che è il massimo. */

stampa(array); /*chiamata alla funzione di stampa. Riceve un solo parametro. */

system("pause"); /*chiamata alle funzionalità DOS, che attende la pressione di */
/*un tasto prima di terminare il programma.ù */

return 0; /*poiché si è scelto di definire il main come int, viene */
/*ritornato il valore di default(0) a windows. */

} /*end ordinamento. */



Ci sono alcuni problemi:
1-Non so come fare per fare in modo che il programma smetta la lettura se incontra il acrattere * a prescindere da quante parole inserisca.
2-Se metto un numero di stringhe dispari me ne mangia una al momento della stampa.
3-Non capisco che ordinamento usa perchè printa entrambi o a volte più volte gli stessi. (Li usa entrambi?? ho sbagliato a inseritre il printf??)

Speriamo di risolvere..

matematiko{gabr
09-02-2007, 16:48
ma questo assomiglia al mio stesso compito :D



auhauhauhauhahuahuuhahuahuauhahuahua :zizi:

io sono fermo e non so dove andare a parare.....

questa è la mia realizzazione.



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

# define N 10
# define L 15

struct parolario {char parola [L];
}dizionario [N];

void minuscolo( char stringa[] )
{ int ln, i;
ln = strlen(stringa);
for( i=0; i<ln; i++ )
if( stringa[i]>='A' && stringa[i]<='Z' )
stringa[i] = stringa[i] + 32;
};

void leggi ()
{ int i=0;
char c [L];
do {scanf("%s", & c);
minuscolo(c);
strcpy( dizionario [i].parola, c );
i++;
}while ( 0!=strcmp(c,"*") && i<=N );
};

void stampa( int a, int b )
{ int i;
for( i=a; i<b; i++ )
printf("\n\n%d) %s", (i+1), dizionario[i].parola);
};

void inverti( char stringa1[], char stringa2[] )
{ char app[L];
strcpy(app,stringa1);
strcpy(stringa1,stringa2);
strcpy(stringa2,app);
};

void insert( struct parolario dizionario[], int a, int b )
{ int punt;
punt = a+1;
do{ if( 0<strcmp(dizionario[punt-1].parola,dizionario[punt].parola) )
{ inverti(dizionario[punt-1].parola,dizionario[punt].parola);
punt--;
if( punt == 0 ) punt = 1; }
else punt++;
}while( punt<=b );
};


void quicksort( struct parolario dizionario[], int a, int b )
{ char pivot[L];
char vocabolo[L];
int i, j;
if( a<b )
{ strcpy(pivot,dizionario[b-1].parola);
//printf("\n\n%s", pivot);
i = a;
j = b;
while( i<= j )
{ while(( i<=b )&&( strcmp(dizionario[i].parola,pivot)<0 )) i++;
while( 0<strcmp(dizionario[j].parola,pivot) ) j--;
if( i<j )
{ inverti(dizionario[i].parola,dizionario[j].parola);
i++;
j--; };
};
if( i<= b )
{ quicksort( dizionario, a, j );
quicksort( dizionario, i, b ); }
else quicksort( dizionario, a, b-1 );
};
};

/*void ordina( parole dizionario[] )
{ quicksort();
insert();
};
*/

/*void quicksort( struct parolario dizionario[], int a, int b )
{ int i, j;
char* x;
char vocabolo[L];
i = a;
j = b;
x = & dizionario[N/2].parola;
do{ while( strcmp(dizionario[i].parola,x)<0 && i<b ) i++;
while( strcmp(dizionario[j].parola,x)>0 && j<a ) j--;
if( i<=j )
{ inverti(dizionario[i].parola,dizionario[j].parola);
i++;
j--;
};
}while( i<=j );
if( a<j ) quicksort( dizionario, a, j );
if( i<b ) quicksort( dizionario, i, b );
stampa();
};
*/

int main ()
{ leggi ();
//insert(dizionario,0,N-1);
//ordina();
quicksort(dizionario,0,9);
stampa( 0, 9 );
system("pause");
};




non mi funziona il quicksort. Vi prego, sto programma lo devo consegnare entro Lunedì alle 12!

Xaratroom
09-02-2007, 18:07
matematiko{gabr bella la soluzione con lo struct...
Potresti anche fare un vettore di puntatori (char *arr [...]).
Così su 2 piedi :


void Ordina (unsigned int inizio, unsigned int fine)
{
if (inizio > fine)
{
char *fulcro = arr[inizio];
unsigned int s = inizio + 1;
unsigned int r = fine + 1;

while(s < r)
{
if (strcmp (arr[s], fulcro) < 0 )
s++;
else
{
char *tmp = arr[s];
arr[s] = arr[--r];
arr[r] = tmp;
}
}
char *tmp = arr[inizio];
arr[inizio] = arr[--s];
arr[s] = tmp;

Ordina (inizio, s);
Ordina (r, fine);
}
}

matematiko{gabr
09-02-2007, 18:30
grazie, ma dove lo sostituisco? :cry:

matematiko{gabr
10-02-2007, 16:05
finito.
:D :D :D

donato.sciarra
11-02-2007, 00:46
Originariamente inviato da Xaratroom
matematiko{gabr bella la soluzione con lo struct...
Potresti anche fare un vettore di puntatori (char *arr [...]).


quoto !
cosi diventa un tantino piu flessibile. . .

Loading