C:STRINGHE

[lucas87]

Non riesco a fare questo esercizio:
Scrivere un programma in C che riceva in input un insieme di parole (stringhe) e produca in output le parole di input ordinate. Esempio:



Input: “Oggi è proprio una bella giornata. Quasi quasi vado al mare.”



Output:

al

bella

è

giornata

mare

Oggi

proprio

Quasi

quasi

una

vado

In piu allocare dinamicamente la memoria per la stringa.

Ecco la mia soluzione:

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

#define MAXWORD 100
#define N 1000

void sort_word(char s[], int );
void swap(char **p, char **q);
void write_word(char s[], int );
int contaparole(char s[], int);
int caricamento(char s[]);

int main(void)
{
char word[MAXWORD];
char s[N];
int n,i,num;

num=contaparole(s,caricamento(s));
if (num>=N)
printf("ERRORE:TROPPE PAROLE");
if (strlen(s)>=MAXWORD)
printf("ERRORE:PAROLA TROPPO LUNGA");
if (calloc(strlen(s)+1,sizeof(char))== NULL)
printf("ERRORE DI CALLOC");


sort_word(s,num);
write_word(s,num);

system("PAUSE");
return 0;
}




void sort_word(char s[], int num){
int i,j;
for (i=0;i<num;++i){
for (j=i+1;j<num;++j){
if (strcmp(s[i],s[j])<0){
swap(&s[i], &s[j]);
}
}
}
}

void swap(char **p, char **q){
char *tmp;
tmp=*p;
*p=*q;
*q=tmp;

}


void write_word(char s[], int num){
int i;
for (i=0;i<num;++i){
printf("%s\n", s[i]);
}
}

int caricamento(char s[]){
int i;
for (i = 0; ;i++){

s[i]=getchar();
if (s[i]=='\n'){
break;
}
}
s[i]='\0';
return i;
}

int contaparole(char s[],int n){
int j;
int k=1;
for(j=0;j<n;j++){
if (s[j]==' '){
k++;
}
}
return k;
}


ma mi da errore a if (strcmp(s[i],s[j])<0).
Chi mi aiuta a risolvere è un genio.
Ringrazio tutti in anticipo.
PS:ho pochissimo tempo per consegnare il rpograma funzionante, ovvero domani.
Se non capite qualcosa nel programma fatemi sapere che ve lo spiego.

[andbin]

Dalla singola stringa iniziale di input dovresti ottenere un array di stringhe .... cosa che non vedo ....
E quindi fare l'ordinamento sull'array di stringhe.

[lucas87]

mhhh, probabilmente si, ma nn so usarlo, se è poco da modificare non è che me lo modificheresti tu?

please

[lucas87]

qualcuno mi aiutiiiii domani devo consegnaro, nn so fare l'array di stringhe!!!!!!!11

[lucas87]

praticamente devo fare l'ordinamento lessicografico di un array di strighe, chi mi aiuta

[andbin]

Ti fornisco qualche indizio utile:

- Un array di stringhe lo dichiari con ad esempio: char *stringhe[30];

- Per "spezzare" la stringa usando gli spazi come delimitatori puoi usare la funzione di libreria strtok(). Ovviamente si può anche fare "a mano" con del codice apposito ma ti consiglio, per semplicità, la strtok().

Se hai altri dubbi, chiedi pure. ;)

[wingman87]

@andbin: funziona ma vorrei sapere se ho scritto del buon codice, me lo puoi controllare? Te lo chiedo xk devo fare le olimpiadi di info, non so se a gennaio o a febbraio, e oltre a scrivere programmi funzionanti bisognerebbe che siano anche scritti bene. Grazie.
#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;

int main(){
char *frase,**parole,*temp;
int np=0,i,j;
frase=(char*)malloc(1);
jump:
cout<<"Inserire frase...\n";
for(i=0;;i++){
frase=(char*)realloc(frase,i+1);
frase[i]=getchar();
if(frase[i]==' ') np++;
else if(frase[i]=='\n'){
frase[i]='\0';
if(i!=0) np++;
break;
}
}
if(np==0) goto jump;
parole=new char*[np];
parole[0]=strtok(frase," ");
for(i=1;i<np;i++)
parole[i]=strtok(NULL," ");
for(i=0;i<np;i++)
for(j=np-1;j>i;j--)
if(strcmp(parole[j],parole[j-1])<0){
temp=parole[j];
parole[j]=parole[j-1];
parole[j-1]=temp;
}
cout<<"Parole ordinate:\n";
for(i=0;i<np;i++)
cout<<parole[i]<<"\n";
system("pause");
}

