Codice dei programmi nella directory:
///File: EserciziVettoriDinamici.txt
1) Nella cartella Gennaio c'e' il file Ordina2.c (contiene bubble, select, insert e quicksort)
Modificare Ordina2.c in modo che lavori su un vettore dinamico anziche' statico.
2) Definito un vettore di puntatori a stringa:
char *testo[MAX];
caricare in testo il contenuto di un file di testo, allocando lo spazio esatto
per ogni riga di testo. Visualizzare a video il vettore testo. Liberare poi la memoria.
3)Definito un vettore di puntatori a parole:
char *parole[MAX];
ed un file contenente un certo numero di parole, tipo:
cane
casa
pane
albero
uomo
cammello
Caricare in parole il file allocando la memoria.
Ordinare alfabeticamente le parole
Salvare il vettore parole in un secondo file (che risultera' ordinato)
///(Fine file: EserciziVettoriDinamici.txt)
///File: ParoleEX3.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000
void bubblesort(char *parole[],int nparole)
{
int i,j;
for(i=0; i < nparole-1; i++)
for(j=i+1; j < nparole; j++)
if(strcmp(parole[i],parole[j]) >0 )
{ // scambio i pointer e non le stringhe!!!!
char *dep=parole[i];
parole[i]=parole[j];
parole[j]=dep;
}
}
int main() {
char *parole[MAX];
FILE *file_in, *file_out;
char buffer[256];
int n_parole = 0;
char nome_file[64];
int i;
// Apri file di input
printf("Nome file di parole (senza spazi)->");
scanf("%s",nome_file);
file_in = fopen(nome_file, "r");
if (file_in == NULL) {
printf("Errore: impossibile aprire file [%s]\n",nome_file);
return 1;
}
// Leggi e alloca memoria per ogni parola
while (fgets(buffer, sizeof(buffer), file_in) != NULL && n_parole < MAX) {
if (strlen(buffer) > 0) {
buffer[strlen(buffer)-1] = '\0'; // Rimuovi newline
parole[n_parole] = malloc(strlen(buffer) + 1); // alloco spazio
if (parole[n_parole] == NULL) { // non c'e' piu' memoria nello heap
printf("Errore di allocazione\n");
fclose(file_in);
return 1;
}
strcpy(parole[n_parole], buffer);
n_parole++;
}
}
fclose(file_in);
printf("Lette dal file %s %d parole\n", nome_file,n_parole);
// Ordina alfabeticamente con bubblesort
// Salva in file di output
file_out = fopen("ordinato.txt", "w");
if (file_out == NULL) {
printf("Errore: impossibile creare ordinato.txt\n");
return 1;
}
bubblesort(parole,n_parole); // ordino il vettore di pointer a parole
for (i = 0; i < n_parole; i++) {
fprintf(file_out, "%s\n", parole[i]);
printf("%3d: %s\n", i + 1, parole[i]);
}
fclose(file_out);
// Libera memoria
for (i = 0; i < n_parole; i++) {
free(parole[i]);
}
printf("\nParole ordinate salvate in 'ordinato.txt'\n");
return 0;
}
///(Fine file: ParoleEX3.c)
///File: parole.txt
cane
casa
pane
albero
uomo
cammello
gatto
fiore
///(Fine file: parole.txt)
///File: Ordina3.c
/*** Ordina 3: uso un vettore dinamico
Algoritmi di ordinamento
e prova tempi di esecuzione
al crescere dei dati in ingresso,
i vettori vengono riempiti con numeri pseudocasuali***/
/**** fai scegliere all'utente l'ordinamento che desidera */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#define MAX 1000000000 /*Massimo 1 mldo elementi*/
int *v; /// Vettore dinamico, lo allochero' con malloc
// Random(X) ritorna un numero fra 1 e X
int Random(int N)
{
static int primavolta = 1; // BOOLEANO
if (primavolta)
{
srand(time(NULL)); /* inizializzo il seme */
primavolta = 0;
}
return (rand() % N) + 1;
}
void riempi(int v[], int nelem)
{
int i;
for(i=0; i <nelem; i++) /*** riempilo con N numeri pseudocasuali fra 1 e N ***/
v[i]=Random(nelem);
}
void scambia(int v[], int px, int py)
{
int dep=v[px];
v[px] = v[py];
v[py] = dep;
}
void visualizza(int v[], int nelem)
{
int i;
int c;
for(i=0; i < nelem; i++)
{
printf("v[%d]=%d\n",i,v[i]);
if (i%24==0 && i !=0)
{
printf("Ancora (S/N)-->");
c = getchar(); /// pesco il carattere
getchar(); /// pesco l'invio
///printf("c=[%c] - asci[%d]\n",c,c);
if (c == 'N' || c == 'n')
return; /// mi fermo
}
}
}
void bubblesort(int v[], int dim)
{
int i;
int scambio; /// booleano a falso
do
{
scambio=0;/// falso
for(i=0; i < dim-1; i++)
if (v[i] > v[i+1])
{
scambia(v,i,i+1);
scambio=1; /// vero
}
}
while(scambio); /// giro finche scambio e' vero, cioe' ho fatto almeno 1 scambio
}
void bubblesort2 (int v[], int nelem)
{
int i, j;
for (i = 0; i < nelem -1; i++) //ciclo fino al penultimo
for (j = i+1; j < nelem; j++) //ciclo interno
if (v[i] > v[j])
scambia(v,i,j);
/***Non basta mai un solo ciclo for per ordinare un vettore***/
}
int pminimo (int v[], int x, int nelem)
{
int pm = x;
int i;
for (i = x; i < nelem; i++)
if (v[i] <v[pm])
pm = i;
return pm;
}
void selectsort (int v[], int nelem)
{
int i, pm;
for (i = 0; i < nelem -1; i++) // Trova indice del minimo da i in poi
{
pm=pminimo(v,i,nelem); // Scambia v[i] con v[pm]
if (pm != i)
scambia(v,i,pm);
}
}
void insertsort(int v[], int nelem)
{
int temp, i, j;
for (i = 1; i < nelem; i++)
{
temp = v[i];
j = i -1;
while(j >= 0 && v[j] > temp)
{
v[j +1] = v[j];
j--;
}
v[j +1] = temp;
}
}
int confronto (int v1[], int v2[])
{
return (v1[0] - v2[0]); //Ordine crescente
}
int main()
{
time_t inizio, fine;
double tempo_reale;
int i;
int nelem; /// numeri elementi del vettore
///int v[]={1,4,-4,-2,0,1,7 };
//system("bubblesort.png"); /// visualizza l'immagine
do
{
char invio; /// solo per invio pendente
printf("Quanti elementi metto nel vettore ?(max %d) ->",MAX);
scanf("%d%c",&nelem,&invio);
/*** chiedi all'utente quanti N elementi vuol mettere nel vettore ***/
}
while(nelem < 2 || nelem > MAX);
v = malloc(nelem*sizeof(int));
if (v == NULL)
{
printf("Errore: Non riesco ad allocare la memoria!\n");
exit(1);
}
riempi(v, nelem);
printf("Inizio Ordinamento QuickSort...\n");
inizio = time(NULL); // Inizio misurazione
qsort(v, nelem, sizeof(int), confronto); /*** ordina il vettore***/
fine = time(NULL); // Fine misurazione
tempo_reale = difftime(fine, inizio);
printf("Fine Ordinamento...\n%c",7);
printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);
/*** visualizza il vettore ordinato ***/
visualizza(v,nelem);
printf("Inizio Ordinamento BubbleSort...\n");
riempi(v, nelem);
inizio = time(NULL); // Inizio misurazione
bubblesort(v, nelem); /*** ordina il vettore***/
fine = time(NULL); // Fine misurazione
tempo_reale = difftime(fine, inizio);
printf("Fine Ordinamento...\n%c",7);
printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);
/*** visualizza il vettore ordinato ***/
visualizza(v,nelem);
/*** visualizza il tempo di ordinamento per N elementi ***/
printf("\n");
printf("Inizio Ordinamento BubbleSort2...\n");
riempi(v, nelem);
inizio = time(NULL); // Inizio misurazione
bubblesort2(v, nelem); /*** ordina il vettore***/
fine = time(NULL); // Fine misurazione
tempo_reale = difftime(fine, inizio);
printf("Fine Ordinamento...\n%c",7);
printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);
/*** visualizza il vettore ordinato ***/
visualizza(v,nelem);
printf("Inizio Ordinamento SelectSort...\n");
riempi(v, nelem);
inizio = time(NULL); // Inizio misurazione
selectsort(v, nelem); /*** ordina il vettore***/
fine = time(NULL); // Fine misurazione
tempo_reale = difftime(fine, inizio);
printf("Fine Ordinamento...\n%c",7);
printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);
/*** visualizza il vettore ordinato ***/
visualizza(v,nelem);
printf("Inizio Ordinamento InsertSort...\n");
riempi(v, nelem);
inizio = time(NULL); // Inizio misurazione
insertsort(v, nelem); /*** ordina il vettore***/
fine = time(NULL); // Fine misurazione
tempo_reale = difftime(fine, inizio);
printf("Fine Ordinamento...\n%c",7);
printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);
/*** visualizza il vettore ordinato ***/
visualizza(v,nelem);
free(v); // libero memoria
return 0;
}
///(Fine file: Ordina3.c)