[andbin]

bisognerebbe che siano anche scritti bene.Posso essere del tutto sincero??? .... Ehm ... il tuo codice è orripilante.

[cionci]

wingman87: lo richiedeva in C, non in un misto C/C++...

[wingman87]

Posso essere del tutto sincero??? .... Ehm ... il tuo codice è orripilante.
Ok, cosa devo fare x migliorarlo?
@cionci: a scuola impariamo il c++, so che una differenza è che il C non è ad oggetti, quindi avrei dovuto non usare la iostream?

[andbin]

Ok, cosa devo fare x migliorarlo?Guarda ... sinteticamente:
- Hai usato roba del C (malloc ad esempio) e roba del C++ (cout e new char*[np] ad esempio). Non è un male grave, però per un esercizietto così, o usi solo cose del C o solo cose del C++.
- Hai usato il goto. :nonsifa:
- Alla fine non hai deallocato quello che è stato allocato.
- Non hai messo un return qualcosa alla fine.
- Non hai testato l'eventuale fallimento delle allocazioni.
- Nella fase di input riallochi il buffer per ogni singolo carattere (inefficiente). Inoltre conti le parole in base al numero di spazi, senza tenere conto che si potrebbero inserire più spazi tra le parole e all'inizio/fine.
- Inoltre come è scritto (tutto appiccicato e senza spaziature) non mi piace. ;)

[cionci]

@andbin: funziona ma vorrei sapere se ho scritto del buon codice, me lo puoi controllare?
Diciamo che te la scrivo in C++ ;)

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

int main()
{
string linea;
vector<string> parole;

getline(cin, linea);

istringstream iss(linea);
while(!iss.eof())
{
string parola;
iss >> parola;
parole.push_back(parola);
}

sort(parole.begin(), parole.end());

for(vector<string>::iterator it = parole.begin(); it != parole.end(); it++)
cout << *it << endl;

return 0;
}

[lucas87]

diciamo che me lo scrivete in C smplice cosi mi risolvete un grande problema?

[cionci]

Guarda...in pratica te l'ha fatto wingman87: prendi il suo sostituisci la scanf alla cin, printf alla cout e la malloc alla new...

[andbin]

Diciamo che te la scrivo in C++ ;)Ah beh ... certo, usando STL è mooooolto facile. :asd:

[lucas87]

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



int main(){
char *frase,**parole,*temp;
int np=0,i,j;

frase=(char*)malloc(1);
jump:
printf("Inserire frase...\n");
for(i=0;;i++){
frase[i]=getchar();
if(frase[i]==' ') np++;
else if(frase[i]=='\n'){
frase[i]='\0';
if(i!=0) np++;
break;
}
}
if(np==0) goto jump;
parole=new char*[np];
parole[0]=strtok(frase," ");
for(i=1;i<np;i++)
parole[i]=strtok(NULL," ");
for(i=0;i<np;i++)
for(j=np-1;j>i;j--)
if(strcmp(parole[j],parole[j-1])<0){
temp=parole[j];
parole[j]=parole[j-1];
parole[j-1]=temp;
}
printf("Parole ordinate:\n");
for(i=0;i<np;i++)
printf("%s\n",parole[i]);
system("pause");
}

eccolo pero non posso usare jump e non so cosa sia strtok. in piu dovrei levare iostream.

che altro devo fare quindi?

[cionci]

Per sostituire il goto (che non va mai usato tranne in rarissimi casi, anzi scordatevi che esiste)...

if(np > 0)
{
parole=new char*[np];
parole[0]=strtok(frase," ");
for(i=1;i<np;i++)
parole[i]=strtok(NULL," ");
for(i=0;i<np;i++)
for(j=np-1;j>i;j--)
if(strcmp(parole[j],parole[j-1])<0){
temp=parole[j];
parole[j]=parole[j-1];
parole[j-1]=temp;
}
printf("Parole ordinate:\n");
for(i=0;i<np;i++)
printf("%s\n",parole[i]);
}
system("pause");

La strtok o string tokenizer è una funzione molto potente, ma anche abbastanza complessa...è probabilmente la più complessa della libreria standard... Sommariamente serve per dividere una stringa in vari pezzi sostituendo il carattere di fine stringa alla prima occorrenza del carattere cercato (in questo caso lo spazio)...
http://www.cplusplus.com/ref/cstring/strtok.html

[lucas87]

ecco penso che adesso l'ho aggiustato ed è puro c, piu leggibile con funzioni:


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

int caricamento(char *frase);
void ordinamento(char **parole, int );
void swap(char **p, char **q);
void stampa(char **parole, int );

int main(){
char *frase,**parole,*temp;
int np,i,j;

frase=(char*)malloc(1);
if (frase== NULL)
printf("ERRORE DI ALLOCAZIONE DI MEMORIA");

np=caricamento(frase);

if (np>0){
parole=new char*[np];
parole[0]=strtok(frase," ");
for(i=1;i<np;i++)
parole[i]=strtok(NULL," ");

ordinamento(parole,np);
stampa(parole,np);
}else printf("non hai inserito nulla\n");
system("pause");
}

int caricamento(char *frase){
int i,np=0;

printf("Inserire frase...\n");
for(i=0;;i++){
frase[i]=getchar();
if(frase[i]==' ') np++;
else if(frase[i]=='\n'){
frase[i]='\0';
if(i!=0) np++;
break;
}
}
return np;
}


void ordinamento(char **parole, int np){
int i,j;
for (i=0;i<np;++i){
for (j=i+1;j<np;++j){
if (strcmp(parole[i],parole[j])>0){
swap(&parole[i], &parole[j]);
}
}
}

}

void swap(char **p, char **q){
char *temp;
temp=*p;
*p=*q;
*q=temp;
}

void stampa(char **parole, int np){
int i;
printf("Parole ordinate:\n");
for(i=0;i<np;i++)
printf("%s\n",parole[i]);
}




ora dovrò sostituire l'ordinamento, in quanto l'esercio non chiede un ordinamento in generale, ma margesort. chia ha qualche idea mi facci sapere.

[lucas87]

ok a quanto pare ho sottovalutato mergesort, è piu difficile di quanto credessi. chi mida una mano??

[trallallero]

ok a quanto pare ho sottovalutato mergesort, è piu difficile di quanto credessi. chi mida una mano??
a parte che potresti scegliere se usare il C o il C++ quindi malloc O new ;)
e poi questa:
frase = (char *) malloc(1);
non ho seguito il programma ma vedo che allochi 1 (UNO) byte di memoria ...
stai usando una cella di memoria per la getchar, secondo me é inutile.
L'allocazione dinamica si usa di solito quando non sai quanta memoria ti servirá ed in certi casi se sai che sará una sola parola conviene comunque una variabile automatica tipo char parola[256];
tanto non esiste una parola cosí lunga. Ce ne stanno 10 ;)
Sull'ordinamento ci vuole un po di tempo per controllare ... ma mi sembra che hai fatto un pó di casini pure nella creazione della matrice :D

EDIT: :eekk: non avevo visto il ciclo dove usi "frase" :eek:
allochi 1 e poi sfori di brutto! non ti si inchioda il programma ?

[lucas87]

gira sempre, pero poi logicamente è scorretto, non è che me lo risolveresti tu questo problema di allocazione e se sei in grado di farlo magari anche l'ordinamente con mergesort ricorsiva che nn mi reisce.


fammmi sapere

[trallallero]

gira sempre, pero poi logicamente è scorretto, non è che me lo risolveresti tu questo problema di allocazione e se sei in grado di farlo magari anche l'ordinamente con mergesort ricorsiva che nn mi reisce.


fammmi sapere
oggi no. Mi spiace ma ho problemi ben più gravi tipo cercare lavoro. Domani se non ti aiuta qualcun altro te lo dovrei riuscire a fare ma non prometto nulla.
Per allocare la matrice comunque devi prima allocare una lista di puntatori (la Y) e poi per ogni puntatore devi allocare l'array. So che non è facile ma è un pò lungo da spiegare ...

[wingman87]

Guarda ... sinteticamente:
- Hai usato roba del C (malloc ad esempio) e roba del C++ (cout e new char*[np] ad esempio). Non è un male grave, però per un esercizietto così, o usi solo cose del C o solo cose del C++.
- Hai usato il goto. :nonsifa:
- Alla fine non hai deallocato quello che è stato allocato.
- Non hai messo un return qualcosa alla fine.
- Non hai testato l'eventuale fallimento delle allocazioni.
- Nella fase di input riallochi il buffer per ogni singolo carattere (inefficiente). Inoltre conti le parole in base al numero di spazi, senza tenere conto che si potrebbero inserire più spazi tra le parole e all'inizio/fine.
- Inoltre come è scritto (tutto appiccicato e senza spaziature) non mi piace. ;)
1- ok
2- l'avevo messo all'inizio xk nn avevo voglia di fare un ciclo while, era x fare + in fretta, poi m sn dimenticato di toglierlo, cmq giusta osservazione.
3- giustissimo, me ne sn dimenticato
4- non lo mette automaticamente il compilatore?
5- a questo non avrei mai pensato, grazie
6- è inefficiente per i tempi o per la frammentazione? Xk lo avrei fatto diversamente ma volevo seguire la specifica di allocare la memoria dinamicamente, c'è un modo migliore x farlo? Cmq il problema dei tanti spazi l'ho risolto dopo aver postato..
7- intendi una riga vuota tra un blocco e l'altro?
Cmq grazie.

[trallallero]

gira sempre, pero poi logicamente è scorretto, non è che me lo risolveresti tu questo problema di allocazione e se sei in grado di farlo magari anche l'ordinamente con mergesort ricorsiva che nn mi reisce.


fammmi sapere
1° Lezione: allocazione matrice :D


void Alloca()
{
char **mat; // ARRAY DI PUNTATORI
int y; // INIDCE PER ALLOCARE LA LISTA DI STRINGHE

// ALLOCO UNA LISTA DI PUNTATORI
mat = (char **)malloc(10 * sizeof(char *));
if (!mat)
puts("errore alloc 1"), exit(1);

// PER OGNI PUNTATORE ALLOCO UNA STRINGA DI 128
for ( y = 0; y < 10; y++ )
{
mat[y] = (char *)malloc(128 * sizeof(char));
if (!mat[y])
puts("errore alloc 2"), exit(1);

// AZZERO LA MEMORIA ALLOCATA (CONVIENE SEMPRE)
memset( mat[y], 0, 128 * sizeof(char) );
}

// PER TESTARE SE FUNZIONA
for ( y = 0; y < 10; y++ )
{
sprintf( mat[y], "stringa_%i", y );
puts(mat[y]);
}

// LIBERO LE 10 STRINGHE
for ( y = 0; y < 10; y++ )
free(mat[y]);

// LIBERO LA LISTA DI PUNTATORI
free(mat);
}

il concetto è semplice:
alloco una lista di puntatori a char e sarebbe la Y della matrice. Poi per ogni Y alloco una stringa di 128 chars e la azzero perchè in C conviene sempre azzerare tutto visto che le stringhe sono terminate coi tappi (0).
Per l'ordinamento ti lascio un pò di tempo forse conviene che tu capisca bene la allocazione prima ;)
Ovviamente la allocazione è locale alla funzione quindi il tutto avviene all'interno di essa. Se la chiami, quando esci dalla funzione la matrice non esiste più.
Spero di esserti stato d'aiuto :)

[andbin]

Ecco un valido esempio per spezzare una stringa e allocare al tempo stesso l'array delle stringhe in modo efficiente.
Enjoy. :)

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

char** split_words (char *str, int *psizeout)
{
char **arr = NULL, **newarr;
char *ptr;
int size = 0, capacity = 0;

ptr = strtok (str, " \t");

while (ptr != NULL)
{
if (size >= capacity)
{
capacity = size + 32;

newarr = (char**) realloc (arr, capacity * sizeof (char*));

if (newarr == NULL)
{
free (arr);
arr = NULL;
break;
}

arr = newarr;
}

arr[size++] = ptr;

ptr = strtok (NULL, " \t");
}

if (arr)
*psizeout = size;

return arr;
}


int main (void)
{
char buf[] = "Ciao, questa e` una \t stringa da spezzare";
char **arr;
int size, i;

if ((arr = split_words (buf, &size)) != NULL)
{
for (i = 0; i < size; i++)
printf ("%s\n", arr[i]);

free (arr);
}

return 0;
}

[lucas87]

E' da stamattina che provo a farlo funzionare ma niente, allora vi posto il programma funzionante, con bubblesort e l'allocazione della memoria logicamente scorretta, ma nn si sa perchè funzionante e vi chiedo se me la potete allocare bene(senza altri esempi di programmi tanto nn gli riesco ad aggiungere al mio) e magari sostituire bubblesort con mergesort che è un altra cosa che provo a fare da 1 giorno ma che non va.
Se me lo fate vi ringrazio, altrimenti grazie lo stesso per il tempo datomi.



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

int caricamento(char *frase);
void ordinamento(char **parole, int );
void swap(char **p, char **q);
void stampa(char **parole, int );

int main(){
char *frase,**parole,*temp;
int np,i,j;

frase=(char*)malloc(1);
if (frase== NULL)
printf("ERRORE DI ALLOCAZIONE DI MEMORIA");

/*np= numero parole della frase*/
np=caricamento(frase);

if (np>0){
/*serve per dividere una stringa in vari pezzi sostituendo il carattere di fine
stringa alla prima occorrenza del carattere cercato (in questo caso lo spazio)*/

parole=new char*[np];
parole[0]=strtok(frase," ");
for(i=1;i<np;i++)
parole[i]=strtok(NULL," ");
/*fine suddivisione stringa*/

ordinamento(parole,np);
stampa(parole,np);
}else printf("non hai inserito nulla\n");
system("pause");
}

int caricamento(char *frase){
int i,np=0;

printf("Inserire frase...\n");
for(i=0;;i++){
frase[i]=getchar();
if(frase[i]==' ') np++;
else if(frase[i]=='\n'){
frase[i]='\0';
if(i!=0) np++;
break;
}
}
return np;
}


void ordinamento(char **parole, int np){
int i,j;
for (i=0;i<np;++i){
for (j=i+1;j<np;++j){
if (strcmp(parole[i],parole[j])>0){
swap(&parole[i], &parole[j]);
}
}
}

}

void swap(char **p, char **q){
char *temp;
temp=*p;
*p=*q;
*q=temp;
}

void stampa(char **parole, int np){
int i;
printf("Parole ordinate:\n");
for (i=0;i<np;i++)
printf("%s\n",parole[i]);
}

[trallallero]

scusa luca ma perchè non provi da solo, magari una cosa alla volta ?
hai 2 esempi, io ho anche commentato mettendomi nei tuoi panni ...
se sei alle prime armi insisto: fai una cosa alla volta, comincia col capire bene l'allocazione memoria, lavorare sulle stringhe splittandole come t'ha fatto vedere andbin, poi passi all'ordinamento.
Tu di colpo vuoi fare allocazione/ordinamento/ricorsione :eek: matto! :D

EDIT: e poi non mi sembra tu segua i nostri consigli :nonsifa:
frase continui ad allocarla (1) quando poi la usi come se fosse un array ...

[lucas87]

sto provando da 2 giorni e domani devo inviarlo al prof per la consegna.
Non è che alloco sempre 1, è che ho postato l'ultima versione funzionante, anche se logicamente scorretta e cmq ci sto provando da 10 ore, l'allocazione nn va, allora penso vabbe il prog pare che va lo stesso proviamo merge sort, e merge sort non va. non va niente.Ci voglio lavorare ma usando tutti gli esempi che mi avete dato e vi ringrazio per quest non ci riesco lo stesso, dato pero che devo consegnarlo alla svelta volevo farmi dare una grande mano e farmi completare il programma.

[trallallero]

a che ora lo devi consegnare ?
di domenica ? :mbe:
io adesso ho da fare devo uscire ma se non t'aiuta nessun altro magari o stasera o domani mattina ti posso aiutare ;)

[lucas87]

Ho tempo fino a domani pomeriggio alle 16:00

[andbin]

sto provando da 2 giorni e domani devo inviarlo al prof per la consegna.
Non è che alloco sempre 1, è che ho postato l'ultima versione funzionante, anche se logicamente scorretta e cmq ci sto provando da 10 ore, l'allocazione nn va, allora penso vabbe il prog pare che va lo stesso proviamo merge sort, e merge sort non va. non va niente.Ci voglio lavorare ma usando tutti gli esempi che mi avete dato e vi ringrazio per quest non ci riesco lo stesso, dato pero che devo consegnarlo alla svelta volevo farmi dare una grande mano e farmi completare il programma.Lo so che non è facile se si è alle "prime armi" ... ma devi anche sforzarti un pochino per cercare di adattare e utilizzare gli esempi e i consigli che ti sono stati forniti.

Io personalmente ti posso consigliare di scrivere 3/4 funzioni separate ognuna con un compito ben preciso:

- Una funzione che legge una stringa in input e il cui buffer è gestito/allocato dinamicamente.
Una idea sarebbe quella di allocare un grosso buffer e usare la funzione fgets() per leggere di botto l'intera riga. Si può anche fare leggendo i singoli caratteri con getchar() e riallocare man mano il buffer. Puoi decidere di riallocare il buffer ad ogni carattere (inefficiente) oppure riallocare il buffer a blocchi (più o meno come nel mio esempio per lo split). A te la scelta.

- Una funzione che data una stringa, la spezza per ottenere/allocare un array di stringhe (vedi il mio esempio che è sicuramente eloquente).

- Una funzione per fare l'ordinamento delle stringhe.

- Una funzione per la stampa delle stringhe (ma puoi integrarla anche nel main).

[lucas87]

ecco qui, ho fatto una funzione apposita per la divisione delle parole e ho inserito l'allocazione anche se poco efficinete non fa niente va bene cosi nella funzione di caricamento. risultato: il programma non va.(crasha)

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




int caricamento(char *frase);
void ordinamento(char **parole, int );
void swap(char **p, char **q);
void stampa(char **parole, int );
void divisione(char **parole, char *frase, int);

int main(){
char *frase,**parole;
int np,i,j;

np=caricamento(frase);

if (np>0){

divisione(parole,frase,np);
ordinamento(parole,np);
stampa(parole,np);
}else printf("non hai inserito nulla\n");
system("pause");
}

int caricamento(char *frase){
int i,np=0;
frase=(char*)malloc(1);
if (frase==NULL){
printf("ERRORE DI ALLOCAZIONE");
} else {
printf("Inserire frase...\n");
for(i=0;;i++){
frase=(char*)realloc(frase,i+1);
frase[i]=getchar();
if(frase[i]==' ') np++;
else if(frase[i]=='\n'){
frase[i]='\0';
if(i!=0) np++;
break;
}
}
}
return np;
}


void ordinamento(char **parole, int dim){
int i,j;
for (i=0;i<dim;++i){
for (j=i+1;j<dim;++j){
if (strcmp(parole[i],parole[j])>0){
swap(&parole[i], &parole[j]);
}
}
}

}

void swap(char **p, char **q){
char *temp;
temp=*p;
*p=*q;
*q=temp;
}

void stampa(char **parole, int dim){
int i;
printf("Parole ordinate:\n");
for (i=0;i<dim;i++)
printf("%s\n",parole[i]);
}

void divisione(char **parole,char *frase,int np){
int i;
parole=new char*[np];
parole[0]=strtok(frase," ");
for(i=1;i<np;i++)
parole[i]=strtok(NULL," ");
}

[lucas87]

PS:IL PROBLEMA SEMBRA ESSERE NELLA DIVIONE DELLE PAROLE

[lucas87]

rettifica: il problema stava nel fatto che sembra che caricamento allocazione e divisione è meglio farli nel main, come funzioni farò solo ordinamento, che pero questo che ora posto è bubblesort e a me serve mergesort, ma mi serve una buon anima che mi da gia il codice bello e fatto perche gia ho provato con mergesort per molto tempo ma non ha mai funzionato.



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

void ordinamento(char **parole, int );
void swap(char **p, char **q);

int main(){
char *frase,**parole;
int np=0,i,j;
frase=(char*)malloc(1);

if (frase==NULL){
printf("ERRORE PROBLEMA DI ALLOCAZIONE");
}
else{
printf("Inserire frase...\n");
for(i=0;;i++){
frase=(char*)realloc(frase,i+1);
if (frase==NULL){
printf("ERRORE PROBLEMA DI ALLOCAZIONE");
}
else{
frase[i]=getchar();
if(frase[i]==' ') np++;
else if(frase[i]=='\n'){
frase[i]='\0';
if(i!=0) np++;
break;
}
}
}
}

parole=new char*[np];
parole[0]=strtok(frase," ");
for(i=1;i<np;i++)
parole[i]=strtok(NULL," ");

ordinamento(parole,np);

printf("Parole ordinate:\n");
for(i=0;i<np;i++)
printf("%s\n",parole[i]);
system("pause");
}

void ordinamento(char **parole, int np){
int i,j;
char *temp;
for(i=0;i<np;i++){
for(j=np-1;j>i;j--){
if(strcmp(parole[j],parole[j-1])<0){
swap(&parole[j], &parole[j-1]);
}
}
}

}

void swap(char **p, char **q){
char *temp;
temp=*p;
*p=*q;
*q=temp;
}

[lucas87]

ps anche la stampa la faccio come funzione ma resta il problema dell'ordinam,ento con merge sort ricorsivo. chi me lo puo fare?



void stampa(char **parole, int np){
int i;
printf("Parole ordinate:\n");
for (i=0;i<np;i++)
printf("%s\n",parole[i]);
}

[mariom86]

Vedi un pò se questo può esserti di aiuto, io sto cercando di modificarlo:


** merge_sort.c
**
** Codifica in linguaggio C dell'algoritmo Merge Sort
** per l'ordinamento di un array di numeri interi.
**
**
** Pseudo-codifica dell'algoritmo
**
** MergeSort(A, p, r):
** 1. se p<r allora
** 2. q = (p+r)/2
** 3. MergeSort(A, p, q)
** 4. MergeSort(A, q+1, r)
** 5. Merge(A, p, q, r)
** End
**
** Merge(A, p, q, r)
** 1. siano i=p, j=q+1, k=0
** 2. fintanto che i<=q e j<=r ripeti:
** 3. se A(i)<A(j) allora B(k)=A(i), i=i+1, k=k+1
** altrimenti B(k)=A(j), j=j+1, k=k+1
** 4. se i<=q allora copia (A(i), ..., A(q)) in B
** altrimenti copia (A(j), ..., A(r)) in B
** 5. copia B in A
** End
**
** Marco Liverani (liverani@mat.uniroma3.it) - Aprile 2001
**
*/

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

#define MAX 300


/*
* Legge in input il numero n ed n numeri interi
* che memorizza nell'array. Restituisce il numero
* di elementi letti (n).
*/

int leggi_array(int V[]) {
int n, i;

printf("Numero di elementi: ");
scanf("%d", &n);
for (i=0; i<n; i++)
scanf("%d", &V[i]);
return(n);
}


/*
* Stampa in output l'array.
*/

void stampa_array(int V[], int n) {
int i;

for (i=0; i<n; i++) {
printf("%d ", V[i]);
}
printf("\n");
return;
}

/*
* Funzione Merge per la fusione di due
* componenti ordinate dell'array.
*/

void Merge(int A[], int p, int q, int r) {
int i, j, k, B[MAX];

i = p;
j = q+1;
k = 0;
while (i<=q && j<=r) {
if (A[i]<A[j]) {
B[k] = A[i];
i++;
} else {
B[k] = A[j];
j++;
}
k++;
}
if (i<=q) {
while (i<=q) {
B[k] = A[i];
i++;
k++;
}
} else {
while (j<=r) {
B[k] = A[j];
j++;
k++;
}
}
for (k=p; k<=r; k++)
A[k] = B[k-p];
return;
}


/*
* Funzione ricorsiva MergeSort.
*/

void MergeSort(int A[], int p, int r) {
int q;

if (p<r) {
q = (p+r)/2;
MergeSort(A, p, q);
MergeSort(A, q+1, r);
Merge(A, p, q, r);
}
return;
}


/*
* Funzione principale
*/

int main(void) {
int n, V[MAX];

n = leggi_array(V);
MergeSort(V, 0, n-1);
stampa_array(V, n);
return(1);
}

[lucas87]

ninete nenahce questo riesco a modificare, spero che qualcuno me lo dia gia bello che fatto perchè ormai mi sono rassegnato

[trallallero]

Non mi piace postare gli esercizi degli esami perchè non aiuta ad imparare ma nel tuo caso è diverso.
Tu ci hai provato parecchio, non hai chiesto la soluzione e basta.
Ed io al lavoro non sto facendo praticamente niente di C/C++ e visto che sto cercando lavoro mi fa piacere ripassare un pò del caro buon vecchio C di una volta :D
Ti convieve riscriverlo a modo tuo perchè la prof potrebbe mangiare la foglia ;) già da come è indentato ...

Non ho fatto l'ordinamento ricorsivo perchè non avevo visto che ti serviva così ma adesso continuo a cercare lavoro quindi non ho più tempo.
Spero tu capisca il tutto.
Ciao :)

ps: l'ho ritoccato prima di compilare (uso il Borland Builder quindi non ho testato le puts e la gets perchè ho usato l'output dell'oggetto Memo) quindi non so se ti darà errori in fase di compilazione.


char **Alloc( int Lines )
{
char **ppMat;
int y;

// ALLOCO UNA LISTA DI PUNTATORI
ppMat = (char **)malloc(10 * sizeof(char *));
if (!ppMat)
puts("errore alloc 1"), exit(1);

// PER OGNI PUNTATORE ALLOCO UNA STRINGA DI 128
for ( y = 0; y < Lines; y++ )
{
ppMat[y] = (char *)malloc(128 * sizeof(char));
if (!ppMat[y])
puts("errore alloc 2"), exit(1);

// AZZERO LA MEMORIA ALLOCATA (CONVIENE SEMPRE)
memset( ppMat[y], 0, 128 * sizeof(char) );
}
return ppMat;
}

int GetWordsCount( char *s )
{
int WordsCount = 0;

while ( s = strchr(s, ' ' )) // CERCA GLI SPAZI
{
s++; // SI POSIZIONA DOPO LO SPAZIO

while (*s && *s == ' ') // SALTA GLI SPAZI
s++;

if (!*s) break; // SE CI SONO SPAZI FINALI *s == \0

WordsCount++;
}
return WordsCount;
}

void OrderMat( char **ppMat, int Lines )
{
int y1,
y2;

char word[128];

for ( y1 = 0; y1 < Lines - 1; y1++ )
for ( y2 = y1 + 1; y2 < Lines; y2++ )
if ( strcmp( ppMat[y1], ppMat[y2] ) > 0 )
{ // CLASSICO SWAP - NON PERFORMANTE MA SEMPLICE
strcpy( word, ppMat[y2] );
strcpy( ppMat[y2], ppMat[y1] );
strcpy( ppMat[y1], word );
}
}

void PrintMat( char **ppMat, int Lines )
{
int y;

for ( y = 0; y < Lines; y++ )
puts(ppMat[y]);
}

void InsertWords( char **ppMat, char *pStr )
{
int i = 0,
y = 0;

while (*pStr && *pStr == ' ') // SALTA SPAZI INIZIALI
pStr++;

while (*pStr)
{
if (*pStr == ' ') // PRIMO SPAZIO: NUOVA PAROLA
y++, i = 0;

while (*pStr && *pStr == ' ') // SALTA SPAZI TRA LE PAROLE
pStr++;

if (!*pStr) // SE CI SONO SPAZI FINALI *s == \0
break;

ppMat[y][i++] = *pStr; // AGGIUNGE IL CARATTERE ALLA PAROLA ATTUALE
pStr++; // PROSSIMO CARATTERE DELLA STRINGA
}
}

int main()
{
char **mat, // ARRAY DI PUNTATORI
*str; // STRINGA DELLE PAROLE INSERITE

int Lines, // IL NUMERO DI PAROLE = RIGHE MATRICE
y ; // INDICE

str = (char *)malloc(4096 * sizeof(char));
if (!str)
puts("errore alloc str"), exit(1);

fgets( str, 4096, stdin );

Lines = GetWordsCount( str );

mat = Alloc(Lines);

InsertWords( mat, str );
OrderMat(mat, Lines);
PrintMat(mat, Lines);

// LIBERO LE PAROLE DELLA MATRIVE
for ( y = 0; y < Lines; y++ )
free(mat[y]);
// LIBERO LA LISTA DI PUNTATORI DELLA MATRICE
free(mat);
// LIBERO LA STRINGA
free(str);

return 0;
}


EDIT: dimenticavo ... lo swap per ordinare è assolutamente una schifezza nel senso che non è assolutamente performante.
La cosa migliore sarebbe swappare i puntatori non le stringhe ma ci avrei dovuto pensare un pò e non m'andava :D

[Capua]

Salutami Galesi e il canale E-O

[wingman87]

Ho seguito tutti i punti indicati da andbin (grazie), ora dovrebbe essere perfetto:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
char *frase,*newfrase,**parole,**newparole,*temp;
int np=0,i,j;

//INSERIMENTO FRASE CON ALLOCAZIONE DINAMICA
frase=NULL;
printf("Inserire frase...\n");
for(i=0;;i++){
if(i%32==0){
newfrase=(char*)realloc(frase,i+32);
if(newfrase==NULL){
free(frase);
exit(0);
}
frase=newfrase;
}
frase[i]=getchar();
if(frase[i]=='\n')
break;
}
frase[i]='\0';

//SPLIT DELLE PAROLE SEMPRE CON ALLOCAZIONE DINAMICA
i=0;
parole=(char**)malloc(sizeof(char*));
if(parole==NULL){
free(frase);
exit(0);
}
parole[i]=strtok(frase," \t");
while(parole[i]!=NULL){
i++;
newparole=(char**)realloc(parole,sizeof(char*)*(i+1));
if(newparole==NULL){
for(i=i;i>=0;i--)
free(parole[i]);
free(parole);
exit(0);
}
parole=newparole;
parole[i]=strtok(NULL," \t");
}
parole=(char**)realloc(parole,sizeof(char*)*(i)); //L'ULTIMA ZONA ALLOCATA NON MI E' SERVITA, LA DEALLOCO

//ORDINAMENTO PAROLE
np=i;
for(i=0;i<np;i++)
for(j=np-1;j>i;j--)
if(strcmp(parole[j],parole[j-1])<0){
temp=parole[j];
parole[j]=parole[j-1];
parole[j-1]=temp;
}

//STAMPA PAROLE
printf("Parole ordinate:\n");
for(i=0;i<np;i++)
printf("%s\n",parole[i]);

//DEALLOCO LA MEMORIA
for(i=np-1;i>=0;i--)
free(parole[i]);
free(frase);
free(parole);
system("pause");
return 0;
}